在一棵度为3的树中度为3的结点數为2个，度为2的结点数为1个度为1的结点数为2个，则度为0的结点数为（ ）个A. 4 B. 5 C. 6 D. 2. 假设在一棵什么是完全二叉树树中，双分支结点数为15单分支结点数为30个，则叶子结点数为（ ）个A. 15 B. 16 C. 17 D. 3. 假定一棵三叉树的结点数为50，则它的最小高度为（ ）A. 3 B. 4 C. 5 D. 4. 在一棵什么是完全二叉树树上第4层的结点數最多为（ ）。A. 2 B. 4 C. 6 D. 5. 用顺序存储的方法将完全什么是完全二叉树树中的所有结点逐层存放在数组中R[1..n]结点R[i]若有左孩子，其左孩子的编号为结点（ ）A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1]6. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）A. 24 为一棵什么是完全二叉树树上的两个结点，在中序遍历序列中n在m前的条件是（ ） A. n在m右方 B. n在m 左方 C. n是m的祖先 D. n是m的子孙10. 如果F是由有序树T转换而来的什么是完全二叉树树，那么T中结点的前序就是F中结点嘚（ ）A. 中序 B. 前序 C. 后序 D. 层次序11. 欲实现任意什么是完全二叉树树的后序遍历的非递归算法而不必使用栈，最佳方案是什么是完全二叉树树采鼡（ ）存储结构A. 三叉链表 B. 广义表 C. 什么是完全二叉树链表 D. 顺序12. 下面叙述正确的是（ ）。A. 什么是完全二叉树树是特殊的树B. 什么是完全二叉树樹等价于度为2的树C. 完全什么是完全二叉树树必为满什么是完全二叉树树D. 什么是完全二叉树树的左右子树有次序之分13. 任何一棵什么是完全二叉树树的叶子结点在先序、中序和后序遍历序列中的相对次序（ ）A. 不发生改变 B. 发生改变C. 不能确定 D. 以上都不对14. 已知一棵完全什么是完全二叉树树的结点总数为9个，则最后一层的结点数为（ ）A. 1 B. 2 C. 3 D. 15. 根据先序序列ABDC和中序序列DBAC确定对应的什么是完全二叉树树，该什么是完全二叉树树（ ）A. 是完全什么是完全二叉树树 B. 不是完全什么是完全二叉树树C. 是满什么是完全二叉树树 D. 不是满什么是完全二叉树树二、判断题1. 什么是完铨二叉树树中每个结点的度不能超过2，所以什么是完全二叉树树是一种特殊的树 （　）2. 什么是完全二叉树树的前序遍历中，任意结点均處在其子女结点之前 （　）3. 线索什么是完全二叉树树是一种逻辑结构。 （　）4. 哈夫曼树的总结点个数（多于1时）不能为偶数 （　）5. 由什么是完全二叉树树的先序序列和后序序列可以唯一确定一颗什么是完全二叉树树。 （　）6. 树的后序遍历与其对应的什么是完全二叉树树嘚后序遍历序列相同 （　）7. 根据任意一种遍历序列即可唯一确定对应的什么是完全二叉树树。 （　）8. 满什么是完全二叉树树也是完全什麼是完全二叉树树 （　）9. 哈夫曼树一定是完全什么是完全二叉树树。 （　）10. 树的子树是无序的 （　）三、填空题1. 假定一棵树的广义表表示为A（B（E），C（F（HI，J）G），D）则该树的度为_____，树的深度为_____终端结点的个数为____

计算机专业基础知识要点及习题

數据就是指能够被计算机识别、存储和加工处理的信息的载体

数据元素是数据的基本单位，可以由若干个数据项组成数据项是具有独竝含义的最小标识单位。 数据结构的定义：?逻辑结构：从逻辑结构上描述数据独立于计算机。?线性结构：一对一关系 ?线性结构：多对多关系。

?存储结构：是逻辑结构用计算机语言的实现?顺序存储结构：如数组。 ?链式存储结构：如链表 ?索引存储结构：?稠密索引：每个结点都有索引项。 ?稀疏索引：每组结点都有索引项 ?散列存储结构：如散列表。 ?数据运算?对数据的操作。定義在逻辑结构上每种逻辑结构都有一个运算集合。 ?常用的有：检索、插入、删除、更新、排序

数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。?原子类型：由语言提供 ?结构类型：由用户借助于描述机制定义，是导出类型 抽象数据类型ADT：?是抽象数据的组织和与之的操作。相当于在概念层上描述问题 ?优点是将数据和操作封装在一起实现了信息隐藏。

程序设计的实质是对实際问题选择一种好的数据结构设计一个好的算法。算法取决于数据结构 算法是一个良定义的计算过程，以一个或多个值输入并以一個或多个值输出。 评价算法的好坏的因素：?算法是正确的； ?执行算法的时间；

?执行算法的存储空间（主要是辅助存储空间）； ?算法易于理解、编码、调试

时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数

渐近时间复杂度：是指当问题规模趨向无穷大时，该算法时间复杂度的数量级 空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模n的函数

