数据结构期末总复习题.docx

数据结构期末总复习题.docx

《数据结构期末总复习题.docx》由会员分享，可在线阅读，更多相关《数据结构期末总复习题.docx（27页珍藏版）》请在冰点文库上搜索。

数据结构期末总复习题

套题1

一、选择题（每题2分，共15题，总计30分）

1以下叙述中正确的是_____。

A数组是数据的最小单位

B数据对象就是一组数据元素的集合

C顺序存储方式只能用于存储线形结构

D树对应到的二叉树其根结点的右子树总是空的

2一个数组的第一个元素的存储地址是100，每个元素长度为2，则第5个元素的存储地址是_____。

A110B108C100D120

3一个栈的入栈顺序是a,b,c,d,e，则其出栈顺序不可能是_____。

Aa,b,c,d,eBe,d,c,b,a

Cd,c,e,a,bDd,e,c,b,a

4栈的特点是_____。

A先进先出B先进后出C随即存取D链式实现

5一个队列的入队顺序是1，2，3，4，5，那么出队顺序是_____。

A5，4，3，2，1B1，2，3，5，4

C1，2，3，4，5D1，3，2，4，5

6向一个长度为10的数组的第5个元素之前插入一个元素时，需向后移动_____个元素。

A3B5C6D7

7若一棵二叉树有101个结点，且无度为1的结点，则叶结点的个数为_____。

A48　　B49　　　C50　　D51

8高度为6的完全二叉树中第4层结点的个数为_____。

A2　　B4　　　C8　　D16

9具有n个顶点的无向完全图，其边数为_____。

An　　Bn（n-1）　　　Cn（n-1）/2　　Dn2

10具有n个顶点的有向完全图，其边数为_____。

An　　Bn（n-1）　　　Cn（n-1）/2　　Dn2

11在有7个顶点的无向图中至少有_____条边才能确保该图连通。

A1　　B6　　　C7　　D21

12对于一个有n个顶点的无向图，若采用邻接矩阵表示法，则该矩阵的大小是_____。

An-1　　Bn　　　C（n-1）2　　Dn2

13在序列1，10，12，15，23，40，66，77，85中利用直接查找，查找15所需的比较次数为_____。

A2B3C4D6

14采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为_____。

AO（n）　　BO（nlogn）　　CO（n2）　　DO（logn）

15在待排序元素基本有序的前提下，效率最高的排序方法是_____。

A插入排序B选择排序C快速排序D归并排序

二、填空题（每空2分，共20空，总计40分）

1判定下列程序段的时间复杂度为_________________，其中语句A[i][j]频度为___________________

for（i=0;i

{

for（j=0;j<=n;j++）

A[i][j]=0;

B[j][i]=1;

}

2对线性表进行二分查找时，要求线性表必须_______________且______________。

3对于一个头指针为head的带头结点的单链表，判定该链表为空的条件是__________________，对于一个不带头指针的单链表，判定该链表为空的条件是__________________。

4在循环单链表中，头指针用head表示，队尾结点用p指向，那么p→next等于__________________。

5在选择数据结构的存储结构时，为了方便地定位和读取某特定元素，数据结构宜采用__________形式，为了方便地进行数据元素的插入删除操作，数据结构宜采用__________形式。

6深度为5的二叉树，最多有___________个结点，最少有___________个结点。

7若深度为5的二叉树中仅有度为0的结点和度为2的结点，那么这棵二叉树最多有___________个结点，最少有___________个结点。

8在线索二叉树中，若以ltag表示某结点的左标志域，以lch表示某结点的左孩子域，则结点t没有左子树的条件是。

9在含有个8结点的二叉链表中有_______个空链域。

10有_______个结点的二叉树将会呈现5种不同的表现形式。

11在无向图的邻接矩阵中，若A[i][j]=1,A[j][i]=_______________。

12如下图所示的有向图，顶点D的入度为，出度为，顶点D的度为。

三、操作题（共4题，总计20分）

1已知一棵二叉树如下图所示：

①写出该二叉树的先根遍历序列（2分）

②写出该二叉树的中根遍历序列（2分）

③判断正误：

这棵二叉树的先根、中根、后根遍历序列中，叶子结点的相对次序保

持不变，其实，任意一棵二叉树，其叶子结点在先根、中根、后根遍历序列中的相

对次序都保持不变。

（2分）

p

2下面的程序段是一个在单链表表示的有序序列a,b,d,e中插入新值c并保持有序的算法，已知插入位置的前驱用p指向，请将程序段补充完整。

（6分）

StatusListInsert_L（LinkList&L,charc）

{

s=（LinkList）malloc（sizeof（LNode））;

;

s→next=;

p→next=;

returnOK;

}//ListInsert_L

3下图为一个无向图G，请给出该图从A出发的两个可能的广度优先遍历序列

