SDUST 2020/数据结构/期末集合.part3

07 树

1、树的类型定义

①基本概念：

结点：数据元素+若干指向子树的分支

结点的度：分支的个数(子树的个数)

树的度：树中所有结点的度的最大值

叶子结点：度为0的结点

分支结点：度大于0的结点(包含根和中间结点)

深度：对任意结点n_i，n_i的深度等于根到该点的唯一路径的长

高度：对任意结点n_i，其高度等于该点到一片树叶的最长的路径

宽度：

结点的层次：假设根节点在第一层，那么其孩子结点在第二层，以此类推

②树的基本分类

有向树：有确定的根、树根与子树之间是有向关系

有序树：子树之间存在确定的次序关系

无序树：子树之间不存在确定的次序关系

树和森林：

③基本操作

2、二叉树

①定义

二叉树:或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成(树的度最大为2)。

二叉树的五种基本形态：空树、只含根节点、左子树为空树、右子树为空树、左右都不为空树

②重要特性

对于结点为n的二叉树，它的分支树b=n-1；

任意的二叉树中叶子节点都比度为2的节点多1

在二叉树的第二层至多有 2^i-1个结点；

深度为k的二叉树上至多含有 2^k-1 个结点；

对任何一个二叉树，若它有n_⁰个叶子结点，n₂个度为2的结点，那么必存在关系式n_⁰=n₂+1；

证明：设二叉树结点总数是n=n0+n₁+n₂

则分支总数为b=n₁+2xn₂

又因为b=n-1。联立得出结论。

具有n个结点的完全二叉树的深度为 ?log₂n?+1

③二叉树的分类

满二叉树：深度为k且有2^k-1个结点，即满树叶的二叉树

完全二叉树：树中所含的n个结点和满二叉树中编号为1到n的结点一一对应

特点：叶子结点出现在最后两层；对于任意结点，若其右分支下的子孙最大层次为L，则左分支下的子孙的最大层次为L或L+1

④二叉树的存储结构

?顺序存储方式

?链式存储结构

二叉链表：这是解题时没有特殊情况最常用的结构

typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
    
}BiTNode,*BiTree;

三叉链表：

typedef struct TriTNode
{
    TElemType data;
    struct TriTNode *lchild,*rchild;
    struct TriTNode *parent;
    
}TriTNode,*TriTree;

双亲链表：

3、二叉树的遍历

单独把遍历拿出来说一下

遍历一共有三种方式：先序、中序、后序，先后都是相对于根节点讲的

如下一棵树，先序遍历是-+a*b-cd/ef，后序遍历是a+b*c-d-e/f，中序遍历是abcd-*+ef/-

                         总结:无论先序、中序、后序遍历二叉树，遍历时的搜索路线是相同的:从根结点出发，逆时针延二叉树外缘移动对每个结点均途径三次。
                         先序遍历:第一次经过结点时访问。
                         中序遍历:第二次经过结点时访问。
                         后序遍历:第三次经过结点时访问。

②算法递归的描述

如下是先中后序的递归算法

void preorderT(BiTree T)
{
    if(T)
    {
        printf("%d",T->data);
        preorderT(T->lchild);
        preorderT(T->rchild);
    }
}

void inorderT(BiTree T)
{
    if(T)
    {
        inorderT(T->lchild);
        printf("%d",T->data);
        inorderT(T->rchild);
    }
}

void postorderT(BiTree T)
{
    if(T)
    {
        postorderT(T->lchild);
        postorderT(T->rchild);
        printf("%d",T->data);
    }
}

特殊地，出现层次遍历：

