2002 年同济大学硕士研究生入学试卷
|业务码 业务名称 数据结构与程序设计（C） (013)
适用专业：检测技术与自动化装置 成人教育学 电机与电器 电力系统及其自动化
信与信息系统 控制理论与控制工程 系统工程 模式识别与智能系统|
计算机系统结构 管理科学与工程 0816 结构工程|
交通信息工程及控制 交通运输规划与管理 计算机软件理论 计算机应用技术
数据结构部分：
1．[10 分]设有一个工程包含了 8 个子工程，这些子工程之间有如下的优先关系：
1>2,3,4 3>5 5>7, 8
2>3, 6 4>7 6>5, 8
(这里，1>2,3,4 表示子工程 1 需要在子工程 2，3，4 开始前完成，其它的依次类推)
如果在邻接表存储结构中，每个顶点的邻接点序号是从小到大链接时，试写出其拓扑有
序序列，并说明这个工程的可行性。
2．[10 分]已知待散列存储的关键字序列为（4，15，38，49，33，60，27，71）， 哈希函
数为 H（key）=key MOD 11，哈希表 HT 的长度为 11。采用二次探测再散列法解决冲
突，试构造此哈希表，并写出在等概率情况下的平均查找长度。
3．[10 分]二叉树的二叉链表表示为：
类 C 语言 类 PASCAL 语言
typedef struct bnode{ TYPE bitreptr=↑bnodetp;
char data; bnodetp=RECORD
struct bnode *Lchild,*Rchild; data:char;
}BNODE; Lchild,Rchild:bitreptr
END;
以下是分别用类 C 语言和类 PASCAL 语言描述的二叉树后序遍历的非递归算法，其中，使用一
个顺序栈 stack，栈顶指针为 top；s 为标志数组；p 为辅助指针。
类 C 语言 类 PASCAL 语言
void postorder(BNODE *p) PROC postorder(p:bitreptr);
{top=0; top:=0;
do{ REPEAT
while(p!=NULL) { WHILE p<>NIL DO
top++; [ top:=top+1;
stack[top]=p; stack[top]:=p;
s[top]=0; s[top]:=0;
(1) ______; (1)______;]
} WHILE(s[top]=1)AND(top>0) DO
while((s[top]= =1)&&(top>0)){ [ (2)________;
(2)________; (3) ________;
(3) ________; write(p↑.data)]
printf(“%c”,p→data); IF top>0
} THEN [s[top]:=1;
if(top>0){ (4)_________;}
s[top]=1; UNTIL top=0
