数据结构模拟试题四及答案.pdf

该【数据结构模拟试题四及答案 】是由【小屁孩】上传分享，文档一共【5】页，该文档可以免费在线阅读，需要了解更多关于【数据结构模拟试题四及答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..数据结构模拟试题四一、(共30分,每题2分)[0..m-1]存放其元素值,已知其头尾指针分别为front和rear,则当前元素个数为()A.(rear-front+m)-front+-front--,与所使用的计算机无关的是数据的(),实现()的操作,其算法的时间复杂度都是O(n)。,中序遍历序列为JLKINMO,则后序遍历序列为(),则需存储的元素个数为()**n/(n+1)/“模式匹配”是指()()+(n-1)/(n+1)(n+1)(),已按关键字值额定升序排列,假定对每个元素进行查找的概率是相同的,且每个元素的关键字的值皆不相同。用顺序查找法查找时,平均比较次数约为()(49,38,65,97,76,13,27,50)按由小到大进行排序,()是初始步长d=4的希尔排序法第一趟的结果。,76,65,13,27,50,97,,27,38,49,50,65,76,,76,65,50,49,38,27,,13,27,50,76,38,65,,第一趟排序完毕后,其最大或最小元素一定在其最终位置的算法是(),正确的结论是(),树可能是有序的,,所有顶点的度数之和与图的边数的比是()::::(46,79,56,38,40,84),则利用快速排序的方法,以第一个纪录为基准得到的一次划分结果为(),40,46,56,79,,38,46,79,56,,38,46,56,79,,38,46,84,56,,将数据以()结构存放,则查找一个数据所用时间不依赖于数据个数n。:..二、(共40分,每空2分)(),申请到新结点p,将p指向的结点后插到s所指结点的操作,其一是p->next=s->next,其二是()。()遍历次序相同。[10..20,5..10]按行优先存储,每个元素占4个单元,A[10,5]的地址为160,则A[15,10]的地址为()。()的,非线性结构反映结点间的逻辑关系是()的。()的二叉树。()棵。,第7层有10个叶子结点,则二叉树的总结点数至少是()。,且仅有一个孩子的结点数为30,则总结点数为()。()个结点。()可唯一确定这棵二叉树。设某二叉树的后序遍历为ABKCBPM,则可知该二叉树的根为()。=((x,(a,b)),((x,(a,b)),y)),则C的长度为(),深度为()。,则G采用()存储较省空间。,若初始数据基本正序,则选用();若初始数据基本反序,则选用()。,空指针域有()个;利用这些空指针域,存放指向结点在中序次序下的前趋或后继的指针,这种附加的指针称为()。三、(10分)已知一棵度为m的树中有N1个度为1的结点,N2个度为2的结点,??Nm个度为m的结点,问该树中有多少个叶子结点。请写出推导过程。四、(15分)给定字母a,b,c,d,,,,,。设计以该权值为基础的赫夫曼树,并给出赫夫曼编码。五、(15分)设散列表的长度为13,散列函数为H(K)=K%13,给定的关键字序列为:19,14,23,01,68,20,84,27,55,11,10,79。试画出用线性探测再散列解决冲突时所构成的散列表。并求等概率情况下这种方法查找成功和查找不成功时的平均查找长度。六、(15分)已知奇偶交换排序如下所述:第一趟对序列中所有奇数项i扫描,将a[i]和a[i+1]进行比较;第二趟对序列中所有偶数项i扫描,将a[i]和a[i+1]进行比较。每次比较时若a[i]>a[i+1],则将两者交换。第三趟对所有奇数项,第四趟对所有偶数项??,如此重复,直至整个序列有序。1)写出奇偶交换排序算法,设待排序的n个元素存放在数组a[1..n]中。2)说明你的排序方法的结束条件3)若待排序的初始序列已按关键字从小到大有序,则关键字的比较次数是多少?七、(10分)已知长度为n的线性表A采用顺序存储结构,并且元素按值大小非递减排列,下面的算法删除线性表中多余的值相同的元素。请在算法中空白处填入适当内容,使之能够正常工作。voidDEL(intA[n])//设A[1]~A[n]存放着n个元素{inti=1;while(1)doif(A[i]!=A[i+1])i++;else//查找满足条件的元素{for(2)A[j-1]=A[j];//删除第i+1个元素(满足条件的元素)(3)//修改线性表的长度}}:..八、(15分)设计算法,已知一棵以二叉链表存储的二叉树,root指向根结点,p指向二叉树中任一结点,编写算法求从根结点到p所指结点之间的路径(要求输出该路径上每个结点的数据)。:..数据结构模拟试题四参考答案一、(共30分,每题2分)单项选择题1A2C3A4C5D6D7B8C9C10D11D12D13C14C15D二、(共40分,每空2分)->next=,-,,,+1,线索三、(10分)解:设N为总结点数,N0为叶子结点数则:N=N0+N1+N2+……+Nm又有:N-1=度的总数,则:N-1=N1*1+N2*2+……Nm*m则有:N0=1+N2+2N3+……+(m-1)Nm四、(15分)cdecabc(00)d(01)a(100)b(101)e(11)五、(15分)线性探测再散列的散列表:012345678910111214168275519208479231110121431139113查找成功的平均长度为ASL=1/12(1*6+2*1+3*3+4*1+9)==1/13(1+2+3+4…….+13)=7六(15分)(1):..voidoesort(inta[n]){inti,flag;do{flag=0;for(i=1;i<n;i+=2)//奇数扫描if(a[i]>a[i+1]){flag=1;t=a[i+1];a[i+1]=a[i];a[i]=t;}for(i=2;i<n;i+=2)//偶数扫描if(a[i]>a[i+1]){flag=1;t=a[i+1];a[i+1]=a[i];a[i]=t;}}while(flag);(2)两趟排序无交换出现(3)n-1次}七(10分)(1)i<=n(2)(j=i+1;j<=n;j++)(3)n--八(15分)voidpath(T,p)BintreeT,p;{Bintreestack[max],q;inttag[max],top=0,find=0;q=T;while((q||top)&&find==0){while(q){stack[top]=q;tag[top++]=0;q=q->lchild;}if(top>0){q=stack[top-1];if(tag[top-1]==1){if(q==p){for(i=0;i<top;i++)printf(“%d”,stack[i]->data);find=1;}elsetop--;}if(top>0&&!find){q=q->rchild;tag[top-1]=1;}}}}