2016年浙江理工大学机械与自动控制学院计算机专业基础之数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 某以太网拓扑及交换机当前转发表如下图所示，主机发送1个数据帧，主机
A. B. C. D.
收到该帧后，向主机
交换机对这两个帧的转发端口分别是（ ）
向主机
发送一个确认帧，
答:B
【解析】
第一次交换机没有录这个数据报源MAC
地址的信息
的信息，只能选择从其他端口全部发送，同时记
确认帧发送时已经有
的信息
了所以只用从1端口转发。
2． 在系统内存中设置磁盘缓冲区的主要目的是（ ）。
A. 减少磁盘I/O次数 B. 减少平均寻道时间 C. 提高磁盘数据可靠性 D. 实现设备无关性 答:A
【解析】访问磁盘的开销远远大于访问内存的开销。磁盘缓冲区便是利用主存中的存储空间，来暂存从磁盘中读出（或写入）的信息，频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。
3． 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A. 插入 B. 选择 C. 希尔 D. 二路归并 答:A
【解析】解此题需要熟知各种排序方法的基本思想。插入排序的基本思想是：假设待排序的
记录存放在数组
中，排序过程的某一中间时刻，R
被划分成两个子区间
插入到有序区
和
其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨
称其为无序区。将当前无序区的第1
个记录
中适当的位置上。使
变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。
4． 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。
答:B
【解析】堆排序需要一个空间用于交换，因此堆排序所需要的附加存储空间为
5． 主机甲向主机乙发送一个的TCP 段，期望与主机乙建立TCP 连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的TCP 段可能是（ ）。
A. （SYN=0, ACK=0, seq=11221, ack=11221） B. （SYN=1, ACK=1, seq=11220, ack=11220） C. （SYN=1，ACK=1, seq= 11221，ack= 11221） D. （SYN=0, ACK=0, seq= 11220, ack= 11220） 答:C
【解析】TCP 是面向连接的，所谓面向连接，就是当计算机双方通信时必需先建立连接，然后数据传送，最后拆除三个过程，也就是客户主动打开TCP 传输，服务器被动打开。第一次握手：客户发送SYN=1，seq=x 给服务器，即客户的TCP 向服务器发出连接请求报文段，其首部中的同步位SYN=1，并选择序号seq=x，表明传送数据时的第一个数据字节的序号是X 。第二次握手：服务器发送SYN=1, ACK=1, Seq=y, ack=X+l给客户，即服务器的TCP 收到连接请求报文段后，如同意则发回确认。服务器在确认报文段中应使SYN=1，使 ACK=1，其确认号ack=x+l, 自己选择的序号seq=y。第三次握手：客户发送ACK=1, seq=x+l, ack=y+l 给服务器，即客户收到此报文段后向服务器给出确认，其ACK=1, 确认号aCk=y+l。客户的TCP 通知上层应用进程，连接已经建立。服务器的TCP 收到主机客户的确认后，也通知其上层应用进程：TCP 连接已经建立。 因此，本题中x=11220, y是主机乙自动选取的序号，可以与x 相同，也可以不相同，从而主机乙所ACK=1, seq=y, ack=x+l，ACK=1, seq=y，ack=11221，发出的TCP 段应该是SYN=1，即 SYN=1，
从而答案是 C 。
6． 已知循环队列存储在一维数组rear 的值分别是（ ）。
A.0, 0 B.0, n-1 C.n-1, 0 D.n-1, n-1
答:B
中，且队列非空时front 和rear 分别指向队头元素和
队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front 和
【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素，若初始时队列为空，且要求第1 个进入队列的元素存储在A[0]处，则此时front 和rear 的值都为0。由于进队操作要执行（rear+1） % n，则初始 时front 的值为0、rear 的值为n-1。
7． 二叉树在线索化后，仍不能有效求解的问题是（ ）。
A. 前序线索二叉树中求前序后继 B. 中序线索二叉树中求中序后继 C. 中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继 答:D
【解析】后序线索二叉树求后序后继要分3种情况，比较复杂，不是仅仅线索化后就能求解的，算法上还要要分情况讨论。
8． 设有一个n 行n 列的对称矩阵A ，将其下三角部分按行存放在一个一维数组B 中，放于
中，那么第i 行的对角元素
存放于B 中（ ）处。
答:A
【解析】
中列标不大于行标，
又
存放在
中，
所以
存放的位置为
存
9． 将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.N B.2N-1 C.2N D.N-1 答:A
【解析】归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为