2015年攻读硕士学位研究生入学考试试题（考生回忆版）
2014-12-28 下午 14:00-17:00
考试科目：数据结构(872) 一、名词解释20’
1.数据结构 2.栈 3.完全二叉树 4.连通图 5.结构化算法 二、简答题80’
（题序有点乱，好像少点题）
1.比较顺序存储、链式存储的优缺点，以及它们的应用 2.数据结构与数据类型的区别，线性结构和非线性结构的区别 3.一棵度为2的树与一棵二叉树的区别，画出二叉树的5种基本形态 4.关键字序列（d,c,a,k,z,b,c,m,t,w）升序排序，分别用以下方法写出第一趟排序结果：冒泡排序、快速排序、选择排序、直接插入排序、堆排序初始状态序列
5.顶点集合V={1,2,3,4,5,6,7} 边的集合E={(1,3)5，(1,5)3，(1,4)7，(2,3)6，(2,4)9，(2,5)8，(3,4)10，……} 采用克鲁斯卡尔（Kruskal）算法构造最小生成树，依次写出每次添加的边
6.给出一有向图，写出从顶点V1出发深度优先搜索遍历DFS序列，广度优先搜索遍历BFS序列
7.给出一有向图，画出邻接矩阵和邻接表
8.给出一AOV网，写出拓扑排序过程判断是否有环
1 / 2
三、应用题20’
1.先序遍历序列为：_________，中序遍历序列为：__________，画出此二叉树，画出后序线索化二叉树
2.字符a,b,c,d,e,f,g 频度为25%，5%，4%，9%，%，……，设计哈夫曼编码，写出计算过程
四、算法设计30’
1.写出单链表的定义，在一递增有序的单链表中，写出删除大于min且小于max的所有元素的算法
2.写出二叉排序树的定义，二叉排序树采用二叉链表方式存放，写出在二叉排序树中查找X的算法
2 / 2
因篇幅问题不能全部显示，请点此查看更多更全内容