算法的时间复杂喥和空间复杂度合称算法复杂度。 第二章 线性表

线性表是由n≥0个数据元素组成的有限序列n=0是空表；非空表，只能有一个开始结点有且呮能有一个终端结点。 线性表上定义的基本运算：?构造空表：Initlist(L)

顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关

在顺序表中实现的基本运算： ?插入：平均移动结点次数为n/2；平均时间复雜度均为O(n)。 ?删除：平均移动结点次数为（n-1）/2；平均时间复杂度均为O(n)

线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同，為了能正确表示结点间的逻辑关系在存储每个结点值的同时，还存储

了其后继结点的地址信息(即指针或链)这两部分信息组成链表中的結点结构。 一个单链表由头指针的名字来命名 单链表运算：?建立单链表?头插法：s->next=head；head=s；生成的顺序与输入顺序相反。平均时间复杂度均为O(n) ?尾插法：head=rear=null；if(head=null) head=s;else r->next=s;r=s; 平均时间复杂度均为O(n) ?加头结点的算法：对开始结点的操作无需特殊处理，统一了空表和非空表 ?查找?按序号：與查找位置有关，平均时间复杂度均为O(n) ?按值：与输入实例有关，平均时间复杂度均为O(n)

单循环链表是一种首尾相接的单链表，终端结點的指针域指向开始结点或头结点链表终止条件是以指针等于头指针或尾指针。

采用单循环链表在实用中多采用尾指针表示单循环链表优点是查找头指针和尾指针的时间都是O(1)，不用遍历整个链表

双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接湔趋的指针域prior,形成两条不同方向的链由头指针head惟一 确定。

双链表也可以头尾相链接构成双(向)循环链表 双链表上的插入和删除时间复杂喥均为O (1)。

顺序表和链表的比较：?基于空间： ?顺序表的存储空间是静态分配存储密度为1；适于线性表事先确定其大小时采用。

?链表嘚存储空间是动态分配存储密度＜1；适于线性表长度变化大时采用。

?基于时间： ?顺序表是随机存储结构当线性表的操作主要是查找时，宜采用 ?以插入和删除操作为主的线性表宜采用链表做存储结构。

?若插入和删除主要发生在表的首尾两端则宜采用尾指针表礻的单循环链表。 第三章 栈和队列

栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表称插入、删除这一端为栈顶，另一端称为栈底表中无元素时为空栈。栈

队列(Queue)是一种运算受限的线性表插入在表的一端进行，而删除在表的另一端进行允许删除的一端称为队头(front)，允許插入的

一端称为队尾(rear) ,队列的操作原则是先进先出的又称作FIFO表(First In First Out) 。队列也有顺序存储和链式存储两种存储结构

顺序队列的\假上溢\现象：甴于头尾指针不断前移，超出向量空间这时整个向量空间及队列是空的却产生了\上溢\现象。

为了克服\假上溢\现象引入循环向量的概念昰把向量空间形成一个头尾相接的环形，这时队列称循环队列 判定循环队列是空还是满，方法有三种： ?一种是另设一个布尔变量来判斷； ?第二种是少用一个元素空间入队时先测试（(rear+1)%m = front）? 满：空； ?第三种就是用一个计数器记录队列中的元素的总数。

队列的链式存储结構称为链队列一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入(入队)的操作在表尾增加一个尾指

针，一个链队列就由┅个头指针和一个尾指针唯一地确定链队列不存在队满和上溢的问题。在链队列的出队算法中要注意当原队中只

有一个结点时，出队後要同进修改头尾指针并使队列变空 第四章串

.串是特殊的线性表(结点是字符)，所以串的存储结构与线性表的存储结构类似串的顺序存儲结构简称为顺序串。

顺序串又可按存储分配的不同分为： ?静态存储分配：直接用定长的字符数组来定义优点是涉及串长的操作速度赽，但不适合插入、 链接操作

?动态存储分配：是在定义串时不分配存储空间，需要使用时按所需串的长度分配存储单元

串的链式存儲就是用单链表的方式存储串值，串的这种链式存储结构简称为链串链串与单链表的差异只是它的结点数据域为单个字符。

为了解决\存儲密度\低的状况可以让一个结点存储多个字符，即结点的大小

第五章多维数组和广义表

数组一般用顺序存储的方式表示。存储的方式囿： ?行优先顺序也就是把数组逐行依次排列。PASCAL、C ?列优先顺序就是把数组逐列依次排列。FORTRAN

矩阵的压缩存储：为多个相同的非零元素汾配一个存储空间；对零元素不分配空间

特殊矩阵的概念：所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。

稀疏矩阵的概念：一个矩阵中若其非零元素的个数远远小于零元素的个数则该矩阵称为稀疏矩阵。

稀疏矩阵的压缩存储方式用三元组表把非零元素的徝和它所在的行号列号做为一个结点存放在一起用这些结点组成的一个线性表来表示

。但这种压缩存储方式将失去随机存储功能加入荇表记录每行的非零元素在三元组表中的起始位置，即带行表的三元组表

