资源描述：
《计算机水平考试-程序员分类模拟题数据结构与算法(四)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、程序员分类模拟题数据结构与算法（四）试题一阅读以下说明和流程图，填补流程图屮的空缺。［说明］已知数组A［l：n］中各个元素的值都是非零整数，其中有些元素的值是相同的（重复）。为删除其中重复的值，可先通过以下流程图找岀所有的重复值，并对所有重复值赋0标记之。该流程图采用了双重循环。处理思路：如果数组A某个元索的值在前面曾出现过，则该元索赋标记值0。例如，假设数组A的各元素Z值依次为2,5,5,1,2,5,3,则经过该流程图处理后，各元素Z值依次为2,5,0,1,0,0f3o［流程图］0—试题二阅读以下说明和c函数，填补c函数屮的空缺。［说明］函数
2、SetDiff（LA,LB•的功能是将LA与LB中的共有元素从LA中删除，使得LA中仅保留与LB不同的元素，而LB不变，LA和LB为含头结点的单链表的头指针。例如，单链表LA、LB的示例如图中的（a）、（b）所示，删除与LB共有的元素后的LA如图中的（c）所示。(C)链表的结点类型定义如下：typedefstructNode{intdata；structNode*next；}Nodez*LinkList;函数SetDiff(LinkListLA,LinkListLB・的处理思路女口下：6从LA的第一个元索结点开始，令LA的第一个元索为当前元索；
3、7在LB中进行顺序查找，查找与LA的当前元素相同者，方法是：令LA的当前元素先与LB的第一个元素进行比较，若相等，则结束在LB中的查找过程，否则继续与LB的下一个元素比较，重复以上过程，直到LB中的某一个元素与LA的当前元素相等(表明查找成功)，或者到达LB的表尾(表明查找失败)为止；8结束在LB表的一次查找后，若在LB中发现了与LA的当前元索相同者，则删除LA的当前元索，否则，保留LA的当前元素；9取LA的下一个元素为当前元素，重复7、8,宜到LA的表尾。[C函数]voidSetDiff(LinkListLA,LinkListLB.{Link
4、Listpre,pazpb；/用于指向单链表LA的当前元素结点,pre指向pa所指元素的前驱*/"pb用于指向单链表LB的元索结点★/;/*开始时令pa指向LA的第一个元素*/pre=LA；while(pa){pb=LB->next；"在LB中查找与LA的当前元素相同者，直到找到或者到达表尾*/while(){if(pa->data==pb->data)break；if(!pb){/法若在LB小没有找到与LA屮当前元素相同者，则继续考察LA的后续元素法/pre=pa；pa=pa->next；01S0{八若在LB中找到与LA的当前元素相同者，贝I
5、删除LA的当前元素★/pre->next=；free(pa)；pa=;试题三阅读以下说明和流程图，填补流程图中的空缺。［说明］本流程图用于计算菲波那契数歹!){al=lza2=lfan=an-l+an-2zIn=3,4,・.・}的前n项(nN2)乞和$。例如，菲波那契数列前6项Z和为20。计算过程小，当前项Z前的两项分别动态地保存在变量A和B中。［流程图］试题四阅读以下说明和C函数，填充函数中的空缺。［说明］函数Insert_key(*rootzkey)的功能是将键值key插入到*root指向根结点的二叉查找树屮(二叉查找树为空&、〃root为
6、空指针)。若给定的二叉查找树屮已经包含键值为key的结点，则不进行插入操作并返冋0；否则巾请新结点、存入key的值并将新结点加入树中，返冋1。提不：二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具冇如下性质的二叉树：若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；左、右子树本身就是二叉查找树。设二叉查找树采用二叉链表存储结构，链表结点类型定义如F：typedefstructBiTrrode{intkey_value；/*结点的键值，为非负整数*/structB
7、iTnode*leftz*right；/*结点的左、右子树指针*/}BiTnode,*BSTree；[C函数]intInsert_key(BsTree*root,intkey)BiTnode*father=NULL,*p=*root,*s;while(&&key!=p->key_value){/*查找键值为Key的结点*/father=p；if(keykey_value)p=；/*进入左了树*/elsep=；/*进入右子树*/}..if(p)return0；/★二叉查找树中已存在键值为key的结点，无须再插入*/s=(BiTraode*
8、)malloc();/*根据结点类型生成新结点*/if(!s)return-1；s->key_value=key；s->left=NULL；s->ri
