《数据结构2008(信管a)》由会员分享，可在线阅读，更多相关《数据结构2008(信管a)（6页珍藏版）》请在金锄头文库上搜索。
1、广东工业大学试卷用纸，共 6 页，第 1 页 学 院： 专 业： 学 号： 姓 名： 装 订 线 广东工业大学考试试卷 ( A ) 课程名称: 数据结构（C语言） 试卷满分 100 分 考试时间: 2008 年 6 月25日 (第 18 周 星期 3 ) 题 号 一 二 三 四 五 六 七 八 九 十 总分 评卷得分 评卷签名 复核得分 复核签名 一、选择题(每项选择 2分，共 36分) 1、下面程序段的时间复杂度为（ ） 。 i=1; while (idata=b;p=h-link;q=h;while(p-data!=ap=_p-link_;(2 分) if(p-data=a) q-link
2、=s; _s-link=p;_;(2 分)else _p-link=s;_;(2 分) s-link=NULL; （1） （2分）什么是表头结点？ 用来指向链表的第一个节点的空节点。 （2） （2分）分析该算法的时间复杂度为多少？O(n)广东工业大学试卷用纸，共 6 页，第 4 页 2、 （12分）以下函数实现二分法查找。 int binarysearch(Elem r,int n,int k) int low,high,mid;low=1;high=n;while(_mid=0_)(2 分) mid=(low+high)/2;if ( k=rmid.key) return(_mid_ );
3、(2 分)else if(krj+1.key) j+; if(x.keyrj.key)ri=rj;i=j;_( 2分) else break;广东工业大学试卷用纸，共 6 页，第 5 页 _（2分） （1） （2分）形参表中的 t 和 w 分别表示（ ） A、待调整子树的根结点和结点最大层序编号； B、待调整子树中层序编号最大的结点和叶子结点数； C、结点总数和根结点； D、结点总数和待调整子树中层序编号最大的结点。 （2）(2 分)所指判断语句的作用是 _。 三、应用题（共 34分） 1、 （10分）对下面的 AOE 网，请求出一条关键路径（列出所有顶点事件的最早 发生时间 VE、最晚发生时
4、间 VL，和所有活动的最早发生时间 E、最迟发生时间 L） 。 D E F A B C G H I a 1 =3 a 5 =1 a 4 =2 a 6 =3 a 3 =4 a 2 =2 a 7 =5 a 8 =8 a 9 =4 a 10 =5 a 11 =2 a 12 =3 顶点 VE VL 活动 E L A a 1 B a 2 C a 3 D a 4 E a 5 F a 6 G a 7 H a 8 I a 9 a 10广东工业大学试卷用纸，共 6 页，第 6 页 a 11 a 12 2、 （8分）对于以下无向带权图 利用 Prim 算法，从 V1 出发，得到最小生成树的过程中，依次归并到最小生
5、成 树顶点集 U 所产生的顶点序列是什么？这棵最小生成树的代价是多少？3、 （4分）已知一棵二叉树的层次序列为 ABCDEFGHIJ，中序序列为 DBGEHJACIF，请画出该二叉树。4、 （8分）某系统在通信联络中只可能出现八种字符，它们分别是 ABCDEFGH， 其概率分别为 0.05，0.19，0.18，0.09，0.12，0.23，0.13，0.01。现要对这八种字符 进行 Huffman 编码。画出该 Huffman 树(权值大的结点做左孩子)，在所有的结点上 标出其权值，并求出这棵树的带权路径长度。V 1 V 2 V 3 V 4 V 5 2 6 2 3 3 5 1 1 2 1 5 9 3 3 1
