2018年南昌大学信息工程学院871数据结构[专业硕士]考研基础五套测试题
● 摘要
一、单项选择题
1． 假定主存地址为32位, 按字节编址, 主存和Cache 之间采用直接映射方式, 主存块大小为4个字, 每字32位, 采用回写(Write Back) 方式, 则能存放4K 字数据的Cache 的总容量的位数至少是（ ）。
A.146k
B.147K
C.148K
D.158K
【答案】B
【解析】Cache 和主存直接映射方式的规则为:主存储器分为若干区, 每个区与缓存容量相同; 每个区分为若干数据块, 每个块和缓存块容量相同; 主存中某块只能映象到Cache 的一个特定的块中。本题中, Cache 总共存放4K 字数据, 块大小为4个字, 因此cache 被分为
要包含所存的数据4个字, 每个字32位, 18位标记位和一个有效位, 因此总容量为:
。
2． 已知两个长度分别为m 和n 的升序链表, 若将它们合并为一个长度为m+n的降序链表, 则最坏情况下的时间复杂度是（ ） A. B. C. D.
【答案】D
m 和n 是两个升序链表长度分别为m 和n , 在合并过程中最坏的情况是两个链表中的【解析】
元素依次进行比较, 比较的次数是m 和n 中的最大值。
3． 一个具有1025个结点的二叉树的高h 为（ ）。
A.11
B.10
C.11至1025之间
D.10至1024之间
【答案】C
【解析】当一棵树是完全二叉树时，其高度最低，此时高度为11，当一棵树的结点在一条线上时，此时最高，这时二叉树的高度是1025。
个块, 由10位表示。块内共16字节, 所以由4位表示, 于是标记位为32-10-14=18位。所以, Cache 的每一行需
4． 设栈S 和队列Q 的初始状态均为空，元素a ，b ，c ，d ，e ，f ，g 依次进入栈S. 若每个元素出
d ，c ，f ，e ，a ，g ，. 栈后立即进入队列Q ，且7个元素出队的顺序是b ，则找S 的容量至少是（ ）
A.1
B.2
C.3
D.4
【答案】C
【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序.. 在本题中，每个元素出栈S 后立即进入队列Q ，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序. 根据出桟顺序可以分析各个元素进出栈的过程：第一个出栈元素为b ，表明栈内还有元素a ，b 出栈前的深度为2；第二个出栈元素为d ，栈内元素为a 和c ，d 出栈前的深度为3；c 出栈后，剩余元素为a ，c 出栈前的深度为2；f 出栈后，剩余元素为a 和e ，f 出栈前的深度为3；e 出栈后，剩余元素为a ，e 出栈前的深度为2；a 出栈后，无剩余元素，a 出栈前的深度为1；g 出栈后，无剩余元素，g 出栈前的深度为1. 所以栈容量至少是3.
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． 某计算机的Cache 共有16块，采用2路组相联映射方式(即每组2块). 每个主存块大小为32字节，按字节编址. 主存129号单元所在主存块应装入到的Cache 组号是（ ）.
A.0
B.2
C.4
D.6
【答案】C
【解析】首先根据主存地址计算所在的主存块号，然后根据组相联映射的映射关系K ＝ImodQ(K代表Cache 的组号，I 代表主存的块号，Q 代表Cache 的组数) 来计算Cache 的组号. 由于每个主存块大小为32字节，按字节编址，那么主存129号单元所在的主存块号是4，Cache 共有16块，采用2路组相联映射方式(即每组2块) ，故Cache 有8组，按照上面的公式可以计算得到Cache 的组号＝4mod8＝4.
7． 在含有n 个关键字的小根堆(堆顶元素最小) 中，关键字最大的记录有可能存储在（ ）位置上。 A. B.
C.1 D.
【答案】D
【解析】小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于Ln/2」的结点上。
8． 已知串
A.0123
B.1123
C.1231
D.1211
【答案】A 其Next 数组值为（ ）。
【解析】KMP 算法的next 数组建立的原则
9． 下列关于RISC 的叙述中，错误的是（ ）.
A.RISC 普遍采用微程序控制器
B.RISC 大多数指令在一个时钟周期内完成
C.RISC 的内部通用寄存器数量相对CISC 多
D.RISC 的指令数、寻址方式和指令格式种类相对CISC 少
【答案】A
【解析】B 项、C 项、D 项都是RISC 的特点之一，所以它们都是正确的，只有A 项是CISC 的特点，因为RISC 的速度快，所以普遍采用硬布线控制器，而非微程序控制器.
10．假设变址寄存器R 的内容为1000H , 指令中的形式地址为2000H ; 地址1000H 中的内容为2000H , 地址2000H 中的内容为3000H , 地址3000H 中的内容为4000H , 则变址寻方式下访问到的操作数是（ ）
A.1000H
B.2000H
C.3000H
D.4000H
【答案】D
【解析】
根据变址寻址的, 变址寄存器的内容与形式地址的内容相加之后得到
相关内容
相关标签