2017年沈阳大学信息工程学院809数据结构考研题库
● 摘要
一、选择题
1． 若磁盘转速为7200转/分，平均寻道时间为8ms , 每个磁道包含1000个扇区，则访问一个扇区的平均存取时间大约是（ ）。
A. B. C. D. 【答案】B
【解析】磁盘的平均寻址时间包括平均寻道时间和平均等待时间。平均寻道时间为8ms , 平均等待时间与磁盘转速有关，
为
因此总的时间为：
磁盘的存取一个扇区的时间
为
2． —棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有（ ）个结点。
A.2h
B.
C.
D. 【答案】B
【解析】此树满足哈夫曼树，除根节点外每层有两个节点。
3． FTP 客户和服务器间传递FTP 命令时，使用的连接是（ ）。
A. 建立在TCP 之上的控制连接 B. 建立在TCP 之上的数据连接 C. 建立在UDP 之上的控制连接 D. 建立在UDP 之上的数据连接 【答案】A
【解析】对于FTP , 为了保证可靠性，选择TCP 。FTP 应用需要建立两条TCP 连接：一条为控制连接，另一条为数据连接。FTP 服务器打开21号端口，被动的等待客户的连接建立请求。客户则以主动方式与服务器建立控制连接，客户通过控制连接将命令传给服务器，而服务器则通过控制连接将应答传给客户，命令和响应都是以NVTASCII 形式表示的。
4． 基于比较方法的n 个数据的内部排序。 最坏情况下的时间复杂度能达到的最好下界是（ ）。
A.0（nlogn ） B.O （logn ） C.O （n ） D.
【答案】A
【解析】在内部排序中，最坏情况下的时间复杂度为0（nlogn ）。 已知待排序的n 个元素可分为
个组，每个组包含k 个元素，且任一组内的各元素均分别
大干前一 5． 在子网192.168.4.0/30中， 能接收目的地址为192.168.4.3的IP 分组的最大主机数是（ ）。
A.0 B.1 C.2 D.4
【答案】C
【解析】每个子网中忽略子网内全为0和全为1的地址剩下的就是有效主机地址，本题中由于子网的比特数是30, 因此用于主机的只有2位，即00, 01, 10, 11，有效主机地址是2个，这里192.168.4.3显然是其广播地址，因此答案是C 。
6． 下列选项中，用于设备和控制器（’接口）之间互连的接口标准是（ ）
A.PCI B.USB C.AGP
D.PCI-Express 【答案】B
【解析】设备和设备控制器之间的接口是USB 接口，其余选项不符合，故答案为B 。 7． 用直接插入排序方法对下面4个序列进行排序，
（由小到大）元素比较次数最少的是（ ）。
【答案】C
8． 某系统有n 台互斥使用的同类设备，3个并发进程需要3, 4, 5台设备，可确保系统不发生死锁的设备数n 最小为（ ）
A.9 B.10 C.11 D.12
【答案】B
【解析】2+3+4+1 = 10
9． 若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组
中，则在B 中确定
的位置k 的关系为（ ）。
【答案】B
【解析】将n 阶对称矩阵存人一维数组中，一维数组的大小需为
中，当
时，i 与k 的关系为
对n 阶对称矩阵
A
以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组
10．假定基准程序A 在某计算机上的运行时间为100秒，其中90秒为CPU 时间，其余为间。若CPU
速度提高
A.55秒 B.60秒 C.65秒 D.70秒 【答案】D 。 CPU 速度提高【解析】秒。
即CRJ 性能提高比为1.5, 改进之后的CPU 运行时间
速度不变，仍维持10秒，所以运行基准程序A 所耗费的时间为70秒。
速度不变，则运行基准程序A 所耗费的时间是（ ）。
时
11．由3个结点可以构造出多少种不同的有向树？（ ）
A.2 B.3 C.4 D.5
【答案】A
【解析】满足以下条件的有向图称为有向树：①有且仅有一个结点的入度为0; ②除树根外结点的入度为1; ③从树根到任一结点有一有向通路。
12．一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。
A.107 B.108 C.214 D.215
【答案】B
【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有以
所
也就是说若对其进行哈夫曼编码，共能得到108个码字。
二、填空题
13．试利用下列栈和串的基本操作完成下述填空题。
initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数；