2017年华侨大学计算机科学与技术学院850数据结构与C++[专业硕士]考研强化模拟题
● 摘要
一、填空题
1． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
2． 文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
3． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
4． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。
【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
5． 在n 个顶点的非空无向图中，最多有_____个连通分量。
【答案】n
【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。
6． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
【答案】（1）（2）
链表未到尾就一直进行
将当前结点作为头结点后的第一元素结点插入
7． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。
【答案】n （n-l ）/2
【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。
8． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
【解析】本题是在哈希表ht[]中插入值为的元素，如该元素已在哈希表中，报告出错。
9． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
10．在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
二、选择题
11．下列选项中，不属于网络体系结构中所描述的内容是（ ）。
A. 网络的层次 B. 每一层使用的协议 C. 协议的内部实现细节 D. 每一层必须完成的功能 【答案】C
【解析】体系结构仅规定协议的功能和消息格式，但对具体的实现细节由具体设备厂商来确定，对于网络的层次，以及每一个层次的协议及其功能都是网络体系结构所要描述的内容，因此答案为选项C 。
12． 在子网192.168.4.0/30中，能接收目的地址为192.168.4.3的IP 分组的最大主机数是（ ）。
A.0 B.1 C.2 D.4
【答案】C
【解析】每个子网中忽略子网内全为0和全为1的地址剩下的就是有效主机地址，本题中由于子网的比特数是30, 因此用于主机的只有2位，即00, 01, 10, 11，有效主机地址是2个，这里192.168.4.3显然是其广播地址，因此答案是C 。
13．相对于微程序控制器，硬布线控制器的特点是（ ）。
A. 指令执行速度慢，指令功能的修改和扩展容易 B. 指令执行速度慢，指令功能的修改和扩展难 C. 指令执行速度快，指令功能的修改和扩展容易 D. 指令执行速度快，指令功能的修改和扩展难 【答案】D
【解析】在同样的半导体工艺条件下，硬布线（组合逻辑）控制器的速度比微程序控制器的速度快。这是因为硬布线控制器的速度主要取决于逻辑电路的延迟，而微程序控制器增加了一级控制存储器，执行的每条微指令都要从控制存储器中读取，影响了速度。由于硬布线控制器一旦设计完成就很难改变，所以指令功能的修改和扩展难。因此，硬布线控制器的特点是指令执行速度快，指令功能的修改和扩展难。
14．系统为某进程分配了4个页框，该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下一页的页号为7，依据LRU 算法，应淘汰页的页号是（ ）。
A.2 B.3 C.4 D.8
【答案】B
【解析】LRU 置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框，题中访问过程中页框的变化如下：
序列：页框：
淘汰：3。
访问页号为7的页时，内存中存在的页的页号是：3、8、4和5，根据LRU 定义应淘汰的是
相关内容
相关标签