int R[n]; { int root;
SqStack *s; //s为一个指针栈，类型为seqstack，其中包含top域和数组data s->top= -1; //s栈置空 root=1;
while ((root<=n) && (s->top>-1)) { while (root<=n) { printf(R[root]); s->top++; s->data[s->top]=root; root=2*root;
} if (s->top>-1) //栈非空访问，遍历右子树 { root=s->data[s->top]*2+1; s->top--;
} } }
2. 解答：考虑用一个顺序队que来保存遍历过程中的各个结点，由于二叉树以二叉链表存储，所以可设que为一个指向数据类型为bitree的指针数组，最大容量为maxnum，下标从1开始，同层结点从左到右存放。算法中的front为队头指针，rear为队尾指针。
levelorder (BiTree *t) //按层次遍历二叉树t
{ BiTree *que[maxnum]; int rear,front; if (t!=NULL)
{ front=0; //置空队列 rear=1; que[1]=t; do { front=front%maxsize+1; //出队 t=que[front]; printf(t->data); if (t->lchild!=NULL) //左子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->lchild;
}
if (t->rchild!=NULL) //右子树的根结点入队
{ rear=rear%maxsize+1; que[rear]=t->rchild;
}
}while (rear= =front); //队列为空时结束 } }
3. 解答：设该线索二叉树类型为bithptr，包含5个域：lchild，ltag，data，rchild，rtag。
insert(p, s) //将s结点作为p的右子树插入 BiThrNode *p,*s; { BiThrNode *q;
if (p->rtag= =1) //无右子树，则有右线索 { s->rchild=p->rchild;
s->rtag=1; p->rchild=s; p->rtag=0;
} else
{ q=p->rchild;
while(q->ltag= =0) //查找p所指结点中序后继，即为其右子树中最左下的结点 q=q->lchild; q->lchild=p->rchild; s->rtag=0; p->rchild=s; }
s->lchild=p; //将s结点的左线索指向p结点 s->ltag=1;
}
4. 解答：利用一个队列来完成，设该队列类型为指针类型，最大容量为maxnum。算法中的front为队头指针，rear为队尾指针，若当前队头结点的左、右子树的根结点不是所求结点，则将两子树的根结点入队，否则，队头指针所指结点即为结点的双亲。
parentjudge(t,n) BiTree *t; int n;
{ BiTree *que[maxnum]; int front,rear; BiTree *parent; parent=NULL; if (t)
if (t->data= =n)
printf(“no parent!”); //n是根结点，无双亲
else
{ front=0; //初始化队列
rear=1;
que[1]=t; //根结点进队 do
{ front=front%maxsize+1; t=que[front];
if((t->lchild->data= =n)|| (t->rchild->data= =n)) //结点n有双亲 { parent=t; front=rear;
printf(“parent”,t->data); } else
{ if (t->lchild!=NULL) //左子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->lchild;
} if (t->rchild!=NULL) //右子树的根结点入队
{ rear=rear%maxsize+1; que[rear]=t->rchild; }
}
}while(rear= =front); //队空时结束
} }
if (parent = =NULL)
printf(“结点不存在”);
习题8
一、单项选择题
1. 若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（ ）。
A. j-i B. i-j-1 C. i-j D. i-j+1
2. 若对n个元素进行直接插入排序，则进行任一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（ ）。
2
A. O(1) B. O(n) C. O(n) D. O(log2n)
3. 在对n个元素进行直接插入排序的过程中，共需要进行（ ）趟。
A. n B. n+1 C. n-1 D. 2n
4. 对n个元素进行直接插入排序时间复杂度为（ ）。
2
A. O(1) B. O(n) C. O(n) D. O(log2n)
5. 在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行（ ）对相邻元素之间的交换。
A. n B. n-1 C. n+1 D. n/2
6. 在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（ ）。
2
A. O(1) B. O(log2n) C. O(n) D. O(n) 7. 在对n个元素进行冒泡排序的过程中，至少需要（ ）趟完成。 A. 1 B. n C. n-1 D. n/2
8. 在对n个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中元素的个数相等或只差一个，则整个排序过程得到的含两个或两个元素的区间个数大致为（ ）。 A. n B. n/2 C. log2n D. 2n
9. 在对n个元素进行快速排序的过程中，第一次划分最多需要移动（ ）次元素，包括开始把支点元素移动到临时变量的一次在内。
A. n/2 B. n-1 C. n D. n+1
10. 在对n个元素进行快速排序的过程中，最好情况下需要进行（ ）躺。 A. n B. n/2 C. log2n D. 2n
11. 在对n个元素进行快速排序的过程中，最坏情况下需要进行（ ）躺。 A. n B. n-1 C. n/2 D. log2n
12. 在对n个元素进行快速排序的过程中，平均情况下的时间复杂度为（ ）。
2
A. O(1) B. O(log2n) C. O(n) D. O(nlog2n) 13. 在对n个元素进行快速排序的过程中，最坏情况下的时间复杂度为（ ）。
2
A. O(1) B. O(log2n) C. O(n) D. O(nlog2n) 14. 在对n个元素进行快速排序的过程中，平均情况下的空间复杂度为（ ）。
2
A. O(1) B. O(log2n) C. O(n) D. O(nlog2n) 15. 在对n个元素进行直接插入排序的过程中，算法的空间复杂度为（ ）。
2
A. O(1) B. O(log2n) C. O(n) D. O(nlog2n)
16. 对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（ ）。
A. 1, 3, 5, 7, 9 B. 9, 7, 5, 3, 1 C. 5, 3, 1, 7, 9 D. 5, 7, 9, 1, 3
17. 假定对元素序列（7, 3, 5, 9, 1, 12, 8, 15）进行快速排序，则进行第一次划分后，得到的