2018年北京联合大学制造业信息化技术801计算机综合之数据结构考研核心题库
● 摘要
一、填空题
1． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4；2
2． 求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】
3． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构(网状结构)
4． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。 【答案】；边稀疏
5． 已知链队列的头尾指针分别是f 和r ，则将值x 入队的操作序列是_____。
【答案】S ＝(LinkedList*)malloc(sizeof (LNode))；s ﹣＞data ＝x ；s ﹣＞next ＝r ﹣＞next ；r ﹣＞next ＝s ；r ＝s ；
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
二、单项选择题
6． 下述二叉树中，哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。
A. 二叉排序树
B. 哈夫曼树
C.A VL 树
D. 堆
【答案】D
【解析】堆的定义:
n 个关键字序列K 1，K 2，... ，K n 称为堆，当且仅当该序列满足如下性质(简称为堆性质) :
(1)
(2)
且且或
满足第(1)种情况的堆，称为小顶堆；满足第(2)种情况的堆，称为大顶堆。
由堆的定义可知堆可以满足上述性质。
7． 设文件索引节点中有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.
8． 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。
A.push ，pop ，push ，pop ，push ，pop
B.push ，push ，push ，pop ，pop ，pop
C.push ，push ，，pop ，pop ，push ，pop
D.push ，pop ，push ，push ，pop ，pop
【答案】B
【解析】根据输入序列和输出序列可知，输入序列全部进找，然后再出找。从中可以看出，push 的数目始终大于等于pop 的数目。
9． 若用户进程访问内存时产生缺页, 则下列选项中, 操作系统可能执行的是（ ）
Ⅰ. 处理越界错
Ⅱ. 置换页
Ⅲ. 分配内存
A. 仅Ⅰ、Ⅱ
B. 仅Ⅱ、Ⅲ
C. 仅Ⅰ、Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
【答案】B
【解析】用户进程访问内存时缺页会发生缺页中断。发生缺页中断, 系统地执行的操作可能是置换页面或分配内存。系统内没有越界的错误, 不会进行越界出错处理。
10．下列选项中, 用于设备和控制器(接口) 之间互连的接口标准是（ ）
A.PCI
B.USB
C.AGP
D.
【答案】B
【解析】设备和设备控制器之间的接口是USB 接口, 其余选项不符合, 故答案为B 。
11．对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。
A.n
B.n ﹣2
C.n ﹣1
D.n ＋1
【答案】c
【解析】每个结点(除根节点外) 都是一个分支，即所有结点的度数之和等于分支个数等于总的结点数减一，即n ﹣1。
12．若某单处理器多进程系统中有多个就绪态进程, 则下列关于处理机调度的叙述中, 错误的是（ ）。
A. 在进程结束时能进行处理机调度
B. 创建新进程后能进行处理机调度
C. 在进程处于临界区时不能进行处理机调度
D. 在系统调用完成并返回用户态时能进行处理机调度
【答案】C 。
【解析】对于A 、B 、D 显然是可以进行处理机调度的, 对于C , 当进程处于临界区时, 只要不破坏临界资源的使用规则, 是不会影响处理机调度的, 比如, 通常访问临界资源可能是慢速的外设(如打印机) , 如果在进程访问打印机时, 不能处理机调度, 那么系统的性能将是非常低的。几种不进行处理机调度的情况如下:
①在处理机中断的过程中;
②进程在操作系统内核程序临界区中;
③其他需要完全屏蔽中断的原子操作过程中。
13．分区分配内存管理方式的主要保护措施是（ ）.
A. 界地址保护
B. 程序代码保护
C. 数据保护
D. 栈保护
【答案】A
【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护. 通常的界地址保护方法采用软硬件结合的方法. 考生要注意本题与虚拟存储方法的区别.