2018年扬州大学信息工程学院834软件基础(含数据结构、操作系统)之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。
A.4
B.5
C.6
D.7
【答案】C
【解析】设度为0的结点数为x ，则度为3的树总结点数n ＝度为0的结点数＋度为1的结点数＋度为2的结点数＋度为3的结点数＝x ＋2＋l ＋2＝x ＋5；从每个结点所指向的结点数的和的角度来计算度为3的树总结点数n ＝2×3＋1×2＋2×1＋1＝11。两种方法所计算出来的n 相等，所以x ＝6。
2． 设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作（ ）。
A. 求子串
B. 判断是否相等
C. 模型匹配
D. 连接
【答案】C
【解析】常用的串的基本操作有七种，INDEX(s，t) 是其中的定位函数，这种运算就是所说的模式匹配。
3． 文件系统中，文件访问控制信息存储的合理位置是（ ）.
A. 文件控制块
B. 文件分配表
C. 用户口令表
D. 系统注册表
【答案】A
【解析】文件控制块是文件存在的标志，文件的相关信息(基本信息、存取控制信息以及使用信息) 都存储在文件控制块中，系统对文件的管理全是依靠文件控制块里的信息.
4． 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。
A.4
B.5
C.6
D.7
【答案】C
【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个(n＞0) 结点的完全二叉树的高度为或由完全二叉树类推到完全三叉树可知，n 个结点的完全三叉树的高度为
或》
5． 某计算机主频为1.2GHz , 其指令分为4类, 它们在基准程序中所占比例及CPI 如下表所示。
该机的MIPS 数是（ ）
A.100
B.200
C.400
D.600
【答案】C
【解析】基准程序的
。 , 为1200MHz , 该机器的MIPS 为计算机的主频为。
6． 对下图进行拓扑排序, 可以得到不同的拓扑序列的个数是（ ）。
图
A.4
B.3
C.2
D.1
【答案】B
【解析】拓扑排序的步骤为:
(1)在有向图中选一个没有前驱的顶点并且输出它;
(2)从图中删除该顶点和以它为尾的弧。重复上述两步, 直至全部顶点均已输出。由于没有前驱的顶点可能不唯一, 所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑排序序列, 分别为abced , abecd , aebcd 。
7． 在虚拟存储管理中, 地址变换机构将逻辑地址变换为物理地址, 形成该逻辑地址的阶段是（ ）。
A. 编辑
B. 编译
C. 链接
D. 装载
【答案】B
【解析】程序的编辑阶段一般都是程序员能够识别的高级语言或低级语言的文本, 不涉及到任何与计算机运行相关的事; 编译是由编译程序将用户源代码编译成若干个目标模块, 源地址编译成目标程序时, 会形成逻辑地址; 链接是由链接程序将编译后形成的一组目标模块, 以及所需库函数链接, 形成完整的装入模块; 装入是由装入程序将装入模块装入内存。
8． 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
A.k －1次
B.k 次
C.k+1次 D.
【答案】D
【解析】至少探测次数。
9． 下列二叉排序树中，满足平衡二叉树定义的是（ ）. 次
A. B.
相关内容
相关标签