《数据结构》期末复习题及参考答案 - 第9章 查找【HSH2013级】给学生.docx

数据结构期末复习题及参考答案 - 第9章 查找一、 选择题 1、适用于折半查找的表的存储方式及元素排列要求为( ) A链接方式存储，元素无序 B链接方式存储，元素有序C顺序方式存储，元素无序 D顺序方式存储，元素有序2、对有18个元素的有序表A作折半查找，则查找A3的比较序列的下标为（ ） A.1，2，3 B.9，5，2，3 C.9，5，3 D.9，4，2，3 3、对有14个数据元素的有序表R进行折半搜索，搜索到R3的关键字等于给定值，查找过程中元素比较的顺序依次为（ ）。A. R6, R2 ,R4, R3 B. R6, R4 ,R2, R3C. R0, R1 ,R2, R3 D. R0, R13 ,R2, R34、对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) A（N+1）/2 B. N/2 C. N D. （1+N）*N /25、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下 查找成功所需的平均比较次数为（ ）。 A35/12 B.37/12 C.39/12 D.43/12 6、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) A必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减7、设有序表的关键字序列为1，4，6，10，18，35，42，53，67，71，78，84，92，99，当用二分查找法查找健值为84的结点时，经（ ）次比较后查找成功。A.2 B. 3 C. 4 D.128、在查找过程中，只完成查找操作，这种查找称为（ ）A. 静态查找B.动态查找C.内部查找D.外部查找9、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A（100，80，90，60，120，110，130） B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130） D. (100，80， 60，90，120，130，110)二、填空题1、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找失败，它们的平均查找长度是 不同的 ，对于查找成功,他们的平均查找长度是 相同的 。2、执行顺序查找时，储存方式可以是_顺序存储或链式存储 _，二分法查找时，要求线性表_顺序存储且有序_。3、在数据结构中一般采用平均查找长度衡量查找算法时间性能，而对于排序算法一班通过统计记录的比较次数和移动次数衡量排序算法的时间性能。4、设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较 _7_ 次就可以断定数据元素X是否在查找表中5、二叉查找树的查找效率与二叉树的 树型 有关, 在 呈单枝树 时其查找效率最低。6、若表中元素个数为n，则顺序查找该表中的元素，若查找成功，则比较关键字的次数最多为_n _次，平均比较次数为 (n+1)/2 ；若进行折半查找，则最大比较次数是 _2n+1 。7、给定一个主关键字，在长为n的有序表中进行折半查找，则最多经过 log2n +1次比较即可确定该关键字是否在表中，至少经过1次比较即可确定该关键字在表中。8、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为_4_。9、在有序表A1.12中，采用二分查找算法查等于A12的元素，所比较的元素下标依次为_6,9,11,12 。10、己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需_2_次查找成功，47时_4_成功，查100时，需_3_次才能确定不成功。11、假定查找有序表A1.12中每个元素的概率相等，则进行二分查找时的平均查找长度为_37/12_。12、在查找中，能够唯一标识一个记录的关键字称之为主关键字，能够标识若干记录的关键字称之为次关键词。13、动态查找表和静态查找表的重要区别在于前者包含有_插入 _和_ 删除_运算，而后者不包含这两种运算。14、已知二叉排序树的左右子树均不为空，则_左子树_上所有结点的值均小于它的根结点值，_ 右子树_上所有结点的值均大于它的根结点的值。三、简答题1、设有序表为(a, b, c, d, e, f, g, h, i, j, k, p, q)，请分别画出对给定值a, g和n进行折半查找的过程。【答案】（1）查找a的过程如下(圆括号表示当前比较的关键字)，经过三次比较，查找成功。（2）g的查找过程如下，一次比较成功。 abcdef(g)hijkpq（3）n的查找过程如下，经过四次比较，查找失败。2、构造有12个元素的二分查找的判定树，并求解下列问题：（1）各元素的查找长度最大是多少？（2）查找长度为1、2、3、4的元素各有多少？具体是哪些元素？（3）查找第5个元素依次要比较哪些元素？（4）试求解在等概率情况下，查找成功情况下二分查找的平均查找长度。【答案】12个元素的二叉判断树如下图所示：（1）最大查找长度是树的深度4。（2）查找长度为1的元素有1个，为第6个，查找长度为2的元素有2个，为第3个和第9个，查找长度为3的元素有4个，为第1、4、7、11个，查找长度为4的元素有5个，为第2、5、8、10、12个。（3）查找第五个元素依次比较6，3，4，5。（4）根据, 平均查找长度ASL =（1+2*2+4*3+5*4）/12 = 37/12 3、设有一个输入数据的序列是 46, 25, 78, 62, 12, 80 , 试画出从空树起，逐个输入各个数据而生成的二叉排序树。答案：4、已知序列40，30，50，24，28，46，60，10。试画出由该输入序列构成的二叉排序树，并分别给出依次执行下列操作后的二叉排序树（共画四棵树） （1）插入数据42和80；（2）删除数据30；（3）删除数据50。答案：四、算法分析题1、若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：（1）查找不成功，即表中无关键字等于给定值K的记录；（2）查找成功，即表中有关键字等于给定值K的记录。【答案】（1）不成功时需要n+1次比较（2）成功时平均为(n+1)/2次【解析】有序表和无序表顺序查找时，都需要进行n+1次比较才能确定查找失败。因此平均查找长度都为n+1。查找成功时，平均查找长度都为(n+1)/2，有序表和无序表也是一样的。因为顺序查找与表的初始序列状态无关。2、为什么有序的单链表不能进行折半查找?【答案】因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。3、阅读下列二叉排序树的插入算法代码，并完成填空。【算法源代码】#include type.h#include stdio.hBiTreeinsort(BiTreebt, ElemType x)/* 向以BT为树根的二叉排序树上插入值为x的结点。函数返回二叉排序树头指针*/BiTreep,q;p=( BiTree)malloc(sizeof(BiTNode); /*生成新结点*/p-data=x;p-lchild=NULL;p-rchild=NULL;q=bt;if(q=NULL) bt=p;/*二叉排序树为空*/else /*二叉排序树不空*/while(q-lchild!=p)&( q-rchild!=p) if(xdata) /*插入到左子树*/ if(q-lchild!=NULL) q=q-lchild; elseq-lchild=p; else /*插入到右子树*/if(q-rchild!=NULL)q=q-rchild;else q-rchild=p; return(bt); /*返回二叉排序树的头指针*/五、算法描述题有递增排序的顺序线性表An，写出利用二分查找算法查找元素K的递归算法。若找到则给出其位置序号，若找不到则其位置号为0。int Binsch( SSElement A, int low, int high, ElemType K ) int mid;if(low=high )int mid=(low+high)