大连理工大学2002年硕士入学试题
数据结构部分(共50分)
一、算法填空题(20分)
1．对以下函数填空，实现将头指针为h的单链表逆置，即原链表的第一个结点变成逆置后新链表的最后一个结点，原链表的第二个结点变成新链表的倒数第二个结点，如此等等，直到最后一个结点作为新链表的第一个结点，并返回指向该结点的指针。设单链表结点类型的定义为
typedef struct node
{int data；
strcut node *next；
}NODE；
NODE dlbnz(NODEh)
{ 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；
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分)
