数据结构算法应用题.doc

一、举例说明二分查找的基本思想，并用类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比较，因为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-next ；/分别指向第一个结点Lc = pc = La ；/用La的头节点作为Lc的头节点while ( pa & pb ) if ( pa-data data ) pc-next = pa ；pc = pa ；pa = pa-next ；else pc-next = pb ；pc = pb ；pb = pb-next ； pc-next = pa ? pa : pb ；/处理剩余部分free (Lb) ；三、假设表达式由单字母变量和双目四则运算符(+，-，*，/)构成，用类C语言设计算法将一个通常书写形式且书写正确的表达式转换为逆波兰式。void Change(char* s1, char* s2) /将字符串s1中的中缀表达式转换为存于字符串s2中的后缀表达式 Stack R; /定义用于暂存运算符的栈 InitStack(R); /初始化栈 Push(R,); /给栈底放入字符，它具有最低优先级0 int i,j; i=0; /用于指示扫描s1串中字符的位置，初值为0 j=0; /用于指示s2串中待存字符的位置，初值为0 char ch=s1i; /ch保存s1串中扫描到的字符，初值为第一个字符 while(ch!=) /顺序处理中缀表达式中的每个字符 if(ch=+|ch=-|ch=*|ch=/) /对于四则运算符，使暂存在栈中的不低于ch优先级的运算符依次出栈并写入到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) case +: case -: return 1; /定义加减运算的优先级为1 case *:case /: return 2; /定义乘除运算的优先级为2 case : case (： return 0; /定义在栈中的左括号和栈底字符的优先级为0 四、设二叉树以二叉链表形式存放。设计非递归算法，实现二叉树的中序遍历。算法如下：Status InorderTranverse(BiTree T,status(*visit)(TELemType e)/采用二叉链表存储，visit是对数据元素操作的应用函数，中序非递归算法IniStack(S);p=T;while(p|!StackEmpty(S)if (p)Push(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 (*visit)(TElemType 2)/层次遍历算法 InitStack(S);/ 初始化栈空间BiTNode* p = root; while(p!=NULL|!StackEmpty(S) /*不是空树*/if(p) Push(S,p); p = p-lchild;else Pop(S,p); Visist(p-data); p=p-rchild;/*else*/ /*while*/ return OK;/*InOrderTraverse*/六、（1）什么是完全二叉树?(2)画出6个顶点的完全二叉树。(3)设二叉树以二又链表形式存放，用类C语言设计算法判断一棵二又树是否为完全二叉树。（1）深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中的编号从1到n一一对应时，称为完全二叉树。（2）略（3）int iscompletetree(BiTree &T,LinkQueue &Q)/是完全二叉树返回1，否则返回0、 BiTree p; 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; 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;/无路径八、基于图的深度优先搜索策略，设计算法判别以邻接表方式存储的有向图中是否存在由顶点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;九、设二叉排序树以二叉链表形式存放，设计非递归算法判断二叉排序树中是否存在值为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，则在左子树中查找，否则在右子树中查找 /endwhile return 0; /InsertBST 十、（1）什么是二叉排序树?（2）设二叉排序树以二叉链表形式存放设计算法，从大到小输出给定二叉排序树中结点值不小于k的数据元素。（1）二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：若他的左子树不空，则左子树上所有的结点的值均小于他的根结点的值；若他的右子树不空，则右子树上所有的结点的值均大于他的根结点的值；他的左右子树也分别是二叉排序树。（2）算法如下：typedef struct BiTnode/*用二叉链表存储二叉树*/ TElemType data; struct BiTnode *lchild,*rchild;BiTnode,*BiTree;Status VisitKey(BiTree root, TElemType key)/通过右根左遍历顺序依次输出结点值，遇到小于给定key值的节点停止 InitStack(S);/ 初始化栈空间BiTNode* p = root;