中国科学技术大学 一九九八年招收硕士学位研究生入学考试试题 试题名称:程序设计 要求: 算法设计题目要求写注解,否则扣分. 写出正确的设计思想和伪代码给分. 填空(15分,每空1分) n个顶点的无向图的邻接矩阵至少有____非零元素;n个顶点的有向图是强连通图至少有____条边. 折半查找的存储结构必须是_____,并且其中存储的关键字必须____;查找成功与不成功的最大比较次数是____.(设关键字总数为n) 设广义表L=( ( ),( (y), B), L),则L的长度是______,深度是_____,head(L)是______, tail(L)是______. 设高度为h的二叉树无度为1的结点,则此类二叉树至少有____个结点,至多有_____个结点. 若要将内存中建立的二叉树(不一定是完全二叉树),写到磁盘文件中,则采用_____表示为宜. 假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行___次探测. 在基于关键字比较且时间为O( nn)的排序中,若要求排序是稳定的,则可选用___排序;若要求就地排序(及辅助空间为O(1)),则可选用___排序 . 请在下列各题中选择一个正确的答案(每个选择2分,共20分) 在一颗m阶的B树中: 若在某结点中插入一个新关键字而引起结点的分裂,则该结点中原有关键字的个数是: (a) m个 (b) m – 1个 (c) m – 2 个 若在某结点中删除一个新关键字而导致结点的合并,则该结点中原有关键字的个数是: (a) 个 (b) 个 (c) 个 用ISAM组织文件适合于 (a) 磁带机 (b) 磁盘 是否存在这样的二叉树,对它采用任何次序的遍历,其遍历产生的节点序列相同? (a) 存在 (b) 不存在 若一个有向图的邻接矩阵中,主对角线以下的元素均为零,则该图的拓扑有序序列: (a) 不存在 (b) 存在 对外部排序的k路平衡归并,采用败者树时,归并效率与k (a) 有关 (b) 无关 设二叉排序树中关键字由1至1000的整数构成,现要检索关键字为363的结点,下述关键字序列哪一个不可能是二叉排序树上搜索到的序列? 2, 252, 401, 398, 330, 344, 397, 363 924, 220, 911, 244, 898, 258, 362, 363 952, 202, 911, 240, 912, 245, 363 2, 399, 387, 219, 266, 382, 381, 278, 363 已知待排序的n个元素可分为n/k个组,每个组包含k个元素,且任一组内的各元素均分别大于前一组的所有元素并小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为: (a) O(nn) (b) O(nk) (c) O(kn) (d) O(kk) 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序: (a) 二叉排序树 (b) 哈夫曼树 (c) AVL树 (d) 堆 将两个各有n个元素的有序表归并成一个有序表,其最多的比较次数是: (a) 2n (b) n (c) 2n – 1 (共15分)Fibonacci树是一种特殊的二叉树,下面给出构造该树的一种算法: procedure FibonacciTree(d:integer ; Var T:binarytree) { //d是 Fibonacci树的深度 if d=0 then T := nil else { new(T); if d=1 then { T^.leftptr:=nil; T^.rightptr:=nil } else { // d>=2 FibonacciTree(d – 2, T^.leftptr); FibonacciTree(d – 1, T^.rightptr); } } } (1) 画出深度为4的Fibonacci树(即用d=4调用上述算法的结果) (7分) (2) 从你画的树中分析深度d的Fibonacci树中结点总数和Fibonacci数的关系.Fibonacci数定义如下:  = 1 ,  = 1  =  +  n>1 (3) 你所画出的Fibonacci树是否为平衡二叉树?若是,它是否为同样深度的平衡二叉树中节点数目最少的一种? (4分) 证明若二叉排序数中的一个结点存在两个孩子,则它的中序后继节点没有左孩子, 则它的中序前趋节点没有右孩子. (10分) (共25分) 设数组A[1..n]含有n个互不相同的数,若 i<j 且A[i] > A[j] , 则偶对(i,j)称为A的一个逆. (1) 列出数组[3, 4, 9, 7, 1]的五个逆; (2分) (2) 元素取自集合{1, 2, 3, … n } 的所有数组中,哪一个数组具有最多的逆,其中数是多少? (3分) (3) 插入排序的运行时间和数组中逆的数目有何关系? (3分) (4) 写一个算法将两个有序段 r[low..mid] 和 r[mid + 1..high] 归并成一个有序段,并要求在归并的同时求出归并前r[low..high]中逆的总数. (15分) (5) 利用(4)中的归并算法来对r[1..n]进行归并排序,并同时求出原数组r[1..n]中逆的总数,其时间复杂度是多少? (2分) (共15分) 一个有向图G=(V,E)的平方图 满足下述性质: (u,w) ∈  当且仅当存在某个顶点v ∈ V, 使得(u,v) ∈ E 且 (v,w) ∈ E. 写一个算法从给定的G求出 , G 和 可 分别用两个邻接表表示.