《数据结构》单元测试含答案.docx

《数据结构》单元测试含答案.docx

《《数据结构》单元测试含答案.docx》由会员分享，可在线阅读，更多相关《《数据结构》单元测试含答案.docx（16页珍藏版）》请在冰点文库上搜索。

《数据结构》单元测试含答案

《数据结构》单元测试1

一、选择题（每题2分，共40分）

1．数据的最小单位是（ A）。

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

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

（A）只允许在端点处插入和删除元素

 （B）都是先进后出   （C）都是先进先出

（D）没有共同点

3. 用链接方式存储的队列，在进行插入运算时（  D）。

       （A）仅修改头指针 　          （B）头、尾指针都要修改

       （C）仅修改尾指针             （D）头、尾指针可能都要修改

4. 以下数据结构中哪一个是非线性结构？

（  D）

       （A）队列  　　  （B）栈       （C）线性表 　　 （D）二叉树

5．函数substr（“DATASTRUCTURE”，5，9）的返回值为（ A）。

  （A）“STRUCTURE”                  （B）“DATA”

  （C）“ASTRUCTUR”                      （D）“DATASTRUCTURE”

6．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ D）。

  （A）O（log2n）    （B）O

（1）       （C）O（n2）      （D）O（n）

7．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（ B）。

  （A）Nl+N2+……+Nm                （B）1+N2+2N3+3N4+……+（m-1）Nm

  （C）N2+2N3+3N4+……+（m-1）Nm     （D）2Nl+3N2+……+（m+1）Nm

8．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ B）次。

  （A）25          （B）10         （C）7                  （D）1

9. 二叉树的第k层的结点数最多为（  D）。

         （A）2k-1       （B）2K+1     （C）2K-1 　　（D）2k-1

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

 （A）有序数据元素                      （B）无序数据元素

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

11.n个权构成一棵Huffman树，其节点总数为（  A）。

（A）2n-1 （B）2n（C）2n+1（D）不确定

12．下面程序的时间复杂为（B ）

for（i=1，s=0；i<=n；i++）{t=1；for（j=1；j<=i；j++）t=t*j；s=s+t；}

  （A）O（n）        （B）O（n2）      （C）O（n3）         （D）O（n4）

13．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ A）。

  （A）q=p->next；p->data=q->data；p->next=q->next；free（q）；

（B）q=p->next；q->data=p->data；p->next=q->next；free（q）；

  （C）q=p->next；p->next=q->next；free（q）；

  （D）q=p->next；p->data=q->data；free（q）；

14．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ D）。

  （A）n，e        （B）e，n       （C）2n，e      （D）n，2e

15.设某强连通图中有n个顶点，则该强连通图中至少有（ C）条边。

  （A）n（n-1）      （B）n+1        （C）n          （D）n（n+1）

16．下面关于线性表的叙述错误的是（  D）。

（A）线性表采用顺序存储必须占用一片连续的存储空间

（B）线性表采用链式存储不必占用一片连续的存储空间

（C）线性表采用链式存储便于插入和删除操作的实现

（D）线性表采用顺序存储便于插入和删除操作的实现

17．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ B）个空指针域。

  （A）2m-1        （B）2m         （C）2m+1       （D）4m

