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

完全二叉树定义为：深度为K、具有N个结点的二叉树的每一个结点都与深度为K的满二叉树中编号从1至N的结点一一对应（此题以此定义为准）。[12分] 六、给定一公园的导游图，自给适当的数据结构，编写算法实现下列要求：

游客从大门进入，选择一条最佳路线，使游客可以不重复的游览各景点，最后回到大门。[10分]

答案请答在答题纸上，答在本试题上的答案一律无效

[注] 编写程序可选用PASCAL 或 C 语言

算法描述采用类语言，算法应加上必要的注释，所有答案均要求写在答题纸上

一、简答问题：[30分]

1．结构化程序设计（目的、构成与方法）

2．简述栈、队列、串、数组的共同点和不同点，它们属于线性表原因 3．简述面向对象方法的特点

4．线性结构与非线性结构的差别 5．算法特性与算法时间复杂度

二、选择题： [20分]

1． 已知一算术表达式的中缀形式为A＋B *C-D/E，后缀形式为ABC *+DE/-，其前缀形式为( )。

A. –A+B*C/DE B. –A+B*CD/E C.-+*ABC/DE D.-+A*BC/DE

2． 利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行（ ）元素间的比较。 A．4次 B．5次 C. 7次 D．10次

3．在有n个叶子结点的哈夫曼树中，其结点总数为 ( ) 。 A、不确定 B、2n C、2n+1 D、2n-1

4． 若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是:

A．快速排序 B.堆排序 C.归并排序 D.直接插入排序

5．若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列( )

A. 存在 B. 不存在

6． 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 ( )

A. n B. 2n－1 C. 2n D. n-1

7． 下述二叉树中，哪一种满足性质：从任一节点出发到根的路径上所经过的节点序列按其关键字有序 ( )

A.二叉排序树 B. 哈夫曼树 C. AVL树 D. 堆

8． 已知待排序的n个元素可分为n/k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )

A. O（nlog2n） B. O(nlog2k) C. O(klog2n) D. O(klog2k) 9．数组A[1..5,1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续内存单元中，则A[5，5]的地址是 ( )。 A、1140 B、1145 C、1120 D、1125

10. 在有n个叶子结点的哈夫曼树中，其结点总数为( )。 A、不确定 B、2n C、2n+1 D、2n-1

三、写出要求结果：[50分]

1． 下列C与PASCAL函数的功能相同

有C函数定义如下： 有PASCAL过程定义如下：

int gc(:int m, n) FUNCTION GC(M,N:INTEGER);INTEGER { BEGIN

if (n==0 ) return(m); I F N=0 THEN GC:=M

else retun (n，m /n); ELSE GC:=GC(N，M MOD N) } END

写出此函数功能，并改写它，使其执行速度仅可能的短。

2．给出求N阶hanoi塔的函数定义如下：

hanoi(int n，char x, char y, char z)；

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

move(x,n,z)； hanoi(n-1,y,x,z)； } }

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

3．在前序线索树中，要找出X结点的后继结点，请写出相关语句 Ltag Lc Data Rtag Rc

4．一棵非空的二叉树其前序序列与后序序列正好相反，给出满足条件的二叉树。

5．在数轴上有n个彼此不交的相邻区间，每个区间下、上界都是整数，按区间位置从左到右依次编号为1~N。试问：要查找某个给定值x所在区间，你认为应选择什么方法查找最快，简述原因。 6．已知关键字序列为：（75, 33, 52, 41, 12, 88, 66, 27）哈希表长为10，哈希函数为： H(K)=K MOD 7, 解决冲突用线性探测再散列法，要求构造哈希表，并求出等概率下查找成功与不成功的平均查找长度。

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

8．已知二叉排序树，现要求得到结点的递减有序的排列，请说明实现此要求应

采用的方法思路。

四、编写程序，求字符串中的字符平台。

一个字符串中的任意一个子序列，若子序列中各字符均相同则称为字符平台。编程要求；输入任意一字符串S时，输出S中长度最大的所有字符平台的起始位置及所含字符，注意字符平台有可能不止一个。[10分]

五、编写算法，要求完成：

已知二叉树采用二叉链表方式存放，要求对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的

编号小于其右孩子的编号，请回答采用什么次序的遍历方式实现编号？并给出在二叉树中结点的数据域部分填写实现如上要求编号的非递归算法。[13分]

六、编写算法：

（1） 要求二叉树按二叉链表形式存储，写一个建立二叉树的算法。 （2）编写计算二叉树最大宽度的算法。

二叉树最大宽度指：二叉树所有层中结点个树的最大值[15分]

七、编写算法：

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

fch danslevta ib el 其中fch 表示指向第一个孩子，nisib表示指向下一个兄弟, level表示结点层次。设根结点层次为1，其它以此类推，

编写一算法，将树中所有结点层次值置入相应level域，并要求由根开始逐层输出树中的各条边，边输出格式为（Ki,Kj）。 [12分] 例： A

B C D 输出为： AB,AC,AD,BE,BF,CG

E F G