《数据结构》模拟试卷二及答案.docx

《《数据结构》模拟试卷二及答案.docx》由会员分享，可在线阅读，更多相关《《数据结构》模拟试卷二及答案.docx（6页珍藏版）》请在优知文库上搜索。

1、模拟试卷二单选题（每题2分，共20分）1 .在一个带有附加表头结点的单链表II1.中,若要向表头插入一个由指斜P指向的结点.则执行（B）.A.H1.=p;pncxt=HI.;B.p-ncxt=H1.-ncxt;HI.-ncxt=p;C.p-next=H1.:p=H1.:D.p-nexl=H1.;H1.=p:2.若依次存储的循环队列的如eueMaxSize=n,则该队列最多可存储（B）个元素.A.nB.n-1C.n+1D.不确定3,下述哪一条是依次存储方式的优点？（CA）A.存储密度大B.插入和删除运算便利C.获得符合某种条件的元素便利I）.查找运算速度快4 .设有一个二维数组ranb假设40存

2、放位置在6（4助，A3113存放位置在678,u）,摊个元素占一个空间，问川23uu,存放在什么位置？（脚注（必表示用IO进制表示,m3）BDA.658B.MSC.633D.6533m+3=78m=255 .下列关于二叉树遍历的叙述中，正确的是（I）A）.若一个树叶是某二叉树的中序遍历的最终一个结点，则它必是该二叉树的前序遍历城终一个结点B.若一个点是某二叉树的前序诩历筑终一个结点,则它必是该二叉树的中序溺历的最终一个结点C.套一个结点是某二叉树的中序遍历的最终一个结点.则它必是该二叉树的前序最终一个结点D,若一个树叶是某二叉树的前序城终一个结点，则它必是该：叉树的中序遍历最终一个结点6 .k

3、层二叉树的结点总数最多为（八）.2k-lB.2K+1C.2K1D.2一7 .对线性表进行二分法查找,其前提条件足（）.A.线性衣以链接方式存储,B.线性衣以依次方式存储,C线性表以依次方式存依,D.线性表以於接方式存Wi.8.对n个记录进行堆排序,并且按关键码怕排好序并旦按关键码伯的检索频率川好序并且按关键码值排好序并且按关械码值的检索颇率排好序所须要的协助存谛空间为.0（log：n）B.0,H.则树中所含的结点数为个树的深度为.相的度为5 .后级算式79230+-42/的值为,中微算式（3+X*Y）-2Y/3对应的后缀算式为.6 .在-探高度为5的志向平衡树中，最少含有个结点，最多含有个结点

4、.7 .在树中，一个结点的干脆后继结点称为该结点的.一个希点的干腌前趋结点称为该结点的.8 .在一个具有IO个顶点的无向完全图中，包含有条边，在一个具有n个顶点的行向完全图中,包含有条边.9 .假定一个线性表为(12.17.74563.49.82.36),若按Kcy%4条件进行划分,使得同余数的元素成为一个子表.则得到的四个子表分别为、和,10 .对一棵B_树进行刑除元素的过程中，若拼终由起树根结点的合并时，会使新树的高度比原树的高度I1.在堆排序的过程中，对任一分支结点进行筛运算的时间困难度为,整个堆排序过程的时间困难度为.12.在线性表的改列存储中，装填因子又称为装填系数，若用m去示散列表

5、的长度，n表示特敌列存储的元素的个数，则a等于,三、 运算题(每题6分，共24分)1 .在如下数组A中鞋接存储/一个线性表,表头指针存放在A().ncxt.试写出该线性表.A0123456760507890341040527132 .己知棵.叉树的前序遍历的结果是ABKCDFGHIJ.中序遍历的结果是KBCDAFHIGJ,试画出这棵：叉树、3.已知一个图的顶点集V为：V=(1.23.4.5.6.7):其共有10条边.该图用如卜边集数组存储：起点终点权122552261364547677751122233457试用克件斯卡尔丁r法依火求出该图的最小生成树中所得到的各条J业及权4 .IDi出向小根

