2017年闽南师范大学计算机学院821计算机学科专业基础综合[专业硕士]之数据结构考研仿真模拟题
● 摘要
一、填空题
1． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））
【答案】归并；堆
2． 二进制地址为011011110000，大小为
【答案】011011110100；011011100000
011011110000是块的起始地址，
【解析】大小分别为式如下：
当大小为4时，起始地址
为
3． 设数组数组中任一元素连续存放在主内存里，主内存字长为16位，那么
（1）存放该数组至少需要的单元数是_____；
（2）存放数组的第8列的所有元素至少需要的单元数_____； （3）数组按列存储时，元素【答案】270; 27; 2204 【解析】
数组的元素个数为需要
第8列有9个元素，共占
因为每个元素占内存48个二进制位，即6个字节。故总
个单元数。
个字节，因此至少需要
个单元数。由题知，每个元素占3
个字节，因为主内存字长为16位，即2个字节，所以至少需要
的起始地址是_____。
当大小为16时，起始地址为
：和
其伙伴块的起始地址计算公
和
块的伙伴地址分别为：_____
均占内存48个二进制位，从首地址2000开始
个单元。按列存储时，的起始地址为
4． 求最短路径的Dijkstra 算法的时间复杂度为_____。
【答案】
5． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测
的次数最小。总次数为
6． 在单链表中设置头结点的作用是_____。
【答案】方便运算
7． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。
【答案】
8． 顺序栈用
【答案】
存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
9． 已知如下程序段：
语句1执行的时间复杂度为_____；语句2执行的时间复杂度为_____；语句3执行的时间复杂度为_____；语句4执行的时间复杂度为_____。
【答案】（1）n ＋1 （2）n
（3）n （n ＋3）/2 （4）n （n ＋l ）/2
【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋（n ＋l ）加起来就是n （n ＋3）/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即n （n ＋l ）/2。
10．求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
二、选择题
11．分区分配内存管理方式的主要保护措施是（ ）。
A. 界地址保护
B. 程序代码保护 C. 数据保护 D. 栈保护 【答案】A
【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护。通常的界地址保护方法采用软硬件结合的方法。考生要注意本题与虚拟存储方法的区别。
12．设哈希表
长哈希函
数表中已有4个结点
：
其余地址为空，如用二次探测
再哈希法解决冲突，关键字为49的结点的地址是（ ）。
【答案】D
【解析】15，38，61，84用哈希函数为5，发生冲突，用二次探测再散列法解决冲突：
仍然发生冲突。
仍然发生冲突。
不再发生冲突。
13．单链表中，增加一个头结点的目的是为了（ ）。
A. 使单链表至少有一个结点 B. 标识表结点中首结点的位置 C. 方便运算的实现
D. 说明单链表是线性表的链式存储 【答案】C
【解析】单链表中增加一个头结点的目的是为了方便运算的实现，使得对第一个元素的操作与其它元素的操作相同。
14．
，用直接插入排序方法对下面4个序列进行排序（由小到大）元素比较次数最少的是（ ）。
【答案】C
15．主机甲和主机乙间已建立一个TCP 连接，主机甲向主机乙发送了两个连续的TCP 段，分别包含300字节和500字节的有效载荷，第一个段的序列号为200, 主机乙正确接收到两个段后，发送给主机甲的确认序列号是（ ）。
A.500 B.700 C.800 D.1000
计算后得地址：4，5，6，7。49计算后