数据结构试题及答案(2)

A. 单链表 B.顺序表 C. 循环链表 D.静态链表 12、在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（）。

2

A. O(n) B. O(1) C. O(n) D. O(n-1) 13、线性表L=(a1,a2,……,an)，下列说法正确的是（）。

A. 每个元素都有一个直接前驱和一个直接后继 B.线性表中至少要有一个元素

C.表中诸元素的排列顺序必须是由小到大或由大到小

D.除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继

14、一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的存储地址是（）。

A. 98 B. 100 C. 102 D. 106 15、在线性表的下列存储结构中，读取元素花费的时间最少的是（）。 A. 单链表 B. 双链表 C. 循环链表 D. 顺序表

16、在一个单链表中，若删除p所指向结点的后续结点，则执行（）。

A. p->next=p->next->next;

B. p=p->next;p->next=p->next->next; C. p =p->next;

D. p=p->next->next;

17、将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（）。

A. O(1) B. O(n) C. O(m) D. O(m+n) 18、线性表的顺序存储结构是一种（）存储结构。

A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 19、顺序表中，插入一个元素所需移动的元素平均数是（）。 A. (n-1)/2 B. n C. n+1 D. (n+1)/2 10、循环链表的主要优点是（）。

A. 不再需要头指针 B. 已知某结点位置后能容易找到其直接前驱 C. 在进行插入、删除运算时能保证链表不断开 D. 在表中任一结点出发都能扫描整个链表 11、不带头结点的单链表head为空的判定条件是（）。

A. head==NULL B. head->next==NULL C. head->next==head D. head!=NULL

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

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

C.删除第i个元素(1?i?n) D. 对顺序表中元素进行排序 13、已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（）。

A. q->next=s->next；s->next=p； B. s->next=p；q->next=s->next； C. p->next=s->next；s->next=q； D. s->next=q；p->next=s->next； 14、在以下的叙述中，正确的是（）。

A.线性表的顺序存储结构优于链表存储结构

B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况

C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况

D.线性表的链表存储结构优于顺序存储结构

15、在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（）。

A. (n-1)/2 B. n/2 C. (n+1)/2 D. n 16、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入一个结点s，则执行（）。

A. s->next=p->next; p->next=s; B. p->next=s->next;s->next=p; C. q->next=s;s->next=p; D. p->next=s;s->next=q; 17、在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（）。 A. p=p->next; B. p->next=p->next->next; C. p->next=p; D.p=p->next->next;

18、在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next==head，则（）。

A. p指向头结点 B. p指向尾结点 C.p的直接后继是头结点

D.p的直接后继是尾结点

二、填空题 1、设单链表的结点结构为（data,next）。已知指针p指向单链表中的结点，q指向新结点，欲将q插入到p结点之后，则需要执行的语句：q-next=p-next,p-next=q 。 答案：q->next=p->next p->next=q

2、线性表的逻辑结构是线性结构，其所含元素的个数称为线性表的长度。 答案：线性结构 长度

3、写出带头结点的双向循环链表L为空表的条件L-prior=L-next=L。 答案：L->prior==L->next==L

4、带头结点的单链表head为空的条件是 head-next==null 。 答案：head->next==NULL

5、在一个单链表中删除p所指结点的后继结点时，应执行以下操作：

q= p->next;

p->next=_q-next ___;

答案：q->next

三、判断题

1、单链表不是一种随机存储结构。?

2、在具有头结点的单链表中，头指针指向链表的第一个数据结点（的存储位置）。? 3、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。? 4、顺序存储方式只能用于存储线性结构。?

5、在线性表的顺序存储结构中，逻辑上相邻的两个元素但是在物理位置上不一定是相邻的。?

6、链式存储的线性表可以随机存取。?

四、程序分析填空题

1、函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。 int GetElem(LinkList L,int i,Elemtype *e){

LinkList p；int j； p=L->next;j=1; while(p&&j

p=p-next (1) ;++j; }

if(!p||j>i) return ERROR; *e= p-data (2) ; return OK;

}

答案：(1)p=p->next (2)p->data

2、函数实现单链表的插入算法，请在空格处将算法补充完整。

int ListInsert(LinkList L,int i,ElemType e){ LNode *p,*s;int j; p=L;j=0;

while((p!=NULL)&&(jnext;j++; }

if(p==NULL||j>i-1) return ERROR; s=(LNode *)malloc(sizeof(LNode)); s->data=e;

(1) s-next=p-next ; (2) p-next=s ; return OK; }/*ListInsert*/ 答案：(1)s->next=p->next (2)p->next=s

3、函数ListDelete_sq实现顺序表删除算法，请在空格处将算法补充完整。

int ListDelete_sq(Sqlist *L,int i){ int k;

if(i<1||i>L->length) return ERROR;

for(k=i-1;klength-1;k++)

L->slist[k]=L->slist[k+1]（1）;

（2）--L->Length; return OK; }

答案：（1）L->slist[k+1] （2） --L->Length

4、函数实现单链表的删除算法，请在空格处将算法补充完整。 int ListDelete(LinkList L,int i,ElemType *s){

LNode *p,*q; int j; p=L;j=0;

while(( p-next!=null （1）)&&(jnext;j++; }

if(p->next==NULL||j>i-1) return ERROR; q=p->next; p-next=q-next （2）; *s=q->data; free(q); return OK; }/*listDelete*/

答案：(1)p->next!=NULL (2)p->next=q->next 5、写出算法的功能。

int L(head){ node * head; int n=0; node *p; p=head;

while(p!=NULL) { p=p->next; n++; }

return(n); }

答案：求单链表head的长度

五、综合题

1、编写算法，实现带头结点单链表的逆置算法。 答案：void invent(Lnode *head)

{Lnode *p,*q;

if(!head->next) return ERROR;

p=head->next; q=p->next; p->next =NULL; while(q)

{p=q; q=q->next; p->next=head->next; head->next=p;} }

2、有两个循环链表，链头指针分别为L1和L2，要求写出算法将L2链表链到L1链表之后，且连接后仍保持循环链表形式。 答案：void merge(Lnode *L1, Lnode *L2)

{Lnode *p,*q ;

while(p->next!=L1)

p=p->next; while(q->next!=L2)

q=q->next;

q->next=L1; p->next =L2; }

3、设一个带头结点的单向链表的头指针为head，设计算法，将链表的记录，按照data域的值递增排序。

答案：void assending(Lnode *head)

{Lnode *p,*q , *r, *s;

p=head->next; q=p->next; p->next=NULL; while(q)

{r=q; q=q->next;

if(r->data<=p->data)

{r->next=p; head->next=r; p=r; } else

{while(!p && r->data>p->data)

{s=p; p=p->next; } r->next=p; s->next=r;} p=head->next; }

}

4、编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。 答案：

void linklist_c(Lnode *head) {Lnode *p; p=head; if(!p) return ERROR;

while(p->next!=NULL)

p=p->next; p->next=head; }

设单链表的长度（数据结点数）为N，则该算法的时间主要花费在查找链表最后一个结点上（算法中的while循环），所以该算法的时间复杂度为O（N）。

5、已知head为带头结点的单循环链表的头指针，链表中的数据元素依次为（a1，a2,a3,a4,?,an）,A为指向空的顺序表的指针。阅读以下程序段，并回答问题： （1）写出执行下列程序段后的顺序表A中的数据元素； （2）简要叙述该程序段的功能。

if(head->next!=head) {

p=head->next; A->length=0;

while(p->next!=head) {

p=p->next;

A->data[A->length ++]=p->data;