数据结构习题三.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,数 据 结 构,习 题 三,第五部分 查找,考点一 查找的基本概念,本部分考查查找的基本概念。,2,第五部分 查找,考点一 查找的基本概念,1.,要进行线性查找，则线性表,(1),；要进行二分查找，则线性表,(2),；要进行散列查找，则线性表,(3),。某顺序存储的表格，其中有,90000,个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为,(4),，最大比较次数为,(5),。,(1)(3):A.,必须以顺序方式存储,B.,必须以链表方式存储,C.,必须以散列方式存储,D.,既可以以顺序方式，也可以以链表方式存储,E.,必须以顺序方式存储且数据元素已按值递增或递减的次序排好,F.,必须以链表方式存储且数据元素已按值递增或递减的次序排好,(4)(5),：,A.25000 B.30000 C.45000 D.90000,D,E,C,C,D,3,【,解析,】(1).,顺序存储和链式存储方式都支持线性查找。,(2).,二分查找时，数据必须以顺序方式查找，而且必须有序。若是链式存储，则只能支持顺序查找。若是数据无序，则不能二分查找。,(3).,要进行散列查找，则元素必须以散列方式进行存储。,(4).,某顺序存储的表格，其中有,90000,个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为表长的一半，即,45000,。最坏的情况下，元素在表尾的位置，需要比较约,90000,次。,第五部分 查找,考点一 查找的基本概念,4,第五部分 查找,考点二 顺序查找法,顺序查找法通常考查查找一个元素的平均查找长度。,5,第五部分 查找,考点二 顺序查找法,1.,对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为 （）,A.,从第,0,个元素往后查找该数据元素,B.,从第,1,个元素往后查找该数据元素,C.,从第,n,个元素往开始前查找该数据元素,D.,与查找顺序无关,【,解析,】,对静态表的顺序查找，通常在表头或者表尾设置岗哨，道理其实都是一样的。本题中，若在表头设置岗哨，则应该从表尾开始向表头方向查找，即从第,n,个元素开始向前查找数据元素，若查找成功，则返回该元素的位置。若返回的结果是,0,，则表示读到了岗哨，查找失败。,C,6,第五部分 查找,考点三 折半查找法,折半查找算法是本章的重点内容，也是数据结构的重点考点，主要考查：,1,、折半查找的条件；,2,、折半查找条件下的关键字比较次数、平均时间复杂度；,3,、折半查找树的建立。,7,第五部分 查找,考点三 折半查找法,1.,有一个有序表为,1,，,3,，,9,，,12,，,32,，,41,，,45,，,62,，,75,，,77,，,82,，,95,，,100,，当折半查找值为,82,的结点时，（）次比较后查找成功。,A.11 B.5 C.4 D.8,C,【,解析,】,本考点大部分题目都考查在有序表上利用折半查找算法查找元素的方法以及平均查找长度，我们不再赘述。简单地画一个顺序表,A,来帮助我们分析，如下表所示。,对上表进行折半查找元素,82,，首先，,low+high)/2=(1+13)/2=7,，显然,A7=4582,，故而，在,A8A13,中再进行折半查找。此时，,low=7+1=8,，,high=13,，,low,+high)/2=(8+13)/2=10,，显然,A10=7782,，故而在,A11,查找。因为,high=mid-1=12-1=11=low,，,Alow=Ahigh=82,，查找成功。,8,第五部分 查找,考点三 折半查找法,2.,在有,11,个关键字的有序表中进行折半查找，查找失败时的最少比较次数和最多比较次数分别是 （）,A.1,和,4 B.3,和,4 C.1,和,3 D.4,和,5,【,解析,】,折半查找的过程为：给定值首先和处于待查区间,“,中间位置,”,的关键字进行比较，若相等，则查找成功，否则将查找区间缩小到,“,前半个区间,”,或,“,后半个区间,”,之后继续进行查找。对,11,个关键字的有序表，构建其二分查找树如下图所示。,从上图可以看出，查找失败的最少比较次数为,3,，最多比较次数为,4,次，故而选择,B,答案。要特别注意，有的书把失败的比较也算作一次比较，这里我们不算一次比较。,B,9,第五部分 查找,考点四 二叉排序树,本考点主要考查：,二叉排序树的概念和构造方法,10,第五部分 查找,考点四 二叉排序树,1.,若构造一棵具有,n,个结点的二叉排序树，最坏的情况下其深度不超过,(),A.n/2 B.n C.(n+1)/2 D.n+1,B,【,解析,】,最坏的情况下，二叉排序树为单支树，比如构造一棵,1,2,3,4,5,n,的二叉树，则得到的二叉排序树如下图所示。,由上图可以看出，最坏的情况下，每插入一个结点，都在该二叉排序树的尾部插入，该二叉排序树插入结点的复杂度类似于在链表的表尾增加一个结点，该二叉排序树的深度为,n,。,11,第五部分 查找,考点五 平衡二叉树,本考点主要考查：,平衡二叉树的概念和构造方法,12,第五部分 查找,考点五 平衡二叉树,1.,由元素序列（,27,，,16,，,75,，,38,，,51,）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为,2,的结点）为,(),A.27 B.38 C.51 D.75,D,【,解析,】,由元素序列（,27,，,16,，,75,，,38,，,51,）构造平衡二叉树，首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为,2,的结点）为第一次需要旋转的部分，我们来看看构造平衡二叉树的过程（如下图）：,如上图所示，当插入结点,51,之后，有,27,和,75,两个结点失去平衡，但是首次出现的最小不平衡子树应该是离插入结点,51,最近的且平衡因子的绝对值为,2,的结点,75,，而不是,27,。,13,第五部分 查找,考点六,B,树及其基本操作、,B+,树的基本概念,这部分主要考查：,1,、考查方式是,B-,树的基本概念；,2,、,B-,树的建立；,3,、结点插入和删除时，,B-,树的调整；,4,、,B+,树。,本考点对考生提出的不是编程方面的要求，而是对,B-,树的建立、插入和删除结点时对,B-,树进行调整的手工操作。,14,1.,设输入序列为,20,45,30,89,70,38,62,，,19,依次插入到一棵,2-3,树中,(,初始状态为空,),，该,B-,树为（）。再删除,38,，该,B-,树为（）。,第五部分 查找,考点六,B,树及其基本操作、,B+,树的基本概念,B,F,15,第五部分 查找,考点六,B,树及其基本操作、,B+,树的基本概念,【,解析,】,构建,B-,树的过程如图所示。,16,第五部分 查找,考点六,B,树及其基本操作、,B+,树的基本概念,B-,树的删除操作不同于插入操作，其步骤如下：首先查找待删除关键字所在结点，并且要求删除之后，结点中的关键字个数不小于,m/2 1;,否则，要从其左（或右）兄弟结点,“,借,”,关键字；若其左右兄弟都没有关键字可以借（结点中只有最少量的关键字），则必须进行结点的合并。下面我们再来看看删除结点,38,之后，,B-,树的变化情况。如图,6.5,所示。待删除关键字,38,所在结点向其左兄弟接一个关键字，于是把父结点的,30,“,拉下来,”,，把兄弟结点里面最靠近自己的那个关键字往父结点,“,拉上去,”,，最后得到下图,(2),所示的,B-,树,17,第五部分 查找,考点六,B,树及其基本操作、,B+,树的基本概念,2.,下面关于,m,阶,B,树说法正确的是 （）每个结点至少有两棵非空子树；树中每个结点至多有,m1,个关键字；所有叶子在同一层上；当插入一个数据项引起,B,树结点分裂后，树长高一层。,B,A.B.C.D.,【,解析,】,对于,m,阶,B,树，除了根结点至少要有两棵子树之外，其他非叶子结点至少有,m/2,棵子树，故而错误。树中，每个结点至多有,m-1,个关键字，而且所有叶子都在同一层上，故而显然正确。但是，插入一个关键字使得,B,树结点分裂，并不一定会引起树长高一层，如第,2,题中插入结点,70,，,B-,树的前后高度都是,2,，故而错误。,18,第五部分 查找,考点七 哈希表,本考点主要命题有以下几种形式：,1,、什么是哈希表的特点？影响哈希表查找效率的因素有哪些？有哪些解决冲突的方法？,2,、怎么构建哈希表、怎么样利用冲突解决方案（如链地址法、二次探测再散列等）来解决冲突。这部分需要考生手工画图；,3,、计算哈希表的在查找成功和查找失败的情况下平均查找长度（或查找某一个元素的比较次数）。,19,第五部分 查找,考点七 哈希表,1.,以下说法错误的是 （）,A.,散列法存储的思想是由关键字值决定数据的存储地址,B.,散列表的结点中只包含数据元素自身的信息，不包含指针。,C.,负载因子是散列表的一个重要参数，它反映了散列表的饱满程度。,D.,散列表的查找效率主要取决于散列表构造时选取的散列函数和处理冲突的方法。,B解析,】,散列表解决冲突的办法有多种，比如线性探测法、平方探测法、再散列法等开放定址法（即：可存放新表项的空闲地址既向其同义词表项开放，也向其非同义词表项开放）。当然，还有拉链法，拉链法的散列表中的结点除了包含元素自身信息，还会有其同义词的指针，而散列地址为,i,的同义词链表的头指针存放在散列表的第,i,个单元中。,20,第五部分 查找,考点七 哈希表,2.,设哈希表长,m=14,，哈希函数,H(key)=key%11,。表中已有,4,个结点：,addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7,如用二次探测再散列处理冲突，关键字为,49,的结点的地址是（）,A.8 B.3 C.5 D.9,D,【,解析,】,二次探测再散列法，简单地理解，就是先探测,H(key)=key mod 11,，若成功，则得到,key,的地址，否则依次探测,H,（,key,）,=(key,i*i)mod 14,，直到探测到,key,的地址为止。,【,注意，处理冲突为,(mod,表长,)】,因为,H,（,49,）,=49 mod 11=5,，与,38,的地址发生冲突。再计算,H1=(5+1,2,)mod14=6,可知依然发生了冲突。再接着计算,H1=(5 1,2,)mod 14=4,可知依然发生了冲突。再接着计算,H2=(5+2,2,)mod 14=9,因为没有关键字存放在下标为,9,的位置，所以,49,可以放在下标为,9,的位置。,21,第六部分 排序,考点一 排序的基本概念,本考点考查排序的基本概念。,22,第六部分 排序,考点一 排序的基本概念,1.,一个排序算法时间复杂度大小（）有关。,A.,不与所需移动记录的数目,B.,与该算法的稳定性,C.,与所需比较关键字的次数,D.,与所需辅助存储空间的大小,【,解析,】,本题考查影响排序算法时间复杂度的因素。内部排序算法种类繁多，但就其排序所遵循的原则而言，大致可分为五大类：插入排序、交换排序、选择排序、归并排序和基数排序。算法性能主要从时间复杂度、空间复杂度和稳定性三个方面来比较。一个算法的时间复杂度，与所需要比较的关键字次数、需要移动的记录数量都有关，但是与算法是否稳定没有关系，与所需要的辅助空间也没有关系。,C,23,第六部分 排序,考点二 插入排序,本考点主要考查折半插入排序和直接插入排序。请同学们注意插入排序的复杂度、平均移动元素次数，并围绕这两个点展开复习。,24,第六部分 排序,考点二 插入排序,1.n,个关键码排序，如果选用直接插入排序方法，则元素的移动次数在最坏情况下可以达到 （）,A.n2/2 B.n(n-1)/2 C.n/2 D.(n-1)/2,B,【,解析,】,我们举一个例子，比如说，要对元素,5,、,4,、,3,、,2,、,1,这五个元素用直接插入的方法非递减排序。那么，,4,插在,5,前面，需要移动一次元素。,3,插在,4,、,5,前面，需要移动两次元素。,2,要在,3,、,4,、,5,前面，需要将,3,、,4,、,5,这三个元素后移，才能给,2,腾出位置来。,1,再插入到已有序的,2,、,3,、,4,、,5,序列中，需要把这,4,个元素都后移，才能腾出位置来放,1,。故而，总共移动了,4+3+2+1=10,次。当有,n,个元素时，最坏的情况下元素的移动次数为,N=1+2+(n-2)+(n-1)=n(n-1)/2,故而，选择,B,答案。,25,第六部分 排序,考点二 插入排序,1.,以下为直接插入排序的算法。请分析算法，并在横线上填充适当的语句。,void straightsort(seqlist r,int n),for(i=,2,;i=n;i+)r0=ri;j=i-1;while(r0.keyrj.key)rj+1=,rj,;,j-;rj+1=,r0,;,26,第六部分 排序,考点三 冒泡排序,冒泡排序的命题方式有两种：,1,、围绕记录交换次数展开；,2,、可以简单地写一个冒泡排序程序,27,1.,设一组初始记录关键字序列为,(Q,，,H,，,C,，,Y,，,P,，,A,，,M,，,S,，,R,，,D,，,F,，,X),，,则按字母升序的第一趟冒泡排序结束后的结果是（）,A.F,，,H,，,C,，,D,，,P,，,A,，,M,，,Q,，,R,，,S,，,Y,，,XB.P,，,A,，,C,，,S,，,Q,，,D,，,F,，,X,，,R,，,H,，,M,，,YC.A,，,D,，,C,，,R,，,F,，,Q,，,M,，,S,，,Y,，,P,，,H,，,XD.H,，,C,，,Q,，,P,，,A,，,M,，,S,，,R,，,D,，,F,，,X,，,Y,第六部分 排序,考点三 冒泡排序,D,【,解析,】,熟悉冒泡排序过程,28,第六部分 排序,考点四 简单选择排序,本考点主要考查简单选择排序下的比较次数和移动次数、排序的时间复杂度和稳定性，也可能考查简单选择排序算法的编写，请同学们多注意这些常见的考查点。,29,第六部分 排序,考点四 简单选择排序,2.,采用简单选择排序，比较次数与移动次数分别为 （）,A.O(n),O(logn)B.O(logn),O(n*n)C.O(n*n),O(n)D.0(nlogn),O(n),【,解析,】,简单选择排序的比较次数,KCN,与对象的初始排列无关。设整个待排序对象序列有,n,个对象，则第,i,趟选择具有最小排序码对象所需的比较次数总是,n-i-1,次。总的排序码比较次数为：,KCN=(n-1)+(n-2)+,+2+1=n(n-1)/2,当这组对象的初始状态是按其关键字从小到大有序的时候,对象的移动次数达到最少，此时,RMN=0,。最坏情况是每一趟都要进行交换，总的对象移动次数为,RMN=3(n-1),。故而比较次数时,O(,n,）,C,30,第六部分 排序,考点五 希尔排序,本考点考查希尔排序算法。希尔排序算法和基数排序算法的解题思路都挺单一，请同学们掌握解题思路，举一反三。,31,第六部分 排序,考点五 希尔排序,1.,对序列,15,，,9,，,7,，,8,，,20,，,-1,，,4,，,用希尔排序方法排序，经一趟后序列变为,15,，,-l,，,4,，,8,，,20,，,9,，,7,，则该次采用的增量是 （）,A.l B.4 C.3 D.2,B,【,解析,】,对序列,15,，,9,，,7,，,8,，,20,，,-1,，,4,，,用希尔排序方法排序，经一趟排序后序列变为,15l,，,4,，,8,，,20,，,9,，,7,。可以得知，,-1,和,9,交换了位置，增量是,4,或者,2,或者,1,。假设增量为,1,，则,-1,应该排在最前面的位置。再假设增量为,2,，则,15,、,4,、,20,、,7,一组，其他记录是另一组，排序的结果应该是,4,、,-1,、,7,、,8,、,15,、,9,、,20,，显然与题中的结果不符。故而增量,d=4,32,第六部分 排序,考点六 快速排序,快速排序主要考查两点：,1,、快速排序算法的特点；,2,、快速排序算法实现；,3,、快速排序的过程或者一趟排序的结果。,33,第六部分 排序,考点六 快速排序,1.,设一组初始记录关键字序列,(5,，,2,，,6,，,3,，,8),，以第一个记录关键字,5,为基准进行一趟快速排序的结果为 （）,A.2,，,3,，,5,，,8,，,6 B.3,，,2,，,5,，,8,，,6C.3,，,2,，,5,，,6,，,8 D.2,，,3,，,6,，,5,，,8,C,【,解析,】,快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，直到整个数据变成有序序列。,34,第六部分 排序,考点七 堆排序,堆排序主要命题有两种方式：,1,、堆排序的特点；,2,、堆排序的过程（要求同学们手工操作），包括堆的建立和输出、调整过程。,35,第六部分 排序,考点七 堆排序,1.,假定对元素序列（,7,3,5,9,1,12,）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为 （）,A.1,3,5,7,9,12 B.1,3,5,9,7,12C.1,5,3,7,9,12 D.1,5,3,9,12,7,【,解析,】,对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。,建立初始堆的过程，如后图：,B,36,第六部分 排序,考点七 堆排序,第一步：利用元素序列（,7,3,5,9,1,12,）构造完全二叉树，如图所示。,第二步：构造初始堆，从最后一个非叶子节点开始调整，调整过程如图所示。,由图得到初始堆为,1,、,3,、,5,、,9,、,7,、,12,，故而选择,B,答案。,37,本考点主要考查归并排序的方法和某一趟归并排序的结果，希望同学们会手工对关键字进行归并排序。,第六部分 排序,考点八 二路归并排序,38,第六部分 排序,考点八 二路归并排序,1.,二路归并排序的时间复杂度为 （）,A.O(n)B.O(n2)C.O(nlog2n)D.O(1og2n),C,【,解析,】,一趟归并操作是将,r1rn,中相邻的长度为,h,的有序序列进行两两归并，这需要,O,(,n,),时间。整个归并排序需要进行,log,2,n,趟，因此，总的时间代价是,O,(,n,log,2,n,),。,39,第六部分 排序,考点九 基数排序,本考点主要考基数排序的方法，要求同学们会手工操作，并给出某一趟分配和收集的结果。,40,