国家二级VB机试（公共基础知识）模拟试卷12
选择题
1.下列叙述中正确的是( )。(A)
A. 非线性结构可以为空
B. 只有一个根结点和一个叶子结点的必定是线性结构
C. 只有一个根结点的必定是线性结构或二叉树
D. 没有根结点的一定是非线性结构
解析：如果一个非空的数据结构满足下列两个条件：
①有且只有一个根结点；
②每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。
如果一个数据结构不是线性结构，则称之为非线性结构。线性结构和非线性结构都可以是空的数据结构。树只有一个根结点，但不论有几个叶子结点，树都是非线性结构。
2.下列叙述中正确的是( )。(B)
A. 能采用顺序存储的必定是线性结构
B. 所有的线性结构都可以采用顺序存储结构
C. 具有两个以上指针的链表必定是非线性结构
D. 循环队列是队列的链式存储结构
解析：所有的线性结构都可以用数组保存，即都可以采用顺序存储结构。而反过来不可以，完全二叉树也能用数组保存(按层次依次存放到数据元素中)，但完全二叉树属于非线性结构。双向链表具有两个以上的指针，但属于线性结构。循环队列是队列的顺序存储结构。
3.下列处理中与队列有关的是( )。(B)
A. 二叉树的遍历
B. 操作系统中的作业调度
C. 执行程序中的过程调用
D. 执行程序中的循环控制
解析：队列是指允许在一端进行插入，而在另一端进行删除的线性表。由于最先进入队列的元素将最先出队，所以队列具有“先进先出”的特性，体现了“先来先服务”的原则。操作系统中的作业调度是指根据一定信息，按照一定的算法，从外存的后备队列中选取某些作业调入内存分配资源并将新创建的进程插入就绪队列的过程。
4.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有( )。(B)
A. 节省存储空间
B. 插入与删除运算效率高
C. 便于查找
D. 排序时减少元素的比较次数
解析：线性表的顺序存储结构称为顺序表，线性表的链式存储结构称为链表，两者的优缺点如下表所示。
5.某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为( )。(B)
A. 0
B. 1
C. 20
D. 不确定
解析：带链的栈就是用一个单链表来表示的栈，栈中的每一个元素对应链表中的一个结点。栈为空时，头指针和尾指针都为NULL；栈中只有一个元素时，头指针和尾指针都指向这个元素。
6.某棵树中共有25个结点，且只有度为3的结点和叶子结点，其中叶子结点有7个，则该树中度为3的结点数为( )。(D)
A. 6
B. 7
C. 8
D. 不存在这样的树
解析：根据题意，树中只有度为3的结点和叶子结点(7个)，则度为3的结点有25-7=18个；又根据树中的结点数=树中所有结点的度之和+1，设度为3的结点数为n，则3n+1=25，得n=8。两种方式得到的度为3的结点数不同，故不存在这样的树。
7.某完全二叉树共有256个结点，则该完全二叉树的深度为( )。(C)
A. 7
B. 8
C. 9
D. 10
解析：根据完全二叉树的性质：具有n个结点的完全二叉树的深度为[log2n]+1。本题中完全二叉．树共有256个结点，则深度为[log2256]+1=8+1=9。
8.设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则后序序列为( )。(B)
A. JIHGFEDCBA
B. DGHEBIJFCA
C. GHIJDEFBCA
D. ABCDEFGHIJ
解析：二叉树的前序序列为ABDEGHCFU，由于前序遍历首先访问根结点，可以确定该二叉树的根结点是A。再由中序序列为DBGEHACIFJ，可以得到结点D、B、G、E、H位于根结点的左子树上，结点C、I、F、J位于根结点的右子树上。由于中序遍历和后序遍历都是先遍历左子树，故本题后序遍历首先访问D结点；再由后序遍历是最后访问根结点，故本题后序遍历最后访问的结点是根结点A。采用排除法可知，后续序列为DGHEBIJFCA。
9.设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是( )。(B)
A. 前序序列
B. 中序序列
C. 后序序列
D. 前序序列或后序序列
解析：中序遍历的次序是先遍历左子树，再遍历根结点，最后遍历右子树。而在排序二叉树中，左子树结点值＜根结点值≤右子树结点值，要使对排序二叉树的遍历结果为有序序列，只能采用中序遍历。
10.下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是( )。(A)
A. 在顺序存储的线性表中寻找最大项
B. 在顺序存储的线性表中进行顺序查找
C. 在顺序存储的有序表中进行对分查找
D. 在链式存储的有序表中进行查找
解析：寻找最大项，无论如何都要查看所有的数据，与数据原始排列顺序没有多大关系，无所谓最坏情况和最好情况，或者说平均情况与最坏情况下的时间复杂度是相同的。而查找无论是对分查找还是顺序查找，都与要找的数据和原始的数据排列情况有关，最好情况是第1次查看的一个数据恰好是要找的数据，只需要比较1次；如果没有找到再查看下一个数据，直到找到为止，最坏情况下是最后一次查看的数据才是要找的。顺序查找和对分查找在最坏情况下比较次数分别是n和log2n，平均情况则是“1-最坏情况”的平均，因而是不同的。
11.下列序列中不满足堆条件的是( )。(D)
A. (98，95，93，94，89，90，76，80，55，49)
B. (98，95，93，94，89，85，76，64，55，49)
C. (98，95，93，94，89，90，76，64，55，49)
D. (98，95，93，96，89，85，76，64，55，49)
解析：根据堆的定义，n个元素的序列(h1，h2，…hn)，当且仅当h1≤h2且hi≤h2i+1时为小顶堆，当且仅当hi≥h2i且hi≥h2i+1时为大顶堆。D项中，h2=95，h4=96，h2＜h4，但h5=89，h2＞h5，不满足小顶堆和大顶堆条件。
12.下面不属于结构化程序设计原则的是( )。(D)
A. 逐步求精
B. 自顶向下
C. 模块化
本文档预览：3600字符，共10365字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
