扬州大学2022年858程序设计与数据结构试题

扬 州 大 学 2022年硕士研究生招生考试初试试题（A卷） 科目代码：858 科目名称：程序设计与数据结构 满分：150分

注意：①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回。

一、应用题（共6小题，每小题10分，共60分。）

1. 试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
2. 请将香蕉banana用工具H()和T()从表L中取出。L=(apple,(orange, (strawberry,(banana)),peach),pear)。（备注： H()和T()分别为取表头 Hea d()和取表尾Tai1()操作）
3. 试找出满足下列条件的二叉树。
   ​ (1) 先序序列与后序序列相同；
   ​ (2) 序序列与后序序列相同；
   ​ (3) 先序序列与中序序列相同；
   ​ (4) 中序序列与层次遍历序列相同。
4. 假设用于通信的电文仅由8个字母组成， 字母在电文中出现的频率分别为0. 07、0. 19、0. 02、0. 06、0. 32、0. 03、0. 21和0. 10。
   ​ (1) 试为这8个字母设计哈夫曼编码；
   ​ (2) 试设计另一种由二进制表示的等长编码方案；
   ​ (3) 对于上述实例，比较两种方案的优缺点。
5. 已知图所示的无向网，请给出：
   
   ​ (1) 邻接矩阵；
   ​ (2) 邻接表；
   ​ (3) 最小生成树。
6. 请证明：任意一颗具有N个节点的满二叉树 ( N>0) 的叶节点数目为(N+1)/2。

二、算法题（共6小题，每小题15分，共90分。）

1. 已知两个链表A和B分别表示两个集合，其元素递增排列。请设计一个算法，用于求出A与B的交集，并存放在A链表中。
2. 设计一个算法，将链表中所有结点的链接方向“原地”逆转，即要求仅利用原表的存储空间，换句话说，要求算法的空间复杂度为0(1)。
3. 设二维数组a[l…m,1…n]含有m*n个整数。
   ​ (1) 写一个算法判断a中所有元素是否互不相同，并输出相关信息(yes/no);
   ​ (2) 试分析算法的时间复杂度。
4. 用按层次顺序遍历二叉树的方法，设计算法统计树中度为1的结点数目。
5. 编写算法，对n个关键字取整数值的记录序列进行整理。以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：
   ​ (1) 采用顺序存储结构，至多使用一个记录的辅助存储空间；
   ​ (2) 算法的时间复杂度为O(n)。
6. 编写函数，判断一个有向图是否存在回路。要求先给出算法思想，再写出相应算法（或代码）。

三、补充说明

作者：@江上_酒
扬州大学2022年858程序设计与数据结构试题参考答案
扬州大学信息工程学院2022届考研情况分析
扬州大学858程序设计与数据结构专业课（资料篇）
扬州大学858程序设计与数据结构专业课（编程题篇）