西安电子科技大学期末数据结构试题及详细答案.docx
MMWK(一)一、单烧算,(«2分.共2。分)I.栈和队列的共同特点赴<).A.只允iT在端点处插入和SH除元素B就是先遇后出C.都是先篷先出D.没有共同点在进行插入运卯时().B.头.足指计都要修改I).头、足指舒可能部空修改2 .用斑接方式存储的队列.A.仅能改头指针C.仅能改其指的3 .以下数幅结构中哪一个是作规性结构？()A.队列B.IftC.统性表D.二叉树4 .设有一下二维故组川川在假设Amm)I存放位置在644即A存放位就在676,M每个兀素占一个空间.问43113um存放在什么位置？脚im衣示用10进制衣示.A.688B.67XC.692D.6%5 .柯依适合用来去示().A.有序数据元素B.无序数据元素C元素之间具有分支限次关乐的数据D.元茶之间无联系的数据6 .二叉树的第k层的站点数很多为().A.2-1B.2K÷lC.2K-1D.2*'7 .假设有18个元个元有序有存放在一在一fiA19H>.第一个元素故AU)中.现进行二分JS找.那么杳设A3的比拟序列的下标依次为(>A.1.2.3B.9,5.2.3C.9.5.3D.9.4.2.38 .对n个记录的文件进行快速扑汴,所需要的i助存储勺间大效为A.0(1)B.0(n)C.0(IOWI)D.0(n2)9 .对J线性表(7.34.55.25,64,46.20.10)进行依列存俅时.钱设选用H(K)=K*9作为散列函数.那么Ift列堆址为I的元素白()个，.IB.2C.3I),410 .他有6个结点,的无向图,该图至少向石()条边才俊痛恨是一个连通图，A.5B.6C.7D.8二、9LSM(空I分，共加分)I.通常从四个方面评价算法的版眼：.和.2.一个算法的时间亚杂度为<+Mk>gyt+l4,"H.共徽旧级衣示为.3.假定棵树的广义表表示为A(C.D(E,F.GJ.H(1.J).那么树中所含的玷点数为个.树的深度为利的度为4 .后皴算式923+IO2/-的4ft为.中级算式(升4X)-2Y/3对应的后绥葬式为5 .假设用械衣在找-W:叉树时，每个结点除数据域外,汪有指向左孩子和右孩子的两个指针花这种存储结构中，n个结点的二叉树共有个指针域.共中方个指笆域是存放了地址，布个指针是空指针.6 .对丁个耳仃n个顶点和e条边的行向图和无向图.在耳对质的翎接表中.所含边结点分别有个和个.7 .AoV网是一种的图.8 .在一个具有n个顶点的无向完全图中，包含有条边，在一个具有n个顶点的有向完全图中，包含有条边.9 .假定个线性我为U223.745S.63.4O).假设按Key%4条件进行划分.依得问余敏的元率成为一个了表,那么掰到的四个子表分别为、和10 .向一株BJ插入元素的过悭中，粗收城终弓I起树根结点的分裂，郡么新树比豪村的Ift境.11 .在堆持序的过程中，对任一分支结点进行筛运算的时间红杂懂为.整个地排序过程的时间复杂度为U.在快速扑序、Jfttmr.归并排序中.井序是杨定的.三、ttHV(«16分，共24分)1.在如下数SiA中故接存储-一个线性表.友头指针为A3next.成写出该线性表.和邻接衣.3 .一个图的顶点集V和边柒E分期为,V=1,2.3,4.5.,7：E=(l.2)3.<1.3)5,(1.-1)8.(2,5)l0.(2.3)6.(3.4)15.(3.(5) 12.(3.6)9,(<J,6)4.(4,7)20,(6,6)18.(6,7)25：用克白斯卡尔第法Jyfl蚊小生成利，试写出在M、生成树中依次得到的各条边.4 .血出向小眼堆中叁加数据4.2.5.8.3时，可也加一个效据后好的变化四、园模筌法(每7分.共14分)1. LinkluMnynle(LinkluM1.)(L是不用头结点的的链表的头折针if(LAL->ncxc)q=L:L=LXicxtcP=LiShWhiklp->ncM)p=p>ncxuS2sp>nct=q:q>ncx=NULL:)returnLt>诱咎亚以下向IS：(I；说明语句Sl的功使：说明语句级S2的功h13；设蓝衣衣示的卷性衣为(Jhq出嫁法执行后的iM的所发示的线性衣.2.UmIABC(BTNmk*BT)(ifBTABC(BT->lcft);ABC(BT->rijhl);«l<<BT><bla<<<该算法的功能是：五、算法*6(共X分)二叉搜索椅的育找一道打就法：boolFind(BTreeNode*BSItEkxnlypefciiE)(if(BSr=MJU.)returnfnlsc;爽我失败else(if<it(?«F=BST->datH)iIEFBSl-Maui：有技成功return;elseif<in<BS,T->data)returnFind(9iten);elsereturnFind(vitem);)if六、百年法(共X分)统计出呦表HL中结点的法等FffiX的结点数.intC<JU11tX(LNodc*HI.,ElrnjTypcx)一、途舞题(24分)1 .下面关于找性表的表达常识的选项是().（八）战性表乘用顺序存储翅占用一片立续的存储空何(B)统性表采用链式存储不必占用一片连续的存储空间(C)统性表采用链式存储便于插入和删除操作的实现(D)线性衣采用Mi序存储便于椅人和DJ除操作的实现2 .设哈夫女树中的叶丁结点总数为明假设用二叉链表作内存他结构.那么谈哈夫业树中1&共有()个空指针城.（八）2n-l(B>2n(C)2n*l<D>4m3 .设留序循环队列皿5MT)的头指针和足指计分别为F和R.头指HF总是指向队头元素的前Vfjfit.足指针R总足指向队尾元架的当的付世,那么该他环队列中的元素个数为(J.（八）R-F(B)F-R(C)(R-F+M)%N(D)(F-R+M)¾M4 .设某根二叉例的中样i历序列为ABCa的序道历序列为CABD,那么后序遍历该二叉例得到序列为().（八）BAl)C(BBa)A(C)QMB(»>OUW5 .设柒完全无向图中芍n个顶点，那么该完全无向图中在()条边。（八）n(n-B2<B>n(n-l)(C)r<D>n1-l6 .设北稷二叉树中在2000个结点，那么诬二叉树的AH、离度为()。（八）9<B>10(C)11(D)127 .设某有向图中有n个顶点.那么该有向图对应的纪检衣中有()个衣头结点.（八）n-l<B>n(C)n+1(D>2n-l8 .设一ill初始记录关键字序列(5.2.6.3.8).以第一个记杀:美Ut学5为基港进行-他快速排序的结界为().（八）2.3.5.8.6(B)3.2.5.8.6(C)3.2.5.6.K(D)2.3.6,5,8二、双空题(24分)1. 为了能有效地应用IUSH先找技术，必须解决的两个问题是».2. 下面程序段的功能实现数据X进收,要求在下划统处埴上正确的语句,WpCdCfstruct(ints100;int«>p:|qstack;VOidush<sqMackArtackJntx)Iif(stack.top=m-l)IMimn"overflow")：ekeI:;J3. 中序闻历二叉柞序树所称到的序列是序列(以有序或无序).4. 快速排序的蚊坏时间复杂慢为.平均时间复杂慢为.5. 设某基二叉树中度数为。的结点数为1,度数为】的结点数为N“那么读二叉制中度数为2的结点数为假Ht采用二叉篌表作为该二叉树的存储结构，那么该二叉树中共百个空指针域.6. 谀某无向图中顶点数和过数分1为n和e,所在顶点的度数之和为d.那么e=7. 设帆初始记录关例字序列为(55.63.H.38.75.80.31.56).布么利用筋设法求立的初始堆为8. 有向图的邻接衣存此结构如旌从顶点IHl发.DFS遍历的输出序列是.BFS西历的籀出序列国)每接臬存由吉构三、应用题(36分)1.设一俎初始记录关俊字序则为(45,80.18.40.22.78).制么分别给出第，1例问里项选抨性排序和第4i8H接插入排序后的结果，2,设指针变景P指向双向链表中结点A.指计变Vq指向被插入结点B,也:求给出在结点A的石面插入地点B的操作序列(设双向跳表中结点的四个指计域分别为IIink和rlink).3 .设组力冲的记录关谯字库列为(13.18,24.35.47.50.62.83.90).杳找方法用二分杳找.要求计算出杳找关键字62时的比拟次数并计尊出亚找成功时的平均在找长度.4 .设一棵树r中边的集介为(AB>.<A.C>.(A.D).(B.E).(C,H.(C.G”.要求用赅子兄笫衣示法(二Mfii衣)衣示出该树的存储结构并将该树转化成对应的二叉树.5 .设右无向图G,要求蛉出用If电册算:法构造最小生成树所走过的边的集合.6 .设有一JH初始记京XC键字为(45.KO.IS.1(1.22.78),要求构域一根二叉排序机并始出构造过程.四、算法处计题(16分)1 .设有一斑和始记录美键字序列(K.Kj,.KJ.要求设计一个算法能婚在OGO的时间或杂度内将慢性表划分成两局SJ,其中左华局部的每个关健字均小于K,右半局部的斑个关位字均大干等干K.2 .设有两个妪合A和象会B,要求设计生成妪令C=AnB的口法,其中集合MB和C用链式存储结构农示.mMw(三)一、途务(1分，共20分)1 .我某数据结构的二元Ul形式入示为A=(D.R>,D=IOI.02.<)3,04.05.06.<)7.08,W.R=r.r=<01,02>.<01.03>.<01.(M>.<02.05>.<02.06>.<03,07>.<03,0S>.<03,09>.那么数据结构A是().（八）线性结构(B)树型结构(C)物理结构(图型结构2 .下面程序的时间夏柴为()for(i=l.S=Osi<=nsi+*)(=!fortj=lj<=i:j÷*)=tjs=Hi|（八）O(n)<B>O(n1)(C)0(n*)(D>O(n,)3 .设Ifi计支Mptfi向小链表中结点A假设JH除堆链表中结点A,那么需要修改指针的操作序列为().(A) q=->nextp->data=q->datap->next=q->nextsfre«<Q)i(B) <=->next:q->data=->data:->next=q->ne*t:free(q)：(C) q=->nexi:->ncxt=q->nexi:fr<e(q>:(D) q-p->11rxt;p->dnt-q->datn;frcc(q):1 .设刊n个恰排库的记NjCU!字，那么在增排序中第鬟()个辅助记录单元.（八）1<B>n(C)nIogJi<D>n!5 .设一加初始关键字记录关健字为(20,15.1%18.21.36.10.10),那么以20为基准记录的的快速推序结束后的结果为().(A) 10.15.14>18.20.36.10.21(B) 10.15.14,18.20.40.36.21
