2018年郑州大学产业技术研究院945软件工程专业基础综合之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 某队列允许在其两端进行入队操作, 但仅允许在一端进行出队操作, 元素a , b , c , d , e 依次入此队列后再进行出队操作, 则不可能得到的出队序列是（ ）。
A.b , a , c , d , e B.d , b , a , c , e C.d , b , c , a , e D.e , c , b , a , d
【答案】C
【解析】根据题意, 队列两端都可以输入数据元素, 但是只能在一端输出数据元素, 这种队列为 输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队, 从而得出不可能的情况。
假设L 代表从左端入队, R 代表从右端入队, 出队都是从左端L 出。四个选项所给序列的进队操作序列分别为:
选项A.aL(或aR) , bL , cR , dR , eR 选项B.aL(或aR) , bL , cR , dL , eR 选项C. 不可能出现选项
D.aL(或aR) , bL , cL , dR , eL
2． 某计算机的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.
3． 一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。
A.107 B.108
C.214 D.215
【答案】B
【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有n0＝n2＋+l，所以215＝n0＋n2＝2*n2＋l ，n2＝107，n0＝108。也就是说若对其进行哈夫曼编码，共能得到108个码字。
4． 下列关于SMTP 协议的叙述中, 正确的是（ ）
Ⅰ. 只支持传输7比特ASC Ⅱ码内容 Ⅱ. 支持在邮件服务器之间发送邮件 Ⅲ. 支持从用户代理向邮件服务器发送邮件 Ⅳ. 支持从邮件服务器向用户代理发送邮件 A. 仅Ⅰ、Ⅱ和Ⅲ B. 仅Ⅰ、Ⅱ和Ⅳ C. 仅Ⅰ、Ⅲ和Ⅳ D. 仅Ⅱ、Ⅲ和Ⅳ 【答案】A
【解析】根据下图可知, SMTP 协议支持在邮件服务器之间发送邮件, 也支持从用户代理向邮件服务器发送信息。SMTP 协议只支持传输7比特的ASC Ⅱ码内容
图
5． 假设磁头当前位于第105道，正在向磁道序号增加的方向移动. 现有一个磁道访问请求，序列为35，45，12，68，110，180，170，195，采用SCAN 调度(电梯调度) 算法得到的磁道访问序列是（ ）.
A.110， 170， 180， 195， 68， 45， 35， 12 B.110， 68， 45， 35， 12， 170， 180， 195 C.110， 170， 180， 195， 12， 35， 45， 68 D.12， 31， 45， 68， 110， 170， 180， 195
【答案】A
【解析】SCAN 算法类似电梯工作原理，即朝一个固定方向前进，经过的磁道有访问请求则马上服务，直至到达一端顶点，再掉头往回移动以服务经过的磁道，并这样在两端之间往返. 因此，当磁头从105道向序号增加的方向移动时，便会服务所有大于105的磁道号(从小到大的顺序) ；
往回返时又会按照从大到小的顺序进行服务. 注意与循环扫描算法的区别，所以SCAN 算法的访问序列是：110， 170， 180， 195， 68， 45， 35， 12
6． 给定二叉树如下图所示. 设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树. 若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）.
A.LRN B.NRL C.RLN
D.RNL
图
【答案】D
【解析】对“二叉树”而言，一般有三条搜索路径： ①先上后下的按层次遍历； ②先左(子树) 后右(子树) 的遍历； ③先右(子树) 后左(子树) 的遍历.
其中第1种搜索路径方式就是常见的层次遍历，第2种搜索路径方式包括常见的先序遍历NLR 、中序遍历LNR 、后序遍历LRN ，第3种搜索路径方式则是不常使用的NRL 、RNL 、RLN. 本题考查的是第3种搜索路径方式的一种情况. 根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D.
7． 已知有向图G=(V，E) , 其中
G 的拓扑序列是（ ）。 A. B. C. D.
【答案】A 拓扑序列的条件:若在顶
点
,
能被称为必须排
【解析】设G=(V，E) 是一个具有n 个顶点的有向图，V 中顶点序列
是图中的边(即从顶点。
到有一条路径) ，则在序列中顶点
之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列
是