2017年上海应用技术学院计算机学院816数据结构与算法考研冲刺密押题
● 摘要
一、填空题
1． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
2． 设单链表的结点结构为为指针域，已知指针px 指向单链表中data 为x 的结
_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：
_____; 【答案】
3． 在有n 个顶点的有向图中，每个顶点的度最大可达。
【答案】2（n-l ）
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。
4． 文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
5． 高度为h 的堆中，最多有_____元素，最少有_____个元素。 【答案】
当最后一层只有【解析】当这个堆构成的是满二叉树时，元素的个数最多，
元素个数为
一个元素时，此时堆的元素个数最少，元素个数为
6． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。
【答案】顺序
【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。
7． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
8． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
9． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。 【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
10．设有两个算法在同一机器上运行，其执行时闻分别为要使前者快于后者，n 至少为_____。
【答案】15
【解析】当
时，而
，时，
二、选择题
11．一个TCP 连接总是以1KB 的最大段发送TCP 段，发送方有足够多的数据要发送。当拥塞窗口为16KB 时发生了超时，如果接下来的4个RTT （往返时间）时间内的TCP 段的传输都是成功的，那么当第4个RTT 时间内发送的所有TCP 段都得到肯定应答时，拥塞窗口大小是（ ）。
A.7KB
B.8KB
C.9KB
D.16KB
【答案】C
【解析】回顾TCP 流量控制和拥塞控制（慢启动）的知识点，从第一个MSS 开始，每次发送成功，拥塞窗口值翻倍，四次以后，应该为16, 但是由于拥塞阈值变为16/2=8, 故三次成功后为8, 以后为线性增长，故为8+1=9, 答案为C 。
12．动态存储管理系统中，通常可有（ ）种不同的分配策略。
【答案】C
【解析】动态存储管理系统中有以下三种：首次拟合法、最佳拟合法、最差拟合法。①首次拟合法，从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户。②最佳拟合法，将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户。则系统在分配前首先要对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n 且最接近n 的空闲块进行分配。③最差拟合法，将可利用空间表中不小于n 且是链表中最大的空闲块的一部分分配给用户。
13．下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。
A. 二叉排序树
B. 哈夫曼树
C.
D. 堆
【答案】D
【解析】堆的定义：
n 个关键字序列
（1）
（2）
且且或 称为堆，当且仅当该序列满足如下性质（简称为堆性质）： 树
满足第（1）种情况的堆，称为小顶堆；满足第（2）种情况的堆，称为大顶堆。
由堆的定义可知堆可以满足上述性质。
14．已知一算术表达式的中缀表达式为
【答案】D
【解析】后缀表达式：在程序语言中，运算符位于两个操作数后面的表达式。
15．设文件F1的当前引用计数值为1，先建立F1的符号链接（软链接）文件F2, 再建立F1的硬链接文件F3, 然后删除F1。此时，F2和F3的引用计数值分别是（ ）。
A.0、1
B.1、1
C.1、2
D.2、1
【答案】B
【解析】为了使文件实现共享，通常在使用该形式文件系统的文件索引节点中设置一个链接计数字段，用来表示链接到本文件的用户目录项的数目（引用计数值），这是共享的一种方法。当新文件建立时，一般默认引用计数值为1。硬链接可以看作是已存在文件的另一个名字，新文件和被链接文件指向同一个节点，引用计数值加1。当删除被链接文件时，只是把引用计数值减1，直到引用计数值为0时，才能真正删除文件。软链接又叫符号链接，在新文件中只包含了被链接文件的路径名，新文件和被链接文件指向不同的节点。建立软链接文件时，文件的引用计数值不会增加。在这种方式下，当被链接文件删除时，新文件仍然是存在的，只不过是不能通过新文件的路径访问被链接文件而已。因此，在本题中，当建立F2时，F1和F2的引用计数值都为1。当再建立F3时，F1和F3的引用计数值就都变成了2。当后来删除F1时，F3的引用计数值为2-1=1。F2的引用计数值仍然保持不变，所以F2和F3的引用计数值分别是：1, 1。
其后缀形式为（ ）。