数据结构试题集(包含答案 - 完整版) 下载本文

结点,欲将q插入到p结点之后,则需要执行的语句: ; 。 答案:q->next=p->next p->next=q

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

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

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

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

q = p->next;

p->next= _ q->next ___; 三、判断题

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

2、在具有头结点的单链表中,头指针指向链表的第一个数据结点。?

3、用循环单链表表示的链队列中,可以不设队头指针,仅在队尾设置队尾指针。? 4、顺序存储方式只能用于存储线性结构。?

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

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

四、程序分析填空题

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

p=L->next;j=1;

while(p&&j

(1) ;++j;

}

if(!p||j>i) return ERROR; *e= (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) ; (2) ; 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]= (1) ;

(2) ; 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(( (1) )&&(jnext;j++; }

if(p->next==NULL||j>i-1) return ERROR; q=p->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; if(p->next!=head)p=p->next; }

}

答案:

(1) (a2, a4, …, ) (2)将循环单链表中偶数结点位置的元素值写入顺序表A

6、设顺序表va中的数据元数递增有序。试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性。 答案:

void Insert_sq(Sqlist va[], ElemType x) {int i, j, n; n=length(va[]); if(x>=va[i])

va[n]=x; else

{i=0;

while(x>va[i]) i++; for(j=n-1;j>=I;j--)

va[j+1]=va[j]; va[i]=x; } n++; }

7、假设线性表采用顺序存储结构,表中元素值为整型。阅读算法f2,设顺序表L=(3,7,3,2,1,1,8,7,3),写出执行算法f2后的线性表L的数据元素,并描述该算法的功能。

void f2(SeqList *L){