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中有弧<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．非空线性表在采(   )存储结构的情况下，删除表的一个数据元素平均需要移动表中近一半元素的位置。
2．将一个长度为n的单链表链接到一个长度为m的单链表后面，该算法的时间复杂度用大O符号表示为(   )。
 

1.点我进入下载 22.38 KB (需下载币10个)