黑龙江科技大学计算机专业考研,2017年黑龙江科技大学计算机与信息工程学院808数据结构考研题库...

黑龙江科技大学计算机专业考研,2017年黑龙江科技大学计算机与信息工程学院808数据结构考研题库..."/>

黑龙江科技大学计算机专业考研,2017年黑龙江科技大学计算机与信息工程学院808数据结构考研题库...

一、选择题

1． 已知程序如下：

{

} {

}

程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是( )。

A. B. C. D. 【答案】A

【解析】函数S (intn )是一个递归函数：①当实际参数小于等于零时则返回0, 并终止递归；，并将S (n-1)的结果加上n 作为返回值。程序从②当实际参数大于零时则递归调用S (n-1)

main ( )函数开始，首先调用main ( )函数；在main ( )函数中调用S (1)；由于函数S (1)的函数时，将main ( )函数的上下文保存到栈中，并进入函数S (1)

；在S 实际参数大于零，需要调用S (0), 故将S (1)函数的上下文保存到栈中，进入S (0)(0)中，实际参数小于等于零，递归终止。

2．

循环两列放在一维数组中，endl 指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是( )

A. 队空：B. 队空：C. 队空：D. 队空：【答案】A

【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等，则队满。而队空的条件还是首尾指针是否相等。

3． 有一个的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是( )。

A.60

队满：队满：

队满：

modM ; 队满：

B.66 C.18000 D.33

【答案】B

【解析】如果是全部，

则是需要10个非零整数则是

个字节；但是用三元组表示的话，只需要记录非零

字节，

数据的X 坐标，Y 坐标，数值即可，就是每个非零数字需要占用三个整数的空间，即

字节；如果问有效元素占的空间大小，则选A 项，但是如果从整体

来看，应该多一个用来记录矩阵宽(100)、高(90)、默认值(0)的元素，所以还应该多算6个字节。所以全部为66字节，选B 项。

4． 下列选项中的英文缩写均为总线标准的是( )。

A.PCI 、CRT 、USB 、EISA B.ISA 、CPI 、VESA 、EISA C.ISA 、SCSI 、RAM 、MIPS D.ISA 、EISA 、PCI 、PCI-Express 【答案】D

【解析】选项A 中的CRT 和USB 、选项B 中的CPI 、选项C 中的RAM 和MIPS 均不是总线标准的英文缩写，只有选项D 中的英文缩写均为总线标准。

5． 将一棵树t 转换为孩子兄弟链表表示的二叉树h ，则t 的后序遍历是h 的( )。

A. 前序遍历 B. 中序遍历 C. 后序遍历 【答案】B

【解析】树的后序遍历恰好对应于二叉树的中序遍历。

6． 为实现快速排序算法，待排序序列宜采用的存储方式是( )。

A. 顺序存储 B. 散列存储 C. 链式存储 D. 索引存储 【答案】A

【解析】对绝大部分内部排序而言，只适用于顺序存储结构，快速排序在排序过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。

7． 某主机的IP 地址为180.80.77.55, 子网掩码为255.255.252.0。若该主机向其所在子网发送广播分组，则目的地址可以是( )。

A.180.80.76.0

B.180.80.76.255 C.180.80.77.255 D.180.80.79.255 【答案】D 。

【解析】IPv4地址中的特殊地址，直接广播地址，也就是把主机位全部设置为1，这里77的二进制是01001101, 子网掩码252的二进制是11111100，由此可以看到77的前6位作为子网位，后四位作为主机位，由此可以知道 其广播地址是180.80.01001111.255，也就是180.80.79.255，因此答案是D 。

8． 本地用户通过键盘登录系统时，首先获得的键盘输入信息的程序是( )。

A. 命令解释程序 B. 中断处理程序 C. 系统调用服务程序 D. 用户登录程序 【答案】B

【解析】外部设备在与计算机连接时有多种方式，中断技术就是一种常用方式。其工作原理是：利用处理机中断信号线，外部设备在需要服务的时候将该线设置为有效，计算机若同意接受，中断则会停止当前进程的运行，转而服务发出中断的物理设备(注意与陷阱，即软中断有区别)那么对不同外部设备进行服务的程序代码是不同的，如何找到这些代码呢? 这就要借助中断向量，中断向量一般是由硬件根据中断的类型(不同外设不同)计算所得，或计算机系统在开机配置时所配置的。处理机取得中断向量，其实就是一个物理地址，该地址下存放的是为此中断服务的代码的起始地址。所以，当键盘按下的时候，键盘控制器获得该操作动作，先将键盘扫描码读入键盘缓冲区，再向处理机发出键盘中断，适当的时候(一条指令的末尾或一条原语结束)处理机会响应中断，调用指定服务程序将键盘缓冲区中的键盘扫描码输入到登录进程中去。如此，最先响应键盘的必然是中断处理程序。本题中，像命令解释器(例如cmd 窗口)、系统调用服务和用户登录程序都在中断处理程序后面。

9． 在下列存储形式中，哪一个不是树的存储形式？( )

A. 双亲表示法 B. 孩子链表表示法 C. 孩子兄弟表示法 D. 顺序存储表示法 【答案】D

【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。因此简单的顺序存储表示不能满足树的基本要求。常用的三种树的表示法为：双亲表示法、孩子链表示法、孩子兄弟表示法。