数据结构附录习题及B卷答案答案

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐数据结构附录习题及B卷答案答案数据结构附录A样卷一

一、推断题：（10分）

正确在括号内打√，错误打×

()1.在单链表中，头结点是必不行少的。

（）2．假如一个二叉树中没有度为1的结点，则必为满二叉树。

()3.循环链表的结点结构与单链表的结点结构彻低相同，只是结点间的衔接方式不同。()4.挨次存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。()5.在一个大根堆中，最小元素不一定在最后。

()6.在一个有向图中，全部顶点的入度之和等于全部顶点的出度之和。

（）7.在采纳线性探测法处理矛盾的散列表中，全部同义词在表中相邻。

（）8.内部排序是指排序过程在内存中举行的排序。

（）9.拓扑排序是指结点的值是有序罗列。

()10.AOE网所表示的工程至少所需的时光等于从源点到汇点的最长路径的长度。

二、挑选题(30分,每题1.5分)

1．有一个含头结点的单链表，头指针为head,则推断其是否为空的条件为：

________________

A．head=NILB.head^.next=NILC.head^.next=headD.headNIL或A．head==NULLB.Head->next==NULLC.head->next==headD.Head!=NULL2．非空的循环单链表head的尾指针p满足______________。

A.p^.next=NIL

B.p=NIL

C.p^.next=head

D.p=head

或A.p->next=NULLB.p==NULLC.P->next==headD.p==head

3．链表不具有的特点是。

A、可随机拜访任一个元素

B、插入删除不需要移动元素

C、不必事先估量存储空间

D、所需空间与线性表的长度成正比

4．若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采纳存储方式最节约运算时光。

A、单链表

B、双链表

C、单循环链表

D、带头结点的双循环链表

5．若线性表最常用的操作是存取第i个元素及其前驱的值，则采纳存储方式节约时光。

A、单链表

B、双链表

C、单循环链表

D、挨次表

6．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不行能的是。

A、A，B，C，D

B、D，C，B，A

C、A，C，D，B

D、D，A，B，C

7．一个队列的入队序列是1，2，3，4，则队列的输出序列是。

A、4，3，2，1

B、1，2，3，4

C、1，4，3，2

D、3，2，4，18．设循环队列中数组的下标范围是1~n，其头尾指针分离为f，r，若队列中元素个数

为。

A、r-fB、r-f+1C、（r-f+1）modnD、（r-f+n）modn

9．串是。

A、不少于一个字母的序列

B、随意个字母的序列

C、不少于一个字符的序列

D、有限个字符的序列