void LevelorderTraversal( BinTree BT )//逐层遍历
{
    if(!BT)
        return;
    BinTree a[10000],b;
    a[0]=BT;
    int len=1;//len记录当前层的节点数量
    while(1)
    {
        if(len==0)
            return;
        int pos=0;
        BinTree b[10000];

        for(int i=0; i)
        {
            if(a[i]!=NULL)
                printf(" %c",a[i]->Data);
            if(a[i]->Left!=NULL)
                b[pos++]=a[i]->Left;
            if(a[i]->Right!=NULL)
                b[pos++]=a[i]->Right;
        }

        len=pos;//更新下一层宽度，为下一次循环做准备
        for(int i=0; i//将下层的b赋给a，为下一次循环做准备
            a[i]=b[i];
    }
}

④应用举例

在树的整章学习中，递归的思想极大地简化了解题步骤，而涉及遍历的题目，大都与递归有关

?先序输出叶结点/求叶子结点的个数：

void PreorderPrintLeaves( BinTree BT )
{
    if(BT)
    {
        if(BT->Left==NULL&&BT->Right==NULL)
            printf(" %c",BT->Data);
        else
        {
            if(BT->Left)
                PreorderPrintLeaves(BT->Left);
            if(BT->Right)
                PreorderPrintLeaves(BT->Right);
        }
    }
}

int LeafCount(Bitree T)
{
    if(!T)
        return 0;
    else if(!T->lchild&&!T->rchild)
        return 1;
    else
        return LeafCount(T->lchild)+LeafCount(T->rchild);
}

?求二叉树的深度

经典题目。关键是要搞清楚深度的定义，即左右子树深度的最大值+1。算法仍是递归。

int BitreeDepth(Bitree T)
{
    if(!T)
        depth=0;
    else
    {
        depthleft=BitreeDepth(T->lchild);
        depthright=BitreeDepth(T->rchild);
        depth=1+(depthleft>depthright?depthleft:depthright);
    }
    return depth;
}

?建立二叉树的存储结构

以字符串的形式建树

Status Creatbitree (Bitree *T)
{
    scanf("%s",ch);
    if(ch=='')
        T=NULL;
    else
    {
        if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))d
            exit(OVERFLOW);
        T->data=ch;
        Creatbitree(T->lchild);
        Creatbitree(T->rchild);
    }
    return OK;
}

按给定的表达式建树

scanf(&ch);//由前缀表达式建树
if(In(ch,字符集))
    建立叶子结点;
else
{
    建立根节点;
    递归左子树;
    递归右子树;
}

根据后续和中序遍历输出先序遍历

