《南邮数据结构B期末试卷1.pdf》由会员分享,可在线阅读,更多相关《南邮数据结构B期末试卷1.pdf(4页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数数题号题号分数分数一一据据 结结 构构 B B期末试卷期末试卷二二三三四四五五六六班级班级学号学号姓名姓名得分得分一、解答题:(共 82 分)1、下列程序段或函数的时间复杂度。(10)(1)for(int k=0;km;k+)(2)int fac(unsigned int n)for(int j=0;jn;j+)if(n=0|n=1)return 1;akj=k*j;else return nfac(n-1);(3)int Prime(int n)(4)k=1;x=0;int k=2,x=(int)sqrt(n);do while(kP2,P1P3,P1P4,P2P3,P2P5,P3P6,P
2、4P6,P5P6。其中符号“”表示先于关系,例如 P1P2 表示只有在工程 P1 完成之后才能进行 P2 的工作。请:(7%)(1)画出该工程的 AOV 网(2)给出工程 P 的其中四种可能的施工顺序.8、按如下关键字序列(60,88,107,15,8,23,100)从空树开始建立一棵 AVL 搜索树,画出建树的步骤以及调整平衡的过程(6%)9、设散列表 ht13,散列函数 h(key)=key 13。采用二次探查法解决冲突,试用关键字值序列:56,78,14,27,41,70,51,66,24,50,36建立散列表。(6%)i0123456789101112hti10、元素序列:55,71,
3、12,98,4,70,51 ,请写出用冒泡排序法和 2 路合并排序法进行排序的各趟排序结果。(6%)冒泡排序法冒泡排序法2 2 路合并排序法路合并排序法二、算法填空:(8%)以下算法实现二叉搜索树的删除,根据给定的关键字k,找到待删除元素后将元素值通过参数e返回,若成功删除则返回 true;找不到待删除元素则返回 false。templateclass E,class K_BSTreeE,K::Delete(constK&k,E e)BTNodeE*p=root,*q=0;while(p p-element!=k)2q=p;if(kelement)p=plchild;else_;if(!p)c
4、errlchild prchild)BTNodeE*s=prchild,r=p;while(s-lchild)_;s=s-lchild;_;p=s;q=r;BTNodeE*c;if(plchild)c=plchild;else_;if(_)root=c;else if(p=qlchild)q-lchild=c;else q-rchild=c;_;return true;三、算法设计(10%)编程实现将两个按元素递增排序的单向循环链表合并成一个单向循环链表,合并后元素仍递增有序,注意:不允许再增加新的结点,相同元素只保留一份。该算法为SingleList 类的成员函数 Merge,该函数的作用是
5、将形参 r 代表的单向循环链表合并到当前单向循环链表中,合并后的结果存于当前单循环链表。template class T class SingleList;template class Tclass Nodeprivate:T data;Nodeclass SingleList:public LinearListTpublic:void Merge(constSingleListT r);。private:NodeT first;。;例:合并前:thisfirst-r.first-234108合并后:thisfirst22378r.first算法实现:template class T2233478108void SingleListT:Merge(constSingleListT r)4