免费智能真题库 > 历年试卷 > 软件评测师 > 2018年下半年 软件评测师 上午试卷 综合知识
  第43题      
  知识点:      堆排序   二叉树   排序   排序算法   数据结构
  关键词:   堆排序   二叉树   时间复杂度   数据结构   算法   排序   数据        章/节:   程序设计语言知识       

 
是一种数据结构,分为大顶和小顶两种类型。大(小)顶要求父元素大于等于(小于等于)其左右孩子元素。则(43)是一个小顶结构。结构用二叉树表示,则适宜的二叉树类型为(44)。对于10个结点的小顶,其对应的二叉树的高度(层数)为(45)。排序是一种基于结构的排序算法,该算法的时间复杂度为(46)。
 
 
  A.  10,20,50,25,30,55,60,28,32,38
 
  B.  10,20,50,25,38,55,60,28,32,30
 
  C.  60,55,50,38,32,30,28,25,20,10
 
  D.  10,20,60,25,30,55,50,28,32,38
 
 
 

 
  第17题    2017年下半年  
   37%
表示"以字符a开头且仅由字符a、b构成的所有字符串"的正规式为( )。
  第41题    2016年下半年  
   48%
某个应用中,需要对输入数据进行排序,输入数据序列基本有序(如输入为1,2,5,3,4,6,8,7)。在这种情况下,采用(40)排序算法最好,..
  第17题    2016年下半年  
   41%
