搜索
南 京 邮 电 学 院 2003年攻读硕士学位研究生入学考试 数 据 结 构 试 题（参考答案） 一、填空题（每小题4分，共40分） 1.在循环队列中，队列长度为n，存储位置从0到n‐1编号，以rear指示实际的队尾元素，现要再次队列中插入一个新元素，新元素的位置是 (rear+1)%n . 2.设二维数组A的行和列的下标范围分别是：[ 0 : 8 ]和[ 0 : 10 ]，每个元素占2 个单元，按行优先顺序存储，第一个元素的存储起始位置为 b ，则存储位置为b+50处的元素为A [2][3] . 解答：loc( a[ i ] [ j ] )=loc( a[ 0 ][ 0 ] ) + ( i * n + j ) * k 其中n为数组的维数（此处为11），k为每个元素所占的存储单元数（此处为2） loc( a[ i ] [ j ] )=b + ( i * 11 + j ) * 2 3.已知字符串p=”abcabcabbac”，则next(3)和next(6)分别为 0，3 . 解答： 0 1 2 3 4 5 6 7 8 9 10 P a b c a b c a b b a C f(j) 0 1 1 1 2 3 4 5 6 1 2 next(j) ‐1 0 0 0 1 2 3 4 5 0 4 4.现有值分别为A，B，C的三个元素，可组成 30 个不同值的二叉树. 解答： 3!C5 * 3！= 30 .设有3 叉树中度为1，2和3的结点的数目分别为15，6，7，则度为0的结点数为 21 5. = nnnn nnnn=n2n3n + 1 n‐1 = n2n 6.设有向图有n个顶点，e条边，则对该图执行拓扑排序算法的时间复杂度为 O( n + e ) 解答： n 3n . 7.无有向回路 当采用拓扑排序算法求有向图的拓扑有序序列时，有向图具有 特性时， 5 该算法在输出图中全部顶点后终止. 8.设5阶B ‐ 树高度为2时（设根节点层次为1，不计入最下层空子树的层次，只考虑包含元素的B – 树节点的层次），则该树的最少关键字数目是. 解答： .设数组顺序存储线性表L = (a,a,…,a，假定删除任何一个元素的概率相同，则计算进行一次删除操作移动元素的次数的计算公式为 1 5阶B – 树，根节点最少要有2个孩子，其它节点至少要有（阶数/2取上整）= 3个孩子，形如： a c d e f 9nn12ni1nnnnn12 10.设有二叉树的先序遍历和中序遍历的结点次序分别为：A，F，E，G，C，B，D，H和E，F，G，C，A，D，B，H，则对其进行后序遍历的结点序列次序为： E，C，G，F，D，H， B，A . 答： 、解答下列各题（每题8分，共40分） .设电文由6个字符A，B，C，D，E，组成，它们在电文中的出现次数分别为：10，4，8，3，2，7，试画出用于编码的哈夫曼树，并列出每个字符的编码。 答： 解A FB 二1F解 A(10): 11 D(3): 1011 B(4): 100 E(2): 1010 C(8): 01 F(7): 00 EGDHC 0 0 1 10001113415 19789105423 2.（暂缺） .（暂缺） .现有元素组成的数据元素集合{1，2，3，4，5，6，7}，请分别给出使下列排序算法产生情况时的输入数据实例：选择排序，冒泡排序，快速排序，直接插入排序。 选择排序：最好情况（1，2，3，4，5，6，7），最坏情况（1，2，3，4，5，6，7） 插入排序：最坏情况（1，2，3，4，5，6，7），最坏情况（7，6，5，4，3，2，1） 解释选择冒泡快速最坏情况，分割元素将序列分割成一个空的子序列 趟都没有数据交换 7}，请分别给出使下列排序算法产生情况时的输入数据实例：选择排序，冒泡排序，快速排序，直接插入排序。 选择排序：最好情况（1，2，3，4，5，6，7），最坏情况（1，2，3，4，5，6，7） 插入排序：最坏情况（1，2，3，4，5，6，7），最坏情况（7，6，5，4，3，2，1） 解释选择冒泡快速最坏情况，分割元素将序列分割成一个空的子序列 趟都没有数据交换 3 4最好和最坏最好和最坏解答： 解答： 冒泡排序：最好情况（1，2，3，4，5，6，7），最坏情况（7，6，5，4，3，2，1） 快速排序：最好情况（4，1，3，2，6，5，7），最好情况（1，2，3，4，5，6，7） 冒泡排序：最好情况（1，2，3，4，5，6，7），最坏情况（7，6，5，4，3，2，1） 快速排序：最好情况（4，1，3，2，6，5，7），最好情况（1，2，3，4，5，6，7） 直接直接： ： 排序最好情况，最坏情况都要进行n‐1趟，每趟交换一次 排序最好情况，最坏情况都要进行n‐1趟，每趟交换一次 排序最坏情况，有序的，进行一趟，没有交换，最坏情况，进行n‐1趟 排序最坏情况，有序的，进行一趟，没有交换，最坏情况，进行n‐1趟 排序最好情况，分割元素将序列分割成两个大小一样的子序列 排序最好情况，分割元素将序列分割成两个大小一样的子序列 直接插入排序，最好情况，序列是有序的，进行n‐1趟，但是每直接插入排序，最好情况，序列是有序的，进行n‐1趟，但是每 5.完成下列操作： 5.完成下列操作： （1）补充完整下列败方树； （1）补充完整下列败方树； （2）画出输出全局优胜者，并重构以后的败方树。 （2）画出输出全局优胜者，并重构以后的败方树。 10 9 19 6 8 128816 14 22 24 1516219618 解答： 输出全局优胜，重构败方树 、解答下列各题（12分） .试说明什么是好的散列函数。 2.设散列表的地址范围是[ 0 …函数公式。 .试说明线性探测法的不足之处。 M=11，并采用线性探测法处理冲突，若输入一组记录，，121，77，80，35），请画出所构造的散列表。 件：一是能快速计算，二是具有均匀性。 加。 先求出各个关键字的散列函数值 35 14 22 24 1516219618 10 9 19 6 8 128816 10 19 1288 9 16 8 6 补充完整后 8 9 16 15 88 19 10 12 10 9 19 158 128816 14 22 24 16219618 三1 M‐1 ]，写出除留余数法的散列34.现采用除留余数法计算地址，取其关键字依次为：（60，78，63解答： （1）一个好的散列函数满足以下条（2）散列函数为：h(key) = key % M （3）线性探测法缺点是：容易产生“聚集”（clusters）现象，从而导致搜索时间增（4）key 60 78 63 121 77 80 k(key) 5 1 8 0 0 3 2 构造成的散列表 0 1 2 3 4 5 6 7 8 9 10 121 78 77 0 360 63 85 四、解答列各题12分） 二叉下图示 请画出该树的先序线索树。 请画出该树所对应的森林。 存储结构。 下（设有树如所1.. .该树对应的森林为： 二叉树对应的森林 .该森林的双亲表示法的存储结构为：（关键字顺序按提设的先序遍历次序存放） 0 B ‐1 BACDE23.请画出该森林的双亲表示法的 解答： 1.该树的先序线索树为： 二叉树的先序遍历序列为BADEC B 2 31 A 0 2 D 0 3 E 2 4 C ‐1 五、分）设AE网如所示，各事件可能的最早发生时间和允许的最迟发生时间，以及关键活动和关路径长度（10 O下求键及其。 ACDENULLBCADE 解答： OE网的关键路径计算结果（1），事件的最早发生时间，事件的最晚发生时间 项目 V V V V V V 答： OE网的关键路径计算结果（1），事件的最早发生时间，事件的最晚发生时间 项目 V V V V V V 245013a=6a=2a=4 a=3a=2 a=3 a=3 a=4 a=8 AAearliest( i ) 0 3 7 15 10 21 latest( i ) 0 3 7 15 13 21 AO关键路径计算结果（2），活动的最早发生时间，活动的最晚发生时间 项目 aa a aa a a a a E网的 early( k) 0 0 3 7 10 15 3 10 7la5 0 11 10 18 15 te( k ) 3 13 7关键路径 √ √ √ √ 关键路径为aaaa，路径长度为21 六、（16分） 算法实现在一个带表头结点的单链表上的简单选择排序算法。算法scal++语函数或过程描述。链表中每个结两个datalink。要求说准述你用的单链存储表。 解答： mplateclass T t; ate: data; *link; lass HeaderListT; 表头结点的线性表类： mps T NodeT *first; 设计一个，用Pa语言或者C/C言的（）单的点有域：和先使用类型明确描所使表示结点类： teclass HeaderListemplateclass T class Node { priv T NodeT friend c}; 带telateclasclass HeaderList { private: int length; st(); rList(); bool IsEmpty()const(return length==0;); th()const; t(ostream&out)const; d SelectSort(); tT::SelectSort() q=first‐link; for(;q;q=q‐link) ta; for(p=q‐link;p;p=p‐link) p‐data) { e=p‐data; r=p; } ta; “forgetful version”的对半查找算法。 为n的有序表顺序存储在一维数组A中，数组A的下标从0开素x在表中，则返回x在数组中的下标，否则函数返回‐1.该函数在执行次查元素和A中下标为mid的元素之间的比较后，即使比较相等也不会终止算法，继（设其上、下界下标为low和high）划分成两个子表。前一个子表的范围是low到id（含mid），后一个子表的范围是mid+1到high，直到待查子表中只剩下一个元素时，再与表中元素是否相等，从而确定搜索成功与失败。 归函数（或过程）。要求先使 public: HeaderLi ~Heade int Leng ...... void Outpu voi}; 实现简单选择排序： templateclass T void HeaderLis{ NodeT *p,*r,*q; { T e=q‐da r=q; if(e e=q‐da q‐data=r‐data; r‐data=e; } } 七、（20分） 设计一种被称为算法描述如下：设长度始编号，如果待查元一待续将原表m去判定待查元素（1）请写出上述算法的Pascal语言或C/C++语言的非递用类型说明准确描述你所使用的有序表的顺序结构。 （2）设以数组A存储一个长度为10的有序表，试画出以你的算法对A进行对半查找的二叉判定树，该二叉判定树上每个圆形结点代表一次元素间的比较，方形结点代表算法终止（成功或失败）。 解答： 线性表类： templateclass T class LinearList { pub