数据结构试题库及答案.doc

数据结构试题库及答案

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

1.以下哪种数据结构是线性结构？（）

A.树B.图C.栈D.集合

答案：C

2.数组的存储结构采用（）。

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

答案：B

3.在单链表中，若要删除p指针所指向的节点（非尾节点），则需要修改（）指针。

A.p-nextB.p-priorC.p-next-priorD.p-prior-next

答案：A

4.栈的操作特性是（）。

A.先进先出B.后进先出C.随机进出D.按优先级进出

答案：B

5.队列的特点是（）。

A.先进先出B.后进先出C.只进不出D.只出不进

答案：A

6.二叉树的第i层上最多有（）个节点。

A.2^iB.2^(i-1)C.2^i-1D.2^(i+1)

答案：B

7.对于有n个节点的完全二叉树，其高度为（）。

A.log?nB.?log?(n+1)?C.?log?n?D.log?(n+1)

答案：B

8.无向图中顶点的度是指（）。

A.与该顶点相邻的顶点数B.与该顶点相邻边的数目C.与该顶点相连的边的权值D.与该顶点相连的边的方向

答案：B

9.采用邻接矩阵存储图，遍历图的时间复杂度为（）。

A.O(n)B.O(n2)C.O(n3)D.O(1)

答案：B

10.对顺序查找，若线性表长度为n，查找成功时平均查找长度为（）。

A.nB.n/2C.(n+1)/2D.1

答案：C

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

1.线性表的存储结构有（）。

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

答案：AB

2.以下属于栈的应用的是（）。

A.表达式求值B.函数调用C.递归实现D.迷宫求解

答案：ABC

3.队列的存储结构可以有（）。

A.顺序队列B.链式队列C.循环队列D.二叉队列

答案：ABC

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

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

答案：ABCD

5.图的遍历算法有（）。

A.深度优先遍历B.广度优先遍历C.拓扑排序D.关键路径算法

答案：AB

6.以下关于散列表的说法正确的是（）。

A.散列表是根据关键码值而直接进行访问的数据结构

B.散列函数将关键字映射为散列表中的存储位置

C.可能存在冲突现象

D.查找效率一定比顺序查找高

答案：ABC

7.以下属于排序算法的是（）。

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

答案：ABCD

8.顺序表的优点有（）。

A.存储密度大B.可以随机访问C.插入删除操作方便D.不需要额外的指针开销

答案：ABD

9.树的存储结构有（）。

A.双亲表示法B.孩子表示法C.孩子兄弟表示法D.邻接矩阵表示法

答案：ABC

10.以下关于二叉排序树的说法正确的是（）。

A.左子树上所有节点的值均小于根节点的值

B.右子树上所有节点的值均大于根节点的值

C.中序遍历二叉排序树得到的序列是有序序列

D.二叉排序树的插入和删除操作都比较复杂

答案：ABC

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

1.链表中每个节点都有一个指针域。（）

答案：正确

2.栈顶元素是最先进入栈的元素。（）

答案：错误

3.队列是一种先进先出的数据结构，只能在一端插入，在另一端删除。（）

答案：正确

4.二叉树的节点数一定比叶子节点数多。（）

答案：错误

5.无向图中边的数目一定比顶点数少。（）

答案：错误

6.散列表中不可能存在两个元素的关键码相同。（）

答案：错误

7.冒泡排序是一种稳定的排序算法。（）

答案：正确

8.顺序存储的线性表不适合插入和删除操作频繁的情况。