期中习题

Page1第一题：填空1.下面函数的时间复杂度是_____O(𝑛)____。intfoo(intn){ints=i=0;while(sn){i++;s+=i;}returns;}设循环了k次停止，即𝑛≤1+2+3+⋯+𝑘=(k+1)×𝑘2=𝑘2+𝑘2∴O(𝑛)Page2第一题：填空2.二叉树的叶结点在前序、中序、后序的遍历序列中的相对次序：___B___。A.都不相同；B.完全相同；C.前序和中序相同，而与后序不同；D.中序和后序相同，而与前序不同。Page3第一题：填空3.对于非空满K叉树，其分支结点的数目为n，则其叶结点的数目为___n(k-1)+1___。∵满K叉树，∴结点度数为0或K。设总结点数为n，度为0的结点数为n0，度为K的结点数为nK，∴n=n0+nK出根节点外，奇遇结点都有一条边进入，设总边数为e，有n=e+1，由于边是度为0或K的结点射出的，∴e=0×n0+K×nK=K×nK∴n=n0+nK=K×nK+1∴n0=nK×(K-1)+1Page4第一题：填空4.在___B,D___中，即使丢失了头结点，只要指出表中任何一个结点的指针，也可以访问到该结点的前驱结点。A．线性单链表B．双向链表C．线性链表D．循环链表线性单链表⊆线性链表Page5第一题：填空5.若森林F对应的二叉树B中有m个结点，B的根结点r的右子树具有n个结点，那么森林F中第1棵树的结点数为___A___。A.m-n；B.m-n-1；C.n+1；D.无法确定。abdecfghiabdecfghi（a）二叉树（b）森林Page6第一题：填空6.给定数据序列为｛a，b，c，d，e，f，g｝的输入流、以及一个空队列，每步可进行以下两种操作：（1）取出输入流的下一个数据、入队列，或（2）一个数据出队列、输出。当输入流和队列均为空时，输出序列不可能是以下哪些序列：___A,B,C,D___。A.{d，e，c，f，b，g，a}B.{f，e，g，d，a，c，b}C.{e，f，d，g，b，c，a}D.{c，d，b，e，f，a，g}Page7第一题：填空7.对一棵完全k叉树，按照广度优先周游顺序给结点从左到右依次连续编号，第一个结点编号为0，则编号m(m≠0)的结点的父结点编号是__⌊𝑚−1𝑘⌋__。（b）完全3叉树012345678Page8第一题：填空8.若一棵二叉搜索树中结点值在1到1000之间，现在要在其中查找值为363的结点。下面序列中___C___不是查找过的序列？A.2,252,401,398,330,344,397,363；B.924,220,911,244,898,258,362,363；C.925,202,911,240,912,245,363；D.2,399,387,219,266,382,381,278,363。925202911240912Page9第一题：填空9.使用重量权衡合并规则与路径压缩，对下列从0到15之间的数的等价对进行归并。在初始情况下，集合中的每个元素分别在独立的等价类中。当两棵树规模同样大时，使结点数值较大的根结点作为值较小的根结点的子结点。(0,2)(1,2)(3,4)(3,1)(3,5)(9,11)(12,14)(3,9)(4,14)(6,7)(8,10)(8,7)(7,0)(10,15)(10,13)请填写下面表格的空白部分树的父指针表示法的数组表示。也就是所有等价对都被处理之后，所得父结点的下标值（没有父结点则填“–1”）。Page10第一题：填空9.(0,2)(1,2)(3,4)(3,1)(3,5)(9,11)(12,14)(3,9)(4,14)(6,7)(8,10)(8,7)(7,0)(10,15)(10,13)小树并入大树、更新父节点Page11第一题：填空10.使用栈计算逆波兰表达式（操作数均为一位数）12+4*5+3−，当处理到完数字5时，栈的内容（以栈底到栈顶从左往右的顺序书写）为___12,5___。Page12第二题：辨析与简答1.序列23,17,14,6,13,10,1,5,8,12是否为一个最大值堆？若是，请说明理由，否则请严格按照筛选法建堆的过程将其调整成为最大值堆，并画出调整建堆的逐步过程。答案：否。结点6比右儿子8要小，所在子树不满足最大值堆的性质。调整过程：从结点13开始从右往左执行一系列sift-down操作，用虚线或其他方法标出比较操作，在结点6需要与结点8交换。Page13第二题：辨析与简答调整过程：从结点13开始从右往左执行一系列sift-down操作，用虚线或其他方法标出比较操作，在结点6需要与结点8交换。131268141017132317Page14第二题：辨析与简答2.已知某电文中共出现了10种不同的字母（A,B,C,D,E,F,G,H,I,J），每种字母出现的次数分别为6、8、5、3、7、22、10、9、1、40，现在对这段电文用三进制进行非定长前缀编码（码字由0、1、2组成），问电文编码总长度至少有多少位？请画出相应编码方案的图示。答案：构造满三叉哈夫曼树来实现最优的非定长前缀编码。因为满三叉树有奇数个叶结点，需要添加出现0次数的哑字符使其成为满三叉树。使用哈夫曼算法构造满三叉哈夫曼树((((D,I,ε),A,C),G,F),(B,E,H),J)，得到电文编码总长度至少4*3+4*1+3*6+3*5+2*10+2*22+2*8+2*7+2*9+1*40=201位三进制码。Page15第二题：辨析与简答3.以下是计算模式P的next向量的算法（1）请在空缺处填写相应的语句，使得算法完整；int*findNext(stringP){inti=0;k=-1;intm=P.length();int*next=newint[m];next[0]=-1;while(im){while(k=0&&P[i]!=P[k])k=next[k];i++;k++;if(i==m)break;}returnnext;}if(P[i]==P[k])next[i]=next[k];elsenext[i]=k;Page16第二题：辨析与简答（2）采用上述算法，计算模式P=“abcdaabcab”的next向量。i0123456789Piabcdaabcabnext[i]-1000-110030Page17第三题：算法填空1.完成非递归的二叉树搜索算法，给定一个二叉树（不是BST）和一个值K，如果K出现在二叉树中则返回true，否则返回false。templateclassTstructBinaryTreeNode{Tvalue();BinaryTreeNodeT*leftchild();BinaryTreeNodeT*rightchild();};templateclassTboolsearch(BinaryTreeNodeT*root,Tk){usingstd::stack;stackBinaryTreeNodeT*aStack;BinaryTreeNodeT*pointer=root;while(pointer!=NULL||aStack.empty()==false){if(pointer){aStack.push(pointer)pointer=pointer-leftchild();}else{pointer=aStack.top();if(pointer-value()==k)returntrue;pointer=pointer-rightchild();aStack.pop();}}returnfalse;}Page18第三题：算法填空2.下面的算法将一个用带度数的后根次序法表示的森林转换为左子结点/右兄弟结点法表示。请利用题目给出的树结点ADT和栈ADT，填充算法的空格，使其成为完整的算法。空格中可能需要填写0到多条语句（或表达式）。回顾北京大学信息科学技术学院数据结构与算法196.3.3带度数的后根次序表示法结点按后根次序顺序存储在一片连续的存储单元中，结点的形式为其中info是结点的数据，degree是结点的度数这种表示法不包括指针，但它仍能反映树结构若某结点的degree值为m，则该结点有m个子结点最右的子结点就是后根次序序列中该结点的前驱最后第二个子结点是以最右子结点为根的子树在后根次序序列中的前驱…。北京大学信息科学技术学院数据结构与算法换一种思路将带度数的后根次序表示转化成森林时只需要从左至右进行扫描，度数为零的结点是叶子结点（也可看作一棵子树）；当遇到度数非零（设为k）的结点时，则排在该结点之前且离它最近的k个子树的根就是该结点的k个子结点。利用栈实现。讨论带度数的先根次序？带度数的层次次序？20北京大学信息科学技术学院数据结构与算法示例infoCXFGJEKHID3000030002degreeFCGDXIEKHJKHJEFGCXIDPage22第三题：算法填空2.下面的算法将一个用带度数的后根次序法表示的森林转换为左子结点/右兄弟结点法表示。请利用题目给出的树结点ADT和栈ADT，填充算法的空格，使其成为完整的算法。空格中可能需要填写0到多条语句（或表达式）。templateclassvalue_typeclassstack{public:boolempty();//判断栈空intsize();//返回栈大小value_type&top();//读栈顶voidpush(constvalue_type&X);//入栈voidpop();//出栈};structNodeT{Tinfo//结点的数据信息intdegree//结点的度数信息};templateclassT//树结点类classTreeNode{public:boolisLeaf();//判断当前结点是否为叶结点TValue();//返回结点的值TreeNodeT*LeftMostChild();//返回第一个左孩子TreeNodeT*RightSibling();//返回右兄弟voidsetValue(constT&);//设置当前结点的值voidsetChild(TreeNodeT*pointer);//设置左孩子voidsetSibling(TreeNodeT*pointer);//设置右兄弟};TreeNodeT*Convert(Node*nodes,intsize){TreeNodeT*cur,*temp1,*temp2;stackTreeNodeT*Cstack;for(inti=0;isize;i++){cur=newTreeNodeT(nodes[i].info);if(nodes[i].degree==0)Cstack.push(cur)else{assert(nodes[i].degree=Cstack.size());temp2=NULL;for(intj=0;jnodes[i].degree();j++){temp1=Cstack.top();Cstack.pop();temp1-setSibling(temp2);temp2=temp1;}cur-setChild(temp2);或cur-setChild(temp1);Cstack.push(cur);}}cur=temp2=NULL;while(!Cstack.empty()){cur=Cstack.top();Cstack.pop();cur-setSibling(temp2)temp2=cur;}returncur;}Page23第四题：算法设计与实现注意：（1）对算法设计有质量要求，请尽量要求写出高效算法（做算法分析，否则将酌情扣分）；（2）请申明所写算法的基本思想，并在算法段（C++伪代码）加以恰当的注释。Page24第四题：算法设计与实现1.设计算法来判断一