2016年山东科技大学测绘科学与工程学院地理信息综合之数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 程序段
其中n 为正整数，则最后一行的语句最坏情况下的时间复杂度是（ ）。
答:D
【解析】这个是冒泡排序，最坏的情况下需要进行
2． 下列选项中，能缩短程序执行时间的措施是（ ）。
I. 提高CPU 时钟频率 II. 优化数据通路结构 III. 对程序进行编译优化 A. 仅I 和II B. 仅I 和III C. 仅II 和III D.I 、II 和III 答:D
【解析】一般说来，CPU 时钟频率（主频）越高，CPU 的速度就越快；优化数据通路结构，可以有效提高计算机系统的吞吐量；编译优化可得到更优的指令序列。所以I 、II 、III 都是有效措施。
3． 图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ）
A.G 的邻接多重表需要n （n-l ）个边结点和n 个顶点结点 B.G 的连通分量个数最少 C.G 为连通图
D.G 所有顶点的度的总和为n （n-1） 答:A
【解析】A 项中G 的邻接多重表中需要n （n-l ）/2个边结点和n 个顶点结点。此时连通分量最少为1。无向完全图中任意两个顶点之间都存在路径，则G 必为连通图。每个顶点的度为n-1，则n 个结点的度的总和为n （n-l ）。
第 2 页，共 46 页
次交换，即时间复杂度是
4． 知一棵二叉树的前序遍历结果为ABCDEF ，中序遍历结果为CBAEDF ，则后序遍历结果为（ ）。
A.CBEFDA B.FEDCBA C.CBEDFA D. 不定
答:A
【解析】由前序结果可知A 为根节点，再由中序遍历结果知BC 为A 的左孩子，且C 为B 的左孩子结点，到此可排除B 项，按照这种逻辑依次推理，便可得出结果对于该类型题目，可以先根据前序遍历结果和中序遍历结果画出二叉树，然后后序遍历二叉树得到后序遍历序列。
5． 每个结点的度或者为0或者为2的二叉树称为正则二叉树。n 个结点的正则二叉树中有（ ）个叶子。
答:D
【解析】二叉树结点总数
分别代表度为0，度为1，度为2的结点数）。
所
以
因
此
又在非空二叉树中
：且本题所给树为正则二叉树
，
6． 下列选项中，不可能是快速排序第2趟排序结果的是（ ）
A.2, 3, 5, 4, 6, 7, 9 B.2, 7, 5, 6, 4, 3, 9 C.3, 2, 5, 4, 7, 6, 9 D.4, 2, 3, 5, 7, 6, 9
答:C
【解析】对于快速排序，每一趟都会使一个元素位于有序时的位置，而有序序列为2, 3, 4, 5, 6, 7, 9, 与C 进行对比，只有9位于它有序的时候的位置，显然不是第二趟快速排序的结果
7． 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3, 当从队列中删除一个元素，再加入两个元素后，rear ，front 的值分别为多少？（ ）
A.1和5 B.2和4 C.4和2 D.5和1 答:B
【解析】入队操作的主要步骤
：个后
，
加入一个后，
第 3 页，共 46 页
再加入一
删除一个后，
出队操作的主要步骤
：
8． 用有向无环图描述表达式（A+B）*（，至少需要顶点的数目为（ ）（A+B）/A）。
A.5 B.6 C.8 D.9 答:A 6条边【解析】一共5个结点
9． 串是一种特殊的线性表，其特殊性体现在（ ）。
A. 数据元素是一个字符 B. 可以顺序存储
C. 数据元素可以是多个字符 D. 可以链接存储 答:A
10．在支持多线程的系统中，进程P 创建的若干个线程不能共享的是（ ）。
A. 进程P 的代码段 B. 进程P 中打开的文件 C. 进程P 的全局变量 D. 进程P 中某线程的栈指针 答:D
【解析】现代操作系统中，进程是资源分配的基本单位，线程是处理机调度的基本单位。因此，进程是线程运行的容器，本题中，进程的代码段，进程打开的文件，进程的全局变量等都是进程的资源，唯有进程中某线程的栈指针是属于线程的，那么，属于进程的资源可以共享，属于线程的栈是独享的，不能共享。
二、填空题
11．对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
答:（1）
置空链表，然后将原链表结点逐个插入到有序表中
第 4 页，共 46 页
相关内容
相关标签