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… 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代表空指针)。 typedef struct node{struct node *firstchild，*nextbrother；}TFNNode； int numberofleaf(TFNNode *r) { int num； if(r==NULL) num=0； else if(r->firstchild==NULL) num= +numberofleaf； 21 (r->nextbrother)； else ； return(num)； } 2．在根结点为r的二叉排序树中，插人数据域值为x的结点，要求插入新结点后的树仍是一棵二叉排序树(NULL代表空指针)。 二叉排序树的结点结构为 typedef struct node { int key； struct node *lc,*rc； }BiNode； BiNode *insert(BiNode *r,int x) { 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; else p=p->rc } if(x 清华大学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) 要求： 22 (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，采用线性探查法解决冲突。请按以下要求，将下列关键码散列到表中。 10 100 32 45 58 126 3 29 200 400 0 (1)散列函数采用除留余数法，用％hashSize(取余运算)将各关键码映像到表中。请指出每一个产生冲突的关键码可能产生多少次冲突。(7分) (2)散列函数采用先将关键码各位数字折叠相加，再用％hashSize将相加的结果映像到表中的办法。请指出每一个产生冲突的关键码可能产生多少次冲突。(8分) 六、设一棵二叉树的结点定义为 struct BinTreeNode{ ElemType data； BinTreeNode *leftChild,*rightChild； } 23 现采用输入广义表表示建立二叉树。具体规定如下： (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分) Void CreateBinTree(BinTreeNode *&BT,char ls) { Stack istream ins(ls)； //把串ls定义为输入字符串流对象ins char ch； ins>>ch； //从ins顺序读入一个字符 while(ch!=”#”) { //逐个字符处理，直到遇到?#?为止 switch(ch) { case?(?： (1) k=1； break； case ?)?：pop(s)； break； 24 case ?,? (2) break； default：p=new BinTreeNode； (3) p->leftChild=NULL； p->rightChfild=NULL； if(BT==NULL) (4) else if(k==1) top(s)->leftChild=p； else top(8)->rightChild=p； } (5) } }| 七、下面是一个用C编写的快速排序算法。为了避免最坏情况，取基准记录pivot采用从left，right和mid=? (1eft+right)/2?中取中间值，并交换到right位置的办法。数组a存放待排序的一组记录，数据类型为Type，left和right是待排序子区间的最左端点和最右端点。 Void quicksort(Type a&#, int lefl，int right) { Type temp； if(left { Type pivot=medlian3(a,left，right)； int i=left，j=right-1; for( ； ；) { while(i { temp=a[i]；a[j]=a[i]；a[i]=temp； i++；j--； } else break； } if(s[i]>pivot) { temp=a[i]；a[i]=a[right]；a[right]=temp；} quicksort(a,left，i-1)； //递归排序左子区间 quicksort(a，i+1，right)；//递归排序右子区间 } } 25