数据结构形考作业4

一、单项选择题（每小题2分，共42分）题目1对线性表进行二分查找时，要求线性表必须（ ）。选择一项：A. 以链接存储方式，且数据元素有序B. 以顺序存储方式，且数据元素有序C. 以链接存储方式D. 以顺序存储方式题目2采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ ）。选择一项：A. (n-1)/2B. nC. (n+1)/2D. n/2题目3有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ ）。选择一项：A. 29/9B. 26/10C. 31/10D. 29/10题目4已知一个有序表为11,22,33,44,55,66,77,88,99，则顺序查找元素55需要比较（ ）次。选择一项：A. 5B. 4C. 3D. 6题目5有数据53,30,37,12,45,24,96，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（ ）。选择一项：A. 12,24,30,37,45,53,96B. 37,24,12,30,53,45,96C. 30,24,12,37,45,96,53D. 45,24,53,12,37,96,30题目6对于顺序存储的有序表5,12,20,26,37,42,46,50,64，若采用折半查找，则查找元素26的比较次数是（ ）。选择一项：A. 4B. 5C. 6D. 3题目7在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（ ）。选择一项：A. 希尔排序B. 直接选择排序C. 直接插入排序D. 冒泡排序题目8从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（ ）。选择一项：A. 交换排序B. 归并排序C. 插入排序D. 选择排序题目9依次将每两个相邻的有序表合并成一个有序表的排序方法称为（ ）。选择一项：A. 归并排序B. 选择排序C. 交换排序D. 插入排序题目10当两个元素出现逆序的时候就交换位置，这种排序方法称为（ ）。选择一项：A. 交换排序B. 选择排序C. 插入排序D. 归并排序题目11每次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（ ）。选择一项：A. 堆排序B. 归并排序C. 插入排序D. 快速排序题目12在待排序元素基本有序的情况下，效率最高的排序方法是（ ）。选择一项：A. 归并排序B. 堆排序C. 快速排序D. 插入排序题目13对数据元素序列（49，72，68，13，38，50，97，27）进行排序，前三趟排序结果时的结果依次为第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38，50，97，27；第三趟：13，49，68，72，38，50，97，27。该排序采用的方法是（ ）。选择一项：A. 冒泡排序法B. 堆积排序法C. 选择排序法D. 插入排序法题目14对具有n个元素的任意序列采用插入排序法进行排序，排序趟数为（ ）。选择一项：A. n-1B. n+1C. nD. log2n题目15对序列（49，38，65，97，76，13，47，50）采用直接插入排序法进行排序，要把第七个元素47插入到已排序中，为寻找插入的合适位置需要进行（ ）次元素间的比较。选择一项：A. 3B. 6C. 5D. 4题目16排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（ ）排序。选择一项：A. 快速B. 归并C. 选择D. 插入题目17一组记录的关键字序列为（40，80，65，100，14，30，55，50），利用堆排序的方法建立的初始小根堆为（ ）。选择一项：A. 14，40，30，50，80，65，55，100B. 40，14，30，50，80，65，55，100C. 40，80，65，50，14，30，55，100D. 40，80，30，50，14，65，55，100题目18一组记录的关键字序列为（25，48，16，35，79，82，23，40，36，72），其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（ ）。选择一项：A. 16，25，35，48，79，82，23，36，40，72B. 16，25，48，35，79，82，23，36，40，72C. 16，25，35，48，23，40，79，82，36，72D. 16，25，35，48，79，23，36，40，82，72题目19已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列从小到大排序，经过一趟冒泡排序后的序列为（ ）。选择一项：A. 16，28，34，54，73，62，60，26，43，95B. 16，28，34，54，62，60，73，26，43，95C. 28，16，34，54，62，73，60，26，43，95D. 28，16，34，54，62，60，73，26，43，95题目20一组记录的关键字序列为（56，30，89，66，48，50，94，87，100），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ ）。选择一项：A. 48，30，50，56，66，89，94，87，100B. 50，30，48，66，56，89，94，87，100C. 30，50，48，56，66，89，94，100，87D. 50，30，48，56，66，89，94，87，100题目21如果要求一个线性表既能较快地查找，又能动态适应变化要求，可以采用（ ）查找方法。选择一项：A. 折半B. 顺序C. 分块D. 散列二、填空题（每小题1分，共16分）题目22在各种查找方法中，平均查找长度与结点个数n无关的查找方法是哈希表查找法。题目23关键字是记录某个数据项的值，用它可以识别、确定一个记录。题目24在一个查找表中，能够唯一地确定一个记录的关键字称为主关键字。题目25平均查找长度是指为确定记录在查找表中的位置，需要与给定值进行比较的关键字个数的数学期望值。题目26顺序查找是一种最简单的查找方法。题目27折半查找又称为二分查找。使用该查找算法的前提条件是，查找表中记录相应的关键字值必须按升序或降序排列。题目28折半查找只适用于顺序存储结构的有序表。题目29分块查找又称为索引顺序查找，它是一种介于顺序查找和折半查找之间的查找方法。题目30二叉排序树或者是一棵空树，或者是具有下列性质的一棵二叉树：（1）若左子数不空，则左子树所有结点的值均小于根结点的值。（2）若右子数不空，则右子树所有结点的值均大于根结点的值。（3）左右子树又分别是二叉排序树。题目31哈希表是用来存放查找表中记录序列的表，每一个记录的存储位置是以该记录得到关键字为自变量，由相应哈希函数计算所得到的函数值。题目32冒泡排序是一种比较简单的交换排序方法。题目33在对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需要比较3次。题目34在堆排序和快速排序中，若原始记录接近正序和反序，则选用堆排序，若原始记录无序，则最好选用快速排序。题目35n个元素进行冒泡法排序，通常需要进行n-1趟冒泡，第j趟冒泡要进行n-j次元素间的比较。题目36当从一个小根堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整。题目37对记录序列排序是指按记录的某个关键字排序，记录序列按关键字排序结果是唯一的。三、综合题（每小题7分，共42分）题目38已知序列（70，83，100，105，10，32，7，9），请写出对此序列采用插入排序法进行升序排序时各趟的结果。原始序列：（70），83，100，65，10，32，7，9第1趟：（70，83），100，65，10，32，7,，9第2趟：（70，83，100），65，10，32，7，9第3趟：（65，70，83，100），10，32，7，9第4趟：（10，65，70，83，100），32，7，9第5趟：（10，32，65，70，83，100），7，9第6趟：（7，10，32，65，70，83，100），9第7趟：（7，9，10，32，65，70，83，100）题目39已知序列（10，18，4，3，6，12，1，9，15，8），请写出对此序列采用归并排序法进行升序排序时各趟的结果。原始序列：10,18,4,3,6,12,1,9,15,8第1趟：10,183,46,121,98,15第2趟：3,4,10,18,1,6,9,128,15第3趟：3,4,10,18,1,6,8,9,12,15第4趟：1,3,4,6,8,9,10,12,15,18题目40已知序列（17，18，60，40，7，32，73，65，85）请给出采用冒泡排序法对该序列作升序排列时的每一趟结果。原始序列：256,301,751,129,937,863,742,694,076,438第1趟：256,301,129,751,863,742,694,076,438,937第2趟：256,129,301,751,742,694,076,438,863,937第3趟：129,256,301,742,694,076,438,751,863,937第4趟：129,256,301,694,076,438,742,751,863,937第5趟：129,256,301,076,438,742,694,751,863,937第6趟：129,256,076,301,438,742,694,751,863,937第7趟：129,076,256,301,438,742,694,751,863,937第8趟：129,076,256,301,438,742,694,751,863,937第9趟：129,076,256,301,438,742,694,751,863,937题目41（1）利用筛选过程把序列42，82，67，102，16，32，57，52建成堆（小根堆），画出相应的完全二叉树（不要求中间过程）。（2）写出对上述堆对应的完全二叉树进行中序遍历得到的序列。(1) 堆 初始树（2）102,52,42,82,16,67,32,57题目42设查找表为（20，19，24，57，68，11）（1）用冒泡对该表进行排序，要求写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？（2）在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。（要求以数据元素作为树结点）（3）求在等概率条件下，对上述有序表成功查找的平均查找长度。（1）原序列16 15 20 53 64 7 15 16 20 53 7 64 n-1趟 15 16 20 7 53 64 n-j次 15 16 7 20 53 64 7 15 16 20 53 64 (2)（3）平均查找长度=（1*1+2*2+3*3）/6=14/6题目43如下是一棵二叉排序树，A1，A2，A9代表1，2，3，9中各个不同数字，（1）给出对该树中序遍历的结果。（2）A3，A5，A7的值各为多少？（3）请在该树中再插入一个结点9.5作为叶结点，并使它仍然是一棵二叉排序树。（1）A7 A4 A8 A2 A5 A9 A1 A3 A6(2)8 5 1（3）