免费智能真题库 > 历年试卷 > 软件设计师 > 2010年下半年 软件设计师 下午试卷 案例
  第4题      
  知识点：   存储结构   堆   队列   二叉树   数据结构   维护

 
堆数据结构定义如下：
对于n个元素的关键字序列a1，a2，…，an}，当且仅当满足下列关系时称其为堆。

在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素为最小元素，则 称为小顶堆。堆常用完全二叉树表示，图4-1是一个大顶堆的例子。

堆数据结构常用于优先队列中，以维护由一组元素构成的集合。对应于两类堆结构， 优先队列也有最大优先队列和最小优先队列，其中最大优先队列采用大顶堆，最小优先队列采用小顶堆。以下考虑最大优先队列。
假设现已建好大顶堆A，且已经实现了调整堆的函数heapify(A，n，index)。
下面将C代码中需要完善的三个函数说明如下：
(1)heapMaximum(A)：返回大顶堆A中的最大元素。
(2)heapExtractMax(A)：去掉并返回大顶堆A的最大元素，将最后一个元素“提前” 到堆顶位置，并将剩余元素调整成大顶堆。
(3)maxHeapInsert(A, key)：把元素key插入到大顶堆A的最后位置，再将A调整成大顶堆。
优先队列采用顺序存储方式，其存储结构定义如下:
 
问题：4.1   根据以上说明和C代码，填充C代码中的空（1)〜（5)。
 
问题：4.2   根据以上 C 代码，函数heapMaximum、heapExtractMax 和maxHeapInsert 的时间复杂度的紧致上界分别为 （6) 、 (7) 和（8)(用O符号表示)。
 
