搜索
《数据结构》期末考试试卷一、选择题（单选题，每小题3分，共33分）1．已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为B。A．BCDEAFB．ABDCEFC．DBACEFD．DABECF2．在11个元素的有序表A[1…11]中进行折半查找（2/)(highlow），查找元素A[11]时，被比较的元素的下标依次是B。A．6，8，10，11B．6，9，10，11C．6，7，9，11D．6，8，9，113．由元素序列（27，16，75，38，51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为2的结点）为D。A．27B．38C．51D．754．利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素30要进行B次元素间的比较。A．4B．5C．6D．75．循环链表的主要优点是D。A．不再需要头指针了B．已知某个结点的位置后，很容易找到它的直接前驱结点C．在进行删除后，能保证链表不断开D．从表中任一结点出发都能遍历整个链表6．已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key）=key%7计算散列地址，并散列存储在散列表A[0…6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率查找时查找成功的平均查找长度为C。A．1．5B．1．7C．2．0D．2．37．由权值为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为C。A．23B．37C．44D．468．在最好和最坏情况下的时间复杂度均为O（nlogn）且稳定的排序方法是D。A．基数排序B．快速排序C．堆排序D．归并排序9．无向图G=(V，E)，其中V={a，b，c，d，e，f}，E={(a，b)，（a，e），(a，c)，（b，e），（c，f），(f，d)，（e，d）}。对该图进行深度优先遍历，下面不能得到的序列是A。A．aebdcfB．abedfcC．aedfcbD．acfdeb10．置换-选择排序的功能是A。A．产生初始归并段B．选出最大的元素C．产生有序文件D．置换某个记录11．ISAM和VSAM文件属于A。A．索引顺序文件B．索引非顺序文件C．顺序文件D．散列文件二、填空题(1~8每空2分，9~12每空1分，共20分）1．下面程序段的时间复杂度为O(n)。Sum=1;For(i=0;sumn;i++)sum+=i;2．稀疏矩阵快速转置算法(见第三题第1小题)的时间复杂度为O(tu+nu)，空间复杂度为O(nu)。3．对广义表A=(a，(b，c，d))的运算head(rail(A))的结果是(b，c，d)。4．将n个数据元素依次按a1，a2，…，an的顺序压入栈中，共有22)!()!2(1111nnnCnnn或种出栈序列。5．含有4个结点的不相似的二叉树有14棵。6．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，则A[3][3](10)存放的位置为692。(脚注(10)表示用10进制表示)7．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总的结点数是69。8．给定一组关键字{49，38，65，97，76，13，27，49’}，以下用了4种不同的排序方法分别得到了第一趟排序后的结果，请指出各自对应的排序方法。（每空1分）第一趟排序后的结果排序方法{27，38，13，49，76，97，65，49’}【快速排序】{38，49，65，97，13，76，27，49’}【二路归并排序】{49’，76，65，49，38，13，27，97}【堆排序】{13，65，76，97，27，38，49，49’}【链式基数排序】三、算法填空题(每空3分,共18分）1．稀疏矩阵快速转置算法//稀疏矩阵的三元组顺序表存储表示#defineMAXSIZE12500//非零元个数最大为12500typedefstruct{inti,j;//行号,列号ElemTypee;//非零元}Triple;typedefstruct{Tripledata[MAXSIZE+1];//三元组表．0号不用intmu,nu,tu;//总行数,总列数,非零元总个数}TSMatrix;#defineMAXCOL50statusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元组表存储表示,求稀疏矩阵M的转置矩阵T．intnum[MAXCOL],cpot[MAXCOL],col,t,p,q;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col=M.nu;++col)num[col]=0;for(t=1;t=M.tu;++t)++num[①];//求M中每一列含非零元个数cpot[1]=1;//求第col列中第一个非零元在T.data中的序号for(col=2;col=M.nu;++col)//后一列第一个非零元在T．data中的序号等于cpot[col]=cpot[col-1]+②;//前一列的序号+前一列非零元个数for(p=1;p=M.tu;++p){col=M.data[p].j;//M中第p行的列号域值赋给colq=cpot[col];//M中的第col列非零元在T.data中的恰当位置赋给qT.data[q].i=M.data[p].j;//M中的第p行复制到T中的第q行T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;③;//M中第col列下一个非零元在T．data中的位置应增1}}returnOK;}2．后序遍历二叉树非递归算法StatusPostOrderTraverse1(BiTreet,Status(*Visit)(TElemTypee)){//后序遍历二叉树T非递归算法,对每个数据元素调用函数Visit一次且仅一次.BiTreep;SqStackS;inttag;InitStack(S);do{while(t){Push(S,t);④;}p=NULL;//p指向当前结点的前一个已访问的结点tag=1;//设置t的访问标记为已访问过while(!StackEmpty(S)&&tag){t=GetTop(S);//取栈顶元素if(t-rchild==p)//右子树不存在或已被访问,访问之{⑤;//访问根结点Pop(S,p);//退栈p=t;}//p指向已被访问的结点else{t=t-rchild;//t指向右子树tag=0;}//设置未被访问的标记}}while(⑥);returnOK;}四、解答题（共20分）1．（6分）已知模式串p=’cbcaacbcbc’，求出p的next数组值和nextval数组值。j12345678910模式串pcbcaacbcbcNext[j]Nextval[j]2．（6分）已知一组关键字为{21，33，12，40，68，59，25，51}，(1)试依次插入关键字生成一棵3阶的B-树；(2)在生成的3阶B-树中依次删除40和12，画出每一步执行后B-树的状态。3．（8分）试对右图所示的AOE网络，解答下列问题。(1)求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[i]。1①2③3②4④5⑤6⑥VeVl(2)求每个活动的最早开始时间e()和最迟开始时间l()。1,21,33,22,42,53,54,65,6ell-e(3)确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。(4)这个工程最早可能在什么时间结束。五、算法设计题（9分）完成以下算法，对单链表实现就地逆置。voidLinkList_reverse(Linklist&L){//链表的就地逆置;为简化算法,假设表长大于2Linklistp,q,s;p=L-next;q=p-next;s=q-next;p-next=NULL;试题答案及评分标准一、选择题（单选题，每小题3分，共33分）1234567891011BBDBDCCDAAA二、填空题(1~8每空2分，9~12每空1分，共20分）【1】【2】【3】【4】【5】【6】O(n)O(tu+nu)O(nu)(b，c，d)22)!()!2(1111nnnCnnn或14【7】【8】【9】【10】【11】【12】69269快速排序二路归并排序堆排序链式基数排序三、算法填空题(每空3分，共18分）1．①M.data[t].j②num[col-1]③++cpot[col]2．④t=t-lchild⑤Visit(t-data)⑥!StackEmpty(S)四、解答题（共20分）1．(6分)2．(共6分)(1)(2分)3阶B-树为：j12345678910模式串pcbcaacbcbcNext[j]0112112343Nextval[j]0102101040(2)（4分）删除40后B-树的状态删除12后B-树的状态3．(8分)按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l-e=0?来确定关键活动，从而确定关键路径。(1)每个事件的最早开始时间Ve[i]和最迟开始时间Vl[i]①2③3②4④5⑤6⑥Ve01519293843Vl01519373843(2)每个活动的最早开始时间e()和最迟开始时间l()1,21,33,22,42,53,54,65,6e00151919152938l170152719273738l-e1700801280(3)关键活动为：1,3，3,2，2,5，5,6；加速这些活动可使整个工程提前完成；由所有关键活动构成的图：（关键路径为：1,33,22,55,6）(4)此工程最早完成时间为43。五、算法设计题（9分）试写一算法，对单链表实现就地逆置。voidLinkList_reverse(Linklist&L){//链表的就地逆置;为简化算法,假设表长大于2Linklistp,q,s;p=L-next;q=p-next;s=q-next;p-next=NULL;解：while(s-next){q-next=p;p=q;q=s;s=s-next;//把L的元素逐个插入新表表头}13265154195q-next=p;s-next=q;L-next=s;}//LinkList_reverse分析：本算法的思想是,逐个地把L的当前元素q插入新的链表头部，p为新表表头。