只给了选择题答案，其他在课上已讲。
数据结构复习题。
一、 名词解释：
1、 单链表：
2、 循环链表。
3、 栈。4、 队列。
5、 存储结构：
6、 数据结构。
7、 结点的度：
8、 树的度。
9、 深度优先：
10、广度优先。
二、填空：1.**性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为。
2. 数据的逻辑结构被分为集合结构和。
3. 下面程序段的时间复杂度为。
for(int i=1;i for(int j=1;i a[i][j]=i*j;
4. 广义表l=（a，（b，( 的深度为。
5．任意一棵完全二叉树中，度为1的结点数最多为。
6. 如图所示，该图的拓扑序列是第6题。
7. 图的遍历有深度优先遍历和。
8. 在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比较次数为。
9. 一个算法的效率可分为空间效率和效率。
10. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 __个元素。
11. 在栈的存储结构中，判断栈空的条件是。
1. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。
typedef struct sqstack;
void push(sqstack &stack,int x)
if ( printf(“overflow”);
else12.中序遍历二叉排序树所得到的序列是序列（填有序或无序）。
13.快速排序的最坏时间复杂度为平均时间复杂度为。
14.设某棵二叉树中度数为0的结点数为n0，度数为1的结点数为n1，则该二叉树中度数为2的结点数为若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有___个空指针域。
15.设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=__
16.设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为。
17.已知一有向图的邻接表存储结构如下：从顶点1出发，dfs遍历的输出序列是。
bfs遍历的输出序列是。
18. 在具有n个单元的循环队列中，队满时共有 n 个元素。
19. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶 。不允许插入和删除运算的一端称为栈底。
20. 设输入序列为，则经过栈的作用后可以得到___5___种不同的输出序列。
21. 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为___i/2右孩子结点的编号为___i+1___
21. for(i=1，t=1，s=0；i<=n；i++)的时间复杂度为。
三、画图及计算题。
1.已知下图，用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。
2.给出初始排序码序序列为：49,38,65,97,49,13,27,76写出直接选择排序算法的各趟运行结果。
3. 下图所示的森林：
1) 求树（a）的先根序列和后根序列；
2）将此森林转换为相应的二叉树；
4.已知叶结点权值集合为：，要求给出哈夫曼树，并计算其带权路径长度wpl。
5.请画出下图的邻接表存储表示。
6.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。
7.试分别画出具有3个结点的二叉树所有的不同形态。
8．已知一棵二叉树的中序序列和后序序列分别为bdceafhg和decbhgfa，画出这棵二叉树，并写出该树的前序序列。
9.已知叶结点权值集合为：，要求给出哈夫曼树，并计算其带权路径长度wpl。
10．根据关键字，生成最大堆。要求写出生成过程。
11. 已知二叉树的中序序列和后序序列均为abcdef，则该二叉树的先序序列？要求画出二叉树。
12. 已知关键字集合：，用快速排序从小到大排序。
13. 根据下图，画出下列树对应的二叉树并对其进行中序遍历。
14. 根据第5题，写出该二叉树的前序线索二叉树。
15. 已知如图所示，请给出该图的邻接表存储结构。
16．根据上图，写出该图的最小生成树。要求写出过程。
四、程序设计。
1、实现冒泡算法排序。
五、看程序写结果。
1．写出下列程序段的输出结果（队列中的元素类型qelem type为char）。
void main( )
printf(x);
结果。六、选择。
1. 树最适合用来表示( c )。
a.有序数据元素b.无序数据元素。
c.元素之间具有分支层次关系的数据 d.元素之间无联系的数据。
2. 在一个单链表hl中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（ d ）。
a．q->next=p->next；p->next=q;
b．p->next=q->next；q=p；
c．q->next=p->next；p->next=q；
d．p->next=q->next；q->next=p；
3. 以下数据结构中哪一个是非线性结构？( d)
a. 队列 b. 栈 c. 线性表 d. 二叉树。
4.下面关于线性表的叙述错误的是（ d ）。
a. 线性表采用顺序存储必须占用一片连续的存储空间b．线性表采用链式存储不必占用一片连续的存储空间。
c．线性表采用链式存储便于插入和删除操作的实现。
d．线性表采用顺序存储便于插入和删除操作的实现。
5．假设以数组a［n］存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为（ ）
a．rear= =front b．(front+1)％n= =rear
c．rear+1= =front d．(rear+1)％n= =front
6. 设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主存储，a11为第一个数据元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（ b ）。
a．13 b．33 c．18 d．40
7. 若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是（ b ）
a．3 b．5
c．6 d．7
8．对广义表l= (a，()执行操作tail(l)的结果是（ b ）
a．()b．((
c．a d．(a)
9．在一棵具有35个结点的完全二叉树中，该树的深度为（ c ）。
a．6 b．7 c．5d．8
10．线索二叉树中某个结点没有孩子的充要条件是（ d ）。
a． b．c．以上答案都不对。
11．串的长度是（ d ）。
a．串中不同字母的个数b．串中不同字符的个数。
c．串中所含字符的个数，且大于0 d．串中所含字符的个数。
12．在一个具有n个顶点的无向完全图中，所含的边数为（c ）。
a．n b．n(n-1) c．n(n-1)/2 d．n(n+1)/2
13．在对n个元素进行直接选择排序的过程中，需要进行（ c ）趟选择和交换。
a．n b．n+1c．n-1d．n/2
14．串是（ d ）。
a．少于一个字母的序列c．不少于一个字符的序列。
b．任意个字母的序列d．有限个字符的序。
数据结构复习提纲
软件学院数据结构与算法复习提纲。data structures and algorithms 概念 type,类型 一组值的集合。type,简单类型例如整数，因为它的值不含有子结构。aggregate type,复杂类型，一个记录含有多项信息。银行账户含有多项信息如姓名 地址 composite t...
数据结构复习提纲
第一章概论 1 数据结构的基本概念和术语。数据 数据元素 数据项 数据对象 数据结构等基本概念。数据结构的逻辑结构，存储结构及数据运算的含义及其相互关系。数据结构的四种逻辑结构及四种常用的存储表示方法。第二章算法分析技术。1 算法的描述和分析。无穷大阶的几种描述方法的区别。算法 算法的时间复杂度和空...
数据结构复习提纲
第一部分试题说明。1 试卷考试时间为90分钟。2 试题类型 选择题 20个，每题2分，共40分 简答题 6个，每题5分，共30分 和算法设计题 2个，每题15分，共30分 第二部分各章知识点。第1章绪论。1 数据结构的概念。2 数据结构的形式化表示方法 ds d，r 要求给定一个形式化表示，能够画出...