南京财经大学.doc

南京财经大学南京财经大学 2007 年攻读硕士学位研究生入学考试(初试)试卷考试科目: 419 数据结构与计算机组成原理适用专业: 计算机应用技术考试时间: 2007 年1月 21 日下午 14:00?~7:00 注意事项: 所有答案必须写在答题纸上, 做在试卷或草稿纸上无效。第一部分:数据结构试题(本部分共六大题,共计 75 分) 一、简答题(共 6 题,每题 5 分,共计 30 分) 1 .线性表有哪两种存储结构?如果有 n 个线性表同时并存,而且在处理过程中各表的长度会动态地发生变化, 线性表的总数也会自动改变,在此情况下,应选用哪一种存储结构?为什么? 2 .已知一棵二叉树的先序遍历为: ABDCEF ;中序遍历为: DBAECF 。要求:( 1 )画出这棵二叉树; (2 )写出这棵二叉树的后序遍历序列。 3 .已知图的邻接矩阵为: V1 V2 V3 V4 V5 V6 V1011100 V2001110 V3000001 V4000000 V5001001 V6000100 要求:( 1 )画出此图的邻接表; (2 )写出对该图进行拓扑排序时所有的拓扑有序序列。 4 .依次输入一个关键字序列{ 50, 17, 66, 56, 70, 12, 60, 52}, 要求:( 1 )画出按输入次序构造的二叉排序树; (2 )画出该树在删除关键字"66" 后的二叉排序树。 5 .指出所有满足下列条件的二叉树: (1 )它们在先序遍历和中序遍历时,得到的遍历序列相同; (2 )它们在后序遍历和中序遍历时,得到的遍历序列相同; (3 )它们在先序遍历和后序遍历时,得到的遍历序列相同。 6 .设有哈希函数为 H(key)=key MOD 11 ,哈希表 HT 的长度为 11,解决冲突的方法为线性探测再散列法,关键字的输入序列为: { 34,58,26,75,67,48,93,81 }。要求: (1) 试构造此哈希表; (2) 求出在等概率情况下查找成功时的平均查找长度。二、稀疏矩阵常用的存储压缩方式有哪几种?设 m×n 稀疏矩阵 A有 k 个非零元素, 其三元组表示为 LIMA[1..(k+1), 1..3] , 试问: 非零元素的个数 k 达到什么程度时采用三元组表示稀疏矩阵才有意义? (共 1 题,共计 7 分) 三、已知一个无向图的邻接表如下图所示, 试写出从顶点 0 出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。(共1题,共计 6 分) 四、已知下图所示的一个网, 按照 Kruskal 方法, 求该网的最小生成树的产生过程。(共 1 题,共计 7 分) 五、阅读以下算法。算法执行时, 依次输入数据 ABC##DE#G## F##H## , 试指出该算法的功能,并画出执行此算法后所建立的数据结构示意图。(共 1 题,共计 5 分) typedef struct Node { char data; struct Node *lc,*rc ; }BiTNode, *BiTree; void ex (BiTree &T) { char ch; scanf("%c", &ch); if (ch= ='#') T=NULL; else { T=(BiTNode *) malloc(sizeof (BiTNode)); if(!T){printf("ERR