①（2分）

②（2分）

③画出该图的邻接矩阵表示（4分）

四、算法设计题（共1题，总计10分）

设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。

试设计S1,S2有关入栈和出栈的操作算法。

套题2

一、选择题（每题2分，共10题，总计20分）

1一个数组的第一个元素的存储地址是1000，每个元素长度为4，则第4个元素的存储地址是_____。

A1004B1008C1012D1016

2一个栈的入栈顺序是a,b,c,d,e，则其出栈顺序不可能是_____。

Aa,b,c,d,eBe,d,c,b,a

Cd,c,e,a,bDd,e,c,b,a

3从一个具有n个结点的单链表中查找值等于x的结点，在查找成功的前提下，其平均比较次数为_____。

AnBn/2C（n-1）/2D（n+1）/2

4在序列1，10，12，15，23，40，66，77，85中利用直接查找，查找15所需的比较次数为_____。

A2B3C4D6

5下列排序算法中不稳定的是_____。

A堆排序B折半插入排序

C直接插入排序D链式基数排序

6向一个长度为100的数组的第45个元素之前插入一个元素时，需向后移动_____个元素。

A45B46C55D56

7若一棵二叉树有101个结点，且无度为1的结点，则叶结点的个数为_____。

A48　　B49　　　C50　　D51

8具有n个顶点的无向完全图，其边数为_____。

An　　Bn（n-1）　　　Cn（n-1）/2　　Dn2

9下列关于图的描述，错误的是_____。

A无向图中所有顶点的度数之和为边数之和的2倍

B有向图中所有顶点的度数之和为边数之和的2倍

C有向图中所有顶点的入度之和等于出度之和

D具有n个顶点，n-1条边的无向图是连通图

10有关二叉树下列说法正确的是_____。

A二叉树是度为2的树

B一棵二叉树的度可以小于2

C二叉树中至少有一个结点的度为2

D二叉树中所有结点的度都为2

二、填空题（每空2分，共12题，总计40分）

1判定下列程序段的时间复杂度为___________________，其语句频度为___________________

for（i=0;i

{

for（j=0;j<=n;j++）

A[i][j]=0;

B[j][i]=1;

}

2在一个单链表中的p所指的结点之前插入一个s所指的结点的操作可以描述为：

s->next=____________________;

p->next=s;

t=p->data;

p->data=____________________;

s->data=____________________;

3在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是____________________，需要内存容量最多的排序是____________________。

4对线性表进行二分查找时，要求线性表必须___________________________。

5对于一个头指针为head的带头结点的单链表，判定该链表为空的条件是__________________，对于一个不带头指针的单链表，判定该链表为空的条件是__________________。

6数据的存储结构是指，设有一批数据元素，为了方便地定位和读取某特定元素，数据结构宜采用__________形式，为了方便地进行数据元素的插入删除操作，数据结构宜采用__________形式。

7已知一棵二叉树，其先序序列为ABCDE，中序序列为CDBEA，则其后序序列为_。

8高度为6的二叉树，其结点个数最多为_____个，最少为_____个。

9在线索二叉树中，若以ltag表示某结点的左标志域，以lch表示某结点的左孩子域，则结点t没有左子树的条件是。

10在含有个20结点的二叉链表中有_______个空链域。

11有_______个结点的二叉树将会呈现5种不同的表现形式。

12如下图所示的AOE－网，其关键路径为。

三、算法题（每题8分，共2题，总计16分）

1、关键字序列a,b,c，d的链式存储如下，编写算法，通过更改指针实现关键字序列a，d，c,b的链式存储。

2、设计算法，现有一字符串“12468”（即该变量为字符数组，每个单元存放一个char型的值，分别为1，2，4，6，8），若该字符串表示的是数值型的八进制数值，即（12468）8，设计算法将它转换为十进制数并输出。

四、操作题（每题6分，共4题，总计24分）

1、已知一棵树如下图所示，要求：

①给出树的先根遍历序列和后根遍历序列（3分）

②将该树转化为二叉树（3分）

2、设有一组关键字为{8,7,13,10,9,23,15}，哈希函数为H（key）=keyMOD7，按开放定址的线性探测再散列解决冲突，即增量序列为1，2，3，…，构造表地址空间为0--9的哈希表。

①请画出该哈希表（3分）

0

1

2

3

4

5

6

7

8

9

②计算对关键字23进行查找时的查找长度并写出计算过程（3分）

3、下图为一个无向图G

①请给出该图的邻接表表示（3分）

②依据你所作的邻接表，从A出发，给出该图的深度优先遍历序列（3分）

4、下图所示为一棵3阶B-树

①请给出删除元素25之后的3阶B-树（3分）

②在①的基础上，给出插入15之后的3阶B-树（3分）

套题3

