2018年西北民族大学电气工程学院849计算机学科专业基础之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 已知广义表LS ＝((a，b ，c) ，(d，e ，f)) ， 用head 和tail 数取出LS 中原子e 的运算是（ ）。
A.head(tail(LS))
B.tail(head(LS))
C.head(tail(head(tail(LS)))
D.head(tail(tail(head(LS))))
【答案】C
【解析】head 操作就是得到广义表中第一个的原子。tail 操作就是得到除第一个原子外剩下元素构成的表。tail(LS)得到((d，e ，f)) ，head(tail(LS))得到(d，e ，f)tail(head(tail(LS)))得到(e，f) ，head(tail(head(tail(LS))) 得到e 。
2． 在OSI 参考模型中，自下而上第一个提供端到端服务的层次是（ ）.
A. 数据链路层
B. 传输层
C. 会话层
D. 应用层
【答案】B
【解析】题目中指明了这一层能够实现端到端传输，也就是端系统到端系统的传输，数据链路层主要负责传输路径上相邻结点间的数据交付，这些结点包括了交换机和路由器等数据通信设备，这些设备不能被称为端系统，因此数据链路层不满足题意. 题目中指明了这一层能够实现传输，会话层只是在两个应用进程之间建立会话而已，应用层只是提供应用进程之间通信的规范，都不涉及传输. 所以本题答案应该是B 项. 在OSI 模型中网络层提供的是主机到主机的通信服务.
3． 假设变址寄存器R 的内容为1000H , 指令中的形式地址为2000H ; 地址1000H 中的内容为2000H , 地址2000H 中的内容为3000H , 地址3000H 中的内容为4000H , 则变址寻方式下访问到的操作数是（ ）
A.1000H
B.2000H
C.3000H
D.4000H
【答案】D
【解析】
根据变址寻址的
操作数的实际地址,
由题可知
, 变址寄存器的内容与形式地址的内容相加之后得到, 根据实际地址访问内存, 获取操作数
4000H 。
4． 下面关于B 和B+树的叙述中，不正确的是（ ）
A.B 树和B+树都是平衡的多叉树
B.B 树和B+树都可用于文件的索引结构
C.B 树和B+树都能有效地支持顺序检索
D.B 树和B+树都能有效地支持随机检索
【答案】C
【解析】B 树是一种平衡的多分树，通常我们说m 阶的B 树，它必须满足如下条件:①每个结点至多有m 个子结点；②除根结点和叶结点外，其它每个结点至少有个子结点；③若根结点不是叶子结点，则至少有两个子结点；④所有的叶结点在同一层；⑤有k 个子结点的非根结点恰好包含k －1个关键码。B+树是B 树的一种变形树，它与B 树的差异在于:有k 个子结点的结点必然有k 个关键码；非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。其中B 树适合与随即检索，不适合于顺序检索，所以C 项错误。
5． 将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.N
B.2N －1
C.2N
D.N －1
【答案】A
【解析】归并排序基本思想:归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为O(n)。
6． 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
A.(100, 80, 90, 60, 120, 110, 130)
B.(100, 120, 110, 130, 80, 60，90)
C.(100, 60, 80, 90, 20, 110, 130)
D.(100, 80, 60, 90, 120, 130, 110)
【答案】C
【解析】二叉排序树:左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。
7． 若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）.
A.. 起泡排序
B. 插入排序
C. 选择排序
D. 二路归并排序
【答案】B
【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B 项插入排序的结果是前三个数有序即可；C 项选择排序结果是两个最小的元素在最前面按顺序排好；D 项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序. 显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B 项正确.
8． 某计算机系统中有8台打印机，由K 个进程竞争使用，每个进程最多需要3台打印机. 该系统可能会发生死锁的K 最小值是（ ）.
A.2
B.3
C.4
D.5
【答案】C
【解析】死锁的抽屉原理一般描述是：将5个苹果放进4个抽屉，那么，必然有1个抽屉中至少有2个苹果. 计算机系统的资源分配充分体现了这一原理. 考察进程运行的特点，只要有一个进程能够运行，则运行结束后必然会归还资源，其余的进程也就会得到满足从而可以执行(这里考虑的资源主要是可重用的资源，不可重用的资源会消失，就不可用上述方法分析). 所以最少需要4个进程竞争使用，每个进程占用2台打印机，此时会产生死锁.
9． 内部异常(内中断) 可分为故障(fault)、陷阱(trap)和终止(abort)三类。下列有关内部异常的叙述中, 错误的（ ）。
A. 内部异常的产生与当前执行指令相关
B. 内部异常的检测由CPU 内部逻辑实现
C. 内部异常的响应发生在指令执行过程中
D. 内部异常处理后返回到发生异常的指令继续执行
【答案】D
【解析】内中断分为:
①由软中断指令启动的中断; ②在一定条件下由CPU 自身启动的中断。
D 项错误, 如突然掉电引发的内中断经处理后不会继续执行。
10．在一个文件被用户进程首次打开的过程中, 操作系统需做的是（ ）
A. 将文件内容读到内存中
B. 将文件控制块读到内存中
C. 修改文件控制块中的读写权限
D. 将文件的数据缓冲区首指针返回给用户进程