2018年广西师范学院计算机与信息工程学院819软件工程专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 计算机硬件能够直接执行的是（ ）。
Ⅰ. 机器语言程序Ⅱ. 汇编语言程序Ⅲ. 硬件描述语言程序
A. 仅Ⅰ
B. 仅Ⅰ Ⅱ
C. 仅Ⅰ Ⅲ
D. Ⅰ Ⅱ Ⅲ
【答案】A
【解析】机器语言是计算机唯一可以直接执行的语言。汇编语言属于低级语言, 但其源程必须要翻译成目标程序成为机器语言程序后才能被直接执行。硬件描述语言是电子系统硬件行为描述、结构描述、数据流描述的语言。
2． 为实现快速排序算法, 待排序序列宜采用的存储方式是（ ）。
A. 顺序存储
B. 散列存储
C. 链式存储
D. 索引存储
【答案】A
【解析】对绝大部分内部排序而言, 只适用于顺序存储结构, 快速排序在排序过程中, 既要从后向前查找, 也要从前向后查找, 因此宜采用顺序存储。
3． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素, 则关键字的比较次数最多是（ ）。
A.4
B.5
C.6
D.7
【答案】B
【解析】
折半查找法在查找不成功时和给定值进行比较的关键字个数最多为
题中, n=16, 故比较次数最多为5。
第 2 页，共 50 页 , 在本
4． 若一棵二叉树的前序遍历序列为a , e , b , d , c , 后序遍历序列为b , c , d , e , a , 则根结点的孩子结点（ ）。
A. 只有e
B. 有e 、b
C. 有e 、c
D. 无法确定
【答案】A 。
【解析】由题目可知, 若一棵二叉树的前序遍历序列为a , e , b , d , c , 后序遍历序列为b , c , d , e , a , 其中a 为这棵二叉树的根结点, 接下来, 在前序遍历的第二个结点为e , 而后序遍历的倒数第二个结点为e , 说明a 的孩子结点只有e 。
5． 在一个文件被用户进程首次打开的过程中, 操作系统需做的是（ ）
A. 将文件内容读到内存中
B. 将文件控制块读到内存中
C. 修改文件控制块中的读写权限
D. 将文件的数据缓冲区首指针返回给用户进程
【答案】B
【解析】概念
6． 下列关于虚拟存储的叙述中, 正确的是（ ）。
A. 虚拟存储只能基于连续分配技术
B. 虚拟存储只能基于非连续分配技术
C. 虚拟存储容量只受外存容量的限制
D. 虚拟存储容量只受内存容量的限制
【答案】D 。
【解析】所谓虚拟存储, 是指运行的进程不必全部装入内存, 只需要部分装入便可以开始运行的一种技术, 在运行过程中, 当所需要的代码部分不在内存时, 通过一种技术(例如缺页中断技术) , 将所需要的页面调入内存, 从而继续运行。虚拟存储可以在较少的内存中运行较大的程序。但是需要有较大的外存以及相应的软、硬件机制配合才能实现。虚拟存储器可以连续分配也可以非连续分配, 虚拟存储器和外存大小没有关系, 所以选项中的A , B , C 都是错误的, 所以答案是D 项。
7． 已知待排序的n 个元素可分为n/k个组，每个组包含k 个元素，且任一组内的各元素均分别大干前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。 A.
B.
C.
第 3 页，共 50 页
D.
【答案】B
【解析】因组与组之间己有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时
，全部时间下界为间下界为
0 。
8． 已知字符串S 为“abaabaabacacaabaabcc ”, 模式串t 为“abaabc ”, 采用KMP 算法进行匹配, 第一次出现“失配”(
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． 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A. 顺序表
B. 双链表
C. 带头结点的双循环链表
D. 单循环链表
【答案】A
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进
行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。
10．某计算机主频为1.2GHz , 其指令分为4类, 它们在基准程序中所占比例及CPI 如下表所示。
) 时, i=j=5, 则下次开始匹配时, i 和j 的值分别是（ ）。
该机的MIPS 数是（ ）
A.100
B.200
C.400
D.600
第 4 页，共 50 页
相关内容
相关标签