业务码 业务名称 数据结构与程序设计（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语言写出算法。
转载请注明出自bbs.kaoyan.com,本贴地址:http://bbs.kaoyan.com/viewthread.php?tid=1696350