4、线索二叉树

                对线索链表中结点的约定:
               在二叉链表的结点中增加两个标志域，并作如下规定:
             ?若该结点的左子树不空，则lchild域的指针指向其左子树，且左标志域的值为“Link（指针）”;否则，lchild域的指针指向其“前驱”，且左标志的值为“Thread(线索）”
             ?若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为“Link（指针）”;否则，rchild域的指针指向其“后继”，且右标志的值为“Thread（线索）”。
                如此定义的二叉树的存储结构称作“线索链表”。

由于在线索链表中添加了遍历中得到的前驱和后继，线索二叉树简化了遍历算法

以如下二叉树为例

其先序、中序、后序遍历依次是ABCDEFGHK、BDCAHGKFE、DCBHKGFEA

其先序遍历的二叉搜索树是

5、最优二叉树/哈夫曼树

存储表示：

 Typedef struct
               {
                   unsigned int weight;
                   unsigned int parent,lchild,rchild;
               } HTNode, *Huffiman Tree;
               Typedef char **HuffimanCode;

             构造最优树
             思路：STEP1:根据给定的n个权值构造n棵二叉树的集合:其中每棵二叉树中均只含一个带权值为w;的根结点，其左、右子树为空树;
                       STEP2:在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一-棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;
                       STEP3:从F中删去这两棵树，同时加入刚生成的新树;
                       STEP4:重复STEP2和STEP3两步，直至F中只含一棵树为止。

算法：

for (i=n+1; i//建哈夫曼树
{
    select(HT,i-I,sl,s2); //在HT[..i-1]选择parent为0且weight最小的两个结点，其序号分别为s1,s2

    HT[s1].parent=i;
    HT[s2].parent=i;

    HT[i].lchild=s1;
    HT[i].rchild= s2;

    HT[ij.weight=HT[s 1]. weight+ HT[s2]. weight;
}

6、选择：

1、如果一棵非空

如果一棵非空

要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是：只有右子树

先序遍历：根——左——右；中序遍历：左——中——右，两种遍历相同，只能使左子树为空

4、在下述结论中，正确的是：① 只有2个结点的树的度为1；② 二叉树的度为2；③ 二叉树的左右子树可任意交换；④ 在最大堆（大顶堆）中，从根到任意其它结点的路径上的键值一定是按非递增有序排列的。

①④

搜索二叉树的左右子树不能任意互换

5、若一棵二叉树的后序遍历序列是{ 1, 3, 2, 6, 5, 7, 4 }，中序遍历序列是{ 1, 2, 3, 4, 5, 6, 7 }，则下列哪句是错的？A

A.这是一棵完全二叉树 B.2是1和3的父结点 C.这是一棵二叉搜索树 D.7是5的父结点

6、如果一棵非空

于是得到：25-15 = 10.

同理，如果某二叉树的中序序列和后序序列正好相反，则该二叉树一定是：任一结点无左孩子

13、对

A.树中一定没有度为1的结点 B.树中两个权值最小的结点一定是兄弟结点

C.树中任一非叶结点的权值一定不小于下一层任一结点的权值 D.该树一定是一棵完全二叉树 A.正确，哈夫曼树不一定就是完全二叉树且哈夫曼树中没有度为1的结点；B.正确，哈夫曼树的性质； C.正确，哈夫曼树的性质；D.错误，同A 14、下列叙述错误的是（）。B

A.一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和 B.当一棵具有n 个叶子结点的二叉树的WPL 值为最小时，称其树为哈夫曼树，其二叉树的形状是唯一的

C.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近 D.哈夫曼树的结点个数不能是偶数 15、设一段文本中包含字符{a, b, c, d, e}，其出现频率相应为{3, 2, 5, 1, 1}。则经过哈夫曼编码后，文本所占字节数为：25 16、设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是：n在m左方 17、设高为

设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为

21、由若干个二叉树组成的森林F中，叶结点总个数为

M-N 22、设一段文本中包含4个对象{a,b,c,d}，其出现次数相应为{4,2,5,1}，则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？2 23、已知字符集{ a, b, c, d, e, f, g, h }。若各字符的哈夫曼编码依次是 0100, 10, 0000, 0101, 001, 011, 11, 0001，则编码序列 0100011001001011110101 的译码结果是：afeefgd 24、在哈夫曼树中，任何一个结点它的度都是（）。0或2

7、判断

1、存在一棵总共有2016个结点的二叉树，其中有16个结点只有一个孩子。 F

没有确定是什么类型的二叉树

设2度的结点、1度的结点、0度的结点分别是n₂、n₁、n₀个

2n2+16=2015

2、若A和B都是一棵二叉树的叶子结点，则存在这样的二叉树，其前序遍历序列为...A...B...，而中序遍历序列为...B...A... F

3、若一个结点是某二叉树的中序遍历序列的最后一个结点，则它必是该树的前序遍历序列中的最后一个结点。 F

举反例：

4、已知一棵二叉树的先序遍历结果是ABC,　则CAB不可能是中序遍历结果。T

5、对于一个有 F

森林中，有等式：树数=结点数-边数

6、对

08 图

学习/复习数据结构的图之前，最好从离散数学来入手图的知识，图部分的选择和判断用离散数学完全可以解决。

1、基本概念

定义：根据离散数学，图是由顶点集V(G)和边集E(G)组成的，记为G=(V,E)。其中E(G)是边的有限集合，边是顶点的无序对（无向图）或有序对（有向图）。

对有向图来说，E(G)是有向边（也称弧(Arc)）的有限集合，弧是顶点的有序对，记为，v、w是顶点，v为弧尾（箭头根部），w为弧头（箭头处）。

对无向图来说，E(G)是边的有限集合，边是顶点的无序对，记为(v, w)或者(w, v)，并且(v, w)=(w,v)。

顶点(Vertex)：图中的数据元素。另，类比之前的内容，线性表中我们把数据元素叫元素，树中将数据元素叫结点。

顶点v的度：与v相关联的边的数目；

顶点v的出度：以v为起点有向边数；

顶点v的入度：以v为终点有向边数。

邻接点：假若顶点v 和顶点w 之间存在一条边，则称顶点v 和w 互为邻接点。

连通图：图中从一个顶点到达另一顶点，若存在至少一条路径，则称这两个顶点是连通着的。在一个图中，如果任意两个顶点之间都能够连通，则称此图为连通图。

强连通图：强连通图（Strongly Connected Graph）是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。

有向图中的极大强连通子图称做有向图的强连通分量。

2、存储结构

①邻接矩阵存储

无向图的邻接矩阵一定是对称的；

有向图的邻接矩阵可以是对称的，也可以是不对称的。

typedef struct ArcCell//弧的定义
{
    VRType adj;//对于无权图，表示1或0
               //对于有权图，为权值
    
}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct//图的定义
{     
    AdjMatrix arcs;//弧的信息
    VertexType vexs[MAX_VERTEX_NUM];//顶点信息
    int ve,ne;//定点数；弧数
    /*GraphKind kind;*///图的种类标志
}MGraph;
typedef enum{DG,DN,UDG,UDN}GraphKind;

这是源于教材上的官方式定义，而在做程序题目的过程中，题目给定的定义也很好理解和使用：

#define MaxVertexNum 10  /* 最大顶点数设为10 */
#define INFINITY 65535   /* ∞设为双字节无符号整数的最大值65535*/
typedef int Vertex;      /* 用顶点下标表示顶点,为整型 */
typedef int WeightType;  /* 边的权值设为整型 */

typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;  /* 顶点数 */
    int Ne;  /* 边数   */
    WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
};
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
bool Visited[MaxVertexNum]; /* 顶点的访问标记 */

按该存储方式创建图：

MGraph CreateGraph()
{
    int Nv, i, VertexNum;
    int v1, v2;
    Vertex V, W ;
    MGraph Graph;
    scanf("%d", &VertexNum);
    Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    for(V = 0; V < Graph->Nv; V ++)
    {
        for(W = 0; W < Graph->Nv; W ++)
        {
            Graph->G[V][W] = INFINITY;
        }
    }
    scanf("%d", &Graph->Ne);
    if(Graph->Ne)
    {
        for(i = 0; i < Graph->Ne; i ++)
        {
            scanf("%d %d", &v1, &v2);
            Graph->G[v1][v2] = 1;
            Graph->G[v2][v1] = 1;
        }
    }
    return Graph;
}

②邻接表存储

相比邻接矩阵，实现起来很是麻烦

typedef struct ArcNode
{
    int adjxex;//该弧所指向的顶点位置
    struct ArcNode *nextarc;//指向下一条弧的指针
}ArcNode;
typedef struct VNode
{
    VertexType data;//顶点信息
    ArcNode *firstarc;//指向第一条衣服该顶点的弧
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
    AdjList vertices;
    int ve,ne;
}ALGraph;

以邻接点的形式来表示弧：

#define MaxVertexNum 10   /* 最大顶点数设为10 */
typedef int Vertex;       /* 用顶点下标表示顶点,为整型 */

/* 邻接点的定义 */
typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex AdjV;        /* 邻接点下标 */
    PtrToAdjVNode Next; /* 指向下一个邻接点的指针 */
};

/* 顶点表头结点的定义 */
typedef struct Vnode{
    PtrToAdjVNode FirstEdge; /* 边表头指针 */
} AdjList[MaxVertexNum];     /* AdjList是邻接表类型 */

/* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode{  
    int Nv;     /* 顶点数 */
    int Ne;     /* 边数   */
    AdjList G;  /* 邻接表 */
};
typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */

