《数据结构（Java语言描述）习题答案.docx》由会员分享，可在线阅读，更多相关《数据结构（Java语言描述）习题答案.docx（15页珍藏版）》请在课桌文档上搜索。
1、1.5习题一.填空巡1 .数据的物理结构包括顺序结构的表示和存储和链式结构的表示和存储。2 .对于给定的n个元素,可以构造出的逻辑结构有（集合结构），（线性结构）,（树型结构），（图型结构）四种。3 .一个算法具有5个特性：（有穷性）、（确定性）、（可行性），有零个或多个输入、有一个或多个输出。4 .抽象数据类型被形式地定义为（D.S,P）,其中D是（数据元素）的有限集合，S是D上的（关系）有限集合，P是对D的（坛本操作）集合。5 .数据结构主要包括数据的（逻辑结构）、数据的（存储结构）和数据的（操作）这三个方面的内容.6 .一个算法的效率可分为（时间）效率和（空间）效率。二.单项选择题1 .
2、线性结构是数据元素之间存在种（D）。A.一对多关系B.多对多关系C.多对一关系D.一对一关系2 .数据结构中,与所使用的计算机无关的是数据的（C）结构.A.存储B.物理C.逻辑D.物理和存储3 .算法分析的目的是（B）。A.找出数据结构的合理性B.分析竟法的效率以求改迸C.研究算法中的输入和输出的关系D.分析算法的易懂性和文档性4 .算法分析的两个主要方面是（A.空间更杂性和时间纪杂性B.正确性和简明性C.可读性和文档性D.数据更杂性和程序豆杂性5 .计算机算法指的是（C）.A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法6 .从逻辑上可以把数据结构分为（八）.A.线性结构和非线
3、性结构B.紧凑结构和非紧凑结构C.动态结构和静态结构D.内部结构和外部结构pl.ncx(=ql.ncxt;1.ength-;)5 .设仃个双链表，每个结点中除有PriOr、data和next三个域外，还有一个访问频度域freq在链表被起用之前，其值均初始化为零。每当对链表进行一次1.OCaICNOdC(1.x)运算，便令元素值为X的结点的限q域的值加I，并调推表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是舞近表头。忒写个符合上述要求的算法1.oCateNOde(1.X)。staticboolean1.ocateNode(dlinklist1.Tx)DuN(lcp=1.gc
4、lHead().ncxt;指针p用于查找第个data域等于X的结点DuNodeq:while(p!=nll&(p.data).euals(x)=falsc)p=p.ncxt;if(p=null)/p为空,意味着没有找到data域等x的结点returnfalse;clscp.freq:将找到的data域等于x的结点的访问频度值加Iq=p.prior;指付q用于查找P的前面结点中第一个freq域不小于当前P所指结点的freq域的结点while(q!=1.getHead()&(q.freq).mpareo(p.freq)()q=q.prior;if(q!=p.prior)如果q发生了前移,才有必要移
5、动Pp.rior.next=p.next;if(p.ncxt!=null)p.next.prior=p.prior:如果P不是终端结点，才有必要修改p的后继结点的prior域p.prior=q;p.next=q.next;q.next=p;p.next.prior=p;/将P插入到q的后边)Jreturntrue;6 .一个单循环链表F,每个结点包含三个域：pre,data-flnext.其中Pre为null,将其变为双循环链表的算法如下，请对算法中的空白处城空：intdoublc_lisi(Du1.ink1.istF)Du1.Node*p,*q;if(F.ncxt=F)(F.pre=F:re
6、turn;)产循环链表为空的情况q=F;=F.nexl;A.front=rcarB.front!=rcarC.front=(rear+l)%n()D.front!=(rear+1)%n()10.判定个循环队列QU(最多元素为m)为满队列的条件是_C_。A.front=rearB.front!=rearC.front=(rear+1)%mD.front!=(rear+1)%m11 .循环队列用数组A()m-l存放其元素值，己知其头尾指针分别是from和rear,则当前队列中的元素个数是_A_。A.(rcar-front+m)%mB.rcar-front+lC.rear-front-1D.rear
7、-front12 .栈和队列的共同点是_CA.都是先进后出B,都是先进先出C.只允许在端点处插入和删除元素D.没有共同点13 .向一个栈顶指针为HS的链栈中插入一个S所指结点时，则执行一Cl(不带空的头结点)A.HS.next=s;B.s.next=HS.next:HS.next=s;C.s.nex(=HS;HS=s;D.s.ncxt=HS:HS=HS.ncxt;14.从一个栈顶指针为HS的链栈中删除一个结点时，用X保存被删结点的值，则执行_D_0(不带空的头结点)A.X=HS;HS=HS.next;B.x=HS.data;C.HS=HS.next;x=HS.data;D.x=HS.data:
8、HS=HS.next：二.填空题1 .向栈中压入元素的操作是(先移动栈顶指针，后存入元素)。2 .时栈进行退栈时的操作是(先取出数据元素，后移动栈顶指针)。3 .在一个循环队列中，队首指针指向队首元素的(前一个位置.)。4 .从循环队列中删除一个元素时，其操作是(先移动队首指针.后取出元素)。5 .在具有n个单元的循环队列中，队满时共有(nJ)个元素。6 .一个栈的输入序列是12345,则栈的输出序列43512是(不可能的)nt;for(i=l;i=size();i+)j=(j+1)%qucucArray.length;System.out.println(queuenrayj);)4 .设一
9、循环队列QUeUe,只有头指针from,不设尾指针，另设一个内含元素个数的计数器，试写出相应的进队、出队算法。publicvoidEnQucuc(Tobj)Iif(cont=quccArray.length-1)队满Tp=(T()newObjcct(qucucArray.lcngth*2;inti=front+Ij=l.m=1:WhiIe(InVCoUni)p(j=qucucArray(i;i=(i+1)%queue11ay.length:j+;m+;queueAnay=p:front=0;count+;qcucAay(front+count)%qucucArray.length=obj;pu
10、blicTDeQucucOIif(count=0)SyStem.ou.rimln(队列已空，无法Hl队！)；returnnull：front=(front+1)%qucucArray.length;count-;returnqucucArrayfront;I5 .设计一算法能判断一个算术表达式中的圆括号配对是否正确。(提示：对表达式进行扫描，凡遇到“(”就进栈，遇到“)”就退出栈顶的“(”，表达式扫描完毕时栈若为空则圆括号配对正豳。)publicstaticbleanmatching(char11exp)intstate=l.i=0:sequenceStacks=newsequenceStac
11、k();/*定义一个顺序栈*/while(icxp.lcngth&state=1)switch(expi)(cases.ush(expi);i+;break：1case):Jif(!s.isEmply()if(s.gctHcad()=()s.op();i+;elsestatc=O;)elsestatc=0;break:default:i+;break;if(s.isEmpty()&state=I)returntrue;elsereturnfalse;4.7习题一.单项选择题1 .空串与空格串是相同的，这种说法B。A.正确B.不正确2 .串是一中特殊的线性表，其特殊性体现在BA.可以顺序存储B.
12、数据元素是一个字符C.可以链接存储D.数据元索可以是多个字符3 .设有两个串P和q,求q在P中首次出现的位置的运算称作A.连接B.模式匹配C.求子中D.求申长4 .设串s1=BCDEFG.s2=PQRST,.函数COn(x.y)返回X和y吊的连接申，subs(s,i,j)返回出s的从序号i的字符开始的j个字符组成的子串，Ien(三)返回返S的长度,则con(subs(s1,2,Ien(s2),SUbS($】Jen($2),2)的结果申是D.A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF5 .常对数组进行的两种基本悚作是A.建立与删除B.索引和修改C.查找和修改D.查找与索引
13、6 .二维数组M的成员是6个字符(每个字符占一个存储单元，即一个字节)组成的串,行下标i的范围从。到8,列下标j的范围从I到10,则存放M至少需要2_个字节：M的第8列和第5行共占一一个字节。 A.90B.180C.240D.540 A.108B.114C.54D.60二.填空题(聘正确的答案填在相应的空中)1 .串的两种最法本的存储方式是顺序存储和徒式存储2 .两个用相制的充分必要条件是长度相等I1.对应位世字符相等。3 .空出是。个展符的符,其长度等于C，空格串是由一个或多个空格字符组成的串,其长度等于空格字符个数.4 .设s=IAMAoTEACHER.其长度是(口表示空格)三.算法设计题
14、：1 .编写算法，实现remove(Stringt)操作，即从当前审中删除所仃和串I相同的子串.publicinirenove(stringt)(在当前串中删除所有与串t相等的子串，并返回甜除的次数inttimc=0.m;fbr(intj=()jthis.length-t.length+kj+)if(this.charsj=t.charsl)intx=0;fbr(inti=O;it.length;i+)if(this.charsj+ij=t.charsi)x+;elsebreak;)if(x=t.length)m=j;for(inti=j+t.lcngth:iVoVIQ0-28VOV0。18V
15、oV3。0。2VOV4小0.13。vlv5P23v2v5p6，24qv2v9金3Pv3v64,3。3”v3v7”3。34v4v6*47,v5v7p2心33v6v5*j13“2(KVeV加Bp小v694,13“36.v7v9*j383%v8v7p22“22丁v8v922a4g7.5习题与解析一.填空黑1 .顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为次：当使用监视哨时，若查找失败，则比较关键字的次数为n+l.2 .在顺序表8,11,15,19,2526,30,33,42,48,50）中,用折半（二分）法查找关键码值20,需做的关键码比较次数为4。3 .在有序表A1.12中，采用
16、折半查找算法查等于A12的元素,所比较的元素下标依次为6、9、11、124,高度为4的3阶B-树中，最多有,个关键字。5 .在一棵m阶B树中,若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是1：若在某结点中剧除一个关键字而导致结点合并,则该结点中原有的关键字的个数是m/21-l。6 .如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为（n+l）27 .高度为8的平衡二叉树的结点数至少有用个。8 .已知二叉排序树的左右子树均不为空，则左子树上所有结点的值均小-它的根结点值，上国_上所有结点的值均大于它的根结点的值。二.
17、单项选择题1.顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为(D),二分法隹找只适用于杳找顺序存储的有序表，平均比较次数为(C),在此假定N为线性表中结点数，且每次查找都是成功的。A.N+lB.21ofcNClog屈D.N/2E.Nlog2NF.N!2 .下面关于二分查找的叙述正确的是(D)。A.表必须有序，表可以唤序方式存储，也可以链表方式存储C.表必须有序，而且只能从小到大排列B,表必须有并且表中数据必须是整里，实现或字符型D.表必须有序，Il表只能以顺序方式存储3 .适用折半查找的表的存储方式及元素排列要求为(D).链接方式存储，元素无序C.顺序方式存储，元素无序4.具有
18、12个关键字的有序表,B.链接方式存储，元素有序D.顺序方式存储，元素有序折半查找的平均杳找长度（八）。A.3.1B.4C.2.5D.55 .折半查找的时间熨杂性为(D).0(112)B.0(n)C.0(nlo3n)D.0(log；n)6 .分别以卜列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(C)eA. (100.80.B. (100.120,C. (100,60,D. (100.80,90.60,120.110,130)110,130,80,60,90)80,90,120,110.130)60,90,120,130,110)7 .在平衡二叉树中插入个结点后造成了不平衡，设最低
19、的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩了的平衡因子为1,则应作(C)型谢整以使其平衡.1.1.B.1.RC.R1.D.RR8,卜列关于In阶B-树的说法错误的是(D)A.根结点至多有In棵子树8 .所有叶子都在同一层次上C.非叶结点至少有m/2(m为偶数)或m/2+1(m为奇数)棵子树D,根结点中的数据是有序的9 .设有一组记录的关键字为19,14,23.1,68,20,84,27,55,I1.10,79,用链地址法构造散列表，散列函数为H(key)=key%13,散列地址为1的链中有(D)个记录.1B.2C.3D.410 .若采用徒地址法构造散列表，散列函数为H(ke法=key
20、%1表则需（八）个链表。这些链的健首指针构成个指针数组，数组的下标葩困为(C)。(1) A.17B.13C.16D.任意(2) A.0至17B.1至17C.0至16D.1至16U.设哈希表长为14,哈希函数是11(key)=key与ll,表中已有数据的关键字为15,38,61,84共四个，现要将关燧字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位身是(D)A.8B.3C.5【).9三、判断题(J)1.顺序查找法适用丁存储结构为厥序或链接存储的线性表。(X)2.折半查找法的杳找速度一定比顺序杳找法快。(X)3.在二叉树排序树中插入一个新结点，总是插入到叶结点卜.面。(J)4.完全二
21、叉树肯定是平衡二叉树。(X) 5.对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。(Y) 6.二叉树中除叶结点外，任一结点X,其左子树根结点的值小于该结点(X)的值：其右子树根结点的值2该结点(X)的值,则此二叉树一定是二叉排序树。(Z) 7.在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。(AA) 8.在m阶B-树中每个结点上至少有m/21个关键字，圾多有m个关键字。(BB) 9.在平衡二义树中，向某个平衡因子不为零的结点的树中插入新结点，必引起平衡旋转.四、应用题1.设有一组关键字9,01,23,14,55,20,84,27,采用哈希函
22、数：H(key)=kef0lf表长为11j,用开放地址法的平方探测再散列方法：”,=(H(g)+4)n,4=F2,3=解决冲突。要求：对该关键字序列构造哈希表，并计算杳找成功的平均查找长度。所构造哈希表为:01234367S914192384：75520AS1.=(l*4+2*2+3*l+4*l)81582.一棵二叉排序树结构如下，各结点的值从小到大依次为1-9,请标出各结点的值。图7.21题4.3图3 .用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树,画出该树，并求在等概率情况下查找成功的平均查找长度。AS1.=(l*l+2*2+3*3+4*2+5*
23、2)10=3.24 .假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找,试回答下列问题:(1)画出描述折半查找过程的判定树：(2)若传找元素54,需依次与那些元素比较？(3)若查找元素90,需依次与那些元素比较？(4)假定每个元素的查找概率相等，求查找成功时的平均查找长度。(2)需比较元素为：30,63,42,54(3)需比较元素为：30,63,87,95(4)AS1.=(1*1+2*2+3*4+4*5)/12=37/128.7习题与解析一、填空题I.分别采用堆排序，快速排序，目泡排序和归并排序，对初态为有序的表,则报行时间的是目泡排序獴法,最拢时间
24、的是快速排序总法。2,直接插入排序用监视哨的作用是免去有找过程中每一步都要检测直找范圉是否：,提高直找效率。23.对n个记录的表rn进行简单选择持序，所需进行的关键字间的比较次数为n（n-l）二、选押题I,如果待排序序列中两个数据元索具有相同的值，在排序前后它们的相互位理发生倾倒，则称该樗序知法是不稳定的。（CE）就是不桎定的排序方法。A.起泡排序B.归并排序C.Shell排序D.直接插入排序E.简单选择排序2 .下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（八）.A.选择排序法B.插入排序法C.快速排序法D.堆排序法3 .数据序列（8,9,10.4.5.6.20,1,2）
25、只能是下列排序算法中的（C）的两趟排序后的结果。A.选择排序B.目泡排序C插入排序D.堆排序4 .数据序列（2,1,4,9,8,10,6,20）只能是卜列排序鸵法中的（八）的两趟排序后的结果。A.快速排序B.冒泡排序C选择排序D.插入排序5 .对一组数据（84,47,25,15,21）排序，数据的排列次序在排序的过程中的变化为（1） S447251521（2）1547258421（3）152125S4474）1521254784则采用的排序是（八）。A.选择B.目泡C.快速D.插入6 .有一组数据（15,9.7,8,20,-1,7,4）用快速排序的划分方法进行一趟划分后数据的排序为（八）（按递
26、增序）。A.下面的B.C.D都不对。B.9,7,8,4,-1,7,15.2（）C.20,15,8.9,7,-I,4,7D.9.4,7,8.7,-I,15.207 .在F面的排序方法中,辅助空间为a）的是（d）.A.希尔排序B.堆排序C.选择排序D.归并排序8 .卜.列排序算法中，在待排序数据已有序时，花费时间反而最多的是（C）排序。A.冒泡B.希尔C.快速D.堆9 .下列排序算法中，在每一熠都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（B）。A.直接插入排序B.快速持序C.直接选择排序D.堆排序10 .对初始状态为递增序列的表按递增版序排序，最省时间的是（C）算法.
27、最费时间的是（B）算法。A.堆排序B.快速排序C.插入排序D.归并排序11 .就平均性能而言，目前最好的内排序方法是（D）排序法。A.目泡B.希尔排序C.交换D.快速12 .如果只想得到100o个元素组成的序列中第5个最小元素之前的部分排序的序列，用（D）方法最快.A.起泡排序B.快速排列C.ShCII排序D.堆排序E.简单选择推序13 .在序列“局部有序或序列长度较小的情况下，最佳内部排序的方法是（八）A.直接插入排序B.自泡排序C.简单选择排序14 .从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（八）排序法。A.插入B.选
28、择C.希尔D.二路归并15 .用直接插入排序方法对下面四个序列进行排序(由小到大)，元素比较次数鼓少的是(C)。A.94.32.40.90.80.46.21.69B.32.40.21.46.69.94.90.80C.21.32.46.40.80.69.90.94D.90.69.80.46.21.32.94.4016 .直接插入排序在最好情况下的时间灯杂度为(B)A.O(log;)B.5)C.O(Mogj11)D.O(r)17 .若用目湖序方法对序列“0.14.26.29.41.52)从大到小排序，需进行(C)次比较。A.3B.10C.15D.2518 .对关键码序列28,16,32,12,60
29、,2,5,72快速排序，从小到大一次划分结果为(B)。A.(2,5,12,I6)26(6O,32,72)B.(5,16,2,12)28(60,32,72)C.(2.16.12,5)28(60,32.72)D.(5,16.2,12)28(32,60.72)三、判断题)1.内排序要求数据一定要以顺序方式存储.(X)2.持序算法中的比较次数与初始元素序列的排列无关。.(X)3.排序的稳定性是指排序算法中的比较次数保持不变，且算法能筋终止。()4.直接选择持序算法在最好情况下的时间宓杂度为05)。(X)5.在待排数据基本仃序的情况下，快速排序效果最好。(J)6.堆肯定是探平衡二义树。四、应用题I.算法
30、模拟设待排序的记录共7个，排序码分别为8,3,2,5,9,1,6。(1)用直接插入排序。试以排序码序列的变化描述形式说明排序全过程(动态过程)要求按递减顺序排序。1) 83259162) 83259163) 85329164)98532165)98532166)986532I(2)用荷单选并排序。试以排序码序列的变化描述形式说明排序全过程(动态过程)要求按递减顺序排序。1)93258I62)98253163) 98653I24) 98653125)98653126)9865321(3)直接插入排序算法和电单.选择排序算法的稳定性如何?直接插入是稳定箕法，简单选择是不稳定箕法2.有一随机数组(2
31、5,84,21,46,13,27,68,35,20),现采用某种方法对它们进行排序,其每越排序结果如下,则该排序方法是什么？初始:25.84.21.46,13,27.68.35.20第一趟:20.13.21.25.46.27.68.35.84第二第:13,20,21.25.35.27.46.68.84第三趟:13,20.21.25,27,35.46.68,84根据排序结果可知该方法是：快速排序。3.4.全国有100OO人参加物理竞赛，只录取成绩优异的前IO名，并将他们从高分到低分输出。而对落选的其他考生，不需排出名次，问此种情况下,用何种排序方法速度最快？为什么？用堆排序，因为堆排序建堆比较次
32、数至多不超过4n,对深度为K的堆，在调整堆兑法进行的关键字比较次数至多为2(k-l)次，且辅助空间为0(1)。给出组关键字：29,18,25,47,58,12,51,10,分别写出按下列各种排序方法进行排序时的变化过程：(I)快速排序每划分一次书写一个次序。10.18.25.12.29.58.51.4710.18.25.12,29.47.51.5810,12,18,25,29,47,51.5810.12.18.25.29.47.51.58(2)堆排序先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。初始堆：10.18.12.29.58.25.51.47取第个元素10.调整堆后:取第二个元
33、素12,调整堆后:取第-：个元素18,取第四个元素25,取第五个元素29,取第六个元素47.调整堆后:调整堆后:调整堆后:调整堆后:取第七个元素51,调整堆后：5,请写出应填入下列叙述中()12.18.25.2958.47.5118,29,25.51,58,4725,29,47,51,5829.51.47.5847.51.5851.5858内的正确答案。排序有各种方法，如插入排序、快速排序、堆排序等。设一数组中原有数据如F：15,13,20,18,12,60。卜面是一组由不同排序方法进行遍排序后的结果。(快速排序)排序的结果为：12,13,15,18,20,60(自泡排序)排序的结果为：13,15,18,12,20,60(插入排序)排序的结果为：13,15,20,18,12,60(堆排序)排序的结果为：12,13,20,18,15,60
