《数据结构》四川大学 期终复习试题+答案

四川大学“精品课程” 计算机科学与技术专业（本科） 《数据结构与算法分析》课程

考试说明与模拟试卷 第一部分 考试说明

数据结构与算法分析》是计算机科学与技术专业统设的一门重要的必修专业基础课，它主要研究数据的各种逻辑结构和在计算机中的存储结构，还研究对数据进行的插入、查找、删除、排序、遍历等基本运算或操作以及这些运算在各种存储结构上具体实现的算法。由于本课程的主教材采用C++语言描述算法，期末卷面考试也采用C++语言描述，因而要求在做平时作业和上机实验操作时用C++开发工具（如：Visual C++或 C++ Builder或Borland C++）。

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

第一章 绪论

重点掌握的内容：

1. 数据结构的二元组表示，对应的图形表示，序偶和边之间的对应关系。 2. 集合结构、线性结构、树结构和图结构的特点。 3. 抽象数据类型的定义和表示方法。

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

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

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

7. 算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。 8. 一个简单算法的最好、最差和平均这三种情况的时间复杂度的计算。 对于本章的其余内容均作一般掌握。

第二章 线性表

重点掌握的内容：

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

2. 线性表的顺序存储结构的类型定义，即List类型的定义和每个域的定义及作用。 3. 线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。 4. 链接存储的概念，线性表的单链接和双链接存储的结构，向单链表中一个结点之

后插入新结点或从单链表中删除一个结点的后继结点的指针链接过程。

5. 单链表中结点的结构，每个域的定义及作用，即LNode类型的定义及结构。 6. 带表头附加结点的链表、循环链表、双向链表的结构特点。

7. 线性表的每一种运算在单链表上实现的算法及相应的时间复杂度。 8. 在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计。 9．Josephus问题的求解过程。

10．顺序表和线性链表的性能比较及各自使用背景。 对于本章的其余内容均作一般掌握。

第三章 数组和广义表

重点掌握的内容：

1. 多维数组的逻辑结构特征。

2. 多维数组的顺序存储结构及地址计算公式。 3．数组是一种随机存取结构的原因。 4．特殊矩阵和稀疏矩阵的概念。

5．特殊矩阵（包括对角矩阵）和压缩存储的下标变换方法及所需存储空间。 6. 稀疏矩阵的定义和三元组线性表及三列二维数组表示。

7. 稀疏矩阵的顺序存储、带行指针向量的链接存储，在每一种存储中非零元素结点的结构。

8. 稀疏矩阵的转置运算。

9. 广义表的定义和表示，广义表长度和深度的计算。 10．广义表上的求表头、表尾运算。

5. 广义表的链接存储结构中结点类型的定义，分别求广义表长度和深度的递归算法，它们对应的时间复杂度。

一般掌握的内容：

稀疏矩阵转置的算法描述。

对于本章的其余内容均作一般了解。

第四章 栈和队列

重点掌握的内容：

1. 栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。

2. 栈的顺序存储结构的类型定义，即Stack类型的定义和每个域的定义及作用。 3．栈的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。 4. 栈的每一种运算在链接存储结构上实现的算法及相应的时间复杂度。

5. 算术表达式的中缀表示和后缀表示，以及相互转换的规则，后缀表达式求值的方法。

6．给定n个栈元素, 出栈可能或不可能的序列数。

7. 队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。

8. 队列的顺序存储结构的类型定义，即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,38,89,56，16，79}，试构造平衡二叉树。 对本章的其余内容均作一般了解。

第七章 图

重点掌握的内容：

1. 图的顶点集和边集的表示。

2. 图的一些概念的含义，如顶点、边、度、完全图、子图、路径、路径长度、连通图、权、网等。

3. 图的邻接矩阵、邻接表、邻接多重表和十字链表四种存储结构及相应的空间复杂度。

4. 存储图使用的vexlist, adjmatrix, adjlist, edgenode, edgeset, edge等类型的定义及用途。

5. 图的深度优先和广度优先搜索遍历的过程。

6. 对分别用邻接矩阵和用邻接表表示的图进行深度优先搜索遍历的过程、算法描述以及相应的时间复杂度。

7. 对分别用邻接矩阵和用邻接表表示的图进行广度优先搜索遍历的过程、算法描述以及相应的时间复杂度。

，8. 图的生成树（若一个具有n个顶点，e条边的无向图是一个森林（n＞e）

则该森林中必有多少棵树。）、深度优先生成树和广度优先生成树、生成树的权、最

小生成树等的定义。

9. 根据普里姆算法求图的最小生成树的过程。

10．根据克鲁斯卡尔算法求图的最小生成树的过程。

11. 图的拓扑序列和拓扑排序的概念，求图的拓扑序列的方法，对用邻接表表示的图进行拓扑排序的过程。

12．强连通图的最少边数。 一般掌握的内容：