3、图的遍历

①深度优先搜索

思路：从图中某个顶点V₀出发，访问此顶点，然后依次从V₀的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V₀有路径相通的顶点都被访问到。

深度优先搜索遍历类似于树的先序遍历，而判断v的邻接点w_i是否被访问，需要设立一个访问标志visit[w_i].

算法：

对于连通图：

void DFS(Graph G,int v)//从顶点v触发
{
    visit[v]=true;
    visitfunc(v);
    for(w=FirstAdjVex(G,v) ; w>=0 ; w=NextAdjVex(G,v,w))//取v的邻接点w；
    {
        if(!visit[w])
            DfS(G,w);//该店未被访问过，递归调用本函数
    }
}

对于非连通图：

void DFST(Graph G,status(*Visit)(int v))
{
    VisitFunc=Visit;
    for(v=0; v)
        visit[v]==false;
    for(v=0; v)
    {
        if(!visit[v])
            DFS(G,v);
    }
}

②广度优先搜索

思路：从图中的某个顶点V₀出发，并在访问此顶点之后依次访问V₀的所有未被访问过的邻接点，

之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V₀有路径相通的顶点都被访问到。
若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

深度优先搜索遍历类似于树的层次遍历

算法：

void BFS(Graph G,status(*Visit)(int v))
{
    for(v=0; v)
        visit[v]=false;
    initQueue(Q);
    for(v=0; v)
    {
        if(!visit[v])
        {
            visit[v]=true;
            Visit(v);//访问，比如输出
            EnQueue(Q,v);
            while(!QueueEmpty(Q))
            {
                DeQueue(Q,v);
                for(w=FirstAdjVex(G,v) ; w>=0 ; w=NextAdjVex(G,v,w))
                {
                    if(visit[w])
                    {
                        visit[w]=true;
                        EnQueue(Q,w);
                    }
                }
            }
        }
    }
}