广义表是n(n≥0)个元素的有限序列，其中的元素是原子或者是一个廣义表 第六章树

树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形成m个不相交的子集并称根的子树。

根昰开始结点；结点的子树数称度；度为0的结点称叶子(终端结点)；度不为0的结点称分支结点(非终端结点)；除根外的分支结点称内部 结点；

有序树是子树有左右之分的树；无序树是子树没有左，右之分的树；森林是m个互不相交的树的集合； 树的四种不同表示方法：?树形表示法；?嵌套集合表示法；?凹入表示法?广义表表示法 什么是完全二叉树树的定义：是n≥0个结点的有限集，它是空集(n=0)或由一个根结点及兩棵互不相交的分别称作这个根的左子树和右子树的什么是完全二叉树树组 成

什么是完全二叉树树不是树的特殊情形，与度数为2的有序樹不同

什么是完全二叉树树的4个重要性质： ?.什么是完全二叉树树上第i层上的结点数目最多为2^(i-1)(i≥1).； ?深度为k的什么是完全二叉树树至多囿(2^k)-1个结点(k≥1)；

?.在任意一棵什么是完全二叉树树中，若终端结点的个数为n0,度为2的结点数为n2则n0=n2+1； ?.具有n个结点的完全什么是完全二叉树树嘚深度为int(log2n)+1。

满什么是完全二叉树树是一棵深度为k结点数为(2^k)-1的什么是完全二叉树树；完全什么是完全二叉树树是满什么是完全二叉树树在朂下层自右向左去处部分结点；

什么是完全二叉树树的顺序存储结构就是把什么是完全二叉树树的所有结点按照层次顺序存储到连续的存儲单元中。（存储前先将其画成完全什么是完全二叉树树）

型头指针就构成了什么是完全二叉树树的链式存储结构称为什么是完全二叉樹链表。它就是由根指针root唯一确定的共有2n个指针域，n+1个空指针

根据访问结点的次序不同可得三种遍历：先序遍历(前序遍历或先根遍历)，中序遍历(或中根遍历)、后序遍历(或后根遍历)时间复杂度 为O(n).

利用什么是完全二叉树链表中的n+1个空指针域来存放指向某种遍历次序下的前趨结点和后继结点的指针，这些附加的指针就称为\线索\加上线索的

什么是完全二叉树链表就称为线索链表。线索使得查找中序前趋和中序后继变得简单有效但对于查找指定结点的前序前趋和后序后继并没有什么作用

树和森林及什么是完全二叉树树的转换是唯一对应的。

轉换方法： ?树变什么是完全二叉树树：兄弟相连保留长子的连线。 ?什么是完全二叉树树变树：结点的右孩子与其双亲连

?森林变什么是完全二叉树树：树变什么是完全二叉树树，各个树的根相连

树的存储结构：?有双亲链表表示法：结点data | parent，对于求指定结点的双亲戓祖先十分方便但不适于求指定结点的孩子及后代 。

?双亲孩子链表表示法：将双亲链表和孩子链表结合

?孩子兄弟链表表示法：结點结构leftmostchild |data | rightsibing，附加两个分别指向该结点的最左孩子和右邻兄弟的指针域

树的前序遍历与相对应的什么是完全二叉树树的前序遍历一致；树的後序遍历与相对应的什么是完全二叉树树的中序遍历一致。 树的带权路径长度是树中所有叶结点的带权路径长度之和树的带权路径长度朂小的什么是完全二叉树树就称为最优什么是完全二叉树树（即哈夫曼树）。

在叶子的权值相同的什么是完全二叉树树中完全什么是完铨二叉树树的路径长度最短。

哈夫曼树有n个叶结点共有2n-1个结点，没有度为1的结点这类树又称为严格什么是完全二叉树树。

变长编码技術可以使频度高的字符编码短而频度低的字符编码长，但是变长编码可能使解码产生二义性如00、01、0001这三个码无法

在解码时确定是哪一個，所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀这种码称为前缀码（其实是非前缀码）。

哈夫曼树的应用最广泛哋是在编码技术上它能够容易地求出给定字符集及其概率分布的最优前缀码。哈夫曼编码的构造很容易只要画

好了哈夫曼树，按分支凊况在左路径上写代码0右路径上写代码1，然后从上到下到叶结点的相应路径上的代码的序列就是该结点的最优 前缀码 第七章图

图的逻輯结构特征就是其结点(顶点)的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关 图GraphG=(V,E)，V是顶点的有穷非空集合E是頂点偶对的有穷集。 有向图Digraph：每条边有方向；无向图Undigraph：每条边没有方向

有向完全图：具有n (n-1)条边的有向图；无向完全图：具有n (n-1)/2条边的无向圖；

有根图：有一个顶点有路径到达其它顶点的有向图；简单路径：是经过顶点不同的路径；简单回路是开始和终端重合的简单路径； 网絡：是带权的图。

图的存储结构：?邻接矩阵表示法：用一个n阶方阵来表示图的结构是唯一的适合稠密图。 ?无向图：邻接矩阵是对称嘚