数据结构精选考研试题(2)

写出akm(2,1)时调用时变化过程与执行结果。

3. 对于正整数A、B，说明下面程序段定义了什么函数功能，要求重写程序段，使之完成原函数功能，且执行时间仅可能短。 Unsigned int f(a,b) int a,b;

{if (a*b==0) return (a+b)

else return(f(b-(b/a)*a,a); (注：b/a相当整除) }

4. 写出在中序线索树BT中找结点X的后继结点的函数过程。

5.对以下关键字序列建立哈希表（jan,feb,mar,apr,may,jun,jul），哈希函数为H（K）=关键字中第一个字母在字母表中的序号）MOD 7，用线性探测再散列法或链地址法之一处理冲突，要求构造一个装填因子为0.7的哈希表，并求出等概率情况下查找成功与不成功的平均查找长度。

四、有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲

得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。[10分]

1． 一棵树采用孩子-兄弟方式存放，结点结构为

fch dansleta ib vel

其中fch 表示指向第一个孩子，nisib表示指向下一个兄弟, level表示结点层次。

设根结点层次为1，其它以此类推，编写一算法，将树中所有结点层次值置入相应level域。[10分]

六、以顺序存储结构表示串,设计算法,求串S中出现的第一个最长重

复子串及其位置并分析算法的时间复杂度. [10分]

七、 编写程序，要求完成：

建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。

在此链表上实现对二进制数加1的运算，并输出运算结果。

分]

[10[注]：编写程序可用PASCAL或C语言；算法描述可采用类语言，加上必要注释； 一、解释和简答下列问题：（20分）

1） 算法的定义和特性 2） 抽象数据类型

3） 广义表与字符串属于线性表的理由

4） 封装

5） 排序算法的稳定性 6） 结构化程序设计 二、写出要求结果：（30分）

1．已知一二叉树中序序列为DBGEAFC，后序序列为DGEBFCA，给出其对应的二叉树。 2．给定权值{8，12，4，5，26，16，9}，构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。

1． 有一线性表，要求重新排列，使所有的正数均在非正数之前，要求用最小交换次数

实现，你认为应采用什么方法？

4．只想得到N个元素序列中第K个最大元素之前的部分递减有序序列（K<

5．在地址空间为0~12的散列区中，对以下关键字序列建哈希表：（Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct）。用线性探测法处理冲突，求出在等概率的情况下查找成功与不成功的平均查找长度。

6．下面给出求N价hanoi塔的过程：

PROCEDURE hanoi(n：integer；x,y,z：char)；

begin

if n=1 then move(x,1,z) else [hanoi(n-1,x,z,y)；

move(x,n,z)；

hanoi(n-1,y,x,z)] end

请写出执行hanoi(3,a,b,c)时递归过程的实在参量变化过程及move的搬动过程。

三、数学归纳法证明非空满K叉树的叶子结点数目为(K-1)N+1，其中N为分支结点数目。

（10分） 四、编写程序，判断一带头结点的双向链表是否对称，对称是指表中各元素满足ai=an-i+1 结点结构为如下：(10分) next dada prior

五、有一个由英文书目构成的文件（书名不定长度，以“；”为分割符）；读入该文件，对这一书目单按字典排序，将结果以文件方式存储。编程实现之。（10分）

六、二叉树按链表方式存放，且树中结点的关键字均不同。写一个判别给定二叉树是否为

二叉排序树的非递归算法。（10分）

写一个算法，确定一个N个顶点的无向图是否包含回路，此算法的时间代价应为O（N） （10分）

[注]：编写程序可选用盘Pascal 或C语言，算法描述可选用类语言，必要时加上注释

一、简答下列问题：

1． 结构化程序设计

2． 参数传递的常用方式及含义

3． 数据类型

4． 几种基本数据结构的名称及特征 5． 算法定义与性质 6． 二、写出要求结果

1． PROGRAM PF(OUTPUT);

VER T,M:INTEGER;

FUNCTION F(N:INTEGER):INTEGER; BEGIN M:=N+M;F:=M END

BEGIN

M:=10;T:=(M+1)*F(10);WRITELN(T); M:=10;T:=F(10)*(M+1); WRITELN(T); M:=10;T:=M*F(10)+F(10); WRITELN(T);

END.

写出程序输出结果，说明为什么T的树出结果不同。

2． 有过程定义如下：

PROCEDURE PRIT(N:INTEGER); BEGIN

VAR N1:INTEGER;

N1:=TRUNC(N/10);{TRUNC(x)表示取x的整数部分} S:=S*10+(N MOD 10);

IF N1<>0 THEN PRIT(N1); WRITELN(N MOD 10)

END;

问：置S初值为0，用PRIT（12345）调用此过程，写出打印结果；当执行完此次调用后，S值是多少？

3． 给定一组权值（7，18，3，32，5，26，12，8），构造

一棵哈夫曼树，并计算带权路径长度。

4． 将树转换成二叉树

5． 对给定以下关键字序列（Jan,Feb,Mar,Apr,May,

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构精选考研试题(2)在线全文阅读。