4、最小生成树

5、最短路径Dijkstra算法
6、拓扑排序

①定义

检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。

按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。

由此所得顶点的线性序列称之为拓扑有序序列。

例如如下的两图，图一的拓扑有序序列可写为ABCD、ACBD；图二存在回路，所以没有拓扑有序序列

②拓扑排序

Step 1:从有向图中选取一个没有前驱的顶点，并输出之;

Step 2:从有向图中删去此顶点以及所有以它为尾的弧;

Step3:重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。

7、关键路径

①AOE网

AOE网(Activity On Edge Network)：即边表示活
动的网。 AOE网是一个带权的有向无环图。其中：
顶点表示事件（Event）

弧表示活动（Activity）
权值表示活动持续的时间

8、选择

1、若无向图G =（V，E）中含10个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是：37

m=n-1=9；

m(m-1)/2 + 1=37.

2、给定有向图的邻接矩阵如下：

顶点2（编号从0开始）的出度和入度分别是：0和2

行之和为出度，列之和为入度

3、如果G是一个有36条边的非连通无向图，那么该图顶点个数最少为多少？ 10

全连通图的话，n(n-1)/2=36,解得n=9,又题意里给出此图为非连通图，孤立一个点，则顶点个数至少为9+1=10

4、设O（N+E）

5、在一个无向图中，所有顶点的度数之和等于所有边数的多少倍？2

定理

6、下列关于无向连通图特征的叙述中，正确的是：①

①所有顶点的度之和为偶数

②边数大于顶点个数减1

③至少有一个顶点的度为1

①度数=出度+入度，出度=入度；②多种情况，最大是n(n-1)/2

7、在

一个有

对于有向图，其邻接矩阵表示比邻接表表示更易于：A

A.求一个顶点的入度 B.求一个顶点的出边邻接点 C.进行图的深度优先遍历 D.进行图的广度优先遍历 12、下列选项中，不是下图深度优先搜索序列的是：D

A.15432 B.13254 C.12543 D.12345

13、若某图的深度优先搜索序列是{V1, V4, V0, V3, V2}，则下列哪个图不可能对应该序列？C

15、已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是：11

16、给定无向图G，从V0出发进行深度优先遍历访问的边集合为： {(V0,V1), (V0,V4), (V1,V2), (V1,V3), (V4,V5), (V5,V6)}。则下面哪条边不可能出现在G中：C

A.(V0,V2) B.(V0,V6) C.(V1,V5) D.(V4,V6) 17、如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是：连通图 18、在图中自a点开始进行广度优先遍历算法可能得到的结果为：D

A.a, e, d, f, c, b B.a, c, f, e, b, d C.a, e, b, c, f, d D.a, b, e, c, d, f

19、在图中自c点开始进行广度优先遍历算法可能得到的结果为：C

A.c,a,b,e,f,d B.c,a,f,d,e,b C.c,f,a,d,e,b D.c,f,a,b,d,e 20、如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是：B A.G肯定不是完全图 B.G中一定有回路 C.G一定不是连通图 D.G有2个连通分量

21、给定一有向图的邻接表如下。若从v1开始利用此邻接表做广度优先搜索得到的顶点序列为：{v1, v3, v2, v4, v5}，则该邻接表中顺序填空的结果应为：v3、v2、v4

22、下列说法不正确的是：D

                     A.图的遍历是从给定的源点出发每一个顶点仅被访问一次     B.遍历的基本算法有两种：深度遍历和广度遍历                      C.图的深度遍历是一个递归过程     D.图的深度遍历不适用于有向图              23、下面关于图的存储的叙述中，哪一个是正确的？A
                     A.用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
                     B.用相邻矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
                     C.用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
                     D.用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关              24、如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是：连通图            25、对下图进行拓扑排序，可以得到不同的拓扑序列的个数是：3

寻找入度为0的点a，删除a点：

继续寻找入度为零的点并删去，发现有两个点，b和e，分别删去后如下：

以此类推，可构建：abecd abced aebcd

26、在拓扑排序算法中用堆栈和用队列产生的结果会不同吗？ 有可能会不同

27、在AOE网中，什么是关键路径？从第一个事件到最后一个事件的最长路径

9、判断

1、如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。 F

2、如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G一定有2个连通分量。 T

3、无向连通图边数一定大于顶点个数减1。 F