10．数组A[1..5,1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的延续内存单元中，则A[5，5]的地址是。

A、1140

B、1145

C、1120

D、1125

11．将一棵有100个结点的彻低二叉树从根这一层开头，每一层从左到右依次对结点举行编号，根结点编号为1，则编号为49的结点的左孩子的编号为。

A、98

B、99

C、50

D、48

12．对二叉树从1开头编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采纳实现编号。

A、先序遍历

B、中序遍历

C、后序遍历

D、从根开头举行层次遍历

13．某二叉树的先序序列和后序序列正巧相反，则该二叉树一定是的二叉树。

A、空或惟独一个结点

B、高度等于其结点数

C、任一结点无左孩子

D、任一结点无右孩子

14．在有n个叶子结点的哈夫曼树中，其结点总数为。

A、不确定

B、2n

C、2n+1

D、2n-1

15．一个有n个顶点的无向图最多有条边。

A、n

B、n（n-1）

C、n（n-1）/2

D、2n

16．任何一个无向连通图的最小生成树。

A、惟独一棵

B、有一棵或多棵

C、一定有多棵

D、可能不存在

17．一组记录的关键字为（46，79，56，38，40，84），利用迅速排序的办法，以第一个记录为基准得到的一次划分结果为。

A、38，40，46，56，79，84

B、40，38，46，79，56，84

C、40，38，46，56，79，84

D、40，38，46，84，56，79

18．已知数据表A中每个元素距其终于位置不远，则采纳排序算法最节约时光。

A、堆排序

B、插入排序

C、迅速排序

D、直接挑选排序

19．下列排序算法中，算法可能会浮现下面状况：初始数据有序时，花费时光反而最多。

A、堆排序

B、冒泡排序

C、迅速排序

D、SHELL排序20．对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必需从键值为的结点开头。

A、100

B、60

C、12

D、15

三、填空题（40分）

1在挨次表（即挨次存储结构的线性表）中插入一个元素，需要平均动个元素.

2.迅速排序的最坏状况，其待排序的初始罗列是.

3.为防止在图中走回，应设立.

4.一个栈的输入序列为123，写出不行能是栈的输出序列。

5.N个结点的二叉树,采纳二叉链表存放,空链域的个数为.

6.要在一个单链表中p所指结点之后插入s所指结点时,

应执行和的操作.

7.Dijkstra算法是按的次序产生一点到其余各顶点最短路径的算法.

8.在N个结点彻低二叉树中，其深度是.

9.对二叉排序树举行遍历,可得到结点的有序罗列.

10．设一哈希表表长M为100，用除留余数法构造哈希函数，即H（K）=KMODP（P〈=M〉,为使函数具有较好性能，P应选

11．单链表与多重链表的区分是

12．深度为6（根层次为1）的二叉树至多有个结点。

13．已知二维数组A[0..20][0..10]采纳行序为主方式存储，每个元素占4个存储单元,并且A[0][0]的存储地址是1016,则A[10][5]的存储地址是

14．循环单链表La中，指针P所指结点为表尾结点的条件是

15．在查找办法中，平均查找长度与结点个数无关的查找办法是。

16．队列的特性是

17．具有3个结点的二叉树有种

18．已知一棵二叉树的前序序列为ABDFCE，中序序列为DFBACE，后序序列为

19．已知一个图的邻接矩阵表示，要删除全部从第i个结点动身的边，在邻接矩阵运算是

四、构造题：（30分）

1．已知关键字序列为：（75,33,52,41,12,88,66,27）哈希表长为10，哈希函数为：

H(k)=KMOD7,解决矛盾用线性探测再散列法，构造哈希表，求等概率下查找胜利的平均

查找长度。

2．已知无向图如图1所示，

（1）给出图的邻接表。

（2）从A开头，给出一棵广度优先生成树。

3．给定叶结点权值：（1，3，5，6，7，8），构造哈夫曼树，并计算其带权路径长度。

4．从空树开头，逐个读入并插入下列关键字，构造一棵二叉排序树：

（24，88，42，97，22，15，7，13）。

5．对长度为8的有序表，给出折半查找的判定树，给出等概率状况下的平均查找长度。

6．已知一棵树如图2所示，要求将该树转化为二叉树。

五、算法设计题(40分)

[算法题可用类PASCAL或类C语言,每题20分]

1．已知一棵二叉树采纳二叉链表存放，写一算法，要求统计出二叉树中叶子结点个数并输出二叉树中非终端结点（输出无挨次要求）。

2．编写算法，推断带头结点的双循环链表L是否对称。

对称是指：设各元素值a1,a2,...,an,则有ai=an-i+1

即指：a1=an，a2=an-1。。。。。。

结点结构为

数据结构附录B样卷二

一、简答题（15分，每小题3分）

1.简要说明算法与程序的区分。

2.在哈希表中，发生矛盾的可能性与哪些因素有关？为什么？

3.说明在图的遍历中，设置拜访标志数组的作用。

4.说明以下三个概念的关系：头指针，头结点，首元素结点。

5.在普通的挨次队列中，什么是假溢出？怎样解决假溢出问题？

二、推断题（10分，每小题1分）

正确在括号内打√，错误打×

()（1）广义表(((a),b),c)的表头是((a),b)，表尾是(c)。

()（2）在哈夫曼树中，权值最小的结点离根结点最近。

()（3）基数排序是高位优先排序法。

()（4）在平衡二叉树中，随意结点左右子树的高度差（肯定值）不超过1。

()（5）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p->next=s;s->next=p->next;

()（6）抽象数据类型（ADT）包括定义和实现两方面，其中定义是自立于实现的，定义仅给出一个ADT的规律特性，不必考虑如何在计算机中实现。

()（7）数组元素的下标值越大，存取时光越长。

()（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的状况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。

()（9）拓扑排序是按AOE网中每个结点大事的最早发生时光对结点举行排序。

()（10）长度为1的串等价于一个字符型常量。

三、单项挑选题（10分,每小题1分）

1．排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序办法的基本思想？

A、堆排序

B、直接插入排序

C、迅速排序

D、冒泡排序

2．已知一个有向图的邻接矩阵表示，要删除全部从第i个结点发出的边，应当：

A）将邻接矩阵的第i行删除B）将邻接矩阵的第i行元素所有置为0

C）将邻接矩阵的第i列删除D）将邻接矩阵的第i列元素所有置为0

3．有一个含头结点的双向循环链表，头指针为head,则其为空的条件是：

A.head->priro==NULL

B.head->next==NULL

C.head->next==head

D.head->next->priro==NULL

4.在挨次表(3,6,8,10,12,15,16,18,21,25,30)中，用折半法查找关键码值11，所需的关键码比较次数为：

A)2B)3C)4D)5

