四川大学计算机学院数据结构与算法分析期末试题(2013级A)

2022年四川大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-12、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入B.选择C.希尔D.二路归并3、以下数据结构中，（）是非线性数据结构。

A.树B.字符串C.队D.栈4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、每个结点的度或者为0或者为2的二叉树称为正则二叉树。

n个结点的正则二叉树中有（）个叶子。

A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/29、有关二叉树下列说法正确的是（）。

A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为210、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（）。

数据结构（本）期末综合练习2013年6月期末综合练习一1. 在数据结构和算法中，与所使用的计算机有关的是（）。

A．数据元数间的抽象关系B．数据的存储结构C．算法的时间复杂度 D．数据的逻辑结构2. 一种逻辑结构在存储时（）。

A．只要存储数据元素间的关系 B．只能采用一种存储结构C．可采用不同的存储结构 D．只要存储数据元素的值3 .对顺序表,以下叙述中正确的是 ( )。

A．用一组地址连续的存储单元依次存放线性表的数据元素B．各个数据元素的首地址是连续的C．数据元素不能随机访问D．插入操作不需要移动元素4 .对链表, 以下叙述中正确的是（）。

A．不能随机访问任一结点 B．结点占用的存储空间是连续的C．插入删除元素的操作一定要要移动结点 D．可以通过下标对链表进行直接访问5．设有一个长度为25的顺序表，要删除第10个元素(下标从1开始),需移动元素的个数为（）。

A．9 B．10 C．15 D．166．线性表在存储后,如果相关操作是:要求已知第i个结点的位置访问该结点的前驱结点，则采用（）存储方式是不可行的。

A．单链表 B．双链表 C．单循环链表 D．顺序表7. 设单向链表中,指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为( )。

A.p->next=p->next->next;B.p=p->next;C.p=p->next->next;D.p->next=p ;8．栈和队列的共同特点是（）。

A．都是先进后出 B．元素都可以随机进出C．只容许在端点处插入和删除元素 D．都是先进先出9．元素1，3，5，7按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的可能输出序列是（）。

（进栈出栈可以交替进行）。

A．7，5，3，1 B．7，3，1,5C．7，5，1，3 D．5,1，3，710．元素2，4，6，8按顺序依次进栈，按该栈的的可能输出序列依次入队列，该队列的可能输出序列是（）（进栈出栈可以交替进行）。

2012-2013山大软件数据结构期末试题(真题)回顾
一、简答题。

1.插入排序、选择排序、冒泡排序、基数排序、堆排序的算法中其比较次数与初始数据集顺序无关的是？请说明理由。

2.已知待散列的线性表为（1,8,16,27,25,28等数据），散列用的一维地址空间为11，假定选用的散列函数是H（K）= K mod 11，将其存入线性开型寻址散列和链表结构。

3.给一个树的层序遍历，中序遍历，写出其后序遍历。

4.给出二叉搜索树的层序遍历，问这个二叉搜索树是否是完全二叉树。

5.请说明广度优先搜索和深度优先搜索算法中所使用的堆栈、队列的作用。

二、应用题。

1.有学号1-36名学生，如果i , j两个学生住在同一个宿舍用（i,j）表示，集合S={（1,2），（4,19）......}如何求集合S中包含多少宿舍。

2.构建霍夫曼树，求ABCDEF的霍夫曼代码
3.有20门课程，如果i , j两门课的学习顺序为先学i ,再学j那么用（i , j）表示，集合S={(2,3),(4,6)....}，求至少要安排多少学期.
4.给出ABCDE消耗邻接矩阵，求A到个点的最短路径
三、算法程序题。

1.一个递增的链表，编写一个算法去除链表中的重复元素。

例如，将
（7,12,12,14,23）变为（7,12,14,23），请写出算法思想和算法实现并分析算法的复杂性。

2.编写一个算法如何判断一个用二叉树链表存储的二叉树是否是最大堆，写出算法思想
和算法实现。

《数据结构》试题（A卷）（考试时间：90分钟）一、单项选择题（本大题共15小题，每小题2分，共30分）（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分）1.（）是组成数据的基本单位，是一个数据整体中相对独立的单元。

A．数据 B.数据元素 C.数据对象 D.数据结构2.算法计算量的大小称为算法的（）。

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

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

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

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

9.队列操作的原则是（）。

