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

（按照自己的情况选作部分习题，不要抄袭）第二章 习题顺序存储线性表一 判断题1线性表的逻辑顺序与存储顺序总是一致的。2顺序存储的线性表可以按序号随机存取。3顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。5在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。6在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。二 单选题 (请从下列A，B，C，D选项中选择一项)1线性表是( A ) 。(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 2对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ A ）个元素。 (A) n/2 (B) n+1/2 (C) n -1/2 (D) n 三 填空题1在顺序表中做插入操作时首先检查_表是否满了_。四 算法设计题1 设线性表存放在向量Aarrsize的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。2 已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同的元素。3 编写一个函数，从一给定的顺序表A中删除值在xy(x0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。package 算法设计;import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class YueSeFu public static void main(String args) Scanner scan = new Scanner(System.in); System.out.print(请输入总人数：); int totalNum = scan.nextInt(); System.out.print(请输入报数的大小：); int cycleNum = scan.nextInt(); yuesefu(totalNum, cycleNum); scan.close(); public static void yuesefu(int totalNum, int countNum) / 初始化人数 List start = new ArrayList(); for (int i = 1; i 0) k = k + countNum; /第m人的索引位置 k = k % (start.size() - 1; / 判断是否到队尾 if (k 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 _;s-data=_t_;四 算法设计题1. 已知带头结点的单链表L中的结点是按整数值递增排列的，试写一算法，将值为x 的结点插入到表L中，使得L仍然有序。并且分析算法的时间复杂度。package xiti;class Lii int data; Lii next;public Lii() data=0; public Lii(int id) data=id; public void display() System.out.print(data+ ); class Lii_2public Lii first; public Lii_2() first=new Lii(); public boolean isEmpty() return (first.next=null); public boolean insert_2(int id)Lii newnode =new Lii(id);Lii p=first;while(p.next!=null&p.next.dataid)p=p.next;newnode.next=p.next;p.next=newnode; return true; public void listdisplay() Lii p=first; System.out.println(显示链表：); while(p!=null) p.display(); p=p.next; System.out.println(); System.out.println(*); public class L public static void main(String args) Lii_2 s1=new Lii_2(); for(int i=1;i=0)int j=0;while(p!=null&jindex)j+;p=p.next;if(p!=null)return p.data;return 0;public int Length() link p=first;int i=0;while(p!=null)p=p.next;i+;return i;/显示全部链表public void listdisplay() link p=first; System.out.println(显示链表：); while(p!=null) p.display(); p=p.next; System.out.println(); System.out.println(*);public class AB public static link_1 Merge(link_1 A,link_1 B ) int l=A.Length()+B.Length();link_1 C=new link_1();int j=0,iA=0,iB=0;while(iAA.Length()&iBB.Length()if(A.get(iA)B.get(iB)C.insert_1(A.get(iA+);elseC.insert_1(B.get(iB+);for(;iAA.Length();)C.insert_1(A.get(iA+);for(;iBB.Length();)C.insert_1(B.get(iB+); return C; public static void main(String args)link_1 s1=new link_1();link_1 s2=new link_1();s1.insert_1(12);s1.insert_1(15);s1.insert_1(19);s1.insert_1(20);s1.insert_1(23);s1.listdisplay();s2.insert_1(10);s2.insert_1(14);s2.insert_1(17);s2.insert_1(21);s2.insert_1(26);s2.listdisplay();link_1 s3=Merge(s1,s2);s3.listdisplay();3. 假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针，编写一个函数删除该结点的前趋结点。4. 已知两个单链表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B的交集C，要求C同样以元素递增的单链表形式存储。package xiti;class link public int data;/数据域（结点关键字）public link next;/指针域（指向下一结点）public link(int id) /结点构造方法data = id;public void Display() / 显示自身的数据域System.out.print(data + );class linkList link first;/单链表的头指针public linkList() /构造方法first = null;/空单链表，头指针为空/ 在单链表尾部插入一个新结点public boolean insertBack(int id) link newlink= new link(id); /诞生新结点newlink4link p; /辅助结点指针if(first=null) first=newlink;else p=first; /指向第一结点while(p.next!=null) p=p.next; /把p移到最后一个结点p.next=newlink; /把新结点接在p所指结点的后面return true;public void listDisplay() / 显示链表link p = first; / 指向第一个结点System.out.println(显示链表：);while (p != null) p.Display(); / 显示结点p = p.next;System.out.println(*);public linkList interSection(linkList A, linkList B) linkList C;link pa, pb;C = new linkList();pa = A.first;pb = B.first;while (pa != null) while (pb != null) / 和B链表的每个元素遍历if(pa.data = pb.data)/ 相等的时候给C链表插入pa.fdC.insertBack(pa.data);pb = pb.next;pa = pa.next;pb = B.first;return C;public class ABC public static void main(String args) linkList A = new linkList();linkList B = new linkList();linkList C = new linkList();A.insertBack(10);A.insertBack(12);A.insertBack(15);A.insertBack(18);A.listDisplay();B.insertBack(13);B.insertBack(10);B.insertBack(12);B.insertBack(18);B.listDisplay();C = C.interSection(A, B);C.listDisplay();5. 设有一个双向链表，每个结点中除有prior、data和next域外，还有一个访问频度freq域，在链表被起用之前，该域其值初始化为零。每当在链表进行一次Locata(L,x)运算后，令值为x的结点中的freq域增1，并调整表中结点的次序，使其按访问频度的递减序列排列，以便使频繁访问的结点总是靠近表头。试写一个算法满足上述要求的Locata(L,x)算法。五 上机实习题目1 一元多项式的相加 提示：（1） 一元多项式的表示问题：对于任意一元多项式：Pn(x)= P0+ P1X1+ P2X2+ + PiXi+ + PnXn可以抽象为一个由“系数-指数”对构成的线性表，且线性表中各元素的指数项是递增的： P=( ( P0,0), ( P1,1), ( P2,2), , ( Pn,n) )(2 ) 用一个单链表表示上述线性表，结点结构为：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(Elem e1,Elem e2) Node pre=e1.getNode(); Node qre=e2.getNode(); Node p=pre.next; Node q=qre.next; Node result=p; while(p!=null & q!=null) if(p.expq.exp) Node temp=q.next; pre.next=q; q.next=p; q=temp; else p.coef=p.coef+q.coef; if(p.coef=0) pre.next=p.next; p=pre.next; else pre=p; p=p.next; qre.next=q.next; q=qre.next; if(q!=null) pre.next=q; return result; public static void main(String args) Elem node1=new Elem(); node1.insert(7,0); node1.insert(12,3); node1.insert(2,8); node1.insert(5,12); Elem node2=new Elem(); node2.insert(4,1); node2.insert(6,3); node2.insert(2,8)