●将两个长度为n的递减有序表归并成一个长度为2n的递减有序表，最少需要进行关键字比较(67)次。
(67)A.1
B.n-1
C.n
D.2n
答案：(67)C
解析：当一个有序表中的最小关键字比另一个表的最大关键字还大时，则最少比较关键字n次。
●设集合N={0，1，2，…}，f为从N到N的函数，且当0≤x≤90时f(x)=f(f(x+11))，当X>90时f(X)=X-10。经计算f(90)=81，f(89)=81，f(49)=(68)。
(68)A.39
B.49
C.81
D.92答案：(68)C
解析：当80<=90时，易得f(x)=f(f(x+11))=f(x+11-10)=f(x+1)，于是当80<=90时，f(x)恒等于f(89)即81。递推f(49)得f(49)=f(f(f(f(82))))=f(f(f(81)))=f(f(81))=f(81)=81。
●集合A={1.2.3}上的二元关系R为：R={<1，1>，<3，3>，<1，2>)}，则二元关系R是(69)。
(69)A.自反的
B.反自反的
C.对称的
D.传递的
答案：(69)C
解析：由<2，2>不属于R知R不是自反的;由<1，1>属于R知R不是反自反的;由<1，2>属于R而<2，1>不属于R知R不是对称的。
●快速排序最坏情况下的时间复杂度为(70)。
(70)A.0(log2n)
B.O(n)
C.O(nlog2n)
D.O(n2)
答案：(70)D
解析：对n个元素进行快速排序时，最坏情况下的时间复杂度为O(n2)。
●任何一个基于“比较”的内部排序的算法，若对5个元素进行排序，则在最坏情况下所需的比较次数至少为(71)。
(71)A.7
B.8
C.21
D.120
答案：(71)A
解析：对于5个记录的集合任何一个基于“比较”的内部排序的算法的判定树的叶子结点数目为5!，此判定树的树高至少为log25!。由5!=120，27=128，26=64可得6<7。因此在最坏情况下所需的比较次数至少为7。
●元素的存储地址与其关键字之间存在某种映射关系的存储结构是(72)。
(72)A.树形存储结构
B.线性存储结构
C.索引存储结构
D.散列存储结构
答案：(72)D
解析：散列存储结构中将结点按其关键值的散列地址存储到散列表中，其关键字与其存储地址之间按照某种关系进行映射。
●若循环队列存储在数组Q[0，m-1]中，变量r表示循环队列中队尾元素的实际位置，其移动按r=(r+1)mod m进行，变量l表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是(73)。
(73)A.r-1
B.(r-1+m)mod m
C.m-1
D.(1+r+m-1)mod m
答案：(73)D
解析：按照循环队列的定义，因为元素移动按照r=(r+1)mod m进行。当数组Q[m-1]存放了元素之后，下一个入队的元素将存放在Q[0]，因此。循环队列的队首元素的实际位置是(1+r+m-1)mod m。
●一个简单无向图含有n个顶点和e条边，则在其邻接矩阵存储结构中，零元素个数为(74)。
(74)A.e
B.2e
C.n2-e
D.n2-2e
答案：(74)D
解析：无向图的邻接矩阵是对称的，图中的一条边对应邻接矩阵中两个非零元素。因此该图的邻接矩阵存储结构中。零元素个数为n2-2e。
●一棵9个顶点的哈夫曼(Huffman)树共有(75)个叶子结点。
(75)A.7
B.6
C.5
D.4
答案：(75)C
解析：哈夫曼(Huffman)树是严格的二叉树。没有度为1的分支结点。n个叶子经过n-1次合并，产生n-1个新结点。于是得到关系式n+n-1=9，推出n=5。本题也可以直接画出哈夫曼树而得到结果。
●采用邻接矩阵来存储简单有向图时，则其某一个顶点i的出度等于该矩阵(76)。
(76)A.所有值为1的元素总数
B.第i行中值为1的元素个数
C.第i行中值为1的元素个数n2-2e
D.第i行及第i列中值为1的元素总个数
答案：(76)B
解析：采用邻接矩阵存储简单有向图时，其邻接矩阵第i行元素的和即为顶点i的出度，第i列元素的和即为顶点i的入度。
●在一棵度为4的树中，若有3个度为4的结点，有1个度为2的结点，没有度为1的结点，则有(77)个度为0的结点。
(77)A.9
B.10
C.11
D.12
答案：(77)C
解析i每个度为4的结点衍生出4个子结点，每个度为3的结点衍生出3个子结点，每个度为2的结点衍生出2个子结点，再加上根结点，于是结点总数为3*4+2+1=15。减去度非零的4个结点，得到度为0的结点数为11个。
●某二叉树的先根遍历序列中x结点在Y结点之前，而在其后根遍历序列中X结点在y结点之后，则x结点和Y结点的关系是(78)。
(78)A.X是Y的左兄弟
B.X是Y的祖先
C.X是Y的右兄弟
D.X是y的后裔
答案：(78)B
解析：二叉树的先根遍历序列中，根结点总是出现在其子树结点之前;二叉树的后根遍历序列中，根结点总是出现在其子树结点之后。因此。x结点是Y结点的祖先。
