数据结构(习题三)

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