2017年江苏大学计算机科学与通信工程学院851数据结构考研题库
● 摘要
一、选择题
1． 在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）
【答案】C
【解析】两个循环嵌套，那么语句x :=x＋l :
则被执行了次。
2． 若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（ ）。
A. 存在，且唯一 B. 存在，且不唯一不唯一 C. 存在，可能不唯一 D. 无法确定是否存在 【答案】C 。
【解析】图的基本应用——拓扑排序，用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，说明该图为有向无环图，所以其拓扑序列存在，但不一定唯一，如图的邻接矩阵为则存在两个拓扑序列。
3． 执行完下列语句段后，f 值为（ ）。
A.2 B.4 C.8
D. 无限递归 【答案】B
【解析】该程序使用了递归调用，由题知，
所以结果为4。
4． 某计算机主存地址空间大小为256MB , 按字节编址。虚拟地空间大小为4GB ，采用页式存储管理，页面大小为4KB ，TLB （快表）采用全相联映射，有4个页表项，内容如下表所示。
则对虚拟地址03FFF180H 进行虚实地址变换的结果是（ ） A.0153180H B.0035180H C.TLB 缺失 D. 缺页 【答案】A
【解析】虚拟地址为03FFF180H ，其中页号为03FFFH , 页内地址为180H ，根据题目中给出的页表项可知页标记为03FFFH 所对应的页框号为0153H , 页框号与页内地址之和即为物理地址015 3180H。
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. 串既可以采用顺序存储，也可以采用链式存储 【答案】B
【解析】
空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。
7． 和顺序栈相比，链栈有一个比较明显的优势是（ ）。
A. 通常不会出现找满的情况 B. 通常不会出现栈空的情况 C. 插入操作更容易实现 D. 删除操作更容易实现 【答案】A
8． 设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，储地址为1，每个元素占一个地址空间，则
A.13 B.33 C.18 D.40
【答案】B
【解析】对于对称矩阵，
的地址为（ ）。
为第一元素，其存
为了节省存储空间，为多个相同的元素只分配一个存储空间。
时，
当
时，
其
对于对称矩阵，元素下表之间的对应关系为：当
中k 相当于地址空间的标号，i 为行号，j 为列号。因为第一个元素存储地址为1，所以最后计算 的k 需要加1。所以
的存储位置为
9． 下列关于中断方式和DMA 方式比较的叙述中，错误的是（ ）
A. 中断
方式请求的是方式请求的是CPU 处理时间，DMA 方式请求的是总线使用权
B. 中断响应发生在一条指令执行结束后，中断响应发生在一条指令执行结束后，DMA 响应发生在一个总线事务完成后
C. 中断D. 中断部设备
【答案】D
【解析】中断处理方式:在与
设备输入每个数据的过程中，由于无需CPU 干预，因而可使CPU
设备并行工作。仅当输完一个数据时，才需CPU 花费极短的时间去做些中断处理。因此中
方式下数据传送通过软件完成，方式下数据传送通过软件完成，DMA 方式下数据方式适用于所有外部设备，方式适用于所有外部设备，DMA 方式仅适用于快速外
传送由硬件完成
断申请使用的是CPU 处理时间，发生的时间是在一条指令执行结束之后，数据是在软件的控制下完成传送。而DMA 方式与之不同。DMA 方式：数据传输的基本单位是数据块，即在CPU 与设备之间，每次传送至少一个数据块，DMA 方式每次申请的是总线的使用权，所传送的数据是从设备直接送入内存的或者相反；仅在传送一个或多个数据块的开始和结束时，才需 CPU 干预，整块数据的传送是在控制器的控制下完成的。答案D 的说法不正确。
10．若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则X 的前驱为（ ）。
A.X 的双亲