数据结构参考题及答案.docVIP

数据结构参考题及答案

单项选择题（每题2分，共10题）

1.线性表采用链式存储时，其地址（）。

A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续与否均可以

2.一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（）。

A.edcbaB.decbaC.dceabD.abcde

3.循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。

A.(rear-front+m)%mB.rear-front+1

C.rear-front-1D.rear-front

4.树最适合用来表示（）。

A.有序数据元素B.无序数据元素

C.元素之间具有分支层次关系的数据D.元素之间无联系的数据

5.具有10个叶结点的二叉树中有（）个度为2的结点。

A.8B.9C.10D.11

6.对线性表进行二分查找时，要求线性表必须（）。

A.以顺序方式存储B.以链接方式存储

C.以顺序方式存储，且数据元素有序D.以链接方式存储，且数据元素有序

7.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。

A.(n-1)/2B.n/2C.(n+1)/2D.n

8.以下排序方法中，稳定的排序方法是（）。

A.快速排序B.堆排序C.归并排序D.希尔排序

9.对于哈希表，以下说法错误的是（）。

A.哈希函数构造的越复杂越好B.哈希表的查找效率与装填因子有关

C.哈希表的查找效率与冲突处理方法有关D.哈希表的平均查找长度与记录个数无关

10.无向图G=(V,E)，其中：V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，则该图的顶点数和边数分别为（）。

A.6，7B.7，6C.6，6D.7，7

多项选择题（每题2分，共10题）

1.以下属于线性数据结构的有（）。

A.栈B.队列C.树D.图

2.栈的应用场景有（）。

A.表达式求值B.括号匹配C.深度优先有哪些信誉好的足球投注网站D.广度优先有哪些信誉好的足球投注网站

3.循环队列的优点有（）。

A.可以避免假溢出B.空间利用率高

C.操作简单D.可以实现无限存储

4.二叉树的遍历方式有（）。

A.前序遍历B.中序遍历C.后序遍历D.层次遍历

5.以下关于图的说法正确的有（）。

A.无向图的邻接矩阵是对称矩阵B.有向图的邻接矩阵一定是非对称矩阵

C.图的存储方式有邻接矩阵和邻接表D.图的遍历有深度优先遍历和广度优先遍历

6.查找算法中，平均查找长度与数据元素个数n有关的有（）。

A.顺序查找B.二分查找C.哈希查找D.分块查找

7.以下哪些排序算法的时间复杂度为O(n^2)（）。

A.冒泡排序B.选择排序C.插入排序D.归并排序

8.关于哈希表冲突处理方法，正确的有（）。

A.开放定址法B.链地址法C.再哈希法D.建立公共溢出区

9.以下哪些是数据结构中存储结构的类型（）。

A.顺序存储B.链式存储C.索引存储D.散列存储

10.树可以转化为（）。

A.二叉树B.森林C.图D.线性表

判断题（每题2分，共10题）

1.线性表的顺序存储结构比链式存储结构更节省存储空间。（）

2.栈和队列都是特殊的线性表。（）

3.循环队列中，当队头指针等于队尾指针时，队列一定为空。（）

4.完全二叉树一定是满二叉树。（）

5.图的深度优先遍历和广度优先遍历都需要借助栈来实现。（）

6.二分查找的时间复杂度为O(log?n)。（）

7.快速排序是一种稳定的排序算法。（）

8.哈希表的装填因子越大，发生冲突的可能性越小。（）

9.顺序存储结构只适合存储线性结构。（）

10.森林可以唯一地转换为二叉树。（）

简答题（每题5分，共4题）

1.简述栈和队列的主要区别。

答：栈是后进先出（LIFO）的数据结构，元素的插入和删除都在栈顶进行；队列是先进先出（FIFO）的数据结构，元素在队尾