数据结构（Java语言描述）模拟试卷2套（含答案）.docx

（20182019学年第二学期）课程号：BosONo30课序号:课程名称：数据结构任课老师:适用专业年缴：2017级本科学生人数：印四份数:考生承诺我己认r（俯读并知晓（四川大学锦城学僚考场规则和四川大学锦城学院学生考试违纪作弊处罚条例%.郑勇承诺:1 .已按妥求格考试*止携帝的文具用品或与考试有关的构修故Jl在指定地.以；2 .不带手"双入考场I3 .号试期间遵守初建规定.若有违规行为.问按照有关条款接殳处理.考生学号：考生姓名：考试时何；I小时却分神单项逸界（在每小国的四个冬选答案中，选出一个正确的答案.每小2分，共20分）、7（）=8"'+15，/+3”+1的时间&杂度是（）,A.O（nA3）B.O（112）C.0（n）D.（Xl）2,下列不属于数据的逻相结构的足（九B.索引A.集合C.图D.W3、下列数据结构，（>不属于“一时一“结构。A.线性表B.栈C.集合D.队列4、随式存储结构时，给点的存储总元地址（）.A.不一定连续B.一定不连续C.一定连线D.部分连城.部分不连续5、时于一个头指针为head的不带头结点的单钺去，判断该表为空的条件是（）.A.head.next=headB.hcad!=nullC.head=nllD.head.next=null6、在一株：叉树上第5层的站点数域多是多少（）。A.18B.16C.10D.87、若将整数A,B.C,D依次进栈，则不可能得到的眼序是（）.A.ADBCB.DCBAC.ABCDD.ACBD8、若小S="Imthcwnl则其子中的个数是（）.A.24B.28C.32D.369、二:叉树的度是（）个。A.IB.2C.3D.410.任选一个记录，以它的关键字作为“基准”，凡关键字小于枢轴的记录均移至枢轴之前，凡关键字大于枢轴的记录均移至枢轴之后，该排序方法称为(川F序法.A.快速B.选择C.冒泡D.插入二、简胃R(每小JBiO分，共20分)1、顺序存储结构的队列在实现的时候存在假溢出现象，请说明什么是假溢出？为什么会有叔溢出？如何解决假溢出？2、简述什么是栈栈行什么特征.假设一个栈的入栈序列是字符A、B.C.D、E,若出栈序列是C、D.E、B.A,试分析入栈和出栈过程；说明若要得到其出栈序列，栈的容Wt至少应该是多少？三、算法分析和设计(共20分)1)分析卜面算法并写出时应功能(SqSlack为地序栈)(8分)publicstaticvoidrev(SqS<ackSJaCk)(SqStackStaCkI=newSqStack(50);构造一个容/为50的顺序栈对象whilc(!s<ack.isEmp<y()StackI.push(stack.pop();SqStackStack2=newSqSlack(50):WhileCStack1.isEmptyO)Stack2.push(Stack1.pojX)：while(!Stack2.isEmpty(»stack.push(Stack2.x>X);12)请定义个完成下表内容的线性去钺式存催结构的结点类PUbliCCIaSSNodC<T>,其中包括创建一个空结点的构造陶数、一个能够创建卜表数据的构造函数,getXuehao()rf½(获取学号)WgetNext()ifc.(12分)；(*介才书目课外题*)其表结构如下：学号姓名成绩174081002刘伟75四、综合题每小,共40分）I、某一个数据初始序列为46,57,32,28,76,35,25,12）,请利用直接选择排序方法写出每次选择和交换后的结果2、如下图所示的无向连通网，边表示城市间的路网践路，边上的权表示假该路所需要的代价.如何选择能够沟通每个城市且总代价最少的nl条线路，国出其可熊的最小生成树.（本题有多种解题方法*）3、试分析稀疏矩阵的存储方式，应该采用什么方式存储，为什么？井说明如下稀疏矩阵应该如何存储，井给出行优先的存储组表。002000,000000003000B=00240000110000500-7004、对关键码序列：37.64,24.39.18.83.45.29,请给出二叉排序树的构建过程.四川大学锦城学院期末考试试题（A卷）答案课程号：BO8O29O3O课序号：课程名称:数据结何任课老师：成钟j:三单选界（在每小的四个备选答案中，选出一个正确的答案.每小M2分，共20分）ABCAC/BADBA二、管答题（每小IBlO分，共20分）1、 （10分）答窠：指认尾指针达数组末端，队列中还有空余的空间,但元素不能进队列现象.称为假溢出.由于队列是一种受限操作，插入在队尾，删除在队首，这种操作会出现银溢出。采用循环队列，将队列看着是一个首尾相连的圆环.2,（10分）答案：|>栈是存储潺中划定的一块受限存储区,限定在栈段操作，特点是：先进后出2）入栈和出入过程是:入梭A、B.CJgl出根C：然后入机D：出根D:然后入栈E：最后出栈所有元素.依照K出栈存列.栈的容量至少应该有3Bytc容量。三、第法分析和设计（共20分）1）（8分）答案I应用栈特点，将栈SlaCk内容逆置，在逆置过程中，借助两个临晡枝StaCkl和StaCk2先将StaCk栈顶元素依次出栈,压入也时栈StaCkI中：然后招StaCkl栈顶元素依次出栈,乐人彼时栈SWCk2中；最后将Su*ck2栈顶元素依次出栈，压入栈NaCk中，实现将栈NaCk内容逆出2）（12分）答案：链式存谛结构的结点类定义如下：publicclassNode<>Stringstunum,xingming;Tcj;Node<T>next;publicNode（）next=null;publicNode（Stringobjl,StringObj2,Tobj3,Node<T>n）Stunum-Objljxingming-obj2;Cj-obj3;ext-n;序表或链表中。（5分）2）三元组表如下：或者：(666).(1.3,2),(3.3.3),(4.3,24).(5211)46,l,5)J64-7)（20182019学年第二学期）探界号：BoW）29（刖球序弓:课程名称：数据结构任课老师:适用专业年缴：2017级本科学生人数:印题份数:考生承诺我己认r（俯读并知晓（四川大学锦城学僚考场规则和四川大学锦城学院学生考试违纪作弊处罚条例%.郑勇承诺:4 .已按妥求将考试禁止携帝的文具用品或万考试有关的物修故51在指定地.氢；5 .不带手"双入考场I6 .号试期间遵守初建规定.若有违规行为.问按照有关条款接殳处理.考生学号：考生姓名：考试时何：I小时却分怦一、单项选界JB（在每小的四个冬选答案中，选出一个正，的答案.每小愚2分，共2（»分）1、算法的时间发杂度取决于（）。A.问题的规模B.待处理数据的初始状态C.A和BD.以上都不是2、链式存谛结构存储设计时,结点间的存饰地址（>.A.一定连续B.不一定连续C.不需要考虑D.以上都可以3、下列（）结构中的数据元素的关系是“多对多”的关系.A.线性去B.二叉树C.图D.队列4、单链表的存储密度是（）顺序表的存储密度，A.大十B.C.差不多等于D.5、队列存储数据除则是（）.A.先进先出B.后进后出6,在完全二叉树中.叶子结点<A.一定在最后一层C,分布在任遨:层以上都有可能C.后进先出D.没有限制J.一定在最后两层）.可能在最后一层，可能在坦后两层A.I（X）B.11（）C.5D.908、用直接插入排序方法对下面4个序列进行递增排序，元素比较次数最少的是（）.,32,46,40.80,69,90.96)B.(32.40,21.46,69,96.90.80)C.196.32.40.90.80.46.21.691D,(90.69.80.46.21.32.96.40»9、在有980个结点的完全二叉树中，有()个叶子结点,.480B.490C.500D.51210.在一个有n个顶点的连通图G中,存在一个极小的连通子图G',G'包含图G的所有顶点.但只有n-1条边,并且G'是连通的,则称G'为图G的().A.破小生成树B.生成图C.生成树D.以上都不是二、管答题(每小题10分，共20分)I、简述什么是循环队列,为什么要引入新环队列.2、什么是完全：叉树？完全：叉树般采用什么存储结构？为什么？三、算法分析和设计(共20分)1)分析下面算法并写出对应功Ife(8分)publicstaticvoidIrUnSfOrm(longnum.mlr)(Stacksck=ncwIinkStackO;while(nun!=0)(inik=(i11)(nun%r):SCkPUSh(k)：num=r;whilc(!sck.isEmpty()System.out.print(sck.pop():Syslen.>ut.println();2)谛定义一个完成卜表内容的找性表链式存储结恂的结点类PUbliCCIaSSNodC<T>.其中包括创建一个空结点的构造函数、一个能好创建下表数据的构造函数、getXinmin()函数(获取姓名)和getNext()函数.(12分)：(*介考书目果外题)其表结构如下：姓名电话住址陈林全13740034842-1-104四、ttfl（每小题10,共40分）1,已知一组元素的排序码为：15»48.26,32,73.25.36.45.12.68）,利用直接插入排序的方法写出每次向前面有序表插入一个元素后的排列结果.2、已知一个无向的连通网，如卜图所示，要求从A点出发，给出其最小生成树,并画出其构造过程。（本题有多种解题方法）3、试分析稀疏矩阵的存储方式，应该采用什么方式存储，为什么？井说明如卜稀疏矩阵应该如何存储，并给出行优先的存储组表。000080,002000A=00000000014000-70000,0005004.对关键码序列:43.21.68.735.49.853k请给出二叉排序树的构建过程,四川大学锦城学院期末考试试题（B卷）答案成绩:课程号：BO8O29O3O课序号：课程名称:数据结构任课老师:一、单项选舞题（每小题2分）CBCBA/DDABC二、简答Ji（每小题10分）I、答案：1）将顺序队列的存体KlW也为是一个头尾相连的回环,划常把这种特殊结构的队列称为循环队列.队头、队足指针加I时从MaXSiZC-I直接进到0.可用取模（余数）运算实现.2）在队列的联序存储结构中，设从头指骨为front、队尾指针为rear、队的容量为MGSiZe.当有元素要加入认列时，若rwr=MQSize-1（初始时Nar=O）,但.front不为0,即指队列中还有空余的空间,但元