第2章 线性表习题参考答案
习题二参考答案
一、选择题
1.链式存储结构的最大优点是（ D ）。
A.便于随机存取
B.存储密度高
C.无需预分配空间
D.便于进行插入和删除操作
2.假设在顺序表{a0,a1,……,a n－1}中，每一个数据元素所占的存储单元的数目为4，且第0
个数据元素的存储地址为100，则第7个数据元素的存储地址是（ D ）。
A.106
B. 107
C.124
D.128
3.在线性表中若经常要存取第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,……,a n-1}中第i个数据元素a i(0≤i≤n-1)删除，需要移动（ B ）
个数据元素。
A.i
B. n-i-1
C. n-i
D. n-i+1
8.在带头结点的双向循环链表中的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 ）。
图2.29 单链表head的存储结构图
A. head.getNext().getData()=='C'
B. head.getData()=='B'
C. P1.getData()==’D’
D. P2.getNext()==null
二、填空题
1.线性表是由n（n≥0）个数据元素所构成的有限序列，其中n为数据元素的个数，称
为线性表的长度，n=0的线性表称为空表。
2.线性表中有且仅有一个开始结点和终端结点，除开始结点和终端结点之外，其它每一个
数据元素有且仅有一个前驱，有且仅有一个后继。
3.线性表通常采用顺序存储和链式存储两种存储结构。若线性表的长度确定或变化不
大，则适合采用顺序存储存储结构进行存储。
4.在顺序表{a0,a1,……,a n-1}中的第i(0≤i≤n-1)个位置之前插入一个新的数据元素，会引
起 n-i 个数据元素的移动操作。
5.在线性表的单链表存储结构中，每一个结点有两个域，一个是数据域，用于存储数据元
素值本身，另一个是指针域，用于存储后继结点的地址。
6.在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中则只能进行
顺序存取。
7.顺序表中逻辑上相邻的数据元素，其物理位置一定相邻，而在单链表中逻辑上相邻的
数据元素，其物理位置不一定相邻。
8.在仅设置了尾指针的循环链表中，访问第一个结点的时间复杂度是 O（1）。
9.在含有n个结点的单链表中，若要删除一个指定的结点p，则首先必须找到指定结点p
的前驱，其时间复杂度为 O（n）。
10.若将单链表中的最后一个结点的指针域值改为单链表中头结点的地址值，则这个链表就
构成了循环单链表。
三、算法设计题
1.编写一个顺序表类的成员函数，实现对顺序表就地逆置的操作。所谓逆置，就是把
（a1,a2,…,a n）变成（a n,a n-1,…,a1）；所谓就地，就是指逆置后的数据元素仍存储在原来顺序表的存储空间中，即不为逆置后的顺序表另外分配存储空间。
参考答案:
public void reverse() {
for (int i = 0,j=curLen-1; i < j; i++,j--) {
Object temp = listElem[i];
listElem[i] = listElem[j];
listElem[j] = temp;
}
}
2.编写一个顺序表类的成员函数，实现对顺序表循环右移k位的操作。即原来顺序表为
（a1,a2,…,a n-k,a n-k+1,…, a n），循环向右移动k位后变成（a n-k+1,…, a n ,a1,a2,…,a n-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;i j=i; l=(i+n-k)%n; temp=listElem[i]; while(l!=i){ listElem[j]=listElem[l]; j=l; l=(j+n-k)%n; }// 循环右移一步 listElem[j]=temp; } } 分析： 要把数组listElem的元素循环右移k位,则listElem[0]移至listElem[k], listElem[k]移至listElem[2k]......直到最终回到listElem[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以listElem[0], listElem[1],... listElem[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别 处在p个"循环链"上面.举例如下: n=15,k=6,则p=3. 第一条链: listElem[0]->listElem[6], listElem[6]->listElem[12], listElem[12]-> listElem[3], listElem[3]-> listElem[9], listElem[9]-> listElem[0]. 第二条链: listElem[1]->listElem[7], listElem[7]->listElem[13], listElem[13]-> listElem[4], listElem[4]->listElem[10], listElem[10]-> listElem[1]. 第三条链: listElem[2]-> listElem[8], listElem[8]-> listElem[14], listElem[14]->listElem[5], listElem[5]->listElem[11], listElem[11]->listElem[2]. 恰好使所有元素都右移一次. 虽然未经数学证明,但相信上述规律应该是正确的. 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(); } else break; } 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() } Node s = new Node(x); // 生成新结点 s.setNext(p.getNext());// 将s结点插入到单链表的q结点与p结点之间 p.setNext(s); } 4.编写一个单链表类的成员函数，实现对带头结点的单链表就地逆置的操作。所谓逆置， 就是把（a1,a2,…,a n）变成（a n,a n-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 } else q = 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; // 置顺序表的当前长度为0 listElem = new Object[maxSize];// 为顺序表分配maxSize个存储单元} // 将一个已经存在的线性表置成空表 public void clear() { curLen = 0; // 置顺序表的当前长度为0 } // 判断当前线性表中数据元素个数是否为0,若为0则函数返回true，否则返回false public boolean isEmpty() { return curLen == 0; } // 求线性表中的数据元素个数并由函数返回其值 public int length() { return curLen; // 返回顺序表的当前长度 } // 读取到线性表中的第i个数据元素并由函数返回其值。其中i取值范围为：0≤i≤length()-1,如果i值不在此范围则抛出异常 public Object get(int i) throws Exception { if (i < 0 || i > curLen - 1) // i小于0或者大于表长减1 throw new Exception("第" + i + "个元素不存在"); // 输出异常 return listElem[i]; // 返回顺序表中第i个数据元素 } // 在线性表的第i个数据元素之前插入一个值为x的数据元素。其中i取值范围为：0≤i≤length()。如果i值不在此范围则抛出异常,当i=0时表示在表头插入一个数据元素x,当i=length()时表示在表尾插入一个数据元素x public void insert(int i, Object x) throws Exception { if (curLen == listElem.length) // 判断顺序表是否已满 throw new Exception("顺序表已满");// 输出异常 if (i < 0 || i > curLen) // i小于0或者大于表长 throw new Exception("插入位置不合理");// 输出异常 for (int j = curLen; j > i; j--) listElem[j] = listElem[j - 1];// 插入位置及之后的元素后移 listElem[i] = x; // 插入x curLen++;// 表长度增1 } // 将线性表中第i个数据元素删除。其中i取值范围为：0≤i≤length()- 1,如果i 值不在此范围则抛出异常 public void remove(int i) throws Exception { if (i < 0 || i > curLen - 1) // i小于1或者大于表长减1 throw new Exception("删除位置不合理");// 输出异常 for (int j = i; j < curLen - 1; j++) listElem[j] = listElem[j + 1];// 被删除元素之后的元素左移 curLen--; // 表长度减1 } // 返回线性表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1 public int indexOf(Object x) { int j = 0;// j为计数器 while (j < curLen && !listElem[j].equals(x)) // 从顺序表中的首结点开始查找，直到listElem[j]指向元素x或到达顺序表的表尾 j++; if (j < curLen)// 判断j的位置是否位于表中 return j; // 返回x元素在顺序表中的位置 else return -1;// x元素不在顺序表中 } // 输出线性表中的数据元素 public void display() { for (int j = 0; j < curLen; j++) System.out.print(listElem[j] + " "); 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 (8) L.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);// 输出else System.out.println("8不在此单链表中"); // --------调用remove(int i)删除第i个数据元素-------- L.remove(5);// 删除数据元素5 System.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("顺序表为空"); else System.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;// 长度增1 } return length; } // 读取带头结点单链表中的第i个数据元素 public Object get(int i) throws Exception { Node p = head.getNext();// 初始化,p指向首结点,j为计数器 int j = 0; while (p != null && j < i) {// 从首结点向后查找，直到p指向第i个元素或p为空 p = p.getNext();// 指向后继结点 ++j;// 计数器的值增1 } if (j > i || p == null) { // i小于0或者大于表长减1 throw 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) {// 寻找i个结点的前驱 p = p.getNext(); ++j;// 计数器的值增1 } if (j > i - 1 || p == null) // i不合法 throw new Exception("插入位置不合理");// 输出异常 Node s = new Node(x); // 生成新结点 s.setNext(p.getNext());// 插入单链表中 p.setNext(s); } // 将线性表中第i个数据元素删除。其中i取值范围为：0≤i≤length()- 1,如果i 值不在此范围则抛出异常 public void remove(int i) throws Exception { Node p = head;// p指向要删除结点的前驱结点 int j = -1; while (p.getNext() != null && j < i - 1) {// 寻找i个结点的前驱p = p.getNext(); ++j;// 计数器的值增1 } if (j > i - 1 || p.getNext() == null) { // i小于0或者大于表长减1 throw new Exception("删除位置不合理");// 输出异常 } p.setNext(p.getNext().getNext());// 删除结点 } // 在带头结点的单链表中查找值为x的元素，如果找到，则函数返回该元素在线性表中的位置，否则返回-1 public 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;// 计数器的值增1 } if (p != null)// 如果p指向表中的某一元素 return j;// 返回x元素在顺序表中的位置 else return -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); else System.out.println("字符'c'不在此单链表中"); // --------调用remove(int i)删除数据元素-------- L.remove(2); // 删除第二个数据元素 System.out.println("删除第二个数据元素后单链表中各个数据元素："); L.display(); // --------调用 insert(int i, Object x)插入数据元素-------- L.insert(2, 'd');// 在单链表的第三个位置插入数据元素d System.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;// 长度增1 } return length; } // 读取单链表中的第i个数据元素 public Object get(int i) throws Exception { Node p = head;// 初始化,p指向首结点,j为计数器 int j = 0; while (p != null && j < i) {// 从首结点向后查找，直到p指向第i个元素或p为空p = p.getNext();// 指向后继结点 ++j;// 计数器的值增1 } if (j > i || p == null) // i小于0或者大于表长减1 throw 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) {// 寻找i个结点的前驱 p = p.getNext(); ++j; } if (j > i - 1 || p == null) throw new Exception("插入位置不合理"); // 插入位置为表的中间或表尾 s.setNext(p.getNext()); p.setNext(s); } // 将线性表中第i个数据元素删除。其中i取值范围为：0≤i≤length()- 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) {// 寻找i个结点 q = p; p = p.getNext(); ++j;// 计数器的值增1 } if (j > i || p == null) // i小于0或者大于表长减1 throw new Exception("删除位置不合理");// 输出异常 if (q == null) head = null;// 删除首结点 else q.setNext(p.getNext());// 删除其他结点 } // 在带头结点的单链表中查找值为x的元素，如果找到，则函数返回该元素在线性表中的位置，否则返回-1 public 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;// 计数器的值增1 } if (p != null)// 如果p指向表中的某一元素 return j;// 返回x元素在顺序表中的位置 else return -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.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); else System.out.println("字符'c'不在此单链表中"); // --------调用remove(int i)删除数据元素-------- L.remove(2); // 删除第二个数据元素 System.out.println("删除第二个数据元素后单链表中各个数据元素："); L.display(); // --------调用 insert(int i, Object x)插入数据元素-------- L.insert(2, 'd');// 在单链表的第三个位置插入数据元素d System.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(); } } } 4.设计一个带头结点的双向循环链表类，要求： (1)编写带头结点的双向循环链表类中的成员函数，包括：求线性表的长度、插入、删 除和取结点值的操作函数。 (2)设计一个测试主函数，使其实际运行来验证类中各成员函数的正确性。 参考答案: package ch02Exercise; import java.util.Scanner; //双向链表的结点类 class DuLNode { private Object data;// 存放结点值 private DuLNode prior; // 前驱结点的引用 private DuLNode next; // 后继结点的引用 public DuLNode() {// 无参数时的构造函数 this(null); } public DuLNode(Object data) {// 构造值为data的结点 this.data = data; this.prior = null; this.next = null; } public Object getData() { return data; } public DuLNode getNext() { return next; } public DuLNode getPrior() { return prior; } public void setData(Object data) { this.data = data; } public void setNext(DuLNode next) { this.next = next; } public void setPrior(DuLNode prior) { this.prior = prior; } } //双向链表类 class DuLinkList { private DuLNode head;// 双向循环链表的头结点 // 双向链表的构造函数 public DuLinkList() { head = new DuLNode(); // 初始化头结点 head.setPrior(head);// 初始化头结点的前驱和后继 head.setNext(head); } // 从表尾到表头逆向建立双向链表的算法。其中n为该双向链表的元素个数public DuLinkList(int n) throws Exception { this(); Scanner sc = new Scanner(System.in);// 构造用于输入的对象 for (int j = 0; j < n; j++) insert(0, sc.next());// 生成新结点,插入到表头 } // 在双向循环链表的第i个数据元素之前插入一个值为x的数据元素，i等于表长时，p 指向头结点；i大于表长时，p=NULL。 // 其中i取值范围为：0≤i≤length()。当i=0时表示在表头插入一个数据元素x,当i=length()时表示在表尾插入一个数据元素x public void insert(int i, Object x) throws Exception { DuLNode p = head.getNext();// 初始化,p指向首结点,j为计数器 int j = 0; while (!p.equals(head) && j < i) {// 寻找插入位置i p = p.getNext();// 指向后继结点 ++j;// 计数器的值增1 } if (j != i && !p.equals(head)) // i小于0或者大于表长 throw new Exception("插入位置不合理");// 输出异常 DuLNode s = new DuLNode(x);// 生成新结点 p.getPrior().setNext(s); s.setPrior(p.getPrior()); s.setNext(p); p.setPrior(s); } // 将双向循环链表中第i个数据元素删除。其中i 取值范围为：0≤i≤ength()-1 public void remove(int i) throws Exception { DuLNode p = head.getNext();// 初始化,p指向首节点结点,j为计数器 int j = 0; while (!p.equals(head) && j < i) {// 寻找删除位置i p = p.getNext();// 指向后继结点 ++j;// 计数器的值增1 } if (j != i) // i小于0或者大于表长减1 throw new Exception("删除位置不合理");// 输出异常 p.getPrior().setNext(p.getNext()); p.getNext().setPrior(p.getPrior()); } // 将一个已经存在的双向循环链表置成空表 public void clear() { 2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 Status OrderListInsert-sq(SqList va, ElemType x) { //将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法1) if (va.length==va.listsize){ newbase=(ElemType *)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); va.elem=newbase; va.listsize+=LISTINCREMENT; }//当前存储空间已满，增加分配空间 if (!va.length) {va.elem[0]=x; ++va.length; return OK;} q=&(va.elem[0]); while (*q<=x)&&(q<=&(va.elem[va.length-1])) ++q; //查找插入位置 for (p=&(va.elem[va.length-1]); p>=q; --p) *(p+1)=*p; *q=x; ++va.length; return OK; }//OrderListInsert-sq Status OrderListInsert-sq(SqList va, ElemType x) { //将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法2) if (va.length==va.listsize){ newbase=(ElemType *)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); va.elem=newbase; va.listsize+=LISTINCREMENT; }//当前存储空间已满，增加分配空间 if (!va.length) {va.elem[0]=x; ++va.length; return OK;} p=&(va.elem[va.length-1]); while (P>=&(va.elem[0])&&*p>x) {*(p+1)=*p; --p;} *(p+1)=x; ++va.length; 第二章线性表作业 一、选择题 1．下述哪一条是顺序存储结构的优点？（） A．存储密度大B．插入运算方便 C．删除运算方便D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（）的有限序列（n>0）。 A．表元素B．字符C．数据元素D．数据项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。 A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。 A．单链表B．双链表C．单循环链表D．带头结点的双循环链表 8. 静态链表中指针表示的是（）. A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址 9. 链表不具有的特点是（） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（） 第二章线性表练习题 一、选择题 1.线性表是具有n个的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 E、信息项 2.线性表的静态链表存储结构与顺序存储结构相比优点是。 A、所有的操作算法实现简单 B、便于随机存储 C、便于插入和删除 D、便于利用零散的存储器空间 3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为。 A、O(log2n) B、O(1) C、O(n) D、O(n2) 4.（1）静态链表既有顺序存储的特点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关； （2）静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加；（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是。 A、（1）、（2） B、（1） C、（1）、（2）、（3） D、（2） 6.在双向链表存储结构中，删除p所指的结点时须修改指针。 A、p－＞next－＞prior=p－＞prior; p－＞prior－＞next=p－＞next; B、p－＞next=p－＞next－＞next;p－＞next－＞prior=p; C、p－＞prior－＞next=p;p－＞prior=p－＞prior－＞prior; D、p－＞prior=p－＞next－＞next;p－＞next=p－＞prior－＞prior; 7.在双向循环链表中，在P指针所指的结点后插入q所指向的新结点，其修改指针的操作是。 A、p－＞next=q; q－＞prior=p;p－＞next－＞prior=q;q－＞next=q; B、p－＞next=q;p－＞next－＞prior=q;q－＞prior=p;q－＞next=p－＞next; C、q－＞prior=p; q－＞next=p－＞next; p－＞next－＞prior=q; p－＞next=q; D、q－＞next=p－＞next;q－＞prior=p;p－＞next=q;p－＞next=q; 8.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。 A、 n b、2n－1 c、2n d、n－1 9.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动个元素。 A、n－i B、n－i+1 C、n－i－1 D、i 10.线性表L=(a1，a2,……an)，下列说法正确的是。 A、每个元素有有一个直接前驱和一个直接后继 B、线性表中至少有一个元素 C、表中诸元素的排列必须是由小到大或由大到小。 D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 11.对单链表表示法，以下说法错误的是。 A、数据域用于存储线性表的一个数据元素 B、指针域(或链域)用于存放一指向本结点所含数据元素的直接后继所在结点的指针 C、所有数据通过指针的链接而组织成单链表 D、NULL称为空指针，它不指向任何结点只起标志作用 第2章线性表 一选择题 1．下述哪一条是顺序存储结构的优点？（ A ） A．存储密度大 B．插入运算方便 C．删除运算方 便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（ B ）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元 素 D．数据项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 AHA12GAGGAGAGGAFFFFAFAF A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链 表 C．双链表D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 AHA12GAGGAGAGGAFFFFAFAF A．单链表 B．双链表 C．单循环链 表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（ BC ）. A．内存地址 B．数组下标 C．下一元素地址D．左、右孩子地址 9. 链表不具有的特点是（ C ） A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（ BC ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 AHA12GAGGAGAGGAFFFFAFAF 第二章线性表 1、描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。 2、对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。(1)定位到第i 个结点a i ； (2)定位到第i 个结点的前驱a i-1； (3)定位到尾结点； (4)定位到尾结点的前驱。 3、已知L 是有表头结点的单链表，且P 结点既不是首元结点，也不是尾结点，试写出实现下列功能的语句序列。 (1)在P 结点后插入S 结点；(2)在P 结点前插入S 结点；(3)在表首插入S 结点；(4)在表尾插入S 结点 . p=head; p=head; j=0; while ( p && jnext; j++;} p=head; j=0; while ( p && j 4、设计算法：在顺序表中删除值为e 的元素，删除成功，返回1；否则，返回0。 5、设计一个算法，将一个带头节点的数据域依次为a 1，a 2，…，a n （n ≥3）的单链表的所有节点逆置，即第一个节点的数据域变为a n ，…，最后一个节点的数据域为a 1。（注意：先用自然语言描述算法基本思想，然后用类C++语言描述） int Sqlist 第2章线性表 班级学号__________-姓名 一、判断正误 （×）1. 链表的每个结点中都恰好包含一个指针。 链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。 （×）2. 链表的物理存储结构具有同链表一样的顺序。 链表的存储结构特点是无序，而链表的示意图有序。 （×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 链表的结点不会移动，只是指针内容改变。 （×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。 （×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” （×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 （×）7. 线性表在物理存储空间中也一定是连续的。 线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 （×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。 （×）9. 顺序存储方式只能用于存储线性结构。 顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如 完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍） （×）10. 线性表的逻辑顺序与存储顺序总是一致的。 理由同7。链式存储就无需一致。 二、单项选择题 （C ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（ B ）2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120 （ A ）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： （A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n） （C）删除第i个结点（1≤i≤n） （D）将n个结点从小到大排序 （ B ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8 （B）63.5 （C）63 （D）7 （ A ）5. 链式存储的存储结构所占存储空间： 第二章线性表 2.1 填空题 (1)一半插入或删除的位置 (2)静态动态 (3)一定不一定 (4)头指针头结点的next 前一个元素的next 2.2 选择题 (1)A (2) DA GKHDA EL IAF IFA(IDA) (3)D (4)D (5) D 2.3 头指针：在带头结点的链表中，头指针存储头结点的地址；在不带头结点的链表中，头指针存放第一个元素结点的地址； 头结点：为了操作方便，在第一个元素结点前申请一个结点，其指针域存放第一个元素结点的地址，数据域可以什么都不放； 首元素结点：第一个元素的结点。 2.4已知顺序表L递增有序，写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 void InserList(SeqList *L,ElemType x) { int i=L->last; if(L->last>=MAXSIZE-1) return FALSE; //顺序表已满 while(i>=0 && L->elem[i]>x) { L->elem[i+1]=L->elem[i]; i--; } L->elem[i+1]=x; L->last++; } 2.5 删除顺序表中从i开始的k个元素 int DelList(SeqList *L,int i,int k) { int j,l; if(i<=0||i>L->last) {printf("The Initial Position is Error!"); return 0;} if(k<=0) return 1; /*No Need to Delete*/ if(i+k-2>=L->last) L->last=L->last-k; /*modify the length*/ 第2章线性表习题解答 第2章习题 (2) 第2章习题 2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？ 【解】 //用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType; typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList; //初始化 void initialList(seqList &S) { https://www.wendangku.net/doc/2f6024868.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.wendangku.net/doc/2f6024868.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.wendangku.net/doc/2f6024868.html,st+1) //i为元素编号，有效范围在https://www.wendangku.net/doc/2f6024868.html,st+1之间 return false; else { x=S.data[i-1]; return true; } } //查找元素x，成功：返回元素编号；失败：返回0 int listLocate(seqList S,elementType x) { int i; for(i=0;i<=https://www.wendangku.net/doc/2f6024868.html,st;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出 } return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i) 第二章测试试题 班级：学号：姓名：成绩： 一、选择题（每小题5分） 1.线性表是( A )。 A一个有限序列，可以为空；B一个有限序列，不能为空； C一个无限序列，可以为空；D一个无序序列，不能为空。 2.用链表表示线性表的优点是（C）。 A便于随机存取 B花费的存储空间较顺序存储少 C便于插入和删除 D数据元素的物理顺序与逻辑顺序相同 3.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( D )存储方式最节省运算时间。 A单链表 B双链表 C单循环链表 D带头结点的双循环链表 4.带头结点的单链表head为空的判定条件是（B ）。 A.head==NULL; B.head->next==NULL; C.head->next==head; D.head!=NULL; 5.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（C ）。 A.s->next=p->next;p->next=s; B.p->next=s->next;s->next=p; C.q->next=s;s->next=p; D.p->next=s; s->next=q; 二、填空题（每小题5分） 1．给定有n个结点的向量，建立一个单链表的时间复杂度_______。建立一个有序单链表的时间复杂度_______。 2．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_____个结点。 3．在一个长度为n的线性表（采用顺序存储结构）中删除第i个元素(1≤i≤n)时，需向前移动____个元素。 4．当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_____存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。5．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的个元素。 三、算法设计题（每小题25分） 1．设有一个用向量表示的线性表L，要求写出一个将该表逆置的过程，允许在原表的存储空间外再增加一个附加的工作单元。 2．已知两个整数集合A和B，它们的元素分别依元素值递增有序存放在两个单链表HA 和HB中，编写一个函数求出这两个集合的并集C，并要求集合C的链表的结点仍依元素值递增有序存放。（注意：并集不是归并） （A ）需经常修改L 中的结点值 （E ）需不断对L 进行删除插入 第二部分线性表 、选择题 1 ?关于顺序存储的叙述中，哪一条是不正确的 （B ） A. 存储密度大 B. 逻辑上相邻的结点物理上不必邻接 C. 可以通过计算直接确定第 i 个结点的位置 D. 插入、删除操作不方便 2.长度为n 的单链表连接在长度为 m 的单链表后的算法的时间复杂度为 （C ） A 0（ n ） B 0（1） C 0（m ） D 0（m+n ） 3 .在n 个结点的顺序表中，算法的时间复杂度是 0（1）的操作是：（A ） A 访问第i 个结点（1<=i<=n ）和求第i 个结点的直接前趋（2<=i<=n ) B 在第i 个结点（1<=i<=n ）后插入一个新结点 C 删除第i 个结点（1<=i<=n ) D 将n 个结点从小到大排序 4.一个向量第一个兀素的存储地址是 100 ,每个兀素的长度为 2 ,则第5 个兀素的地址是 (B ) ( A ) 110 ( B ) 108 (C ) 100 ( D ) 120 5 .已知一个顺序存储的线性表， 设每个结点需要占 m 个存储单元，若第一个结点的地址为 da , 则第i 个结点的地址为：（A ） 7 .链表是一种采用（ B ）存储结构存储的线性表。 （A ）顺序 （B ）链式 （C ）星式 （D ）网状 8 .线性表若采用链式存储结构时，要求内存中可用存储单兀的地址： （D ） （A ）必须是连续的 （B ）部分地址必须是连续的 （C ）一定是不连续的 （D ）连续或不连续都可以 9 .线性表L 在_ （ B ）情况下适用于使用链式结构实现。 A ） da+（i-1）*m B ） da+i*m 6.在具有n 个结点的单链表中，实现（ A ）遍历链表和求链表的第 i 个结点 C ）删除开始结点 C ） da-i*m D ） da+（i+1）*m A ）的操作，其算法的时间复杂度为 0（n ）。 B ）在地址为p 的结点之后插入一个结点 D ） 删除地址为p 的结点的后继结点 第2章线性表 1．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2．线性表是具有n个（）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 3.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置 元素的时间复杂性为（） A．O（i） B．O（1） C．O（n） D．O（i-1） 4.若长度为n的线性表采用顺序存储结构，在其第i个位置插 入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 5. 对于顺序存储的线性表，访问结点和增加、删除结点的时间 复杂度为（）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 6．对于一个头指针为head的带头结点的单链表，判定该表为空 表的条件是（） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 7.链表不具有的特点是（） A．可随机访问任一元素 B．插入、删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 8.在双向链表指针p的结点前插入一个指针q的结点操作是（）。 >Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q； >Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink ; C. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q; >Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q ; 9.在单链表指针为p的结点之后插入指针为s的结点，正确的 操作是：（）。 A． s->next=p->next;p->next=s; B． p->next=s;s->next=p->next; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 10．对于一个头指针为head的带头结点的单链表，判定该表为 第二章线性表习题 判断题 1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（） 选择题 1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( ) （A）110 （B）108 （C）100 （D）120 3. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。 （A）64 （B）63 （C）63.5 （D）7 4.线性表采用链式存储结构时，其地址（）。 (A) 必须是连续的 (B) 部分地址必须是连续的 (C) 一定是不连续的 (D) 连续与否均可以 5. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（） （A）s->next=p;p->next=s; （B） s->next=p->next;p->next=s; （C）s->next=p->next;p=s; （D）p->next=s;s->next=p; 6.在一个单链表中，若删除p所指结点的后续结点，则执行（） （A）p->next=p->next->next; （B）p=p->next; p->next=p->next->next; （C）p->next=p->next; （D）p =p->next->next; 7.下列有关线性表的叙述中，正确的是（） （A）线性表中的元素之间隔是线性关系 （B）线性表中至少有一个元素 （C）线性表中任何一个元素有且仅有一个直接前趋 （D）线性表中任何一个元素有且仅有一个直接后继 8.线性表是具有n个（）的有限序列（n≠0) （A）表元素（B）字符（C）数据元素（D）数据项 填空题 1.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：( ) 。 2.顺序表中逻辑上相邻的元素物理位置(一定 )相邻，单链表中逻辑上相邻的元素物理位置( )相邻。 第二章线性表习题及答案 一、基础知识题 2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 答：始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。 头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。 2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i 越接近n则所需移动的结点数越少。 2.4 为什么在单循环链表中设置尾指针比设置头指针更好? 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。 2.5 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少? 答：我们分别讨论三种链表的情况。 1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。 2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。 3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。 2.6 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是无头结点单链表 ListNode *Q,*P; if(L&&L->next){ Q=L;L=L->next;P=L; 第二章 一选择题 1.一个线性表第一个元素的存储地址是100,每个元素的长度为4,则第5个元素的地址是( ) A.110 B.116 C.100 D.120 2. 向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。 A.64 B.63 C.63.5 D.7 3．在循环双链表的p所指接点之前插入s所指接点的操作是 A.p-> prior =s;s-> next t=p;p-> prior t->left=s;s-> prior =p-> prior; B. p-> prior =s;p-> prior -> next =s;s-> next =p;s-> prior =p-> prior; C.s-> next =p;s-> prior =p-> prior;p-> prior =s;p-> prior -> next =s; D.s-> next =p;s-> prior =p-> prior;p-> prior -> next =s;p-> prior =s; 4．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点。 A.n B.n/2 C.(n-1)/2 D.(n+1)/2 5．线性表是具有n个（）的有限序列（n≠0） A.表元素 B.字符 C.数据元素 D.数据项 6．非空的循环单链表head的尾结点（由P指向）满足 A. p->next=NULL B. p=NULL C. p->next=head D.p=head 7．在一个单链表中已知q所指的结点是p所指结点的前驱结点，若在q和p之间插入s 结点，则执行( ) A. s->next=p->next;p->next=s; B.p->next=s->next;s->next=p; C. q->next=s;s->next=p; D.p->next=s;s->next=q; 8．已知一个顺序存储线性表，若第1个结点的地址d，第3个的地址是5d，则第n个结点的地址为( ) A．[2*(n-1)+1]*d B.2*(n-1)*d C.[2*(n-1)-1]*d D.(n+1)*d 9．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( ) A.O(1) B.O(n) C.O(n2) D.O(nlog2n) 10．如果最常用的操作是提取第i个结点及其前驱，则采用( )存储方式最节省时间。 A．单链表 B.顺序表 C.循环链表 D.双链表 11．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n)之前插入一个新元素时，需要从后向前依次后移( )个元素。 A.n-i B.n-i+1 C.n-i-1 D.i 12．在一个长度为n的顺序存储线性表中，删除第i个元素(0≤i≤n-1)时，需要从后向 第二章线性表 一、填空题 1、数据逻辑结构包括线性结构、树型结构、图型结构这三种类型，树形结构和图形结构合称为非线性结构。 2、在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有个前驱结点，最后一个结点没有后续结点，其余每个结点有且只有一个后续结点。 3、在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。 4、在顺序表中，逻辑上相邻的元素，其物理位置一定相邻。在单链表中，逻辑上相邻的元素，其物理位置不一定相邻。 5、在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位置由头结点的next域指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋结点的next域指示。 6、阅读下列算法，并补充所缺内容。 void purge_linkst( ListNode *& la ) { // 从头指针为 la 的有序链表中删除所有值相同的多余元素，并释放被删结点空间ListNode *p,*q; if(la==NULL) return; q=la; p = la->link; while (p) { if (p && ___(1)p->data!=q->data___) {q=p; p = p->link;} else { q->link= ___(2)p->link___; delete(p); p=___(3)q->link___; } }//while }// purge_linkst 二、选择题 1、在数据结构中，从逻辑上可以把数据结构分成 C。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、线性表的逻辑顺序与存储顺序总是一致的，这种说法 B。 A、正确 B、不正确 3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址D。 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以 4、在以下的述叙中，正确的是B。 A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作是先进先出 D、队列的操作方式是先进后出 三、综合题 1、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 A、在P结点后插入S结点的语句序列是（（4）、（1））； B、在P结点前插入S结点的语句序列是（（7）、（11）、（8）、（4）、（1））； C、在表首插入S结点的语句序列是（（5）、（12））； 一、选择题 1. D 2. B 3. B 4. B 5. B 6. B 7. D 8. B 9. C 10. B 11. C 12. C 13. B 14. D 15. A 16. B 17. B 18. C 19. A 20. C 21. D 22. A 23. A 24. A 二、填空题 1. 首元素其直接前驱结点的链域的值 2. HL→next =NULL； HL=HL→next 3. 有限、一对一 4. O(1) 随机存取 5. 表中一半表长和该元素在表中的位置 6. 必定不一定 7. O（1） O（n） 8. 前驱结点的地址 O（n） 9. n-i+1 n-i 10. s->left=p p->right 三、判断题 1. × 2. × 3. × 4. × 5. × 6. × 7. √ 8. × 9. × 10. × 11. × 四、简答题 1. 线性表为：（78，50，40，60，34，90） 2. (36, 12, 8, 50, 25, 5, 15) 3. 解答： 尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。 五、编程题 1. 解答：由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法如下： int ListLength ( LinkList L ) { int len=0 ; ListNode *p; p=L; //设该表有头结点 while ( p->next ) { p=p->next; len++; } return len; } 2. int searchmin(linklist l) { int min; int *p; p=l; min=p->data; p=p->next; while (p->next< >nil) { if (min>p->data) min=p->data; p=p->next; } return min; } 3. int searchmax(linklist l) { int max; int *p; p=l; max=p->data; p=p->next; while (p->next< >nil) { if (max 第二章线性表习题(答案) 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。 若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置也相邻。在单链表中，逻辑上相邻的元素，其物理位置不一定相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位置由头结点的next域指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋的next域指示。 3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：（4）、（1）。 b. 在P结点前插入S结点的语句序列是：（7）、（11）、（8）、（4）、（1）。 c. 在表首插入S结点的语句序列是：（5）、（12）。 d. 在表尾插入S结点的语句序列是：（11）、（9）、（1）、（6）。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next;（4）S->next= P->next; （5）S->next= L; （6）S->next= NULL;（7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a[n]中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保 持线性表的有序性。 void insertData(int a[],int data) { int i,location=0; for(i=0;i第二章线性表答案
第二章 考研试题精选
第2章线性表习题解析(答)
第二章线性表答案
数据结构第二章线性表测试题
数据结构第2章作业 线性表(答案)
DS第二章-课后习题答案
第2章线性表习题解答
第二章线性表测试题
(完整版)数据结构第二章线性表1答案
第2章线性表(课堂作业)
第二章 线性表习题
第二章线性表习题及答案
线性表 习题
第二章_线性表(参考答案)
第2章线性表习题参考答案
第二章课后作业答案