4、在一个有权无向图中，若b到a的最短路径距离是12，且c到b之间存在一条权为2的边，则c到a的最短路径距离一定不小于10。 T

5、无向连通图至少有一个顶点的度为1。 F

在顶点数n≥3的完全有向图中，没有度为1的节点

09 查找

1、静态查找表

①二分查找

int Search_ Bin ( SSTable ST, KeyType key)
{
    low= 1;
    high = STlength;//置区间初值while (low <= high) {
    mid= (low + high)/ 2;
    if (EQ(key, ST.elem[mid].key) )
        return mid;
//找到待查元素
    else if (LT(key, ST.elem[mid].key))
        high = mid- 1;
//继续在前半区间进行查找
    else
        low= mid + 1;
//继续在后半区间进行查找
}
  return0; // 顺序表中不存在待查元素
} // Search Bin

②顺序查找

int Search _Seq(SSTable ST, KeyType key)
{
    //在顺序表ST中顺序查找其关键字等于//key的数据元素。若找到，则函数值为//该元素在表中的位置，否则为0。
    ST.elem[0].key= key; //“哨兵
    for(i=STlength; ST.elem[i].key!=key; --i); //从后往前找
    return i;
    //找不到时，i为0

} // Search Seq

eg.在表中查找数据64

2、动态查找树表

①二叉排序树/二叉查找树/二叉搜索树

       定义:
      二叉排序树或者是一棵空树;或者是具有如下特性的二叉树:
      (1)若它的左子树不空，则左子树上所有结点的值均小于根结点的值;
      (2)若它的右子树不空，则右子树上所有结点的值均大于根结点的值;
    (3)它的左、右子树也都分别是二叉排序树。

?二叉搜索树下的查找：

                思路：若二叉排序树为空，则查找不成功;否则:
                          若给定值等于根结点的关键字，则查找成功;
                        若给定值小于根结点的关键字，则继续在左子树上进行查找;
                          若给定值大于根结点的关键字，则继续在右子树上进行查找

算法：在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找成功，则返回指针p指向该数据元素的结点,并返回函数值为TRUE;否则表明查找不成功，返回指针p指向查找路径上访问的最后一个结点，并返回函数值为FALSE，指针f指向当前访问的结点的双亲，其初始调用值为NULL。

Status SearchBST(BiTree T,BiTree f,BiTree &p,int key)//树，双亲结点，目标结点，目标数据
{
    if(!T)
    {
        p=f;
        return false;
    }
    else if(EQ(key,T->data.key))
    {
        p=T;
        return true;
    }
    else if(LT(key,T->data.key))
    {
        SearchBST(T->lchild,T,p,key)
    }
    else
        SearchBST(T->rchild,T,p,key)
}//SearchBST

?二叉搜索树下的插入：

思路：若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。

算法：当二叉排序树中不存在关键字等于e.key的数据元素时，插入元素值为e的结点，并返回TRUE;否则，不进行插入并返回FALSE。

Status InsertBST(BiTree &T,ElemType e)
{
    if(SearchBST(T,NULL,p,e.key))
    {
        s=(BiTree)malloc(sizeof(BiTNode));//为新结点分配空间
        s->data=e;
        s->lchild=s->rchild=NULL;
        
        if(!p)
            T=s;//s为根结点
        else if(LT(e.key,p->data.key))
            p->lchild=s;//s为p的左孩子
        else
            p->rchild=s;//s为p的右孩子
        
        return true;
    }
    else
        return false;
}

②二叉平衡树

3、哈希表

1、构造哈希函数

①直接定址法

哈希函数为关键字的线性函数: f(key)=a*key+b

②数字分析法

假设关键字集合中的每个关键字都是由s位数字组成(u1, u2,.., u,)，分析关键字集中的全体,并从中提取分布均匀的若干位或它们的组合作为地址。

此方法仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。

③平方取中法

以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”,同时平方值的中间各位又能受到整个关键字中各位的影响。

此方法适用于：关键字中的每一位都有某些数字重复出现频度很高的现象。

2、处理冲突的方法：

①开放定址法

                      H_i=( H(key) + d_i) MOD m（ i=,..,k(k< =m-1)）其中: H(key)为哈希函数; m为哈希表长;
                      d_i为增量序列;
                      对增量d;有三种取法:
                      ●1线性探测再散列
                         d_i=c*i   最简单的情况c=1

                      ●平方探测再散列
                           d_i=1,-12,2,-22,...
                      ●随机探测再散列
                        d_i是一组伪随机数列或者

