2017年上海理工大学管理学院848数据结构及操作系统之数据结构考研强化模拟题
● 摘要
目录
2017年上海理工大学管理学院848数据结构及操作系统之数据结构考研强化模拟题（一） ... 2 2017年上海理工大学管理学院848数据结构及操作系统之数据结构考研强化模拟题（二） . 13 2017年上海理工大学管理学院848数据结构及操作系统之数据结构考研强化模拟题（三） . 24 2017年上海理工大学管理学院848数据结构及操作系统之数据结构考研强化模拟题（四） . 33 2017年上海理工大学管理学院848数据结构及操作系统之数据结构考研强化模拟题（五） . 43
一、选择题
1．
协议对
A.011111000011111010
B.011111000111110101111110 C.01111100011111010
D.011111000111111001111101 【答案】A
HDLC 协议对比特串进行组帧时，HDLC 数据帧以位模式0111 1110标识每一个帧的【解析】
开始和结束，因此在帧数据中凡是出现了 5个连续的位“1”的时候，就会在输出的位流中填充一个“0”。所以答案为A 。
2． 下列命中组合情况中，一次访存过程中不可能发生的是（ ）。
A.TLB 未命中，Cache 未命中，Page 未命中 B.TLB 未命中，Cache 命中，Page 命中 C.TLB 命中，Cache 未命中，Page 命中 D.TLB 命中，Cache 命中，Page 未命中 【答案】D
【解析】TLB （快表）和慢表（页表，Page ）构成二级存储系统，若TLB 命中，则Page 必命中。因此不可能发生的是D 选项。
3． 设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块的大小均为256字节，则可表示的单个文件最大长度是（ ）。
A.33KB B.519KB C.1057KB D.16513KB 【答案】C
【解析】4个地址项为直接地址索引，其指向的数据块大小4×256B=lKB，一级间接地址索引可以索引256/4=64个直接地址索引，故2个一级间接地址索引指向的数据块大小为2×64×256B=32KB，二级间接地址索引为256/4×256/4=4096个直接地址索引，故1个二级间接地址索引指向的数据块大小为4096×256B=1024KB, 共计1KB+32KB+1024KB=1057KB。
组帧后对应的比特串为（ ）
4． 哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（ ）方法是哈希文件的关键。
A. 哈希函数 B. 除余法中的质数 C. 冲突处理
D. 哈希函数和冲突处理 【答案】D
【解析】哈希表是根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。
5． 先序序列为a , b，c , d的不同二叉树的个数是（ ）。
A.13 B.14 C.15 D.16
【答案】B
【解析】二叉树的先序遍历定义为：若二叉树为空，则空操作；否则，访问根节点，然后先序遍历左子树，最后先序遍历右子树。本题中，结点a 为二叉树的根节点，左右子树的先序遍历可能存在下面四种情况：①左子树为空，bed 为右子树；②b 为左子树，cd 为右子树；③be 为左子树，d 为右子树；④bed 为左子树，右子树为空。然后将左右子树继续分解，如第①种情况的右子树先序遍历（bed ）可能有：a. 左子树为空，右子树为cd ；b. 左子树为c ，右子树为d ；c. 左子树为cd ，右子树为空。按照这种方法继续分解左右子树，直到不能再分解为止，可得第①和④种情况各包含5种不同情况，第②和③种情况各包含2种情况，因此总共有14种不同的二 叉树。
6． 在无噪声情况下，若某通信链路的带宽为3kHz ，采用4个相位，每个相位具有4种振幅的QAM 调制技术，则该通信链路的最大数据传输速率是（ ）。
A.12kbps B.24kbps C.48kbps D.96kbps
【答案】B
【解析】首先要根据信道有无噪声来确定是否采用奈奎斯特定理。解题难点在于离散数值的确定，先确定调制技术的码元数，此处为4个相位乘以4种振幅，共16种，即该通信链路的最大数据传输速率=2×3×
（4×4）=6×4=24kbps。
7． 对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。
A.4
B.3 C.2 D.1
【答案】B
【解析】拓扑排序的步骤为：
（1）在有向图中选一个没有前驱的顶点并且输出它；
（2）从图中删除该顶点和以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑棑序序列，分别为abced ，abecd ，aebcd 。
8． 就平均性能而言，目前最好的内排序方法是（ ）排序法。
A. 起泡 B. 希尔插入 C. 交换 D. 快速 【答案】D
【解析】快速排序的平均时间复杂度是复杂度也是
所需要的辅助存储为
仅仅表示的是一个量级，
比如
所需要的辅助存储为和
的量级都为
虽然堆排序的时间
之所以说快排
看似堆排序比快速排序的性能好，
但是需要注意
最好，是在综合考虑的情况下。
9． 若无向图G= （V , E）中含7个顶点，则保证图G 在任何情况下都是连通的，则需要的边数最少是（ ）。
A.6 B.15 C.16 D.21
【答案】C
【解析】要保证无向图G 在任何情况下都是连通的，即任意变动图G 中的边，G 始终保持连通。首先需要图G 的任意6
个结点构成完全连通子图然后再添加一条边将第7个结点与
需
条边，
连接起来，共需16条边。本题非常容易错误地选择选项A ，
主要原因是对“保证图G 在任何情况下都是连通的”的理解，分析选项A ，在图G 中，具有7个