数据结构2008(信管A).doc

广东工业大学考试试卷 ( A )课程名称: 数据结构（C语言） 试卷满分 100 分考试时间: 2008 年 6 月25日 (第 18 周 星期 3 )题 号一二三四五六七八九十总分评卷得分评卷签名复核得分复核签名一、选择题(每项选择2分，共36分)1、下面程序段的时间复杂度为（ ）。i=1;while (idata=b; p=h-link;q=h; while(p-data!=a&p-link!=NULL) q=p;p=_p-link_;(2分)if(p-data=a) q-link=s;_s-link=p;_;(2分) else _p-link=s;_;(2分)s-link=NULL;（1）（2分）什么是表头结点？ 用来指向链表的第一个节点的空节点。（2）（2分）分析该算法的时间复杂度为多少？O(n)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_ ); (2分) else if(krmid.key) high=_mid_;(2分) else low=_mid_;(2分) return(-1);（1）（2分）该函数查找成功和查找不成功分别返回什么？Mid,-1;（2）（2分）二分法查找特别适合于什么特点的线形表？顺序表3、（10分）以下是floyd筛选法调整堆的程序段，阅读程序完成填空：int sift(JD r,int t,int w)/*JD为待排序记录结构，含排序码key*/ int i,j; JD x; i=t; x=ri; j=2*i; while(_) （2分） if( jrj+1.key) j+; if(x.keyrj.key) ri=rj;i=j;_( 2分) else break; _（2分）（1）（2分）形参表中的t和w分别表示（ ） A、待调整子树的根结点和结点最大层序编号；B、待调整子树中层序编号最大的结点和叶子结点数；C、结点总数和根结点；D、结点总数和待调整子树中层序编号最大的结点。（2）(2分)所指判断语句的作用是_。三、应用题（共34分）1、（10分）对下面的AOE网，请求出一条关键路径（列出所有顶点事件的最早发生时间VE、最晚发生时间VL，和所有活动的最早发生时间E、最迟发生时间L）。顶点VEVL活动ELAa1Ba2Ca3Da4Ea5Fa6Ga7Ha8Ia9a10a11a122、（8分）对于以下无向带权图利用Prim算法，从V1出发，得到最小生成树的过程中，依次归并到最小生成树顶点集U所产生的顶点序列是什么？这棵最小生成树的代价是多少？V1V2V3V4V5262335112159331 3、（4分）已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二叉树。 4、（8分）某系统在通信联络中只可能出现八种字符，它们分别是ABCDEFGH，其概率分别为0.05，0.19，0.18，0.09，0.12，0.23，0.13，0.01。现要对这八种字符进行Huffman编码。画出