搜索
专业《数据结构（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)015576538080335380395425445(3)通过上表不用求出活动的最早最迟开始时间就可以看出关键路径为：1，2，4，6，8，9，10，11完成工程所需的最短时间为：4451.算法的计算量的大小称为计算的（）。【北京邮电大学2000二、3（20/8分）】A．效率B.复杂性C.现实性D.难度2.算法的时间复杂度取决于（）【中科院计算所1998二、1（2分）】A．问题的规模B.待处理数据的初态C.A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。(1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法(2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性【南京理工大学1999一、1（2分）【武汉交通科技大学1996一、1（4分）】4．一个算法应该是（）。【中山大学1998二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.5.下面关于算法说法错误的是（）【南京理工大学2000一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的1．下述哪一条是顺序存储结构的优点？（）【北方交通大学2001一、4（2分）】A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）【北方交通大学2001一、14（2分）】A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。3．线性表是具有n个（）的有限序列（n0）。【清华大学1998一、4（2分）】A．表元素B．字符C．数据元素D．数据项E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。【哈尔滨工业大学2001二、1（2分）】A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。【南开大学2000一、3】A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表【合肥工业大学2000一、1（2分）】7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。【北京理工大学2000一、1（2分）】A．单链表B．双链表C．单循环链表D．带头结点的双循环链表8.静态链表中指针表示的是（）.【北京理工大学2001六、2（2分）】A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址9.链表不具有的特点是（）【福州大学1998一、8(2分)】A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比10.下面的叙述不正确的是（）【南京理工大学1996一、10（2分）】A．线性表在链式