南京审计大学考研专业课试题2019年814数据结构.pdf

1、 科目代码：814 科目名称：数据结构 第 1 页 共 2 页 南京审计大学南京审计大学 2012019 9 年硕士研究生入学考试年硕士研究生入学考试初试初试（笔试）（笔试）试题试题（ A A 卷卷 ） 科目代码: 814 满分: 150 分 科目名称: 数据结构 注意: 认真阅读答题纸上的注意事项；认真阅读答题纸上的注意事项；所有答案必须写在所有答案必须写在答题纸答题纸上，写在本试题纸或草稿纸上均无上，写在本试题纸或草稿纸上均无效；效；本试题纸须随答题纸一起装入试题袋中交回！本试题纸须随答题纸一起装入试题袋中交回！ 一、名词解释（共一、名词解释（共 6 6 小题，每题小题，每题 5 5 分，

2、总分分，总分 3030 分）分） 1、数据结构 2、数据类型 3、时间复杂度 4、栈 5、赫夫曼树 6、图 二、二、简答题（共简答题（共 4 4 小题，每题小题，每题 1010 分，总分分，总分 4040 分）分） 1、请简要回答算法的定义和特征。 2、线性结构的特点有哪些？ 3、请描述头指针、头结点、首元结点（第一个元素节点）的区别。 4、简述树的存储结构类型。 三、综合应用题（共三、综合应用题（共 8 8 小题，每题小题，每题 1010 分，总分分，总分 8080 分）分） 1、已知三个元素 A、B、C 依次进入栈中， (1)如果要求所有元素都进栈后才开始出栈，请写出元素的出栈序列； (2

3、)如果元素进栈过程中也可以有元素出栈，请写出所有可能的出栈序列。 2、已知二叉树的先序遍历序列是 ABDGEHCFI，中序遍历序列是 DGBEHACIF， (1)请画出此二叉树； (2)请写出该二叉树的后序遍历序列。 3、给定树结构如右图所示， (1)请写出树的先根遍历序列； (2)将树转换为二叉树，请画出转换以后的二叉树。 4、已知一个无向图的顶点集 V 和边集 E，其中 V=A，B，C，D，E，E=， (1)请画出该图； (2)采用邻接表存储该无向图，假定邻接表中顶点按字母顺序存储，每个顶点的相邻顶点按顶点序号从大到小的次序链接，请画出该图的邻接表； (3)基于上述邻接表存储结构，请写出该

4、图从 A 出发的深度优先遍历序列和广度优先遍历序列。 5、请证明二叉树的以下性质： 对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0=n2+1。 科目代码：814 科目名称：数据结构 第 2 页 共 2 页 6、采用哈希表存储元素 7、4、5、3、6、2、8、9，设哈希函数为 H（key）=（key2+2）MOD 9,采用链地址法处理冲突， (1)请画出依次存储上述元素后该哈希表的存储结构，要求每个链表中元素从小至大排列； (2)假定每个元素的查找概率相等，请计算平均成功查找长度。 7、设关键字序列为(4，28，15，37，76，23，57，19，45，6)，请写出希尔排序的过程。要求按从小到大的次序排列，设增量序列为 5、3、1。 8、从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加 1，请据此补充完整以下求解二叉树深度的函数 TreeDepth： int TreeDepth (BiTree T ) (1)已知二叉树采用二叉链表存储，二叉链表的存储结构为 typedef struct BiTNode int data; struct BiTNode *lchild, *rchild; BiTNode ,*BiTree; (2)使用教材中的类 C 代码描述即可。 (3)要求 TreeDepth 为递归函数。