一、选择题（共10题，每题2分，共20分）：

1、从逻辑上可以把数据结构分为（）两大类。

A）动态结构、静态结构

B）顺序结构、链式结构

C）线性结构、非线性结构

D）初等结构、构造型结构

2、下面关于线性表的叙述中，错误的是哪一个？

（）

A）线性表采用顺序存储，必须占用一片连续的存储单元。

B）线性表采用顺序存储，便于进行插入和删除操作。

C）线性表采用链接存储，不必占用一片连续的存储单元。

D）线性表采用链接存储，便于插入和删除操作。

3、设无向图的顶点个数为n，则该图最多有（）条边。

A）n-1　　　B）n（n-1）/2C）n（n+1）/2　D）0

4、对线性表进行二分查找时，要求线性表必须（）

A）以顺序方式存储B）以顺序方式存储且元素有序

C）以链式方式存储　D）以链式方式存储且元素有序

5、下面给出的四种排序法中（）排序法是不稳定性排序法。

A）插入　　B）冒泡　　C）二路归并　　D）堆

6、以下说法正确的是______。

A）数据元素是数据的最小单位

B）数据项是数据的最小单位

C）数据结构是带有结构的各数据项的集合

D）数据结构是带有结构的数据元素的集合

7、下列说法不正确的是（）

A）图的遍历是从给定的源点出发每一个顶点仅被访问一次

B）遍历的基本算法有两种：

深度遍历和广度遍历

C）图的深度遍历不适用于有向图

D）图的深度遍历是一个递归过程

8、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）

A）9　　B）11　　　C）15　　D）不确定

9、栈和队列的共同点是（）

A）都是先进先出　　　　B）都是先进后出　　

C）只允许在端点处插入和删除元素　　D）没有共同点

10、有关二叉树下列说法正确的是（）

A）二叉树的度为2

B）一棵二叉树的度可以小于2

C）二叉树中至少有一个结点的度为2

D）二叉树中任何一个结点的度都为2

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

1、当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。

1）查邻接表中入度为______的顶点，并进栈；

2）若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk进行入度处理，处理方法是______；

3）若栈空时，输出顶点数小于图的顶点数，说明有______，否则拓扑排序完成。

2、给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树深度为__________，带权路径长度WPL的值为__________。

3、在单链表p结点之后插入s结点的操作是：

______。

4、设有一批数据元素，为了最快地存取某元素，数据结构宜采用__________结构，为了方便地插入一个数据元素，数据结构宜采用__________结构。

5、在一个无向图中，所有顶点的度数之和等于所有边数倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的倍。

6、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是_____。

7、二叉树的第i层上最多含有结点数为          。

8、具有N个结点的二叉树，采用二叉链表存储，共有______个空链域。

9、一个有n（n>0）个结点的图，最少有个连通分量，最多有个连通分量。

三、算法题（共3题，每题5分，共15分）

1、写一算法，求带有头结点的单链表的表长。

2、请用非递归算法写出折半查找的算法。

3、请写出直接插入排序的算法。

四、操作题（共6题，第1题10分，其余每题5分，共35分）

1、输入一个正整数序列（53，17，12，66，58，70，87，25，56，60），试完成下列各题。

（1）按次序构造一棵二叉排序树BS。

（2）依此二叉排序树，如何得到一个从大到小的有序序列？

（3）画出在此二叉排序树中删除结点66后的树结构。

（10分）

2、已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79），则按哈希函数H（key）=keymod13和链地址法处理冲突构造哈希表。

（5分）

3、对于下面的有向图G，请写出所有可能的拓扑序列。

（5分）

4、已知一棵二叉树前序为ABDEGCF，中序为DBGEACF，画出这棵二叉树。

（5分）

5、写出对数据（15，9，7，8，20，-1，7，4）进行快速排序中第一趟的序列。

（5分）

6、无向图G=（V，E），其中：

V={a，b，c，d，e，f}，E={（a，b），（a，e），（a，c），（b，e），（c，f），（f，d），（e，d）}，写出对该图进行深度优先遍历的一个序列。

（5分）

套题4

一、选择题（共10题，每题2分，共20分）：

1、以下属于逻辑结构的是（）。

A）顺序表B）哈希表C）有序表D）单链表

2、下面关于线性表的叙述中，错误的是哪一个？

（）。

A）线性表采用顺序存储，必须占用一片连续的存储单元。

B）线性表采用顺序存储，便于进行插入和删除操作。

C）线性表采用链接存储，不必占用一片连续的存储单元。

D）线性表采用链接存储，便于插入和删除操作。

3、设无向图的顶点个数为n，则该图最多有（）条边。

A）n-1　　　B）n（n-1）/2C）n（n+1）/2　D）0

4、线性表是具有n个（）的有限序列（n>0）。

