业务码 业务名称 数据结构与程序设计（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
（4）________； ENDP；
}
}while（top！=0）
}
4.[10分]试写出在含有n个元素的堆中增加一个新元素x，且调整为堆的算法。
说明： （1）本题中的堆为小顶堆。
（2）每个元素为一个记录，类型rectype，其中，关键字域为key；由n个记录
R[1]到R[n]所组成的文件类型为filetype.
5.[10分]在某商店仓库中，欲对电视机按其价格从低到高的次序构造一个头指针为head的、
不带表头结点的单循环链表，链表的每个结点指出同样价格的电视机的台数。现有m台价格
为n元的电视机入库，试编写出仓库电视机的进货算法。
链表的结点类型表示：
类C语言 类PASCAL语言
typedef struct list{ TYPE linkisttp=↑nodetp；
float price；（价格） nodetp=RECORD
int num；（数量） price：real； （价格）
struct list *next； num：integer；（数量）
}Linklist； next：linkisttp
END；
说明：请在4，5题的答案中，先说明算法思想或步骤，然后任选C语言或类PASCAL语言写出算法。
相关链接：同济大学历年考研专业课试题汇总