设元素a、b、c、d依次进入一个初始为空的栈,则不可能通过合法的栈操作序列得到(17)。
   知识点讲解    
   ·     · 堆排序    · 二叉树    · 排序    · 排序算法    · 数据结构
 
       堆
        1)定义
        n个元素的序列{k1, k2, …, kn}当且仅当满足以下的关系式时才称之为堆:,并相应地称为小顶堆或大顶堆。
        2)判断办法
        判断堆的办法是把序列看成一棵完全二叉树,若树中所有非终端节点的值均不大于(或不小于)其左右孩子的节点的值,则该序列为堆。
        3)典型应用
        堆的典型应用是堆排序。堆排序首先要根据待排序记录的关键字建立初始堆,其方法是:将待排序的关键字按层序遍历方式分放到一棵完全二叉树的各个节点中,显然所有i>[n/2]的节点ki都没有子节点,以这样的ki为根的子树已经是堆,因此初始堆可从完全二叉树的第(i=[n/2])个节点开始,通过调整,逐步使以k[n/2], k[n/2]-1, …, k2, k1为根的子树满足堆的定义。
        注意:堆与一棵完全二叉树对应,但堆本身是线性表。
 
       堆排序
        对于n个元素的关键字序列{k1k2,…,kn},当且仅当满足下列关系时称其为堆。
        
        若将此序列对应的一维数组(即以一维数组作为序列的存储结构)看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值。因此,在一个堆中,堆顶元素(即完全二叉树的根结点)必为序列中的最小元素(或最大元素),并且堆中任一棵子树也都是堆。若堆顶为最小元素,则称为小顶堆;若堆顶为最大元素,则称为大顶堆。
        例如,将序列(48,37,64,96,75,12,26,54,03,33)中的元素依次放入一棵完全二叉树中,如下图(a)所示。显然,它既不是大顶堆(48<64),也不是小顶堆(48>37),调整为大顶堆后如下图(b)所示。
        
        用完全二叉树表示堆
        堆排序的基本思想是:对一组待排序记录的关键字,首先把它们按堆的定义排成一个序列(即建立初始堆),从而输出堆顶的最小关键字(对于小顶堆而言)。然后将剩余的关键字再调整成新堆,便得到次小的关键字,如此反复,直到全部关键字排成有序序列为止。
        n个元素进行堆排序时,时间复杂度为Onlog2n),空间复杂度为O(1)。堆排序是不稳定的排序方法。
 
       二叉树
               二叉树的定义
               二叉树(Binary Tree)是n(n≥0)个节点的有限集合,它或者是空树(n=0),或者是由一个根节点及两棵互不相交的、分别称为左子树和右子树的二叉树所组成。
               二叉树与树的区别如下。
               .二叉树的节点的子树要区分左子树和右子树,即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
               .二叉树的节点的最大度为2,而树中不限制节点的度数。
               二叉树的运算
               二叉树的基本运算是遍历,其他运算可建立在遍历运算的基础上。
               二叉树的性质
               二叉树具有以下性质。
               (1)二叉树第i层上的节点数目最多为2i-1(i≥1)个。
               (2)深度为k的二叉树至多有2k-1(k≥1)个节点。
               (3)在任意一棵二叉树中,若终端节点数为n0,度为2的节点数为n2,则n0=n2+1。
               (4)具有n个节点的完全二叉树的深度为[log2n]+1。
               (5)对一棵有n个节点的完全二叉树的节点按层次自左至右进行编号,则对任意节点i有以下性质。
               .若i=1,则节点i是二叉树的根,无双亲;若i>1,则其双亲为
               .若2i>n,则节点i无左孩子;否则其左孩子为2i
               .若2i+1>n,则节点i无右孩子;否则其右孩子为2i+1。
               若深度为k的二叉树有2k-1个节点,则称其为满二叉树。
               深度为k、有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树编号从1至n的节点一一对应时,称之为完全二叉树。
               二叉树的存储结构
               1)顺序存储结构
               用一组地址连续的存储单元存储二叉树中的数据元素,必须把节点排成一个适当的线性序列,并且节点在这个序列中的相互位置能反映出节点之间的逻辑关系。
               顺序存储结构用于完全二叉树时既简单又节省空间,而对于一般二叉树则不适用。因为在顺序存储结构中,以节点在存储单元中的位置来表示节点之间的关系,那么对于一般的二叉树来说,也必须按照完全二叉树的形式存储,也就是要添上一些实际并不存在的"虚节点",这将造成空间的浪费。
               2)链式存储结构
               由于二叉树中的节点包含有数据元素、左子树根、右子树根及双亲等信息,因此可以用三叉链表或二叉链表来存储二叉树,链表的头指针指向二叉树的根节点。
               二叉树的遍历
               遍历是指按某种策略访问树中的每个节点,且仅访问一次。由于二叉树所具有的递归性质,一棵非空的二叉树可以看作由根节点、左子树和右子树三部分构成,因此若能依次遍历这三部分中的每个节点信息,也就遍历了整棵二叉树。按照遍历左子树要在遍历右子树之前进行的约定,根据访问根节点位置的不同,可得到二叉树的前序、中序和后序3种遍历方法。
               遍历二叉树的基本操作就是访问节点,不论按照哪种次序遍历,对含有n个节点的二叉树,遍历算法的时间复杂度都为O(n)。在最坏情况下,二叉树是有n个节点且深度为n的单枝树,遍历算法的空间复杂度也为O(n)。
               遍历二叉树的过程实质上是按一定规则,将树中的节点排成一个线性序列的过程,因此遍历操作得到的是树中节点的一个线性序列。在每一种序列中,有且仅有一个起始点和一个终节点,其余节点有且仅有唯一的直接前驱和直接后继。
               对二叉树还可以进行层序遍历。层序遍历就是从树的根节点出发,首先访问第1层的树根节点,然后从左到右依次访问第2层上的节点,以此类推,自上而下、自左到右逐层访问树中各层上节点的过程。
               线索二叉树
               若n个节点的二叉树采用链表作存储结构,则链表中含有n+1个空指针域,利用这些空指针域来存放指向节点的前驱和后继信息。线索链表的节点结构如下图所示。
               
               线索链表的节点结构
               若二叉树的二叉链表采用上图所示的节点结构,则相应的链表称为线索链表,其中指向节点前驱、后继的指针称为线索,加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。
               二叉树的应用:最优二叉树
               霍夫曼树又称最优二叉树,是一类带权路径长度最短的树。
               路径:是指从树中一个节点到另一个节点之间的通路,路径上的分支数目称为路径长度。
               树的路径长度:是从树根到每一个叶子的路径长度之和。节点的带权路径长度为从该节点到树根之间的路径长度与该节点权的乘积。
               树的带权路径长度:指树中所有叶子节点的带权路径长度之和,记为
               
               式中,n为带权叶子节点的数目;wi为叶子节点的权值;li为叶子节点到根的路径长度。
               霍夫曼树是指权值为w1w2,…,wnn个叶子节点的二叉树中带权路径长度最小的二叉树。
               构造最优二叉树的霍夫曼算法如下。
               (1)根据给定的n个权值w1w2,…,Wn构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根节点,其左右子树均空。
               (2)在F中选取两棵根节点的权值最小的树作为左右子树,构造一棵新的二叉树,置新构造二叉树的根节点的权值为其左、右子树根节点的权值之和。
               (3)从F中删除这两棵树,同时将新得到的二叉树加入到F中。
               重复(2)、(3),直到F中只含一棵树时为止。这棵树便是霍夫曼树。
               树和森林
               1)树的存储结构
               .树的双亲表示法:用一组地址连续的单元存储树的节点,并在每个节点中附设一个指示器,指示其双亲节点在该存储结构中的位置。显然这种表示对于求指定节点的双亲或祖先都十分方便,但对于求指定节点的孩子及后代则需要遍历整个数组。
               .树的孩子表示法:在存储结构中用指针指示出节点的每个孩子,由于树中每个节点的子树数目不尽相同,因此在采用链式存储结构时可以考虑多重链表。
               .树的孩子兄弟表示法:又称二叉链表表示法。在链表的节点中设置两个指针域分别指向该节点的第一个孩子和下一个兄弟。利用这种存储结构便于实现树的各种操作。
               2)树和森林的遍历
               (1)树的遍历。树的遍历分为先根遍历和后根遍历两种。
               .先根遍历:先访问树的根节点,然后依次先根遍历根的各棵子树。对树的先根遍历等同于对转换所得的二叉树进行先序遍历。
               .后根遍历:先依次后根遍历树根的各棵子树,然后访问树根节点。树的后根遍历等同于对转换所得的二叉树进行中序遍历。
               (2)森林的遍历。森林的遍历分为前序遍历和后序遍历两种。
               .前序遍历森林:若森林非空,访问森林中第一棵树的根节点,前序遍历第一棵子树根节点的子树森林,再前序遍历除第一棵树之外剩余的树所构成的森林。
               .后序遍历森林:若森林非空,后序遍历森林中第一棵树的子树森林,访问第一棵树的根节点,后序遍历除第一棵树之外剩余的树所构成的森林。
               3)树、森林与二叉树的转换
               (1)树、森林转换为二叉树。利用树的孩子兄弟表示法可导出树与二叉树的对应关系,在树的孩子兄弟表示法中,从物理结构上看与二叉树的二叉链表表示法相同,因此就可以用这种同一存储结构的不同解释将一棵树转换为一棵二叉树。
               将一个森林转换为一棵二叉树的方法是:先将森林中的每一棵树转换为二叉树,再将第一棵树的根作为转换后的二叉树的根,第一棵树的左子树作为转换后二叉树根的左子树,第二棵树作为转换后二叉树根的右子树,第三棵树作为转换后二叉树根的右子树的右子树,以此类推,森林就可以转换为一棵二叉树。
               (2)二叉树转换为树和森林。若二叉树非空,则二叉树根及其左子树为第一棵树的二叉树形式,二叉树根的右子树又可以看作一个由森林转换后的二叉树,应用同样的方法,直到最后产生一棵没有右子树的二叉树为止,这样就得到了一个森林。为了进一步得到树,可用树的二叉链表表示的逆方法,即节点的右子树的根、右子树的右子树的根……找出原本是同一个双亲的兄弟。二叉树转换为树或森林是唯一的。
 
       排序
        假设含n个记录的文件内容为{R1R2,…,Rn},其相应的关键字为{k1k2,…,kn}。经过排序确定一种排列{Rj1Rj2,…,Rjn},使得它们的关键字满足如下递增(或递减)关系:kj1≤kj2≤…≤kjn(或kj1kj2≥…≥kjn)。
 
       排序算法
               简单排序
               简单排序包括直接插入排序、冒泡排序、简单选择排序等方法。
               1)直接插入排序
               直接插入排序的基本操作是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。
               2)冒泡排序
               首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序(即 r[1].key>r[2].key),则交换两个记录,接着比较第二个记录和第三个记录的关键字。依次类推,直至第n-1个记录和第n个记录的关键字进行过比较为止。这个过程称为第一趟冒泡排序,使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟冒泡排序,对前n-1个记录进行同样的操作,结果是使关键字次大的记录被安置到第n-1个记录的位置上。当进行完第n-1趟冒泡排序时,所有记录都已有序排列。
               3)简单选择排序
               简单选择排序的基本思想是:在进行每趟排序时,从无序的记录中选择出关键字最小(或最大)的记录,将其插入到有序序列(初始时为空)的尾部。
               希尔排序
               希尔排序又称"缩小增量排序",是对直接插入排序方法的改进。希尔排序的基本思想是:先将整个待排记录序列分割成若干序列,然后分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。
               快速排序
               快速排序是对冒泡排序的一种改进。先通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后分别对这两部分记录继续进行排序,使得整个序列有序。
               堆排序
               1)堆的概念
               对于n个元素的关键字序列{k1,k2,…,kn},当且仅当所有关键字都满足下列关系时称其为堆:
               
               从序列元素间的关系来看,堆是一棵完全二叉树的层次序列。显然,堆顶元素为序列中n个元素的最小值(或最大值)。若堆顶为最小元素,则称为小根堆;若堆顶为最大元素,则称为大根堆。
               2)堆排序的基本思想(小根堆)
               对一组待排序记录的关键字,首先把它们按堆的定义排成一个堆序列,从而输出堆顶的最小关键字,然后将剩余的关键字再调整成新堆,便得到次小的关键字,如此反复进行,直到全部关键字排成有序序列。
               归并排序
               归并排序是不断将多个小而有序的序列合成一个大而有序的序列的过程。其中最常用的归并排序是二路归并排序,它是将整个序列中的元素进行分组,相邻的两个元素为一组,然后分别为每个小组进行排序,随后将两个相邻的小组合成一个组,继续进行组内排序;直到所有元素被合并成一个组内,并使组内元素有序,此时排序结束。
               基数排序
               基数排序的思想是按组成关键字的各个数位的值进行排序,它是分配排序的一种。基数排序把一个关键字Ki看成一个d元组,即
               
               其中称为最高有效位,@称为最低有效位。基数排序可以从最高有效位开始,也可以从最低有效位开始。
               基数排序的基本思想是:设立r个队列(r为基数),队列的编号为0, 1, 2, …,r-1。首先按最低有效位的值,把n个关键字分配到这r个队列中;然后从小到大将各队列中的关键字再依次收集起来;接着再按次低有效位的值把刚收集起来的关键字再分配到r个队列中。重复上述收集过程,直至最高位有效。这样得到了一个从小到大有序的关键字序列。
 
       数据结构
        根据数据元素之间关系的不同特性,通常有下列4类基本的逻辑结构,即集合结构、线性结构、树形结构、图形结构。
        1)线性结构
        线性表是最常用且最简单的一种数据结构。线性表中除第一个元素外,每个元素均只有一个直接前驱;除最后一个元素外,每个元素都只有一个直接后继。
        栈是限定仅在表尾进行插入或删除操作的线性表,是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。
        队列是一种先进先出(FIFO)的线性表,它只允许在表的一端进行插入,而在另一端删除元素。
        2)树
        树是nn≥0)个互不相交的有限集,当n=0时称为空树。在一棵非空树中,有且仅有一个节点称为根节点;当n>1时,其余的节点可分为若干个不相交的集合,其中每一个集合本身又是一棵树,这些集合称为根节点的子树。
        3)图
        图是由两个集合VE组成的二元组,记为G=(V, E),其中V是顶点的非空有限集合,E是图中边的有限集合。
   题号导航      2018年下半年 软件评测师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第43题    在手机中做本题