2016年复旦大学软件学院数据结构(同等学力加试)考研复试题库
● 摘要
一、选择题
1． 在下面的排序方法中，辅助空间为
A. 希尔排序
B. 堆排序
C. 选择排序
D. 归并排序
答:D
2． 在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）
答:C
【解析】两个循环嵌套，那么语句x :=x＋l :
则被执行了次。
3． 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。
I. 简单选择排序II. 希尔排序III. 快速排序IV . 堆排V. 二路归并排序
A. 仅 I 、III 、IV
B. 仅 I 、II 、III
C. 仅 II 、III 、IV
D •仅III 、IV 、V
答:A 。
【解析】其中简单选择排序、堆排序属于选择类排序，每一趟排序结束时将确定最大（或最小）关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。
4． 主机甲和主机乙之间已建立了一个TCP 连接，TCP 最大段长度为1000字节，若主机甲的当前拥塞窗口为4000字节，在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的对第一个段的确认段，确认段中通告的接收窗口大小为2000字节，则此时主机甲还可以向主机乙发送的最大字节数是（ ）。
A.1000
B.2000
C.3000
第 2 页，共 41 页 的是（ ）。
D.4000
答:A
【解析】发送方的发送窗口的上限值应该取接收方窗口和拥塞窗口这两个值中较小的一个，
=2000字节，于是此时发送方的发送窗口为min{4000, 2000）由于发送方还没有收到第二个最大段
的确认，所以此时主机甲还可以向主机乙发送的最大字节数为2000-1000=1000字节，正确选项为A 。
5． 在参考摸型中，下列功能需由应用层的相邻层实现的是（ ）
A. 对话管理
B. 数据格式转换
C. 路由选择
D. 可靠数据传输
答:B
【解析】应用层的相邻层即为表示层，表示层负责管理数据的压缩、加密与解密、格式装换等，故答案为B 。
6． 若一个用户进程通过read 系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（ ）。
I. 若该文件的数据不在内存，则该进程进入睡眠等待状态；II. 请求read 系统调用会导致CPU 从用户态切换到核心态；III. read系统调用的参数应包含文件的名称
A. 仅 I 、II
B. 仅 I 、III
C. 仅 II 、III
D.I 、II 和III
答:A
，原进程【解析】对于I ，当所读文件的数据不再内存时，产生中断（缺页中断、缺段中断）
，直到所需数据从外村调入内存后，将该进程唤醒，使其变为就绪进入睡眠等待状态（阻塞状态）
状态。对于II , read系统调 用CPU 将从用户态切换到核心态，从而获取操作系统提供的服务。对于III ，在操作系统中，要读一个文件首先要open 系统调用将该文件打开。Open 系统调用的参数需要包含文件的路径名与文件名，而read 系统调用只需使用open 返回的文件描述符，并不使用
Read 系统调用要求用户提供三个输入参数：文件名作为参数。①文件描述 符；②buf 缓冲区首址；
③传送的字节数n 。read 系统调用的功能是试图从fd 所指示的文件中读入n 个字节的数据，并将它们送至由指针buf 所指示的缓冲区中。
7． 对于循环队列（ ）。
A. 无法判断队列是否为空
B. 无法判断队列是否为满
第 3 页，共 41 页
相关内容
相关标签