数据结构Java版习题

1、v1.0可编辑可修改(按照自己的情况选作部分习题，不要抄袭)第二章 习题顺序存储线性表一判断题1 线性表的逻辑顺序与存储顺序总是一致的。X2顺序存储的线性表可以按序号随机存取。V3顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。X4. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 V5 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。X6.在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。V二 单选题(请从下列A B, C, D选项中选择一项)1.线性表

2、是(A )。(A) 一个有限序列，可以为空；(B)个有限序列，不能为空；(C) 一个无限序列，可以为空；(D)个无序序列，不能为空。2 对顺序存储的线性表，设其长度为n,在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的( A )个元素。(A) n/2(B) n+1/2(C) n -1/2(D) n三填空题12v1.0可编辑可修改1 在顺序表中做插入操作时首先检查表是否满了。四算法设计题1 设线性表存放在向量 Aarrsize的前elenum个分量中，且递增有序。试写一算法，将 x插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。2. 已知一顺序表A

3、,其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同 的元素。3. 编写一个函数，从一给定的顺序表 A中删除值在xy(x<=y)之间的所有元素，要求以较 高的效率来实现。提示：可以先将顺序表中所有值在xy之间的元素置成一个特殊的值，并不立即删除它们，然后从最后向前依次扫描，发现具有特殊值的元素后，移动其后面的元素 将其删除掉。4. 线性表中有n个元素，每个元素是一个字符，现存于向量Rn中，试写一算法，使 R 中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。(研54)5. 线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表

4、中前m个元 素和后n个元素进行整体互换。即将线性表(a1, a 2,，a m b 1, b 2,，b n)改变为：(b1, b 2,b n , a 1, a 2,a m)。五上机实习题目约瑟夫环问题约瑟夫环问题：设编号为 1, 2, 3,n的n(n>0)个人按顺时针方向围坐一圈,22v1.0可编辑可修改每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的 m值, 从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。

5、package算法设计； importimportimportpublic class YueSeFu public static void main(String args) Scanner sca n =new Scanner;"请输入总人数：");int totalNum =();"请输入报数的大小：”)；int cycleNum =();yuesefu (totalNum, cycleNum);();public static void yuesefu( int totalNum, int countNum) 33v1.0可编辑可修改I 血& rw

6、i N m s J i | * - - ' * /public cIabb YueSeFu 1Apublic static wid msin (String 己匕号曰) 30*Scanner- new seanner(5y31em£n);10-out.print;1呷屮七otalHiiDn = scan.nex七Tut;?E12Syateni. out. or mt "谁詁:.-把吐 J丈 J'. *"；913Lnt cycleHum = scan«nextlnt(:1214yi?(t ccyelaNiizii) 1515scan>

7、close);IS1621172410!-ptjblxc static void(a.nt totint co279*/軻站代人販30p巧Linr art = new ArrayList<1 ntege421for (xnt i - lj i <- tote J Num; i+J fe?.tart add (1);132317汕2225ix&t k = 0 jZr21whlXe ( at art>0) 12?k k +72ft禮 Ji14朋k k % otat) - 1;20S3/判撕县直買认電28 M“ 4J| r r 1.rfC链表中最常用的操作是在最后一个元素之

8、后插入一个元素和删除最后一个元素，则采用(D)存储方式最节省运算时间。(A) 单链表(B) 双链表(C) 单循环链表(D) 带头结点的双循环链表5. 循环链表的主要优点是(D )。(A) 不在需要头指针了(B) 已知某个结点的位置后，能够容易找到他的直接前趋(C) 在进行插入、删除运算时，能更好的保证链表不断开(D) 从表中的任意结点出发都能扫描到整个链表6. 下面关于线性表的叙述错误的是(B )。(A)线性表采用顺序存储，必须占用一片地址连续的单元;45v1.0可编辑可修改（B）线性表采用顺序存储，便于进行插入和删除操作；（C）线性表采用链式存储，不必占用一片地址连续的单元；（D）线性表采用

9、链式存储，不便于进行插入和删除操作；7. 单链表中，增加一个头结点的目的是为了（C ）。（A）使单链表至少有一个结点（B）标识表结点中首结点的位置（C）方便运算的实现（D）说明单链表是线性表的链式存储& 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素， 则采用（D）存储方式最节省运算时间。（A）单链表（B）仅有头指针的单循环链表（C）双链表（D）仅有尾指针的单循环链表9.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省运算时间（ C ）。（A）单链表（B）顺序表（C）双链表（D）单循环链表三填空题1.带头结点的单链表 H

10、为空的条件是H-> next = NULL。1.非空单循环链表 L中*p是尾结点的条件是p->next = L。3. 在一个单链表中p所指结点之后插入一个由指针f所指结点，应执行s->next=_ p->next;禾廿p->next=s的操作。4. 在一个单链表中p所指结点之前插入一个由指针f所指结点，可执行以下操作：s->next=_ p->next;p_>n ext=s;t=p_>data;56v1.0可编辑可修改p->data= s->data ;s->data= t;四算法设计题1.已知带头结点的单链表L中的结点是

11、按整数值递增排列的，试写一算法，将值为x的结点插入到表L中，使得L仍然有序。并且分析算法的时间复杂度。package xiti;class Liiint data;Lii next;public Lii()data=0;public Lii( int id)data=id;public void display()"");class Lii_2public Lii first;public Lii_2()f irst= new Lii();67v1.0可编辑可修改public boolean isEmpty()return =null );public boolean in

