数据结构+算法分析与设计［22-24年真题版］

2022年考试试题

一、名词解释：(1)数据；(2)数据结构；(每小题5分，共10分)

二、简答题：(1)什么是算法?(2)算法的五个特性是什么?(第(1)小题5分，第(2)小题10分，共15分)

三、分析题：请分析以下所给程序段，并写出时间复杂度的具体计算过程。(10分)

for(t=1,k=1;k<=n;k++)

{t=t×2;

for(j=1;j<=t;j++)

s=s+j;}

五、算法编程：请编写满足下列要求的函数：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数，例如(40)10=(50)8(10分)

五、已知一棵二叉树的先序序列的结果是-+a*b-cd/ef,中序序列的结果是a+b*c-d-e/f,试画出这棵二叉树。(10分)

六、使用普里姆(Prim)算法构造出如下图所示的图1的一棵最小生成树。(10分)

七、请用Dijkstra算法计算图2从源顶点1到其它顶点间最短路径并写出详细过程。(15分)

八、已知图3所示的有向图。请给出该图的(1)每个顶点的入和出度；(2)邻接矩阵；(3)邻接表；(4)逆邻接表；(5)强连通分量。(每小题3分，共15分)

九、依次输入表(35,20,33,25,29,15,17,73,40,55,51,60)中的元素，生成一棵二叉树排序树。(每小题5分，共15分)

(1)试画出生成之后的二叉排序树；

(2)对该二叉排序树作中序遍历，试写出遍历序列；

(3)假定每个元素的查找概论相等，试计算该二叉排序树的平均查找长度。

十一、假设在某次通信联络过程中只能出现八种符号，设八种符号的权集W={5,29,7,8,14,23,3,11},试构造出关于W的一棵赫(哈)夫曼树，并求出其加权路径长度WPL。(15分)

十一、假设关键码为{503,087,512,061,908,170,897,275,653,426}分别执行以下排序算法(1)、(2)、(3),写出每一趟排序结束时的关键码状态。(每小题5分，共15分)

(1)快速排序；(2)归并排序；(3)堆排序；

十二、算法编写：请编写求解n阶Hanoi塔问题的函数。 (10分)

2023年考试试题

一、名词解释：(1)串；(2)栈； (每小题5分，共10分)

二、简答题： (每小题6分，共18分)

(1)请描述什么是0-1背包问题?

(2)图的遍历方式通常有哪些?

(3)根据数据元素之间关系的不同特性，可分为哪几类基本结构?

三、分析题：请分析以下程序段的时间复杂度。(10分)

for (p=1,q=1;q<=n;q++)

{p=p×2;

for(i=1;i<=p;i++)

x=x+i;}

四、算法编程：给定一维数组A 中有已排好序的 n 个元素，请用二分搜索技术编写算法在这 n个元素中查找一个特定的元素x 。(说明：未采用二分搜索技术不得分)(10分)

五、计算题：现要计算矩阵连乘积X₁X₂X₃X₄, 其中各矩阵的维数分别是X₁:30×35,X₂:35×15,X₃: 15×5,X4:5×10,请用动态规划法求解该矩阵连乘问题，确定最优计算次序，使得计算该 矩阵连乘积需要的数乘次数最少。(说明：未采用动态规划法不得分) (15分)

六、分析题：分别使用普里姆(Prim)和克鲁斯卡尔(K ruskal)算法构造出如下图1所示的一 棵最小生成树。 (说明：未采用普里姆和克鲁斯卡尔算法不得分)(每种算法7.5分，共 15分)

七、计算题：已知长度为12的表：(Jan,Feb,Mar;Apr;May,June,July,Aug,Sep,Oct,Nov,Dec)

(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树(按字母先后顺序排序),画出 插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度；

(2)若对表中元素先进行排序构成有序表(按字母先后顺序排序),求在等概率的情况下对 此有序表进行折半查找时查找成功的平均查找长度。

(3)按照表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的 平均查找长度。 (每小题5分，共计15分)

八、问答题：按照渐进阶由低到高的顺序排列以下表达式。 (10分)

nlog2n ,4n ,2n³ ,nn ,log2n ,n! ,3 ,3√n ,8n ,√n

九 、计算题：请采用求解大整数乘法，计算下列两个十进制数x,y的乘积：x=7479, y=9986, (说明：未采用分治法不得分)(15分)

十、算法编程：某企业设计员工业绩管理系统，请编写算法实现以下功能：(1)输入企业100 名员工的信息包括：员工号、姓名及业绩；(2)按照员工业绩由高到低进行排序，员工号 及姓名也随之变化。(第1小题5分，第2小题7分，共12分)

十一、算法编程：请编写算法求解 n皇后问题，要求采用非穷举类算法求解。 (20分)

2024年考试试题

一、名词解释：（每小题5分，共10分)

