2022年西北民族大学电气工程学院849计算机学科专业基础之数据结

目录

2017年西北民族大学电气工程学院849计算机学科专业基础之数据结构考研仿真模拟题（一） (2)

2017年西北民族大学电气工程学院849计算机学科专业基础之数据结构考研仿真模拟题（二） (12)

2017年西北民族大学电气工程学院849计算机学科专业基础之数据结构考研仿真模拟题（三） (24)

2017年西北民族大学电气工程学院849计算机学科专业基础之数据结构考研仿真模拟题（四） (34)

2017年西北民族大学电气工程学院849计算机学科专业基础之数据结构考研仿真模拟题（五） (44)

第1 页，共53 页

第 2 页，共 53 页 2017年西北民族大学电气工程学院849计算机学科专业基础之数据结构考研仿真模

拟题（一）

说明：①本资料为VIP 学员内部使用，严格按照2017考研最新题型及历年试题难度出题。

——————————————————————————————————————————

一、选择题

1． —次总线事物中，主设备只需给出一个首地址，从设备就能从首地址开始的若干连续单元格读出或写入的个数，这种总线事务方式称为（ ）

A.并行传输

B 串行传输

C.突发

D.同步

【答案】C

【解析】猝发数据传输方式：在一个总线周期内传输存储地址连续的多个数据字的总线传输方式

2． 设二维数组（即m 行n 列）按行存储在数组

中，

则二维数组元素在一维数组B 中的下标为（ ）。

【答案】A

【解析】

前

的元素个数为

所以二维数组元素在一维数组B

中的下标为需要注意数组B 的下标是从0开始，还是从1开始。

3． 一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。

A.其中任意一个结点均无左孩子

B.其中任意一个结点均无右孩子

C.其中只有一个叶结点

D.其中度为2的结点最多为一个

【答案】C

【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A 项或B 项都不全。

4． 响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（ ）。

I.开关中断II.保存通用寄存器的内容III.形成中断服务程序入口地址并送PC

A.仅I 、II

B.仅 I 、III

第 3 页，共 53 页 C.仅 II 、III

D.I 、II 、III

【答案】B 。

【解析】中断隐指令完成的操作有3个：①保存断点；②关中断；③引出中断服务程序（形成中断服务程序入口地址并送PC ）。而保存通用寄存器内容的操作是由软件来实现，不是由中断隐指令实现的。

5． 以下与数据的存储结构无关的术语是（ ）。

A.循环队列

B.链表

C.哈希表

D.栈

【答案】D

【解析】循环队列体现线性表是以顺序存储。用散列法存储的线性表称散列表。链表说明线性表是以链式结构存储的。栈不能体现出是顺序还是链式存储结构。

6． 假设某计算机按字编址，Cache 有4个行，Cache 和主存之间交换的块大小为1个字。若Cache 的内容初始为空，采用2路组相联映射方式和LRU 替换算法，当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4， 8时，命中Cache 的次数是（ ）。

A.1

B.2

C.3

D.4

【答案】C 。

【解析】Cache 有4个行，2路组相联，即Cache 被分成2组，每组2行。主存地址为0?1、4?5、8?9 可映射到第0组Cache 中，主存地址为2?3、6?7可映射到第1组Cache 中。Cache 初始为空，采用LRU 替换算法，当访问主存的10个地址依次为0, 4，8, 2, 0, 6，8, 6, 4, 8时，命中Cache 的次数共有3次，分别发生在第7、8和10步时。

7． 有个分支结点的满二叉树的深度是（ ）。

A.

B.

C.

D.

【答案】C

【解析】满二叉树的结点总数=分支的结点总数+非分支的结点总数。由于此树为满二叉树，所以非分支的结点总数为1，所以满二叉树共有

个结点，所以满二叉树的深度为

第 4 页，共 53 页 8． 已知字符串S 为“abaabaabacacaabaabcc ”，模式串t 为“abaabc ”，采用KMP 算法进行匹配，第一次出现“失配” （

），i=j = 5，则下次开始匹配时，i 和j 的值分别是（ ）。

A.i=l ，j=0

B.i=5，j=0

C.i=5，j=2

D.i=6，j=2

【答案】C 【解析】模式匹配（KMP ）算法对普通的暴力匹配的改进在于：每当匹配过程中匹配失败时，主串（本题为S ）的指针（i ）不需要回溯，而是利用已经得到的“部分匹配”的结果将模式串（t ）向右“滑动”尽可能远的一段距离后，继续进行比较。模式串“滑动”的距离是由模式串（t ）本身决定的，即t

的子串中前缀串和后缀串相等的最长长度。本题中第一次失配i=5,字串为“abaab”，其相等且最长的前后缀为“ab”，一次下一个j = 2。

9． 下列给出的指令系统特点中，有利于实现指令流水线的是（ ）。

I.指令格式规整且长度一致

II.指令和数据按边界对齐存放

III.只有Load / Store 指令才能对操作数进行存储访问

A.

仅

B.

仅

C.

仅

D.

【答案】D

【解析】特点I 和III 都是RISC 机的特征，而特点II 则有利于指令和数据的存放，所以以上三个特点都有利于实现指令流水线。

10．在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。

【答案】B

【解析】二分查找的时间复杂度为在一个用N 个元素的有序单链表中查找具有给定关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，

因此时间复杂度为

11．下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。

A.二叉排序树

B.哈夫曼树

C.树

本文来源：https://www.bwwdw.com/article/tfvl.html