2019年04月自学考试02331《数据结构》试题和答案.docx

《2019年04月自学考试02331《数据结构》试题和答案.docx》由会员分享，可在线阅读，更多相关《2019年04月自学考试02331《数据结构》试题和答案.docx（13页珍藏版）》请在优知文库上搜索。

1、施击启用前2019年4月高等教育自学考试全国统一命题考试数据结构(课程代码02331)注意事项：1 .本试卷分为两部分,第一部分为选探源，第二部分为非送理现.2 .应考者必须按试近眼序在答姮卡()指定位H上作答，答在试卷上无效.3 .涂BiS分、通图部分必须使用2BU1笔，书写部分必须使用黑色字遗着字笔.第一部分选择题单IS选经Hh本大题共15小JS,毋小JS2分.共30分.在督小Ii列出的备选项卬只育一项是最符合短目要求的.请将其选出.1 .线性货是一朴由“个数网元京组成的数雄结构的取值是A.。或者任彦一个正整数或8B.4T5ttC.任总一个正毕数或赤-D.某个正整数2 .在一个力发中.已知

2、q所抵结点是P所指络的小维”点？；P和q之间扬入S所指结点,则正确的探作是A. s-ncxlp-11ext;pncxtSB. sneMq;pncxt-s-ncxt;C.q-ncxtHs;s11cxlp;D.P、4tS;Ancxt-p;3 .下列法项中,小N通过收求薪的豺咫足A.用Bi字符印是否是同文B.仁英围括弓是否内配C.不同数翻之间进行”换D.图的广度优先强*遍历4 .设栈S的除入在列为1.Z3.4$则下列选项中不可能是S的输出序列的是A.2.3.4.1.5B.5.4,3.2C.2.3.,5D.1.5.43.2$,使用一个人小为6的数组保存循环队列Q.若从Q中出队两个几东.并人队一个兀.此

3、0从几rear和从头from的值分别为2和心则在执行这三个捺作之前和from的值分别比A,。和3BI和2C.2和50-4*,57.2.l-试d第I爽（共。贞）6.设二雄数IaM盯3行4列,投行优先的方式存储.得个元素占6个存他单元.第1个元京的存隹地址为100.则MRM2）的存10址为A.135B.1S3C.160D.1657 .设”阶方牌M是对冰能防.如SEE缩存1方式将M中的元京保存在一敷IaB中.剜下列逸项中,正确的是A.保0M中的主用启线中的元京.B的元It个数是”B保存M中上三角部分的元素.B的元索个数是Mt-Iy2C.保存M中上三角部分的元累.B的元京个数是D.保存M中的全那元K.

4、B的元素个数是/8 .已知完全二叉轲T的第4层有S个计结点.则T的结点个数Ja多是A.12B.20C.21D.369 .在一株It空二叉树的后序通历序列中.所有列在懵铝点Il面的ItA.左子树中的孤分结点B.右于树中的全部结点C.左右于树中的部分结点D.左右于树中的全都特点10 .若对HIO图所示的无向!B进行谭及优先It*遍历剜下列选二中正的历序列A.Kc.a.b.d.e.g.fb,f8bhcdC.d.b.c,a.h.e.f.gd.b.c.d.h.c,f.g对HIl图所示的有向用遂行拓扑痔序下外选项中就第和到的拓扑序列是A.3.1.2.45.6B.3.I,2.46.SC.3.1,42,5.6

5、D3.1.4.2.6.S已如豉搦序列（8,9.10.4.5.6.20.1.2）足某总所律法第一*8缚祗由则的结“JMii算法可能是a,通簿Il序B.Hifit9fTc.H接婚入揖序D.快速。样JS据结构试电第2页（共9页）n.下列选4中,每一M都能送出一个元,故在Kie终上.H不注定的fl*D,EJA.HtMlfB.合尔第序C.归弁1序D.快泳“序14.对物序&(1.9.12.41.62.，,82.95.100)是用二分。找方雄出找值矣.”假匚拄中关0字的比收次Ik必A.IB.2C.4D.7IS.将下列政据依次如入到初始为空的二叉搏件树中.母的料厦金小曾二ZJIf?”为序列是A.2.47.5.

6、8.10B.5.126,3.4C.6.4.1.8.10.5D,9.7.2,1.4,0tM.构求0634!（）第二部分非选择题二填空题：本大题共0小降印卜题2分，共20分.,6线性表的存储方式中,施够随机存取友中任一元素的存体结构是.,7用S表示入校操作X表示出枝接作,若元素入栈限序为12M.为了树刎1“2的出杈顺序相应的S.X-作耶为.18 .若广义表1.的深度是8,则1.一定足.19 .广义表(ab),(c,d),e)的衣足是.20 .利用二叉树中的空指计域.使之指向结点在某肿遍历次序下的前启或后缰结点,此时域中的内容称为.21 .若用“个偌权字符构造哈夫曼树T.则T中结点的总数是.22 .

