数据结构练习题及答案6套

U课程名称 数据结构 一、判断题 (每小题2分，共10分)

1.在单链表中，头结点是必不可少的。( ) 2.线性表的顺序存储表示优于链式存储表示。( ) 3.栈是一种后进先出的线性表。( )

4.已知二叉树的先序序列和后序序列，并不能唯一确定这棵二叉树。( ) 5.n个顶点的有向图至多有n(n-1)条弧。( ) 6.无向完全图一定是一个连通图。( )

7.无向图的邻接矩阵一定是一个对称矩阵。( )

8.在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻。( ) 9.已知关键码为Key=05587463253，设哈希表长为3位数，则可对关键码按3位为一部分来分割，用间界叠加法求出哈希地址是308 ( )

10.在一个图中所有顶点的入度之和等于所有顶点的出度之和。( ) 二、单项选择题 (每小题2分，共20分) 1.组成数据的基本单位是______。

A. 数据类型 B.数据项 C. 数据变量 D.数据元素

2.有一个含头结点的单链表，头指针为Head，则判断其是否为空的条件为______。 A．Head==NULL B．Head-> next==NULL C．Head-> next== Head

D．Head！=NULL

3.一棵有124个叶子结点的完全二叉树，最多有____个结点。 A.247

B.248

C.249 D.250

4.设一数列的输入顺序为1,2,3,4,5,6,通过栈操作不可能排成的输出序列为____。 A. 3,2,5,6,4,1 B. 1,5,4,6,2,3 C. 2,4,3,5,1,6 D. 4,5,3,6,2,1 5.设连通图G的顶点树为n,则G的生成树的边数为____。

A.n B.2n

C.n-1 D.2n-1 6.二叉树第K(K>=1)层最多有____。

A.2k个结点 B.2k-1个结点 C.2k-1个结点 D.2k-1-1个结点 7.采用链结构存储线性表时,其地址____。

A.必须是连续的 B.连续不连续都可以 C.部分地址必须是连续的 D.必须是不连续的

8.具有2000个结点的二叉树,其高度至少为____。 A.9 B. 10 C.11 D.12

9.在关键字序列(6，12，15，18，22，25，28，35，46，58，60)中用折半查找法查找关键字为12的结点时，所需进行的比较次数分别为____。

A．2 B．3 C．4

D．5

10.一个无向连通图的生成树是含有该连通图的全部顶点的____。 A. 极小连通子图 B. 极小子图 C. 极大连通子图

D. 极大子图

三、填空题 (每小题2分，共20分)

1.设单链表中指针P指向结点A,若要删除A后的结点(若存在),则需要修改指针的操作为 。 2.线性表中 ___________ 称为表的长度。

3.Substr(‘DATA STRUCTURE’,5，9)=‘ ’。 4.队列的操作原则是_ ____。

5.后序序列和中序序列相同的二叉树为 。 6.如果一个有向图有5个顶点，则它最多有 条弧。 7.设单链表中指针P指向结点A，若要删除A后的结点（若存在）， 则需要修改指针的操作为 。 8.已知关键码集为{47,7,29,11,16,92,22,8,3},哈希表表长为11, Hask(Key)=Key mod 11,用线性探测法处理冲突,在数据元素查找 等概率情况下,平均查找长度为 。

１9.对于一个以顺序实现的循环队列Q[0...m-1],对头、队尾指针分别为f,r,其判满条件是 。

10.通过遍历可以将树和图这种 转变成线性结构。 四、构造题（每题8分，共40分）

1.已知一棵二叉树的中序遍历结果为DBHEAFICG，后序遍历结果为DHEBIFGCA （1）画出该二叉树。

（2）对该二叉树进行前序遍历。

2.设有一台模拟机，共有7种不同的指令，指令使用频率分别为：（I1：0.40， I2：0.30,I3:0.15,I4:0.05,I5:0.04,I6:0.03,I7:0.03)。 试写出相应频度指令的哈 夫曼编码。

3.画出此有向图的邻接矩阵。

4.请利用Prim算法构造下面无向网的最小生成树，要求分步给出构造过程。

5. 已知关键码集合为{47，7，29，11，16，92，22，8，3}，哈希表表长为11。 （1）用除留余数法构造哈希函数。

（2）所设计的哈希函数有无冲突，如有冲突，用线性探测法处理冲突并建表。 （3）求线性探测法的平均查找长度ASL。

数据结构参考答案

一 判断题

1. × 2. × 3. × 4. √ 5. √ 6. √ 7. × 8. × 9. √ 10. √ 二 选择题

1. D 2.B 3. A 4. B 5.C 6.B 7.B 8.B 9.C 10.A 三 填空题

1. P->next= P->next->next 2. 数据元素个数 3.‘STRUCTURE’ 4. 先进先出 5. 单左支二叉树或者孤立顶点 6. 20

7. P->next=P->next->next 8. 5/3 9. （r+1）%m=f 10. 非线性结构 四 构造题 1（1）

A B C D E F G H I （2）二叉树的前续遍历的结果为ABDEHCFIG 2. 1.00 0.60 0.40 I1 0.30 0.30 I2 0.15 0.15 I3 0.06 0.09

0.03 I7 0.03 I6 0.04 I5 0.05 I4

２

指令的哈夫曼编码：I1：0，I2：10，I3：110，I4：11100，I5：11101，I6：11110