A.后进先出B.先进先出C.只能进行插入D.只能进行删除10.栈中允许进行插入和删除的一端称为（）。

A.栈首B.栈尾C.栈顶D.栈底11．假设以数组A[n]存放循环队列的元素，其首尾指针分别为front和rear，则当前队列中的元素个数为（）。

A．（rear-front+n）%nB.rear-front+1C.(front-rear+n)%nD.(rear-front)%n12.最大容量为n的循环队列，队尾指针是rear，队首指针是front，则队空的判断条件是（）。

13.构。

14.15.12在q3．放了2个字符。

4．广义表（a,b,c,d）的表尾是。

5．一棵深度为k的二叉树，最多有个结点。

6．已知有向图G=（V，E），其中:V={v1,v2,v3,v4,v5,v6,v7},E={<v1,v2>,<v1,v3>,<v1,v4>,<v2,v5>,<v3,v5>,<v3,v6>,<v4,v6>,<v5,v7>,<v6,v7>},则G的拓扑序列是______。

7.有n个顶点的连通图至少有条边。

8.1.（）23.4（）5.6.7.8.9.（）10.采用线性探测法解决冲突问题，所产生的一系列后继散列地址必须大于等于原散列址。

算法与数据结构期末考试卷一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构被称为：A. 链表B. 栈C. 队列D. 数组2. 快速排序算法的时间复杂度在最坏情况下是：A. O(n)B. O(n log n)C. O(n^2)D. O(log n)3. 哈希表解决冲突最常用的方法是：A. 链地址法B. 线性探测法C. 二次探测法D. 双重哈希法4. 二叉树的遍历方式不包括：A. 前序遍历B. 中序遍历C. 后序遍历D. 广度优先遍历5. 堆排序算法是基于：A. 链表B. 栈C. 队列D. 堆...（此处省略其他选择题）二、简答题（每题10分，共20分）1. 请简述二叉搜索树与普通二叉树的区别。

2. 什么是递归？请举例说明递归在算法中的应用。

三、编程题（每题15分，共30分）1. 编写一个函数，实现对链表的反转。

2. 编写一个函数，实现快速排序算法。

四、综合应用题（每题15分，共30分）1. 描述如何使用哈希表实现一个简单的数据库索引系统。

2. 假设你有一个数组，其中包含了一些重复的数值，请编写一个算法来找出数组中出现次数超过数组长度一半的数值。

五、论述题（每题15分，共15分）1. 论述动态规划与贪心算法的区别，并给出一个动态规划问题的例子。

六、附加题（10分，可选做）1. 请设计一个算法，用于检测一个字符串是否是回文。

如果字符串是回文，请返回True，否则返回False。

注意：本试卷中所有题目的答案必须以书面形式给出，编程题需要提供完整的代码实现。

祝各位考生考试顺利，取得优异成绩。

数据结构与算法分析习题及参考答案四川⼤学计算机学院《数据结构与算法分析》课程模拟试卷及参考答案模拟试卷⼀⼀、单选题（每题 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 个元素之后插⼊⼀个元素B. 从队头删除⼀个元素C. 判断⼀个队列是否为空D.读取队头元素的值4. 字符A 、B 、C 依次进⼊⼀个栈，按出栈的先后顺序组成不同的字符串，⾄多可以组成( )个不同的字符串？A.14B.5C.6D.85. 由权值分别为3,8,6,2的叶⼦⽣成⼀棵哈夫曼树，它的带权路径长度为( )。

A ． 11 B.35 C. 19 D. 53 以下6-8题基于图1。

6. 该⼆叉树结点的前序遍历的序列为( )。

A. E 、G 、F 、A 、C 、D 、BB. E 、A 、G 、C 、F 、B 、DC. E 、A 、C 、B 、D 、G 、FD. E 、G 、A 、C 、D 、F 、B 7. 该⼆叉树结点的中序遍历的序列为( )。

A. A 、B 、C 、D 、E 、G 、FB. E 、A 、G 、C 、F 、B 、DC. E 、A 、C 、B 、D 、G 、FE. B 、D 、C 、A 、F 、G 、E8. 该⼆叉树的按层遍历的序列为( )。

A ．E 、G 、F 、A 、C 、D 、B B. E 、A 、C 、B 、D 、G 、FC. E 、A 、G 、C 、F 、B 、DD. E 、G 、A 、C 、D 、F 、BE A G CB D F 图19.下⾯关于图的存储的叙述中正确的是( )。

