2017年大连理工大学软件学院810数据结构和计算机组成原理之数据结构考研仿真模拟题
● 摘要
一、选择题
1． 在双向链表指针P 的结点前插入一个指针q 的结点操作是（ ）。 A. B. C. D.
【答案】C
2． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素，则关键字的比较次数最多是（ ）。
A.4
B.5
C.6
D.7
【答案】B
【解析】折半查找法在查找不成功时和给定值进行比较的关键字个数最多为（l 〇g2n ） +1，在本题中，n=16, 故比较次数最多为5。
3． 若则下列表达式采用8位定点补码运算实现时，会发生溢出的是（ ）
A.x+y
B.-x+y
C.x-y
D.-x-y
【答案】C
【解析】8位定点补码能表示的数的范围为：
码能表示的数的范围，会发生溢出
4． 下列寄存器中，汇编语言程序员可见的是（ ）。
A. 存储器地址寄存器（MAR ）
B. 程序计数器（PC ）
C. 存储器数据寄存器（MDR ）
D. 指令寄存器（IR ）
【答案】B
【解析】CPU 有5个专用寄存器，它们是程序计数器（PC ）、指令寄存器OR ）、存储器地址
第 2 页，共 56 页 A 结果为78, B结果为-128, D结果为-78都在此范围内，只有C 结果128超过了8位定点补
，这些寄存器中有些寄存器（MAR ）、 存储器数据寄存器（MBR ）和状态标志寄存器（PSWR ）
是CPU 的内部工作寄存器，对汇编语言程序员来说是透明的，在汇编语言程序设计中不会出现。但汇编语言程序员可以通过制定待执行指令的地址来设置PC 的值，所以程序计数器（PC ）对于汇编语言程序员可见的。
5． 在下列表述中，正确的是（ ）
A. 含有一个或多个空格字符的串称为空格串
B. 对个顶点的网，求出权最小的条边便可构成其最小生成树
C. 选择排序算法是不稳定的
D. 平衡二叉树的左右子树的结点数之差的绝对值不超过1
【答案】C
【解析】平衡二叉树的左右子树的深度之差的绝对值不超过1。求最小生成树时，每次挑最小权值边，是要求该边的两点都在不同的连通分量上的。
6． 以下说法错误的是（ ）。
（1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n 下，复杂度的算法在时间上总是优于复杂度的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
A. （1）
B. （1）, （2）
C. （1）, （4）
D. （3）
【答案】A
【解析】算法原地工作的含义不是指不需要任何额外的辅助，而是算法所需要的辅助空间不随着问题的规模而变化，是一个确定的值。
7． 已知三叉树T 中6个叶结点的权分别是2，3, 4, 5，6，7, T的带权（外部）路径长度最小是（ ）
A.27
B.46
C.54
D.56
【答案】B
【解析】利用三叉树的6个叶子结点的权构建最小带权生成树，
最小的带权路径长度为
第 3 页，共 56 页
8． 某字长为8位的计算机中，y 的机器数分别为已知整型变量x 、
若整型变量
A.11000000
B.00100100
C.10101010
D. 溢出
【答案】A
y 右移一位， 【解析】将x 左移一位，两个数的补码相加的机器数为1 1000000, 故答案选择A 。
9． 在一棵具有15个关键字的4阶B 树中，含关键字的结点数最多是（ ）
A.5
B.6
C.10
D.15
【答案】D
【解析】m 阶B 树非根结点含关键字个数
关键字，一共有15个关键字那么最多有15个含有关键字的结点
10．在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）
【答案】C
【解析】两个循环嵌套，那么语句x :=x＋l :
则被执行了次。
11．若线性表最常用的操作是存取第I 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（ ）。
A. 单链表
B. 双向链表
C. 单循环链表
D. 顺序表
【答案】D
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素。
12．下列有关RAM 和ROM 的叙述中，正确的是（ ）。
I.RAM 是易失性存储器，ROM 是非易失性存储器
II.RAM 和ROM 都采用随机存取方式进行信息访问
III.RAM 和ROM 都可用作Cache
第 4 页，共 56 页 则z 的机器数为（ ） 4阶B 树非根结点含关键字1〜3个，所以要使关键字结点数量最多，那么每个结点只有一个