请分别解释数据结构当中的（1)数据；(2)图。

二、简答题：（每小题6分，共18分）

（1）请比较线性表、栈及队列的异同.

（2）请列举至少三种常用的构造哈希函数方法。

（3）请说明动态规划算法的三个基本要素。

三、分析题：请分析以下程序段的时间复杂度。（10分）

for (p=l;p<=n;p++)

 for(q=1;q<=p;q++)

   x=p+q;

   s=s+x;

四、问答题：请给出下列各函数的渐近表达式（每小题3分，共12分)

(1)2n+10n²; (2)(n2/100)+3n；(3)33+(1/n)； (4)20log27n;

五、计算题：假设有2种不同面值的邮票，分别为1和3，并且规定每张信封上最多只允许贴5张邮票,请计算在此情况下可以贴出的最本连续邮资区间是多少？（请给出具体计算过程）（8分)

六、分析题：已知一个图的顶点集V和边集E分别为：V={A,B,C,D,E,F};

E={(A,B)10,(A,C)12,(A,E)15,(B,C)7,(B,F)6,(B,D)5,(C,E)12,(C,F)8,(D,F)6,(E,F)10}；其中(A,B)10表示顶点A到顶点B存在一条边，权值是10。请完成以下工作：（第（1)题3分，第（2）)题4分，第(3）题5分，共12分)）

（1)画出该图；

(2)写出该图的邻接表结构.

（3)用普利姆(Prim)或克鲁斯卡尔(Kruskan算法求出该图的最小生成树。(说明：未采用普利姆或克鲁斯卡尔算法不得分)

七、计算题：已知如下所示长度为12的表(One,Two,Three,Four,Five,Six.Seven,Eight,Nine,Ten,Eleven,Twelve）（每小题5分，共计10分）

（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树（按字母先后顺序排序)，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度;

（2）若对表中元素先进行排序构成有序表（按字母先后顺序排序），求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

八、问答题：(第(1)题 3分，第(2)题 10分，共13分)

（1）请问己知一棵二叉树的先序遍历序列和后序遍历序列是否能唯一确定一颗二叉树？

(2)已知一颗二叉树的中序遍历序列为DBCAFGE，后序遍历序列为DCBGFEA，请画出该二叉树，并写出先序遍历序列。

九、问答题：假设某电文中含有六种字符：{A,B,C,D,E,F}，它们的出现频率依次为{0.24,0.07,0.15,0.03,0.5,0.01}（每小题6分，共12分)

（1）请画出一棵哈夫曼树，并计算其编码平均长度；

(2）按照（1）的哈夫曼树，规定向左的分支标记为1，向右的分支标记为0，请写出电文中六种符号A,B,C,D,E,F的哈夫曼编码。

十、计算题：现要计算矩阵连乘积A1A2A3A4，其中各矩阵的维数分别是A1：30×35,A2:35×15,A3:15×5,A4:5×10,请用动态规划法求解该矩阵连乘问题，确定最优计算次序，使得计算该矩阵连乘积需要的数乘次数最少。（说明：未采用动态规划法不得分）（15分）

十一、编程题：假设迷宫大小为n×m, 如图1所示的方块图表示迷宫，图中每个空白方块表示通道，带 斜线的方块表示墙，请结合栈的思想编写算法找到从入口到出口的所有路径，所求得的路径上不能重 复出现同一通道块(即通道块只能出现一次)。(说明：未结合栈的思想不得分)(10分)

十一、编程题：请编写算法解决如下问题，要求结合递归思想，（每小题5分，共10分)

(1）求二叉树中叶子结点的数目；

（2）求二叉树中以元素值为x的结点为根的子树的深度。

（说明：未结合递归思想不得分)

十二、问答题：假设有初始序列{11,2,36,62,90,37,56}使用冒泡排序算法升序排序，请分别给出前5趟的排序结果。（说明：未采用冒泡算法不得分)(10分)