全真试题（六）
一、填空题（每空1分，共15分）
1 数据元素之间有四种基本结构，它们是集合,结构,结构和网状结构。
2 算法的时间度量用 表示，算法的存储空间度量用 表示。
3 每个单线性链表的存取必须从 开始进行。
4 在单链表中，若P和S是两个指针，且满足P->next与S相同，则语句P->next=S->next作用是 S指向的结点。
5 栈的实现有两种存储结构，它们是 结构和 结构。
6 在PASCAL语言中，多维数组在内存中按 为主排列；而在FORTRAN语言中，多维数组按 为主排列。
7 树中结点的 称为树的深度。
8 二叉树的第k层上至多有 个结点。
9 在图的邻接表存储结构中，对图的每一个顶点都建立一个 。
10 在n个元素的有序表中，折半查找给定值至多比较 次，平均查找长度为 。
二、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内，每小题的1分，共10分）
1,若线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，那么采用哪种存储方式最省时间？ ( )
A,单链表 B,仅有头指针的单循环链表
C,仅有尾指针的单循环链表 D,双链表
2,利用两个队列，设输入序列为A，B，C，D，E，则下面哪种排列不可能得到？ ( )
A,EDCBA B,ABCDE C,EABCD D,CABDE
3,哈夫曼树的带权路径长度是什么? ( )
A,所有结点权值之和 B,所有叶结点带权路径长度之和
C,权结点的值 D,除根以外所有结点权值之和
4,已给如下二叉树，按先序遍历的结果是什么? ( )
A,12354
B,12345
C,21435
D,24531
5,队列和栈都是什么结构? ( )
A,顺序存储的线性结构 B,链式存储的线性结构
C,限制存储结点的线性结构 D,限制存储结点的非线性结构
6,设有一棵22个结点的完全二叉树，那么整棵二叉树有多少个度为0的结点? ( )
A．6 B.7 C.8 D.11
7,在有向图的邻接表表示中，下面哪一种操作最费时间? ( )
A,求某顶点的出度 B,求某顶点的入度
C,求图中顶点的个数 D,求从某顶点出发的弧
８,设在二叉排序树上要删除P指向的节点，且设f指向P的父结点，P为f的左孩子,P结点只有左子树,无右子树,那么应做的操作是什么？ ( )
A f->lchild=null B,f->lchild=p->lchild
C.f->lchild=p->rchild D,都不是
９,在下列排序方法中，在最好情况下，时间复杂度为O(n)的算法是哪一个？ ( )
A,简单选择排序 B.直接插入排序 C.冒泡排序 D.都不是
10 在下列方法中，排序所花时间不受初始数据排列特征影响的算法是哪一个？ ( )
A.直接插入排序 B,简单选择排序 C,快速排序 D.都不是三、简释名词（小题3分，共15分）
1.串
2.广义表
3.连通图的生成树
4.哈希表中的二次聚集
5.记录的逻辑结构四、简答题（每小题的5分，共30分）
1.设有一个三维数组a[C1：d1，C2：d2，C3：d3]，其中Ci：di是第i维的界偶，若该数组在内存中按行排列，且a[C1，C2，C3]在内存中的地址为a0，写出任一下标变量a[i1，i2，i3]的地址。设数组的每个元素占?个单元。
2.设通信中出现5种字符，它们是A，B，C，D，E，出现的频率分别为0.2,0.1,0.3,0.15,0.25。构造其哈夫曼树，并对字符编码。
3.已给一个有向图的邻接表如下：
要求:画出该有向图，并写出3种拓扑排序。
4．已给关键字序列为{13,24,37,90,53}，画出每插入一个关键后所建立的二叉平衡树。
5．已给如下一个序列:
{49,38,65,97,76,13,27,49,55,4},用希尔排序(shell)，写出每趟排序的结果（增量依次取5，3，1）。
6．已给有向图
利用迪杰特拉算法（Dijkstra），,求V0到各顶点的最短距离和路线，即填写如下表格。
终点
从V0到各终点的dist值和最短距离
V1
V2
V3
V4
V5
五、综合题（用类C语言写出下列各题的算法，每小题10分，共30分）
1.已给单链表的头指针为H，每个节点的数据域data为整型，指针域为next，设计一个算法inserta(H,d)，实现:
若D已在链表H中，则输出“已存在”，然后返回；否则将d插在链表的最后。
2,设二叉树用二叉链表表示，各结点的结构为,其中data为整型字
段。设计一个算法，打印出其中data值为正偶数的结点值。要求每个结点不能比孩子结点先打印。
已给有向图，用邻接表表示。写出这种表示的数据结构，并设计一个算法，打印某一个顶点的入度。
一、填空题（每空1分，共15分）
1 数据元素之间有四种基本结构，它们是集合,结构,结构和网状结构。
2 算法的时间度量用 表示，算法的存储空间度量用 表示。
3 每个单线性链表的存取必须从 开始进行。
4 在单链表中，若P和S是两个指针，且满足P->next与S相同，则语句P->next=S->next作用是 S指向的结点。
5 栈的实现有两种存储结构，它们是 结构和 结构。
6 在PASCAL语言中，多维数组在内存中按 为主排列；而在FORTRAN语言中，多维数组按 为主排列。
7 树中结点的 称为树的深度。
8 二叉树的第k层上至多有 个结点。
9 在图的邻接表存储结构中，对图的每一个顶点都建立一个 。
10 在n个元素的有序表中，折半查找给定值至多比较 次，平均查找长度为 。
二、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内，每小题的1分，共10分）
1,若线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，那么采用哪种存储方式最省时间？ ( )
A,单链表 B,仅有头指针的单循环链表
C,仅有尾指针的单循环链表 D,双链表
2,利用两个队列，设输入序列为A，B，C，D，E，则下面哪种排列不可能得到？ ( )
A,EDCBA B,ABCDE C,EABCD D,CABDE
3,哈夫曼树的带权路径长度是什么? ( )
A,所有结点权值之和 B,所有叶结点带权路径长度之和
C,权结点的值 D,除根以外所有结点权值之和
4,已给如下二叉树，按先序遍历的结果是什么? ( )
A,12354
B,12345
C,21435
D,24531
5,队列和栈都是什么结构? ( )
A,顺序存储的线性结构 B,链式存储的线性结构
C,限制存储结点的线性结构 D,限制存储结点的非线性结构
6,设有一棵22个结点的完全二叉树，那么整棵二叉树有多少个度为0的结点? ( )
A．6 B.7 C.8 D.11
7,在有向图的邻接表表示中，下面哪一种操作最费时间? ( )
A,求某顶点的出度 B,求某顶点的入度
C,求图中顶点的个数 D,求从某顶点出发的弧
８,设在二叉排序树上要删除P指向的节点，且设f指向P的父结点，P为f的左孩子,P结点只有左子树,无右子树,那么应做的操作是什么？ ( )
A f->lchild=null B,f->lchild=p->lchild
C.f->lchild=p->rchild D,都不是
９,在下列排序方法中，在最好情况下，时间复杂度为O(n)的算法是哪一个？ ( )
A,简单选择排序 B.直接插入排序 C.冒泡排序 D.都不是
10 在下列方法中，排序所花时间不受初始数据排列特征影响的算法是哪一个？ ( )
A.直接插入排序 B,简单选择排序 C,快速排序 D.都不是三、简释名词（小题3分，共15分）
1.串
2.广义表
3.连通图的生成树
4.哈希表中的二次聚集
5.记录的逻辑结构四、简答题（每小题的5分，共30分）
1.设有一个三维数组a[C1：d1，C2：d2，C3：d3]，其中Ci：di是第i维的界偶，若该数组在内存中按行排列，且a[C1，C2，C3]在内存中的地址为a0，写出任一下标变量a[i1，i2，i3]的地址。设数组的每个元素占?个单元。
2.设通信中出现5种字符，它们是A，B，C，D，E，出现的频率分别为0.2,0.1,0.3,0.15,0.25。构造其哈夫曼树，并对字符编码。
3.已给一个有向图的邻接表如下：
要求:画出该有向图，并写出3种拓扑排序。
4．已给关键字序列为{13,24,37,90,53}，画出每插入一个关键后所建立的二叉平衡树。
5．已给如下一个序列:
{49,38,65,97,76,13,27,49,55,4},用希尔排序(shell)，写出每趟排序的结果（增量依次取5，3，1）。
6．已给有向图
利用迪杰特拉算法（Dijkstra），,求V0到各顶点的最短距离和路线，即填写如下表格。
终点
从V0到各终点的dist值和最短距离
V1
V2
V3
V4
V5
五、综合题（用类C语言写出下列各题的算法，每小题10分，共30分）
1.已给单链表的头指针为H，每个节点的数据域data为整型，指针域为next，设计一个算法inserta(H,d)，实现:
若D已在链表H中，则输出“已存在”，然后返回；否则将d插在链表的最后。
2,设二叉树用二叉链表表示，各结点的结构为,其中data为整型字
段。设计一个算法，打印出其中data值为正偶数的结点值。要求每个结点不能比孩子结点先打印。
已给有向图，用邻接表表示。写出这种表示的数据结构，并设计一个算法，打印某一个顶点的入度。