7、设连通僭权图G中科”个顶点,使用普里阈Jl法构造G的餐小生成树T.T中含在的边数是.23 .要使”个记录的关Ct字序列M.&.,及成为小根堆美Ut字之间必续濡足的关系24 .索引顺序近找是一肿将顺序查找和二分查找思想结合在一闻的套找方法又杉为.25 .5阶BI4T中,除根结点之外卷个结京中所含美俄字个St最少是三、解答题：本大题共4小瓢,每小题5分，共20分.26设布藐矩即M如下所示矩防的行列F标均从I开始WJAi出M技打优尢”1的三元组表07-50A.M.O.1.N.请商出T107902331(通卡)2t已知“向带权图G如咫28图所示.请回答下列包心.妗出图G的旬报跄冷.jH(kcy)-kc

8、y%I!.将关田字依次放入表长为“的败列&H中.家用线慢找别”.处理;*夬.请回？卜列同腹.(I)否出构通的Itt列表,并M出位找好个关Ct字的仅点次C1.求数列我的平均自找长度AS1.lmE3.H法阅读期；本大!共4小I1.W小骏$分共20分)0.收序及类5?定义如下，define1.hlSiM100ty-pedefstruct(imdataIJSuc;Hlength；Seq1.nt;该下列0法MHffHX8.voidtnywtn(SckM,for(k0;khukdto(kl)SIJd*u(M-S1.2-faukhCBCSl2bu(k-S1.I-ukj.return;、“;”，/“BiIK结

9、构浸U*5允void(Scq1.istS1.I,Scq1.istS1.2)if(S1.I-lengjhS1.2-length)mysum(S1.I1S1.2);elsemysum(S1.2.S1.I);return；(I)若S1.Idata中的数据为(52,14256.-9,-38.30,128257,64).S1.2data中的数笈(32,I4,53,159,51,16,8).则执行打法00(S1.I.S1.2)S1.I-XiiU和S1.2data中的数%各是什么？lchild);rhigh=hcight(Prchild);if(highrhigh)returnIhighI;elseretu

10、rnrhigh*I；IidOI(BinTrecT)irtIcftHigh-O.rigH*,01BinTrcctemp；if(U=NU1.1.)return；收据绍构试期第6页(共9页)ckcif(beight(llduld)rchi!d)(temp三Tlchild;l-khild-Trchi!d;T-rchild-temp;)OI(Tchild);OI(T-rchili);return;)设二叉树TJH31EB所示.画出执行BIEg得到的二叉轲Tl.(2)蛉出函数。1()的功怆.32.改履序表的存储欠Z定义如下，HdeGne1.BtSize100typedefi11tKeyTyPe;Iyped

11、cfst11ct(KeyiyPCkey;NodcTypc;自考料目包过oq15O273357typcdcfNodclypcScq1.isi(1.istSizc);由数B2()的功能是在于二分点找在长度为的有序表R中插入-个关设字X,并保持R的乔序性.请在空白处境上适当通句使Jt法正确.void02(Scq1.istR.KeyTypetn)(intlow-0.highn-.mid,impacc.i,find-0;whik(low-high&.!find)mid-(low+highX2;if(xRImidkey)low-mid；I;eicfind-;)if(lnd)inspe-一(2):eke11

12、sp3ce三low;(i三K()：i)RU+1】即；R(insccl.kcyx;33设超序衣的存储员里定义如下typedcfintKcyTypc.tyedefstruct(KcyTypckey;)RccTypc;阅读下列我法.井阿谷何蜀.int03(RccTypeR(.inti.intj)(RccTypcX-R(i;Whiledvj)(while(iVj&即RCy-x.key)j-；if(iJ)(R(ikcyIWhik(iVj&RbikcyV-XlWy)if;if(ij11RUiF-RWyj-;)Rli1.kCy-xky；returni;(!)设ReCWRIZS2.M.256.9.383O2825SM绐出执忏伙R0A；R的结果(2)给出速0法的功能致帆靖构试N6i贯9页)五、Jt法设计晚：本JKIO分.34.已如二文树的存储结构英型定义如下:IyPCdCfstructnodeintdata;structnodelchild,rehild;BinNode;typcdcfBinNodcBinTrec;编写递归算法,对于培定的一株二叉树T计算并迂回所有结人匕口法的以之和的数原里为：HfM(BinTET);.例如，对于H乂田所示的二T04(T)3返回24.数据姑构上