2016年国防科学技术大学计算机学院F0606数据结构与算法复试笔试仿真模拟题
● 摘要
一、选择题
1． 对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（ ）。
A. B. C. D. 【答案】C 。
【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间
为
其中n 为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为
其
中e 为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为即可得出正确答案。
2． 栈和队的共同点是（ ）。
A. 都是先进后出 B. 都是后进先出
C. 只允许在端点处插入和删除元素 D. 没有共同点 【答案】C
【解析】栈和队列的区别是栈是先进后出的数据结构，队列是先进先出的数据结构，栈和队列的共同点是都只能在端点处插入和删除元素。
3． 中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（ ）。
A. 程序计数器 B. 程序状态字寄存器 C. 通用数据寄存器 D. 通用地址寄存器 【答案】B 。
【解析】中断处理与子程序调用最大的区别是中断处理程序与正在运行的进程可能无关，而子程序调用与正在运行的进程有关。中断是要打断处理器的正常工作次序，并要求其去处理某一
事件的一种常用手段。因此，除了要保护当前程序的地址，计数器（指针）和数据寄存器以外，还需要保存程序状态字。子程序调用是与当前进程有关，是正在运行的程序有意安排执行的，这一类调用发生的时间以及位置具有确定性，处于同一个进程内，因此不需要保存程序状态字。所以中断处理和子程序调用不同的区别是中断处理程序必定会保存程序状态字寄存器。
4． —个进程的读磁区操作完成后，操作系统针对该进程必做的是（ ）
A. 修改进程状态为就绪态 B. 降低进程优先级 C. 进程分配用户内存空间 D. 增加进程的时间片大小 【答案】A
【解析】进程等待的操作完成便会从等待状态转移到就绪状态。
5． 以下与数据的存储结构无关的术语是（ ）。
A. 循环队列 B. 链表 C. 哈希表 D. 栈 【答案】D
【解析】循环队列体现线性表是以顺序存储。用散列法存储的线性表称散列表。链表说明线性表是以链式结构存储的。栈不能体现出是顺序还是链式存储结构。
6． 某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int 和short 型长度分别为32位和16位，并且数据按边界对齐存储。某C 语言程序段如下：
若record 变量的首地址为A. B. C. D. 【答案】D 。
则地址
中内容及record.c 的地址分别为（ ）。
【解析】32位整数a 需要占4个字节，16位整数c 需要占2个字节，而字符数据b 占一个字节。a=273, 转换成十六进制是111H , 采用小端方式存放数据，地址0xC008中的内容为11H 。由于数据按边界对齐存储，地址
中存放a , 地址
中存放b , 地址中空闲，
地址中存放c 。
7． —个非空广义表的表尾（ ）。
A. 不能是子表 B. 只能是子表 C. 只能是原子 D. 是原子或子表 【答案】B
【解析】广义表的定义是一个递归定义，当广义表非空时，称第一个元素是它的表头，称其余元素构成的表称为它的表尾。因此一个非空广义表的表尾只能是子表。
8． 直接插入排序在最好情况下的时间复杂度为（ ）。
【答案】B
【解析】当序列是按照直接插入排序的顺序有序时，此时进行插入时，每次都只需要和末尾 的一个元素进行比较，此时的时间复杂度最好，为
9． 内部异常（内中断）可分为故障（fault ）、陷讲（trap ）和终止（abort ）三类。下列有关内部异常的叙述中，错误的（ ）。
A. 内部异常的产生与当前执行指令相关 B. 内部异常的检测由CPU 内部逻辑实现 C. 内部异常的响应发生在指令执行过程中
D. 内部异常处理后返回到发生异常的指令继续执行 【答案】D
【解析】内中断分为：①由软中断指令启动的中断；②在一定条件下由CPU 自身启动的中断。D 项错误，如突然掉电引发的内中断经处理后不会继续执行。
10．下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。
A. 二叉排序树 B. 哈夫曼树 C. D. 堆 【答案】D
【解析】堆的定义： n 个关键字序列（1）
且
或
树
称为堆，当且仅当该序列满足如下性质（简称为堆性质）：
相关内容
相关标签