数据结构第九、十章 作业答案.doc

1第九章 查找一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值 k，用二分法检索表中与 k 相等的元素，在查找不成功的情况下，最多需要检索 8 次设有 100 个结点，用二分法查找时，最大比较次数是 7 3. 假设在有序线性表 a[1..20]上进行折半查找，则比较一次查找成功的结点数为 1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是 1,3,6,8,11,13,16,19______，平均查找长度为 3.7 解：显然，平均查找长度＝O（log 2n）high) return 0; //查找不到时返回 0 mid=(low+high)/2; if(ST.elem[mid].key= =key) return mid; else if(ST.elem[mid].key>key) return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(ST, key, mid+1, high); } }//Search_Bin_Recursive 2.试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。

且树中结点的关键字均不同解：注意仔细研究二叉排序树的定义易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树”（刘注：即不能只判断左右孩子的情况，还要判断左右孩子与双亲甚至根结点的比值也要遵循（左小右大）原则） 若要采用递归算法，建议您采用如下的函数首部：bool BisortTree(BiTree T, BiTree&PRE)，其中 PRE 为指向当前访问结点的前驱的指针或者直接存储前驱的数值，随时与当前根结点比较）一个漂亮的算法设计如下：int last=0, flag=1; // last 是全局变量，用来记录前驱结点值，只要每个结12点都比前驱大就行int Is_BSTree(Bitree T) //判断二叉树 T 是否二叉排序树，是则返回 1，否则返回0 { if(T->lchild if(T->datadata; if(T->rchild return flag; }//Is_BSTree 3. 已知一个含有 1000 个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过 3。

解：设计哈希表的步骤为：a) 根据所选择的处理冲突的方法求出装载因子 a 的上界；b) 由 a 值设计哈希表的长度 m；c) 根据关键字的特性和表长 m 选定合适的哈希函数刘注：要求 ASL≤3，则 m 必然要尽量长，以减少冲突；4. 已知某哈希表的装载因子小于 1，哈希函数 H(key)为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法解：注意此题给出的条件：装载因子 a〈1, 则哈希表未填满由此可写出下列形式简明的算法：void PrintWord(Hash Table ht){//按第一个字母的顺序输出哈希表 ht 中的标识符哈希函数为表示符的第一个字母在字母表中的序号，处理冲突的方法是线性探测开放定址法for(i=1; ir[j+1].key THENBEGIN flag:= (4)___; t:=r[j]; r[j]:=r[j+1]; r[j+1]:=tEND;i:=i+1;m:=m-1END; END. （1） 请在上面横线上填上适当的语句，完成该算法程序2） 设计标志 flag 的作用是什么？（3） 该算法结点的最大比较次数和最大移动次数是多少？（4） 该分类算法稳定吗？答：[略]2、有 n 个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。

注：双向起泡排序即相邻两趟排序向相反方向起泡）答： typedef struct node{ ElemType data;struct node *prior,*next;}node，*DLinkedList;20void TwoWayBubbleSort(DLinkedList la)//对存储在带头结点的双向链表 la 中的元素进行双向起泡排序{int exchange=1; // 设标记 DLinkedList p,temp,tail;head=la //双向链表头，算法过程中是向下起泡的开始结点tail=null; //双向链表尾，算法过程中是向上起泡的开始结点while (exchange){p=head->next; //p 是工作指针，指向当前结点exchange=0; //假定本趟无交换 while (p->next!=tail) // 向下（右）起泡，一趟有一最大元素沉底if (p->data>p->next->data) //交换两结点指针，涉及 6 条链{temp=p->next; exchange=1;//有交换p->next=temp->next;temp->next->prior=p //先将结点从链表上摘下temp->next=p; p->prior->next=temp; //将 temp 插到 p 结点前temp->prior=p->prior; p->prior=temp;}else p=p->next; //无交换，指针后移tail=p; //准备向上起泡p=tail->prior;while (exchange && p->prior!=head) //向上（左）起泡，一趟有一最小元素冒出if (p->dataprior->data) //交换两结点指针，涉及 6 条链{temp=p->prior; exchange=1; //有交换p->prior=temp->prior;temp->prior->next=p；//先将 temp 结点从链表上摘下temp->prior=p; p->next->prior=temp; //将 temp 插到 p 结点后（右）temp->next=p->next; p->next=temp;}else p=p->prior; //无交换，指针前移head=p; //准备向下起泡}// while (exchange)} //算法结束213、对单链表中元素用插入法按从小到大排序的算法描述如下（L 为链表头结点指针），请将该算法补充完整。

typedef struct node{int data; struct node *next;}linknode,*link;void Insertsort(link L){ link p,q,r,s;p=L->next; L->next=null ;while(p!=null){ r=L; q=L->next;while(_ q!=null && （1） ； ){r=q;（2） ;}s=p->next; （3） _; _ （4）_____; p=s;}}（1） _ （2） _ （3） _ （4） _（1）q->datadata （2）q=q->next （3）p->next=r->next （4）r->next=p 4、。