第6章 排的序.docxVIP

第6章排序[能力要求]计算机基础知识：掌握各种排序算法的思想和实现。分析问题：针对具体的排序问题，要能够运用各种排序方法去进行分析，找到最优的算法。解决方法和建议：在具体工程应用中，发现了关于排序的问题，要能够解决问题，并提出合理的建议。设计过程的分段与方法：采取不同的阶段去设计（概念设计、详细设计）一个具体的排序算法。软件实现过程：了解系统中各个模块中的关于排序的问题；讨论算法（数据结构、控制流程、数据流程）；使用编程语言实施低层设计（编程）。6.1知识点：直接插入排序一、选择题1②用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（）。A． 94，32，40，90，80，46，21，69 B． 32，40，21，46，69，94，90，80C． 21，32，46，40，80，69，90，94 D． 90，69，80，46，21，32，94，402②直接插入排序在最坏情况下的时间复杂度为（）A． O（） B． O（n） C． O（） D． O（）3②若对n个元素进行直接插入排序，则进行第I趟排序过程前，有序表中的元素个数为（）A．I B．I+1 C．I-1 D．1二、填空题1②直接插入排序用监视哨的作用是_____________________。【南京理工大学 2001】三、判断题（） 1②直接选择排序算法在最好情况下的时间复杂度为O（n）。【合肥工业大学2001】四、简答题1③算法模拟：设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。用直接插入排序以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。【山东工业大学 1997】五、算法题1③请编写直接插入排序算法。（用C语言写）Struct rcdtype{Int key;Element otheritem;} ARRAY[0..n]; 【北京轻工业学院 1998】6.2知识点：希尔排序一、选择题1③对序列{15，9，7，8，20，-1，4}，用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}，则该次采用的增量是（） A. l B. 4 C. 3 D. 2二、填空题1③设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需__________趟，写出第一趟结束后，数组中数据的排列次序__________。2③关键码序列{Q，H，C，Y，Q，A，M，S，R，D，F，X}，要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是_______________________________；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是________________________________。【北京大学 1997】三、简答题1③对下面数据表，写出采用SHELL排序算法排序的每一趟的结果，并标出数据移动情况。（125，11，22， 34，15，44，76，66，100，8，14，20，2，5，1）。【合肥工业大学 1999】6.3知识点：冒泡排序一、选择题1③若用冒泡排序方法对序列{10，14，26，29，41，52}从大到小排序，需进行（）次比较。A. 3 B. 10 C. 15 D. 25 2③若用冒泡排序对关键字序列{18，16，14，12，10，8}，进行从小到大的排序，所需进行的关键字比较总次数是（）。A. 10 B. 15 C. 21 D. 343②对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。（）Ａ. 从小到大排列好的Ｂ. 元素逆序Ｃ. 元素无序Ｄ. 元素基本有序4②对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为（）Ａ. n+1 Ｂ. n Ｃ. n-1 Ｄ. n（n-1）/2三、简答题1②设要求从大到小排序。问在什么情况下冒泡排序算法关键字交换的次数为最多。2③设与记录R1，R2，…，Rn对应的关键词分别是K1，K2，…，Kn。如果存在Ri和Rj使得ji且KiKj成立，试证明经过一趟冒泡后，一定有记录与Ri进行交换。【吉林大学 1996】四、算法题1④冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。【吉林大学 2001】6.4知识点：快速排序一、选择题1③有一组数据{