12、sert_2(int id)Lii newnode = new Lii(id);Lii p=first;p=;while !=null &&一，=newno de;r eturn true ;public void listdisplay()Lii p=first;"显示链表：");while (p!= null )();p=;"*")public class Lpublic static void main(String args)78v1.0可编辑可修改Lii_2 s1= new Lii_2(); for (int i=1;i<

13、=9;i=i+2)(i)；()； ()；0 ljm k I口 ma k'_ Mu' * .(jt >' f ：-：.-=HJ-« | Ift- d FZ fHlF 7pW讨 Ja% * 亡t 27V-RJT0 耳4- -Ln n它冒nodpLii (id) jLn p»firat r whilen«xt.nextd.eita:l-r，next?newn -tdv newt=|- -newt; p nex t=nswn cda : return trua;)public void 113tdi3play ()(Lil p-flrst;s

14、yatem»put. print In (;whilep»display0 rp-pnest：39System.out.prinTin(;41 System.ott.print丄玖十十士 *士 ±* * *十”卜;42 J43 44 public cIabs L|piiblic static void! main (St rin? 口工g汨/Lii_2 31=new Lii_2 ();4 7forlint i=lri<=97i=i+2 J 4 日sl« ixisEir 2 (i);时间复杂度：O(ele num)2假设有两个已排序的单链表A和B,编

15、写一个函数将他们合并成一个链表C而不改变其排序性。package xiti1;class link88v1.0可编辑可修改intdata;JE A5 二 mitiw 雋出區 j 一|二-QEf 擄2 fr«tum tru*;AB A*AM聶尸fT叵12 82912 15 19 20 2330public itit get (in t index) *131link p-firatF03 2.if (p ! nullAA indejc>0) 10 14 17 21 2633int j-0：34while(pj<ind«xI35j+;10 12 14 15 17 1

16、9 20* -A- * -A- * -A- * -A- * ir 世* 舍 * 4r +21 23 26Hlp=pf13BJif (p.! =n.ull t3?r«turn p ,d-ata ;40)41r«turn Of42)43*public int Lengtli 0 电4link p-firatr45int i Q;46while £p-null4 7pp next ;4B1 + +J4 9)50return ij<J假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针，编写一个函数删除该结点的前趋结点。4.已知两个单链

17、表 A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B的交集C,要求C同样以元素递增的单链表形式存储。package xiti;intclass link public data;99v1.0可编辑可修改B AKjmi 菇 |._O WJH 罔 K 鬓耳:驻旦'旦 * 9-1- Efti，*61 T 3WF创祜年蜩苗E Qajbc Z SF7W m ,砂出狀冷R iRtt華谒M耳 耳示毬奏;10 12 15 ia *且示偿左:13 10 12 18 *10 12 IB *64 publi.u class ABC public stalLXC void iqa 1 n f S

18、 tr inq ?i rqn )lxiiltLls t A = mw linkLiat ); linkLis七 B = n«w linkLiat- ).; 丄丄nkList C = n«*r linkliDt )； A+ iM©rtB&ck(10| fA+ insert Back (12) tA* inaert&ackdS) ra, insert Back (16):a. liatoiaplay£>B* maert-Back (13) fB* insert Back (10) *tB* insert Back (12);色亠 ins

19、ert Back (18) ；!B. listDiaplay (> :C C intersection (A, B) jrC* liatDiplay C);pi )B2 设有一个双向链表，每个结点中除有prior、data和next域外，还有一个访问频度freq域，在链表被起用之前，该域其值初始化为零。每当在链表进行一次Locata(L,x)运算后,令值为x的结点中的freq域增1,并调整表中结点的次序，使其按访问频度的递减序列排列，以便使频繁访问的结点总是靠近表头。试写一个算法满足上述要求的Locata(L,x)算法。五上机实习题目1. 一元多项式的相加提示：(1) 一元多项式的表示问

20、题：对于任意一元多项式：12inR(X)= P 0+ P1X+ P2X+ + P iX+ + P nX可以抽象为一个由“系数 -指数”对构成的线性表，且线性表中各元素的指数项是递增的：P=( ( P0,0), ( P 1,1), ( P 2,2),，(Pn,n)(2 )用一个单链表表示上述线性表，结点结构为:1011v1.0可编辑可修改*指针域*/coef exp nexttypedef sturct node float coef;/* 系数域 */int exp;/* 指数域 */struct node* next; / Ploy Node;package 一元多项式的加法；import

21、一元多项式的加法.;public class Lin kedAdd public Node add(Elem e1,Elem e2)Node pre=();Node qre=();Node p=;Node q=;Node result=p;while(p!=null && q!=null)if<pre=p;p=;else if>Node temp=;=q;=p;1112v1.0可编辑可修改q=temp;else=+；if=O)一，p=;elsepre=p;P=；一，q=;if(q!=null)=q;return result;public static void m

22、ain( Stri ng args) Elem no de1= new Elem();(7,0);(12,3);(2,8);1213v1.0可编辑可修改(5,12);Elem no de2=new Elem();(4,1)；(6,3);(2,8);(5,20);(7,28);Lin kedAdd l=new Lin kedAdd();Node no de=(no de1, no de2);while (no de!=nu ll)"coef:"+"exp:"+;node=;package 一元多项式的加法；class Elempublic class Nodepublic int coef;/系数public int exp;/指数下一个节点public Node n ext =nu ll;public Node()1314v1.0可编辑可修改coef=0;exp=O;public Node(i nt coef,i nt exp)=coef;=exp;public Node first=new Node();添加节点public void in sert(i nt coef,i nt exp)Node node=new Node(coef,exp); if(first=null)=no de;els