数据结构练习题

p= (1) ;

Lc=(LinkList) malloc(sizeof(ListNode)); Lc->next=Lc; while(p!=L) if(p->data>c) {

pre->next=p->next; (2) ; Lc->next=p; p=pre->next; } else {

pre=p;

(3) ; }

return Lc; }

23.已知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; } }

24．假设线性表采用顺序存储结构，表中元素值为整型。阅读算法f 30，并回答下列问题： （1）设顺序表L=(3,7,3,2,1,1,8,7,3),写出执行算法f 30后的L; （2）简述算法f 30的功能。 void f 30(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;

13

}

25．阅读算法f 31,并回答下列问题： （1）设队列Q=（1，3，5，2，4，6）。写出执行算法f 31后的队列Q; （2）简述算法f 31的功能。 void f 31(Queue *Q){ DataType e;

if (!QueueEmpty(Q)){ e=DeQueue(Q); f 31(Q);

EnQueue(Q,e); } }

五、算法设计题

1．设单链表的结点结构如下： struct node{datatype data; struct node*next; }

试编写一个函数int count(struct node *head,datatype x)统计单链表中数据域为x的结点个数。 2．假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node{ DataType data; struct node *next }LinkNode, *LinkList;

编写算法，从有序表A中删除所有和有序表B中元素相同的结点。

3.二叉树是由所有度数不大于2的结点构成的一种特定树，若某结点度为2，则该结点有左 右两个孩子，请编写算法计算一二叉树所有度数为2的结点个数。

4.若二叉树存储结构采用二叉链表表示，试编写一算法，计算一棵二叉树的所有结点数。

14