南京财经大学2007419

《南京财经大学2007419》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、南京财经大学2007年攻读硕士学位研究生入学考试（初试）试卷考试科目：419数据结构与计算机组成原理适用专业：计算机应用技术考试时间：2007年1月21日下午14:00~7:00注意事项：所有答案必须写在答题纸上，做在试卷或草稿纸上无效。第一部分：数据结构试题（本部分共六大题，共计75分）一、简答题（共6题，每题5分，共计30分）1．线性表有哪两种存储结构？如果有n个线性表同时并存，而且在处理过程中各表的长度会动态地发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？2．已知一棵二叉树的先序遍历为：ABDCEF；中序遍历为：DBAECF。要

2、求：（1）画出这棵二叉树；（2）写出这棵二叉树的后序遍历序列。3．已知图的邻接矩阵为：V1V2V3V4V5V6V1011100V2001110V3000001V4000000V5001001V6000100要求：（1）画出此图的邻接表；（2）写出对该图进行拓扑排序时所有的拓扑有序序列。4．依次输入一个关键字序列{50，17，66，56，70，12，60，52}，要求：（1）画出按输入次序构造的二叉排序树；6第页共6页（2）画出该树在删除关键字“66”后的二叉排序树。5．指出所有满足下列条件的二叉树：（1）它们在先序遍历和中序遍历时，得到的遍历序列相同；（2）它们在后序

3、遍历和中序遍历时，得到的遍历序列相同；（3）它们在先序遍历和后序遍历时，得到的遍历序列相同。6．设有哈希函数为H(key)=keyMOD11，哈希表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分）三、已知

4、一个无向图的邻接表如下图所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。（共1题，共计6分）V1V2V3V4V5V6V760506540457050524230四、已知下图所示的一个网，按照Kruskal方法，求该网的最小生成树的产生过程。（共1题，共计7分）6第页共6页五、阅读以下算法。算法执行时，依次输入数据ABC##DE#G##F##H##，试指出该算法的功能，并画出执行此算法后所建立的数据结构示意图。（共1题，共计5分）typedefstructNode{chardata;structNode*lc,*rc;}BiTNode,*BiT

5、ree;voidex(BiTree&T){charch;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初始时都为

6、0．试设计一个实现下述要求的查找运算函数Locate．每当在链表上进行一次Locate(L,x)操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头．设定义链表结构structDoubleListNode{chardata;intfreq;DoubleListNode*llink,*rlink;};要求：(1)对主要步骤加注释说明；(2)算法描述如下：DoubleListNode*locate(DoubleListNode*f;char&x)

7、6第页共6页2．假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data,next和prior。其中data为整型数域，next和prior均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域（此域初值为NULL）把所有结点按照其值从小到大的顺序链接起来。设已定义类型LinkList如下：typedefstructnode{intdata;structnode*next,*prior;}LinkList;要求：(1)采用插入排序的方法；(2)对主要步骤加注释说明；(3)算法描述如下：insert(Link