数据结构试题集（含答案）

（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[n-1])

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++; }

试编写一个算法，在一个递增有序排列的单链表中插入一个新结点x，并保持有序。

struct Linknode{

int data ;

struct Linknode *next ; };

typedef struct Linknode *Link; Link insert(Link head) {

int i,e,j ; Link pointer,s;

printf(\

9

scanf(\ pointer= head;

while (pointer->next && e>=pointer->next->data)/*在链表中确定插入的位置*/

pointer=pointer->next; if (!pointer->next) { s=(Link)malloc(sizeof(struct Linknode)); s->data=e; s->next=NULL; pointer->next=s; } else {

s=(Link)malloc(sizeof(struct Linknode));

s->data=e; /*为插入的结点建立链接关系*/ s->next=pointer->next; pointer->next=s; }/*if*/ return head; }/*LinkList_insert*/

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

void f2(SeqList *L){

int i,j,k; k=0;

for(i=0;ilength;i++){

for(j=0;jdata[i]!=L->data[j];j++);

if(j==k){

if(k!=i)L->data[k]=L->data[i];

k++; }

}

L->length=k; }

答案：

(3,7,2,1,8) 删除顺序表中重复的元素

8、已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。 答案：

10

void Delete_list(Lnode *head, ElemType x, ElemType y) {Lnode *p, *q;

if(!head) return ERROR;

p=head; q=p; while(!p)

{if(p->data>x) && (p->data

if(p==head)

{head=p->next; free(p); p=head; q=p; } else

{q->next=p->next; free(p); p=q->next; }

else

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

}

}

9、在带头结点的循环链表L中，结点的数据元素为整型，且按值递增有序存放。给定两个整数a和b，且a

void Delete_list(Lnode *head, ElemType a, ElemType b) {Lnode *p, *q;

if(!head->next) return ERROR;

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

{if(p->data>x) && (p->data

if(p==head)

{head=p->next; free(p); p=head; q=p; } else

{q->next=p->next; free(p); p=q->next; }

else

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

}

}

试编写一个算法，将两个元素值递减排列的顺序表合并为一个非递增的顺序表。

typedef struct { ElemType *elem; int length; }Sqlist;

Merge_list(Sqlist *A, Sqlist *B, Sqlist *C)

{int j=0, k=0, i=0; C->length= A->length+ B->length;

11

while(ilength&&jlength)

if(A->elem[i]>B->elem[j]) {C->elem[k]= A->elem[i]; i++; k++;}

else { C->elem[k]= B->elem[j]; j++; k++;}

while(i< A->length) { C->elem[k]= A->elem[i]; i++; k++;} while(j< B->length) { C->elem[k]= B->elem[j]; j++; k++;} }

12