2017年南京师范大学教育科学学院829数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为2字节，逻辑地址结构为：
逻辑地址空间大小为（ ）。
A.64 B.128 C.256 D.512
【答案】B
【解析】地址空间分为逻辑地址空间和物理地址空间。页的大小为采用二级页表，一页可存放要
个页面来保存页表项，故本题答案为B 。
字节，页表项大小为2B ，
字节，故最少需
’个页表项，本题中逻辑地址空间大小为
页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是
字节，页表项大小为
2． 已知关键字序列5, 8, 12, 19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（ ）。
A.3, 5，12，8, 28，20, 15，22，19 B.3, 5, 12, 19, 20, 15, 22, 8, 28 C.3, 8, 12, 5, 20, 15, 22, 28, 19 D.3, 12, 5, 8, 28, 20, 15, 22, 19
【答案】A
【解析】在堆中插入或删除一个元素后，将不再满足堆的性质。为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素。具体过程如图（1）〜（5）所示，（1）为原堆，（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。
3． 在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。
【答案】B
【解析】二分查找的时间复杂度为
在一个用N 个元素的有序单链表中查找具有给定
关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，
因此时间复杂度为
4． 对矩阵压缩存储是为了（ ）。
A. 方便运算 B. 方便存储 C. 提高运算速度 D. 减少存储空间 【答案】D
【解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素放在一个存储空间，目的就是为了节省空间。
5． 一个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 。
6． 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A. 顺序表 B. 双链表
C. 带头结点的双循环链表 D. 单循环链表 【答案】A
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进 行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。
7． 最大容量为n 的循环队列，队尾指针是rear ，队头：front , 则队空的条件是（ ）。
A.
B.
C.
D. 【答案】B
【解析】循环队列队空的条件是：rear=front。循环队列队满的条件，通常采
用
来判定队满，其中
表示队列的长度。
相关内容
相关标签