A）表元素B）字符C）数据元素　D）数据项

5、下面给出的四种排序法中（）排序法是稳定性排序法。

A）希尔　　B）快速　　C）二路归并　　D）堆

6、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。

A）快速排序B）堆排序C）归并排序D）直接插入排序

7、下列说法不正确的是（）。

A）图的遍历是从给定的源点出发每一个顶点仅被访问一次

B）遍历的基本算法有两种：

深度遍历和广度遍历

C）图的深度遍历不适用于有向图

D）图的深度遍历是一个递归过程

8、若一棵二叉树具有14个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。

A）9　　B）11　　　C）15　　D）不确定

9、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A）顺序表　　　　B）双链表　　

C）带头结点的双循环链表　　D）单循环链表

10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。

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

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

1、数据的物理结构包括的表示和的表示。

2、给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树深度为__________，带权路径长度WPL的值为__________。

3、在单链表p结点之后删除s结点的操作是：

______。

4、设有一批数据元素，为了最快地存取某元素，数据结构宜采用__________结构，为了方便地插入一个数据元素，数据结构宜采用__________结构。

5、在拓扑排序中，拓扑序列的第一个顶点必须是________的顶点。

6、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是_____。

7、二叉树的第i层上最多含有结点数为          。

8、具有N个结点的二叉树，采用二叉链表存储，共有______个空链域。

9、一个有n（n>0）个结点的图，最少有个连通分量，最多有个连通分量。

10、对于具有N个结点的完全二叉树，其深度为。

11、在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为。

三、算法题（共3题，每题5分，共15分）

1、请写一算法，求带有头结点的单向循环链表的表长。

2、请用非递归算法写出在二叉树中计算叶子结点个数的算法。

3、请写出简单选择排序的算法。

四、操作题（共6题，第1题10分，其余每题5分，共35分）

1、已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79），则按哈希函数H（key）=keymod13和链地址法处理冲突构造哈希表。

（10分）

2、请写出在如下具有11个数据元素的有序表中使用折半查找算法查找21的过程（关键字即为数据元素的值）。

（5分）

（05，13，19，21，37，56，64，75，80，88，92）

3、对于下面的有向图G，请写出所有可能的拓扑序列。

（5分）

4、写出对数据（49，38，65，97，76，13，27，49）进行快速排序中第一趟的序列。

（5分）

5、无向图G=（V，E），其中：

V={a，b，c，d，e，f},E={（a，b），（a，e），（a，c），（b，e），（c，f），（f，d），（e，d）}，写出对该图进行广度优先遍历的序列。

（5分）

6、已知一棵二叉树前序为ABDEGCF，中序为DBGEACF，画出这棵二叉树。

（5分）

套题5

一、选择题（每题2分，共10题，总计20分）

1．以下那一个术语与数据的存储结构无关？

（）

A．栈B.哈希表C.线索树D.双向链表

2．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）

A．head==NULLB．head→next==head

C．head→next==NULLD．head!

=NULL

3.对于栈操作数据的原则是（）。

A.先进先出B.后进先出C.后进后出D.不分顺序

4．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）

A．9B．11C．15D．不确定

5．树的后根遍历序列等同于该树对应的二叉树的（）.

A.先序序列B.中序序列C.后序序列D．不一定

6．n个结点的完全有向图含有边的数目（　　　）。

A．n*nB．n（n＋１）C．n／2D．n*（n－l）

7．下列哪一种图的邻接矩阵是对称矩阵？

（）

A．有向图B．无向图C．AOV网D．AOE网

8.下面关于哈希（Hash，杂凑）查找的说法正确的是（）

A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B．除留余数法是所有哈希函数中最好的

C．不存在特别好与坏的哈希函数，要视情况而定

D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可

9．下列排序算法中，其中（）是稳定的。

A.堆排序，冒泡排序B.快速排序，堆排序

C.直接选择排序，归并排序D.归并排序，冒泡排序

10堆是一种有用的数据结构。

试判断下面的关键码序列中哪一个是堆（）

A．16，72，31，23，94，53B．94，53，31，72，16，23

C．16，53，23，94，31，72D．16，31，23，94，53，72

二、填空题（每空2分，共20空，总计40分）

1．在下面的程序段中，语句x+=1的频度是___________________，语句A[i][j]=1的频度是________________，整个程序的时间复杂度是___________________。

for（i=0;i

{

x+=1；

for（j=0;j<=n;j++）

A[i][j]=0;

B[j][i]=1;

}

2．在单链表指针为p的结点之后插入指针为s的结点，操作是__________________，_______________________。

3．从逻辑上可以把数据结构分为_____和两大类。

4．一个队列的输入顺序是a，b，c，d，e，则其输出序列为________________________。

5．一个具有N个顶点，K条边的无向图是一个森林（