南昌大学硕士研究生入学考试
2017年数据结构试题
试卷类型 b 卷 考试类型 闭 卷
考生姓名
考 号
座位编号
（试题共有三部分第一部分60分，第二部分60分，第三部分30分，总分150分）
第一部分（6*10,总分60分）
1、数据结构包括哪两种结构？
2、请叙述顺序表结构和链表结构的特点？ 3、什么是二叉树、满二叉树、完全二叉树？ 4、请叙述栈和队列？
5、顺序排序与折半排序有什么特点，它们的时间复杂度是多少？ 6、什么是字符串？
7、对比使用尾指针与使用头指针那个更好，为什么。 8、线性结构与非线性结构的特点。
9、递归算法和非递归算法谁快，为什么。 10、图中有关路径的定义是。
第二部分（15*4，总分60分）
1、使用快速排序方法将下列序列进行排序，并写出执行流程 原始序列：49 38 65 97 76 13 27 49
2、我们通过一些特定的样例对人们在使用英语交流中某些英文字母出现的频率进行了一组调查，调查概率如下a（0.03）；s（0.2）；c（0.33）；e（0.03）；x（0.04）；m（0.05），p(0.32)。
1) 请根据对应字符的概率画出对应的哈弗曼树。
2) 根据哈弗曼编码写出对应的英文短语 （00111110101110110111111100）(左孩子为1，
右孩子为0)
3、根据下列无向图使用克鲁斯卡尔或普里姆算法构造最小生成树，并画出每一步构造过程
4、请补全以下中序遍历线索二叉树。
第三部分（15*2，总分30分）
1、请用代码块方式写出起泡排序算法，语言不限。
2、一个高度为L的满K叉树有以下性质：第L层上的节点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果从上倒下、自左至右，对K叉树中全部结点进行编号（根部结点编号为1），编写程序实现以下效果。
1) 输出各层结点数目
2) 编号为n的结点的双亲（若存在）的编号是多少