1、一、举例说明二分查找的基本思想，并用类 C 语言设计算法实现二分查找 (折半查找)。解：二分法查找的过程是：首先确定待查记录的范围，然后逐步缩小范围到直到找到或找不到该记录为止。例如：已知 11 个数据元素的有序表， （关键字为数据元素的值）：（05 ，13，19，21，37 ，56，64，75，80 ，88，92） ，现在查找关键字为 21 的数据元素。设指针 low 指向下界，high 指向上界，mid=（low+high） /2 指向中间区域。所以此例种设low=1，则 high=11，mid=6。首先取 mid 所指元素 ST.elemmid.key 与给定值 key=21 比较，因为
2、 5621，说明所查 key=21 一定在 56 的左侧，则令 high=mid-1，所以所查元素在low，mid-1之间即 1，5范围，求出 mid=（low+high） /2=3，取 mid 所指元素 19 再与key 的值 21 比较，因为 19high 的情况，因此当 lowhigh 说明查找不成功。算法如下：Int Search_Bin(SSTable ST, KeyType key)/在有序表 ST 中查找值为 key 的元素，若找到，则函数值为该元素在表中的位置，否则为0low=1;high=ST.length; /置区间初值while(lownext ； pb = Lb-nex
3、t ；/ 分别指向第一个结点Lc = pc = La ；/用 La 的头节点作为 Lc 的头节点while ( pa /定义用于暂存运算符的栈InitStack(R); /初始化栈Push(R,); /给栈底放入字符，它具有最低优先级 0int i,j;i=0; /用于指示扫描s1 串中字符的位置，初值为0j=0; /用于指示s2串中待存字符的位置，初值为0char ch=s1i; /ch保存s1串中扫描到的字符，初值为第一个字符while(ch!=) /顺序处理中缀表达式中的每个字符if(ch=+|ch=-|ch=*|ch=/) /对于四则运算符，使暂存在栈中的不低于ch优先级的运算符依次出
4、栈并写入到s2中char w=top(R);while(Precedence(w)=Precedence(ch) / Precedence(w)函数返回运算符形参的优先级s2j+=w; Pop(R); w=top(R);Push(R,ch); /把ch 运算符写入栈中ch=s1+i;else s2j+=ch;ch=s1+i; /把暂存在栈中的运算符依次出栈并写入到s2 串中while(！Empty(R) s2j+=pop(R); s2j+=0;求运算符优先级的Precedence函数为：int Precedence(char op)/返回运算符op所对应的优先级数值 switch(op) ca
5、se +: case -:return 1; /定义加减运算的优先级为1case *:case /:return 2; /定义乘除运算的优先级为2case : case (：return 0; /定义在栈中的左括号和栈底字符的优先级为0四、设二叉树以二叉链表形式存放。设计非递归算法，实现二叉树的中序遍历。算法如下：Status InorderTranverse(BiTree T,status(*visit)(TELemType e)/采用二叉链表存储，visit 是对数据元素操作的应用函数，中序非递归算法IniStack(S);p=T;while(p|!StackEmpty(S)if (p)P
6、ush(S,p);p=p-lchild;/根指针进栈，遍历左子树else /根指针退栈，遍历右子树Pop(S,p);if(!visit(p-data)return ERROR;p=p-rchild;Return OK;五、设二叉树以二叉链表形式存放。利用循环队列，用类 C 语言设计算法实现二叉树的按层次遍历。算法：typedef struct BiTnode/*用二叉链表存储二叉树*/TElemType data;struct BiTnode *lchild,*rchild;BiTnode,*BiTree;Status InOrderTraverse(BiTree root, Status (
7、*visit)(TElemType 2)/层次遍历算法InitStack(S);/ 初始化栈空间BiTNode* p = root; while(p!=NULL|!StackEmpty(S) /*不是空树*/if(p) Push(S,p); p = p-lchild;elsePop(S,p);Visist(p-data);p=p-rchild;/*else*/*while*/return OK;/*InOrderTraverse*/六、 （1）什么是完全二叉树?(2)画出 6 个顶点的完全二叉树。(3)设二叉树以二又链表形式存放，用类 C 语言设计算法判断一棵二又树是否为完全二叉树。（1 ）深
8、度为 k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中的编号从 1 到 n 一一对应时，称为完全二叉树。（2 ）略（3 ） int iscompletetree(BiTree p=T;if(!T) return 1;initqueue(Q); enqueue(Q,T);while(！queueempty(Q) dequeue(Q,p);if(p) enqueue(Q,p-lchild); enqueue(Q,p-rchild); if(!p) while(！queueempty(Q) dequeue(Q,p);if(p) /空节点后还有节点 return 0;
9、return 1;七、基于图的广度优先搜索策略，设计算法判别以邻接表方式存储的有向图中是否存在由顶点 vi 到 vj 的路径(ij)。注意，算法中涉及的图的基本操作必须在此存储结构上实现。int BFSTraverse_path(ALGraph G,int i,int j)for ( v = 0; v =0;k=NextAdjVex(G,i,k) )if ( !visitedk ) /* 访问顶点 u 的尚未访问的邻接点并入队 */if(k=j) return 1;/有路径visitedk = TRUE;EnQueue(Q, k);return 0;/无路径八、基于图的深度优先搜索策略，设计算
10、法判别以邻接表方式存储的有向图中是否存在由顶点 vi 到 vj 的路径(ij)。注意，算法中涉及的图的基本操作必须在此存储结构上实现。 int DFSPath(Graph G, int v, int w)/如果 v 到 w 有路径返回 1，否则返回 0;G 为有向图的邻接表for (int vi = 0; vi =0;vi=NextAdjVex(G,v,vi) if(!visitedvi) visitedvi=1;if(vi=w) return 1; /找到路径else return(DFSPath(G,vi,w) ;return 0;九、设二叉排序树以二叉链表形式存放，设计非递归算法判断二叉
11、排序树中是否存在值为X 的结点，若存在，返回其地址，否则返回空指针。typedef struct BiTnode/*用二叉链表存储二叉树*/int data;struct BiTnode *lchild,*rchild;BSTnode,*BSTree;BSNode* InsertBST(BSTree Tptr，KeyType key) BSTNode *f，*p=TPtr; /p 的初值指向根结点while(p) /查找位置if(p-key=key) return p;/找到 key，返回其地址p=(p-keykey)?p-lchild ：p-rchild;/若 p-keykey，则在左子树中
12、查找，否则在右子树中查找 /endwhile return 0; /InsertBST 十、 （1）什么是二叉排序树?（2）设二叉排序树以二叉链表形式存放设计算法，从大到小输出给定二叉排序树中结点值不小于 k 的数据元素。（1 ）二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：若他的左子树不空，则左子树上所有的结点的值均小于他的根结点的值；若他的右子树不空，则右子树上所有的结点的值均大于他的根结点的值；他的左右子树也分别是二叉排序树。（2 ）算法如下：typedef struct BiTnode/*用二叉链表存储二叉树*/TElemType data;struct BiTnode *lc
13、hild,*rchild;BiTnode,*BiTree;Status VisitKey(BiTree root, TElemType key)/通过右根左遍历顺序依次输出结点值，遇到小于给定 key 值的节点停止InitStack(S);/ 初始化栈空间BiTNode* p = root; while(p!=NULL|!StackEmpty(S) /*不是空子树*/if(p) Push(S,p); p = p-rchild;elsePop(S,p);if(p-data=key) printf(“c“，q-data);q=q-lchild;else break;/*else*/ /*while*/DestroyStack(S);/释放栈空间return OK;/*InOrderTraverse*/
