2017年河南大学计算机与信息工程学院840专业基础课(数据结构、操作系统)之数据结构考研题库
● 摘要
一、选择题
1． 某网络的IP 地址空间为
采用定长子网划分，子网掩码为
则该
网络的最大子网个数、每个子网内的最大可分配地址个数分别是（ ）。
A.32, 8 B.32, 6 C.8, 32 D.8, 30
【答案】B
【解析】子网号为5位，在CIDR 中可以表示的情况可以表示6个主机地址，答案为B 。
2． 归并排序中，归并的趟数是（ ）。
【答案】B
【解析】不妨设归并的趟数为m ，第一次归并每组有两个元素，最后一次归并只剩下一组，这组的元素个数为n
。因此每次归并元素的个数增加一倍。所以
3． 对线性表进行折半查找时，要求线性表必须（ ）。
A. 以顺序方式存储B. 以顺序方式存储，且数据元素有序 C. 以链接方式存储D. 以链接方式存储，且数据元素有序 【答案】B
【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
4． 若一个用户进程通过read 系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（ ）。
I. 若该文件的数据不在内存，则该进程进入睡眠等待状态；II. 请求read 系统调用会导致CPU 从用户态切换到核心态；III. read系统调用的参数应包含文件的名称
A. 仅 I 、II B. 仅 I 、III C. 仅 II 、III
个子网，主机号为3位，除去全0和全1
所以归并的趟数为
D.I 、II 和III 【答案】A
，原进程【解析】对于I ，当所读文件的数据不再内存时，产生中断（缺页中断、缺段中断），直到所需数据从外村调入内存后，将该进程唤醒，使其变为就绪进入睡眠等待状态（阻塞状态）
状态。对于II , read系统调 用CPU 将从用户态切换到核心态，从而获取操作系统提供的服务。对于III ，在操作系统中，要读一个文件首先要open 系统调用将该文件打开。Open 系统调用的参数需要包含文件的路径名与文件名，而read 系统调用只需使用open 返回的文件描述符，并不使用Read 系统调用要求用户提供三个输入参数：文件名作为参数。①文件描述 符；②buf 缓冲区首址；③传送的字节数n 。read 系统调用的功能是试图从fd 所指示的文件中读入n 个字节的数据，并将它们送至由指针buf 所指示的缓冲区中。
5． 已知有向图G=（V ，E ），其中
G 的拓扑序列是
（ ）。
【答案】A
【解析】设G=（V ，E ）是一个具有n 个顶点的有向图，V 中顶点序列
能被称
，则在序列中顶点Vi 为拓扑序列的条件：若
必须排在顶点Vj 之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列
是
6． 线性表的顺序存储结构是一种（ ）。
A. 随机存取的存储结构 B. 顺序存取的存储结构 C. 索引存取的存储结构 D.Hash 存取的存储结构 【答案】A
【解析】线性表包括顺序存储结构和链式存储结构，顺序存储结构能够随机存取表中的元素，但插入和删除操作较麻烦，链式存储结构不能随机访问表中的元素，但是能够表示元素之间的先后次序，而且插入和删除操作较容易。
7． 设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，储地址为1，每个元素占一个地址空间，则
A.13 B.33 C.18 D.40
【答案】B
的地址为（ ）。
为第一元素，其存
【解析】对于对称矩阵，为了节省存储空间，为多个相同的元素只分配一个存储空间。
时，
当
时，
其
对于对称矩阵，元素下表之间的对应关系为：当
中k 相当于地址空间的标号，i 为行号，j 为列号。因为第一个元素存储地址为1，所以最后计算 的k 需要加1。所以
的存储位置为
8． 在系统总线的数据线上，不可能传输的是（ ）。
A. 指令 B. 操作数
C. 握手（应答）信号 D. 中断类型号型号 【答案】C
【解析】握手（应答）信号属于通信联络控制信号应该在通信总线上传输，不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。
9． ARP 协议的功能是（ ）。
A. 根据IP 地址查询MAC 地址 B. 根据MAC 地址查询IP 地址 C. 根据域名查询IP ±也址 D. 根据IP 地址查询域名 【答案】A 。
【解析】ARP 协议是网络层协议，因此只能和传输层和数据链路层有关系，从这一点出发，域名是应用层的范畴，选项C 和D 是不正确的，根据MAC 地址查询IP 地址是RARP 协议的功能，因此进而得出正确答案是A 。
10．有关二叉树下列说法正确的是（ ）。
A_二叉树的度为2
B. —棵二叉树的度可以小于2 C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2 【答案】B
【解析】树的度=MAX（结点1的度，结点2的度，结点3的度，... ，结点n 的度）。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。
11．下列四个序列中，哪一个是堆（ ）？
A.75，65，30，15，25，45，20，10 B.75，65，45，10，30，25，20，15 C.75，45，65，30，15，25，20，10 D.75，45，65，10，25，30，20，15
相关内容
相关标签