1．根据普里姆算法求图的最小生成树的算法描述。 2．根据克鲁斯卡尔算法求图的最小生成树的算法描述。 3. 对用邻接表表示的图进行拓扑排序的和算法描述。 对本章的其余内容均作一般了解。

第八章 查找

重点掌握的内容：

1. 在一维数组及单链表上进行顺序查找的过程、算法、成功及不成功的平均查找长度和时间复杂度。

2. 在一维数组上进行二分查找的过程、递归和非递归算法、平均查找长度和时间复杂度，二分查找一个给定值元素的查找长度（即查找路径上的元素数），二分查找对应的判定树的性质。

3. 散列存储的概念，散列函数、散列表、冲突、同义词、装填因子等术语的含义。 4. 利用除留余数法建立散列函数求元素散列地址的方法。

5. 利用开放定址法中的线性探查法处理冲突进行散列存储和查找的过程，利用链接法处理冲突进行散列存储和查找的过程。

6. 根据除留余数法构造散列函数，采用线性探查法或链接法处理冲突，把一组数据散列存储到散列表中，计算出一个给定值元素的查找长度和查找所有元素的平均查找长度。

7. B_树中每个结点的结构，树根结点或非树根结点中关键字的个数范围和子树的个数范围，B_的结构特性，从B_树上查找一个给定值元素的过程。

一般掌握的内容： 1. B_树查找算法。

2. 向B_树中插入元素的过程。 对本章的其余内容均作一般了解。

第九章 排序

重点掌握的内容：

1. 直接插入、直接选择和冒泡排序的方法，排序过程及时间复杂度。

2. 在堆排序中建立初始堆的过程和利用堆排序的过程，对一个分支结点进行筛运算

的过程、算法及时间复杂度，整个堆排序的算法描述及时间复杂度。

3. 快速排序的方法，对一组数据的排序过程，对应的二叉搜索树，快速排序过程中划分的层数和递归排序区间的个数。

4. 递归排序的递归算法，它在平均情况下的时间和空间复杂度，在最坏情况下的时间和空间复杂度。

5. 二路归并排序的方法和对数据的排序过程，每趟排序前、后的有序表长度，二路归并排序的趟数、时间复杂度和空间复杂度。

6．各种排序方法的不同数据序的比较、最好、最坏、平均情况。 7．哪些排序不受初始数据的影响。 一般掌握的内容：

1. 每一种排序方法的稳定性。

2. 直接插入排序和直接选择排序的算法。 一般了解的内容：

1. 二路归并排序过程中涉及的每个算法描述。 2. 冒泡排序算法。

第十章 文件

重点掌握的内容： 1. 文件的有关概念。

2. 文件的逻辑结构及其操作。 3. 索引文件的组织方式和特点。

4．索引文件的的查询和更新操作的基本思想。

5. 两种最常用的索引顺序文件(ISAM文件和VSAM文件) 的组织方式和特点。 6. 在ISAM文件和VSAM文件上查找和更新操作的基本思想。 7. 散列文件的组织方式和特点。

8. 散列文件的查询和更新操作的基本思想。 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个元素之后插入一个元素 B）从队头删除一个元素 C）判断一个队列是否为空 D）读取队头元素的值

（4）字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（ ）个不同的字符串。

A）14 B）5 C）6 D）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、D C）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、D C）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、F C）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,z C）g,m,q,a,n,p,x,h,z D）h,g,m,p,a,n,q,x,z

二、（每小题4分，共8分）

已知一个6?5稀疏矩阵如下所示，试：

?00?00??0?1??00?50???000000000000701? 0??0???2?0??0??（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>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};

若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试给出得到的拓扑排序的序列。

六、（本题8分）

对于序列{8,18,6,16,29,28}，试写出堆顶元素最小的初始堆。 七、（本题8分）

一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。

先序序列： B F ICEH G 中序序列：D KFIA EJC 后序序列： 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 （6）C （7）A （8）C （9）B 二、（每小题4分，共8分）