di=iX H,(key) (又称双散列函数探测)

②再哈希法

H_i=RH_i(key)

RHi为不同的哈希函数，产生地址冲突时计算另一个哈希函数地址,直到不产生冲突为止。

③连地址法

将哈希地址相同的记录都链接在同一链表中

3、开放定址法的哈希表查找

#define SUCCESS 1
#define UNSUCCESS -1
int hashsize[]={997,...};
typedef struct
{
    ElemType *elem;
    int count;
    int sizeindex;
    //hashsize[sizeindex];
}HashTable;
Status searchhash(HashTable H,int K,int &p,int &c)
{
    p=Hash(K);//求哈希地址
    while(H.elem[p].key!=NULL&&K!=H.elem[p].key)
        collision(p,++c);//求下一探查地址p
    if(K==H.elem[p].key)
        return SUCCESS;
    else
        return UNSUCCESS;
}

4、ASL平均查找长度

顺序查找——失败：n；成功：(n+1)/2

二分查找/二叉排序树——log₂n↓+1 (log₂(n+1)-1)；时间复杂度O(log₂n)

二叉平衡树——

哈希表——

5、选择

1、已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用二分查找法查找一个L中不存在的元素，则关键字的比较次数最多是：5

log₂n↓+1

2、用二分查找从100个有序整数中查找某数，最坏情况下需要比较的次数是：7

带入上题的公式

3、下列二叉树中，可能成为折半查找判定树（不含外部结点）的是：A

首先我们可以知道 $\left \lfloor \frac{(l+r)}{2} \right \rfloor$ 对应的判定树的叶子节点是向右偏移， $\left \lceil \frac{(l+r)}{2} \right \rceil$ 向左偏移。

因此我们知道2,3不对，其次叶子节点一定是连续的，不会出现第四个的情况。

4、若二叉搜索树是有

$A.所有结点的平均查找效率是O(logN) B.最小值一定在叶结点上 C.最大值一定在叶结点上 D.中位值结点在根结点或根的左子树上$

$5、若二叉搜索树是有N个结点的完全二叉树，则不正确的说法是： B A.平均查找效率是O(logN) B.最大值一定在最后一层 C.最小值一定在叶结点上 D.中位值结点在根结点或根的左子树上$

$6、$ 对二叉搜索树进行什么遍历可以得到从小到大的排序序列？ 中序遍历

$7、下列叙述正确的是（）。 D A.在任意一棵非空二叉搜索树，删除某结点后又将其插入，则所得二叉搜索树与删除前原二叉搜索树相同。 B.二叉树中除叶结点外, 任一结点X，其左子树根结点的值小于该结点（X）的值；其右子树根结点的值\geq该结点（X）的值，则此二叉树一定是二叉搜索树。 C.虽然给出关键字序列的顺序不一样，但依次生成的二叉搜索树却是一样的。 D.在二叉搜索树中插入一个新结点，总是插入到最下层，作为新的叶子结点。 8、哈希表的平均查找长度( )。 C A．与冲突处理方法有关而与表长无关 B．与冲突处理方法无关而与表长有关 C．与冲突处理方法和表长都有关 D．与冲突处理方法和表长都无关$

6、判断

1、二叉搜索树的查找和折半查找的时间复杂度相同。F

只有平衡的二叉搜索树才与折半查找时间复杂度相同

2、二叉搜索树的最小元素一定位于树根的左子树。 F

还有可能是根结点

10 排序

$1、排序种类$

左侧分析表取自博客，来源右下角水印

$希尔排序：将原序列分成若干子序列，对子序列进行插入排序冒泡排序：对长度为n的序列进行n(n-1)/2次比较排列快速排序：设置枢轴进行多次划分，将多部分进行排序达到整体排序的效果选择排序：从未排序序列中依次取出元素与未排序序列中的元素进行比较，将最小值其放入已排序序列列尾位置的方法插入排序：从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置的方法归并排序：将两个或两个的以上的有序序列归并成新的有序序列堆排序：通过建堆、交换达到排序的目的$

$对于起泡排序和选择排序而言，每一趟过后都能确定一个元素的最终位置$

$对于插入排序、起泡排序和选择排序而言，两趟过后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列不满足。$

$2、判断$

$1、对$

对

5、对N个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。F

3、选择

