全真试题(六) 填空题(每空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 ABCDE C. EABCD D. CABDE 3.哈夫曼树的带权路径长度是什么? A.所有结点权值之和 所有叶结点带权路径长度之和 C.权结点的值 D.除根以外所有结点权值之和 4.已给如下二叉树,按先序遍历的结果是什么? A.12354 B.12345 C.21435 D.24531 5.队列和栈都是什么结构 A.顺序存储的线性结构 B.链式存储的线性结构 C.限制存储结点的线性结构D.限制存储结点的非线性结构 6.设有一棵22个结点的完全二叉树,那么整棵二叉树有多少个度为0的结点? B.7 C.8 D.11 7.在有向图的邻接表表示中,下面哪一种操作最费时间? A.求某顶点的出度 B.求某顶点的入度 C.求图中顶点的个数D.求从某顶点出发的弧 8.设在二叉排序树上要删除P指向的节点,且设f指向P的父结点,P为f的左孩子,P结点只有左子树,无右 子树,那么应做的操作是什么? A f->lchild=null B. f->lchild=p->lchild C. f->lchild=p->rchild D.都不是 9.在下列排序方法中,在最好情况下,时间复杂度为0(n)的算法是哪一个? A.简单选择排序B.直接插入排序 C.冒泡排序 D.都不是
全真试题（六） 一、填空题（每空 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.都不是 1 2 3 4 5
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]在内存中的地址为a,写出任一下标变量a[i1,i2,i3]的地址。设数组的每个元素占C 个单元 2.设通信中出现5种字符,它们是A,B,C,D,E,出现的频率分别为0.2,0.1,0.3,0.15,0.25。构造其哈 夫曼树,并对字符编码。 3.已给一个有向图的邻接表如下 3 A 2 A 456 A 要求:画出该有向图,并写出3种拓扑排序。 4.已给关键字序列为{13,24,37,90,53},画出每插入一个关键后所建立的二叉平衡树 5.已给如下一个序列 {49,38,65,97,76,13,27,49,55,4},用希尔排序(shel1),写出每趟排序的结果(增量依次取5,3,1)。 6.已给有向图 100 利用迪杰特拉算法( Dijkstra),,求Ⅶ0到各顶点的最短距离和路线,即填写如下表格 点 从V0到各终点的dist值和最短距离
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 值和最短距离 1 2 3 4 5 6 4 3 5 2 2 5 6 5 Λ Λ Λ Λ Λ Λ V5 V0 V1 V2 V4 V3 10 5 50 20 30 60 100
v2 V3 五、综合题(用类C语言写出下列各题的算法,每小题10分,共30分) 1.已给单链表的头指针为H,每个节点的数据域data为整型,指针域为next,设计一个算法 inserta(H,d), 实现 若D已在链表H中,则输出“已存在”,然后 2.设二叉树用二又链表表示,各结点的结构为1c data 其中data为整型字 段。设计一个算法,打印出其中data值为正偶数的结点值。要求每个结点不能比孩子结点先打印 3.已给有向图,用邻接表表示。写出这种表示的数据结构,并设计一个算法,打印某一个顶点的入度 rc
V1 V2 V3 V4 V5 五、综合题（用类 C 语言写出下列各题的算法，每小题 10 分，共 30 分） 1.已给单链表的头指针为 H，每个节点的数据域 data 为整型，指针域为 next，设计一个算法 inserta(H,d)， 实现: 若 D 已在链表 H 中，则输出“已存在”，然后返回；否则将 d 插在链表的最后。 2. 设二叉树用二叉链表表示，各结点的结构为 ，其中 data 为整型字 段。设计一个算法，打印出其中 data 值为正偶数的结点值。要求每个结点不能比孩子结点先打印。 3． 已给有向图，用邻接表表示。写出这种表示的数据结构，并设计一个算法，打印某一个顶点的入度。 lc lc rc lc data rc