1 数据结构试卷（十） 一、选择题(24 分) 1．下列程序段的时间复杂度为（ ）。 i=0，s=0； while (snext=p->next；p->next=-s； (B) q->next=s； s->next=p； (C) p->next=s->next；s->next=p； (D) p->next=s；s->next=q； 4．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ ）。 (A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1 (C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3 5．设有一个10 阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（ ）。 (A) 10 (B) 19 (C) 28 (D) 55 6．设一棵m 叉树中有N1个度数为1 的结点，N2个度数为2 的结点，……，Nm 个度数为m 的结点，则该树中共有（ ）个叶子结点。 (A) miiNi1)1( (B) miiN1 (C) miiN2 (D) miiNi2)1(1 7. 二叉排序树中左子树上所有结点的值均（ ）根结点的值。 (A) < (B) > (C) = (D) != 8. 设一组权值集合 W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ ）。 (A) 129 (B) 219 (C) 189 (D) 229 9. 设有n 个关键字具有相同的Hash 函数值，则用线性探测法把这 n 个关键字映射到HASH表中需要做（ ）次线性探测。 (A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/2 10.设某棵二叉树中只有度数为0 和度数为2 的结点且度数为0 的结点数为n，则这棵二叉中共有（ ）个结点。 (A) 2n (B) n+l (C) 2n-1 (D) 2n+l 11.设一组初始记录关键字的长度为8，则最多 经 过（ ）趟 插入排序可以得到有序序列。 (A) 6 (B) 7 (C) 8 (D) 9 12.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升 序的第 一趟 冒 泡 ...