5.以下哪一个不是队列的基本运算？

A）从队尾插入一个新元素B）从队列中删除第i个元素

C）推断一个队列是否为空D）读取队头元素的值

6.在长度为n的挨次表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为：

A)n–i+1B)n–iC)iD)i–17．对于只在表的首、尾两端举行插入操作的线性表，宜采纳的存储结构为:

A)挨次表B)用头指针表示的循环单链表

C)用尾指针表示的循环单链表D)单链表

8．对包含n个元素的哈希表举行查找，平均查找长度为：

A)O(log2n)B)O(n)C)O(nlog2n)D)不直接依靠于n

9．将一棵有100个结点的彻低二叉树从根这一层开头，每一层从左到右依次对结点举行编号，根结点编号为1，则编号最大的非叶结点的编号为：

A、48

B、49

C、50

D、51

10．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为：

A）3B）2C）4D）5

四、填空题（10分，每空1分）

1．填空完成下面一趟迅速排序算法：

intQKPass(RecordTyper[],intlow，inthigh)

{x=r[low]；

while(low,,,,

,,,,,}

2．（6分）对以下关键字序列建立哈希表：（SUN,MON,TUE,WED,THU,FRI,SAT）,哈希函数为H(K)=（K中最后一个字母在字母表中的序号）MOD7。用线性探测法处理矛盾，要求构造一个装填因子为0.7的哈希表，并计算出在等概率状况下查找胜利的平均查找长度。

3.（6分）将关键字序列（3，26，12，61，38，40，97，75，53，87）调节为大根堆。

4．（4分）已知权值集合为：{5，7，2，3，6，9}，要求给出哈夫曼树，并计算其带权路径长度WPL。

六、算法分析题（10分）

阅读下面程序，并回答有关问题。其中BSTree为用二叉链表表示的二叉排序树类型。（1）简要说明程序功能。（5分）

（2）n个结点的满二叉树的深度h是多少？（3分）

（3）假设二叉排序树*bst是有n个结点的满二叉树,给出算法的时光复杂度。（2分）intProc(BSTree*bst,KeyTypeK)

{BSTreef,q,s;

s=(BSTree)malloc(sizeof(BSTNode));

s->key=K;s->lchild=NULL;s->rchild=NULL;

if(*bst==NULL){*bst=s;return1;}

f=NULL;q=*bst;

while(q!=NULL)

{if(Kkey)

{f=q;q=q->lchild;}

else

{f=q;q=q->rchild;}

}

if(Kkey)f->lchild=s;

elsef->rchild=s;

return1;

}

七、算法设计题（25分）

1．已知一个带头结点的整数单链表L，要求将其拆分为一个正整数单链表L1和一个负整数单链表L2。（9分）

2．无向图采纳邻接表存储结构，编写算法输出图中各连通重量的结点序列。（8分）3．编写一个建立二叉树的算法，要求采纳二叉链表存储结构。（8分）

《数据结构》附录B样卷二参考答案

一、简答题（15分，每小题3分）

6.算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实现，与详细的计算机语言有关。

7.主要与哈希函数、装填因子α有关。假如用哈希函数计算的地址分布匀称，则矛盾的可能性较小，假如装填因子α较小，则哈希表较稀疏，发生矛盾的可能性较小。

8.图中结点可能有多个前驱，设置拜访标志数组主要是为了避开重复拜访同一个结点。

9.头指针指向头结点，头结点的后继域指向首元素结点。

10.当队尾到达数组最后一个单元时，就认为队满，但此时数组前面可能还有空单元，因此叫假溢出。解决的办法是采纳循环队列，即令最后一个单元的后继是第一个单元。