数据结构练习9.doc

习 题 101单项选择题。 (1)排序方法的时间效率主要用排序过程中来衡量。 A排序趟数的多少 B参加排序的序列中元素的多少 D排序过程中元素移动或者交换的次数 D排序过程中元素之间的比较次数 (2)从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放在已排序序列中的合适位置，这种排序方法称为。 A选择排序法 B插入排序法 C泡排序法 D堆积排序法 (3)每一趟排序从未排序序列中挑选一个值最小的元素，然后将其放在已排序序列的右端，这种排序方法称为。 A选择排序法 B插入排序法 C快速排序法 ， D谢尔排序法 (4)从未排序序列中任选出一个元素，该元素将当前参加排序的序列分成前后两个部分，前一部分中所有元素均小于等于所选元素，后一部分中所有元素均大于等于所选元素，而 所选元素处在排序的最终位置，然后分别对被分成的两部分中元素个数超过1的部分重 复上述过程，直至排序结束。这种排序方法称为。 A选择排序法 B插入排序法 C快速排序法 D二路归并排序法 (5)与直接插入排序方法比较，折半插入排序方法减少了排序过程中的。 A排序趟数 D元素之间的比较次数 C元素的移动次数 D辅助空间 (6)在所学过的排序方法中，排序趟数与序列的原始状态有关的方法是。 A选择排序法 B谢尔排序法 C堆积排序法 D泡排序法 (7)对序列(49，38，65，97，76，13，47，50)采用折半插入排序法进行排序，当把第七个元素47插入到已排序序列中，为寻找插入的合适位置需要进行次元素间的比较。 A3 B4 C5 D6 (8)若对序列(tang，deng，an，wang，shi，bai，fang，1iu)采用选择排序法按字典顺序进行排序，下面给出的四个序列中，是第三趟的结果。 Aan，bai，deng，wang，tang，fang，shi，1iu Ban，bai，deng，wang，shi，tang，fang，liu Can，bai，deng，wang，shi，fang，tang，1lu Dan，bai，deng，wang，shi，1iu，tang，fang (9)对于序列(49，38，65，97，13，27，50)按从小到大进行排序，是初始步长d=4的谢尔排序法第一趟的结果。 A49，76，65，13，27，50，97，38 B3，27，38，49，50，65，76，97 C97，76，65，50，49，38，27，13 D49，13，27，50，76，38，65，97 (10)对序列(Q，D，F，X，A，P，N，B，Y，M，C，W)采用二路归并排序，下面的四个序列中是第三趟的结果。 AA，B，D，F，N，P，Q，X，C，W，M，Y BA，B，F，D，N，P，Q，X，C，M，W，Y CA，B，D，F，P，Q，X，N，C，M，W，Y DA，B，D，F，N，P，Q，X，C，M，W，Y (11)对具有n个元素的序列采用选择排序法排序，排序趟数为。 An Bn-1 Cn+l DLlog2n (12)对具有n个元素的序列采用泡排序法排序，排序趟数为。 An Bn-1 C1，n D1，n-1 (13)对具有n个元素的序列采用堆积排序法排序，排序趟数为。 An B.Lnlog2nJ C.L10g2nJ Dn-1 (14)根据(大顶)堆积的定义，下面的四个序列中是一个堆积。 A75，65，30，15，25，45，20，10 B75，65，45，10，30，25，20，15 C75，45，65，30，15，25，20，10 D75，45，65，10，25，30，20，15 (15)插入排序法的时间花费主要取决于元素间的比较次数，若具有n个元素的序列初始时已经是一个递增序列，则排序过程中一共要进行次这种比较。 An Bn-1 Cn(n-1)2 Dn2 (16)插入排序法的时间花费主要取决于元素间的比较次数，若具有n个元素的序列初始时为一个递减序列，则排序过程中一共要进行次元素间的比较。 An Bn-1 Cn(n-1)2 Dn2 (17)若，则称这样的排序方法为非稳定性排序方法。 A排序前后，值相同的元素的先后相对位置可能会颠倒 B排序前后，值相同的元素的先后相对位置一定会颠倒 C对同一个序列，每次排序的结果可能不相同 D排序结果不可预测 (18)下面四种排序方法中，是一种稳定性排序方法。 A插入排序法 B.选择排序法 C快速排序法 D谢尔排序法 (19)下面四种排序方法中，占用的辅助空间最多。 A插入排序法 B堆积排序法 C快速排序法 D二路归并排序法 (20)在序列中各元素已经排好序的情况下，采用方法可以尽可能快地结束排序。 A，插入排序 B泡排序 C快速排序 D堆积排序 (21)在序列中各元素已经排好序的情况下，采用方法的时间效率最低。 A。插入排序 B泡排序 C快速排序 D堆积排序 (22)在序列中各元素已经排好序的情况下，采用方法时元素的移动次数最少。 A。选择排序 B快速排序 C堆积排序 D归并排序 (23)若序列的原始状态为9，8，7，6，5，4，3，2，1，要想获得比较好的时间效率，不应该采用下列四种排序方法中的方法。 A。谢尔排序 B快速排序 C堆积排序 D归并排序 (24)若序列的原始状态为1，2，3，4，5，10，6，7，8，9，要想使得排序过程中元素的比较次数最少，应该采用方法。 A，插入排序 B选择排序 C谢尔排序 D泡排序 (25)当参加排序的数据量较大，元素的分布又比较随机，并且无排序稳定性要求，宜选择_. A。插入排序法 B选择排序法 C快速排序法 D堆积排序法 102 请以关键字序列503，87，512，75，93，170，365，602，612为例，分别写出执行以下排序算法时每一趟排序的结果，并分别统计每一趟排序过程中所进行的关键字比较的次数。 (1)插入排序； (2)谢尔排序； (3)堆积排序； (4)二路归并排序。 103 什么是堆积?请根据堆积的定义和堆积的构造方法写出对应于序列12，18，4，36，23，41，20，50，19的初始堆积。 104 已知序列为12，2，16，30，8，28，4，10，20，6，请分别写出采用下列排序方法进行排序时每一 趟结束的结果。 (1)选择排序法； (2)泡排序法； (3)快速排序法； (4)基数排序法。 105 设有10000个元素组成的无序序列，希望尽快挑选出其中前10个(仅挑出前10个最大值元素，在不改变已有算法结构的前提下，以下几种内排序算法中哪一种最合适?为什么? (1)选择排序法； (2)快速排序法； (3)堆积排序法； (4)泡排序法。 106 请写出快速排序法的非递归算法。 107 请写出用带头结点的线性链表作为存储结构时的选择排序算法。设链表中头结点的指针为list；要求算法中不得使用除链表以外的其他链结点空间，也不得改变链结点数据域内容。 108 请写出用带头结点的双向循环链表作为存储结构时的插入排序算法。设头结点指针为list；算法中不得使用除链表外的其他链结点空间，也不得改变链结点数据域内容。 109 请回答在你所学过的内排序方法中，哪些方法是稳定的?哪些方法是不稳定的?并为每一 种不稳定的排序方法举出一个不稳定的实例。 1010 选择排序法与堆积排序法每一趟排序都是从当前未排好序的元素中选出一个元素，而一般情况下堆积排序法的时间效率远比选择排序法的时间效率要高，为什么? 1011 若n个值各不同的元素存在于数组An中，则可按如下所述过程实现的排序方法称为计数排序法：另设一个数组Bn(初值均为0)，对A中每个元素Ai，统计A中值比它小的元素的个数并存于Bi中，则与Bi0对应的元素Ai必为A中值最小的元素；然后，根据Bi值的大小将A中元素重新排列(即根据BC门确定Ai的排序位置)。请编写一算 法，实现上述排序方法。 1012 请为下列每种情况选择合适的内排序方法： (1)n=30，且要求最坏情况下速度最快； (2)n=30，且要求既要快，又要排序稳定； (3)n=1000，要求平均情况下速度最快； (4)n=1000，要求最坏情况下速度最快；(5)n=1000，要求既要快，又要最节省存储空间。历年考试题12当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（）A左子树的叶子结点B左子树的分支结点C右子树的叶子结点D右子树的分支结点13希尔排序的增量序列必须是（）A递增的B随机的C递减的D非递减的14如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为（）A插入排序B归并排序C冒泡排序D堆排序2设某二维数组A1.n，1.n，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（）AO（log2n）BO(n)CO(nlog2n)DO(n2)14下列关键码序列中，属于堆的是（）A（15，30，22，93，52，71）B（15，71，30，22，93，52）C（15，52，22，93，30，71）D（93，30，52，22，15，71）15已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为（）A16，28，34，54，73，62，60，26，43，95B28，16，34，54，62，73，60，26，43，95C28，16，34，54，62，60，73，26，43，95D16，28，34，54，62，60，73，26，43，9514一组记录的键值为（46，74，18，53，14，20，40，38，86，65），利用堆排序的方法建立的初始堆为（）A（14，18，38，46，65，40，20，53，86，74）B（14，38，18，46，65，20，40， 53，86，74）C（14，18，20，38，40，46，53，65，74，86）D（14，86，20，38，40，46，53，65，74，18）15对序列（22，86，19，49，12，30，65，35，18）进行一趟排序后得到的结果如下：（18，12，19，22，49，30，65，35，86），则可以认为使用的排序方法是（）A选择排序B冒泡排序C快速排序D插入排序12.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是( ) A.快速排序 B.堆排序 C.归并排序 D.基数排序13.不可能生成右图所示二叉排序树的关键字序列是( ) A.4 5 3 1 2 B.4 2 5 3 1 C.4 5 2 1 3 D.4 2 3 1 5 14.ALV树是一种平衡的二叉排序树，树中任一结点的( ) A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度15.在VSAM文件的控制区间中，记录的存储方式为( ) A.无序顺序 B.有序顺序 C.无序链接 D.有序链接3、某顺序存储的表格,其中有90, 000个元素,已按关键项的植的上升顺序排列。现假定对各个元素进行查的概率是相同的, 并且各个元素的关键项的值皆不相同。用顺序查找法查找时，平均比较次数约为A，最大比较次数为B。现把90,000个元素按排列顺序划分成若干组，使每组有g个元素（最后一组可能不足g个）。查找时，先从第一组开始，通过比例各组的最后一个元素的关键项的值，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的平均比较次数最小的g是C，此时的平均比较次数是D。当g的值大于等于90，000时，此方法的查找速度接近于E。 供选择的答案 A、B：25，000 30，000 45，000 90，000 C、D：100 200 300 400 E：快速分类法 斐波那契查找法 二分法 顺序查找法(试题2）堆是一种特殊的数据结构，_A_是一个堆，堆排序是一种_B_排序，m个元素进行堆排序时，其时间复杂性为_C_。排序的算法很多，若按排序的稳定性和不稳定性分类，则_D_是不稳定排序。外排序是指_E_。供选择的答案：19,75,34,26,97,56 97,26,34,75,19,5619,56,26,97,34,75 19,34,26,97,56,75：归并 交换 选择 插入：o(m) o(m2) o(log2m) o(mlog2m)：冒泡排序 归并排序 直接插入排序 希尔(shell)排序：用机器指令直接对硬盘中需排序数据排序把需排序数据，用其他大容量机器排序把外存中需排序数据一次性调入内存，排好序后，再输回外存对外存中大于内存允许空间的需排序的数据，通过多次内外存间的交换实现排序。试题6堆是一种有用的数据结构。例如关键码序列A是一个堆。堆排序是一种B排序，它的一个基本问题是如何建堆，常用的建堆算法是1964 年 Floyd 提出的，C对含 n 个元素的序列进行排序时，堆排序的时间复杂性是D，所需的附加存储结点是E。供选择的答案A： 16, 72, 31, 23, 94, 53 94, 53, 31, 72, 16, 53 16, 53, 23, 94, 31, 72 16, 31, 23, 94, 53, 72 94, 31, 53, 23, 16, 72 B： 插入 选择 交换 基数 归并C： 淘汰法 筛选法 递推法 LRU 算法D、E：O(nlog2n) O(n) O(log2n) O(n2) O(1)(试题1 )在排序算法中，两两比较待排序的记录，当发现不满意顺序要求时，变更它们的相对位置，这就是_A_ 排序。每次从未排序的记录中挑出最小(或最大)关键码值的记录，加入到已排序记录的末尾，这是_B_就组成一个堆，堆排序的平均执行时间和需附加的存储结点分别为_E_。供选择的答案 AC： 插入 枚举 交换 归并 基数 选择 希尔 D： 20、76、35、23、80、54 20、54、23、80、35、76 80、23、35、76、20、54 20、35、23、80、54、76 E： O（n2）和O（1） O（n log2 n）和O（1） O（n log2 n）和O（n） O(n2) 和O(n) 23若希望只进行8趟排序便能在4800个元素中找出其中值最小的8个元素，并且要求排序过程中所进行的关键字比较次数尽可能少，则应该选用_排序方法。27在待排序的n个记录中任取一个记录，以该记录的键值作为标准，将所有记录分为两组，使得第一组中各记录的键值均小于或等于该键值，第二组中的各记录的键值均大于该键值；然后将该记录排在两组中间。再对所分成的两组分别使用上述方法，直到所有记录都排在适当位置为止。这种排序方法称为_。28在对一组记录关键字（54，38，96，23，15，72，60，45，83）进行冒泡排序时，整个冒泡排序过程中需进行_趟才能完成。23.对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为_。24.由10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到_。28.对关键字序列(72，87，61，23，94，16，05，58)进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。初始堆：_第1趟：_第2趟：_第3趟：_(3) 给定序列100, 86, 48, 73, 35, 39, 42, 57, 66, 21, 按堆结构的定义, 则它一定( )堆。 (4) 在进行直接插入排序时, 其数据比较次数与数据的初始排列（ ）关；而在进行直接选择排序时，其数据比较次数与数据的初始排列（ ）关。33已知序列（503，87，512，61，908，170，897，275，653，462）请给出采用快速排序法作升序排序时的每一趟的结果。（8分）29已知R1.8中的元素依次为（12，5，9，20，6，31，24，27），写出按算法MergeSortDC对R进行自顶向下的二路归并排序过程中，前5次调用函数Merge(R, low, mid, high)时参数 low, mid 和high的值。 void MergeSortDC (int R, int low, int mid, int high ) int mid;if (lowhigh)mid = (low +high)/2;MergeSortDC (R, low, mid); MergeSortDC (R, mid+1, high);Merge (R, low, mid, high); / MergeSortDC （1）第一次调用时的参数值；（2）第二次调用时的参数值；（3）第三次调用时的参数值；（4）第四次调用时的参数值；（5）第五次调用时的参数值；33已知整形数组L1.8中的元素依次为（9，8，5，7，6，3，2，1），阅读下列函数，并写出执行函数调用sort(L, 8)时，对L进行的头两趟（pass分别为0和1）处理结果。Void sort (int R,int n)int pass = 0, k, exchange, x;do k=pass%2+1;exchange = 0;while (kRk+1)x = Rk; Rk = Rk+1; Rk+1 = x;exchange =1; K+=2 pass +;while (exchange = = 1| pass =1);第一趟（pass = 0）:第二趟（pass = 1）:34已知二叉排序树中结点的关键字为整数，设计递归算法按递增有序性输出树中所有大于或等于给定值x的结点，并以函数的参数返回输出的结点个数。假设以二叉链表为存储结构，其结点结构为：lchildkeyrchild33已知序列（10，18，4，3，6，12，1，9，15，8），请给出采用二路归并排序法对该序列进行升序排序时的每一趟结果。（6分）35修改冒泡排序法以实现双向冒泡排序。双向冒泡排