南京财经大学

南 京 财 经 大 学 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 　　　　　V1 0 1 1 1 0 0 　　　　　V2 0 0 1 1 1 0 　　　　　V3 0 0 0 0 0 1 　　　　　V4 0 0 0 0 0 0 　　　　　V5 0 0 1 0 0 1 　　　　　V6 0 0 0 1 0 0 要求：（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("ERROR");exit(0);} 　　　 T→data=ch; 　　　 ex(T→lc); 　　　 ex(T→rc); 　　　 } 　　　　　} 六、实现下列算法（共2题，每题10分，共计20分） 1．设有一个带表头结点的双向链表L， 每个结点有4个数据成员：指向前驱结点的指针llink，指向后继结点的指针rlink，存放字符数据的成员data和访问频度freq．所有结点的freq 初始时都为0．试设计一个实现下述要求的查找运算函数Locate．每当在链表上进行一次Locate(L, x) 操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头． 　　设定义链表结构 　　struct DoubleListNode 　　{ 　　 char data ; 　　 int freq; 　　 DoubleListNode * llink, *rlink ; 　　}; 要求：(1) 对主要步骤加注释说明； (2) 算法描述如下： 　　　　　　DoubleListNode * locate ( DoubleListNode *f ; char &x ) 　　　　　　　 2．假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data, next和prior。其中data为整型数域，next和prior均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域（此域初值为NULL）把所有结点按照其值从小到大的顺序链接起来