6、堆中加入数据4,2,5,8,3,6,10.1时,每加入一个数据后堆的改变.四、 网读翼法蝴B7分，共14分)1 .在下面的集个程序段中，假定规性表1.a的类型为1.isl,元素类型ElemTyPe为int.并假定每个程序段是连续执行的，试写出每个程序段执行后所得到的戏性表1.a.(1) Init1.ist(1.a)：Inta=(100,26.57,34,79;For(i=0115J)Insert(1.a,a(i):Traverse1.ist(1.a)：(2) DelctvFront(1.a);InsertRea(1.a,DeletePront(1.a);Traverse1.ist(1);(3)

7、 Clear1.ist(1.a);For(i=0;i5;i+)InserlFront(1.a,ai);Traverse1.ist(1.a)：2.现面算法的功能是什么？VOidABC(BTNOde*BT)ifBT(coutdaa;ABCleft);ABC(BT-righ();)1五、 算法填空(共8分)二分查找的速打算法.IntBinsch(Elen)Type,intlow,inthigh,KeyTypeK)(if(intaid=(lo11-high2;if()returnBid;直找胜利,返回元素的下标elseif(KAmid.key)returnBinsch(A,low,mid-i,K);在

8、左子表上接着查找elseretun:在右子表上接着查找)else：有找失败,返回T)六、 写算法(共8分)HI.为尔度上的衣头指针，试写出在该总鞋表中查找具布给定的元素item的算法，boolFind(74.82)63)10. 削减1(或削减)11. O(logzn)0(nlog2n)12. n/m三、运算Ji(每6分，共24分)1 .线性表为：90.40,78.50.34.60)2 .当的序序列为ABKCDFGHU.中序序列为KBCAFHIGJ时,逐步形成：叉树的过程如下图4所示：(1.6)1,(2,4)1,(25)2.(5.7)2.(2.6)3.(3.5)74.见图5。图S四、 闽读算法(

9、每题7分,共14分).1.(I)1.a=26,3457,79Joo)(2) 1.a=(57.79Joo34)(3)1.a=(79.34.57.26.1(X2,前序/历钺式存储的二叉树。五、 算法填空(每空2分,共8分)(lowdata=item)returntrue;elsep=nexnex(=H1.;B,p-next=H1.-next;H1.-next=p;C.p-ncxt=H1.:p=H1.:D.p-ncxt=H1.:H1.=p:12 .若依次存储的循环队列的QUeUeMaXSiZe=n,则该队列最多可存他()个儿，；.A.nB.n-1C.n+1D.不确定13 .下述哪一条是依次存储方式的

10、优点？().存储密度大B.插入和捌除运算便利C.获得符合某种条件的元素便利I).查找运算速度快14 .设有一个渔数祖m(n.偿设A00存放位Jl在6Otho,A3113存放位置在678ll,每个元素占一个空间,问A网(o存放在什么位置？(脚注眄表示用10进制表示.m3)A.658B.648C.633D.65315 .下列关于二叉树遍历的叙述中，正确的是().A.若一个树叶是某二叉树的中序遍历的爆终一个结点，则它必是该：叉树的前序遍历最终一个站点B,若一个点是某二叉树的前序诩历/S终一个结点,则它必是该二叉树的中序遍历的发终一个结点C.若一个结点是某二叉树的中洋遍历的最终一个结点则它必是该二叉树

11、的前序最终一个结点D,若一个树叶是某：叉树的前序坦终一个结点，则它必是该：叉树的中序遍历终一个结点16 .k层二叉椅的结点总数最多为().A.2k-lB.2K+1C.2K-1D.2k117 .对线性表进行二分法查找，其前提条件是().E.线性表以接接方式存Wi,并I1.按关犍码值排好序R线性表以依次方式存储.并1.按关键码值的检索领率排好序G跷性表以依次方式存储，并旦按关键码伯排好序H.线性表以钺接方式存储，并旦按关键码伯的检索频率排好序18 .而n个记录进行堆排序，所须要的协助存佛空间为A.O(log111B.0n)C.0(1)D.0(n2)19 .对于线性表(7.34.77.25.64.49.20.14)进行散列存储时,若选用H(K)=K作为散列函数，则散列地址为0的元素有()个，A.IB.2C.3D.d20 .下列关于数据结构的叙述中，正确的是().E.数纲是不同类型值的集合F,还Uj算法的程序结构比迭代算法的程序结构更为粘煤G.树是一种线性结构H.用一维数组存储一棵完全二叉树是有效的存储方法八、 填空JB(每空I分，共26分)13 .数据的能辑结构被分为、和四种。14 .一个算法的时间困难度为(3+2000Mog2r+90)/,其数量级表示为.15 .对于一个长度为n的单位存储的队列,在表头插入元素的时间困难度为.在