（1） ((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) （2）三元组线性表的顺序存储表示如下所示：

?6?1??3??4?5??6?5525125?1?? ?1???2?5??7??（5）B

（10）B

三、（本题8分）

求网的最小生成树可使用Prim算法，时间复杂度为O(n2)，此算法适用于边较多的稠密图，也可使用Kruskal算法，时间复杂度为O(eloge)，此算法适用于边较少的稀疏图。

四、（每小题4分，共8分） （1）DFS：v1 v2 v3 v4 v5 （2）BFS：v2 v3 v4 v5 v1 五、（本题8分）

拓扑排序为： 4 3 6 5 7 2 1 六、（本题8分）

所构造的堆如下图所示：

七、（本题8分）

在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。 八、（每小题2分，共8分） （1）二叉排序树如下图所示：

（2）哈夫曼树如下图所示：

（3）平衡二叉树如下图所示：

（4）对于增量d=2按降序执行一遍希尔排序的结果：28,80,27,24,23 九、（本题9分） 哈希表如下图所示：

十、（本题15分）

从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。

C++语言版测试程序见exam1\\10c++，具体算当如下：

template

void display_BT_with_tree_shape(const Binary_tree &T) {

aux_display_BT_with_tree_shape(T.get_root()); }

template

void aux_display_BT_with_tree_shape(Binary_node *sub_root,int level = 1) // 按树状形式显示二叉树，level为层次数，可设根结点的层次数为1 { if(sub_root != NULL) { //空树不显式，只显式非空树 aux_display_BT_with_tree_shape(sub_root->right,level+1);//显示右子树 cout<data; //显示结点 aux_display_BT_with_tree_shape(sub_root->left,level+1);//显示左子树 } }

C语言版测试程序见exam1\\10c，具体算当如下：

void DisplayBTWithTreeShape(BiTree T,int level=1) // 按树状形式显示二叉树，level为层次数，可设根结点的层次数为1 { if(T) { //空树不显式，只显式非空树 DisplayBTWithTreeShape(T->rchild,level+1); //显示右子树 cout<data; //显示结点 DisplayBTWithTreeShape(T->lchild,level+1); //显示左子树 } }

模拟试题（二）

一、单项选择题（每小题 2 分，共20分）

（1）设Huffman树的叶子结点数为m，则结点总数为（ ）。

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

（2）若顺序存储的循环队列的QueueMaxSize=n，则该队列最多可存储（ ）个元素。

A）n B）n-1 C）n+1 D）不确定 （3）下述哪一条是顺序存储方式的优点？（ ）

A）存储密度大 B）插入和删除运算方便

C）获取符合某种条件的元素方便 D）查找运算速度快

（4）设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，

m>3） 每个元素占一个空间，问A[2][3](10)存放在什么位置？（脚注(10)表示用10进制表示，（ ）。

A）658 B）648 C）633 D）653 （5）下列关于二叉树遍历的叙述中，正确的是（ ）。

A）若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点

B）若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点

C）若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点

D）若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点

（6）k层二叉树的结点总数最多为（ ）。

A）2k-1 B）2k+1 C）2K-1 D）2k-1 （7）对线性表进行二分法查找，其前提条件是（ ）。

A）线性表以链接方式存储，并且按关键码值排好序

B）线性表以顺序方式存储，并且按关键码值的检索频率排好序 C）线性表以顺序方式存储，并且按关键码值排好序

D）线性表以链接方式存储，并且按关键码值的检索频率排好序 （8）对n个记录进行堆排序，所需要的辅助存储空间为（ ）。

A）O(1og2n) B）O(n) C）O(1) D）O(n2)

（9）对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（ ）个。

A）1 B）2 C）3 D）4 （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，试计算出A[1,1,1]的存储位置。

六、（本题8分）

试列出如下图中全部可能的拓扑排序序列。

123456 七、（本题8分）

已知哈希表地址空间为0..8，哈希函数为H(key)=key%7，采用线性探测再散列处理冲突，将数据序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。

八、（本题8分） 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个

数据而生成的二叉搜索树。 九、（本题9分）

试画出表达式(a+b/c)*(d-e*f)的二叉树表示，并写出此表达式的波兰式表示，中缀表示及逆波兰式表示。

十、（本题15分）

以二叉链表作存储结构，试编写计算二叉树中叶子结点数目的递归算法。

模拟试题（二）参考答案

一、单项选择题（每小题 2 分，共20分） （1）B （2）B （3）A （4）D （6）A （7）C （8）C （9）D

（5）A

（10）D

二、（本题8分） 先序： a,b,c,d,e,f 中序： c,b,a,e,d,f 后序： c,b,e,f,d,a 按层： a,b,d,c,e,f 三、（每小题4分，共8分） 【解答】

（1）该图的图形如下图所示：

（2）深度优先遍历序列为：abdce；广度优先遍历序列为：abedc。 四、（本题8分）

树的遍历方法有先根序遍历和后根序遍历，它们分别对应于把树转变为二叉树后的先序遍历与中序遍历方法。

五、（本题8分）

A[1,1,1]的存储位置=2000+((1-(-1))*(6-0+1)*(3-(-2)+1)+(1-0)*(3-(-2)+1)+(1-(-2)))*5=2465。 六、（本题8分）

全部可能的拓扑排序序列为：1523634、152634、156234、561234、516234、512634、512364

七、（本题8分）

哈希表及查找各关键字要比较的次数如下所示：

ASL=1(4×1+1×2+1×4+2×5)=2.5

8八、（本题8分）

九、（本题9分）

表达式的波兰式表示，中缀表示及逆波兰式表示分别是此表达式的二叉树表示的前序

遍历、中序遍历及后序遍历序列。

二叉树表示如下图所示：

波兰式表示：*+a/bc-d*ef 中缀表示：a+b/c*d-e*f 逆波兰式表示：abc/+def*-* 十、（本题15分）

本题只要在遍历二叉树的过程序中对叶子结点进行记数即可。 C++语言版测试程序见exam2\\10c++，具体算当如下：

template

long leaf_count(const Binary_tree &T) // 计算二叉树中叶子结点数目 { return aux_leaf_count(T.get_root()); }

template

long aux_leaf_count(Binary_node *sub_root) // 按树状形式显示二叉树，level为层次数，可设根结点的层次数为1 { if(sub_root==NULL) return 0; //空树返回0 else if(sub_root->left==NULL&&sub_root->right==NULL) return 1; //只有一个结点的树返回1 else //叶子结点数为左右子树的叶子结点数之和 return aux_leaf_count(sub_root->left)+aux_leaf_count(sub_root->right); }

C语言版测试程序见exam2\\10c，具体算当如下：

long LeafCount(BiTree T) // 计算二叉树中叶子结点数目 { if(T==NULL) return 0; //空树返回0 else if(T->lchild==NULL&&T->rchild==NULL) return 1; //只有一个结点的树返回1 else //叶子结点数为左右子树的叶子结点数之和

}

}