2 I7：11111（规定向左的分支标记为1，向右的分支标记为0。） 1 1 1 4 2 4 2 4 3.

a b c d e f 4.

a b 0 1 0 0 0 1 0 0 0 0 0 0 c d 1 1 0 0 0 0 1 0 0 0 0 1 e f 0 0 1 0 1 1 0 0 0 1 0 0 3 3 3 5 6 5 6 5 6 1 1 2 4 2 4 3 3 5 6 5 6 5. （1）Hash（Key）= key mod 11

（2）建表如下

0 1 2 3 4 5 6 7 8 9 10 11 22 47 92 16 3 7 29 8 （3）线性探测法的平均查找长度为 ASL=（5*1+3*2+1*4）/9=5/3

课程名称 数据结构 一、判断题 (每小题2分，共20分)

1.在单链表中，头结点是必不可少的。( ) 2.线性表的唯一存储形式是链表。( ) 3.栈是一种后进先出的线性表。( )

３4.已知二叉树的先序序列和后序序列，并不能唯一确定这棵二叉树。( ) 5.栈的操作原则是先进后出。( ) 6.完全二叉树一定是一棵满二叉树。( ) 7.无向完全图一定是一个连通图。( )

8.已知关键码为Key=05587463253，设哈希表长为3位数，则可对关键码按3位为一部分来分割，用间界叠加法求出哈希地址是308 。( )

9.在有向图中，各顶点的入度之和等于各顶点的出度之和。( ) 10.二叉排序树中新插入结点一定是作为叶子结点添加上去的。( ) 二、单项选择题 (每小题2分，共20分) 1. 组成数据的基本单位是( )。

A.数据项 B.数据类型 C.数据元素 D.数据变量

2. 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是( )。A.p=p->next; B.p->next=p->next->next; C.p->next=p; D.p=p->next->next; 3. 队列的操作原则是( )。 A.只能进行插入 B.只能进行删除 C.先进先出

D.后进先出

4.一个栈的入栈序列为1，2，3，4，5，那么出栈序列不可能的是( )。 A. 3，2，5，4，1 B. 1，5，4，2，3 C. 2，4，3，5，1 D. 4，5，3，2，1 5.设连通图G的顶点数为n,则G的生成树的边数为( )。 A.n B.2n

C.n-1 D.2n-1

6.一棵具有n(n>1)个结点的二叉树，存放在二叉链表结构中，空指针域个数( )。A.n-1 B.n+1 C.n D.n-2 7. 在一棵二叉树的第4层上最多有( )个结点。

A.4 B.9 C.8 D.16

8.具有2000个结点的二叉树，其高度至少为( )。 A.9 B.10 C.11 D.12

9.表长为25的哈希表，用除留余数法，即按式H(Key)=Key mod P，建立哈希函数，则P应取( )。 A．26 B．15 C．24

D．23

10.一个无向连通图的生成树是含有该连通图的全部顶点的( )。 A. 极小连通子图 B. 极小子图 C. 极大连通子图

D. 极大子图

三、填空题 (每小题2分，共20分)

1.具有64个结点的完全二叉树的深度为 。

2.双向循环链表的主要优点是 。 3.Substr(‘DATA STRUCTURE’,5，9)=‘ ’。 4.后序序列和中序序列相同的完全二叉树为 。

5.设一棵二叉树共有50个叶结点（终端结点），则共有 个度为2的结点。 5.循环队列中判断队满的条件是 。

6.在队列中，进行插入操作的一端称为__ ___，进行删除操作的一端称为_ _。 7.如果一个有向图有5个顶点，则它最多有 条弧。 8.无向图的邻接矩阵一定是一个 。

9.对一棵二叉排序树进行 遍历，可得到结点值的有序序列。 10.通过遍历可以将树和图这种 转变成线性结构。 四、构造题（每题8分，共40分）

1.已知一棵二叉树的中序遍历结果为DBHEAFICG，后序遍历结果为DHEBIFGCA

（1）画出该二叉树。

（2）对该二叉树进行前序遍历。

2.试用权集合{1，3，6，7，9，15，22},构造哈夫曼(Huffman)树，并求出其WPL值。 3.画出下面有向图的邻接矩阵。

４

4.利用Prim从顶点1开始构造下面无向网的最小生成树，要求分步给出构造过程。

5.已知关键码集合为{47，7，29，11，16，92，22，8，3}，哈希表表长为11。 （1）用除留余数法构造哈希函数。

（2）所设计的哈希函数有无冲突，如有冲突，用线性探测法处理冲突并建表。 （3）求线性探测法的平均查找长度ASL。

08-09学年第二学期数据结构参考答案

一 判断题

1. × 2. × 3. √4. √5. √ 6. × 7. √8. √9. √ 10. √

二 选择题

1. C 2.B 3.C 4.B 5.C 6.B 7.C 8.C 9.D 10.A

三 填空题

1. 7 2. 既可以方便的找到一个结点的后继，又可以方便的找到一个结点的前驱。 3‘STRUCTURE’ 4单左支二叉数或孤立结点。 5 49 6 队尾 队头 7 20 8 对称矩阵 9 中序 10 非线性结构

四 构造题 1.

A B C D E F G H I 前序遍历序列：ABDEHCFIG

2.

63 25 38 15 10 16 22 4 6 7 9 3 1 WPL=(3+1)*4+(9+6+7)*3+(22+15)*2=156

3.

５

本文来源：https://www.bwwdw.com/article/70ot.html