数据结构Java版第二章复习题.doc

《数据结构Java版第二章复习题.doc》由会员分享，可在线阅读，更多相关《数据结构Java版第二章复习题.doc（16页珍藏版）》请在课桌文档上搜索。

1、第二章习题顺序存储线性表一判断题1线性表的逻辑顺序与存储顺序总是一致的。2顺序存储的线性表可以按序号随机存取。3顺序表的插入和删除操作不需要付出很大的时间代价,因为每次操作平均只有近一半的元素需要移动。4线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因此是属于同一数据对象。5在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上并不一定紧邻。6在线性表的顺序存储结构中,插入和删除时,移动元素的个数与该元素的位置有关。二单选题 1线性表是 。 一个有限序列,可以为空； 一个有限序列,不能为空； 一个无限序列,可以为空； 一个无序序列,不能为空。2对顺序存储的线性表,

2、设其长度为n,在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的A个元素。n/2 n+1/2 n -1/2 n 三 填空题1在顺序表中做插入操作时首先检查_表是否满了_。四 算法设计题1 设线性表存放在向量Aarrsize的前elenum个分量中,且递增有序。试写一算法,将x 插入到线性表的适当位置上,以保持线性表的有序性。并且分析算法的时间复杂度。2 已知一顺序表A,其元素值非递减有序排列,编写一个函数删除顺序表中多余的值相同的元素。3 编写一个函数,从一给定的顺序表A中删除值在xyx之间的所有元素,要求以较高的效率来实现。提示：可以先将顺序表中所有值在xy之间的元素置成

3、一个特殊的值,并不立即删除它们,然后从最后向前依次扫描,发现具有特殊值的元素后,移动其后面的元素将其删除掉。4 线性表中有n个元素,每个元素是一个字符,现存于向量Rn中,试写一算法,使R中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间,元素移动次数最小。研545 线性表用顺序存储,设计一个算法,用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表a1, a2, , am, b1, b2, , bn 改变为：b1, b2, , bn , a1, a2, , am。五上机实习题目约瑟夫环问题约瑟夫环问题：设编号为1,2,3,n的n0个人按顺时针方

4、向围坐一圈,每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m,从第一个人开始顺时针方向自1起顺序报数,报到m是停止报数,报m的人出列,将他的密码作为新的m值,从他的下一个人开始重新从1报数。如此下去,直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程,求出出列编号序列。package 算法设计;import java.util.ArrayList; import java.util.List; import java.util.Scanner; publicclass YueSeFu publicstaticvoid main Scanner scan = new

5、 Scanner; System.out.print; int totalNum = scan.nextInt; System.out.print; int cycleNum = scan.nextInt; yuesefu; scan.close; publicstaticvoid yuesefu / 初始化人数 List start = new ArrayList; for int i = 1; i start.add; /从第K个开始计数 int k = 0; while start.size 0 k = k + countNum; /第m人的索引位置 k = k % start.size

6、 - 1; / 判断是否到队尾 if k System.out.printlnstart.getstart.size-1; start.removestart.size - 1; k = 0; else System.out.printlnstart.get; start.remove; 链式存储线性表一判断题1在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上不一定相邻。2线性表的链式存储结构优于顺序存储结构。3线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。4在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。二单选题 1线性表是

7、 。 一个有限序列,可以为空； 一个有限序列,不能为空； 一个无限序列,可以为空； 一个无序序列,不能为空。2线性表采用链式存储时,其地址 。 必须是连续的； 部分地址必须是连续的； 一定是不连续的； 连续与否均可以。3用链表表示线性表的优点是 C。便于随机存取花费的存储空间较顺序存储少便于插入和删除数据元素的物理顺序与逻辑顺序相同4.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素,则采用存储方式最节省运算时间。单链表双链表单循环链表带头结点的双循环链表5 循环链表的主要优点是 。不在需要头指针了已知某个结点的位置后,能够容易找到他的直接前趋在进行插入、删除运算时,能更

8、好的保证链表不断开从表中的任意结点出发都能扫描到整个链表6 下面关于线性表的叙述错误的是。(A) 线性表采用顺序存储,必须占用一片地址连续的单元；(B) 线性表采用顺序存储,便于进行插入和删除操作；(C) 线性表采用链式存储,不必占用一片地址连续的单元；(D) 线性表采用链式存储,不便于进行插入和删除操作；7 单链表中,增加一个头结点的目的是为了C。 使单链表至少有一个结点 标识表结点中首结点的位置C方便运算的实现 说明单链表是线性表的链式存储8 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用D 存储方式最节省运算时间。 单链表 仅有头指针的单循环链表 双链表

9、 仅有尾指针的单循环链表9 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用 存储方式最节省运算时间 C。 单链表 顺序表 双链表 单循环链表三 填空题1带头结点的单链表H为空的条件是_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-next=s;t=p-data;p-data=_s-data

10、_;s-data=_t_;四 算法设计题1. 已知带头结点的单链表L中的结点是按整数值递增排列的,试写一算法,将值为x 的结点插入到表L中,使得L仍然有序。并且分析算法的时间复杂度。package xiti;class Liiint data; Lii next;public Lii data=0; public Lii data=id; publicvoid display System.out.print; class Lii_2public Lii first;public Lii_2 first=new Lii; publicboolean isEmptyreturn ; public

11、boolean insert_2Lii newnode =new Lii;Lii p=first;whilep.next!=null&p.next.datap=p.next;newnode.next=p.next;p.next=newnode;returntrue; publicvoid listdisplay Lii p=first; System.out.println;while p.display; p=p.next; System.out.println; System.out.println; publicclass Lpublicstaticvoid main Lii_2 s1=

