2016年宁波大学信息科学与工程学院数据结构考研复试题库
● 摘要
一、选择题
1． 用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是（ ）
A. 存储效率
B. 数列函数
C. 装填（装载）因子
D. 平均查找长度
答:D
【解析】哈希方法冲突会使在查找冲突的关键字时，还要根据冲突处理办法多次比较关键字，则直接影响了平均查找长度。
2． 折半查找的时间复杂性为（ ）。
答:D
【解析】顺序查找的事件复杂度为因为折半查找是查找效率最高的算法，它的事件复杂 度为
3． 对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（ ）。 A. B. C. D.
答:C 。
【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间
为其中n 为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为其中e 为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为即可得出正确答案。
4． 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。
A. 二叉排序树
B. 哈夫曼树
C.
D. 堆
答:D 树
【解析】堆的定义：
n 个关键字序列
（1）（2）且且或 称为堆，当且仅当该序列满足如下性质（简称为堆性质）：
满足第（1）种情况的堆，称为小顶堆；满足第（2）种情况的堆，称为大顶堆。
由堆的定义可知堆可以满足上述性质。
5． 主机甲向主机乙发送一个
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． 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
A. 栈
B. 队列
C. 树
的TCP 段，期望与主机乙建立TCP 连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的TCP 段可能是（ ）。