数据结构复习题 有答案的打印版(3)

s->data=x; s->next=rear->next; //将s结点链入队尾

rear->next=s; rear=s; //rear指向新队尾 }

2、在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针域next），请给出这种队列的出队操作的实现过程。

解：void DeQueue (LinkedList rear)

// rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素；否则给出出错信息。 { if (rear->next==rear) { printf(“队空\\n”); exit(0);} s=rear->next->next; //s指向队头元素， rear->next->next=s->next; //队头元素出队。 printf (“出队元素是”，s->data); if (s==rear) rear=rear->next; //空队列 free(s); }

3．请编写直接插入排序算法。 #define maxsize 100 typedef struct

{ Elemtype data[maxsize]; int last; }Sqlist; 解：

StraightInsertSort (SQLIST *v) ;n:integer);

VAR i,j:integer; BEGIN

FOR i:=2 TO n DO {假定第一个记录有序} BEGIN

v.data[0]:=v.data[i]; j:=i-1; {将待排序记录放进监视哨}

WHILE v.data[0]

BEGIN v.data[j+1]:=v.data[j]; j:=j-1; END; v.data[j+1]:=v.data[0] {将待排序记录放到合适位置} END {FOR} END；

4．二叉树以下列二叉链表为存储结构，其头指针为*Bitree, 编写将二叉树中每个结点的左右孩子交换的算法。 struct bitreptr {Elemtype data;

struct bitreptr *lchild,*rchild; };

SwepBitree(BITREPTR *bt)

{ if(bt!=NULL){t=bt->lchild; bt->lchild= bt->rchild ; bt->rchild=t;}

preptr(bt->lchild); preptr(bt->rchild);} }

5有n个人围成一圈做循环报数游戏，规定报到m的人出列。请编写程序输出所有人的出列顺序。要求：使用循环队列循环链表实现该算法。

6请编写一个判别给定二叉树是否为（平衡）二叉排序树的算法。