1.         以Niklus Wirth的观点，程序等于什么? =数据结构+算法

2.         算法的重要特性：确定、有穷、能行、输入、输出

3.         好算法的标准：正确、可读、健壮、高效低存贮

4.         数据结构主要研究对象：逻辑结构、存贮结构和运算（增删改查）

5.         数据的逻辑结构有几大类？（线性、非线性）

6.         数据的存贮结构有几类？（顺序、链式、索引、散列hash）

7.         对数据的最主要的操作：增删改查

8.         线性结构的特点:

在数据元素的非空有限集中

存在唯一一个被称做"第一个"的数据元素；     

存在唯一一个被称做“最后一个”的数据元素；

除第一个元素外，每个数据元素均有唯一一个直接前驱；

除最后一个元素外每个数据元素均有唯一一个直接后继。

9.         线性结构与非线性结构的区别。

    在线性结构中，该数据结构中的元素是一对一的关系，非线性结构就不是了

线性结构是最简单最常用的一种数据结构,线性结构的特点是结构中的元素之间满足线性关系,按这个关系可以把所有元素排成一个线性序列.线性表,串,栈和队列都属于线性结构.

非线性结构是指在该类结构中至少存在一个数据元素,它具有两个或者两个以上的前驱或后继.如树和二叉树等.

10.     列出所学过的线性结构与非线性结构。

线性结构：线性表、队列、栈、数组、串

非线性结构：广义表、树、图

11.  头指针、头结点、首元结点的区别。

头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针； 
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针?那还得另配一个头指针!） 
首元素结点是指链表中存储线性表中第一个数据元素a1的结点.

12.     带头结点和不带头结点的线性链表的区别。

带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。
在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点。
在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点，算法步骤都相同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不同

13.     单链表、双链表、循环链表的区别、各自的优缺点及怎样决定选取何种存贮结构。

  单链表：每个结点中只包含一个指针域
    优点：插入和删除时候不需要移动大量的元素

缺点：指针只能单方向移动
  双链表：有两个指针域，其一指向直接后继，其二指向直接前驱
    优点：查找直接前驱的时候，则从头指针出发，能够克服单链表这种单向性的缺点

缺点：插入删除操作时需要修改多个指针域
  循环链表：最后一个结点的指针域指向头结点
    优点：使两个表连接起来就很简单，这个操作仅需两个指针即可，插入、删除时，不会断链等。

缺点：不容易确定退出循环的条件

14.     栈和队列是什么样的线性表?

栈与队列是操作受限制的线性表

15.     指出顺序线性表、顺序栈、顺序队列的区别。

      相同：他们都是线性表，都是一维数组，
     不相同：操作不同而已；
           线性表：任意位置操作

            栈：栈顶操作

        队列：尾进头出

16.     例举栈和队列的实例及用栈和队列所能解决的问题。

   栈：铁路中转站，餐厅的食物盘, 子弹壳。
   队列：操作系统作业排队，排队买东西
   栈解决的问题是：后进先出的数据（LIFO）
   队列解决的问题：先进先出的数据 (FIFO)

17.     指出通常解决队列和栈溢出时所能用到的方法。

   队列：双向队列，链队列，循环队列
    栈：双栈共享，多栈共享，链栈

18.     循环队列的循环是怎样实现的?

队头、队尾指针加1，用取模(余数)运算实现循环

19.     给出对称矩阵、三角矩阵、对角矩阵节省内存的存贮结构并写出相应的输入、输出算法。

对称矩阵的存贮结构：

利用 = 来存储(以按行存储为例)

K=I(I-1)/2 +J-1  I>=J;
K=J(J-1)/2 +I-1  I<J;

 k 是对称矩阵位于（i，j）位置的元素在一维数组中的存放位置，从0开始

三角矩阵的存贮结构：

以下三角为例，当i<j时,aij=0

K=0的位置存储0

对角矩阵的存贮结构：

记住loc( aij )=loc( a11 )+( 2i+j-3 ) L    i-1<=j<=i+1

输入输出算法：自己写（你应该会写了）

20.     给出稀疏矩阵的节省内存的存贮结构并写出相应的输入、输出算法。

为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。其中每一个非零元素所在的行号、列号和值组成一个三元组，并由此三元组惟一确定。

三元组表

#define MAXSIZE 100              //非零元个数的最大值

 typedef struct{

   int i,j;               // 行下标,列下标

   ElemType e; // 非零元素值

 }Triple;

typedef struct

 {Triple data[MAXSIZE+1]; //非零元三元组表,data[0]未用

   int mu,nu, tu; // 矩阵的行数、列数和非零元个数

 }TSMatrix;

十字链表

typedef struct OLNode                 //结点的定义

 {int i,j;                                            // 非零元的行和列下标

   ElemType e;                                // 非零元素值

   struct OLNode *right,*down;    // 该非零元所在行表和列表的后继链域

 }OLNode, *OLink;

 typedef struct                           //链表的定义

 { OLink *rhead,*chead;  // 行和列链表头指针向量基址,由CreatSMatrix_OL()分配

   int mu,nu,tu;            // 稀疏矩阵的行、列数和非零元个数

 }CrossList;

