数据结构课后习题(第2章).doc

《数据结构课后习题(第2章).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、【课后习题】第2章线性表 2011级计科(网工)班学号：姓名：题号一二三四总分得分一、判断题（如果正确，在题号前打“Ö”，否则打“´”。每题2分，共10分)()1.线性表若采用顺序存储表示时所有结点之间的存储单元地址必须连续。()2.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。()3.如果某个数据结构的每一个元素都是最多只有一个直接前驱，则必为线性结构。()4.线性表的逻辑顺序与物理顺序总是一致的。()5.线性表的长度是指它所占存储空间的大小。二、填空题（每空1.5分，共21分)1.从逻辑结构看，线性表是典型的。2.在一个长度为n的向量中在第i（1≤

2、i≤n+1）个元素之前插入一个元素时，需向后移动个元素，算法的时间复杂度为。3.在一个长度为n的向量中删除第i（1≤i≤n）个元素时，需向前移动个元素，算法的时间复杂度为。4.若长度为n的线性表采用链式存储结构，在其第i个结点前插入一个新的元素的算法的时间复杂度为。删除其第i个元素的算法的时间复杂度为。5.线性表顺序存储结构的优点是可以实现，主要缺点是:。6.不带头结点的单链表L为空的条件是，带头结点的单链表L为空的条件是，带头结点的单循环链表L为空的条件是。7.两指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前导的条件是。8.设双向循环链表中结

3、点的结构为（data,prior,next），若指针p指向该链表的某个结点，则有下面的关系：p->next->prior==。三、单项选择（请将正确答案的代号填写在下表对应题号下面。每题2分，共40分)题号12345678910答案　　　　　　　　题号11　12　　13　1415　16　17181920答案　　　　　　　　1.P和Q两个指针分别指向双向循环表L的两个元素，P所指元素是Q所指元素的后继的条件是（   ）。A.P==Q              B.Q-﹥Next==PC.P-﹥Next==Q       D.Q-﹥PRIOR==P2.指针P指向不带

4、头结点的线性链表L的首元素的条件是（   ）。A.P==L          B.L-﹥Next==PC.P-﹥next==L    D.P-﹥next==NULL3.指针p指向带头结点的单循环链表L的首元素的条件是（   ）。A.P==L          B.L-﹥Next==PC.P-﹥next==L    D.P-﹥next==NULL4.指针P指向单链表L的尾元素的条件是（   ）。A.P==L          B.L-﹥Next==PC.P-﹥next==L    D.P-﹥next==NULL5.指针P所指的元素是双向循环链表L的尾元素的条件是（

5、   ）。A.P==L           B.P==NULL   C.P-﹥next==LD.P-﹥prior==L 6.在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（   ）。A.0(1)   B.0(n)    C.0(nlog2n)    D.0(n2)7.顺序存储的线性表(a1,a2,…an)，在任一结点前插入一个新结点时所需移动结点的平均次数为（   ）。A.n      B.n/2           C.n+1      D.(n+1)/28.删除长度为n的顺序表的第i(1≤i≤n)个位置上的元素

6、，元素的移动次数为()A)i-1B)iC)n-iD)n-i+19.在C语言中可用（）描述线性表。A、数组；B、指针；C、数组或指针；D、结构10.链表不具有的特点是（）A)插入、删除不需要移动元素B)可随机访问任一元素C)不必事先估计存储空间D)所需空间与线性长度成正比11.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是()A)p=p->next;B)p->next=p;C)p->next=p->next->next;D)p=p->next->next;12.单链表的存储密度（）A)大于1；B)等于1；C)不能确定；D)小于11.非空的循环单

7、链表first的尾结点（由p所指向）满足：。A.p->next==NULL；　　B.p==NULL；C.p->next==first；　D.p==first；2.下列静态链表没有设置空闲指针链，则其表示的线性表逻辑结构为（）。01234567…100abcdef…32516410…A、（c,a,b,e,d,f,…）；B、；C、；D、。3.在下列线性表如下图所示中将结点P插入到Q结点之前采用的操作是（）。（已知：结点的前驱指针域为pre，后继指针域为next）。图1PeabdQD……A、P->next=Q->next；P->pre=P->next->pre；P->

8、next->pre=P-