2014年南京航空航天大学922数据结构与操作系统（专业学位）考研真题

2014年南京航空航天大学922数据结构与操作系统（专业学位）考研真题

真题原文：

南京航空航天大学
2014 年硕士研究生入学考试初试试题（ A 卷 ）
科目代码: 922
科目名称: 数据结构与操作系统 满分: 150 分
注意: ①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无
效；③本试题纸须随答题纸一起装入试题袋中交回！
数据结构部分（75 分）
1. （5 分）给出广义表 G=( （e, a ) , ( (b，（）, d) , c), f )的以表头表尾形式的链式存
储结构示意图。
2.（10 分）解释哈希表工作原理。将关键字序列（75，54，48，90，18，22，84，63）存
储在长度为 10 的哈希表中，使用哈希函数 H(key) = Key % 10 ，并采用二次探测再散列法
解决冲突，画出哈希表示意图。
3.（10 分）试用 Floyd 算法，求解下图中各顶点之间的最短路径，写出算法过程中每一步
的状态。 
4. （10 分）已知数据序列为 (555, 88, 499, 58, 808, 170, 797, 275, 653, 460)，给
出堆排序过程的示意图。
5.（10 分）设有 6 个字符，其权值为（12，40，16，8，14，10），给出进行 Huffman 编码
的数据结构和执行过程示意图。
6．（10 分）设一个带头结点的单链表 L，数据元素为（a1,a2,a3,a4,... ,an）,编写函数，
调整该链表，使得数据元素次序为（a1, a3,...,an, ... ,a4,a2）, 要求 T(n)=O(n)，先
给出算法思想，再写出相应代码。
7.（10 分）设有一家谱树 T，用二叉链表结构存储（孩子兄弟表示法），树中的结点信息为
成员名字。编写函数，输出家谱中共有多少代以及最后一代人数和成员名字。要求先给出
算法思想，再写出相应代码。
8.（10 分）编写函数，给有向无环图 G 的每一个顶点赋以一个整数编号，要求：若顶点 v
到顶点 w 之间有一条弧，则顶点 v 的编号小于顶点 w 的编号。先给出算法思想，再写出相
应代码。 

资料截图：



下载地址：
 

2014年南京航空航天大学922数据结构与操作系统（专业学位）考研真题