南京航空航天大学1997考研题
说明：
统考生做一～九、十题
单考生做一～九、十一题
题后注有用程序实现的可用任意语言编写
一、判断下列命题是否正确(10分)
(1) 链表中的头结点仅起到标识的作用。
(2) 顺序存储结构的主要缺点是不利于插入或删除操作。
(3) 对任何数据结构链式存储结构一定优于顺序存储结构。
(4) 必须把一般树转换成二叉树后才能进行存储。
(5) 通常实用队列来处理函数或过程的调用。
(6) 堆肯定是一棵平衡二叉树。
(7) 拓扑排序算法仅能适用于有向无环图。
(8) 排序算法中的比较次数与初始元素序列的排列无关。
(9) Hash表的平均查找长度与处理冲突的方法无关。
(10) 倒排文件是对次关键字建立索引。
二、设一棵二叉树的先序、中序遍历序列分别为(10分)
先序遍历序列： A B D F C E G H
中序遍历序列： B F D A G E H C
(1) 画出这棵二叉树。
(2) 画出这棵二叉树的后序线索树。
(3) 将这棵二叉树转换成对应的树(后森林)。
三、设有一个无向图(8分)
(1) 画出其邻接表。
(2) 在该邻接表基础上求DFS的顶点序列 。
(3) 在该邻接表的基础上求BFS的顶点序列。
四、设有两个链表，ha为单项链表，hb为单向循环链表。编写算法，将两个链表合并成一
个单向链表，要求算法所需时间与链表长度无关。(8分)
五、简要叙述堆排序的算法思想。并对如下关键字序列(3，8，85，12，37，50)按堆排序算法进行从小到大排序，要求画出排序全过程的示意图。(10分)
六、设有一个数组中存放了一个无序的关键序列K1、K2、· ·Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。
(注：用程序实现) (12分)
七、设有一个带头结点的单向链表，数据项递减有序。写一算法，重新排列链表，使数据项递增有序，要求算法时间复杂度为O(n)。(注：用程序实现) (12分)
八、编写算法，将自然数1～n 按“蛇形”填入n×n矩阵中。例(1～4 )如图所示：
九、设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。如果是，输出子串所在位置(第一个字符)，否则输出0。
(注：用程序实现) (10分)
十、已知二叉链表存储结构，root指向其根结点，，编写算法，求二叉树的深度。
(注：用程序实现) (10分)
十一、求a的平方根可用公式Xn=(Xn-1+a/Xn-1)/2，X0取意值(X0=1)。编写算法求a，直到误差小于e。 (注：用程序实现) (10分) | 
