数据结构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<x<=y>之间的所有元素,要求以较高的效率来实现。提示：可以先将顺序表中所有值在xy之间的元素置成一个特殊的值,并不立即删除它们,然后从最后向前依次扫描,发现具有特殊值的元素后,移动其后面的元素将其删除掉。4 线性表中有n个元素,每个元素是一个字符,现存于向量Rn中,试写一算法,使R中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间,元素移动次数最小。研545 线性表用顺序存储,设计一个算法,用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表a1, a2, , am, b1, b2, , bn 改变为：b1, b2, , bn , a1, a2, , am。五上机实习题目约瑟夫环问题约瑟夫环问题：设编号为1,2,3,n的n<n>0>个人按顺时针方向围坐一圈,每个人持有一个正整数密码。开始时任选一个正整数做为报数上限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<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<> publicstaticvoid yuesefu<int totalNum, int countNum> / 初始化人数 List<Integer> start = new ArrayList<Integer><> for <int i = 1; i <= totalNum; i+> start.add<i> /从第K个开始计数 int k = 0; while <start.size<> >0> k = k + countNum; /第m人的索引位置 k = k % <start.size<>> - 1; / 判断是否到队尾 if <k < 0> System.out.println<start.get<start.size<>-1>> start.remove<start.size<> - 1> k = 0; else System.out.println<start.get<k>> start.remove<k> 链式存储线性表一判断题1在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上不一定相邻。×2线性表的链式存储结构优于顺序存储结构。×3线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。4在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。×二单选题 <请从下列A,B,C,D选项中选择一项>1线性表是< A > 。<A> 一个有限序列,可以为空； <B> 一个有限序列,不能为空；<C> 一个无限序列,可以为空； <D> 一个无序序列,不能为空。2线性表采用链式存储时,其地址< D > 。<A> 必须是连续的； <B> 部分地址必须是连续的；<C> 一定是不连续的； <D> 连续与否均可以。3用链表表示线性表的优点是 C。<A>便于随机存取<B>花费的存储空间较顺序存储少<C>便于插入和删除<D>数据元素的物理顺序与逻辑顺序相同4.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素,则采用< D>存储方式最节省运算时间。<A>单链表<B>双链表<C>单循环链表<D>带头结点的双循环链表5 循环链表的主要优点是<D > 。<A>不在需要头指针了<B>已知某个结点的位置后,能够容易找到他的直接前趋<C>在进行插入、删除运算时,能更好的保证链表不断开<D>从表中的任意结点出发都能扫描到整个链表6 下面关于线性表的叙述错误的是< B>。(A) 线性表采用顺序存储,必须占用一片地址连续的单元；(B) 线性表采用顺序存储,便于进行插入和删除操作；(C) 线性表采用链式存储,不必占用一片地址连续的单元；(D) 线性表采用链式存储,不便于进行插入和删除操作；7 单链表中,增加一个头结点的目的是为了C。<A> 使单链表至少有一个结点 <B>标识表结点中首结点的位置C方便运算的实现 <D> 说明单链表是线性表的链式存储8 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用D 存储方式最节省运算时间。<A> 单链表 <B> 仅有头指针的单循环链表 <C> 双链表 <D> 仅有尾指针的单循环链表9 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用 存储方式最节省运算时间 C。<A> 单链表 <B> 顺序表 <C> 双链表 <D> 单循环链表三 填空题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 _;s->data=_t_;四 算法设计题1. 已知带头结点的单链表L中的结点是按整数值递增排列的,试写一算法,将值为x 的结点插入到表L中,使得L仍然有序。并且分析算法的时间复杂度。package xiti;class Liiint data; Lii next;public Lii<> data=0; public Lii<int id> data=id; publicvoid display<> System.out.print<data+" "> class Lii_2public Lii first;public Lii_2<> first=new Lii<> publicboolean isEmpty<>return <first.next=null> publicboolean insert_2<int id>Lii newnode =new Lii<id>Lii p=first;while<p.next!=null&&p.next.data<id>p=p.next;newnode.next=p.next;p.next=newnode;returntrue; publicvoid listdisplay<> Lii p=first; System.out.println<"显示链表：">while<p!=null> p.display<> p=p.next; System.out.println<> System.out.println<"*"> publicclass Lpublicstaticvoid main<String args> Lii_2 s1=new Lii_2<>for<int i=1;i<=9;i=i+2>s1.insert_2<i> s1.listdisplay<> s1.insert_2<2> s1.listdisplay<> 时间复杂度：O<elenum>2. 假设有两个已排序的单链表A和B,编写一个函数将他们合并成一个链表C而不改变其排序性。package xiti1;class linkint data;/数据域结点关键字 link next;/指针域指向下一结点public link<int id>/结点构造方法 data=id;/结点构造方法 publicvoid display<>/显示自身的数据域System.out.print<data+" ">class link_1link first;/单链表的头指针public link_1<>/构造方法first=null;/空单链表,头指针为空/从单链表最前面插入一个新结点,作为第一个结点publicboolean insert_1<int id>link newLink= new link<id> link p;if<first=null> first=newLink;else p=first;while<p.next!=null> p=p.next;p.next=newLink; returntrue;publicint get<int index>link p=first;if<p!=null&&index>=0>int j=0;while<p!=null&&j<index>j+;p=p.next;if<p!=null>return p.data;return 0;publicint Length<> link p=first;int i=0;while<p!=null>p=p.next;i+;return i;/显示全部链表publicvoid listdisplay<> link p=first; System.out.println<"显示链表：">while<p!=null> p.display<> p=p.next; System.out.println<> System.out.println<"*">publicclass AB publicstatic link_1 Merge<link_1 A,link_1 B > intl=A.Length<>+B.Length<>link_1 C=new link_1<>intj=0,iA=0,iB=0;while<iA<A.Length<>&&iB<B.Length<>>if<A.get<iA><B.get<iB>>C.insert_1<A.get<iA+>>elseC.insert_1<B.get<iB+>>for<iA<A.Length<>>C.insert_1<A.get<iA+>>for<iB<B.Length<>>C.insert_1<B.get<iB+>>return C; publicstaticvoid 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 publicint data;/数据域结点关键字public link next;/指针域指向下一结点public link<int id> /结点构造方法data = id;publicvoid Display<> / 显示自身的数据域System.out.print<data + " ">class linkList link first;/单链表的头指针public linkList<> /构造方法first = null;/空单链表,头指针为空/ 在单链表尾部插入一个新结点publicboolean 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所指结点的后面returntrue;publicvoid 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;publicclass ABC publicstaticvoid 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.exp<q.exp> pre=p; p=p.next; else if<p.exp>q.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> node2.insert<5,20> node2.insert<7,28> LinkedAdd l=new LinkedAdd<> Node node=l.add<node1, node2> while<node!=null> System.out.println<"coef:"+node.coef+" exp:"+node.exp> node=node.next; package 一元多项式的加法;class Elem public class Node public int coef;/系数 public int exp;/指数 public Node next=null;/下一个节点 public Node<> coef=0; exp=0; public Node<int coef,int exp> this.coef=coef; this.exp=exp; public Node first=new Node<> public void insert<int coef,int exp>/添加节点 Node node=new Node<coef,exp> if<first=null> first.next=node; else Node temp=first; while<temp.next!=null> temp=temp.next; temp.next=node; public Node getNode<> return first;
