线性表习题参考

1、习题二参照答案一、选择题链式储存构造的最大长处是（D）。A.便于随机存取B.储存密度高C.无需预分派空间D.便于进行插入和删除操作2.假定在次序表a,a,a中，每一个数据元素所占的储存单元的数量为4，且第0个数据元素的储存地01n1址为100，则第7个数据元素的储存地点是（D）。A.106B.107C.1243.在线性表中若常常要存取第i个数据元素及其前趋，则宜采纳（A）储存方式。A.次序表B.带头结点的单链表C.不带头结点的单链表D.循环单链表4.在链表中若常常要删除表中最后一个结点或在最后一个结点以后插入一个新结点，则宜采纳（C）储存方式。A.次序表B.用头指针表记的循环单链表C.用尾指针

2、表记的循环单链表D.双向链表5.在一个单链表中的p和q两个结点之间插入一个新结点，假定新结点为S,则改正链的java语句序列是（D）。A.(p);(s);B.();(p);C.();(p);D.(s);(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.iB.n-i-1C.n-iD.n-i+18.在带头结点的双向循环链表中的p结点以后插入一个新结点s，其改正链的java语句序

3、列是（D）。(s);(p);().setPrior(s);();(s);().setPrior(s);(p);();(p);();(s);().setPrior(s);D.();(p);().setPrior(s);(s);9.次序表的储存密度是（B），而单链表的储存密度是（A）。A小于1B.等于1C.大于1D.不可以确立关于图所示的单链表，以下表达式值为真的是（D）。headABCDEP1P2图单链表head的储存构造图A.().getData()=CB.()=BC.()=DD.()=null二、填空题1.线性表是由n（n0）个数据元素所组成的n=0的线性表称为空表。有限序列，此中n为数据元

4、素的个数，称为线性表的长度，线性表中有且仅有一个开始结点和终端结点，除开始结点和终端结点以外，其余每一个数据元素有且仅有一个前驱，有且仅有一个后继。3.线性表往常采纳次序储存和链式储存两种储存构造。若线性表的长度确立或变化不大，则合适采纳次序储存藏储构造进行储存。4.在次序表a0,a1,an-1中的第i(0in-1)个地点以前插入一个新的数据元素，会惹起n-i个数据元素的挪动操作。在线性表的单链表储存构造中，每一个结点有两个域，一个是数据域，用于储存数据元素值自己，另一个是指针域，用于储存后继结点的地点。在线性表的次序储存构造中可实现迅速的随机存取，而在链式储存构造中则只好进行次序存取。7.次

5、序表中逻辑上相邻的数据元素，其物理地点必定相邻，而在单链表中逻辑上相邻的数据元素，其物理位置不必定相邻。8.在仅设置了尾指针的循环链表中，接见第一个结点的时间复杂度是O（1）。9.在含有n个结点的单链表中，若要删除一个指定的结点p，则第一一定找到指定结点p的前驱，其时间复杂度为O（n）。10.若将单链表中的最后一个结点的指针域值改为单链表中头结点的地点值，则这个链表就组成了循环单链表。三、算法设计题1.编写一个次序表类的成员函数，实现对次序表就地逆置的操作。所谓逆置，就是把（a1,a2,an）变为（an,an-1,a1）；所谓就地，就是指逆置后的数据元素仍储存在本来次序表的储存空间中，即不为逆

6、置后的顺序表此外分派储存空间。参照答案:publicvoidreverse()for(inti=0,j=curLen-1;ij;i+,j-)Objecttemp=listElemi;listElemi=listElemj;listElemj=temp;2.编写一个次序表类的成员函数，实现对次序表循环右移12n-k,an-k+1n），k位的操作。即本来次序表为（a,a,a,a循环向右挪动k位后变为（an-k+1,an,a1,a2,an-k）。要求时间复杂度为O（n）。参照答案:publicvoidshit(intk)intn=curLen,p=0,i,j,l;Objecttemp;for(i=1

7、;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,listElem1

8、1-listElem2.恰巧使所有元素都右移一次.固然未经数学证明,但相信上述规律应当是正确的.3.编写一个单链表类的成员函数，实此刻非递减的有序单链表中插入一个值为拥有序的操作。参照答案(方法一):publicvoidinsert(intx)Nodep=();ntValue();if(tempx)q=p;p=();elsebreak;x的数据元素，并使单链表仍保Nodes=newNode(x);etData().intValue()x)p=();Nodes=newNode(x);quals(x)q=p;p=();quals(x)();+j;etNext();/原多项式的首结点while(p!=()PolynNodedata=(PolynNode