2010年《数据结构》期终考试试卷(A)-清华大学

2010年《数据结构》期终考试试卷（A）班级学号姓名一、简答题（每小题6分，共30分）(1)假设一个线性链表的类名为linkedList，链表结点的类名为ListNode，它包含两个数据成员data和link。data存储该结点的数据，link是链接指针。下面给定一段递归打印一个链表中所有结点中数据的算法：voidPrintList(ListNode*L){if(L!=NULL){coutL-dataendl;PrintList(L-link);}}试问此程序在什么情况下不实用？给出具体修改后的可实用的程序？(1)此程序在内存容量不足时不适用。因为需要一个递归工作栈。当链表越长，递归工作栈的深度越深，需要的存储越多。可采用非递归算法节省存储。voidPrintList(ListNode*L){while(L!=NULL){coutL-dataendl;L=L-link;}}(2)如果每个结点占用2个磁盘块因而需要2次磁盘访问才能实现读写，那么在一棵有n个关键码的2m阶B树中，每次搜索需要的最大磁盘访问次数是多少？(2)在2m阶B树中关键码个数n与B树高度h之间的关系为h≤logm((n+1)/2)+1，那么每次搜索最大磁盘访问次数为2hmax=2logm((n+1)/2)+2。(3)给定一棵保存有n个关键码的m阶B树。从某一非叶结点中删除一个关键码需要的最大磁盘访问次数是多少？(3)在m阶B树中关键码个数n与B树最大高度h的关系为h=logm/2((n+1)/2)+1。若设寻找被删关键码所在非叶结点读盘次数为h’，被删关键码是结点中的ki，则从该结点的pi出发沿最左链到叶结点的读盘次数为h-h’。当把问题转化为删除叶结点的k0时，可能会引起结点的调整或合并。极端情况是从叶结点到根结点的路径上所有结点都要调整，除根结点外每一层读入1个兄弟结点，写出2个结点，根结点写出1个结点，假设内存有足够空间，搜索时读入的盘块仍然保存在内存，则结点调整时共读写盘3(h-1)+1。总共的磁盘访问次数为h’+(h-h’)+3(h-1)+1=4h-2=4(logm/2((n+1)/2)+1)-2==4logm/2((n+1)/2)+2(4)给定一个有n个数据元素的序列，各元素的值随机分布。若要将该序列的数据调整成为一个堆，那么需要执行的数据比较次数最多是多少？(4)设堆的高度为h=log2(n+1)，当每次调用siftDown算法时都要从子树的根结点调整到叶结点，假设某子树的根在第i层（1≤i≤h-1），第h层的叶结点不参加比较。从子树根结点到叶结点需要比较h-i层，每层需要2次比较：横向在两个子女里选一个，再纵向做父子结点的比较。因此，在堆中总的比较次数为)ihj(2j22j222j22)ih(221h1jj1-h1h1jj-1h1h1j1-j-h1h1i1-i代换因为2h-1≤n≤2h-1，且1h1jjh22jlim，则n42n22j221h1jj1h(5)设有两个分别有n个数据元素的有序表，现要对它们进行两路归并，生成一个有2n个数据元素的有序表。试问最大数据比较次数是多少？最少数据比较次数是多少？(5)两个长度为n的有序表，当其中一个有序表的数据全部都小于另一个有序表的数据时，关键码的比较次数达到最小（=n）。而当两个有序表的数据交错排列时，关键码的比较次数达到最大（=2n-1）。二、简作题（每小题5分，共15分）针对如下的带权无向图其中，每条边上所注的ei为该边的编号，冒号后面是该边所对应的权值。(1)使用Prim算法，从顶点A出发求出上图的最小生成树。要求给出生成树构造过程中依次选择出来的边的序列（用边的编号表示），权值相等时编号小的边优先。（不必画图）(2)使用Kruskal算法求出上图的最小生成树。要求给出生成树构造过程中依次选择出来的边的序列（用边的编号表示），权值相等时编号小的边优先。（不必画图）(3)上面求出的最小生成树是唯一的吗？试举理由说明。(1)使用Prim算法(2)e1e5e9e7e11e15e13e2e17321232147EFGABCHIJDe2:4e3:4e8:4e4:5e6:6e12:6e17:7e19:8e10:10e14:11e18:11e1:3e11:3e16:3e7:2e15:2e5:2e9:1e13:1EFGABCHIJDe4:5e2:4e3:4e8:4e6:6e12:6e17:7e19:8e10:10e14:11e18:11e1:3e11:3e16:3e7:2e15:2e5:2e9:1e13:1(2)使用Kruskal算法e9e13e5e7e15e1e11e2e17112223347(3)这样选取的最小生成树是唯一的。因为在边上的权值相等时先选编号小的，限定了选择的机会。假如不限定在具有相等权值的边中的选择次序，结果可能就可能不唯一了。三、简作题（共10分）假设一个散列表中已装入100个表项并采用线性探查法解决冲突，要求搜索到表中已有表项时的平均搜索次数不超过4，插入表中没有的表项时找到插入位置的平均探查次数不超过50.5。请根据上述要求确定散列表的容量，并用除留余数法设计相应的散列函数。21112111121nnUS三、简作题（共10分）5.5011121,4111212nnUS由前一式得到76，由后一式得到109，综合得76因n=100，有76100m，67.1166700m,EFGABCHIJDe4:5e2:4e3:4e8:4e6:6e12:6e17:7e19:8e10:10e14:11e18:11e1:3e11:3e16:3e7:2e15:2e5:2e9:1e13:1可取m=117。用除留余数法设计散列函数：Hash(key)=key%113(注：117不是质数，117=9*13)四、算法设计题（每小题5分，共15分）设中序线索化二叉树的类声明如下：templateclassTypestructThreadNode{//中序线索化二叉树的结点类intleftThread,rightThread;//线索标志ThreadNodeType*leftChild,*rightChild;//线索或子女指针Typedata;//结点中所包含的数据};templateclassTypeclassinOrderThreadTree{//中序线索化二叉树类public:ThreadNodeType*getRoot(){returnroot;}//其他公共成员函数……private:ThreadNodeType*root;//树的根指针};试依据上述类声明，分别编写下面的函数。(1)ThreadNodeType*getPreorderFirst(ThreadNodeType*p);//寻找以p为根指针的中序线索化二叉树在前序下的第一个结点。(2)ThreadNodeType*getPreorderNext(ThreadNodeType*p)//寻找结点*p的在中序线索化二叉树中前序下的后继结点。(3)voidpreorder(inOrderThreadTreeType&T);//应用以上两个操作，在中序线索化二叉树上做前序遍历。四、算法设计题（每小题5分，共15分）(1)tamplateclassTypeThreadNodeType*getPreorderFirst(ThreadNodeType*p){returnp;}(2)templateclassTypeThreadNodeType*getPreorderNext(ThreadNodeType*p){if(p-leftThread==0)returnp-leftChild;if(p-rightThread==0)returnp-rightChild;while(p-rightThread!=0&&p-rightChild!=NULL)p=p-rightChild;returnp-rightChild;}(3)templateclassTypevoidpreorder(inOrderThreadTreeType&T){ThreadNodeType*p=getRoot();p=getPreorderFirst(p);while(p!=NULL){coutp-dataendl;p=getPreorderNext(p);}}五、算法分析题（每小题5分，共15分）下面给出一个排序算法，其中n是数组A[]中元素总数。templateclassTypevoidunknown(Typea[],intn){intd=1,j;while(dn/3)d=3*d+1;while(d0){for(inti=d;in;i++){Typetemp=a[i];j=i;while(j=d&&a[j-d]temp){a[j]=a[j-d];j-=d;}a[j]=temp;}d/=3;}}(1)阅读此算法，说明它的功能。(2)对于下面给出的整数数组，追踪第一趟while(d0)内的每次for循环结束时数组中数据的变化。（为清楚起见，本次循环未涉及的不移动的数据可以不写出，每行仅写出一个for循环的变化）(3)以上各次循环的数据移动次数分别是多少。五、算法分析题（每小题5分，共15分）(1)希尔排序(2)第一趟while循环内各for循环结束时数组中数据的变化：步a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]移动次数7744996633558822441113377324455238899342266354477361144554(3)各趟数据移动次数见表的最右一栏。六、算法设计题（每小题5分，共15分）下面是队列和栈的类声明：templateclassTypeclassqueue{public:queue();//队列的构造函数queue(constqueue&qu);//队列的复制构造函数queue&operator=(constqueue&qu);//赋值操作boolisEmpty();//判断队列空否，=1为空,=0不空Type&getFront();//返回队头元素的值voidpush(constType&item);//将新元素插入到队列的队尾voidpop();//从队列的队头删除元素//……//其他成员函数}templateclassTypeclassstack{public:stack();//栈的构造函数boolisEmpty();//判断栈空否。=1栈空，=0不空voidpush(conststack&item);//将新元素进栈voidpop();//栈顶元素退栈Type&getTop();//返回栈顶元素的值}试利用栈和队列的成员函数，编写以下针对队列的函数的实现代码（要求非递归实现）。(1)“逆转”函数templateclassTypevoidreverse(queueType&Q);（5分）(2)“判等”函数boolqueue::operator==(constqueue&Q);（5分）(3)“清空”函数voidqueue::clear();（5分）六、算法设计题（每小题5分，共15分）(1)#include“stack”templateclassTypevoidreverse(queueType&Q){//普通函数stackTypeS;Typetmp;while(!Q.isEmpty()){tmp=Q.getFront();Q.Pop();S.Push(tmp);}while(!S.isEmpty()){tmp=S.getTop(