《数据结构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