数据结构期末考试【含答案】

数据结构期末考试选择、判断

一、单选题（共30题）

1.含n个叶结点的哈夫曼树，其总结点个数为（ B ）。
A.2n
B.2n-1
C.n+2
D.2n+2

2.空格串是指（ A ）。
A.一个或多个空格组成的串
B.长度为0的串
C.用“φ”表示的串
D.零个字符的串

3.下面二叉树中一定是完全二叉树的是（ B ）。
A.哈夫曼树
B.满二叉树
C.单枝二叉树
D.二叉排序树

4.一棵有27结点的完全二叉树，对它按层编号，则对编号为8的结点X，它的双亲结点及右孩子结点的编号分别为（　C　　）。
A.4，14
B.2，15
C.4，17
D.3，15

5.已知一长度为17的有序表A[1…17]，利用折半查找进行查找时，查找元素A[3]所需进行比较的元素次序依次为：( A )
A.A[9]–>A[4]–>A[2]–>A[3]
B.A[8]–>A[4]–>A[2]–>A[3]
C.A[9]–>A[5]–>A[3]
D.A[9]–>A[5]–>A[2]–>A[3]

6.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是( C )。
A.110
B.100
C.108
D.120

7.具有5个记录的序列，采用直接选择排序方法进行排序，需要进行的比较次数是（ A ）。
A.10
B.9
C.8
D.7

8.已知一组关键字{62，25，37，45，18，19，53，3，58}，则利用堆排序的方法建立的初始堆（min堆）为：( B )
A.3,19,18,25,62,53,37,45,58
B.3,18,19,25,62,37,53,45,58
C.3,18,19,62,25,37,53,45,58
D.3,18,19,25,62,53,37,58,45

9.有以下序列{43，15，73，35，38，12，100，53}，以43为划分标准元进行一趟快速排序后的结果为：( D )
A.15，12，38，35，43，73，100，53
B.12，15，38，35，43，53，100，73
C.35，15，38，12，43，73，100，53
D.12，15，38，35，43，73，100，53

10.在树结构中，如果结点A有3个兄弟，而且B是A的双亲，则B的度是（ C ）。
A.3
B.1
C.4
D.5

11.若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ B ）图。
A.非连通
B.连通
C.强连通
D.有向

12.若一个栈的进栈序列为a，b，c，d，则 不可能 的出栈序列是（ C ）。
A.dcba
B.cdba
C.dacb
D.abcd

13.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。
A.必须是连续的
B.部分地址必须是连续的
C.一定是不连续的
D.连续或不连续都可以

14.采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字 ( A )。
A．不一定都是同义词
B．一定都是同义词
C．一定都不是同义词
D．都相同

15.一棵结点总数为n的二叉树，其边数为（ D ）。
A.n
B.n/2
C.n + 1
D.n – 1

16.要解决哈希存储引起的冲突问题，常采用的方法有（ D ）。
A.数字分析法、平方取中法
B.数字分析法、线性探测法
C.平方取中法、除留余数法
D.线性探测法、链地址法

17.图的深度优先搜索遍历类似于二叉树的（ A ）。
A.先序遍历
B.中序遍历
C.后序遍历
D.层次序遍历

18.快速排序执行一遍后，已经到位的元素个数至少是（ A ）个。
A.1
B.2
C.n
D.n/2

19.下述几种排序方法中，不稳定的排序方法是（ B ）。
A.直接插入排序和冒泡
B.快速排序和堆排序
C.归并排序和冒泡
D.冒泡排序

20.对序列{15，12，56，13，23，27}按从小到大进行排序，一趟冒泡排序后的结果为（ B ）。
A.12，15，27，13，23，56
B.12，15，13，23，27，56
C.12，15，56，13，23，27
D.12，13，15，23，27，56

21.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ D ）倍。
A.4
B.3
C.2
D.1

22.设栈S和队列Q的初始状态均为空，元素1,2,3,4,5,6依次入栈S，元素退栈后即进入队列Q，若6个元素的出队序列是2,4,3,6,5,1，则栈S的容量至少为（ B ）。
A.2
B.3
C.4
D.6

23.设有一组关键字为（20，5，25，10，15，56，13，23，3，7，27），按序列中元素顺序依次插入一棵初始为空的二叉排序树上。则最后得到的二叉排序树的第3层结点从左到右分别是：( A )
A.3,10,23,56
B.7,15,23,27
C.3,10,23,27
D.7,10,23,27

24.在线性表的链式存储结构中，只能从头指针出发才能访问表中所有结点的存储结构是（ A ）。
A.单链表
B.双向链表
C.循环链表
D.B和C

25.对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（ D ）
A.n+1
B.n
C.n-1
D.n(n-1)/2

26.一个带权无向连通图的最小生成树（ A ）。
A.有一棵或多棵
B.只有一棵
C.一定有多棵
D.不知道

27.（ B ）遍历二叉排序树可得到一个关键字的有序序列（从小到大）。
A.前序
B.中序
C.后序
D.随意

28.在n个顶点，e条边的连通图中，连通分量个数为（ B ）。
A.0
B.1
C.e
D.n

29.算法的时间复杂度取决于（ D ）。
A.问题的规模
B.计算机的配置
C.待处理数据的初态
D.A和C

30.顺序存储结构仅适合于（ B ）。
A.平衡二叉树
B.完全二叉树
C.二叉排序树
D.单枝二叉树

二、判断题（共10题）

1.判断循环队列满的条件是:front==rear. ×

2.无向图的邻接矩阵是对角矩阵。×

3.一个非空广义表的表头总是一个单元素。×

4.已知一颗树的先序序列和后序序列，可以唯一确定出这棵树。√

5.若无向图中有m条边，则其邻接表中表结点的个数为2m。√

6.具有14个记录的序列，采用冒泡排序算法进行排序，最少的比较次数是13。√

7.如果某种排序算法是不稳定的，则该排序算法没有实际应用价值。×

8.线性表、链栈、顺序队列、二维数组、字符串、广义表、图都是线性结构。×

9.一颗二叉树中度为0的结点个数比度为2 的结点个数多1个。√

10.广义表((a,b,c))的深度和长度是一致的。×