第二章线性表习题参考解析.doc

习题二参考答案 一、选择题 链式存储结构的最大优点是（ D ）。 A.便于随机存取 B.存储密度高 C.无需预分配空间 D.便于进行插入和删除操作 假设在顺序表{a0,a1,……,an－1}中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是（ D ）。 106 B. 107 C.124 D.128 在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ A ）存储方式。 A.顺序表 B. 带头结点的单链表 C.不带头结点的单链表 D. 循环单链表 在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（ C ）存储方式。 顺序表 B. 用头指针标识的循环单链表 C. 用尾指针标识的循环单链表 D. 双向链表 在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为S,则修改链的java语句序列是（ D ）。 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); 在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ C ）。 O(1) B. O(log2n) C. O(n) D. O(n2) 要将一个顺序表{a0,a1,……,an-1}中第i个数据元素ai(0≤i≤n-1)删除，需要移动（ B ）个数据元素。 i B. n-i-1 C. n-i D. n-i+1 在带头结点的双向循环链表中的p结点之后插入一个新结点s，其修改链的java语句序列是（ D ）。 p.setNext(s); s.setPrior(p); p.getNext().setPrior(s); s.setNext(p.getPrior()); p.setNext(s); p.getNext().setPrior(s); s.setPrior(p); s.setNext(p.getNext()); s.setPrior(p); s.setNext(p.getNext()); p.setNext(s); p.getNext().setPrior(s); s.setNext(p.getNext()); s.setPrior(p); p.getNext().setPrior(s); p.setNext(s); 顺序表的存储密度是（ B ），而单链表的存储密度是（ A ）。 A．小于1 B. 等于1 C. 大于1 D. 不能确定 对于图2.29所示的单链表，下列表达式值为真的是（ D ）。 图2.29 单链表head的存储结构图 A. head.getNext().getData()==C B. head.getData()==B C. P1.getData()==’D’ D. P2.getNext()==null 二、填空题 线性表是由n（n≥0）个数据元素所构成的 有限序列 ，其中n为数据元素的个数，称为线性表的 长度 ，n=0的线性表称为 空表 。 线性表中有且仅有一个开始结点和终端结点，除开始结点和终端结点之外，其它每一个数据元素有且仅有一个 前驱 ，有且仅有一个 后继 。 线性表通常采用 顺序存储 和 链式存储 两种存储结构。若线性表的长度确定或变化不大，则适合采用 顺序存储 存储结构进行存储。 在顺序表{a0,a1,……,an-1}中的第i(0≤i≤n-1)个位置之前插入一个新的数据元素，会引起 n-i 个数据元素的移动操作。 在线性表的单链表存储结构中，每一个结点有两个域，一个是数据域，用于存储数据元素值本身，另一个是 指针域 ，用于存储后继结点的地址。 在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中则只能进行 顺序 存取。 顺序表中逻辑上相邻的数据元素，其物理位置 一定 相邻，而在单链表中逻辑上相邻的数据元素，其物理位置 不一定 相邻。 在仅设置了尾指针的循环链表中，访问第一个结点的时间复杂度是 O（1） 。 在含有n个结点的单链表中，若要删除一个指定的结点p，则首先必须找到 指定结点p的前驱 ，其时间复杂度为 O（n）public void reverse() { for (int i = 0,j=curLen-1; i j; i++,j--)