学海网

浙江商职院成教院成人大专（业余班）《数据结构》期末考试A
一、选择题（30分）
1、设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为( )。
(A) 20 (B) 30 (C) 40 (D) 45
2、执行一趟快速排序能够得到的序列是( )。
(A) [41，12，34，45，27] 55 [72，63]
(B) [45，34，12，41] 55 [72，63，27]
(C) [63，12，34，45，27] 55 [41，72]
(D) [12，27，45，41] 55 [34，63，72]
3、设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是( )。
(A) head==0 (B) head-﹥next==0
(C) head-﹥next==head (D) head!=0
4、时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是( )。
(A) 堆排序 (B) 冒泡排序 (C) 希尔排序 (D) 快速排序
5、设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是( )。
(A) 空或只有一个结点 (B) 高度等于其结点数
(C) 任一结点无左孩子 (D) 任一结点无右孩子
6、一趟排序结束后不一定能够选出一个元素放在其最终位置上的是( )。
(A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希尔排序
7、设某棵三叉树中有40个结点，则该三叉树的最小高度为( )。
(A) 3 (B) 4 (C) 5 (D) 6
8、顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为( )。
(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)
9、二路归并排序的时间复杂度为( )。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
10、 深度为k的完全二叉树中最少有( )个结点。
(A) 2k-1-1 (B) 2k-1 (C) 2k-1+1 (D) 2k-1
11、设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入
......
B
一、选择题（30分）
1、下面关于线性表的叙述错误的是( )。
(A) 线性表采用顺序存储必须占用一片连续的存储空间
(B) 线性表采用链式存储不必占用一片连续的存储空间
(C) 线性表采用链式存储便于插入和删除操作的实现
(D) 线性表采用顺序存储便于插入和删除操作的实现
2、以下数据结构中哪一个是非线性结构？( )
（A）队列 （B）栈 （C）线性表 （D）二叉树
3、设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有( )个空指针域。
(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m
4、设一棵二叉树的深度为k,则该二叉树中最多有( )个结点。
(A) 2k-1 (B) 2k (C) 2k-1 (D) 2k-1
5、设某无向图中有n个顶点e条边,则该无向图中所有顶点的入度之和为( )。
(A) n (B) e (C) 2n (D) 2e
6、设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记录的一趟快速排序结束后的结果为( )。
(A) 10，15，14，18，20，36，40，21
......