下载文档原格式
数据结构考试题目和答案一、单项选择题1. 在数据结构中，线性结构和非线性结构的区别在于（）。
A. 结构中元素的个数B. 结构中是否包含子结构C. 结构中元素之间是否有一对一的对应关系D. 结构中元素之间是否有层次关系答案：D2. 一个栈的入栈序列为1, 2, 3, 4, 5，则可能的出栈序列为（）。
A. 4, 3, 2, 5, 1B. 5, 4, 3, 2, 1C. 5, 4, 3, 1, 2D. 1, 2, 3, 4, 5答案：B3. 在二叉树中，度为2的节点数为n，度为1的节点数为m，度为0的节点数为p，则m的值为（）。
A. nB. n-1C. p-1D. p+1答案：B4. 哈希表的冲突解决方法中，开放定址法和链地址法的主要区别在于（）。
A. 是否使用链表B. 是否使用数组C. 是否使用额外的存储空间D. 是否使用线性探测答案：C5. 对于一个无向图，其邻接矩阵表示法中，矩阵的行数和列数分别为（）。
A. 顶点数和边数B. 顶点数和顶点数C. 边数和边数D. 边数和顶点数答案：B二、填空题1. 在顺序表中，插入一个元素平均需要移动元素的个数为表长减1，即 _______ 。
答案：n-12. 快速排序算法的时间复杂度为 _______ 。
答案：O(n^2)3. 折半查找法的平均查找长度为 _______ 。
答案：O(log n)4. 在图的遍历中，深度优先搜索（DFS）使用的栈是_______ 。
答案：非必需的5. 一个完全二叉树有15个度为2的节点，则该树的叶子节点数为 _______ 。
答案：16三、简答题1. 什么是二叉搜索树？请简述其特点。
答案：二叉搜索树是一种特殊的二叉树，其中每个节点的值都大于其左子树中所有节点的值，并且小于其右子树中所有节点的值。
其特点包括：- 每个节点的左子树只包含小于节点值的节点。
- 每个节点的右子树只包含大于节点值的节点。
- 左子树和右子树也必须是二叉搜索树。
数据结构自测题及答案**数据结构自测题及答案**一、选择题（每题2分，共10分）1. 数据结构是一种用于组织和管理数据的方式，它主要关注的是：A. 数据的存储和表示方式B. 数据的输入和输出方式C. 算法和数据的交互方式D. 数据处理的速度和效率2. 在数据结构中，数组是一种：A. 线性结构B. 树形结构C. 图形结构D. 集合结构3. 下列哪种数据结构是先进先出（FIFO）的：A. 栈B. 队列C. 链表D. 哈希表4. 在二叉树中，每个节点最多有几个子节点：A. 0B. 1C. 2D. 35. 下列哪种数据结构适合用于实现图的存储：A. 数组B. 链表C. 堆D. 散列表二、填空题（每题2分，共10分）1. 在栈中，最后一个进入栈的元素最先出栈，这种特点叫做**后进先出**。
2. 哈希表一般是通过**散列函数**将键映射到存储位置上。
3. 图中节点之间的关系可以用**边**来表示。
4. 在二叉搜索树中，左子树的值都小于根节点的值，右子树的值都大于根节点的值，这种特点叫做**二叉搜索树的性质**。
5. 在链表中，每个节点都包含一个指向下一个节点的**指针**。
三、判断题（每题2分，共10分）1. 队列是一种先进先出（FIFO）的数据结构。
（正确）2. 图是一种非线性的数据结构。
（正确）3. 二叉树是一种树形数据结构，每个节点最多有两个子节点。
（正确）4. 栈可以用数组和链表两种方式实现。
（正确）5. 哈希表的插入和查询操作的时间复杂度都为O(1)。
（错误）四、程序设计题（总分20分）请编写一个程序，实现以下功能：1. 定义一个结构体，用于表示学生信息，包含姓名、年龄和成绩三个字段。
2. 动态创建一个长度为5的数组，用于存储学生信息。
3. 通过键盘输入，依次为每个学生的姓名、年龄和成绩赋值，并存储到数组中。
4. 分别计算学生的平均年龄和平均成绩，并输出结果。
代码示例（C语言）：```c#include<stdio.h>#include<stdlib.h>struct Student {char name[20];int age;float score;};int main() {struct Student* students = (struct Student*)malloc(5 * sizeof(struct Student));for (int i = 0; i < 5; i++) {printf("请输入第 %d 个学生的姓名：", i + 1);scanf("%s", students[i].name);printf("请输入第 %d 个学生的年龄：", i + 1);scanf("%d", &students[i].age);printf("请输入第 %d 个学生的成绩：", i + 1);scanf("%f", &students[i].score);printf("\n");}int totalAge = 0;float totalScore = 0.0;for (int i = 0; i < 5; i++) {totalAge += students[i].age;totalScore += students[i].score;}float avgAge = totalAge / 5.0;float avgScore = totalScore / 5.0;printf("平均年龄： %.2f\n", avgAge);printf("平均成绩： %.2f\n", avgScore);free(students);return 0;}```以上就是自测题及答案的全部内容。
数据结构试题及答案(10套)数据结构试题及答案(10套)根据您的需求，我为您准备了10套数据结构试题及答案。
每套试题包含以下几个部分：选择题、填空题、编程题及答案解析。
下面是试题的具体内容：第一套试题：选择题：1. 在数据结构中，什么是栈？A. 先进先出（FIFO）的数据结构B. 后进先出（LIFO）的数据结构C. 随机访问的数据结构D. 无序排列的数据结构2. 以下哪种操作与队列的特性不相符？A. 入队操作B. 出队操作C. 查找操作D. 获取队首元素填空题：1. ______ 是一种动态集合，支持插入、删除和查找等操作。
2. 在二叉搜索树中，中序遍历的结果是________。
编程题：实现一个栈的数据结构，并包含以下操作：- push(x)：将元素 x 压入栈中- pop()：删除栈顶的元素并返回该元素- top()：获取栈顶元素的值- empty()：检查栈是否为空答案解析：选择题：B、C填空题：1. 集合 2. 升序序列编程题：略第二套试题：选择题：1. 以下哪个数据结构是一种广度优先搜索的应用？A. 栈B. 队列C. 堆D. 链表2. 在链表中，如果要删除一个节点，只给出该节点的指针，那么需要通过什么方式完成删除操作？A. 直接删除该节点B. 指向该节点的前一个节点的指针C. 指向该节点的后一个节点的指针D. 无法完成删除操作填空题：1. 树是一种________的数据结构。
2. 二叉树每个节点最多有______个子节点。
编程题：实现一个队列的数据结构，并包含以下操作：- enqueue(x)：将元素 x 入队- dequeue()：删除队首的元素并返回该元素- peek()：获取队首元素的值- is_empty()：检查队列是否为空答案解析：选择题：B、B填空题：1. 分层组织 2. 2编程题：略（以下部分省略）通过以上的题目，您可以对数据结构的知识点进行综合练习和复习。
每套试题包含了不同难度和类型的题目，能够帮助您全面了解和掌握数据结构的概念和操作。
数据结构试卷试题及答案一、选择题（每题5分，共40分）1. 数据结构是研究数据元素的（）A. 存储结构B. 处理方法C. 逻辑结构D. 所有以上内容答案：D2. 在数据结构中，通常采用（）方式来表示数据元素之间的逻辑关系。
A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 散列存储结构答案：B3. 下面哪一个不是栈的基本操作？（）A. 入栈B. 出栈C. 判断栈空D. 获取栈顶元素答案：D4. 下面哪一个不是队列的基本操作？（）A. 入队B. 出队C. 判断队列空D. 获取队头元素答案：D5. 下面哪一个不是线性表的特点？（）A. 有且只有一个根节点B. 每个节点最多有一个前驱和一个后继C. 数据元素类型相同D. 数据元素类型可以不同答案：D6. 在下列哪种情况中，使用链式存储结构比顺序存储结构更合适？（）A. 数据元素经常插入和删除B. 数据元素大小不固定C. 数据元素个数不确定D. 所有以上情况答案：D7. 下面哪一个不是树的遍历方式？（）A. 前序遍历B. 中序遍历C. 后序遍历D. 翻转遍历答案：D8. 在下列哪种情况中，使用散列存储结构比其他存储结构更合适？（）A. 数据元素个数较少B. 数据元素查找频繁C. 数据元素插入和删除频繁D. 数据元素大小不固定答案：B二、填空题（每题5分，共30分）9. 栈是一种特殊的线性表，它的插入和删除操作都限定在表的一端进行，这一端称为______。
答案：栈顶10. 队列是一种特殊的线性表，它的插入操作在表的一端进行，这一端称为______，而删除操作在另一端进行，这一端称为______。
答案：队尾、队头11. 二叉树中的节点包括______和______。
答案：根节点、子节点12. 在图的存储结构中，邻接矩阵表示法用______个一维数组来表示图中各个顶点之间的关系。
答案：两个13. 散列存储结构中，关键码到存储地址的映射方法称为______。
单选题
1.在深度为5的满二叉树中，叶子节点个数为?( C )
A:32 B: 31 C: 16 D:15
2.如果进栈序列为：e1,e2,e3,e4则出栈序列正确的是？（B ）
A: e3，e1，e4，e2
B: e2，e4，e3，e1
C: e3，e4，e1，e2
D: 任意序列
3.数据的__C___包括集合结构、线性结构、树结构和图状结构四个基本类型。
A:算法描述
B:基本运算
C:逻辑结构
D:存储结构
4.数据的存储结构包括：顺序、___D__、索引和散列四个基本类型。
A:向量
B:数组
C:集合
D:链式
5.假设一个栈的输入顺序为：A,B,C,D,E则下列不可能是栈的输出序列的是？（b）
A：BCDAE
B: EDACB
C: BCADE
D: AEDCB
6.线性表的二分法查询的前提条件是？（A）
A:线性表以顺序方式存储，并且按关键码值排好序
B: 线性表以链式方式存储，并且按关键码值排好序
C: 线性表以顺序方式存储, 并且按关键码的检索频率排好序
D: 线性表以链式方式存储, 并且按关键码的检索频率排好序
7.以下四种排序方法，需要附加内存空间最大的是？（D）
A：插入排序
B: 选择排序
C: 快速排序
D: 归并排序
8.在顺序栈中进行退栈操作时，___D___。
A;谁先谁后都可以
B:先移动栈顶指针，后取出元素
C:不分先后，同时进行
D:先取出元素，后移动栈顶指针
填空题
9.稳定的排序方法有：插入派讯、冒泡排序和归并排序。
10.线性链表属于数据结构中的_____存储___结构。
第1章绪论二、填空题1. 4种基本结构是：集合、线性结构、树形结构、图状结构。
2. 树形结构中元素的关系是一对多，图形结构中元素的关系是多对多。
3. 顺序存储结构中数据元素的存储位置与其逻辑顺序是对应的。
4. 算法效率的度量方法有：事后统计方法和事前分析估算方法。
5. 好算法应达到的目标：正确性、可读性、健壮性、执行时间短、存储量低。
6. 抽象数据类型可细分为3种：原子类型、固定聚合类型和可变聚合类型。
7. 抽象数据类型的定义包括：数据对象的定义、数据关系的定义、基本操作的定义。
三、判断题五、应用题1. 按增长率从小到大的顺序排列下列各函数：(2/3)n ，nlog，n ，n2 ，n!22. 写出以下各函数的功能，并求出其时间复杂度。
(1) 功能是判断n是否为素数，时间复杂度为O(√n ) 。
(2) 功能是计算1!+2!+…+n! ，时间复杂度为O(n ) 。
(3) 功能是计算1!+2!+…+n! ，时间复杂度为O(n2 ) 。
六、算法题1. 编写算法计算1!+2!+…+n!，并使算法的时间复杂度为O(n)。
算法思想：用循环实现阶乘的累加求和，注意在求n!时，使用前一次循环中已经求出的(n-1)!的结果。
double factorial(int n){ int i;double p=1, sum=0;for( i=1; i<=n; i++){ p=p*i;sum=sum+p;}return(sum);}2. 编写算法计算2i (i=0,1,2,…,n)，并将计算结果存入数组a中，设计算机中允许的最大整数值为MAXINT，则当2k >MAXINT（0≤k≤n）时，应进行出错处理。
算法思想：先判断n的取值是否合法，若非法则直接退出程序，若n 合法则继续计算2i，在计算2i时，需要判断2i的值是否大于MAXINT/2，这个条件其实就是判断2i+1的值是否大于MAXINT#define arrsize 100#define MAXINT 65535void calculate(int a[ ], int n){ int i;if(n<=0 || n>arrsize){ printf("n error!\n");exit(-1);}a[0]=1;printf("a[0]=%d\n", a[0]);for(i=1; i<n; i++){ a[i]=a[i-1]*2;printf("a[%d]=%d\n", i, a[i]);if( a[i]>MAXINT/2 ){ printf(“i=%d, ERROR!\n”, i+1)；break;}}}第2章线性结构一、选择题二、填空题1. 需向后移动__n-i+1____个元素。
一、概念题（每空0.5分，共28分）1．树（及一切树形结构）是一种“________”结构。
在树上，________结点没有直接前趋。
对树上任一结点X来说，X是它的任一子树的根结点惟一的________。
2．由３个结点所构成的二叉树有种形态。
3．一棵深度为6的满二叉树有个分支结点和个叶子。
4．一棵具有２５７个结点的完全二叉树，它的深度为。
5．二叉树第i(i>=1)层上至多有______个结点；深度为k(k>=1)的二叉树至多有______个结点。
6．对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。
7．满二叉树上各层的节点数已达到了二叉树可以容纳的______。
满二叉树也是______二叉树，但反之不然。
8．设一棵完全二叉树有700个结点，则共有个叶子结点。
9.设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。
10.一棵含有n个结点的k叉树，可能达到的最大深度为，最小深度为。
11.二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。
因而二叉树的遍历次序有六种。
最常用的是三种：前序法（即按N L R次序），后序法（即按次序）和中序法（也称对称序法，即按L N R次序）。
这三种方法相互之间有关联。
若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。
12.中序遍历的递归算法平均空间复杂度为。
13.二叉树通常有______存储结构和______存储结构两类存储结构。
14.如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有：（1）若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。
（2）若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。
《数据结构》课程第一章小测验一、判断题：（每题2分，共4分）1、数据元素是数据的最小单位。
F2、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。
F链表的存储中结点之间可以是连续的，也可以是不连续的。
但结点内部是连续的。
答题区二、选择题：（每题2分，共16分）1、线性表是具有n个（）的有限序列。
C（A）表元素（B）字符（C）数据元素（D）数据项2、如果数据结构中每个结点都有一个前驱，则该结构属于（）。
A（A）图状结构（B）树形结构（C）循环结构（D）线性结构3、如果数据结构中每个结点都没有后继，则该结构属于（）。
D（A）独立结构（B）散列结构（C）树形结构（D）非线性结构4、算法的时间复杂度与（）有关。
A（A）问题规模（B）计算机硬件性能（C）编译程序质量（D）程序设计语言5、算法的执行时间一般与（）无关。
D（A）问题规模的大小（B）计算机的档次（C）程序设计语言的种类或版本（D）算法设计者的水平6、算法分析的主要任务是分析（）。
D（A）算法是否具有较好的可读性（B）算法中是否存在语法错误（C）算法的功能是否符合设计要求（D）算法的执行时间和问题规模之间的关系7、某算法的时间复杂度为O（2n），表明该算法的（）。
C（A）问题规模是2n（B）执行时间等于2n（C）执行时间与2n成正比（D）问题规模与2n成正比8、在决定选取何种存储结构时，一般不考虑（）。
A（A）各结点的值如何（B）结点数目的多少（C）对数据有哪些运算（D）所用编程语言实现这种结构是否方便三、填空题：（每空2分，共14分）1、数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。
2、一个算法的效率可分为时间效率和空间效率。
3、线性表是具有n个数据元素有限序列。
四、简答题：（每题10分，共20分）1.数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结合在一起的数据元素。
第一章概论 自测题答案一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。
2. 数据结构被形式地定义为（D, R ），其中D 是 数据元素 的有限集合，R 是D 上的 关系 有限集合。
3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。
4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。
5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
6． 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有1个后续结点。
7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。
8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。
9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列 。
10. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。
11. 一个算法的效率可分为 时间 效率和 空间 效率。
二、单项选择题（ B ）1. 非线性结构是数据元素之间存在一种：A ）一对多关系B ）多对多关系C ）多对一关系D ）一对一关系（ C ）2. 数据结构中，与所使用的计算机无关的是数据的 结构；A) 存储 B) 物理 C) 逻辑 D) 物理和存储（ C ）3. 算法分析的目的是：A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性（ A ）4. 算法分析的两个主要方面是：A) 空间复杂性和时间复杂性 B) 正确性和简明性C) 可读性和文档性 D) 数据复杂性和程序复杂性（ C ）5. 计算机算法指的是：A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法（ B ）6. 计算机算法必须具备输入、输出和 等5个特性。
单项选择题第1题由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )A、48B、51C、63D、72第2题按照二叉树的定义，具有3个结点的二叉树有（）种。
A、3B、4C、5D、6第3题有n个结点的二叉树，采用二叉链表存储，空指针的个数为（）A、n-1B、nC、n+1D、n+2第4题在有n个结点的哈夫曼树中，总的结点个数是（）。
A、nB、2n-1C、2nD、2n+1第5题若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是( )A、9B、10C、11D、12第6题要连通具有n个顶点的有向图，至少需要（）条边。
A、n-1B、nC、n+1D、2n判断题第7题后序序列和中序序列能唯一确定一棵二叉树。
正确错误第8题常用的图的遍历算法包括深度优先搜索和广度优先搜索。
正确错误第9题图G由两个集合V(G)和E(G)所组成，其中顶点集V(G)和边集E(G)都可以为空集。
正确错误第10题图是非线性结构。
正确错误第11题邻接表表示法和邻接矩阵表示法是图的常用的存储方法。
正确错误第12题一个有向无环图的拓扑排序序列是唯一的。
（）正确错误单项选择题第1题下列排序方法中，稳定的是（）A、快速排序B、堆排序C、基数排序D、希尔排序第2题排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。
A、希尔排序B、起泡排序C、直接插入排序D、简单选择排序第3题在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）。
A、直接插入排序B、简单选择排序C、快速排序D、2路归并排序第4题下列排序方法中，稳定的是（）A、快速排序B、堆排序C、希尔排序D、基数排序第5题衡量查找算法效率的主要标准是（）。
A、元素个数B、所需的存储量C、平均查找长度D、算法难易程度第6题一个排序算法的时间复杂度与（）有关。
A、排序算法的稳定性B、所需比较关键字的次数C、所采用的存储结构D、所需辅助存储空间的大小判断题第7题快速排序并非在任何情况下都比其他排序方法速度快。
数据结构自测题1、算法的计算量的大小称为计算的（）。
A. 效率B. 复杂性C. 现实性D. 难度2、一个算法应该是（）。
A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.3、下面说法错误的是（）（1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B. (1), (2) C. (1), (4) D. (3)4、在数据结构中，从逻辑上可以将之分为（）。
A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C. 内部结构和外部结构D. 线性结构和非线性结构5、计算算法的时间复杂度是属于一种（）。
A. 事前统计的方法B. 事前分析估算的方法C. 事后统计的方法D. 事后分析估算的方法6、可以用（）定义一个完整的数据结构:A. 数据元素B. 数据对象C. 数据关系D. 抽象数据类型7、算法分析的目的是_______。
A. 找出数据结构的合理性B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性8、设计一个“好”的算法应考虑达到的目标有______。
A. 是可行的B. 是健壮的C. 无二义性D. 可读性好线性表1、线性表是具有n个（）的有限序列（n>0）。
A．表元素B．字符C．数据元素D．数据项2、若线性表最常用的操作是存取第I个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。
A.单链表B.双向链表C.单循环链表D.顺序表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．线性表采用链接存储，便于插入和删除操作。
在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构.顺序存储结构的主要优点是节省存储空间，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。
但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。
在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)叫链式存储结构.又叫链接存储结构。
它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点.链式存储结构特点：1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
2、逻辑上相邻的节点物理上不必相邻。
3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。
4、查找结点时链式存储要比顺序存储慢。
5、每个结点是由数据域和指针域组成。
8、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表9、链表不具有的特点是（）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比10、(1) 静态链表既有顺序存储的优点，又有动态链表的优点。
所以，它存取表中第i个元素的时间与i无关。
(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
以上错误的是（）A.(1), (2)B.(1)C.(1),(2), (3)D.(2)11、单链表中，增加一个头结点的目的是为了( ）。
A．使单链表至少有一个结点B．标识表结点中首结点的位置C．方便运算的实现D．说明单链表是线性表的链式存储12、对于双向循环链表,在p指针所指的结点之后插入s指针所指结点的操作应为（）。
A． p->right=s ; s->left=p;p->right->left=s ; s->right=p->right;B． p->right=s ; p->right->left=s ;s->left=p; s->right=p->right;C． s->left=p; s->right=p->right;p->right=s ; p->right->left=s ; ;D． s->left=p; s->right=p->right;p->right->left=s ; p->right=s ;13、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL堆栈和队列1、为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是（）A. 栈B. 队列C. 树D. 图2、设栈S和队列Q的初始状态均为空，元素a,b,c,d,e, f,g依次进入栈S。
若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是（）A. 1B. 2C. 3D. 4习题1、设将整数1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答以下问题：（1）若入栈次序为push(1)，pop()，push(2)，push(3)，pop()，pop()，push(4)，pop( )，则出栈的数字序列为什么？（2）能否得到出栈序列423和432？并说明为什么不能得到或如何得到。
（3）请分析1、2、3、4的24种排列中，哪些序列可以通过相应的入出栈得到。
2、链栈中为何可以不设头指针？3、循环队列的优点是什么？如何判断它的空和满？4、设长度为n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？5、利用栈的基本操作，写一个返回栈s中结点个数的算法int stacksize(seqstack s)，并说明s为何不用作为指针参数？6、利用栈的基本操作，写一个将栈中所有结点均删除算法，并说明S为何要作为指针参数？7、用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个基本操作。
8、假设循环队列只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。
树1、n(n>0)个结点的树的高度:最低是多少？__________________最高是多少？__________________2、n(n>0)个结点的二叉树的高度:最低是多少？__________________最高是多少？__________________3、有关二叉树下列说法正确的是（）A．二叉树的度为2B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为24、已知一棵完全二叉树的第6层（设根是第1层）有8个叶结点，则该完全二叉树的结点个数最多是（）A. 39B. 52C. 111D. 1195、一棵124个叶结点的完全二叉树，最多有( )个结点。
A.247B.248C.249;D.250;E.2516、已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。
A. 311B. 312C. 313D. 3147、一个具有1025个结点的二叉树的高h为（）A．11B．10C．11至1025之间D．10至1024之间8、一棵树高为K的完全二叉树至少有（）个结点A. 2k –1B. 2k-1 –1C. 2k-1D. 2k9、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_________个叶子结点。
10、•已知二叉树的•先序序列ABDFCEHG•中序序列DBFAHECG•请构造该二叉树。
11、•已知二叉树的•先序序列ABDFCEHG•中序序列DBFAHECG•请构造该二叉树。
12、•一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。
•先序序列为：_ _ C D E _ G H I _ K•中序序列为：C B _ _ F A _ J K I G•后序序列为： _ E F D B _ J I H _ A13、一棵二叉树的先序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。
A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEGB14、一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足( )。
A. 其中任意一个结点均无左孩子B. 其中任意一个结点均无右孩子C. 其中只有一个叶子结点D. 其中度为2的结点最多为一个15、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是( )的二叉树A．空或只有一个结点B. 高度等于其结点数C．任一结点无左孩子D. 任一结点无右孩子16、17、18、按关键字序列15,21,27,43,36,8,11构造平衡二叉树19、LL型调整的两个例子20、二叉查找树的查找效率与二叉树的( （1） )有关, 在 (（2） )时其查找效率最低(1) A. 高度B. 结点的多少C. 树型D. 结点的位置(2) A. 结点太多B. 完全二叉树C. 呈单枝树D. 结点太复杂。
21、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。
