川大精品课数据结构复习题docx.docx
《川大精品课数据结构复习题docx.docx》由会员分享，可在线阅读，更多相关《川大精品课数据结构复习题docx.docx（80页珍藏版）》请在冰点文库上搜索。
川大精品课数据结构复习题docx
四川大学“精品课程”
计算机科学与技术专业（本科）
《数据结构与算法分析》课程
考试说明与模拟试卷
第一部分考试说明
数据结构与算法分析》是计算机科学与技术专业统设的一门重要的必修专业基础课，它主要研究数据的各种逻辑结构和在计算机中的存储结构，还研究对数据进行的插入、查找、删除、排序、遍历等基本运算或操作以及这些运算在各种存储结构上具体实现的算法。
由于本课程的主教材采用C++语言描述算法，期末卷面考试也采用C++语言描述，因而要求在做平时作业和上机实验操作时用C++幵发工具（如：
VisualC++或C++Builder或BorlandC++）。
下面按照主教材中各章次序给出每章的具体复习要求，以便同学们更好地进行期末复习。
第一章绪论
重点掌握的内容：
1.数据结构的二元组表示，对应的图形表示，序偶和边之间的对应关系。
2.集合结构、线性结构、树结构和图结构的特点。
3.抽象数据类型的定义和表示方法。
4.一维和二维数组中元素的按下标和按地址的访问方式以及相互转换，元素地址和数组地址的计算，元素占用存储空间大小和数组占用存储空间大小的计算。
5.普通函数重载和操作符函数重载的含义，定义格式和调用格式。
6.函数定义中值参数和引用参数的说明格式及作用，函数被调用执行时对传送来的实际参数的影响。
7.算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。
&一个简单算法的最好、最差和平均这三种情况的时间复杂度的计算。
对于本章的其余内容均作一般掌握。
第二章线性表
重点掌握的内容：
1.线性表的定义及判别和抽象数据类型的描述，线性表中毎一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。
2.线性表的顺序存储结构的类型定义，即List类型的定义和每个域的定义及作用。
3.线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。
4.链接存储的概念，线性表的单链接和双链接存储的结构，向单链表中一个结点之后插入新结点或从单链表中删除一个结点的后继结点的指针链接过程。
5.单链表中结点的结构，每个域的定义及作用，即LNode类型的定义及结构。
6.带表头附加结点的链表、循环链表、双向链表的结构特点。
7.线性表的每一种运算在单链表上实现的算法及相应的时间复杂度。
&在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计。
9.Josephus问题的求解过程。
10.顺序表和线性链表的性能比较及各自使用背景。
对于本章的其余内容均作一般掌握。
第三章数组和广义表
重点掌握的内容：
1.多维数组的逻辑结构特征。
2.多维数组的顺序存储结构及地址计算公式。
3.数组是一种随机存取结构的原因。
4.特殊矩阵和稀疏矩阵的概念。
5.特殊矩阵（包括对角矩阵）和压缩存储的下标变换方法及所需存储空间。
6.稀疏矩阵的定义和三元组线性表及三列二维数组表示。
7.稀疏矩阵的顺序存储、带行指针向量的链接存储，在每一种存储中非零元素结点的结构。
&稀疏矩阵的转置运算。
9.广义表的定义和表示，广义表长度和深度的计算。
10.广义表上的求表头、表尾运算。
5.广义表的链接存储结构中结点类型的定义，分别求广义表长度和深度的递归算法,它们对应的时间复杂度。
一般掌握的内容：
稀疏矩阵转置的算法描述。
对于本章的其余内容均作」般了解。
第四章栈和队列
重点掌握的内容：
1.栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。
2.栈的顺序存储结构的类型定义，即Stack类型的定义和每个域的定义及作用。
3.栈的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。
4.栈的每…种运算在链接存储结构上实现的算法及相应的时间复杂度。
5.算术表达式的中缀表示和后缀表示，以及相互转换的规则，后缀表达式求值的方法。
6.给定n个栈元素，出栈可能或不可能的序列数。
7.队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。
&队列的顺序存储结构的类型定义，即Queue类型的定义和每个域的定义及作用。
9.队列的每一种运算在顺序存储结构上实现的算法及相应的时间复杂度。
10.利用栈和队列解决简单问题的算法分析和设计。
11.双端队的概念及可能出队序列。
12.队和栈的应用背景，如cpu队、进程队、打印机队。
13.链队的各种存储表示。
一般掌握的内容：
1.后缀表达式求值的算法，把中缀表达式转换为后缀表达式的算法。
2.队列的链接存储结构，以及实现每一种队列运算的算法和相应的时间复杂度。
对于本章的其余内容均作」般了解。
第五章字符串
重点掌握的内容：
1.串的有关概念及基本运算。
2.串与线性表的关系。
3.串的各种存储结构。
4.一个串中真子串和子串个数的确定。
一般掌握的内容：
1.串上各种运算的实现及其时间性能分析。
2.使用C++提供的操作函数构造与串相关的算法解决简单的应用问题。
第六章树和二叉树
重点掌握的内容：
1.树和二义树的定义，对于「棵具体树和二义树的二元组表示及广义表表示。
2.树和二叉树的概念，如结点的度、树的度、树叶、分枝结点、树的层数、树的深度等。
3.不同结点数的树和二叉树的形态。
4.树和二叉树的性质，如已知树或二叉树的深度h可求出相应的最多结点数，已知结点数n可求出对应树或二叉树的最大和最小高度。
5.二叉树中结点的编号规则和对应的顺序存储结构。
6.二叉树的链接存储结构及存储结点的类型定义，即BTreeNode类型的定义和每个域的定义及作用。
7.二叉树的先序、中序、后序、遍历的递归过程和递归算法，中序遍历的非递归算法，按层遍历的过程和算法，每种算法的时间复杂度。
8.二叉树的先序、中序、后序遍历序列，唯一确定一棵二叉树的原则。
9.算术表达式的二叉树表示及逆波兰表达式、中缀表示。
一般掌握的内容：
1.普通树的链接存储结构，GTreeNode类型的定义和每个域的定义及作用。
2.普通树的先根、后根和按层遍历的过程及算法。
3.在链接存储的二叉树上实现指定功能的算法分析和设计。
对于本章的其余内容均作一般了解。
二叉树的应用
重点掌握的内容：
1.二叉搜索树的定义和性质、建立。
2.二叉捜索树查找的递归算法和非递归算法，相应的时间复杂度，查找一个元素的查找长度，即从树根结点到该结点的路径上的结点数。
3.二义搜索树插入的递归算法和非递归算法，相应的时间复杂度，根据■组数据生成一棵二叉搜索树的过程。
4.堆的定义和顺序存储结构，小根堆和大根堆的异同及堆的判别、建立堆的过程。
5.向堆中插入元素的过程、算法描述及时间复杂度。
6.从堆中删除元素的过程、算法描述及时间复杂度。
7.哈夫曼树的定义，树的带权路径长度的计算，根据若干个叶子结点的权构造哈夫曼树的过程。
8•顺序二叉树及二叉链表表示二叉树。
9.已知关键字序列{22,16,3&89,56,16,79},试构造平衡二叉树。
对本章的其余内容均作…般了解。
第七章图
重点掌握的内容：
1.图的顶点集和边集的表示。
2.图的一些概念的含义，如顶点、边、度、完全图、子图、路径、路径长度、连通图、权、网等。
3.图的邻接矩阵、邻接表、邻接多重表和十字链表四种存储结构及相应的空间复杂度。
4.存储图使用的vexlist,adjmatrix,adjlist,edgenode,edgeset,edge等类型的定义及用途。
5.图的深度优先和广度优先搜索遍历的过程。
6.对分别用邻接矩阵和用邻接表表示的图进行深度优先搜索遍历的过程、算法描述以及相应的时间复杂度。
7.对分别用邻接矩阵和用邻接表表示的图进行广度优先捜索遍历的过程、算法描述以及相应的时间复杂度。
&图的生成树（若一个具有n个顶点，e条边的无向图是一个森林（n>e）,则该森林中必有多少棵树。
）、深度优先生成树和广度优先生成树、生成树的权、最小生成树等的定义。
9.根据普里姆算法求图的最小生成树的过程。
10.根据克鲁斯卡尔算法求图的最小生成树的过程。
11.图的拓扑序列和拓扑排序的概念，求图的拓扑序列的方法，对用邻接表表示的图进行拓扑排序的过程。
12.强连通图的最少边数。
一般掌握的内容：
1.根据普里姆算法求图的最小生成树的算法描述。
2.根据克鲁斯卡尔算法求图的最小生成树的算法描述。
3.对用邻接表表示的图进行拓扑排序的和算法描述。
对本章的其余内容均作一般了解。
第八章查找
重点掌握的内容：
1.在一维数组及单链表上进行顺序查找的过程、算法、成功及不成功的平均查找长度和时间复杂度。
2.在一维数组上进行二分查找的过程、递归和非递归算法、平均查找长度和时间复杂度，二分查找一个给定值元素的查找长度（即查找路径上的元素数），二分查找对应的判定树的性质。
3.散列存储的概念，散列函数、散列表、冲突、同义词、装填因子等术语的含义。
4.利用除留余数法建立散列函数求元素散列地址的方法。
5.利用开放定址法中的线性探查法处理冲突进行散列存储和查找的过程，利用链接法处理冲突进行散列存储和查找的过程。
6.根据除留余数法构造散列函数，采用线性探查法或链接法处理冲突，把一组数据散列存储到散列表中，计算出一个给定值元素的查找长度和查找所有元素的平均查找长度。
7.B_树中每个结点的结构，树根结点或非树根结点中关键字的个数范围和子树的个数范围，B_的结构特性，从B—树上查找一个给定值元素的过程。
一般掌握的内容：
1.B_树查找算法。
2.向匸树中插入元素的过程。
对本章的其余内容均作一般了解。
第九章排序
重点掌握的内容：
1.直接插入、直接选择和冒泡排序的方法，排序过程及时间复杂度。
2.在堆排序中建立初始堆的过程和利用堆排序的过程，对一个分支结点进行筛运算的过程、算法及时间复杂度，整个堆排序的算法描述及时间复杂度。
3.快速排序的方法，对一组数据的排序过程，对应的二叉搜索树，快速排序过程中划分的层数和递归排序区间的个数。
4.递归排序的递归算法，它在平均情况下的时间和空间复杂度，在最坏情况下的时间和空间复杂度。
5.二路归并排序的方法和对数据的排序过程，每趟排序前、后的有序表长度，二路归并排序的趟数、时间复杂度和空间复杂度。
6.各种排序方法的不同数据序的比较、最好、最坏、平均情况。
7.哪些排序不受初始数据的影响。
一般掌握的内容：
1.每一种排序方法的稳定性。
2.直接插入排序和直接选择排序的算法。
一般了解的内容：
1.二路归并排序过程中涉及的每个算法描述。
2.冒泡排序算法。
第十章文件
重点掌握的内容：
1.文件的有关概念。
2.文件的逻辑结构及其操作。
3.索引文件的组织方式和特点。
4.索引文件的的查询和更新操作的基本思想。
5.两种最常用的索引顺序文件（ISAM文件和VSAM文件）的组织方式和特点。
6.在ISAM文件和VSAM文件上查找和更新操作的基本思想。
7.散列文件的组织方式和特点。
&散列文件的查询和更新操作的基本思想。
9.多关键字文件和其它文件的差别。
10.多重表文件和倒排文件组织方式和特点。
11.多重表文件和倒排文件查询和更新操作的基本思想。
本章其它内容一般掌握
第二部分模拟试卷
模拟试题
（一）
一、单项选择题（每小题2分，共20分）
（1）以下数据结构中哪一个是线性结构？
（）
A）有向图B）队列C）线索二叉树D）B树
（2）在个单链表HL中，若要在当前由指针p指向的结点后面插入■个由q指向的
结点，则执行如下（）语句序列。
A）p=q;p->next=q;B）p->next=q;q->next=p;
C）p->next=q->next;p=q;D）q->next=p->next;p->next=q;
（3）（）不是队列的基本运算。
A）在队列第i个元素Z后插入■个元素B）从队头删除•个元素
C）判断■个队列是否为空D）读取队头元素的值
（4）字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可
以组成（）个不同的字符串。
A）14B）5C）6D）8
（5）由权值分别为3,8,6,2的叶子生成■棵哈夫曼树，它的带权路径长度为（）o
（6）该二义树结点的前序遍历的序列为（）。
A）E、G、F、A、C、D、B
B）
E、A、G、C、F、B、
D
C）E、A、C、B、D、G、F
D）
E、G、A、C、D、F、
B
（7）该二叉树结点的中序遍历的序列为（
）O
A）A、B、C、D、E、G、F
B）
E、A、G、C、F、B、
D
C）E、A、C、B、D、G、F
D）
B、D、C、A、F、G、
E
（8）该二叉树的按层遍历的序列为（
）
O
A）E、G、F、A、C、D、B
B）
E、A、C、B、D、G、
F
C）E、A、G、C、F、B、D
D）
E、G、A、C、D、F、
B
（9）下面关于图的存储的叙述中正确的是
（
）O
A）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
B）用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C）用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关
D）用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
（10）设有关键码序列（q,gun,z,a,n,p,x,h）,下面哪一个序列是从上述序列出发建堆的结果？
（）
A）a,g,h,m,n,p,q,x,zB）a,g,m,h,q,n,p,x,zC）g,m,q,a,n,p,x,h,zD）h,g,m,p,a,n,q,x,z
二、（每小题4分，共8分）
已知一个6x5稀疏矩阵如下所示，试：
o
0
0
0
5
0
0001
0000
-1000
000-2
0000
0700
（1）写出它的三元组线性表;
（2）给出三元组线性表的顺序存储表示。
三、（本题8分）
求网的最小生成树有哪些算法？
它们的时间复杂度分别下多少，各适用何种情况？
四、（每小题4分，共8分）
对于如下图所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：
（1）从顶点V1岀发进行深度优先搜索所得到的深度优先生成树;
（2）从顶点v2出发进行广度优先搜索所得到的广度优先生成树。
五、（本题8分）
已知一个图的顶点集V和边集E分别为：
V二{1,2,3,4,5,6,7};
E={<2,1>,<3,2>,v3,6>,v4,3>,v4,5>,v4,6>,v5,1>,<5,7>,<6,1>,v6,2>,v6,5>};
若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试给出得到的拓扑排序的序列。
六、（本题8分）
对于序列{8,18,6,16,29,28}，试写出堆顶元素最小的初始堆。
七、（本题8分）
一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。
试求出空格处的内容，并画出该二叉树。
先序序列：
_B_F_ICEH_G
中序序列：
DKFIAEJC
后序序列：
_K_FBHJ_G_A
八、（每小题2分，共8分）
设有序列:
w={23,24,27,80,28},试给出:
（1）二叉排序树；
（2）哈夫曼树；
（3）平衡二义树；
（4）对于增量d=2按降序执行一遍希尔排序的结果。
九、（本题9分）
有关键字序列{7,23,6,9,17,19,21,22,5},Hash函数为H（key）=key%5,采用链地址法处理冲突，试构造哈希表。
十、（本题15分）
假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如下图所示的树状显示二叉树。
模拟试题
（一）参考答案
一、单项选择题
（1）B
（2）D（3）A（4）B（5）B
（6）C（7）A（8）C（9）B（10）B
二、（每小题4分，共8分）
（1）（（1,5,1）,（32-1）,（4,5,-2）,（5丄5）,（637））
（2）三元组线性表的顺序存储表示如下所示：
655_
151
32-1
45-2
515
627
三、（本题8分）
求网的最小生成树可使用Prim算法，时间复杂度为0（『），此算法适用于边较多的稠密图，也可使用Kruskal算法，时间复杂度为O（eloge）,此算法适用于边较少的稀疏图。
四、（每小题4分，共8分）
（1）DFS：
vlv2v3v4v5
（2）BFS：
v2v3v4v5vl
五、（本题8分）
拓扑排序为：
4365721
六、（本题8分）
所构造的堆如下图所示：
七、（本题8分）在先序序列空格中依次填ADKJ,中序中依次填BHG,后序中依次填DIEC。
八、（每小题2分，共8分）
（1）二叉排序树如下图所示：
（2）哈夫曼树如下图所示:
0
1
2
3
4
哈希表如下图所示:
二*5|A|
二》6|八|
二叫7]+W二胡22|八|
十、（本题15分）
从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示•个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。
C++语言版测试程序见examl\10c++,具体算当如下：
template
voiddisplay_BT_with_tree_shape（constBinary_tree&T）
{
aux_display_BT_with_tree_shape（T.get_root（））;
template
voidaux_display_BT_with_tree_shape（Binary_node*sub_root,intlevel=1）
//按旃状形£显示二叉前，level为层次数，可设根结点的层关数为1
{
if（sub_root!
=NULL）
{〃空树不显式，只显式非空树
aux_display_BT_with_tree_shape（sub_root->right,level+l）;//显示右子树cout«endl;〃显示新行
for（inti=O;icout«H〃确保在第level列显示结点
cout«sub_root->data;〃显示结点
aux_display_BT_with_tree_shape（sub_root->left,level+l）;//显示左子树
}
C语言版测试程序见examl\10c,具体算当如下:
voidDisplayBTWithTreeShape（BiTreeT,intlevel=l）
//
按树状形式显示二叉树，level为层次数，可设根结点的层次数为1
i
if（T）
{〃空树不显式，只显式非空树
DisplayBTWithTreeShape（T->rchild,level+l）;
〃显示右子树
cout«endl;
〃显示新行
for（inti=0;icout«HH;
〃确保在第level列显示结点
cout«T->data;
〃显示结点
}
DisplayBTWithTreeShape（T->lchildjevel+l）;
}
〃显示左子树
模拟试题
（二）
-、单项选择题（每小题2分，共20分）
（1）设Huffman树的叶子结点数为m,贝IJ结点总数为（）。
C）2m+lD）m+1
（2）若丿W亭存储的循环队列的QueueMaxSize=n,贝ll该队列最多可存储（）个元素。
A）nB）n-1C）n+1D）不确定
（3）下述哪一条是顺序存储方式的优点？
（）
A）存储密度大B）插入和删除运算方便
C）获取符合某种条件的元素方便D）查找运算速度快
（4）设有一个二维数组假设A[0][0]存放位置在6OO（io”川3]⑶存放位置在67&如,
毎个元素占一个空间,问A⑵[3]g存放在什么位置？
（脚注io表示用10进制表示,m>3）（）。
A）658B）648C）633D）653
（5）下列关于二义树遍历的叙述中，正确的是（）。
A）若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点
B）若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点
C）若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点
D）若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点
（6）k层二叉树的结点总数最多为（）。
A）2k-lB）2k+lC）2K-1D）2k_l
（7）对线性表进行二分法查找，其前提条件是（）。
A）线性表以链接方式存储，并且按关键码值排好序
B）线性表以顺序方式存储，并且按关键码值的检索频率排好序
C）线性表以顺序方式存储，并且按关键码值排好序
D）线性表以链接方式存储，并且按关键码值的检索频率排好序
（8）对n个记录进行堆排序，所需要的辅助存储空间为（
A）O（log2n）B）O（n）C）0
（1）
）。
D）O（n2）
（9）对于线性表（7,34,77,25,64,49,20,14）进彳亍散列存储时，若选用H（K）=K%7作为散列函数，贝散列地址为0的元素有（）个。
（10）下列关于数据结构的叙述中，正确的是（）。
A）数组是不同类型值的集合
B）递归算法的程序结构比迭代算法的程序结构更为精炼
C）树是一种线性结构
D）用一维数组存储一棵完全二叉树是有效的存储方法
二、（本题8分）
假定一棵二叉树广义表表示为a（b（c）,d（e,f））,分别写出对它进彳亍先序、中序、后序、按
层遍历的结果。
三、（每小题4分，共8分）
已知」个无向图的顶点集为｛a,b,c,d,e｝,其邻接矩阵如下所示:
01001
10010
00011
01101
10110
（1）画出该图的图形；
（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。
四、（本题8分）
树有哪些遍历方法？
它们分别对应于把树转变为二叉树的哪些遍历方法？
五、（本题8分）
设有数组A卜1:
3,0:
6,-2:
3],按行为主序存放在2000开始的连续空间中，如元素的长度是5
升级会员 