附录：
大连理工大学2002年硕士入学试题
数据结构部分(共50分)
一、算法填空题(20分)
1．对以下函数填空，实现将头指针为h的单链表逆置，即原链表的第一个结点变成逆置后新链表的最后一个结点，原链表的第二个结点变成新链表的倒数第二个结点，如此等等，直到最后一个结点作为新链表的第一个结点，并返回指向该结点的指针。设单链表结点类型的定义为
typedef struct node {int data；
strcut node *next； }NODE；
NODE *dlbnz(NODE*h) { NODE *p，*q； q=NULL； while(h) p=h；
h=h->next； ； ； }
return q； }
2．假设算术表达式由字符串b表示，其中可以包含三种括号：圆括号和方括号及花括号，其嵌套的顺序随意，如{[]([])}。请对以下函数填空，实现判别给定表达式中所含括号是否正确配对出现的算法。
#define M 10 int khjc(char *b) { char sM}；
int i，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； } }
return f&& ； }
3．对以下函数填空，实现以带头结点的单链表h为存储结构的直接选择排序。设单链表结点类型的定义为
typedef struct node { int key；
struct node *next；
}NODE；
void pxx(NODE *h)
{ NODE *p，*q，*m；
1
int z；
p=h->next； while(p!=NULL) { q=p->next； m=p；
while(q!=NULL)
{ if(m->key>q->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… 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) 2 { int num； if(r==NULL) num=0； else if(r->firstchild==NULL) 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(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) 要求： (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分) 3 (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； } 现采用输入广义表表示建立二叉树。具体规定如下： (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!=”#”) { //逐个字符处理，直到遇到?#?为止 4