1 、对10TB的数据文件进行排序，应使用的方法是：归并排序

外部排序指待排序文件较大，内存一次性放不下，需存放在外部介质中。外部排序通常采用归并排序法。选项A、B、C都是内部排序的方法。

2、数据序列{ 3, 1, 4, 11, 9, 16, 7, 28 }只能是下列哪种排序算法的两趟排序结果？快速排序

3、希尔排序的组内排序采用的是（）。 直接插入排序

4、在内部排序时，若选择了归并排序而没有选择插入排序，则可能的理由是：仅有3

归并排序的程序代码更短....1

归并排序占用的空间更少....2

归并排序的运行效率更高....3

归并排序代码比选择插入排序更复杂，前者空间复杂度是O(n)，后者是O(1)。但是前者时间复杂度是O(nlogn)，后者是O(n²)

5、将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下：

第1趟排序后：2, 12, 16, 10, 5, 34, 88

第2趟排序后：2, 5, 10, 12, 16, 34, 88

则可能的排序算法是：快速排序

6、若数据元素序列{ 11，12，13，7，8，9，23，4，5 }是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是：C

A.冒泡排序 B.选择排序 C.插入排序 D.归并排序

对于起泡排序和选择排序而言，每一趟过后都能确定一个元素的最终位置，而由题目中所说，前两个元素和后两个元素均不是最小或最大的两个元素并按序排列。

插入排序在每趟排序结束后能保证前面的若干元素是有序的，而此时第二趟排序后，序列的前三个元素是有序的，符合其特点。

7、数据序列{ 3，2，4，9，8，11，6，20 }只能是下列哪种排序算法的两趟排序结果？D

A. 冒泡排序 B.选择排序 C.插入排序 D.快速排序

排除AB的方法同上；

对于C，插入排序在每趟排序结束后能保证前面的若干元素是有序的，第二次排序完成后，应该出现三个有序元素在列首或列尾。

8、对于7个数进行冒泡排序，需要进行的比较次数为：21

n(n-1)/2，n长的序列比较n-1趟

9、在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都会停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？O(NlogN)

10、在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？O(N²)

在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左指针停止移动，而右指针在同样情况下却不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？O(N²)

$11、对一组包含10个元素的非递减有序序列，采用直接插入排序排成非递增序列，其可能的比较次数和移动次数分别是： D$

A.100 100 B.100 54 C.54 63 D.45 44 假设插入的顺序是递增的，排序后要求全部递减，这样的比较次数应该是最多的。 即除了第一个进去的元素，其他的每一次新插入的元素都要跟已经插进去的元素做对比，共9(9+1)/2，即45次。 故可能的次数应<=45 12、对于序列{ 49，38，65，97，76，13，27，50 }，按由小到大进行排序，下面哪一个是初始步长为4的希尔排序法第一趟的结果？ A.13,27,38,49,50,65,76,97 B.49,13,27,50,76,38,65,97 C.49,76,65,13,27,50,97,3 D.97,76,65,50,49,38,27,13 13、设有1000个元素的有序序列，如果用二分插入排序再插入一个元素，则最大比较次数是：D A.1000 B.999 C.500 D.10 注意是“二分插入排序”。log₂n取整再加一，n=1000，得10 1 4、下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是：4、5

1.插入排序；2.选择排序；3.起泡排序；4.希尔排序；5.堆排序

堆排序和希尔排序都利用了顺序存储的随机访问特性。

           15、有组记录的排序码为{ 46，79，56，38，40，84 }，则利用堆排序的方法建立的初始堆为：
                    A.79，46，56，38，40，80
                    B.84，79，56，46，40，38
                    C.84，56，79，40，46，38
                    D.84，79，56，38，40，46

           16、采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是：
                A.每次划分后，先处理较长的分区可以减少递归次数
                B.每次划分后，先处理较短的分区可以减少递归次数
                C.递归次数与每次划分后得到的分区处理顺序无关
                D.递归次数与初始数据的排列次序无关

17、对 $N$ 个元素采用简单选择排序，比较次数和移动次数分别为：O(N²),O(N）

18、对于10个数的简单选择排序，最坏情况下需要交换元素的次数为 9

19、

采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是：

(2分) A.

每次划分后，先处理较长的分区可以减少递归次数

每次划分后，先处理较短的分区可以减少递归次数

递归次数与每次划分后得到的分区处理顺序无关

递归次数与初始数据的排列次序无关

review