问题：4.3   若将元素10 插入到堆 A =<15, 13, 9, 5, 12, 8, 7,4, 0, 6,2, 1>中，调用 maxHeapInsert 函数进行操作，则新插入的元素在堆A中第 （9) 个位置(从1开始）。
 
 
 

   知识点讲解    
   · 存储结构    · 堆    · 队列    · 二叉树    · 数据结构    · 维护
 
       存储结构
               邻接矩阵表示法
               对于具有n个顶点的图G(V,E)来说，其邻接矩阵是一个n阶方阵，且满足
               
               由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，有向图的邻接矩阵就不一定对称了。借助邻接矩阵易判定任意两个顶点之间是否有边（或弧）相连，并且容易求得各个顶点的度。
               网（赋权图）的邻接矩阵可定义为
               
               邻接链表表示法
               邻接链表指的是为图的每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点vi的边（对于有向图是以vi为尾的弧）。邻接链表中的节点有表节点和表头节点两种类型。
               邻接矩阵和邻接链表表示法对有向图和无向图都适用。
 
       堆
        1）定义
        n个元素的序列{k1, k2, …, kn｝当且仅当满足以下的关系式时才称之为堆：或，并相应地称为小顶堆或大顶堆。
        2）判断办法
        判断堆的办法是把序列看成一棵完全二叉树，若树中所有非终端节点的值均不大于（或不小于）其左右孩子的节点的值，则该序列为堆。
        3）典型应用
        堆的典型应用是堆排序。堆排序首先要根据待排序记录的关键字建立初始堆，其方法是：将待排序的关键字按层序遍历方式分放到一棵完全二叉树的各个节点中，显然所有i>［n/2］的节点ki都没有子节点，以这样的ki为根的子树已经是堆，因此初始堆可从完全二叉树的第（i=［n/2］）个节点开始，通过调整，逐步使以k[n/2]， k［n/2]-1, …, k2, k1为根的子树满足堆的定义。
        注意：堆与一棵完全二叉树对应，但堆本身是线性表。
 
       队列
        1）队列的定义及基本运算
        队列是一种先进先出（FIFO）的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中，允许插入元素的一端称为队尾（Rear），允许删除元素的一端称为队头（Front）。
        对队列进行的基本操作如下。
        （1）置队空InitQueue(Q)：创建一个空的队列Q。
        （2）判队空Empty(Q)：判断队列是否为空。
        （3）入队EnQueue(Q,x)：将元素x加入到队列Q的队尾，并更新队尾指针。
        （4）出队DeQueue(Q)：将队头元素从队列Q中删除，并更新队头指针。
        （5）读队头元素Frontque(Q)：返回队头元素的值，但并不更新队头指针。
        2）队列的存储结构
        （1）顺序存储。队列的顺序存储结构是利用一组地址连续的存储单元存放队列中的元素。由于队列中元素的插入和删除限定在队列的两端进行，因此设置队头指针和队尾指针，分别指示当前的队首元素和队尾元素。
        在顺序队列中，为了降低运算的复杂度，元素入队时只需修改队尾指针，元素出队时只需修改队头指针。由于顺序队列的存储空间是提前设定的，所以队尾指针会有一个上限值，当队尾指针达到其上限时，就不能只通过修改队尾指针来实现新元素的入队操作了。此时，可通过整除取余运算将顺序队列假想成一个环状结构，称之为循环队列。在队列空和队列满的情况下，循环队列的队头、队尾指针指向的位置是相同的。为了区别队空和队满的情况，可采用两种处理方式：其一是设置一个标志位，以区别头、尾指针的值相同时队列是空还是满；其二是牺牲一个元素空间，约定以"队列的尾指针所指位置的下一个位置是头指针时"表示队列满，头、尾指针的值相同时表示队列空。
        （2）链式存储。用链表表示的队列简称为链队列。为了便于操作，给链队列添加一个头节点，并令头指针指向头节点。队列为空的判定条件是：头指针和尾指针的值相同，且均指向头节点。
        3）队列的应用
        队列结构常用于处理需要排队的场合，如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。
 
       二叉树
               二叉树的定义
               二叉树（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为叶子节点到根的路径长度。
               霍夫曼树是指权值为w1，w2，…，wn的n个叶子节点的二叉树中带权路径长度最小的二叉树。
               构造最优二叉树的霍夫曼算法如下。
               （1）根据给定的n个权值w1，w2，…，Wn构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根节点，其左右子树均空。
               （2）在F中选取两棵根节点的权值最小的树作为左右子树，构造一棵新的二叉树，置新构造二叉树的根节点的权值为其左、右子树根节点的权值之和。
               （3）从F中删除这两棵树，同时将新得到的二叉树加入到F中。
               重复（2）、（3），直到F中只含一棵树时为止。这棵树便是霍夫曼树。
               树和森林
               1）树的存储结构
               .树的双亲表示法：用一组地址连续的单元存储树的节点，并在每个节点中附设一个指示器，指示其双亲节点在该存储结构中的位置。显然这种表示对于求指定节点的双亲或祖先都十分方便，但对于求指定节点的孩子及后代则需要遍历整个数组。
               .树的孩子表示法：在存储结构中用指针指示出节点的每个孩子，由于树中每个节点的子树数目不尽相同，因此在采用链式存储结构时可以考虑多重链表。
               .树的孩子兄弟表示法：又称二叉链表表示法。在链表的节点中设置两个指针域分别指向该节点的第一个孩子和下一个兄弟。利用这种存储结构便于实现树的各种操作。
               2）树和森林的遍历
               （1）树的遍历。树的遍历分为先根遍历和后根遍历两种。
               .先根遍历：先访问树的根节点，然后依次先根遍历根的各棵子树。对树的先根遍历等同于对转换所得的二叉树进行先序遍历。
               .后根遍历：先依次后根遍历树根的各棵子树，然后访问树根节点。树的后根遍历等同于对转换所得的二叉树进行中序遍历。
               （2）森林的遍历。森林的遍历分为前序遍历和后序遍历两种。
               .前序遍历森林：若森林非空，访问森林中第一棵树的根节点，前序遍历第一棵子树根节点的子树森林，再前序遍历除第一棵树之外剩余的树所构成的森林。
               .后序遍历森林：若森林非空，后序遍历森林中第一棵树的子树森林，访问第一棵树的根节点，后序遍历除第一棵树之外剩余的树所构成的森林。
               3）树、森林与二叉树的转换
               （1）树、森林转换为二叉树。利用树的孩子兄弟表示法可导出树与二叉树的对应关系，在树的孩子兄弟表示法中，从物理结构上看与二叉树的二叉链表表示法相同，因此就可以用这种同一存储结构的不同解释将一棵树转换为一棵二叉树。
               将一个森林转换为一棵二叉树的方法是：先将森林中的每一棵树转换为二叉树，再将第一棵树的根作为转换后的二叉树的根，第一棵树的左子树作为转换后二叉树根的左子树，第二棵树作为转换后二叉树根的右子树，第三棵树作为转换后二叉树根的右子树的右子树，以此类推，森林就可以转换为一棵二叉树。
               （2）二叉树转换为树和森林。若二叉树非空，则二叉树根及其左子树为第一棵树的二叉树形式，二叉树根的右子树又可以看作一个由森林转换后的二叉树，应用同样的方法，直到最后产生一棵没有右子树的二叉树为止，这样就得到了一个森林。为了进一步得到树，可用树的二叉链表表示的逆方法，即节点的右子树的根、右子树的右子树的根……找出原本是同一个双亲的兄弟。二叉树转换为树或森林是唯一的。
 
       数据结构
        根据数据元素之间关系的不同特性，通常有下列4类基本的逻辑结构，即集合结构、线性结构、树形结构、图形结构。
        1）线性结构
        线性表是最常用且最简单的一种数据结构。线性表中除第一个元素外，每个元素均只有一个直接前驱；除最后一个元素外，每个元素都只有一个直接后继。
        栈是限定仅在表尾进行插入或删除操作的线性表，是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。
        队列是一种先进先出（FIFO）的线性表，它只允许在表的一端进行插入，而在另一端删除元素。
        2）树
        树是n（n≥0）个互不相交的有限集，当n=0时称为空树。在一棵非空树中，有且仅有一个节点称为根节点；当n>1时，其余的节点可分为若干个不相交的集合，其中每一个集合本身又是一棵树，这些集合称为根节点的子树。
        3）图
        图是由两个集合V和E组成的二元组，记为G=（V, E），其中V是顶点的非空有限集合，E是图中边的有限集合。
 
       维护
        维护阶段是软件生存期中时间最长的阶段。软件一旦交付正式投入运行后便进入软件维护阶段。该阶段的关键任务是通过各种必要的维护活动使系统持久地满足用户的需要。每一项维护活动都应该准确地记录下来，作为正式的文档资料加以保存。
   题号导航      2010年下半年 软件设计师 下午试卷 案例   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
 
第4题    在手机中做本题