第2章 线性表习题参考答案.doc

习题二参考答案一、选择题1. 链式存储结构的最大优点是（ D ）。A.便于随机存取B.存储密度高 C.无需预分配空间D.便于进行插入和删除操作 2. 假设在顺序表a0,a1,an1中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是（ D ）。A. 106 B. 107 C.124 D.1283. 在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ A ）存储方式。A.顺序表B. 带头结点的单链表C.不带头结点的单链表D. 循环单链表4. 在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（ C ）存储方式。A. 顺序表B. 用头指针标识的循环单链表C. 用尾指针标识的循环单链表D. 双向链表5. 在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为S,则修改链的java语句序列是（ D ）。A. s.setNext(p); q.setNext(s); B. p.setNext(s.getNext(); s.setNext(p);C. q.setNext(s.getNext(); s.setNext(p); D. p.setNext(s); s.setNext(q);6. 在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ C ）。A. O(1) B. O(log2n) C. O(n) D. O(n2)7. 要将一个顺序表a0,a1,an-1中第i个数据元素ai(0in-1)删除，需要移动（ B ）个数据元素。A. i B. n-i-1 C. n-i D. n-i+18. 在带头结点的双向循环链表中的p结点之后插入一个新结点s，其修改链的java语句序列是（ D ）。A. p.setNext(s); s.setPrior(p); p.getNext().setPrior(s); s.setNext(p.getPrior();B. p.setNext(s); p.getNext().setPrior(s); s.setPrior(p); s.setNext(p.getNext();C. s.setPrior(p); s.setNext(p.getNext(); p.setNext(s); p.getNext().setPrior(s);D. s.setNext(p.getNext(); s.setPrior(p); p.getNext().setPrior(s); p.setNext(s);9. 顺序表的存储密度是（ B ），而单链表的存储密度是（ A ）。A小于1 B. 等于1 C. 大于1 D. 不能确定10. 对于图2.29所示的单链表，下列表达式值为真的是（ D ）。ABCE headDP1P2图2.29 单链表head的存储结构图A. head.getNext().getData()=C B. head.getData()=BC. P1.getData()=D D. P2.getNext()=null二、填空题1. 线性表是由n（n0）个数据元素所构成的 有限序列 ，其中n为数据元素的个数，称为线性表的 长度 ，n=0的线性表称为 空表 。2. 线性表中有且仅有一个开始结点和终端结点，除开始结点和终端结点之外，其它每一个数据元素有且仅有一个 前驱 ，有且仅有一个 后继 。3. 线性表通常采用 顺序存储 和 链式存储 两种存储结构。若线性表的长度确定或变化不大，则适合采用 顺序存储 存储结构进行存储。4. 在顺序表a0,a1,an-1中的第i(0in-1)个位置之前插入一个新的数据元素，会引起 n-i 个数据元素的移动操作。5. 在线性表的单链表存储结构中，每一个结点有两个域，一个是数据域，用于存储数据元素值本身，另一个是 指针域 ，用于存储后继结点的地址。6. 在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中则只能进行 顺序 存取。7. 顺序表中逻辑上相邻的数据元素，其物理位置 一定 相邻，而在单链表中逻辑上相邻的数据元素，其物理位置 不一定 相邻。8. 在仅设置了尾指针的循环链表中，访问第一个结点的时间复杂度是 O（1） 。9. 在含有n个结点的单链表中，若要删除一个指定的结点p，则首先必须找到 指定结点p的前驱 ，其时间复杂度为 O（n） 。10. 若将单链表中的最后一个结点的指针域值改为单链表中头结点的地址值，则这个链表就构成了 循环单链表 。三、算法设计题1. 编写一个顺序表类的成员函数，实现对顺序表就地逆置的操作。所谓逆置，就是把（a1,a2,an）变成（an,an-1,a1）；所谓就地，就是指逆置后的数据元素仍存储在原来顺序表的存储空间中，即不为逆置后的顺序表另外分配存储空间。参考答案:public void reverse() for (int i = 0,j=curLen-1; i j; i+,j-) Object temp = listElemi;listElemi = listElemj;listElemj = temp;2. 编写一个顺序表类的成员函数，实现对顺序表循环右移k位的操作。即原来顺序表为（a1,a2,an-k,an-k+1, an），循环向右移动k位后变成（an-k+1, an ,a1,a2,an-k）。要求时间复杂度为O（n）。参考答案:public void shit(int k) int n=curLen,p=0,i,j,l; Object temp; for(i=1;i=k;i+) if(n%i=0&k%i=0) /求n和k的最大公约数p p=i; for(i=0;ilistElem6, listElem6-listElem12, listElem12- listElem3, listElem3- listElem9, listElem9- listElem0. 第二条链: listElem1-listElem7, listElem7-listElem13, listElem13- listElem4, listElem4-listElem10, listElem10- listElem1. 第三条链: listElem2- listElem8, listElem8- listElem14, listElem14-listElem5, listElem5-listElem11, listElem11-listElem2.恰好使所有元素都右移一次.虽然未经数学证明,但相信上述规律应该是正确的.3. 编写一个单链表类的成员函数，实现在非递减的有序单链表中插入一个值为x的数据元素，并使单链表仍保持有序的操作。参考答案(方法一):public void insert(int x) Node p = head.getNext();/p指向首结点Node q = head;/ q用来记录p的前驱结点int temp;while (p != null) temp = (Integer) p.getData().intValue();if (temp x) q = p;p = p.getNext(); elsebreak;Node s = new Node(x); / 生成新结点s.setNext(p);/ 将s结点插入到单链表的q结点与p结点之间q.setNext(s);参考答案(方法二):public void insert(int x) Node p = head.getNext(); /p指向首结点while (p.getNext()!= null&(Integer) p.getNext().getData().intValue()x) p = p.getNext();Node s = new Node(x); / 生成新结点s.setNext(p.getNext();/ 将s结点插入到单链表的q结点与p结点之间p.setNext(s);4. 编写一个单链表类的成员函数，实现对带头结点的单链表就地逆置的操作。所谓逆置，就是把（a1,a2,an）变成（an,an-1,a1）；所谓就地，就是指逆置后的结点仍存储在原来单链表的存储空间中，只不过通过修改链来改变单链表中每一个结点之间的逻辑位置关系。参考答案:public void reverse() /实现对单链表就地逆置(采用的是头插法)Node p = head.getNext();head.setNext(null);Node q;while (p != null) q = p.getNext();p.setNext(head.getNext();head.setNext(p);p = q;5. 编写一个单链表类的成员函数，实现删除不带头结点的单链表中数据域值等于x的第一个结点的操作。若删除成功，则返回被删除结点的位置；否则，返回-1。参考答案: public int remove(Object x) Node p = head;/ 初始化,p指向首结点Node q=null; /q用来记录p的前驱结点 int j = 0; /j为计数器/ 从单链表中的首结点元素开始查找，直到p.getData()指向元素x或到达单链表的表尾while (p != null & !p.getData().equals(x) q=p; p = p.getNext();/ 指向下一个元素 +j;/ 计数器的值增1 if (p!=null&q=null) /删除的是单链表中的首结点 head=p.getNext(); else if (p != null) / 删除的是单链表中的非首结点 q.setNext(p.getNext(); else return -1;/值为x的结点在单链表中不存在 return j; 6. 编写一个单链表类的成员函数，实现删除带头结点的单链表中数据域值等于x的所有结点的操作。要求函数返回被删除结点的个数。参考答案:public int removeAll(Object x) Node p = head.getNext();/ 初始化,p指向首结点,j为计数器Node q = head; / 用来记录p的前驱结点int j = 0;/ 用来记录被删除结点的个数while (p != null) / 从单链表中的首结点开始对整个链表遍历一次if (p.getData().equals(x) q.setNext(p.getNext();+j;/ 计数器的值增1 elseq = p;p = p.getNext();/ 指向下一个元素return j;/ 返回被删除结点的个数7. 编写一个多项式类的成员函数，实现将一个用循环链表表示的稀疏多项式分解成两个多项式的操作，并使两个多项式中各自仅含奇次项或偶次项。要求利用原来循环链表中的存储空间构成这两个链表。参考答案:public CircleLinkList separatePolyn(CircleLinkList cList) CircleLinkList cList1 = new CircleLinkList();/ 含奇次项的多项式Node p1 = cList1.getHead();/ p2指向奇次项多项式的头结点CircleLinkList cList2 = new CircleLinkList();/ 含偶次项的多项式Node p2 = cList2.getHead();/ p2指向偶次项多项式的头结点Node p = cList.getHead().getNext();/ 原多项式的首结点while (p!=cList.getHead() PolynNode data = (PolynNode) p.getData();int expn = data.getExpn();if (expn % 2 != 0) / 加入奇次项多项式p1.setNext(p);p1 = p; else / 加入偶此项多项式p2.setNext(p);p2 = p;p = p.getNext();p1.setNext(cList1.getHead();p2.setNext(cList2.getHead();CircleLinkList polyns = cList1, cList2 ;return polyns;四、上机实践题1. 设计一个测试类，使其实际运行来测试顺序表中各成员函数的正确性。参考答案:package ch02Exercise;/顺序表类class SqList private Object listElem; / 线性表存储空间private int curLen; / 当前长度/ 顺序表的构造函数，构造一个存储空间容量为maxSize的线性表public SqList(int maxSize) curLen = 0; / 置顺序表的当前长度为0listElem = new ObjectmaxSize;/ 为顺序表分配maxSize个存储单元/ 将一个已经存在的线性表置成空表public void clear() curLen = 0; / 置顺序表的当前长度为0/ 判断当前线性表中数据元素个数是否为0,若为0则函数返回true，否则返回falsepublic boolean isEmpty() return curLen = 0;/ 求线性表中的数据元素个数并由函数返回其值public int length() return curLen; / 返回顺序表的当前长度/ 读取到线性表中的第i个数据元素并由函数返回其值。其中i取值范围为：0ilength()-1,如果i值不在此范围则抛出异常public Object get(int i) throws Exception if (i curLen - 1) / i小于0或者大于表长减1throw new Exception(第 + i + 个元素不存在); / 输出异常return listElemi; / 返回顺序表中第i个数据元素/ 在线性表的第i个数据元素之前插入一个值为x的数据元素。其中i取值范围为：0ilength()。如果i值不在此范围则抛出异常,当i=0时表示在表头插入一个数据元素x,当i=length()时表示在表尾插入一个数据元素xpublic void insert(int i, Object x) throws Exception if (curLen = listElem.length) / 判断顺序表是否已满throw new Exception(顺序表已满);/ 输出异常if (i curLen) / i小于0或者大于表长throw new Exception(插入位置不合理);/ 输出异常for (int j = curLen; j i; j-)listElemj = listElemj - 1;/ 插入位置及之后的元素后移listElemi = x; / 插入xcurLen+;/ 表长度增1/ 将线性表中第i个数据元素删除。其中i取值范围为：0ilength()- 1,如果i值不在此范围则抛出异常public void remove(int i) throws Exception if (i curLen - 1) / i小于1或者大于表长减1throw new Exception(删除位置不合理);/ 输出异常for (int j = i; j curLen - 1; j+)listElemj = listElemj + 1;/ 被删除元素之后的元素左移curLen-; / 表长度减1/ 返回线性表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1public int indexOf(Object x) int j = 0;/ j为计数器while (j curLen & !listElemj.equals(x)/ 从顺序表中的首结点开始查找，直到listElemj指向元素x或到达顺序表的表尾j+;if (j curLen)/ 判断j的位置是否位于表中return j; / 返回x元素在顺序表中的位置elsereturn -1;/ x元素不在顺序表中/ 输出线性表中的数据元素public void display() for (int j = 0; j curLen; j+)System.out.print(listElemj + );System.out.println();/ 换行/测试类public class Exercise2_4_1 public static void main(String args) throws Exception / -调用构造函数-SqList L = new SqList(10); / 构造一个10个存储空间的顺序表/ -调用 insert(int i, Object x)插入数据元素-for (int i = 0; i = 8; i+) / 对该顺序表的前9个元素进行赋值，分别为0、1、2.8L.insert(i, i);/ -调用length()求顺序表的长度-System.out.println(顺序表的长度: + L.length();/ 输出顺序表的长度/ -调用get(int i)取出第i个元素-System.out.println(顺序表中各个数据元素:);/ 输出L.display();/ -调用indexOf(Object x)查找x元素所在的位置-int order = L.indexOf(8);/ 求出数据元素8在顺序表中的位置if (order != -1)System.out.println(顺序表中值为8的数据元素的位置为： + order);/ 输出elseSystem.out.println(8不在此单链表中);/ -调用remove(int i)删除第i个数据元素-L.remove(5);/ 删除数据元素5System.out.println(顺序表中删除数据元素5后,表的长度: + L.length();/ 输出System.out.println(顺序表中删除数据元素5后，剩余的数据元素：);/ 输出L.display();/ -调用insert(int i, Object x)把数据元素x插入到i的位置-L.insert(5, 5);System.out.println(顺序表中在5的位置前插入数据元素5后，表的长度： + L.length();System.out.println(顺序表中在5的位置前插入数据元素5后，表中的数据元素：);L.display();/ -调用L.clear()将顺序表置空-L.clear();System.out.println(将顺序表置空后，再次打印表中的元素：);L.display();/ -调用isEmpty()判断顺序表是否为空-if (L.isEmpty()System.out.println(顺序表为空);elseSystem.out.println(顺序表不为空);运行结果:2. 设计一个测试类，使其实际运行来测试单链表中各成员函数的正确性。参考答案:package ch02Exercise;import ch02.Node;import java.util.Scanner;/链表类class LinkList private Node head;/ 单链表的头指针/ 单链表的构造函数public LinkList() head = new Node(); / 初始化头结点public LinkList(int n, boolean Order) throws Exception this();/ 初始化头结点if (Order) / 用尾插法顺序建立单链表create1(n);else/ 用头插法逆位序建立单链表create2(n);/ 用尾插法顺序建立单链表。其中n为该单链表的元素个数public void create1(int n) throws Exception Scanner sc = new Scanner(System.in);/ 构造用于输入的对象for (int j = 0; j n; j+)/ 输入n个元素的值insert(length(), sc.next();/ 生成新结点,插入到表尾/ 用头插法逆位序建立单链表。其中n为该单链表的元素个数public void create2(int n) throws Exception Scanner sc = new Scanner(System.in);/ 构造用于输入的对象for (int j = 0; j n; j+)/ 输入n个元素的值insert(0, sc.next();/ 生成新结点,插入到表头/ 将一个已经存在的带头结点单链表置成空表public void clear() head.setData(null);head.setNext(null);/ 判断当前带头结点的单链表是否为空public boolean isEmpty() return head.getNext() = null;/ 判断首结点是否为空/ 求带头结点单链表中的数据元素个数并由函数返回其值public int length() Node p = head.getNext();/ 初始化,p指向首结点,length为计数器int length = 0;while (p != null) / 从首结点向后查找，直到p为空p = p.getNext();/ 指向后继结点+length;/ 长度增1return length;/ 读取带头结点单链表中的第i个数据元素public Object get(int i) throws Exception Node p = head.getNext();/ 初始化,p指向首结点,j为计数器int j = 0;while (p != null & j i | p = null) / i小于0或者大于表长减1throw new Exception(第 + i + 个元素不存在);/ 输出异常return p.getData();/ 返回元素p/ 在带头结点单链表中第i个数据元素之前插入一个值为x的数据元素public void insert(int i, Object x) throws Exception Node p = head;/ 初始化p为头结点,j为计数器int j = -1; / 第i个结点前驱的位置while (p != null & j i - 1 | p = null) / i不合法throw new Exception(插入位置不合理);/ 输出异常Node s = new Node(x); / 生成新结点s.setNext(p.getNext();/ 插入单链表中p.setNext(s);/ 将线性表中第i个数据元素删除。其中i取值范围为：0ilength()- 1,如果i值不在此范围则抛出异常public void remove(int i) throws Exception Node p = head;/ p指向要删除结点的前驱结点int j = -1;while (p.getNext() != null & j i - 1 | p.getNext() = null) / i小于0或者大于表长减1throw new Exception(删除位置不合理);/ 输出异常p.setNext(p.getNext().getNext();/ 删除结点/ 在带头结点的单链表中查找值为x的元素，如果找到，则函数返回该元素在线性表中的位置，否则返回-1public int indexOf(Object x) Node p = head.getNext();/ 初始化,p指向首结点,j为计数器int j = 0;while (p != null & !p.getData().equals(x) / 从单链表中的首结点元素开始查找，直到p.getData()指向元素x或到达单链表的表尾p = p.getNext();/ 指向下一个元素+j;/ 计数器的值增1if (p != null)/ 如果p指向表中的某一元素return j;/ 返回x元素在顺序表中的位置elsereturn -1;/ x元素不在顺序表中/ 输出线性表中的数据元素public void display() Node node = head.getNext();/ 取出带头结点的单链表中的首结点元素while (node != null) System.out.print(node.getData() + );/ 输出数据元素的值node = node.getNext();/ 取下一个结点System.out.println();/ 换行public Node getHead() return head;public void setHead(Node head) this.head = head;/测试类public class Exercise2_4_2 public static void main(String args) throws Exception / -调用create(int n)从表尾到表头逆向建立单链表-System.out.println(请输入3个单链表中的数据元素：);LinkList L = new LinkList(3, true);/ 从表头到表尾顺序建立一个表长为3的单链表System.out.println(单链表中各个数据元素：);L.display(); / 输出单链表中所有的数据元素/ -调用length()求顺序表的长度-System.out.println(单链表的长度: + L.length();/ 输出顺序表的长度/ -调用get(int i)取出第i个元素-if (L.get(2) != null)/ 取第二个元素System.out.println(单链表中第2个元素: + L.get(2);/ -调用indexOf(Object x)查找x元素所在的位置-int order = L.indexOf(c);/ 求出数据元素字符串c在顺序表中的位置if (order != -1)System.out.println(单链表中值为字符串c的数据元素的位置为： + order); elseSystem.out.println(字符c不在此单链表中);/ -调用remove(int i)删除数据元素-L.remove(2); / 删除第二个数据元素System.out.println(删除第二个数据元素后单链表中各个数据元素：);L.display();/ -调用 insert(int i, Object x)插入数据元素-L.insert(2, d);/ 在单链表的第三个位置插入数据元素dSystem.out.println(在2的位置插入数据元素d后单链表中各个数据元素：);L.display(); / 输出单链表中所有的数据元素/ -调用L.clear()将顺序表置空-L.clear();System.out.println(将单链表置空后，再次打印表中的元素:);/ -调用isEmpty()判断顺序表是否为空-if (L.isEmpty()System.out.println(单链表为空);else System.out.println(单链表不为空,单链表中各个数据元素：);L.display();运行结果:3. 设计一个不带头结点的单链表类，要求：(1) 编写不带头结点的单链表类中的成员函数，包括：求线性表的长度、插入、删除和取结点值的操作函数。(2) 设计一个测试主函数，使其实际运行来验证类中各成员函数的正确性。参考答案:package ch02Exercise;import ch02.Node;/不带头结点的单链表类class LinkList2 private Node head;/ 单链表的首结点指针/ 构造函数public LinkList2() head = null;/ 将一个已经存在的单链表置成空表public void clear() head = null;/ 判断当前单链表是否为空public boolean isEmpty() return head =null;/ 求单链表中的数据元素个数并由函数返回其值public int length() Node p = head;/ 初始化,p指向首结点,length为计数器int length = 0;while (p != null) / 从首结点向后查找，直到p为空p = p.getNext();/ 指向后继结点+length;/ 长度增1return length;/ 读取单链表中的第i个数据元素public Object get(int i) throws Exception Node p = head;/ 初始化,p指向首结点,j为计数器int j = 0;while (p != null & j i | p = null) / i小于0或者大于表长减1throw new Exception(第 + i + 个元素不存在);/ 输出异常return p.getData();/ 返回元素p/ 在单链表中第i个数据元素之前插入一个值为x的数据元素public void insert(int i, Object x) throws Exception Node s = new Node(x);if (i = 0) / 插入位置为表头s.setNext(head);head = s;return;Node p = head;int j = 0;/ 第i个结点前驱的位置while (p != null & j i - 1 | p = null)throw new Exception(插入位置不合理);/ 插入位置为表的中间或表尾s.setNext(p.getNext();p.setNext(s);/ 将线性表中第i个数据元素删除。其中i取值范围为：0ilength()- 1,如果i值不在此范围则抛出异常public void remove(int i) throws Exception Node p = head;/ 初始化p为首结点,j为计数器Node q = null; / 用来记录p的前驱结点int j = 0;while (p != null & j i | p = null) / i小于0或者大于表长减1throw new Exception(删除位置不合理);/ 输出异常if (q = null)head = null;/ 删除首结点elseq.setNext(p.getNext();/ 删除其他结点/ 在带头结点的单链表中查找值为x的元素，如果找到，则函数返回该元素在线性表中的位置，否则返回-1public int indexOf(Object x) Node p = head;/ 初始化,p指向首结点,j为计数器int j = 0;while (p != null & !p.getData().equals(x) / 从单链表中的首结点元素开始查找，直到p.getData()指向元素x或到达单链表的表尾p = p.getNext();/ 指向下一个元素+j;/ 计数器的值增1if (p != null)/ 如果p指向表中的某一元素return j;/ 返回x元素在顺序表中的位置elsereturn -1;/ x元素不在顺序表中/ 输出线性表中的数据元素public void display() Node node = head;/ 取出带头结点的单链表中的首结点元素while (node != null) System.out.print(node.getData() + );/ 输出数据元素的值node = node.getNext();/ 取下一个结点System.out.println();/ 换行/测试类public class Exercise2_4_3 public static void main(String args) throws Exception / -初始化单链表中各个元素-LinkList2 L = new LinkList2();for (int i = 0; i = 8; i+)L.insert(i, i);System.out.println(单链表中各个数据元素：);L.display(); / 输出单链表中所有的数据元素/ -调用length()求顺序表的长度-System.