四川大学“精品课程”计算机科学与技术专业（本科）《数据结构与算法分析》课程考试说明与模拟试卷第一部分考试说明数据结构与算法分析》是计算机科学与技术专业统设的一门重要的必修专业基础课，它主要研究数据的各种逻辑结构和在计算机中的存储结构，还研究对数据进行的插入、查找、删除、排序、遍历等基本运算或操作以及这些运算在各种存储结构上具体实现的算法。

由于本课程的主教材采用C++语言描述算法，期末卷面考试也采用C++语言描述，因而要求在做平时作业和上机实验操作时用C++开发工具（如：Visual C++或C++ Builder或Borland C++）。

下面按照主教材中各章次序给出每章的具体复习要求，以便同学们更好地进行期末复习。

第一章绪论重点掌握的内容：1. 数据结构的二元组表示，对应的图形表示，序偶和边之间的对应关系。

2. 集合结构、线性结构、树结构和图结构的特点。

3. 抽象数据类型的定义和表示方法。

4. 一维和二维数组中元素的按下标和按地址的访问方式以及相互转换，元素地址和数组地址的计算，元素占用存储空间大小和数组占用存储空间大小的计算。

5. 普通函数重载和操作符函数重载的含义，定义格式和调用格式。

6. 函数定义中值参数和引用参数的说明格式及作用，函数被调用执行时对传送来的实际参数的影响。

7. 算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。

8. 一个简单算法的最好、最差和平均这三种情况的时间复杂度的计算。

对于本章的其余内容均作一般掌握。

第二章线性表重点掌握的内容：1. 线性表的定义及判别和抽象数据类型的描述，线性表中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。

2. 线性表的顺序存储结构的类型定义，即List类型的定义和每个域的定义及作用。

3. 线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。

4.链接存储的概念，线性表的单链接和双链接存储的结构，向单链表中一个结点之后插入新结点或从单链表中删除一个结点的后继结点的指针链接过程。

试题一一、单项选择题（每小题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个元素之后插入一个元素B）从队头删除一个元素C）判断一个队列是否为空D）读取队头元素的值（4）字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串。

A）14 B）5 C）6D）8（5）由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）。

A）11 B）35 C）19 D）53 以下6-8题基于下图：（6）该二叉树结点的前序遍历的序列为（）。

A）E、G、F、A、C、D、B B）E、A、G、C、F、B、DC）E、A、C、B、D、G、F D）E、G、A、C、D、F、B（7）该二叉树结点的中序遍历的序列为（）。

A）A、B、C、D、E、G、F B）E、A、G、C、F、B、DC）E、A、C、B、D、G、F D）B、D、C、A、F、G、E（8）该二叉树的按层遍历的序列为（）。

A）E、G、F、A、C、D、B B）E、A、C、B、D、G、FC）E、A、G、C、F、B、D D）E、G、A、C、D、F、B（9）下面关于图的存储的叙述中正确的是（）。

A）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B）用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C）用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D）用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关（10）设有关键码序列(q,g,m,z,a,n,p,x,h)，下面哪一个序列是从上述序列出发建堆的结果?（）A）a,g,h,m,n,p,q,x,z B）a,g,m,h,q,n,p,x,zC）g,m,q,a,n,p,x,h,z D）h,g,m,p,a,n,q,x,z二、（本题8分）对于序列{8,18,6,16,29,28}，试写出堆顶元素最小的初始堆。

《数据结构与算法》复习题一、选择题。

1．在数据结构中，从逻辑上可以把数据结构分为 C 。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。

A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。

A．逻辑 B．存储 C．逻辑和存储 D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。

A．数据的处理方法 B．数据元素的类型C．数据元素之间的关系 D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。

A．各结点的值如何 B．结点个数的多少C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。

6．以下说法正确的是 D 。

A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。

（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是 O(n2) 。

s =0;for( I =0; i<n; i++)for(j=0;j<n;j++)s +=B[i][j]; sum = s ;9．下面程序段的时间复杂度是 O(n*m) 。

for( i =0; i<n; i++)for(j=0;j<m;j++)A[i][j] ＝ 0;10．下面程序段的时间复杂度是 O(log3n) 。

i ＝ 0；while（i<=n）i = i * 3；11．在以下的叙述中，正确的是 B 。