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)
设一组权值集合 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
