北航数据结构与程序设计方案真题-北航真题及答案.pdf

2013 年 “数据结构与 C 程序设计 ”(代码 991) 试卷 一、单项选择题 （本题共 20 分，每小题各 2 分） 1 ．对于长度为 n 的线性表，建立其对应的单链表的时间复杂度为 ( ) 。 A ．O(1) ； B ．O(log2n) ； ．O(n) ； D ．O(n2) 。2 ．一般情况下，在一个双向链表中插入一个新的链 结点， ( ) 。 A ．需要修改 4 个指针域内的指针； B ．需要修改 3 个指针域内的指针； C ．需要修改 2 个指针域内的指针； D ．只需要修改 1 个指针域内的指针。 3 ．假设用单个字母表示中缀表达式中的一个运算数 ( 或称运算对象 ) ，并利用堆栈产生中缀表达式对应的 后缀表达式。对于中缀表达式 A+B*(C/D-E) ，当从左至右扫描到运算数 E 时，堆栈中的运算符依次是 ( ) 。 ( 注：不包含表达式的分界符 ) A ．+*/- ； B ．+*(/- ； C ．+*- ； ．+*(- 。 4 ．若某二叉排序树的前序遍历序列为 50,20,40,30,80,60,70 ，则后序遍历序列为 ( ) 。 A ．30,40,20,50,70,60,80 ； B ．30,40,20,70,60,80,50 ； C ．70,60,80,50,30,40,20 ； D ．70,60,80,30,40,20,50 。 5 ．分别以 6, 3, 8, 12, 5, 7 对应叶结点的权值构造的哈夫曼 (Huffman) 树的深度为 ( ) 。 A ．6 ； B ．5 ； C ．4 ； D ．3 。 6 ．下列关于图的叙述中，错误的是 ( ) 。 A ．根据图的定义，图中至少有一个顶点； B ．根据图的定义，图中至少有一个顶点和一条边 ( 弧 ) ； C ．具有 n 个顶点的无向图最多有 n#61620 。(n-1)/2 条边； D ．具有 n 个顶点的有向图最多有 n#61620 。(n-1) 条边 ( 弧) 。 7 ．若在有向图 G 的拓扑序列中，顶点 vi 在顶点 vj 之前，则下列 4 种情形中不可能出现的是 ( ) 。 A ．G 中有弧 vi,vj ； B ．G 中没有弧 vi,vj ； C ．G 中有一条从顶点 vi 到顶点 vj 的路径； D ．G 中有一条从顶点 vj 到顶点 vi 的路径。 8 ．下列关于查找操作的叙述中，错误的是 ( ) 。 A ．在顺序表中查找元素可以采用顺序查找法，也可以采用折半查找法； B ．在链表中查找结点只能采用顺序查找法，不能采用折半查找法； C ．一般情况下，顺序查找法不如折半查找法的时间效率高； D ．折半查找的过程可以用一棵称之为 “判定树 ”的二叉树来描述。 9 ．在一棵 m 阶 B- 树中，除根结点之外的任何分支结点包含关键字的个数至少是 ( ) 。 A ．m/2-1 ； B ．m/2 ； C ．#61673 。m/2-1 ； D ．#61673 。m/2#61689 。。 10 ．若对序列 (49, 38, 65, 97, 76, 13, 27, 49 进行快速排序，则第一趟排序结束’) ( 即确定了第 1 个 分界元素的最终位置 ) 时，序列的状态是 ( ) 。 A ．(13, 27, 49 ’ , 38, 49, 76, 97, 65) ；B ．(13, 38, 27, 49 ’ , 49, 76, 97, 65) ； C ．(13, 38, 49 27, 49, 97, 76, 65)’, ；D ．(13, 38, 49 ’ , 27, 49, 76, 97, 65) 。 二、填空题 ( 本题共 20 分，每小题各 2 分 ) 1 ．非空线性表在采 ( ) 存储结构的情况下，删除表的一个数据元素平均需要移动表中近一半元素的位 置。