985院校数据结构试卷

一、算法填空题(20分)大连理工大学2002年硕士入学试题数据结构部分(共50分)1．对以下函数填空，实现将头指针为h的单链表逆置，即原链表的第一个结点变成逆置后新链表的最后一个结点，原链表的第二个结点变成新链表的倒数第二个结点，如此等等，直到最后一个结点作为新链表的第一个结点，并返回指向该结点的指针。设单链表结点类型的定义为typedefstructnode{intdata；strcutnode*next；}NODE；NODE*dlbnz(NODE*h){NODE*p，*q；q=NULL；while(h)p=h；h=h-next；；；}returnq；}2．假设算术表达式由字符串b表示，其中可以包含三种括号：圆括号和方括号及花括号，其嵌套的顺序随意，如{[]([])}。请对以下函数填空，实现判别给定表达式中所含括号是否正确配对出现的算法。#defineM10intkhjc(char*b){charsM}；inti，j=0，f=1；j=0；for(i=0；f&&b[i]!=’\0’；i++){switch(b[i]){case’(’：；break；case’[’：；break；case‘{’：；break；case’)’：case’]’：case’[’：if(j==0;||b[I]!=)f=0；}}returnf&&；}3．对以下函数填空，实现以带头结点的单链表h为存储结构的直接选择排序。设单链表结点类型的定义为typedefstructnode{intkey；structnode*next；}NODE；voidpxx(NODE*h){NODE*p，*q，*m；intz；p=h-next；while(p!=NULL){q=p-next；m=p；while(q!=NULL){if(m-keyq-key)；；}if(p!=m){x=p-key；p-key=m-key；m-key=x；}；}}二、算法设计题(30分)请用类C或类PASCAL语言设计实现下列功能的算法。1．设二叉排序树以二叉链表为存储结构，请编写一个非递归算法，从大到小输出二叉排序树中所有其值不小于X的键值。(10分)2．设由n个整数组成一个大根堆(即第一个数是堆中的最大值)，请编写一个时间复杂度为O(log2n)的算法，实现将整数X插入到堆中，并保证插入后仍是大根堆。(10分)3．请编写一个算法，判断含n个顶点和e条边的有向图中是否存在环。并分析算法的时间复杂度。(10分)大连理工大学2003年硕士入学试题数据结构部分(共75分)一、回答下列问题(20分)1．循环队列用数组A[0．．m—1)存放其数据元素。设tail指向其实际的队尾，front指向其实际队首的前一个位置，则当前队列中的数据元素有多少个?如何进行队空和队满的判断?2．设散列表的地址空间为0~10，散列函数为H(key)=key％11(％为求余函数)，采用线性探查法解决冲突，并将键值序列{15，36，50，27，19，48}依次存储到散列表中，请画出相应的散列表；当查找键值48时需要比较多少次?3．什么是m阶B-树?在什么情况下向一棵m阶B-树中插入一个关键字会产生结点分裂?在什么情况下从一棵m阶B-树中删除一个关键字会产生结点合并?4．什么是线索二叉树?一棵二叉树的中序遍历序列为由djbaechif，前序遍历序列为abdjcefhi，请画出该二叉树的后序线索二叉树。二、请用类C或类PASCAL语言进行算法设计，并回答相应问题。(45分)1．设计一非递归算法采用深度优先搜索对无向图进行遍历，并对算法中的无向图的存储结构予以简单说明。2．用链式存储结构存放一元多项式Pn(x)=P1xel+P2xe2+…+Pnxen，其中Pi是指数为ei的项的非零系数，且满足0≤e1≤e2…en=n。请设计算法将多项式B=Pn2(x)加到多项式A=Pn1(x)，同时对算法及链表的结点结构给出简单注释。要求利用Pnl(x)和Pn2(x)的结点产生最后求得的和多项式，不允许另建和多项式的结点空间。3．(1){Rl，R2，…，Rn}为待排序的记录序列，请设计算法对{R1，R2，…，Rn}按关键字的非递减次序进行快速排序。(2)若待排序的记录的关键字集合是{30，4，48，25，95，13，90，27，18)，请给出采用快速排序的第一趟、第二趟排序结果。(3)若对(2)中给出的关键字集合采用堆排序，请问初建的小根堆是什么?(4)当给定的待排序的记录的关键字基本有序时，应采用堆排序还是快速排序?为什么?三、算法填空(10分)1．一棵树以孩子兄弟表示法存储，递归算法numberofleaf计算并返回根为r的树中叶子结点的个数(NULL代表空指针)。typedefstructnode{structnode*firstchild，*nextbrother；}TFNNode；intnumberofleaf(TFNNode*r){intnum；if(r==NULL)num=0；elseif(r-firstchild==NULL)num=+numberofleaf；(r-nextbrother)；else；return(num)；}2．在根结点为r的二叉排序树中，插人数据域值为x的结点，要求插入新结点后的树仍是一棵二叉排序树(NULL代表空指针)。二叉排序树的结点结构为typedefstructnode{intkey；structnode*lc,*rc；}BiNode；BiNode*insert(BiNode*r,intx){BiNode*p,*q,*s;s=(BiNode*)malloc(sizeof(BiNode));s-key=x;s-lc=NULL;s-rc=NULL;q=NULL;if(r==NULL){r=s;return(r);}p=r;while(){q=p;if()p=p-lc;elsep=p-rc}if(xq-key);else;return;}清华大学2001年数据结构与程序设计试题试题内容：一、试给出下列有关并查集(mfsets)的操作序列的运算结果：union(1，2)，union(3，4)，union(3，5)，union(1，7)，union(3，6)，union(8，9)，union(1，8)，union(3，10)，union(3，11)，union(3，12)，union(3，13)，union(14，15)，union(16，0)，union(14，16)，union(1，3)，union(1，14)。(union是合并运算，在以前的书中命名为merge)要求：(1)对于union(i，j)，以i作为j的双亲；(5分)(2)按i和j为根的树的高度实现union(i，j)，高度大者为高度小者的双亲；(5分)(3)按i和j为根的树的结点个数实现union(i，j)，结点个数大者为结点个数小者的双亲。(5分)二、设在4地(A，B，C，D)之间架设有6座桥，如下图所示：要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。(1)试就以上图形说明：此问题有解的条件是什么?(5分)(2)设图中的顶点数为n，试用C或Pascal描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。(10分)三、针对以下情况确定非递归的归并排序的运行时间(数据比较次数与移动次数)：(1)输人的n个数据全部有序；(5分)(2)输入的n个数据全部逆向有序；(5分)(3)随机地输入几个数据。(5分)四、简单回答有关AVL树的问题。(1)在有N个结点的AVL树中，为结点增加一个存放结点高度的数据成员，那么每一个结点需要增加多少个字位(bit)?(5分)(2)若每一个结点中的高度计数器有8bit，那么这样的AVL树可以有多少层?最少有多少个关键码?(5分)五、一个散列表包含hashSize=13个表项，其下标从0到12，采用线性探查法解决冲突。请按以下要求，将下列关键码散列到表中。101003245581263292004000(1)散列函数采用除留余数法，用％hashSize(取余运算)将各关键码映像到表中。请指出每一个产生冲突的关键码可能产生多少次冲突。(7分)(2)散列函数采用先将关键码各位数字折叠相加，再用％hashSize将相加的结果映像到表中的办法。请指出每一个产生冲突的关键码可能产生多少次冲突。(8分)六、设一棵二叉树的结点定义为structBinTreeNode{ElemTypedata；BinTreeNode*leftChild,*rightChild；}现采用输入广义表表示建立二叉树。具体规定如下：(1)树的根结点作为由子树构成的表的表名放在表的最前面；(2)每个结点的左子树和右子树用逗号隔开。若仅有右子树，没有左子树，逗号不能省略。(3)在整个广义表表示输入的结尾加上一个特殊的符号(例如“#”)表示输入结果。；例如，对于如右图所示的二叉树，其广义表表示为A(B(D，E(G，))，C(，F))此算法的基本思路是：依次从保存广义表的字符串ls中输入每个字符。若遇到的是字母(假定以字母作为结点的值)，则表示是结点的值，应为它建立一个新的结点，并把该结点作为左子女当(k=1)或右子女(当k=2)链接到其双亲结点上。若遇到的是左括号”(”，则表明子表的开始，将A置为1；若遇到的是右括号”)”，则表明子表结束。若遇到的是逗号”，”，则表示以左子女为根的子树处理完毕，应接着处理以右子女为根的子树，将A置为2。在算法中使用了一个栈s，在进入子表之前，将根结点指针进栈，以便括号内的子女链接之用。在子表处理结束时退栈。相关的栈操作如下：MakeEmpty(s)置空栈Push(s，p)元素p进栈Pop(s)退栈Top(s)存取栈顶元素的函数下面给出了建立二叉树的算法，其中有5个语句缺失。请阅读此算法并把缺失的语句补上。(每空3分)VoidCreateBinTree(BinTreeNode*&BT,charls){StackBinTreeNode*s；MakeEmpty(s)；BT=NULL；//置二叉树BinTreeNode*p；intk；istreamins(ls)；//把串ls定义为输入字符串流对象inscharch；insch；//从ins顺序读入一个字符while(ch!=”#”){//逐个字符处理，直到遇到’#’为止switch(ch){case’(’：(1)k=1；break；case’)’：pop(s)；break；case‘,’(2)break；default：p=newBinTreeNode；(3)p-leftChild=NULL；p-rightChfild=NULL；if(BT==NULL)(4)elseif(k==1)top(s)-leftChild=p；elsetop(8)-rightChild=p；}(5)}}|七、下面是一个用C编写的快速排序算法。为了避免最坏情况，取基准记录pivot采用从left，right和mid=(1eft+right)/2中取中间值，并交换到right位置的办法。数组a存放待排序的一组记录，数据类型为Type，left和right是待排序子区间的最左端点和最右端点。Voidquicksort(Typea&#,intlefl，intright){Typetemp；if(leftright){Typepivot=medlian3(a,left，right)；inti=left，j=right-1;for(；；){while(ij&&s[I]pivot)i++；while(ij&&pivota[j]j--；if(ij){temp=a[i]；a[j]=a[i]；a[i]=temp；i++；j--；}elsebreak；}if(s[i]pivot){temp=a[i]；a[i]=a[right]；a[right]=temp；}quicksort(a,left，i-1)；//递归排序左子区间quick