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(n-1)/2 条边; D.具有 n 个顶点的有向图最多有 n(n-1)条边(弧)。 7.若在有向图 G 的拓扑序列中,顶点 vi 在顶点 vj 之前,则下列 4 种情形中不可能出现的是( )。 A.G 中有弧; B.G 中没有弧; C.G 中有一条从顶点 vi 到顶点 vj 的路径; D.G 中有一条从顶点 vj 到顶点 vi 的路径。 8.下列关于查找操作的叙述中,错误的是( )。 A.在顺序表中查找元素可以采用顺序查找法,也可以采用折半查找法; B.在链表中查找结点只能采用顺序查找法,不能采用折半查找法; C.一般情况下,顺序查找法不如折半查找法的时间效率高; D.折半查找的过程可以用一棵称之为“判定树” 的二叉树来描述。 9.在一棵 m 阶 B-树中,除根结点之外的任何分支结点包含关键字的个数至少是( )。 A.m/2-1; B.m/2; C.m/2-1; D.m/2。 10.若对序列(49, 38, 65, 97, 76, 13, 27, 49’)进行快速排序,则...