e_to->lchild=NULL; //左孩子为空 if(e_from->rchild!=NULL) { //复制e_from右孩子 e_to->rchild=new BiTNode; e_to->rchild->data=e_from->rchild->data; EnQueue(Q_from,e_from->rchild);EnQueue(Q_to,e_to->rchild);//入队 } else e_to->rchild=NULL; //右孩子为空

模拟试题（六）

一、单项选择题（每小题 2 分，共20分）

（1）下列文件的物理结构中，不利于文件长度动态增长的文件物理结构是（ ）。

A）顺序结构 B）链接结构 C）索引结构 D）Hash结构 （2）在数据结构中，数据元素可由（ ）。

A）实体 B）域 C）数据项 D）字段

（3）对于有n个顶点的有向图，由弗洛伊德（Floyd）算法求每一对顶之间的最短路径的时间复杂度是（ ）。

A）O(1) B）O(n) C）O(n) D）O(n3)

（4）对n个记录的文件进行快速排序，所需要的辅助存储空间为（ ）。

A）O（1） B）O（log2n） C）O（n） D）O（n2） （5）哈夫曼树中一定不存在（ ）。

A）度为0的结点 B）度为1的结点 C）度为2的结点 D）带权的结点 （6）设D={A,B,C,D}，R={,,,,}，则数据结构(D,{R})是（ ）。

A）树 B）图 B）线性表 D）前面都正确 （7）（ ）关键码序列不符合堆的定义。

A）A、C、D、G、H、M、P、Q、R、X B）A、C、M、D、H、P、X、G、Q、R C）A、D、P、R、C、Q、X、M、H、G D）A、D、C、M、P、G、H、X、R、Q （8）假定关键字K=442205883，允许存储地址为四位十进制数，并且Hash地址为6111，则所采用的构造Hash函数的方法是（ ）。

A）直接定址法 B）平方取中法 C）除留余数法，模为97 D）折叠法 （9）在算法的时间复杂度中，n表示问题规模，f(n)表示基本操作重复执行的次数，则随问题的规模n的增大，算法执行时间的增长率同（ ）相同。

A）f(n) B）n C）O(n) D）前面都不正确 （10）对线性表进行二分法查找，其前提条件是（ ）。

A）线性表以顺序方式存储，并且按关键码值排好序

B）线性表以顺序方式存储，并且按关键码值的检索频率排好序 C）线性表以链接方式存储，并且按关键码值排好序

D）线性表以链接方式存储，并且按关键码值的检索频率排好序 二、（本题8分）

在如下表所示的数组A中链接存储了一个线性表，表头指针存放在A[0].next，试写出该线性表。

线性表

A Data next 0 4 1 60 0 2 50 5 3 78 2 4 90 7 5 34 1 6 7 40 3 三、（本题8分）

已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ，中序遍历的结果是KBCDAFHIGJ，试画出这棵二叉树。

四、（本题8分）

已知一个图的顶点集V为： V={1,2,3,4,5,6,7}，弧如下表所示。

图的弧集

起点 终点 权 1 6 1 2 4 1 2 5 2 5 4 2 5 7 2 2 6 3 2 7 3 6 7 4 1 7 5 3 5 7 试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。 五、（本题8分）

向最小根堆中依次插入数据4, 2, 5, 8, 3, 6, 10, 1时，画出每插入一个数据后堆的变化。

六、（本题8分）

已知广义表L=(((b,c),d),((a),((b,c),d)),())，试画出它的存储结构。 七、（每小题4分，共8分）

对给定的有7个顶点的有向图的邻接矩阵如下： （l）画出该有向图；

（2）若将图看成是AOE-网，画出关键路径。

??????????????????

2?522?1???????????????????8???35???

5????39????5??????八、（本题8分）

给出一组关键字29、18、25、47、58、12、51、10，分别写出按下列各种排序方法进行排序时的变化过程：

（1）归并排序，每归并一次书写一个次序。

（2）快速排序，每划分一次书写一个次序以及最后排好序后的序列。 （2）快速排序： (10,18,25,12)29(58,51,47)

