2016年华东交通大学软件学院数据结构考研复试题库
● 摘要
一、选择题
1． 下列序列中，（ ）是执行第一趟快速排序后所得的序列。
答:C
【解析】快速排序将数据划分成两部分，其中一部分关键字比另一部分关键字小。
2． 主机甲与主机乙之间已建立一个TCP 连接，主机甲向主机乙发送了 3个连续的TCP 段，分别包含300字节、400字节和500字节的有效载荷，第3个段的序号为900。若主机乙仅正确接收到第1和第3个段，则主机乙发送给主机甲的确认序号是（ ）。
A.300 B.500 C.1200 D.1400 答:B
【解析】本题考查TCP 的确认机制，TCP 首部的序号字段是指本报文所发送的数据的第一个字节的序号。本题中首先根据第3个段的序号为900, 可以得出第2个段的序号为500, 第1个段的序号为200, 这里主机乙仅 正确接收了第1段和第3段，这意味着第2段丢失，需要超时重传，因此主机乙发送给主机甲的确认序号，也就是此时接收端期望收到的下一个数据包中第一个字节的序号应该是第二段的第一个字节的序号，也就是500, 因此答案是B 。
3． 当字符序列作为图输入时，输出长度为3的且可用作C 语言标识符的序列的有（ ） 。
A.4个 B.5个 C.3个 D.6个
图
答:C
【解析】首先需要明白C 语言标识符的命名规则。数字不能作为标识符的开头，因此第一个字符只能为t 或者下划线。若首字符为t , 有两种结果此总共有3种结果。
第 2 页，共 45 页
若首字符为则只有一种结果因
4． 设栈S 和队列Q 的初始状态为空，元素后即进队列Q ，若6个元素出队的序列是
A.6 B.4 C.3 D.2 答:C
5． —
组记录的关键码为
准得到的一次划分结果为（ ）。
依次通过栈S ，一个元素出栈 则栈S 的容量至少应该是（ ）。
则利用快速排序的方法，以第一个记录为基
答:C
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：46比84小，不交换； 第二次比较：40比46小，交换，此时为第三次比较：46比79小，交换，此时为第四次比较：38比46小，交换，此时为第五次比较：56比46大，交换，此时为
一次划分结束。
6． 若磁盘转速为7200转/分，平均寻道时间为8ms , 每个磁道包含1000个扇区，则访问一个扇区的平均存取时间大约是（ ）。
A. B. C. D. 答:B
【解析】磁盘的平均寻址时间包括平均寻道时间和平均等待时间。平均寻道时间为8ms , 平均等待时间与磁盘转速有关，
为
因此总的时间为：
磁盘的存取一个扇区的时间
为
第 3 页，共 45 页