2018年大连理工大学管理与经济学部810数据结构和计算机组成原理之数据结构考研核心题库
● 摘要
一、单项选择题
1． 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。
A.4
B.5
C.6
D.7
【答案】C
【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个(n＞0) 结点的完全二叉树的高度为或由完全二叉树类推到完全三叉树可知，n 个结点的完全三叉树的高度为
或》
2． 某时刻进程的资源使用情况如下表所示
此时的安全序列是（ ）。
A.P1, P2, P3, P4
B.P1, P3, P2, P4
C.P1, P4, P3, P2
D. 不存在
【答案】D
【解析】典型的死锁避免算法, 银行家算法的应用。银行家算法是操作系统中的一个重点知识单元, 考生对此应该非常熟悉, 本题并无难点。分析一下下表, 可以看到, 经过P1, P4的运行以后, 可用资源是2, 2, 1, 而P2, P3所需资源分别是1, 3, 2和1, 3, 1。所以剩余资源已经不够P2或P3的
分配, 亦即找不到能够安全运行的序列, 因此此时是处于不安全状态, 所以不存在这样的安全序列。
3． 将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.N
B.2N －1
C.2N
D.N －1
【答案】A
【解析】归并排序基本思想:归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为O(n)。
4． 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A. 顺序表
B. 双链表
C. 带头结点的双循环链表
D. 单循环链表
【答案】A
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进
行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。
5． 下列不是设计一个“好”的算法应考虑达到的目标是（ ）。
A. 可行的
B. 健壮的
C. 无二义性的
D. 可读性好的
【答案】A
【解析】设计一个“好”的算法应考虑以下目标:正确性；可读性；健壮性；效率和低存储量需求。可行性是算法的五个基本特征之一，不是一个好的算法该达到的目标。
6． 某网络拓扑如下图所示, 路由器R1
只有到达子网
（ ）。
的路由。为使R1可以将IP 分组正确地路由到图中所有子网, 则在R1中需要增加一条路由(目的网络, 子网掩码, 下一跳) 是
A.
B.
C.
D.
【答案】D
因此是 【解析】首先从题目给出的路由表项可以确定下一跳肯定是路由器R1直接相连的R2的地址, , 此时可以排除A 和B 两个选项了。进而分析路由器R2所连接的网络特点, 注意
和, 但答案选项中只有一条信息, 因此这里其连接了2
个网络分别是
用到了超网的概念, 超网是与子网类似的概念一IP 地址根据子网掩码被分为独立的网络地址和主机地址。但是, 与子网把大网络分成若干小网络相反, 它是把一些小网络组合成一个大网络一超网,
这里
和
, 那么子网掩码就是前24位是相同的,
因此所构成的超网就是即, 因此答案是D 。
7． 分区分配内存管理方式的主要保护措施是（ ）.
A. 界地址保护
B. 程序代码保护
C. 数据保护
D. 栈保护
【答案】A
【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护. 通常的界地址保护方法采用软硬件结合的方法. 考生要注意本题与虚拟存储方法的区别.
8． 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）.
A.28字节
B.216字节
C.224字节
D.232字节
【答案】C