第9章 查找答案.doc

第9章 查找9.1知识点:静态查找表一、填空题1. 顺序查找（线性查找） 2. 查找表 3.静态查找表 动态查找表 4. log2n+1 5. 分块查找 关键字有序排列 索引表 6. O（m+n) （m是块长度，n是索引表长度） 7.n n+1二、选择题1.B 2.D 3.A 4.B. 三、判断题1. 2. 3. 4. 四、简答题1答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。2（1） 先画出判定树如下（注：mid=(1+12)/2=6）：(2)查找元素54，需依次与30, 63, 42, 54 等元素比较；(3) 查找元素90，需依次与30, 63,87, 95等元素比较；(4)求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找12243=17次；但最后一层未满，不能用84，只能用54=20次，所以ASL1/12（1720）37/123.083.（1）每块理想长度d=45 （2）块数b=2000/45=45 (3)ASL=(b+1)/2+(d+1)/2=(45+1)/2+(45+1)/2=46 (4)b= 2000/20=100(块) 每块元素个数d=20 ASL=(b+1)/2+(d+1)/2 =(100+1)/2+（20+1）/2=61五、算法设计题1 /折半查找的递归算法 int Search_Bin_Recursive(SSTable ST, int key, int low, int high) if(lowhigh) return 0; /查找不到时返回0 mid=(low+high)/2; if(ST.elemmid.key= =key) return mid; else if(ST.elemmid.keykey) return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(ST, key, mid+1, high); /Search_Bin_Recursive int search(SqList S, KeyType x)/折半查找的非递归算法/二分查找，返回有序表中大于等于x的元素位置int low=1,high=L.length;while(low=high)mid=(low+high)/2;if(S.elemmid.key=x) return midelseif(S.elemmid.keylchild&flag) Is_BSTree(T-lchild); if(T-datadata; if(T-rchild&flag) Is_BSTree(T-rchild); return flag; /Is_BSTree 2 BSTNode * BSTSearch(BSTNode *bt,KeyType k) BSTNode *p=bt; while( p!=NULL & p-key!=k) if(kkey ) p=p-lchild; /沿左子树查找 else p=p-rchild; /沿右子树查找 return p; 3 balance为平衡二叉树的标记，返回二叉树bt是否为平衡二叉树，若是balance为1，否则为0。H为二叉树bt的高度。采用递归先序遍历的判断方法。 void judgeAVL(BSTNode *bt, int &balance,int &h) int bl,br,hl,hr; if(bt=NULL) h=0; balance=1 else if(b-lchild=NULL & bt-rchild=NULL) h=1; balance=1 else judgeAVL(bt-lchild,bl,hl); judgeAVL(bt-rchild,br,br);h=(hlhr?hl:hr)+1; if (abs(hl-hr)2) balance=bl&br; /&为整数的逻辑与 else balance=0;9.3知识点：哈希表一、填空题1. 表中结点数目 负载因子 2. n(n-1)/2 3. 直接定址 4. 小于等于表长的质数（素数）5.哈希函数 解决冲突的方法 6.存取元素时发生冲突的可能性就越大 存取元素时发生冲突的可能性就越小二、选择题1. A B C D 2.D 3.D三、判断题1. 2. 3. 4. 5. 四、简答题1.（1）画表如下：0011223344556677889911011111211311411511611733211763492044010303146471111663311221111113333（2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。（4） ASL=1/11（61*6+233）23/11=2.092. ASL=(1*7+2*4+3)/12=18/12=1.5五、算法设计题1.void PrintWord(HashTable ht)/按第一个字母的顺序输出哈希表ht中的标识符。哈希函数为表示符的第一个字母在字母表中的序号，处