全真试题(六) 填空题(每空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