第二章 考研试题精选

第二章线性表作业

一、选择题

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. 下面的叙述不正确的是（）

B. 线性表在链式存储时，查找第i个元素的时间同i的值无关

C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比

D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关

11.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无

关。

(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是（）

A．（1），（2）B．（1）C．（1），（2）,(3) D.（2）

12. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。

A. O(0)

B. O(1)

C. O(n)

D. O(n2)

13. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。

A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)

14．线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A．O（i）B．O（1）C．O（n）D．O（i-1）

15．在双向链表指针p的结点前插入一个指针q的结点操作是（）。

A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；

B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;

C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;

D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;

16．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。

A．p->next=s;s->next=p->next; B．s->next=p->next;p->next=s;

C．p->next=s;p->next=s->next; D．p->next=s->next;p->next=s;

17．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL

二、程序阅读题

1以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

/* h为附加头结点指针；类型pointer同算法设计第3题*/

{ pointer p,q;

p=h->next; h->next=NULL;

while((1)________)

{q=p; p=p->next; q->next=h->next; h->next=(2)________; }

}

2 .下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针，试在空缺处填入适当的语句。

void reverse（linklist &L）{

p=null；q=L；

while（q！=null）

{ (1) ; q->next=p；p=q；(2)___ ; }

(3)_____;

}

3. 一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef ，指数域exp和指针域next；现对链表求一阶导数，链表的头指针为ha，头结点的exp域为–1。

derivative(ha)

{ q=ha ; pa=ha->next;

while( (1)_______)

{ if ( (2)____) { ( (3)__); free(pa); pa= ( (4) _); }

else{ pa->coef ( (5) ___); pa->exp( (6)___); q=( (7) __);}

pa=( (8)________);

}

}

4．对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。

typedef struct node

{int data; struct node *next;

}linknode,*link;