12、new Lii_2;forint i=1;is1.insert_2; s1.listdisplay; s1.insert_2; s1.listdisplay; 时间复杂度：O2. 假设有两个已排序的单链表A和B,编写一个函数将他们合并成一个链表C而不改变其排序性。package xiti1;class linkint data;/数据域结点关键字 link next;/指针域指向下一结点public link/结点构造方法 data=id;/结点构造方法 publicvoid display/显示自身的数据域System.out.print;class link_1link first;/单链

13、表的头指针public link_1/构造方法first=null;/空单链表,头指针为空/从单链表最前面插入一个新结点,作为第一个结点publicboolean insert_1link newLink= new link; link p;if first=newLink;else p=first;while p=p.next;p.next=newLink; returntrue;publicint getlink p=first;if=0int j=0;whilep!=null&jj+;p=p.next;ifreturn p.data;return 0;publicint Length l

14、ink p=first;int i=0;whilep=p.next;i+;return i;/显示全部链表publicvoid listdisplay link p=first; System.out.println;while p.display; p=p.next; System.out.println; System.out.println;publicclass AB publicstatic link_1 Merge intl=A.Length+B.Length;link_1 C=new link_1;intj=0,iA=0,iB=0;whileiAA.Length&iBB.Leng

15、thifA.getB.getC.insert_1A.get;elseC.insert_1B.get;for;iAA.Length;C.insert_1A.get;for;iBB.Length;C.insert_1B.get;return C; publicstaticvoid mainlink_1 s1=new link_1;link_1 s2=new link_1;s1.insert_1;s1.insert_1;s1.insert_1;s1.insert_1;s1.insert_1;s1.listdisplay;s2.insert_1;s2.insert_1;s2.insert_1;s2.i

16、nsert_1;s2.insert_1;s2.listdisplay;link_1 s3=Merge;s3.listdisplay;3. 假设长度大于1的循环单链表中,既无头结点也无头指针,p为指向该链表中某一结点的指针,编写一个函数删除该结点的前趋结点。4. 已知两个单链表A和B分别表示两个集合,其元素递增排列,编写一个函数求出A和B的交集C,要求C同样以元素递增的单链表形式存储。package xiti;class link publicint data;/数据域结点关键字public link next;/指针域指向下一结点public link /结点构造方法data = id;pub

17、licvoid Display / 显示自身的数据域System.out.print;class linkList link first;/单链表的头指针public linkList /构造方法first = null;/空单链表,头指针为空/ 在单链表尾部插入一个新结点publicboolean insertBack link newlink= new link; /诞生新结点newlink4link p; /辅助结点指针if first=newlink;else p=first; /指向第一结点while p=p.next; /把p移到最后一个结点p.next=newlink; /把新结

18、点接在p所指结点的后面returntrue;publicvoid listDisplay / 显示链表link p = first; / 指向第一个结点System.out.println;while p.Display; / 显示结点p = p.next;System.out.println;public linkList interSection linkList C;link pa, pb;C = new linkList;pa = A.first;pb = B.first;while while / 和B链表的每个元素遍历if/ 相等的时候给C链表插入pa.fdC.insertBack

19、;pb = pb.next;pa = pa.next;pb = B.first;return C;publicclass ABC publicstaticvoid main linkList A = new linkList;linkList B = new linkList;linkList C = new linkList;A.insertBack;A.insertBack;A.insertBack;A.insertBack;A.listDisplay;B.insertBack;B.insertBack;B.insertBack;B.insertBack;B.listDisplay;C =

20、 C.interSection;C.listDisplay;5. 设有一个双向链表,每个结点中除有prior、data和next域外,还有一个访问频度freq域,在链表被起用之前,该域其值初始化为零。每当在链表进行一次Locata运算后,令值为x的结点中的freq域增1,并调整表中结点的次序,使其按访问频度的递减序列排列,以便使频繁访问的结点总是靠近表头。试写一个算法满足上述要求的Locata算法。五上机实习题目1 一元多项式的相加提示：（1） 一元多项式的表示问题：对于任意一元多项式：Pn= P0+ P1X1+ P2X2+ + PiXi+ + PnXn可以抽象为一个由系数-指数对构成的线性表

21、,且线性表中各元素的指数项是递增的：P= , , , , 用一个单链表表示上述线性表,结点结构为：coef exp next typedef sturct node float coef; /*系数域*/int exp; /*指数域*/ struct node *next; /*指针域*/ Ploy Node;package 一元多项式的加法;import 一元多项式的加法.Elem.Node;public class LinkedAdd public Node add Node pre=e1.getNode; Node qre=e2.getNode; Node p=pre.next; Nod

22、e q=qre.next; Node result=p; while ifp.exp pre=p; p=p.next; else ifq.exp Node temp=q.next; pre.next=q; q.next=p; q=temp; else p.coef=p.coef+q.coef; if pre.next=p.next; p=pre.next; else pre=p; p=p.next; qre.next=q.next; q=qre.next; if pre.next=q; return result; public static void main Elem node1=new

23、Elem; node1.insert; node1.insert; node1.insert; node1.insert; Elem node2=new Elem; node2.insert; node2.insert; node2.insert; node2.insert; node2.insert; LinkedAdd l=new LinkedAdd; Node node=l.add; while System.out.println; node=node.next; package 一元多项式的加法;class Elem public class Node public int coef

24、;/系数 public int exp;/指数 public Node next=null;/下一个节点 public Node coef=0; exp=0; public Node this.coef=coef; this.exp=exp; public Node first=new Node; public void insert/添加节点 Node node=new Node; if first.next=node; else Node temp=first; while temp=temp.next; temp.next=node; public Node getNode return first;