2006年南邮考研数据结构考研试卷

南京邮电大学 2006年攻读硕士学位研究生入学考试    数据结构   试题 考生注意：本试卷共4页。所有答题均写在答题纸上（包括单选和填空题），请务必准确标明所答题的题号和填空号。  一、单选题（每题3分，共30分） 1.可以使用大O记号表示一个算法的时间复杂度。下列标识中不正确的是___D___。 A.On     B. O C. Onlogn   D. nn2nnlogn2nn nnlognnnlognOlogn 术语中，_____B 2.下列_____与数据的存储结构无关。 A.循环队列   B. 堆栈   C. 散列表   D. 单链表 新结点。 结点的单循环链表，一个链表指针指向表头结点 个结点 个节点 配第一趟失配后下一趟匹配开始时，子串指针指示的字符是____A 3.设线性表非空，采用下列_____D_____所描述的链表可以在O(1)时间内在表尾插入一个A.带表头结点的单链表，一个链表指针指向表头结点 B.带表头C.不带表头结点的单链表，一个链表指针指向标的第一D.不带表头结点的单循环链表，一个链表指针指向表的第一 4.设主串为“abceabceyabceabceab”，字串为“abceabcea”。则在KMP匹____。 A.a   B. b   C. c   D. e  5.二叉树中第5层上的结点个数最多为____C____，假定根节点层次为1. A.8   B. 15  C. 16  D. 32 回时打印当前顶点，则输出的顶点序列是____C 6.用DFS遍历一个有向无环图，并在DFS算法退栈返____。    D. 按顶点编号次序的 7.A. 拓扑有序的   B. 无序的 C. 逆拓扑有序的 下面____A____算法可于无向图的所有连通分量用求 .广度优先遍历   B. 拓扑排序 叶结点的8路合并胜方树。在输出一个元素后，将有一个新元素补充到相应的叶结点中。在重构的胜方树中，应有____DAC. 求最短路径   D. 求关键路径  8.设有以元素10，9，20，6，8，23，21，17为____个杂度为____D元素需要修正。 A.1   B. 2   C. 3   D. 4  9.在一棵二叉搜索树上搜索一个元素的平均时间复____。 A.On   B. O(n)   C. Onlogn   D. Ologn B 10.下面关于倒排文件的说法中正确的是______。 A. 倒排文件是对主关键字建立索引的B.倒排文件是对次关键字建立索引的 A）开始顺序存放，每个元素占2个字节。元素A[4,4]在行优先方式下的存储地址为____(1)C.倒排序文件的优点是维护简单 D.采用倒排文件是为了节省存储空间  二、填空题（每题6分，共48分） 1.设有二维数组A[0…5,0…6]，从地址Loc（____，在列优先方式下的存储地址为____(2)____。 解答： (1)Loc(A) + 2*7*4 + 2*4 = Loc(A) + 64 (2)Loc(A) + 2*6*4 + 2*4 = Loc(A) + 56  )*C – E/D，其后缀形式为____(3)2.已知一算术表达式的中缀形式为(A +B____。另有一算术0至9的一位数。此表达式的值为____(4)表达式的后缀形式为2 6 4 ‐ * 2 /，每个操作数均为____。  = 2  夫曼树实现对字符集{F,G,H,I,J}的哈夫曼编码。 文为：011101011101，则利用此哈夫曼树进行译码得到的电文为____(5)解答： (3)A B + C * E D / ‐  (4)2*(6 – 4) / 23.使用如图1所示的哈已知编码后得到的码JI H GF1 0 1 1 0 01____。设该字符集中各字符的使用频率各不相同，则其中使用频率最小的两个字符应当是____(6)____。 解答： (5)G I H J G (6)I J 0图1 2所示。则所有拓扑有序序列为____(7)4.设有向图如图可能的____。  ③ ⑥  ⑤ ② ③ ⑥  5.已知对一棵二叉树的先序和中序遍历的结点次序可以唯一确定该二叉树。设某棵二叉树的先 ABCDEFG 和 BDCAEGF，则其后续次序为____(8)6 4 854322124356解答： (7)① ② ④ ⑤ ③ ⑥ ① ④ ② ⑤① ④图2序和中序次序分别为____。此外，已知后序和____(9)____序遍历次序也可以唯一确定一棵二叉树。 解答： (8)D C B G F E A (9)中  本原因是____(10)6.引入B‐ 树的最根____。在有n个元素的访问外存的次数至多为____(11)m阶 B‐ 树中，搜索一个元素的算法需要____。 解答： (10)为了减少外搜索的磁盘访问次数，为修改过程提供简单的平衡算法 (11)log取上整N1  7.分别采用直接插入排序和快速排序方法对下面所列出的四个序列进行排序（由小到大）。直接插入排最长的序列是____(12)使得序时间____，使得快速排序时间最短的序列是____(13)____ A.10，20，30，40，50，60，70 ，30，50，70，60 辑结构是指____(14)_B.70，60，50，40，30，20，10 C.40，10，30，20，60，50，70 D.40，20，10解答： (12)B (13)C D  8.数据的逻___，数据的存储结构是指____(15)____。  据逻辑关系的描述 (15)数据在存储器中的存储方法 三、解答题（每题8分，共40分） 阵实现矩阵快速转置算法时，需要附设两个一维数组，设矩阵第col列中非零元素个数。现有稀疏矩阵如右图所示 示的示意图； 解下列关于散列表的问题 )除法（除留余数法）散列函数是最常用的一种散列函数，请写出散列函数的一般形式。 )设有散列表Ht如下，现采用二次探查法解决冲突。已知H(38) = 5，H(25) = 3，请将当位置。请在答题纸上画出完整的插入两个新元素后的散1 2 3 4 5 6 7 8 9 10 解答：(14)对数 1.当采用行三元组表存储稀疏矩为num和k，其中num[col]表示原0   12  0   0   0 (1)请给出它的转置前后的行三元组表‐1   0   13  18  0 (2)计算数组num和k的元素值。   11  20  0   0   0 0   0   0   0   0 0   0   ‐5   0   0   0   0   0   0   0 2.求(1(238和25依次插入表中适列表。 0   13 14  16 17 18    Ht 3.已知AOE网如第二题第4小题图2所示。 (1)计算每个顶点代表的事件可能的最早发生时间。(2)列出计算顶点代表事件允的最发生时计算关键路径长度，并列出关键路径的顶点序列。.设有向图如图3所示， 连通分量。 、算法设计题（共32分） 题要求： )只允许使用pascal，C和C++语言中的一种语言描述数据结构和算法。 上以实现的过程或函数。 )要求对算法的每一条语句加明确注释。 借助于一个一维数组，设为第k个元素小的元素个数。因此count[k]也表明了第k个元素在有序序列中的位置。请设计一个算法计算数组count的值。分析此算最好和平均情况时间复杂度。  2.递归用普通二叉链表存储的二叉树。二叉链表的个结点有三个域：lChild，rChild和element。算法返回所构造的新二叉树的根结点地址。  的计式和计结果  ，22。请画出每插入一个元素后4所的许迟间算算。(3) 4.从空二叉平衡树开始，依次插入：19，25，43，16，18的二叉平衡树。  51(1)画出邻接表存储表示的示意图； (2)求它的全部强02   34 图3四 解(1(2)算法描述中不允许直接调用教材(3 1.（14分） 设有n个元素保存在一维数组A中。枚举排序的基本思想是count。count[k]记录在初始序列A中，比法的最坏、（18分） 设一棵n个结点的完全二叉树采用顺序存储结构，保存在一维数组A中。试设计一个算法，复制该完全二叉树，得到一棵新的采每