下载文档原格式
数据结构笔试复习⼀选择题1．下述哪⼀条是顺序存储结构的优点？（）A．存储密度⼤ B．插⼊运算⽅便 C．删除运算⽅便 D．可⽅便地⽤于各种逻辑结构的存储表⽰2.数据结构在计算机内存中的表⽰是指( ）。
A. 数据的物理结构B. 数据结构C. 数据的逻辑结构D. 数据元素之间的关系3．下⾯关于线性表的叙述中，错误的是哪⼀个？（）A．线性表采⽤顺序存储，必须占⽤⼀⽚连续的存储单元。
B．线性表采⽤顺序存储，便于进⾏插⼊和删除操作。
C．线性表采⽤链接存储，不必占⽤⼀⽚连续的存储单元。
D．线性表采⽤链接存储，便于插⼊和删除操作。
4.若线性表最常⽤的操作是存取第i个元素及其前驱的值，则采⽤( ）存储⽅式节省时间。
A. 单链表B. 双向链表C. 循环链表D. 顺序表5．线性表是具有n 个（）的有限序列（n>0）。
A．表元素 B．字符 C．数据元素 D．数据项 E．信息项6．若某线性表最常⽤的操作是存取任⼀指定序号的元素和在最后进⾏插⼊和删除运算，则利⽤（）存储⽅式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表7．某线性表中最常⽤的操作是在最后⼀个元素之后插⼊⼀个元素和删除第⼀个元素，则采⽤（）存储⽅式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表8．设⼀个链表最常⽤的操作是在末尾插⼊结点和删除尾结点，则选⽤( )最节省时间。
A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表9．若某表最常⽤的操作是在最后⼀个结点之后插⼊⼀个结点或删除最后⼀个结点。
则采⽤（）存储⽅式最节省运算时间。
A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表10. 链表不具有的特点是（）A．插⼊、删除不需要移动元素 B．可随机访问任⼀元素C．不必事先估计存储空间 D．所需空间与线性长度成正⽐11、3个结点可构成_____棵不同形态的⼆叉树。
数据结构(一)目录第1章序论 (1)1.1 什么是数据? (1)1.2 什么是数据元素? (1)1.3 什么是数据结构及种类? (1)1.4 数据的逻辑结构 (1)1.5 数据的物理结构 (1)1.6 算法和算法分析 (1)1.7 算法的五个特性 (1)1.8 算法设计的要求 (2)1.9 算法效率的度量 (2)第2章线性表 (3)2.1 线性表举例 (3)2.2 线性表的存储 (4)2.3 线性表-栈 (4)2.4 队列 (4)2.5 双端队列 (6)第3章树和二叉树 (6)3.1 树 (6)3.1.1 树的基本概念 (6)3.1.2 树的常用存储结构 (6)3.1.3 树的遍历 (7)3.2 二叉树 (7)3.2.1 二叉树的基本概念 (7)3.2.2 二叉树与树的区别 (7)3.2.3 树及森林转到二叉树 (7)3.2.4 二叉树的性质 (8)3.2.5 满二叉树 (8)3.2.6 完全二叉树 (8)3.2.7 完全二叉树的性质 (9)3.2.8 二叉树的四种遍历 (9)3.2.9 二叉排序树 (10)3.2.10 平衡二叉树 (11)3.2.11 m阶B-树 (11)3.2.12 最优二叉树 (11)3.2.13 二叉树的存储结构 (12)3.3 广义表 (13)3.4 矩阵的压缩存储 (14)3.4.1 特殊矩阵 (14)3.4.2 压缩存储 (14)第4章历年真题讲解 (15)4.1 2009年上半年 (15)4.2 2009年下半年 (15)4.3 2010年上半年 (15)4.4 2011年上半年 (16)4.5 2011年下半年 (16)4.6 2012年上半年 (17)4.7 2012年下半年 (17)4.8 2013年上半年 (18)4.9 2013年下半年 (18)4.10 2014年上半年 (18)4.11 2014年下半年 (19)4.12 2015年上半年 (19)4.13 2015年下半年 (19)4.14 2016年上半年 (20)第1章序论什么是数据?所有能输入到计算机中并能够被计算机程序处理的符号的总称,它是计算机程序加工的原料。
第5章树和二叉树一、填空题1、指向结点前驱和后继的指针称为线索。
二、判断题1、二叉树是树的特殊形式。
（）2、完全二叉树中，若一个结点没有左孩子，则它必是叶子。
（）3、对于有N个结点的二叉树，其高度为。
（）4、满二叉树一定是完全二叉树，反之未必。
（）5、完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。
（）6、若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。
（）7、不使用递归也可实现二叉树的先序、中序和后序遍历。
（）8、先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。
（）9、赫夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
（）110、在赫夫曼编码中，出现频率相同的字符编码长度也一定相同。
（）三、单项选择题1、把一棵树转换为二叉树后，这棵二叉树的形态是（A）。
A．唯一的Ｂ．有多种C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。
2、由3个结点可以构造出多少种不同的二叉树？（D）A．2 B．3 C．4 D．5解释：五种情况如下：3、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（D）。
A．250 B． 500 C．254 D．501解释：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉树的性质可得B=0或1，又因为C为整数，所以B=0，C=500，A=501，即有501个叶子结点。
4、一个具有1025个结点的二叉树的高h为（C）。
A．11 B．10 C．11至1025之间 D．10至1024之间解释：若每层仅有一个结点，则树高h为1025；且其最小树高为⎣log21025⎦ + 1=11，即h在11至1025之间。
数据结构树的种类树是一种基本的数据结构，用于表示具有层次结构的数据。
它由一组节点组成，其中的每个节点都可以有零个或多个子节点。
树可以有不同的种类，每种种类具有不同的特点和应用场景。
以下是一些常见的树的种类：1. 二叉树（Binary Tree）：二叉树是一种每个节点最多只有两个子节点的树结构。
它可以是空树，或者由一个根节点、左子树和右子树组成。
二叉树具有简单的结构，常用于二分和排序。
2. 二叉树（Binary Search Tree）：二叉树是一种具有以下特点的二叉树：左子树中的所有节点都比根节点小，右子树中的所有节点都比根节点大。
二叉树支持快速的查找、插入和删除操作，并在树中保持有序性。
3. 平衡二叉树（Balanced Binary Tree）：平衡二叉树是一种二叉树，但它在插入和删除节点时会自动调整树的结构以保持树的平衡性。
平衡二叉树的常见实现包括 AVL 树和红黑树，它们可以提供在最坏情况下仍保持对数时间复杂度的查找、插入和删除操作。
4. B树（B-Tree）：B树是一种自平衡的树结构，它具有以下特点：每个节点可以有多个子节点，每个节点中的键值有序排列，并且每个节点中的键值数量有一个上限和下限。
B树通常用于大规模数据的存储和数据库系统。
5. Trie树（Trie Tree）：Trie树，也称为字典树或前缀树，是一种专门用于处理字符串集合的树结构。
Trie树的每个节点都代表一个字符串前缀，通过将字符逐级插入树中，可以高效地完成字符串的和查找操作。
6. 线段树（Segment Tree）：线段树是一种用于处理区间查询问题的树结构。
它将要处理的区间划分为一系列离散的线段，并为每个线段创建一个节点。
线段树可以高效地回答关于区间的统计性质，如区间最小值、区间最大值、区间和等。
7. 堆（Heap）：堆是一种完全二叉树，它具有以下特点：对于每个节点，它的值都大于等于（或小于等于）它的子节点的值。
堆被广泛应用于优先队列、排序算法（如堆排序）以及图算法中。
《数据结构》期末复习题及参考答案 - 第6章 树和二叉树一、 选择题1、在二叉树的第I 层(I≥1)上最多含有结点数为（ ）A. 2IB. 2I-1-1C. 2I-1D. 2I -12、深度为6的二叉树最多有( )个结点A ．64 B.63 C.32 D.313、一棵树高为K 的完全二叉树至少有( )个结点A.2k –1B.2k-1 –1C.2k-1D.2 k4、有关二叉树下列说法正确的是（ ）A. 二叉树的度为2B. 一棵二叉树的度可以小于2C. 二叉树中至少有一个结点的度为2D. 二叉树中任何一个结点的度都为25、n 个结点的线索二叉树上含有的线索数为（ ）A. 2nB. n －lC. n ＋lD. n6、线性表和树的结构区别在于（ ）A ．前驱数量不同，后继数量相同B ．前驱数量相同，后继数量不同C ．前驱和后继的数量都相同D ．前驱和后继的数量都不同7、已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，则其前缀形式为( )A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE8、设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（ ）A. A*B+C/(D*E)+(F-G)B. (A*B+C)/(D*E)+(F-G)9、一棵具有 n 个结点的完全二叉树的树高度（深度）(符号⎣⎦x 表示取不大于x 的最大整数)是（ ）10、利用二叉链表存储树，则根结点的右指针是（）。
11、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）。
12、某二叉树中序序列为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．上面的都不对13、若前序遍历二叉树的结果为序列A、B、C，则有_________棵不同的二叉树可以得到这一结果。
二叉树的顺序存储结构代码二叉树的顺序存储结构代码一、前言二叉树是一种重要的数据结构，常用于实现搜索、排序等算法。
在实际应用中，为了方便对二叉树进行操作，需要将其存储在计算机中。
本文介绍了二叉树的顺序存储结构代码。
二、二叉树的顺序存储结构1. 定义二叉树的顺序存储结构是指将二叉树中所有节点按照层次遍历的顺序依次存储到一个数组中。
2. 实现方法（1）计算数组长度：由于一个深度为k的满二叉树共有2^k-1个节点，因此可以通过计算出给定深度k下最多可能存在的节点数来确定数组长度。
（2）按层次遍历顺序存储节点：从根节点开始，按照从左到右、从上到下的顺序依次将每个节点存入数组中。
如果某个节点为空，则在数组中用特定符号表示。
3. 代码实现以下是C++语言实现的二叉树顺序存储结构代码：```#include <iostream>#include <cmath>using namespace std;#define MAXSIZE 1000 // 数组最大长度#define EMPTY '#' // 空节点标记// 二叉树结点struct TreeNode {char value; // 结点值};// 二叉树顺序存储结构class SeqBinaryTree {private:TreeNode nodes[MAXSIZE]; // 存储结点的数组int depth; // 树的深度public:SeqBinaryTree(char *values, int len) { // values为层次遍历序列，len为序列长度depth = ceil(log2(len+1)); // 计算树的深度for (int i = 0; i < MAXSIZE; i++) { // 初始化数组nodes[i].value = EMPTY;}for (int i = 0; i < len; i++) { // 将节点按层次遍历顺序存入数组中nodes[i].value = values[i];}}void print() { // 输出二叉树中所有结点值for (int i = 0; i < pow(2,depth)-1; i++) {if (nodes[i].value != EMPTY) {cout << nodes[i].value << " ";}}}};// 测试代码int main() {char values[] = {'A','B','C','#','#','D','E'};SeqBinaryTree tree(values,7);tree.print(); // 输出结果：A B C # # D E}```三、总结本文介绍了二叉树的顺序存储结构代码实现方法，该方法可以方便地对二叉树进行操作。
