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

20．在一个具有n个结点的有序单链表中插人一个新结点并使之仍然有序的时间复杂度为O(n)。

21．写出带头结点的双向循环链表L为空表的条件(L==L->Next) && (L==L->Prior) 。

22．线性表、栈和队列都是线性_结构。

23．向栈中插人元素的操作是先移动栈顶针，再存人元素。 三、判断题

1．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（错） 2．在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。(错) 3．顺序存储的线性表不可以随机存取。（错） 4．单链表不是一种随机存储结构。（对） 5．顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关。(错)

6．顺序存储结构是动态存储结构，链式存储结构是静态存储结构。（错） 7．线性表的长度是线性表所占用的存储空间的大小。（错） 8．双循环链表中，任意一结点的后继指针均指向其逻辑后继。（错） 9．线性表的惟一存储形式是链表。（错） 四、综合题

1．编写一个将带头结点单链表逆置的算法。

void reverse_list( linklist * head ) { /*逆置带头结点的单链表*/ linklist *s, *p; p=head->next; /*p指向线性表的第一个元素*/ head->next=NULL; /*初始空表*/ while ( p != NULL ) { s=p; p=p->next; s->next=head->next; head->next=s; /*将s结点插入逆表*/ }

} /*reverse_list*/

2．ha和hb分别是两个按升序排列的、带头结点的单链表的头指针，设计一个算法，把这两个单链表合并成一个按升序排列的单链表，并用hC指向它的头结点。

linklist *combine_list( linklist *ha,

linklist *hb ) { /*ha, hb分别是两个按升序排列的,带有头结点的单链表的头指针，设计一个算法，把这两个单链表合并成一个按升序排列的单链表,并用hc指向它的头结点*/ linklist *hc, *pa, *pb, *pc, *p, *q, *r; hc=(linklist

*)malloc(sizeof(linklist)); /*建立hc头结点*/ p=hc; pa=ha->next; free(ha); /*释放ha头结点*/ pb=hb->next; free(hb); /*释放hb头结点*/ while (pa!=NULL && pb!=NULL ) { q=(linklist *)malloc (sizeof (linklist)); /*产生新结点*/ if (pb->datadata) { q->data=pb->data; pb=pb->next; } else { q->data=pa->data; pa=pa->next; if (pa->data==pb->data) /*将相同的元素删除*/ { r=pb;

pb=pb->next; free(r); } } p->next=q; /*将结点链入c链表*/ p=q; } while(pa!=NULL) /*a链表非空*/ { q=(linklist *)malloc (sizeof (linklist)); q->data=pa->data; pa=pa->next; p->next=q; p=q; } while(pb!=NULL) /*b链表非空*/ { q=(linklist *)malloc (sizeof (linklist)); q->data=pb->data; pb=pb->next; p->next=q; p=q; } p->next=NULL; return(hc); /*返回*/ }

3．有一个带头结点的单链表，头指针为head，编写一个算法count．list（）计算所有数据域为X的结点的个数（不包括头结点）。

int count_list(linklist *head ) {

/*在带头结点的单链表中计算所有数据域为x的结点的个数*/ linklist *p; int n; p=head->next; /*p指向链表的第一个结点*/ n=0; while (p!=NULL) { if (p->data==x) n++; p=p->next; } return(n); /*返回结点个数*/ } /*count_list*/

head，它的数据域的类型为整型，

而且按由小到大的顺序排列，编写一个算法insertx＿list（），在该链表中

4．在一个带头结点的单链表中，头指针为

linklist *insertx_list(linklist *head, int x) { /*在带头结点的单链表中插入值为x的元素，使该链表仍然有序*/ linklist *s, *p, *q; s=(linklist

*)malloc(sizeof(linklist)); /*建立数据域为x的结点*/ s->data=x; s->next=NULL; if (head->next==NULL || xnext->data ) /*若单链表为空或x小于链表第一个结点的数据域*/ { s->next=head->next;

插人值为x的元素，并使该链表仍然有序

head->next=s; } else { q=head->next; p=q->next; while( p != NULL && x>p->data ) { q=p; p=p->next; } s->next=p; q->next=s; } /*if*/

} /**insertx_list*/ 。

5．在一个带头结点的单链表中，head为其头指针，p指向链表中的某一个结点，编写算法swapin．list（），实现p所指向的结点和p的后继结点相互交换。

linklist *swapin_list(linklist *head, linklist *p) { /*在带头结点的单链表中，实现p所指向的结点和p的后继结点相互交换*/ linklist *q, *r, *s; q=p->next; /*q为p的后继*/ if (q !=NULL) /*若p有后继结点*/ { if (p==head) /*若p指向头结点*/ { head=head->next; s=head->next;

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构习题及答案(2)在线全文阅读。