2017年哈尔滨工业大学计算机科学与技术学院854计算机基础之数据结构考研题库
● 摘要
一、选择题
1． 在虚拟存储管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是（ ）。
A. 编辑
B. 编译
C. 链接
D. 装载
【答案】B
【解析】程序的编辑阶段一般都是程序员能够识别的高级语言或低级语言的文本，不涉及到任何与计算机运 行相关的事；编译是由编译程序将用户源代码编译成若干个目标模块，源地址编译成目标程序时，会形成逻辑地址；链接是由链接程序将编译后形成的一组目标模块，以及所需库函数链接，形成完整的装入模块；装入是由装入程序将装入模块装入内存。
2． 本地用户通过键盘登录系统时，首先获得的键盘输入信息的程序是（ ）。
A. 命令解释程序
B. 中断处理程序
C. 系统调用服务程序
D. 用户登录程序
【答案】B
【解析】外部设备在与计算机连接时有多种方式，中断技术就是一种常用方式。其工作原理是：利用处理机中断信号线，外部设备在需要服务的时候将该线设置为有效，计算机若同意接受
，中断则会停止当前进程的运行，转而服务发出中断的物理设备（注意与陷阱，即软中断有区别）
那么对不同外部设备进行服务的程序代码是不同的，如何找到这些代码呢? 这就要借助中断向量，中断向量一般是由硬件根据中断的类型（不同外设不同）计算所得，或计算机系统在开机配置时所配置的。处理机取得中断向量，其实就是一个物理地址，该地址下存放的是为此中断服务的代码的起始地址。所以，当键盘按下的时候，键盘控制器获得该操作动作，先将键盘扫描码读入键盘缓冲区，再向处理机发出键盘中断，适当的时候（一条指令的末尾或一条原语结束）处理机会响应中断，调用指定服务程序将键盘缓冲区中的键盘扫描码输入到登录进程中去。如此，最先响应键盘的必然是中断处理程序。本题中，像命令解释器（例如cmd 窗口）、系统调用服务和用户登录程序都在中断处理程序后面。
3． 下列选项中，在用户态执行的是（ ）。
A. 命令解释程序
B. 缺页处理程序
C. 进程调度程序
D. 时钟中断处理程序
【答案】A
【解析】题目是问用户态执行，可见是有关操作系统基本概念的问题。四个选项中，用户唯一能面对的是命令解释程序，缺页处理程序和时钟中断都属于中断，在核心态执行，而进城调度属于系统调用在核心态执行。只有命令解释程序属于命令接口，可以运行在用户态，接受用户的命令操作控制。
4． 折半查找的时间复杂性为（ ）。
【答案】D
【解析】顺序查找的事件复杂度为
度为 因为折半查找是查找效率最高的算法，它的事件复杂
5． 下列因素中，不会影响信道数据传输速率的是（ ）
A. 信噪比
B. 频率宽带
C. 调制速率
D. 信号传播速度
【答案】D
【解析】信道数据传输速率与信噪比、频率宽度、调制速率都有关。
6． FTP 客户和服务器间传递FTP 命令时，使用的连接是（ ）。
A. 建立在TCP 之上的控制连接
B. 建立在TCP 之上的数据连接
C. 建立在UDP 之上的控制连接
D. 建立在UDP 之上的数据连接
【答案】A
【解析】对于FTP , 为了保证可靠性，选择TCP 。FTP 应用需要建立两条TCP 连接：一条为控制连接，另一条为数据连接。FTP 服务器打开21号端口，被动的等待客户的连接建立请求。客户则以主动方式与服务器建立控制连接，客户通过控制连接将命令传给服务器，而服务器则通过控制连接将应答传给客户，命令和响应都是以NVTASCII 形式表示的。
7． 数组通常具有的两种基本操作是（ ）。
A. 查找和修改
B. 查找和索引
C. 索引和修改
D. 建立和删除
【答案】A
【解析】数组中的元素是顺序存放的，通过下标可以很好地查找数组元素，同时通过对应的指针可以修改数组元素的值，因此数组通常具有的两种基本操作是查找和修改。根据数组的性质，数组通常具有的两种基本运算是排序和查找。
8． 无向图G=（V , E ）, 其中：V={a, b , c , d , e , f ）}, E={（a , b ）, （a , e ）, （a , c ），，（b , e ）, （c , f ）
，（f , d ）（e , d ）, 对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A.a , b , e , c , d , f B.a , c , f , e , b , d
C.a , e , b , c , f , d D.a , e , d , f , c , b
【答案】D
【解析】图的深度优先遍历过程是：从图中某个初始顸点V 出发，首先访问初始顶点V ，然后选择一个与顶点V 相邻且没被访问过的顶点U 为初始顶点。再从U 出发进行深度优先搜索，直到图中与当前顶点V 邻接的所有顶点都被访问过为止。
，，，，，根据E={（a , b ）（a ，e ）（a ，c ）（b ，e ）（c , f ）（f ，d ）, （e ，d ）}可知各顶点之间的邻
接关系。依据上面的原则遍历，得出遍历顺序a , e ，d ，f ，c , b 。
9． 若元素a ，b , c, d, e，f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（ ）。
A.d ，c ，e ，b ，f ，a
B.c ，b ，d ，a ，e ，f
C.b ，c ，a ，e ，f ，d
D.a ，f ，e ，d ，c ，b
【答案】D
【解析】4个选项所给序列的进、出栈操作序列分别为：
选项A.Push , Push , Push ，Push , Pop, Pop, Push，Pop , Pop, Push , Pop ，Pop
选项B.Push , Push , Push , Pop , Pop , Push, Pop, Pop, Push, Pop , Push, Pop
选项C.Push , Push , Pop , Push , Pop , Pop, Push, Push, Pop, Push , Pop , Pop
选项D.Push , Pop , Push, Push , Push , Push, Push, Pop, Pop，Pop , Pop , Pop
按照题目要求，不允许连续三次进行退栈操作，所以选项D 所给序列为不可能得到的出栈顺序。
10．将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。
A.4
相关内容
相关标签