输入输出算法（你应该自己会写啦）

21.     用十字链表存贮稀疏矩阵时, 矩阵的每个元素同时在几条链上, 分别被称为什么链？

  两条链：行链和列链

22.     给出树的不同的几种表示（图示）形式。

（一）层次表示法     （二）广义表表示法
（三）嵌套表示法   （四）凹入法表示法

23.     在二叉树的第 i层上至多有多少个结点。深度为 K的二叉树至多有多少个结点。

24.     在一颗二叉树中, 其叶子结点数n0和度为二的结点数n2之间的关系。

25.     有 n个结点的完全二叉树的深度。

26.     在二叉树的顺序存贮结构中如何求结点的双亲、孩子?

双亲：i/2；   左孩子：2*i；   右孩子：2*i+1；

27.     有 n个结点的二叉树用二叉链表存贮时有多少个空链域，用三叉链表存贮时有多少个空链域。

         二叉：n+1个空链域

           三叉：n+2个空链域

 28.     为什么可在不增加指针域的情况下，对二叉树进行线索化，线索化的目的是什么?

    a.利用n+1个空链域      

    b.目的：遍历方便

 29.  对于已线索化二叉树如何识别指针域是指向孩子还是其后继结点?

  增加标志域    LeftThread和RightThread

LeftThread=0,     LeftChild为左孩子指针

LeftThread=1,     LeftChild为前驱线索

RightThread=0,   RightChild为右孩子指针

RightThread=1,   RightChild为后继指针

 30.  树的几种存贮结构(双亲表示法、孩子表示法、孩子兄弟表示法)的优缺点，各自适应的运算。

双亲表示法：便于查找双亲，

             缺点：找孩子难
       孩子表示法：便于涉及到孩子的操作，
             缺点：找双亲难
       孩子兄弟法：操作容易
             缺点：破坏了树的层次

 31.  哪种存贮结构可将森林转为二叉树。对此种结构的各个域给予注释。说明在这个结构中怎样找到森林的n棵树。

孩子兄弟表示法，左指针是第一个孩子，右指针是第一个兄弟，最右的为第n棵树

 32.  树的先根遍历、后根遍历对应其二叉树的哪种遍历，森林的先根遍历、中根遍历对应其二叉树的哪种遍历?

  树的先根遍历对应二叉树的先序遍历；
  树的后根遍历对应二叉树的中序遍历；
  森林的先根遍历对应于二叉树的先序遍历；

  森林的中根遍历对应于二叉树的中序遍历。

 33.  写算法求树中结点的度；树的度；树中的叶子结点数；树中的非终端结点数；树中某结点的兄弟、祖先、子孙、层次、堂兄弟；树的高度；森林中树的数目。

考试时候大家默认为树是二叉树，减轻自己负担又不会错

求树中结点的度：（孩子表示法）求树的度只需要指针移动，度数递增就好

树的度：先把每个结点的度数求出来，再把所有结点的度数总和求出来就好啦

求树的叶子结点的个数：（下面这个只是求二叉树的）

int Leaf_Count(Bitree T)

 {//求二叉树中叶子结点的数目

   if(!T) return 0; //空树没有叶子

    else if(!T->lchild&&!T->rchild) return 1;
                                                                 //叶子结点
         else return Leaf_Count(T-lchild)+Leaf_Count(T-rchild);

                                       //左子树的叶子数加上右子树的叶子数
}

求森林中树的数目：就是右孩子循环过去，算出右孩子的数目，再加上本身根节点（即右孩子树+1）

后面的其它的求的，自己应该能想出来

大致上很多都是用递归算法

 34.  Huffman树能够解决的问题是什么？图示huffman编码过程。

数据通信中的数据压缩编码问题

 35.  如何设计Huffman编译码器最有效？

没做出来，别问我（考这个就等死啦）

1.高频率的短编码  2.不要是别的编码的前缀编码

36.  何为完全图、稀疏图、稠密图。

完全图：对有向图来说，边数为n(n-1),对无向图来说,边数为n(n-1)/2
稀疏图：有很少条边的图(e<<n )
稠密图：有很多条边的图

 37.  写算法求无向图中结点的度；有向图中结点的入度和出度。

  （这里只给思想，不给算法，邻接矩阵存图）

 无向图：邻接矩阵的一行或一列的数值和，代表对应定点的度。

 有向图：邻接矩阵的行代表对应顶点的出度，列代表入度。38.  图的邻接矩阵、邻接表存贮结构各自的优缺点，适应的运算。

  图的数组表示法（邻接矩阵表示法）：二维数组存储图
       优点：容易求各个顶点的度
       缺点：当图为稀疏图时浪费空间

  邻接表表示法：
       优点：容易找到第一个邻接点和下一个邻接点，
       缺点：不方便找一个结点的入度

 39.  最小代价生成树的实际应用背景。

  公路， 铁路，通讯网等等实际问题的急需解决

例子：要在n个城市间建立通信联络网，

顶点——表示城市

