《数据结构(C语言描述)》期末试卷.doc

《数据结构(C语言描述)》期末试卷(—学年第学期)题号总分得分一、填空(10分)1、一个m阶B-树中,每个结点最少有(ceil(m/2))个儿子结点,m阶B+树中每个结点(除根外)最多有(m)、n(n>0)个结点构成的二叉树,叶结点最多有(floor((n+1)/2))个,最少有(1)个。若二叉树有m个叶结点,则度为2的结点有(m-1)个。3、顺序查找方法适用于存储结构为(顺序表和线性链表)的线性表,使用折半查找方法的条件是(查找表为顺序存贮的有序表)4、广义表A=((),(a,(b,c)),d)的表尾Gettail(A)为(((a,(b,c)),d))5、直接插入排序,起泡排序和快速排序三种方法中,(快速排序)所需的平均执行时间最小;(快速排序)所需附加空间最大。二、选择(10分)1、倒排文件的主要优点是:(C)A、便于进行插入和删除B、便于进行文件的合并C、能大大提高基于非主关键字数据项的查找速度D、易于针对主关键字的逆向检索2下面程序段的时间复杂性为(C)y=0;while(n>=(y+1)*(y+1)){y++;}A、O(n)B、O(n2)C、O(sqrt(n))D、O(1)3、若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序,则该二叉树是(C)A、二叉排序树B、哈夫曼树C、堆D、AVL树4、栈和队列都是(B)A、顺序存储的线性结构B、限制存取点的线性结构C、链式存储的线性结构D、限制存取点的非线性结构5、用顺序查找方法查找长度为n的线性表时,在等概率情况下的平均查找长度为(D)A、nB、n/2C、(n-1)/2D、(n+1)/2三、简答(30分)1、已知一棵二叉树的前序扫描序列和中序扫描序列分别为ABCDEFGHIJ和BCDAFEHJIG,试给出该二叉树的后序序列并绘出该二叉树对应的森林。解:后序序列为:DCBFJIHGEA2、若对序列(7,3,1,8,6,2,4,5)按从小到大排序,请写出起泡排序的第一趟结果和堆排序的初始堆。解:冒泡:31762458堆:874562133、某通讯系统只可能有A、B、C、D、E、F6种字符,、、、、、,试画出相应的哈夫曼树,并设计哈夫曼编码。解:编码:A:1011B:0C:1010D:110E:111F:1004、在二叉平衡检索树(AVL树)的调整中,将最靠近新插入点的不平衡结点调整平衡后,树中是否还会有不平衡结点?为什么?解:不会再有不平衡点。因为插入结点发生不平衡现象后,会改变以“靠近新插入点的不平衡结点”为根的子树(即最小不平横树)的高度加1,经过调整后使最小不平衡树的整体高度又恢复到原来的值,所以不会对原平衡树的其他部分造成危害,因此不会再有不平衡点。5、指定Hash函数H(k)=3*kmod11及线性探测开地址法处理冲突,试在0~10的散列空间中对关键字序列(22,41,53,46,30,13,01,67)构造Hash表,并求在等查找概率下查找成功的平均查找长度。解:插入元素后的分布情况:0123456789102241300153461367ASL=(1+1+1+1+2+2+2+6)/8=、(10分)下图是带权的有向图G的邻接矩阵表示,请给出:1、其邻接表存储结构2、按Floyd算法求所有顶点对之间最短距离的矩阵变化过程。V1V2V3V4V1|01∞4V2| ∞ 0 9 2V3|3508V4| ∞∞60解:Floyd算法执行过程中矩阵的变化情况为(从左到右):01∞4∞0923407∞∞6001103∞0923406∞∞600110312092340691060019311082340691060五、(12分)设双链表结点结构为llinkdatarlink,请设计算法将其中P所指结点与其rlink所指结点位置互换的算法。解:typedefstructDLNode{ElemTypedata;structDLNode*llink,*rlink;}DLNode,*DLinkList;//思想:将P->rlink先从链表中删除掉,然后再插入到P前StatusSwapANode(DLNode*&P){//结点存在吗?if(!P||!(P->rlink))returnERROR;q=P->rlink;//删除q结点if(!q->rlink)P->rlink=NULL;else{P->rlink=q->rlink;q->rlink->llink=P;}//将q结点插入到P结点前面if(!P->llink){q->llink=NULL;q->rlink=P;P->llink=q;}else{q->llink=P->llink;q->rlink=P;P->llink->rlink=q;P