精华内容
下载资源
问答
  • 对n个记录的线性表进行快速排序为减少算法的递归(栈)深度,每次分区后,先处理较短的部分。 举个栗子。 现在有这么个序列:123456789 假设每次划分出短序列的长度为1 即第一次划分 短序列:1 长序列:23456789 如果...

    对n个记录的线性表进行快速排序为减少算法的递归(栈)深度,每次分区后,先处理较短的部分。
    举个栗子。
    现在有这么个序列:123456789
    假设每次划分出短序列的长度为1
    即第一次划分
    短序列:1
    长序列:23456789
    如果优先处理短序列1
    则栈中仅用保存23456789,深度为1
    然后23456789出栈,划分
    短序列:2
    长序列:3456789
    同样的先处理短序列
    栈中保存3456789,深度为1
    类推下去,处理完整个序列,栈的最大深度都为1

    假如每次划分出的短序列长度为2呢
    短序列:12
    长序列:3456789
    优先处理短序列12
    栈中保存3456789 深度为1
    12只能划分为同样长度的序列1和2
    先处理左边的
    栈保存2 此时栈中有3456789 和 2 深度为2
    然后2 出栈 处理
    接着3456789出栈
    划分为短序列34
    长序列 56789
    处理短序列34
    栈中保存56789
    类推下去,处理完整个序列,栈的最大深度都为2

    也就是说栈的最大深度取决于划分出来的短序列的长度 (前提是先处理短序列)

    那么先处理长序列呢
    短序列:1
    长序列:23456789
    如果优先处理长序列序列23456789 短序列入栈,长序列划分为2和3456789
    2入栈,3456789划分
    。。。
    8入栈,9处理
    此时栈中有12345678 深度为8

    短序列:12
    长序列:3456789
    12入栈 3456789划分为34和56789
    34入栈 56789划分为56和789
    56入栈 789划分为78和9
    9入栈 78划分为7和8
    7入栈 8处理
    此时栈中有12 34 56 9 7 深度为5

    很明显先处理长序列 栈的深度要大于 先处理短序列栈的深度。

    展开全文
  • 1.考前密押试题对长度为n的线性表排序,在最坏情况下,比较次数不是n(n-1)/2的排序方法是答案:AA)堆排序B)冒泡排序C)快速排序D)直接插入排序2.考前密押试题下列关于栈的叙述正确的是A)栈按"先进后出"组织数据B)栈...

    1.

    考前密押试题 对长度为n的线性表排序,在最坏情况下,比较次数不是n(n1)/2的排序方法是

    答案:A

    A)堆排序

    B)冒泡排序

    C)快速排序

    D)直接插入排序

    2.

    考前密押试题 下列关于栈的叙述正确的是

    A)栈按"先进后出"组织数据

    B)栈按"先进先出"组织数据

    C)不能删除数据

    D)只能在栈底插入数据

    3.

    考前密押试题 某二叉树有5个度为2的结点,则该二叉树中的叶子结点数是

    答案:D

    A)4

    B)8

    C)10

    D)6

    4.

    考前密押试题 下列叙述中正确的是

    A)算法的复杂度包括时间复杂度与空间复杂度

    B)算法复杂度是指算法控制结构的复杂程度

    C)算法复杂度是指设计算法的难度

    D)算法的时间复杂度是指设计算法的工作量

    5.

    考前密押试题 下列叙述中正确的是

    答案:B

    A)在循环队列中,只需要队尾指针就能反映队列中元素的动态变化情况

    B)循环队列中元素的个数是由队头指针和队尾指针共同决定

    C)循环队列有队头和队尾两个指针,因此,循环队列是非线性结构

    D)在循环队列中,只需要队头指针就能反映队列中元素的动态变化情况

    6.

    考前密押试题 在长度为n的有序线性表中进行二分查找,最坏情况下需要比较的次数是

    A)O(n2)

    B)O(nlog2n)

    C)O(log2n)

    D)O(n)

    7.

    考前密押试题 下列叙述中正确的是

    答案:A

    A)顺序存储结构的存储一定是连续的,链式存储结构的存储空间不一定是连续的

    B)链式存储结构比顺序存储结构节省存储空间

    C)顺序存储结构只针对线性结构,链式存储结构只针对非线性结构

    D)顺序存储结构能存储有序表,链式存储结构不能存储有序表

    8.

    考前密押试题 对于循环队列,下列叙述中正确的是

    A)队头指针可以大于队尾指针,也可以小于队尾指针

    B)队头指针是固定不变的

    C)队头指针一定大于队尾指针

    D)队头指针一定小于队尾指针

    9.

    考前密押试题 算法的空间复杂度是指

    答案:B

    A)算法在执行过程中所需要的临时工作单元数

    B)算法在执行过程中所需要的计算机存储空间

    C)算法所处理的数据量

    D)算法程序中的语句或指令条数

    10.

    考前密押试题 一个栈的初始状态为空。现将元素12345ABCDE依次入栈,然后再依次出栈,则元素出栈的顺序是

    A)12345ABCDE

    B)54321EDCBA

    C)EDCBA54321

    D)ABCDE12345

    11.

    考前密押试题 下列排序方法中,最坏情况下比较次数最少的是

    答案:C

    A)简单选择排序

    B)直接插入排序

    C)堆排序

    D)冒泡排序

    12.

    考前密押试题 支持子程序调用的数据结构是

    A)栈

    B)树

    C)二叉树

    D)队列

    13.

    考前密押试题 算法的有穷性是指

    答案:D

    A)算法程序所处理的数据量是有限的

    B)算法只能被有限的用户使用

    C)算法程序的长度是有限的

    D)算法程序的运行时间是有限的

    14.

    考前密押试题 下列数据结构中,属于非线性结构的是

    A)带链栈

    B)二叉树

    C)循环队列

    D)带链队列

    15.

    考前密押试题 下列叙述中正确的是

    答案:C

    A)循环队列是非线性结构

    B)队列是“先进后出”的线性表

    C)有序线性表既可以采用顺序存储结构,也可以采用链式存储结构

    D)栈是“先进先出”的线性表

    16.

    考前密押试题 下列数据结构中,能够按照“先进后出”原则存取数据的是

    A)栈

    B)二叉树

    C)循环队列

    D)队列

    17.

    考前密押试题 下列叙述中正确的是

    答案:A

    A)线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构

    B)线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构

    C)线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的

    18.

    考前密押试题 下列叙述中正确的是

    A)栈与队列都是线性结构

    B)栈与队列都是非线性结构

    C)队列是一种后进先出的线性表

    D)栈是一种先进先出的线性表

    19.

    考前密押试题 一棵完全二叉树共有360个结点,则在该二叉树中度为1的结点个数为

    答案:B

    A)0

    B)1

    C)181

    D)180

    20.

    考前密押试题 算法的时间复杂度是指

    A)算法中指令的条数

    B)执行该算法所需要的时间

    C)设计该算法所需的工作量

    D)执行该算法时所需要的基本运算次数

    21.

    考前密押试题 下列关于栈叙述正确的是

    答案:A

    A)栈顶元素最先能被删除

    B)栈底元素永远不能被删除

    C)栈顶元素最后才能被删除

    22.

    考前密押试题 下列叙述中正确的是

    A)在栈中,栈底指针不变,栈中元素随栈顶指针的变化而动态变化

    B)在栈中,栈中元素随栈底指针与栈顶指针的变化而动态变化

    C)在栈中,栈顶指针不变,栈中元素随栈底指针的变化而动态变化

    23.

    考前密押试题 某二叉树共有7个结点,其中叶子结点只有1个,则该二叉树的深度为(假设根结点在第1层)

    答案:C

    A)4

    B)6

    C)7

    D)3

    24.

    考前密押试题 设循环队列存储空间为Q(1:50),初始状态为front=rear=50。经过一系列入队和退队操作后,front=rear=25,则该循环队列中元素个数为

    A)25

    B)0或50

    C)26

    D)24

    25.

    考前密押试题 下列叙述中正确的是

    答案:A

    A)设计算法时要考虑时间复杂度和空间复杂度

    B)设计算法时只需要考虑结果的可靠性

    C)算法就是程序

    D)设计算法时只需要考虑数据结构的设计

    26.

    考前密押试题 下列叙述中正确的是

    A)双向链表是非线性结构

    B)有一个以上根结点的数据结构不一定是非线性结构

    C)只有一个根结点的数据结构不一定是线性结构

    D)循环链表是非线性结构

    27.

    考前密押试题 下列关于二叉树的叙述中,正确的是

    答案:D

    A)叶子结点数是度为2的结点数的两倍

    B)叶子结点总是比度为2的结点少一个

    C)度为2的结点数是度为1的结点数的两倍

    D)叶子结点总是比度为2的结点多一个

    28.

    考前密押试题 下列各组的排序方法中,最坏情况下比较次数相同的是

    A)堆排序与希尔排序

    B)简单插入排序与希尔排序

    C)快速排序与希尔排序

    D)冒泡排序与快速排序

    29.

    考前密押试题 下列叙述中正确的是

    答案:D

    A)循环队列是一种逻辑结构

    B)循环队列是队列的一种链式存储结构

    C)循环队列是非线性结构

    D)循环队列是队列的一种顺序存储结构

    30.

    考前密押试题 下列关于线性链表的叙述中,正确的是

    A)进行插入与删除时,不需要移动表中的元素

    B)各数据结点的存储顺序与逻辑顺序可以不一致,但它们的存储空间必须连续

    C)各数据结点的存储空间可以不连续,但它们的存储顺序与逻辑顺序必须一致

    31.

    考前密押试题 一棵二叉树共有25个结点,其中5个是叶子结点,则度为1的结点数为

    答案:D

    A)4

    B)6

    C)10

    D)16

    32.

    考前密押试题 设循环队列存储空间为Q(1:50)。初始状态为front=rear=50。经过一系列入队和退队操作后,front=14rear=19,则该循环队列中的元素个数为

    A)5

    B)45

    C)46

    D)6

    33.

    考前密押试题 下列链表中,其逻辑结构属于非线性结构的是

    答案:D

    A)双向链表

    B)循环链表

    C)带链的栈

    D)二叉链表

    34.

    考前密押试题 设循环队列的存储空间为Q(1: 35),初始状态为front=rear=35。现经过一系列入队与退队运算后,front=15rear=15,则循环队列中的元素个数为

    A)15

    B)0或35

    C)16

    D)20

    35.

    考前密押试题 下列关于栈的叙述中,正确的是

    答案:B

    A)栈底元素一定是最后入栈的元素

    B)栈操作遵循先进后出的原则

    C)栈顶元素一定是最先入栈的元素

    36.

    考前密押试题 设二叉树共有150个结点,其中度为1的结点有10个,则该二叉树中的叶子结点数为

    A)不可能有这样的二叉树

    B)70

    C)69

    D)71

    37.

    考前密押试题 下列叙述中正确的是

    答案:B

    A)程序执行的效率只取决于所处理的数据量

    B)程序执行的效率与数据的存储结构密切相关

    C)程序执行的效率只取决于程序的控制结构

    38.

    考前密押试题 下列与队列结构有关联的是

    A)函数的递归调用

    B)多重循环的执行

    C)先到先服务的作业调度

    D)数组元素的引用

    39.

    4ff01ee0df46de72ef41473664820590.png

    考前密押试题 对如下图所示的二叉树

    进行前序遍历的结果为

    答案:C

    A)ABCDEFXYZ

    B)YDEBFZXCA

    C)ABDYECFXZ

    D)DYBEAFCZX

    40.

    考前密押试题 一个栈的初始状态为空。现将元素1,2,3,A,B,C依次入栈,然后再依次出栈,则元素出栈的顺序是

    A)1,2,3,C,B,A

    B)C,B,A,3,2,1

    C)1,2,3,A,B,C

    D)C,B,A,1,2,3

     计算机二级题库

    展开全文
  • 排序算法之冒泡排序

    2017-05-05 23:28:50
    这一片篇我来分享一下冒泡排序的编写。 冒泡排序:通过对待排序序列从后向前或从前向后,...在最坏情况下,对长度为n的线性表排序,冒泡排序需要比较的次数为n(n-1)/2。 #include #define N 10void bubble_sort(int a
    这一片篇我来分享一下冒泡排序的编写。
    冒泡排序:通过对待排序序列从后向前或从前向后,依次比较相邻元素的排序码,若发现逆序则交换,使较大的元素逐渐从前部移向后部或较小的元素逐渐从后部移向前部,直到所有元素有序为止。
    在最坏情况下,对长度为n的线性表排序,冒泡排序需要比较的次数为n(n-1)/2。
    
    #include<stdio.h>
    #define N 10
    
    void bubble_sort(int a[],int n)
    {
        int i,t,j;
        for(i=0;i<N-1;i++)//N-1轮比较
            for(j=0;j<=n-i-1;j++)//N-i-1轮比较
                {
                    if(a[j]>a[j+1])//交换顺序
                    {
                        t=a[j];
                        a[j]=a[j+1];
                        a[j+1]=t;
                    }
                }
    }
    
    int main()
    {
        int i;
        int a[N]={0};
        printf("请输入10个数据:\n");
        for(i=0;i<N;i++)
            scanf("%d",&a[i]);
        printf("这10个数据的顺序是:\n");
        for(i=0;i<N;i++)
            printf("%5d",a[i]);
        bubble_sort(a,N);
        printf("\n");
        printf("排序后的数据的顺序是:\n");
        for(i=0;i<N;i++)
            printf("%5d",a[i]);
        return 0;
    }
    
    展开全文
  • 国二office11套

    2015-05-16 10:38:31
    2 对长度为n的线性表排序 在最坏情况下 比较次数不是n n-1 2的排序方法是( ) 答案:D A)快速排序 B)冒泡排序 C)直接插入排序 D)堆排序">一 选择题 1 算法的有穷性是指( ) A)算法程序的运行时间是...
  • 线性表(List)定义:零个或多个数据元素有限序列 ...2.排序对线性表安装一定规则排序,其中排序算法有很多,算法时间复杂度也有差异 3.根据位序(第几位)得到对应数据元素 4.在线性表

    线性表(List)的定义:零个或多个数据元素的有限序列

    注意:1.序列:元素之间是有顺序的

                2.元素的个数是有限的

                3.当n=0,称这个线性表为空表


    线性表的基本操作:

    1.获得线性表的长度

    2.排序:对线性表安装一定规则排序,其中排序算法有很多,算法的时间复杂度也有差异

    3.根据位序(第几位)得到对应的数据元素

    4.在线性表里面查找某个元素是否存在

    5.线性表的插入

    6.线性表的删除


    线性表的两种物理存储结构:

    1.顺序存储结构

    2.链式存储结构

    展开全文
  • 1.考前密押试题对长度为n的线性表排序,在最坏情况下,比较次数不是n(n-1)/2的排序方法是答案:AA)堆排序B)冒泡排序C)快速排序D)直接插入排序2.考前密押试题下列关于栈的叙述正确的是A)栈按"先进后出"组织数据B)栈...
  • 对长度为n的线性表排序,在最坏情况下,冒泡排序和快速排序需要比较的次数为n(n-1)/2,堆排序需要比较的次数O(nlog2n),希尔排序所需要的比较次数为O(n1.5). 软件调试的任务是诊断和改正程序中的错误。 数据...
  • 对长度为n的线性表排序,最坏情况下,比较次数不是n(n-1)/2的排序方法是堆排序。 直接插入排序、快速排序、冒泡排序都是。 堆排序最坏情况下比较次数为n*log2n。 栈,先进后出、后进先出。 只能在栈顶这一端插入...
  • 1、对长度为n的线性表排序,在最坏的情况下: 比较次数为nlog2n的排序方法:堆排序(比较次数最少); 比较次数是n(n-1)/2的排序方法是:快速排序、直接插入排序、冒泡排序。 希尔排序:nr(1<r<2)。 2、栈:...
  • 数据结构_线性表操作

    2009-05-02 23:00:16
    cout请选择======================\n"; cout* 1.初始化线性表 *\n"; cout* 2....对线性表进行从小到大排序 *\n"; cout* 0. 退出 *\n"; cout<<"=====================End=========================\n";
  • 二级C语言复习(1)

    2016-09-14 16:41:38
    1数据流程图中标有名字的箭头表示数据流,程序流程图中标有名字的箭头表示控制流。 2结构化程序设计思想:(1)自顶...5对长度为n的线性表排序,在最坏情况下,快速排序、冒泡排序、直接插入排序的比较次数为n(n-1)/
  • C语言二级笔记

    2020-08-08 16:23:56
    快速排序最坏情况下蜕化为冒泡排序,在最坏情况下,对长度为n的线性表排序,冒泡排序需要比较的次数为n(n-1)/2。 关于前序中序后序 E-R图不能描述算法 如果a是实型变量,a=10是可以的,但是不能说实型变量中可以...
  • 计算机二级MS-office题目练习

    千次阅读 2020-09-10 15:50:09
    2.对长度为 n 的线性表排序,在最坏情况下,比较次数不是 n(n-1)/2 的排序方法是()。答案:D A)快 速 排 序 B)冒泡排序 C)直接插入排序 D)堆排序 3.下列关于栈的叙述正确的是()。答案:B A)栈按"先进先出...
  • n为用户输入十进制数开始,一直到n等于0为止 { Push(S, N % 8); //n除以8余数(8进制低位)入栈 //先压入余数是八进制低位,后压入余数是八进制高位 N = N / 8; //令n等于n整除以8商,进入...
  • 二级C语言易错锦集

    2019-09-26 17:09:30
    二级C语言易错锦集 1、 C语言中的非执行语句不会被编译,不会生成二进制的机器指令 C程序经过编译、连接步骤之后才能形成一个真正可执行的二进制机器...3、 对长度为n的线性表排序,在最坏的情况下,堆排序算法的...
  • 入队尾进,退队头进,m便是空 前序遍历:根节点→左节点→右节点 要在具有 n 个元素的有序顺序表中插入一个元素,插入后仍是有序...​ 【对长度为n的线性表排序,最坏情况下,它们的比较次数为n(n-1)/2】 ..
  • 针对无序数组中查询最长连续元素问题,一般情况下先数组进行排序处理,然后进行最长连续元素查询,以上算法时间复杂度可以控制在O(nlogn),此处要求时间复杂度O(n),所以需要采用其他算法; 针对无序数组...
  • 计数排序 计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H....它的优势在于在一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中...2、设输入的线性表长度为n,|S|=k(表示集合S中元素的总数目...
  •  基本原理:对长度为 n 的线性表应用直接选择排序,将对线性表进行 n-1次扫描。第一次扫描在原始线性表上进行,从该线性表的第一个位置开始,找出线性表中的最小元素,并将它交换到第一个位置上去。第二次扫描在第...
  • 2.设输入的线性表长度为n,|S|=k(k表示几何S中元素的总数目为k),k=O(n) 算法步骤: 扫描整个集合S,每一个Si∈S,找到在线性表中小于等于Si的元素个数T(Si) 搜索整个线性表L,L中的每一个元素Li, 将Li放在...
  • 计数排序

    2016-04-17 19:09:00
    计数排序 [计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。它的优势在于在一定范围内的整数排序时,它的复杂度为...2、设输入的线性表长度为n,|S|=k(表示集合S中元素的总数...
  • 排序算法-计数排序

    2013-03-17 16:46:37
     2、设输入的线性表长度为n,|S|=k(表示集合S中元素的总数目为k),则k=O(n)。  在这两个条件下,计数排序的复杂性为O(n+k)。    计数排序算法的基本思想是对于给定的输入序列中的每一个元素x,确定该...
  • 1.掌握顺序查找、折半查找及二叉排序树上查找基本思想和算法实现,了解怎样各种查找方法进行时间性能(平均查找长度)分析。 2.掌握各种排序方法基本思想、排序过程、算法实现,能进行时间和空间性能分析...
  • 计数排序Counting sort

    2016-01-21 12:54:03
    计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。它的优势在于在一定范围内的整数排序时,它的...2、设输入的线性表长度为n,|S|=k(表示集合S中元素的总数目为k),则k=O(n)。

空空如也

空空如也

1 2 3 4 5
收藏数 85
精华内容 34
关键字:

对长度为n的线性表排序