数据结构复习知识点

A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 （2） 栈在（ ）中应用。

A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ

（3） 一个递归算法必须包括（）。

A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分

（4） 用链接方式存储的队列，在进行删除运算时（ ）。

A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 （5） 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。

A．仅修改队头指针 B. 仅修改队尾指针

C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改

（6）递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。

A．队列 B．多维数组 C．栈 D. 线性表

（7）栈和队列都是（ ）

A．顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构 2、 应用题

（1）名词解释：栈、队列？

（2）简述顺序存储队列的假溢出的避免方法及队列满和空的条件。

第4章 多维数组和广义表 知识点：

1、多维数组的定义，对于一个多维数据，如何计算里面元素的个数？在存储多维数组时，如果已知首元素的存储地址，如何求数组里面任意元素的存储地址？（注意，行优先、列优先、元素的长度）

2、广义表的概念、表长、深度、表头、表尾；广义表的取表头和取表尾操作；注意，取表头去的是原则取表尾得到的是表，会利用广义表的取表头和取表尾操作分离广义表的原子。 习题： 1、选择题

（1） 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（ ）。供选择的答案：

A. 198 B. 195 C. 197

（2）设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为( )。

A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-1

（3）设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。

A.（i-1）*n+j B.（i-1）*n+j-1 C. i*（j-1） D. j*m+i-1 （4）数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。

A. 55 B. 45 C. 36 D. 16 （5）广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）。 Head(Tail(Head(Tail(Tail(A)))))

A. (g) B. (d) C. c D. d （6） 广义表运算式Tail(((a,b),(c,d)))的操作结果是（ ）。

A. (c,d) B. c,d C. ((c,d)) D. d （7）广义表（（a,b,c,d））的表头是（ ），表尾是（ ）。

A. a B.（） C.（a,b,c,d） D.（b,c,d） 2、填空题

（1）设广义表L=((),()), 则head(L)是(1) ___；tail(L)是(2) __；L的长度是(3) _；深度是 (4)_ _。 （2）已知广义表A=(9,7,( 8,10,(99)),12)，试用求表头和表尾的操作Head( )和Tail( )将原子元素99从A中取出来。

（3）广义表的深度是_ _。

（4）广义表(a,(a,b),d,e,((i,j),k))的长度是 ，深度是 _。

（5）已知广义表LS=(a，(b，c，d)，e),运用head和tail函数取出LS中原子b的运算是_ ____。 （6）广义表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是: _ _ _。

第五章 树形结构 知识点：

1、 树的概念、根、度、兄弟、路径、叶子、孩子、双亲、高度、深度、层数；根据一棵树，能够知道它的度、根节点、叶子结点、深度等；根据树中的某个结点，可以找出它的孩子结点；

2、 二叉树的概念、性质和几种特殊形态的二叉树及其特点：斜树、满二叉树、完全二叉树

3、 二叉树的存储（顺序存储，适合完全二叉树；链式存储） 4、 二叉树的遍历及其应用（先根、中根和后根遍历）

5、 二叉树的双序列生成（先根和中根或者中根和后根生成二叉树）

6、 树和森林的概念、树和森林与二叉树的相互转换方法、以及转换的二叉树的特点，树和森林的遍历

7、 哈弗曼编码的概念和哈弗曼树的构造 题目

1、 选择题

（1）已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )

A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE

（2）设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）

A．5 B．6 C．7 D．8 （3）在下述结论中，正确的是（ ）

①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④

（4）设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）

A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定

（5）若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）

A．9 B．11 C．15 D．不确定

（6）在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个

A．4 B．5 C．6 D．7

（7）设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。

A．M1 B．M1+M2 C．M3 D．M2+M3 （8）具有10个叶结点的二叉树中有（ ）个度为2的结点，

A．8 B．9 C．10 D．ll

（9）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）

A． 250 B． 500 C．254 D．505 E．以上答案都不对 （10）设给定权值总数有n 个，其哈夫曼树的结点总数为( )

A．不确定 B．2n C．2n+1 D．2n-1 （11）有关二叉树下列说法正确的是（ ）

A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2

（12）二叉树的第I层上最多含有结点数为（ ）

A．2I B． 2I-1-1 C． 2I-1 D．2I -1 （13） 一个具有1025个结点的二叉树的高h为（ ）

A．11 B．10 C．11至1025之间 D．10至1024之间

（14）一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点

A．2h B．2h-1 C．2h+1 D．h+1 （15）在一棵高度为k的满二叉树中，结点总数为（ ）

A．2k-1 B．2k C．2k-1 D．?log2k?+1 （16）一棵树高为K的完全二叉树至少有（ ）个结点

A．2k –1 B. 2k-1 –1 C. 2k-1 D. 2k

（17）一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）

A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG

（18）已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。

A．CBEFDA B． FEDCBA C． CBEDFA D．不定 （19）某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是：（ ）

A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不对

（20）二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是： （ ）

A、 E B、 F C、 G D、 H 2、 填空题

（1）二叉树由_(1) __，__(2) _，_(3) __三个基本单元组成。 （2）具有256个结点的完全二叉树的深度为______。

（3）深度为k的完全二叉树至少有___(1) ___个结点，至多有___(2) ____个结点。

（4）深度为H 的完全二叉树至少有_(1) ___个结点；至多有_(2) ___个结点；H和结点总数N之间的关系是 (3)。

（5）假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是__ __。 （6）在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =__ ____

（7）高度为K的完全二叉树至少有_____个叶子结点。 （8）高度为8的完全二叉树至少有_____个叶子结点。

（9）已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______。 （10）层完全二叉树至少有_____个结点，拥有100个结点的完全二叉树的最大层数为______。

3、 应用题

（1）树所有结点的度数之和与结点数有何关系？与边数有何关系？二叉树（或者树中），度为0的结点数与度不为0的结点树有何关系？ （2）已知一棵二叉树的对称序和后序序列如下：

中序：GLDHBEIACJFK 后序： LGHDIEBJKFCA (1) 出这棵二叉树，并写出该二叉树的先序序列：

(2) 写出这棵二叉树的根节点、叶子节点、度为1的节点、度为2的节点 (3) 转换为对应的森林：

（3）从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。

（4）二叉树的遍历算法及其应用，如求叶子结点数、度为1的结点数、度为2的结点数，交换二叉树的左右子树、判断两棵二叉树是否等价等。

第6章 图 知识点

1、 图的概念：有向图、无向图、完全图、连通图、强连通图、邻接点、顶点的度、出度、入度、路径

2、 图的存储：有向图和无向图的邻接矩阵存储和邻接表存储，及其特点