数据结构期末试
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
及
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
计算机科学与技术、网络工程本科《数据结构》期末考试试卷一、选择题（单选题，每小题3分，共33分）1．已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为。A．BCDEAFB．ABDCEFC．DBACEFD．DABECF2．在11个元素的有序表A[1…11]中进行折半查找（），查找元素A[11]时，被比较的元素的下标依次是。A．6，8，10，11B．6，9，10，11C．6，7，9，11D．6，8，9，113．由元素序列（27，16，75，38，51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为2的结点）为。A．27B．38C．51D．754．利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素30要进行次元素间的比较。A．4B．5C．6D．75．循环链表的主要优点是。A．不再需要头指针了B．已知某个结点的位置后，很容易找到它的直接前驱结点C．在进行删除后，能保证链表不断开D．从表中任一结点出发都能遍历整个链表6．已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key）=key%7计算散列地址，并散列存储在散列表A[0…6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率查找时查找成功的平均查找长度为。A．1．5B．1．7C．2．0D．2．37．由权值为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为。A．23B．37C．44D．468．在最好和最坏情况下的时间复杂度均为O（nlogn）且稳定的排序方法是。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．aebdcfB．abedfcC．aedfcbD．acfdeb10．置换-选择排序的功能是。A．产生初始归并段B．选出最大的元素C．产生有序文件D．置换某个记录11．ISAM和VSAM文件属于。A．索引顺序文件B．索引非顺序文件C．顺序文件D．散列文件二、填空题(1~8每空2分，9~12每空1分，共20分）1．下面程序段的时间复杂度为【1】。Sum=1;For(i=0;sum
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,2><1,3><3,2><2,4><2,5><3,5><4,6><5,6>ell-e(3)确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。(4)这个工程最早可能在什么时间结束。五、算法
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
题（9分）完成以下算法，对单链表实现就地逆置。voidLinkList_reverse(Linklist&L){//链表的就地逆置;为简化算法,假设表长大于2Linklistp,q,s;p=L->next;q=p->next;s=q->next;p->next=NULL;试题答案及评分
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
一、选择题（单选题，每小题3分，共33分）1234567891011BBDBDCCDAAA二、填空题(1~8每空2分，9~12每空1分，共20分）【1】【2】【3】【4】【5】【6】O()O(tu+nu)O(nu)(b，c，d)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分)j12345678910模式串pcbcaacbcbcNext[j]0112112343Nextval[j]01021010402．(共6分)(1)(2分)3阶B-树为：(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,2><1,3><3,2><2,4><2,5><3,5><4,6><5,6>e00151919152938l170152719273738l-e1700801280(3)关键活动为：<1,3>，<3,2>，<2,5>，<5,6>；加速这些活动可使整个工程提前完成；由所有关键活动构成的图：（关键路径为：<1,3><3,2><2,5><5,6>）13265154195(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的元素逐个插入新表表头}q->next=p;s->next=q;L->next=s;}//LinkList_reverse分析：本算法的思想是,逐个地把L的当前元素q插入新的链表头部，p为新表表头。
浙公网安备 33021202002483