第章线性表习题参考答案.docx
精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -习题二参考答案一、挑选题1. 链式储备结构的最大优点是（D）。A. 便于随机存取B. 储备密度高C. 无需预安排空间D. 便于进行插入和删除操作2. 假设在次序表a 0,a 1,a n 1 中，每一个数据元素所占的储备单元的数目为4，且第 0 个数据元素的储备的址为 100，就第 7 个数据元素的储备的址是（D ） 。A.106B. 107C.124D.1283. 在线性表中如常常要存取第i 个数据元素及其前趋，就宜采纳（A）储备方式。A. 次序表B.带头结点的单链表C. 不带头结点的单链表D.循环单链表4. 在链表中如常常要删除表中最终一个结点或在最终一个结点之后插入一个新结点，就宜采纳（C）储备方式。A.次序表B.用头指针标识的循环单链表C.用尾指针标识的循环单链表D.双向链表5. 在一个单链表中的p 和 q 两个结点之间插入一个新结点，假设新结点为S, 就修改链的java语句序列是（ D ）。A. s.setNextp; q.setNexts;B. p.setNexts.getNext; s.setNextp;C. q.setNexts.getNext; s.setNextp;D. p.setNexts; s.setNextq;6. 在一个含有n 个结点的有序单链表中插入一个新结点，使单链表仍旧保持有序的算法的时间复杂度是（ C ） 。A. O 1B.O log 2nC.O nD.O n27. 要将一个次序表a 0,a 1,a n-1 中第 i 个数据元素ai 0 i n-1 删除，需要移动（B）个数据元素。A. iB. n-i-1C. n-iD. n-i+18. 在带头结点的双向循环链表中的p 结点之后插入一个新结点s ，其修改链的java语句序列是（D）。A. p.setNexts; s.setPriorp; p.getNext.setPriors; s.setNextp.getPrior;B. p.setNexts; p.getNext.setPriors; s.setPriorp; s.setNextp.getNext;C. s.setPriorp; s.setNextp.getNext; p.setNexts; p.getNext.setPriors;D. s.setNextp.getNext; s.setPriorp; p.getNext.setPriors;p.setNexts;9. 次序表的储备密度是（B），而单链表的储备密度是（A）。A小于 1B.等于 1C.大于 1D.不能确定10. 对于图 2.29 所示的单链表，以下表达式值为真 的是（ D）。可编辑资料 - - - 欢迎下载精品名师归纳总结headABCDE可编辑资料 - - - 欢迎下载精品名师归纳总结P1P2图 2.29单链表 head 的储备结构图A. head.getNext.getData='C'B. head.getData='B'C.P1.getData=DD. P 2.getNext=null二、填空题1. 线性表是由n（ n 0）个数据元素所构成的有限序列，其中n 为数据元素的个数，称为线性表的长度，可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 5 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -n=0 的线性表称为空表。2. 线性表中有且仅有一个开头结点和终端结点，除开头结点和终端结点之外，其它每一个数据元素有且仅有一个 前驱，有且仅有一个后继。3. 线性表通常采纳次序储备和 链式储备两种储备结构。 如线性表的长度确定或变化不大，就适合采纳次序储备储备结构进行储备。4. 在次序表 a 0,a 1,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,a 2,a n）变成（ an,a n-1 ,a 1）。所谓就的，就是指逆置后的数据元素仍储备在原先次序表的储备空间中，即不为逆置后的次序表另外安排储备空间。参考答案 :public void reverse for int i = 0,j=curLen-1; i < j; i+,j- Object temp = listElemi; listElemi = listElemj; listElemj = temp;2. 编写一个次序表类的成员函数，实现对次序表循环右移k 位的操作。 即原先次序表为（a1,a 2,a n-k ,a n-k+1 , an），循环向右移动k 位后变成（ an-k+1 , a n ,a 1,a 2,a n-k ）。要求时间复杂度为O（ n）。参考答案 :public void shitint k int n=curLen,p=0,i,j,l; Object temp;fori=1;i<=k;i+ifn%i=0&&k%i=0 /求n和k的最大公约数p p=i;fori=0;i<p;i+ j=i;l=i+n-k%n; temp=listElemi; whilel.=i listElemj=listEleml; j=l;l=j+n-k%n;/循环右移一步listElemj=temp;可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 5 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结分析：要把数组 listElem的元素循环右移k位, 就listElem0移至 listElemk, listElemk移至listElem2k.直到最终回到listElem0.然而这并没有全部解决问题, 由于有可能有的元素在此过程中始终没有被拜访过, 而是被跳了过去. 分析可知 , 当n和k 的最大公约数为p时, 只要分别以 listElem0,listElem1,. listElemp-1为起点执行上述算法, 就可以保证每一个元素都被且仅被右移一次, 从而满意题目要求 . 也就是说 ,A 的全部元素分别处在p个" 循环链 " 上面 . 举例如下 :n=15,k=6, 就p=3.第一条链 : listElem0->listElem6, 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 insertint 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 Nodex; /生成新结点s.setNextp;/将 s 结点插入到单链表的q 结点与 p 结点之间q.setNexts;参考答案 方法二 :public void insertint x Node p = head.getNext; /p指向首结点while p.getNext.= null&&Integer p.getNext.getData.intValue<x p = p.getNext;Node s = new Nodex; /生成新结点s.setNextp.getNext;/将 s 结点插入到单链表的q 结点与 p 结点之间p.setNexts;可编辑资料 - - - 欢迎下载精品名师归纳总结4. 编写一个单链表类的成员函数，实现对带头结点的单链表就的逆置的操作。所谓逆置，就是把（a1,a 2,a n）变成（ an,a n-1 ,a 1）。所谓就的，就是指逆置后的结点仍储备在原先单链表的储备空间中，只不过通过修改链来转变单链表中每一个结点之间的规律位置关系。参考答案 :public void reverse /实现对单链表就的逆置 采纳的是头插法Node p = head.getNext; head.setNextnull;Node q;while p .= null q = p.getNext; p.setNexthead.getNext; head.setNextp;p = q;5. 编写一个单链表类的成员函数，实现删除不带头结点的单链表中数据域值等于x 的第一个结点的操作。如删除胜利，就返回被删除结点的位置。否就，返回-1 。参考答案 :public int removeObject x Node p = head;/初始化 ,p 指向首结点Node q=null; /q用来记录p 的前驱结点int j = 0;/j为计数器/从单链表中的首结点元素开头查找，直到p.getData指向元素 x 或到达单链表的表尾while p .= null && .p.getData.equalsx q=p;p = p.getNext;/指向下一个元素+j;/计数器的值增1if p.=null&&q=null /删除的是单链表中的首结点head=p.getNext;else if p .= null /删除的是单链表中的非首结点q.setNextp.getNext;可编辑资料 - - - 欢迎下载精品名师归纳总结elsereturn -1;/值为 x 的结点在单链表中不存在可编辑资料 - - - 欢迎下载精品名师归纳总结return j;6. 编写一个单链表类的成员函数，实现删除带头结点的单链表中数据域值等于x 的全部结点的操作。要求函数返回被删除结点的个数。参考答案 :public int removeAllObject x Node p = head.getNext;/初始化 ,p 指向首结点 ,j为计数器Node q = head; /用来记录p 的前驱结点int j = 0;/用来记录被删除结点的个数while p .= null /从单链表中的首结点开头对整个链表遍历一次可编辑资料 - - - 欢迎下载精品名师归纳总结if p.getData.equalsx q.setNextp.getNext;+j;/计数器的值增1 elseq = p;p = p.getNext;/指向下一个元素return j;/返回被删除结点的个数7. 编写一个多项式类的成员函数，实现将一个用循环链表表示的稀疏多项式分解成两个多项式的操作，并使两个多项式中各自仅含奇次项或偶次项。要求利用原先循环链表中的储备空间构成这两个链表。参考答案 :public CircleLinkList separatePolynCircleLinkList 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.setNextp; p1 = p; else /加入偶此项多项式p2.setNextp; p2 = p;p = p.getNext;p1.setNextcList1.getHead; p2.setNextcList2.getHead; CircleLinkList polyns = cList1, cList2 ; return polyns;可编辑资料 - - - 欢迎下载
