线性表 08-12年1月试题及参考答案

第2章 线性表08-12年1月试题及参考答案

（2008年1月）

2、在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（ ）

A、访问第i个元素的前驱（1

B、在第i个元素之后插入一个新元素(1?i?n) C、删除第i个元素(1?i?n) D、对顺序表中元素进行排序

3、假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（ ）

A、head= =NULL B、head–>next= =NULL C、head!=NULL D、head–>next= =head

17、输入线性表的n个元素建立带头结点的单链表，其时间复杂度为___________。

30、假设以带头结点的单链表表示线性表,阅读下列算法f30,并回答问题: (1) 设线性表为( a1, a2, a3, a4, a5, a6, a7 ), 写出执行算法f30后的线性表； (2) 简述算法f30的功能。 void f30(LinkList L) {

//L为带头结点单链表的头指针 LinkList p,q; p=L;

while (p &&p–>next){ q = p–>next;

p–>next =q–>next; p =q–>next; free(q); } }

(1)

(2)

34、假设以单链表表示线性表,单链表的类型定义如下:

typedef struct node { DataType data; struct node *next;

} LinkNode, *LinkList;

编写算法,将一个头指针为head且不带头结点的单链表改造为一个含头结点且头指针仍为head的单向循环链表,并分析算法的时间复杂度。

（2008年10月）

3、在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是（ ）

A、 p->next==head B、 p->next->next==head C、 p->next==NULL D、 p==head

17、将两个长度分别为m和n的递增有序单链表，归并成一个按元素递减有序的单链表，可能达到的最好的时间复杂度是 。 30、已知线性表的存储结构为顺序表，阅读下列算法，并回答问题： （1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30(&L)后的L状态；

（2）简述算法f30的功能。 void f30 (SeqList *L) { int i,j;

for (i=j=0;ilength; i++) if(L->data[i]>=0){

if(i!=j)L->data[j]=L->data[i]; j++； }

L->length=j; }

(1) (2)

（2009年1月）

2、假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是( )

A、head==NULL； B、head->next==NULL； C、head!=NULL； D、head->next==head；

17、在双向循环链表中插入一个新的结点时，应修改_________个指针域的值。 30、假设以带头结点的单链表表示线性表，单链表的类型定义如下： typedef int DataType;

typedef struct node { DataType data; struct node * next; } LinkNode, * LinkList;

阅读下列算法，并回答问题：

(1)已知初始链表如图所示，画出执行f30(head)之后的链表；

题30图

(2)简述算法f30的功能。 void f30( LinkList head) { LinkList p,r, s; if (head - > next)

{

r = head - > next; p = r->next;

r - > next = NULL; while (p) {

s =p;

p = p->next;

if ( s - > data% 2 = = 0) {

s - > next = head - > next; head - > next = s; } else {

s - > next = r - > next;

r->next = s; r =s; } } }

} (1) (2)

34、假设以带头结点的单链表表示线性表，单链表的类型定义如下： typedef int DataType; typedef struct node { DataType data; struct node * next; } LinkNode, * LinkList;

编写算法，删除线性表中最大元素(假设最大值唯一存在)。函数原型为： void f34(LinkList head) ; （2009年10月）

3、指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是（ ）

A、p->next=r； q->next=r->next； r->next=q； B、p->next=r； r->next=q； q->next=r->next； C、r->next=q； q->next=r->next； p->next=r； D、r->next=q； p->next=r； q->next=r->next； 17、如果需要对线性表频繁进行________或________操作，则不宜采用顺序存储结构。

31、假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下：

typedef struct Node {

int id; /*学号*/

int score； /*成绩*/ struct Node *next；

} LNode， *LinkList； 阅读算法f31，并回答问题： (1)设结点结构为

f31(A，B)后A所指的链表；

，成绩链表A和B如图所示，画出执行算法

(2)简述算法f31的功能。

void f31(LinkList A, LinkList B) {

LinkList p, q; p=A->next; q=B->next; while (p && q) {

if (p->idid)

p=p->next;

else if (p->id>q->id)

q=q->next; else {

if (p->score<60) if (q->score<60)

p->score=q->score;