数据结构C语言描述期末试卷

一、填空(10分)1、一个m阶B-树中，每个结点最少有(ceil(m/2))个儿子结点,m阶B+树中每个结点(除根外)最多有(m)个儿子结点.2、n(n0)个结点构成的二叉树，叶结点最多有(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种字符，其出现的概率分别是0.1、0.4、0.04、0.16、0.19、0.11，试画出相应的哈夫曼树，并设计哈夫曼编码。解：编码：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=2.0四、（10分）下图是带权的有向图G的邻接矩阵表示，请给出：1、其邻接表存储结构2、按Floyd算法求所有顶点对之间最短距离的矩阵变化过程。V1V2V3V4V1|01∞4V2|∞092V3|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-llink=q;}returnOK;}六、（13分）若有一棵二叉树的存储结构为二叉链表，T指向根结点，请写出一个非递归算法判定其是否为二叉排序数。解：解法一：#defineTRUE1#defineFALSE0typedefintBOOL;typedefstructBTreeNode{ElemTypedata;structBTreeNode*lchild,*rchild;}BTreeNode,*BTree;//我是将教材P130的中序非递归遍历方法改的//注释没写，大家看书上的吧BOOLIsBST(BTreeT){if(!T)returnTRUE;InitStack(S);x=T-data;Push(S,T);while(!StackEmpty(S)){while(GetTop(S,p)&&p)Push(S,p-lchild);Pop(S,p);if(!StackEmpty(S)){Pop(S,p);if(xp-data)returnFALSE;x=p-data;Push(S,p-rchild);}//if//whilereturnTRUE;}另解：//我的另外一个解法,根据longeli的思想//Author:Ritchie//Date:2002-10-12typedefintElemType;typedefstructBiTreeNode{ElemTypedata;structBTreeNode*lchild,*rchild;}BiTreeNode,*BiTree;//功能：判断二叉树T是否为二叉排序树,如果是返回TRUE,否则返回FALSE//思想：判断T中的结点是否符合要求,按层序进行判断,一旦不符合就返回StatusIsBST(BiTreeT){if(!T)returnTRUE;//空树是BSTInitQueue(Q);EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,t);//左右孩子先入队if(t-lchild)EnQueue(Q,t-lchild);if(t-rchild)EnQueue(Q,t-rchild);if(t-lchild&&t-lchild){//左右子树不为空且不满足BST的条件，返回FALSEif((t-lchild-data=t-data)||(t-rchild-datat-data))returnFALSE;}elseif(t-lchild&&(t-lchild-data=t-data)){//右子树为空的情况returnFALSE;}elseif(t-rchild&&(t-rchild-datat-data)){//左子树为空的情况returnFALSE;}}DestroyQueue(Q);returnTRUE;}用递归的方式做也有两三种做法，这儿就不列举了。七、（15分）下表列出了某工序之间的优先关系和各工序所需时间，要求：（1）画出AOE网（2）列出各事件的最早、最晚发生时间（3）找出该AOE网中的关键路径，并回答完成该工程所需要的最短时间。工序代所需时先驱工序工序代号所需时先驱工号间间序A15无H15G、IB10无I120EC50A、BJ60ID8BK15F、IE15C、DL30H、J、KF40BM20LG300E解：(1)AOE图如下(需要添加虚线才可以画出图，我就是在这儿被迷惑住的，第一次看到这样的题目)（2）各事件的最早最迟发生时间:事件编号1234567891011ve(i)01510655080200380395425445vl(i)015576538803338394244050555(3)通过上表不用求出活动的最早最迟开始时间就可以看出关键路径为：1，2，4，6，8，9，10，11完成工程所需的最短时间为：445