(10(18,25,12)29((47,51)58) (10((12)18(25))29((47(51))58) (10,12,18,25,29,47,51,58)

（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。 九、（本题9分）

试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。 十、（本题15分）

设计以单链表存储的两个集合求交集的算法。

模拟试题（六）参考答案

一、单项选择题（每小题 2 分，共20分） （1）A （2）C （3）D （4）B （6）B （7）C （8）D （9）A 二、（本题8分）

线性表为：(90,40,78,50,34,60) 三、（本题8分）

（5）B

（10）A

四、（本题8分）

用克鲁斯卡尔算法得到的最小生成树为：

(1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)7 五、（本题8分） 如下图所示：

六、（本题8分）

本题广义表存储结构如下图所示：

七、（每小题4分，共8分）

（1）由邻接矩阵所画的有向图如下图所示：

2212523145358635957 （2）关键路径如下图所示：

22123145597 八、（本题8分）

变化过程如下：

（1）归并排序： (l8,29)(25,47)(12,58)(l0,51)

(l8,25,29,47)(10,12,51,58) (l0,12,18,25,29,47,51,58)

（2）快速排序： (10,18,25,12)29(58,51,47)

(10(18,25,12)29((47,51)58) (10((12)18(25))29((47(51))58) (10,12,18,25,29,47,51,58)

（3）堆排序：

初始堆（大顶推）：(58,47,51,29,18,12,25,10) 第一次调整：(51,47,25,29,18,12,10)(58) 第二次调整：(47,29,25,10,18,12)(51,58) 第三次调整：(29,18,25,10,12)(47,51,58) 第四次调整：(25,18,12,10)(29,47,51,58) 第五次调整：(l8,10,12)(25,29,47,51,58) 第六次调整：(l2,10)(18,25,29,47,51,58) 第七次调整：(l0,12,18,25,29,47,51,58)

九、（本题9分）

具有3个结点的树的不同形态如下图所示。

具有3个结点的二叉树的不同形态如下图所示。

十、（本题15分）

用单链表lc表示集合 C。分别将la中元素取出，再在lb中进行查找，如在lb中出现，则将其插入到lc中。

C++语言版测试程序见exam6\\10c++，具体算当如下：

template

void interaction(List* &la,List* &lb,List* &lc) // 将链表la与lb中共同出现的元素插入到链表lc中 { List_entry la_it,lb_it; lc=new List; //生成lc for(int i=0;isize();i++) { la->retrieve(i,la_it);

}

}

for(int j=0;jsize();j++) { lb->retrieve(j,lb_it); if(la_it==lb_it) break; }

if(jsize()) //定位成功 lc->insert(lc->size(),la_it);

C语言版测试程序见exam6\\10c，具体算当如下：

void interaction(LinkList la,LinkList lb,LinkList &lc)

// 将链表la与lb中共同出现的元素插入到链表lc中 { LinkList pa,pb,pc; lc=new LNode; //生成lc的头结点 pc=lc; //pc永远指向lc的尾结点 pa=la->next; //pa指向la的第一个元素 while(pa) { pb=lb->next; while(pb&&pb->data!=pa->data) pb=pb->next; //在pb中定位pa->data if(pb) //定位成功 { pc->next=new LNode; //生成lc新的尾结点 pc=pc->next; //pc指向新的尾结点 pc->data=pa->data; //将pa->data复制到pc中 } pa=pa->next; } pc->next=NULL; //pc为尾结点，其后继为空 }

*模拟试题（七）

注：本套试题选作

一、单项选择题（每小题 2 分，共20分）

（1）若以1234作为双端队列的输入序列，则既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列是（ ）。

A）1234 B）4132 C）4231 D）4213 （2）将一个A[1..100,1..100]的三对角矩阵，按行优先存入一维数组B[298]中，A中元

素a66,65（即该元素下标）在B数组中的位置k为（ ）（假设B[0]的位置是1）。 A）198 B）195 C）197 D）198

【分析】如下所示，三对角矩阵第1行和最后1行非零元素个数为2个，其余各行的非零元素个数是3个，所知a66,65前面共有2+3*64＝194个非零元素，a66,65本身是第 195个非零元。

?a11?a?21??A???????a12a22a32a23a33?a34?an?2,n?1?an?2,n?2an?1,nan?2,n?1an?1,n?1an,n?1?n??1 ??m??n?1? ??m?1??????? ??an?1,n?ann???n??1 ??m?1? （3）若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）。

A）n-1

B）?C）?D）?（4）若一个有向图具有拓扑排序序列，并且顶点按拓扑排序序列编号，那么它的邻

接矩阵必定为（ ）。

A）对称矩阵 B）稀疏矩阵 C）三角矩阵 D）一般矩阵

（5）设森林 F对应的二叉树为有 m个结点，此二叉树根的左子树的结点个数为k，则另一棵子树的结点个数为（ ）。

A）m-k+1 B）k+1 C）m-k-1 D）m-k （6）假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（ ）次探测。

A）K-1次 B）K次 C）K＋l次 D）K(K+1)/2次 （7）一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（ ）个结点。

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

（8）如表r有100000个元素，前99999个元素递增有序，则采用（ ）方法比较次数较少。

A）直接插入排序 B）快速排序 C）归并排序 D）选择排序 （9）如果只考虑有序树的情形，那么具有7个结点的不同形态的树共有（ ）棵。

A）132 B）154 C）429 D）前面均不正确

（10）对ISAM

文件的删除记录时，一般(

B）需移动记录

)

A）只需做删除标

C）需改变指针 D）一旦删除就要做整理

二、（本题8分）

斐波那契数列Fn定义如下：

F0=0，F1=1，Fn=Fn-1+Fn-2

请就此斐波那契数列，回答下列问题：

（1）在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，?，F1，F0精确计算多少次？ （2）若用有关大O表示法，试给出递归计算Fn时递归函数的时间复杂度是多少？ 三、（本题8分） 证明：如果一棵二叉树的后序序列是u1,u2,?,un，中序序列是up,up,?,up，则由

12n序列1,2,?,n可通过一个栈得到序列p1,p2,?,pn。

四、（本题8分）

如下图所示为5个乡镇之间的交通图，乡镇之间道路的长度如图中边上所注。现在要在这5个乡镇中选择一个乡镇建立一个消防站，问这个消防站应建在哪个乡镇，才能使离消防站最远的乡镇到消防站的路程最短。试回答解决上述问题应采用什么算法，并写出应用该算法解答上述问题的每一步计算结果。

图 乡镇交通图

五、（本题8分）

证明一个深度为n的AVL树中的最少结点数为：Nn=Fn+2-1 (n≥0) 其中，Fi为Fibonacci数列的第i项。 六、（本题8分）

简单回答有关AVL树的问题：（北方名校经典试题）

（1）在有 n个结点的AVL树中，为结点增加一个存放结点高度的数据成员，那么每一个结点需要增加多少个字位（bit）？

（2）若每一个结点中的高度计数器有8bit，那么这样的AVL树可以有多少层？最少有多少个关键码？

七、（本题8分）

设有12个数据 {25，40，33，47，12，66，72，87，94，22，5，58}，它们存储在散列表中，利用线性探测再散列解决冲突，要求插入新数据的平均查找次数不超过3次。

（1）该散列表的大小m应设计多大？ （2）试为该散列表设计相应的散列函数。

（3）顺次将各个数据散列到表中。 （4）计算查找成功的平均查找次数。 八、（本题8分）

已知某电文中共出现了10种不同的字母，每个字母出现的频率分别为A：8，B：5，C：3，D：2，E：7，F：23，G：9，H：11，I：2，J：35，现在对这段电文用三进制进行编码（即码字由0，l，2组成），问电文编码总长度至少有多少位？请画出相应的图。

九、（本题9分）

N2个度为2的结点，Nm个度为m已知一棵度为m的树中有N1个度为1的结点，?，

的结点。试问该树中有多少个叶子结点？（北方名校经典试题）

十、（本题15分）

试用递归法编写输出从n个数中挑选 k个进行排列所得序列的算法。

模拟试题（七）参考答案

一、单项选择题（每小题 2 分，共20分） （1）参考答案：C）

（2）【分析】如下所示，三对角矩阵第1行和最后1行非零元素个数为2个，其余各行的非零元素个数是3个，所知a66,65前面共有2+3*64＝194个非零元素，a66,65本身是第 195个非零元。

?a11?a?21??A???????a12a22a32a23a33?a34?an?2,n?1?an?2,n?2an?1,nan?2,n?1an?1,n?1an,n?1?????? ??an?1,n?ann??参考答案：B）

（3）【分析】在哈夫曼树的非叶结点中最多只有1个结点的度不为m，设非叶结点的个数为k，则其中有k-1个结点的度为m，设另1个结点的度为u，则2≤u≤m，设结点总数为n总，则有如下关系：

n总-1=m(k-1)+u ① n总=k+n ②

将②代入①可得：k+n-1= m(k-1)+u，解得：k?(n?1)?(m?u)，由于2≤u≤m，

m?1

所以可得0≤m-u＜m-1，所以可得：

n?1n?1?n?1?+1，可知k??≤k＜。 ?m?1m?1m?1??参考答案：C）

（4）【分析】设顶点按拓扑排序序列为：v0,v1,…,vn-1，则对于邻接矩阵A，只有当i，也就是当i>j时，一定没有弧< vi,vj>，所以这时A[i][j]=0，可知邻接矩阵为三角矩阵。

参考答案：C）

（5）【分析】设另一棵子树的结点个数为n，所以有 m=n+k+1，可知n= m-k-l。 参考答案：C）

（6）【分析】因为K个关键字互为同义词，只有在存入第一个关键字的情况下不发生冲突，所以至少需进行1+2+?+K=K(K+1)/2次探测。

参考答案：D）

（7）【分析】由于每个非终端结点的平衡因子均为0，所以每个非终端结点必有左右两个孩子，且左子树的高度和右子树的高度相同，这样AVL树是满二叉树。高度为k的

k

满二叉树的结点数为2-l。

参考答案：D） （8）【分析】本题中只有直接插入排序利用前面有序的子序列这个性质，如用直接插入排序对本题只需将最后一个元素插入到前面99999个元素的有序子序列中即可，显然比较次数较少。

参考答案：A）

（9）【分析】具有n个结点有不同形态的树的数目和具有n-l个结点互不相似的二叉树的数目相同（将树转化为二叉树时，根结点右子树为空，所以除根结点而外只有左子树，其不相似的二叉树的等价于不相似的左子树）。具有n个结点互不相似的二又树的数目为

11n6C2C12?132。 n，本题中应为n?16?1参考答案：A）

（9）参考答案：A）

二、（本题8分）

【解答】

（1）设在计算Fn时，由Fn-1+Fn-2可知Fn-1要精确计算1次； 由Fn-1=Fn-2+Fn-3可知Fn=2Fn-2+Fn-3，Fn-2要精确计算2次；

由Fn-2=Fn-3+Fn-4可知Fn=3Fn-3+2Fn-4，Fn-3要精确计算3次，Fn=3Fn-3+2Fn-4公式中Fn-3

的系数为Fn-3要精确计算次数，而Fn-4的系数为Fn-2要精确计算次数，以此类推，设Fn-j的精确计算次为aj，则有：Fn=aj*Fn-j+aj-1*Fn-j-1。

Fn-j-1的精确计算次数为aj+1， 由Fn-j=Fn-j-1+Fn-j-2可知Fn=(aj+ aj-1)*Fn-j-1+aj*Fn-j-2 ，所以有：

aj+1=aj+aj-1

由于Fn-1要精确计算a1为1次，即a1=1，即可知Fn-1，Fn-2，?，F1，F0的精确计算次为：1，2，3，5，??，aj=aj-1+aj-2??

与斐波那契数列数列：

0，1，2，3，5，??，Fn=Fn-1+Fn-2?? 比较可知aj=Fj+1。

（2）由于Fn的计算最终要转化为F0与F1之和，其加法的计算次数为F0与F1的精确计算次数之和再减1之差，由于F0=Fn-n与F1=Fn-(n-1)，所以计算Fn时，加法计算次数为：

an+an-1-1=Fn+1+Fn-1

由于Fn=

11?5n11?5n1?5n()?()，可知时间复杂度为O(())。 22255三、（本题8分）

【解答】当n=1时，结论显然成立。

设n<=k时结论成立，当n=k+1时，设一棵二叉树的后序序列是u1,u2,?,un，中序序列是up,up,?,up，可知un是二叉树的根结点，设pj?n，可知{up,up,?,up}是左

j?1112n2子树的结点集合，{upj?1,upj?2,?, up}是右子树的结点集合，进一步可知：

n2j?1（1）左子树的后序序列是u1,u2,?,uj?1，中序序列是up1,up,?,up知序列1,2,?,j-1可以通过一个栈得序列p1,p2,?,pj?1。

，由归纳假设

（2）右子树的后序序列是uj,uj?1,?, un?1，中序序列是upj?1,upj?2,?, up，设

n??uj，u2??uj?1，?，un??j?un?1；u?p1??upj?1，u?p?2?upj?2，?，u?p?n?j?upn，则u1??pj?1?j?1，p2??pj?2?j?1，?，pn??j?pn?j?1，由归纳假设知序列1,2,?,n-jp1可以通过一个栈得序列p1??j，显然按同样的方式，j,j+1,?,n-1 可以通过一?，p2?，?，pn个栈得序列j?1?p1??j，也就是pj?1，pj?2，?，pn。 ?,j?1?p2?,?,j?1?pn由（1）（2）及pj?n可知由1,2,?,n可通过一个栈得到序列p1,p2,?,pn。由数学归纳法可知本题结论成立。 四、（本题8分）

【解答】由弗洛伊德（Floyd）算法进行求解，具体步骤如下：

D(?1)?0129?3??0129?3??1206????1206?15?????(0)??9604??，D??960412?； ??????406??406???????3??60???3151260??D(1)?0129?3??0129133??1206?15??12061015?????(2)??960412?，D??960412?； ??????4061310406???????3151260???3151260???0129133??012993??12061015??12061015?????(4)??960412?，D??960410?。 ????1310406910406???????3151060???3151060??D(3)设乡镇vi到其他各乡镇的最远距离为max_disdance(vi)，则有：max_disdance(v1)=12，

max_disdance(v2)=15，max_disdance(v3)=10，max_disdance(v4)=10，max_disdance(v5)=15，所以可知消防站应建在v3或v4乡镇，才能使离消防站最远的乡镇到消防站的路程最短。

五、（本题8分）

【解答】对n用归纳法证明。当n＝1时，有N1=F3-l=2-l=1到。当n=2时，有N2=F4-1=3-1=2。设n

当n=k+1，对于一个k+l层深度的平衡二叉树而言，其左右子树都是平衡的。结点数为最少的极端情况，故左右子树中的结点数是不相等的，设其中一个是k层深度的二叉平衡树，另一个是k-l层深度的二叉平衡树。所以有：

Nk+1=1+Nk+Nk-1==1+(Fk+2-1)+(Fk+1-1)= Fk+2+Fk+1-1= Fk+3 -1 当n=k+1时成立，由此可知深度为n都等式都成立。 六、（本题8分）

【解答】n个结点的平衡二叉树的最大高度为h?log(5(n?1))?2，设表示高度

1?52xx-1

需xbit，则有关系式：2≥h＞2，所以有：

??x??log2h???log2(log1?5(5(n?1))?2)?

2??1?5h?2)（2）设深度为h的平衡二叉树的最少关键字数为nh，则有公式：n?2?1，h5(8

本题中8bit的计数器共可以表示2=256层，即高度为256，从而可知最少有

1?5258()2n??1个关键字。 5七、（本题8分） 【解答】

（1）线性探测再散列的哈希表查找成功的平均查找长度为：Snl?解得α≤4／5，也就是12/m≤4／5， 所以m≥15，可取m=15。

（2）散列函数可取为H(key)=key % 13 （3）散列表如表7-4所示。

表10-1 散列表

0 1 40 2 66 3 94 4 5 5 6 58 7 33 8 47 9 72 10 87 11 22 11(1?)≤3，21??12 25 13 12 14 （4）12个数据 {25，40，33，47，12，66，72，87，94，22，5，58｝的比较次数分别是：1，1，1，1，2，2，3，2，1，3，1，1。

可知查找成功的平均查找次数=(1+1+1+1+2+2+3+2+1+3+1+1)/12=1.25 八、（本题8分）

【解答】有n个叶子结点的带权路径长度最短的二叉树称哈夫曼树，同理，存在有n个叶子结点的带权路径长度最短的三叉、四叉、……、k叉树，也称为哈夫曼树。如叶子结点数目不足以构成正则的k叉树（树中只有度为k或0的结点），即不满足(n-l)MOD(k-l)=0，k-(n-1)MOD(k-1)-1。需要添加权为0的结点，添加权为0的结点的个数为：添加的位置应该是距离根结点的最远处。

所构造出的哈夫曼树如下图所示：

其中，每个字母的编码长度等于叶子结点的路径长度，电文的总长度为

?wl=191。

iii?1n注释：对于正则的k叉树，设叶结点数为n，度为k的结点数为nk，结点总数为m,则有m-1=knk，m=nk+n，两式相减可得n-1=(k-1)nk，即(n-l)MOD(k-l)=0；如n与k不满足此关系，n加上k-(n-1)MOD(k-1)-1后，n’= n+(k-(n-1)MOD(k-1)-1)，这时： (n’-l)MOD(k-l)=(n+(k-(n-1)MOD(k-1)-1)-l)MOD(k-l) =((n-1)+(k-1)-(n-1)MOD(k-1))MOD(k-l) =((n-1)-(n-1)MOD(k-1))MOD(k-l) =0。 现有12个初始归并段，其记录数分别为｛30,44,8,6,3,20,60,18,9,62,68,85｝，采用3-路平衡归并，画出最佳归并树。

九、（本题9分）

【解答】设该树中结点总数为N，叶子结点个数为N0，则有：

N??Ni，

i?0m ①

N?1??iNi

i?1m

m ②

由②-①再经过移项可得：N0?1??(i?1)N

ii?1十、（本题15分） 【解答】

对于排列的解空间可构造一个虚拟的解空间树，比如n=5，k=3时的解空间树如下图所示，可采用对此树进行先序遍历方式进行遍历，并用递归法进行递归输出从n个数中挑选 k个进行排列所得序列。

图 排列的解空间示意图

C++语言版测试程序见exam7\\10c++，具体算当如下：

template

void arrage(entry list[],int k,int n,int outlen=0)

/* 回溯法输出排列序列，list[1..k-1]为k个数的排列序列outlen为当前所求排列 序列的长度，其中outlen=k时的排列序列为所求；n为list数组长度 */ { if(k<0||k>n)return; //此时无排列 int i; if(outlen==k) { //输出一个排列 for(i=1;i<=k;i++)cout<

C语言版测试程序见exam7\\10c，具体算当如下：

typedef int entry;

void arrage(entry list[],int k,int n,int outlen=0)

/* 回溯法输出排列序列，list[1..k-1]为k个数的排列序列outlen为当前所求排列 序列的长度，其中outlen=k时的排列序列为所求；n为list数组长度 */ { if(k<0||k>n)return; //此时无排列 int i; if(outlen==k) { //输出一个排列 for(i=1;i<=k;i++)cout<

本文来源：https://www.bwwdw.com/article/az0x.html