18．设顺序循环队列Q[0：

M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ C）。

  （A）R-F         （B）F-R        （C）（R-F+M）％M （D）（F-R+M）％M

19．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（  A）。

  （A）BADC        （B）BCDA       （C）CDAB       （D）CBDA

20．设某完全无向图中有n个顶点，则该完全无向图中有（ A）条边。

  （A）n（n-1）/2    （B）n（n-1）     （C）n2        （D）n2-1

二、填空题（每题2分，共28分）

 1.在有n个结点的二叉链表中，空链域的个数为____n+1_____。

2.设循环队列的元素存放在一维数组Q[0..30]中，front指向队头元素的前一个位置，rear指向队尾元素。

若front=25，rear=5，则该队列中的元素个数为11。

3.设源串S=“bcdcdcb”，模式串P=“cdcb”，按KMP算法进行模式匹配，当“S2S3S4”=“P1P2P3”，而S5≠P4时，S5应与p2比较。

4.假设以一维数组

作为n阶对称矩阵A的存储空间，以行序为主序存储A的下三角，则元素A[6][1]的值存储在S[_16__]中。

5.单循环链表L中指针P所指结点为尾结点的条件是____ p->next=L________。

6.若一棵树中度为1的结点有N1个，度为2结点有N2个，……度为m的结点有Nm个，则该树的叶结点有1+N2+2N3+…+（m-1）Nm个。

7.设某二叉树的前序和中序序列均为ABCDE，则它的后序序列是

EDCBA。

8.图的遍历方法主要是宽度优先搜索深度优先搜索。

 9.一棵有n个叶子结点的哈夫曼树共有___2n-1_______个结点。

10.有时在单链表的第一个结点之前附加一个"头结点"，其作用是____避免在插入和删除操作中将第一个结点看作是特殊结点，使程序编写简单________。

11.求解图的最小生成树的算法有两个，分别是Prim算法和Kruskal算法。

 12.对于任意一棵二叉树，如果其叶结点数为N0，度为1的结点数为N1，度为2的结点数为N2，则N0=_____N2+1_______。

 13.一棵有N个叶子结点的Huffman树，共有__2n-1_____个结点。

14、假设用一维数组A{0..m}作为循环队列Q的存储空间，front和rear分别表示该队列的队头和队尾指针，则该队列的队空条件　　　是_____front==rear________,队满条件是___（rear+1）%（m+1）==front______。

  15.稀疏矩阵的存储方法主要有两个：

一个是___三元组表法_____,另一个是十字链表示法。

三、解答题

1、根据图的邻接表画邻接矩阵。

（12分）

四、算法设计题

1、设采用邻接表作为有向图的存储结构，试编写算法：

计算有向图中每个顶点的出度和入度。

（20分）

typedefstructArcNode

{

intadjvex;

structArcNode*nextarc;

}ArcNode;

typedefstructVNode

{

intdata;

intin;

intout;

ArcNode*firstarc;

}VNode;

typedefstruct

{

VNodevertices[NUM];

intvexnum;

intarcnum;

}AlGraph;

//获得结点的入度和出度

voidGetInAndOut（AlGraph&g）//开始时所有结点的入度出度为0

{

inti;

ArcNode*p;

for（i=0;i

{

p=g.vertices[i].firstarc;

while（p!

=NULL）

{

g.vertices[i].out++;

g.vertices[p->adjvex].in++;

p=p->nextarc;

}

《数据结构》各章课后作业答案

第一章绪论课后作业答案

1.简述线性结构与非线性结构的不同点。

答：

线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。

2．分析下面各程序段的时间复杂度（每小题5分，共20分）

解：

1.第一个for循环执行n+1次，第二个for循环执行n（m+1）次，A[i][j]=0;语句执行n*m次，此程序段总的执行次数为n+1+n*（m+1）+n*m=2nm+2n+1次。

故时间复杂度为O（n*m）。

2.算法的时间复杂度是由嵌套最深层语句的执行次数决定的，本程序段嵌套最深层语句为：

s+=B[i][j];

它的执行次数为n2，所以本程序段的时间复杂度是O（n2）。

3.该算法的基本操作是语句x++,其语句频度为：

=

=

所以本程序段的时间复杂度是O（n2）。

4.设语句执行m次，则有

3m≤n⇒m≤log3n

所以本程序段的时间复杂度为O（log3n）。

第二章线性表课后作业答案

1.填空题。

（1）在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。

（2）线性表中结点的集合是有限的，结点间的关系是一对一的。

（3）向一个长度为n的向量的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移

动n-i+1个元素。

（4）顺序表中逻辑上相邻的元素的物理位置必定相邻。

单链表中逻辑上相邻的元素的物理位置不一定相邻。

2.试写一算法，对单链表实现就地逆置。

分析：

将单链表就地逆置，即不另外开辟结点空间，而将链表元素翻转顺序。

解：

从链上依次取下结点，按照逆序建表的方法重新建表。

voidReverse（LinkList&L）{

p=L->next;//原链表

L->next=NULL;//新表（空表）

while（p）{

//从原链表中取下结点s

s=p;

p=p->next;

//插入L新表表头

s->next=L->next;

L->next=s;

}

}

第三章栈和队列课后作业答案

1、填空题。

（1）栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。

不允许插入和删除运算的一端称为栈底。

（2）队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

（3）在具有n个单元的循环队列中，队满时共有n-1个元素。

2．计算题。

设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有①front=11，rear=19;②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？

解：

用队列长度计算公式：

（N＋r－f）%N

①L=（40＋19－11）%40=8②L=（40＋11－19）%40=32

3.写出下列程序段的输出结果（栈的元素类型SElemType为char）。

voidmain（）{

StackS;

charx,y;

InitStack（S）;

x=’c’;y=’k’;

Push（S,x）;Push（S,’a’）;Push（S,y）;

Pop（S,x）;Push（S,’t’）;Push（S,x）;

Pop（S,x）;Push（S,’s’）;

while（!

StackEmpty（S））{

Pop（S,y）;

printf（y）;

}

printf（x）;

}

答：

输出结果为“stack”。

第四章串课后作业答案

1．算法填空题。

本算法是在S中找子串t。

若找到。

则返回子串t第一次出现在主串s中的位置，否则返回-1。

intindex（chars[],chart[]）{

inti=0,j=0;

while（①）

{if（s[i+j]==t[j]）j++;

else{②;③;}

}

if（④）retruni;

elsereturn–1;

}

解：

可以参照课本上模式匹配算法中的BF算法思想。

答案为：

①i

②i++

③j=0

④j>=strlen（t）

2．写出子串t=”ABCABCACAB”的next值和nextval值。

解：

j

1

2

3

4

5

6

7

8

9

10

模式串

A

B

C

A

B

C

A

C

A

B

next[j]

0

1

1

1

2

3

4

5

1

2

nextval[j]

0

1

1

0

1

1

0

5

0

1

第五章数组和广义表课后作业答案

1、选择题。

（1）设数组a[1..60,1..70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为8950。

解：

不考虑0行0列，利用列优先公式：

LOC（aij）=LOC（ac1，c2）+[（j-c2）*（d1-c1+1）+

i-c1）]*L

得：

LOC（a32,58）=2048+[（58-1）*（60-1+1）+32-1]]*2＝8950

（2）一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。

那么，这个数组的体积是288个字节。

（3）三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。

（4）求下列广义表操作的结果：

①GetHead【（（a,b）,（c,d））】=（a,b）;

②GetHead【GetTail【（（a,b）,（c,d））】】=（c,d）;//头元素不必加括号

③GetHead【GetTail【GetHead【（（a,b）,（c,d））】】】=b;

④GetTail【GetHead【GetTail【（（a,b）,（c,d））】】】=（d）;

2、递归算法比非递归算法花费更多的时间，对吗？

为什么？

答：

不一定。

时间复杂度与样本个数n有关，是指最深层的执行语句耗费时间，而递归算法与非递归算法在最深层的语句执行上是没有区别的，循环的次数也没有太大差异。

仅仅是确定循环是否继续的方式不同，递归用栈隐含循环次数，非递归用循环变量来显示循环次数而已。

第六章树和二叉树课后作业答案

1、填空题。

（1）一棵完全二叉树有1000个结点，则它必有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。

分析题意：

已知n=1000,求n0和n2,还要判断末叶子是挂在左边还是右边？

解1:

易求出总层数和末层叶子数。

总层数k=

＋1=10;且前9层总结点数为29-1=511（完全二叉树的前k-1层肯定是满的），所以末层叶子数为1000-511=489个。

由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现非空右子树（0个）。

请注意叶子结点总数≠末层叶子数！

还应当加上第k-1层（靠右边）的0度结点个数。

根据分析末层的489个叶子只占据了上层的245个结点（

）

上层（k=9）右边的0度结点数还有29-1-245=11个。

所以，全部叶子数＝489（末层）＋11（k-1层）=500个。

度为2的结点＝叶子总数－1=499个。

解2：

可先求2度结点数,再由此得到叶子总数。

首先，k-2层的28-1（255）个结点肯定都是2度的（完全二叉）。

另外，末层叶子（刚才已求出为489）所对应的双亲也是度＝2，（共有

＝244个）。

所以，全部2度结点数为255（k-2层）＋244（k-1层）=499个；总叶子数＝2度结点数＋1=500个。

（2）用二叉链表存储n个结点的二叉树（n>0），共有n+1个空指针域；采用三叉链表存储，共有n+2个空指针域。

解2：

当二叉树中采用二叉树链表存储时，共有2n个指针，其中只有n-1个指针指向左右孩子，所以空指针数=2n-（n-1）=n+1。

当二叉树中采用三叉树链表存储时，共有3n指针，其中只有n-1个指针指向左右右孩子，又因为根结点没有父结点，所以根结点的父指针为空，其它结点的每个父指针不为空,共有n-1个。

所以根据分析，得到如下等式：

3n=n-1+n-1+空指针数，解得空指针数=n+2。

（3）由3个结点所构成的二叉树有5种形态。

解2：

含有n个结点的不相似的二叉树的棵数为

（即为Catalan数）去计算。

当n=3时，

=5。

2、假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。

请画出该树。

【解答】

3、编写递归算法，计算二叉树中叶子结点的数目。

【分析】

输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。

【解答】

算法如下：

intLeafCount_BiTree（BitreeT）{//求二叉树中叶子结点的数目

if（!

T）return0;//空树没有叶子

elseif（!

T->lchild&&!

T->rchild）return1;//叶子结点

elsereturnLeaf_Count（T->lchild）+Leaf_Count（T->rchild）;

//左子树的叶子数加上右子树的叶子数

}//LeafCount_BiTree

第七章图课后作业答案

1、填空题。

（1）图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。

（2）有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。

（3）如果n个顶点的图是一个环，则它有n棵生成树。

（4）图的逆邻接表存储结构只适用于有向图。

（5）用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。

（6）拓扑排序算法是通过重复选择具有0个前驱顶点的过程来完成的。

2、求解下图的最小生成树，并计算出它的权值。

解：

图的最小生成树如下：

最小生成树的权值为1+5+4+2+3=15。

第九章查找课后作业答案

1、填空题。

（1）具有11个元素的有序表进行折半查找，则平均查找长度为3,3。

解：

先看一个具体的情况，假设表长n=11。

i为有序表中元素的位置，Ci为在折半查找过程中比较的次数。

i

1

2

3

4

5

6

7

8

9

10

11

Ci

3

4

2

3

4

1

3

4

2

3

4

ASLbs=（1×1+2×2+3×4+4×4）/11=3.3。

（2）在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找。

（3）在分块查找方法中，首先查找索引表，然后再查找相应的块表。

（4）在散列函数H（key）=key%m中，m应取素数。

2、设散列表长为7，记录关键字组为：

15,14,28,26,56,23，散列函数：

H（key）=keyMOD7，冲突处理采用线性探测法，将它们填入表中。

解：

H（15）=15MOD7=1H（14）=14MOD7=0

H（28）=28MOD7=0冲突H1（28）=1又冲突H2（28）=2

H（26）=26MOD7=5

H（56）=56MOD7=0冲突H1（56）=1又冲突H2（56）=2又冲突H3（56）=3

H（23）=23MOD7=2冲突H1（23）=3又冲突

H3（23）=4

各个关键字的存放的位置如下：

0123456

14

15

28

56

23

26

第十章内部排序课后作业答案

1、填空题。

（1）大多数排序算法都有两个基本的操作：

比较（两个关键字的大小）和移动（记录或改变指向记录的指针）。

（2）对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O（n2）。

若对其进行快速排序，在最坏的情况下所需要的时间是O（n2）。

（3）对于n个记录的集合进行归并排序，所需要的平均时间是O（nlog2n），所需要

的附加空间是O（n）。

（4）对于n个记录的表进行2路归并排序，整个归并排序需进行log2n趟，共计移动nlog2n次记录。

注：

需要log2n趟，每趟都要移动n个元素，移动到新表中的总次数为nlog2n。

2、已知序列{10，18，4，3，6，12，1，9，18，8}，请给出采用归并排序法对该序列作升序排序时的每一趟的结果。

解：

采用归并排序法排序的各趟的结果如下：

初始：

10，18，4，3，6，12，1，9，18，8

第1趟：

[10，18][3，4][6，12][1，9][8，18]

第2趟：

[3，4，10，18][1，6，9，12][8，18]

第3趟：

[3，4，10，18][1，6，8，9，12，18]

第4趟：

[1，3，4，6，8，9，10，12，18，18]

第4趟归并完毕，则排序结束。