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

数据结构试题库及答案

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

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

A.必须是连续的

B.部分地址必须是连续的

C.一定是不连续的

D.连续与否均可以

2.栈和队列的共同特点是（）

A.都是先进先出

B.都是先进后出

C.只允许在端点处插入和删除元素

D.没有共同点

3.树最适合用来表示（）

A.有序数据元素

B.无序数据元素

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

D.元素之间无联系的数据

4.具有n个顶点的无向图最多有（）条边。

A.n(n-1)

B.n(n+1)

C.n(n-1)/2

D.n(n+1)/2

5.对一组数据(84,47,25,15,21)排序，数据的排列次序在排序的过程中的变化为：(1)8447251521(2)1547258421(3)1521258447(4)1521254784，则采用的排序方法是（）

A.选择排序

B.冒泡排序

C.快速排序

D.插入排序

6.顺序存储结构的优点是（）

A.存储密度大

B.插入、删除操作方便

C.不必事先估计存储空间

D.方便实现多队列共享存储空间

7.带头结点的单链表head为空的判定条件是（）

A.head==NULL

B.head-next==NULL

C.head-next==head

D.head!=NULL

8.循环队列存储在数组A[0..m]中，则入队时的操作为（）

A.rear=rear+1

B.rear=(rear+1)%(m-1)

C.rear=(rear+1)%m

D.rear=(rear+1)%(m+1)

9.线索二叉树是一种（）结构。

A.逻辑

B.逻辑和存储

C.物理

D.线性

10.散列函数有一个共同的性质，即函数值应当以（）取其值域的每个值。

A.最大概率

B.最小概率

C.平均概率

D.同等概率

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

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

A.栈

B.队列

C.树

D.图

2.关于栈的说法正确的是（）

A.栈是先进先出的线性表

B.栈顶元素总是最后被插入的元素

C.栈底元素总是最先被插入的元素

D.栈可以用顺序存储结构实现，也可用链式存储结构实现

3.完全二叉树的特点有（）

A.叶子结点只可能在层次最大的两层上出现

B.对任一结点，如果其右子树的深度为d，则其左子树的深度必为d或d+1

C.每个结点的度要么为0，要么为2

D.若有度为1的结点，则该结点只有左孩子

4.以下哪些是图的存储结构（）

A.邻接矩阵

B.邻接表

C.十字链表

D.三元组表

5.排序算法中，平均时间复杂度为O(n^2)的有（）

A.冒泡排序

B.选择排序

C.插入排序

D.快速排序

6.链表的优点有（）

A.不必事先估计存储空间

B.可随机访问任一元素

C.插入、删除操作方便

D.存储密度大

7.对于队列，以下说法正确的是（）

A.队列是先进先出的线性表

B.队头元素总是最先被插入的元素

C.队尾元素总是最后被插入的元素

D.队列只能用顺序存储结构实现

8.二叉树遍历方式有（）

A.前序遍历

B.中序遍历

C.后序遍历

D.层次遍历

9.哈希表冲突处理方法有（）

A.开放定址法

B.链地址法

C.再哈希法

D.建立公共溢出区

10.以下属于非线性数据结构的是（）

A.栈

B.树

C.图

D.线性链表

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

1.线性表的顺序存储结构优于链式存储结构。（）

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

3.树中结点的度可以为0。（）

4.无向图的邻接矩阵一定是对称矩阵。（）

5.快速排序在任何情况下的时间复杂度都是O(nlogn)。（）

6.顺序存储的线性表可以随机访问。（）

7.循环队列中，front和rear指针相等时表示队列空。（）

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

9.哈希表是一种基于查找码值直接访问的数据结构。（）

10.二叉排序树的中序遍历序列是有序序列。（）

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

1.简述线性表顺序存储和链式存储的优缺点。

答案：顺序存储优点是存储密度大，可随机访问；缺点是插入、删除操作不便，需事先估计空间。链式