25．关键字序列为：49，38，65，97，76，13，27，35，写出归并排序的每一趟结果。
[49，38] [65，97] [76，13] [27，35]
[38，49] [65，97] [13，76] [27，35]
[38，49，65，97 ] [13，27，35，76 ]
[13，27，35，38，49，65，76，97 ]
26．已知数据序列{12, 02, 16, 30, 28, 10, 17, 20, 06, 18}，写出希尔排序每一趟排序的结果。（设d=5、2、1）
解： 12 02 16 30 28 10 17 20 06 18 d=5
10 02 16 06 18 12 17 20 30 28 d=2
12 02 16 06 17 12 18 20 30 28
d=1 02 06 10 12 16 17 18 20 28 30
27. 已知数据序列{53, 36, 48, 36, 60, 7, 18, 41}，写出采用简单选择排序的每一趟排序结果。 解： [53 36 48 36 60 7 18 41] （7） [36 48 36 60 53 18 41]
（7 18） [48 36 60 53 36 41] （7 18 36） [48 60 53 36 41] （7 18 36 36） [60 53 48 41] （7 18 36 36 41） [53 48 60] （7 18 36 36 41 48） [53 60] （7 18 36 36 41 48 53） [60]
28. 已知数据序列{10, 1, 15, 18, 7, 15}，试画出采用快速排序法，第一趟排序的结果。 解：
10 1 15 18 7 15 low high 交换 7 1 15 18 [10] 15 low high 交换
第一趟排序结果： 7 1 [10] 18 15 15
low high
29． 已知数据序列{10，1，15，18，7，15}，试画出采用快速排序法，第一趟排序的结果。 解：
10 1 15 18 7 15 low high 交换 7 1 15 18 [10] 15 low high 交换 第一趟排序结果： 7 1 [10] 18 15 15
low high
五．程序填空题（每空1分，共5分）
1. 已知线性表中的元素是无序的，并以带表头结点的单链表作存储。试填空完成算法，删除表中所有大于min，小于max的元素。
Void delete (lklist head; datatype min, max) { q=head->next; while (p!=NULL)
{ if ((p->data<=min ) | | ( p->data>=max ) {q=p; p= p->next ; }
else
{ q->next= p->next ;
delete (p) ; p= q->next ; } } }
2. 试填空完成二叉树后序遍历的递归程序。
typedef struct BT
{ datatype data; // 定义结点
BT *lchild; BT *rchild; }BT;
void Postorder( BT *T ) // 后序遍历 { if ( T==NULL ) return; else
{ Postorder( T->lchild );
Postorder( T->rchild ); Printf( T->data );
} }
六．写出运行下列程序段的输出结果 （5分）
1. 二叉树的结构如图所示，试写出执行下列算法后的输出结果。
typedef struct BT
{ datatype data; // 定义结点
BT *lchild; BT *rchild; }BT;
int BTD(BT *T) { int ldep,rdep; if(T==NULL)
return 0;
E C F G BD A H else { ldep=BTD(T->lchild) ;
}
}
rdep=BTD(T->rchild) ; if(ldep>rdep)
return ldep+1; return rdep+1; else
解： 5 求二叉树深度
2. 二叉树的结构如图所示，试写出执行下列算法后的输出结果： 。
typedef struct BT { datatype data; BT *lchild; BT *rchild;
}BT;
void Postorder(BT *T) { if (T!=NULL） { Postorder(T->lchild);
Postorder(T->rchild); cout<
解： 后序遍历ECBHFGDA ，结果正确5分
C E BHF A D G 复习：1．先序遍历算法； 2．中序遍历算法
3．后序遍历算法； 4．层次遍历算法 5. 求二叉树叶结点算法； 6. 求二叉树总结点算法 7．深度优先遍历算法； 8．广度优先遍历算法
七．程序设计题(10分) 1. 十进制数转换为十六进制数
#include
struct stacknode *next;
// 指向栈的指针
// 栈的存储结构
}stacknode; typedef struct }linkstack;
void Conversion(int n) { linkstack s;
int x; s.top=NULL; do { } while(n);
printf(\转换以后的16进制数值为：\while(s.top)
{ if (s.top->data<10)
printf(\ else
switch (s.top->data)
{ case 10: printf(\ case 11: printf(\x=n; n=n/16; stacknode *p; p=new (stacknode); p->next=s.top; s.top=p; s.top->data=x;
// 二——十六进制转换函数
{ stacknode *top;
case 12: printf(\
case 13: printf(\ case 14: printf(\ case 15: printf(\ } void main() { int n;
printf(\请输入一个10进制正整数：\ scanf(\ Conversion(n); }
2. 二叉树按二叉链表形式存储： （1）编写一个建立二叉树的算法。
（2）判别给定的二叉树是否为完全二叉树的算法。
分析：二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左孩子就不应有右孩子”的原则进行判断。 解：
BiTree Creat() // 建立二叉树的二叉链表形式的存储结构 { ElemType x; BiTree bt; scanf(\ if(x==0) bt=NULL; else if(x>0)
{ bt=(BiTNode *) malloc (sizeof(BiTNode));
bt->data=x; bt->lchild=creat(); bt->rchild=creat(); } return(bt);
}
int JudgeComplete(BiTree bt) // 如是完全二叉树返回1，否则，返回0 { int tag=0;
BiTree p=bt, Q[50]; // Q是队列，元素是二叉树结点指针，容量足够大
}
stacknode* p=s.top; }
printf(\
s.top=s.top->next; free(p);