大连理工大学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代表空指针)。
typedef struct node{struct node *firstchild，*nextbrother；}TFNNode；
int numberofleaf(TFNNode *r)
{ int num；
if(rNULL) num=0；
else
if(r->firstchildNULL)
num= +numberofleaf；
(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®;}
p=r;
while( )
{ q=p;
if( ) p=p->lc;
else p=p->rc
}
if(xkey) ;
else ;
return;
}