权——城市间建立通信线路所需花费代价

希望找到一棵生成树，它的每条边上的权值之和（即建立

该通信网所需花费的总代价）最小———最小代价生成树

 40.  什么图适合用Prim算法求最小代价生成树，什么图适合用 Kruskal算法求最小代价生成树。

Prim算法适合求稠密的网的最小生成树

kruskal适合求稀疏的网的最小生成树

一般来说，当n>47时，用prim比较好！

 41.  图示用 Prim算法及 Kruskal算法求最小代价生成树的过程。

（给出思想，图自己根据思想或伪代码演示）

方法一：普里姆(Prim)算法

                   ——加点法，时间复杂度O(n2)

   从某顶点开始，找其相邻边中权值最小的边所连另一个顶点，再找与这两个顶点相邻边中权值最小的边所连第三个顶点，重复，扩展到所有顶点。

方法二：克鲁斯卡尔（Kruskal）算法

                   ——加边法,时间复杂度与边相关

   先将所有顶点都看作无边的非连通图，选择各顶点间最小边做连通分量，直到所有顶点都在同一个连通分量上。

 42.  举例简述“拓扑排序”所解决的实际问题。

流程图，施工流程图，课程决定的优先权

 43.  请图示“拓扑排序”的过程。

（给出思想，图自己根据思想或伪代码演示）

拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序的操作。拓扑排序实际上是对邻接表表示的图进行深度优先遍历的过程.

（具体自己举个树的例子，然后对其拓扑排序）

a.在有向图中任选一个没有前趋的顶点输出；

b.从图中删除该顶点和所有以它为尾的弧；

c.重复上述a、b，直到全部顶点都已输出，此时，顶点输出序列即为一个拓朴有序序列； 或者直到图中没有无前趋的顶点为止。如果还有有前驱的顶点，此情形表明有向图中存在环。

 44.  举例简述“关键路径”所解决的实际问题。

  一个工程的并行的进行过程

（1） 完成整个工程至少需要多少时间；

（2） 哪些活动是影响工程的关键。

 45.  最短路径的两个算法是什么？

迪杰斯特拉Dijkstra算法：求从某个源点到其余各顶点的最短路径；

弗洛易德Floyd算法：求每一对顶点之间的最短路径

 46.  简述静态查找和动态查找？

静态查找：基于线性表的查找

            只对查找表进行查询某个特定的数据元素或某个特定数据元素的各种属性的操作。如：查询成绩表中是否有某学生或该学生某门课程的成绩。

动态查找：基于树的查找

对查找表进行查找，找不到就插入某个数据元素的操作。如：查找某个学生信息，找不到就插入。

47.  顺序查找、折半查找、分块查找算法适合的关键字结构和存贮结构。

  顺序查找：对存储结构和关键字排列方式没有特殊要求

      折半查找：关键字整体有序，只适合顺序存储的有序表

  分块查找：关键字局部有序，即分块有序，对存储结构为顺序和线性链表的均适用

 48.  怎样从二叉排序树得到有序表。

  中序遍历

 49.  已知长度为n 的表按表中元素顺序构造平衡二叉排序树，图示构造过程。

提醒：得事先弄懂 LL型平衡旋转  RR型平衡旋转  LR型平衡旋转  RL型平衡旋转

在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，如果是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。通常将这样得到的平衡二叉排序树简称为AVL树

 50.  解释构造平衡二叉排序树的过程中做各种旋转后仍能满足二叉排序树的特性。

利用大小顺序来解释

 51.  各种查找算法的平均时间复杂度。

      查找类型                   平均时间复杂度

      顺序查找                       O（n）

      折半查找                       O（Log₂N）

      分块查找                       O（n）-不确定原式为：1/2*(n/m+m)+1

 52.  简述Hash查找的构建过程。

 53.  为一组关键字构造哈希函数并建立哈希表。

构造哈希函数的方法：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法

1. 哈希函数(散列函数):

把关键字key映射成记录存贮地址的函数。

记做: d=H(key)，

把哈希函数值d称为K的哈希地址或散列地址。

     2.哈希表:

假定有查找表:ht[0]～ht[n-1]，

根据记录的关键字K计算出d=H(key),以d为记录地址，所构成的表叫做哈希表。

 54.  指出希尔排序，归并排序，快速排序，堆排序，基数排序中稳定的排序方法，并对不稳定的举出反例。

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，

冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

 55.  堆排序算法选用什么样的存贮结构，按此算法得到的有序表是递增还是递减的。图示建堆过程。

一维数组存储，

小顶堆：递增

大顶队：递减

 56.  藉助于“比较”进行排序的算法在最坏情况下能达到的最好的时间复杂度是什么?

 57.  指出直接插入排序，冒泡排序，快速排序, 堆排序，基数排序算法各适合的关键字结构。

直接插入排序：基本有序

冒泡排序：基本有序

归并排序：多个排序表
                快速排序：混乱的情况
                  堆排序：数据非常大
                基数排序：多关键字排序

 58.  指出各种排序算法的平均时间复杂度、最坏情况的时间复杂度。

数据结构复习