2017年安徽理工大学计算机科学与技术841数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 下面关于串的叙述中，不正确的是（ ）。
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
【答案】B
【解析】
空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。
2． 对于循环队列（ ）。
A. 无法判断队列是否为空
B. 无法判断队列是否为满
C. 队列不可能满
D. 以上说法都不是
【答案】D
【解析】循环队列也会出现队列满的情况，并且循环队列也可以判断是否为空或满。至少可以通过两种方法进行判断：①另设一个布尔变量来区别队列是空还是满；②队满时，（rear+1）==font。
3． 在一株高度为2的5阶B 树中，所含关键字的个数最少是（ ）
A.5
B.7
C.8
D.14
【答案】A
【解析】根据B 树的定义可知，跟结点最少含有个关键字，高度为2的阶B 树最少有（5-1）+1=5个关键字，其中根节点含有个关键字，第2层结点含有1关键字。
4． 下列关于虚拟存储的叙述中，正确的是（ ）。
A. 虚拟存储只能基于连续分配技术
B. 虚拟存储只能基于非连续分配技术
C. 虚拟存储容量只受外存容量的限制
D. 虚拟存储容量只受内存容量的限制
【答案】D 。
【解析】所谓虚拟存储，是指运行的进程不必全部装入内存，只需要部分装入便可以开始运行的一种技术，在运行过程中，当所需要的代码部分不在内存时，通过一种技术（例如缺页中断
，技术）将所需要的页面调入内存，从而继续运行。虚拟存储可以在较少的内存中运行较大的程序。但是需要有较大的外存以及相应的软、硬件 机制配合才能实现。虚拟存储器可以连续分配也可以非连续分配，虚拟存储器和外存大小没有关系，所以选项中 的A ，B ，C 都是错误的，所以答案是D 项。
5． 下列关于RISC 的叙述中，错误的是（ ）。
A.RISC 普遍采用微程序控制器
B.RISC 大多数指令在一个时钟周期内完成
C.RISC 的内部通用寄存器数量相对CISC 多
D.RISC 的指令数、寻址方式和指令格式种类相对CISC 少
【答案】A
【解析】B 项、C 项、D 项都是RISC 的特点之一，所以它们都是正确的，只有A 项是CISC 的特点，因为RISC 的速度快，所以普遍采用硬布线控制器，而非微程序控制器。
6． 下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是（ ）。
A.24，10，5 和24，10，7
B.24，10，5 和24，12，7
C.24，10，10和24，14，11
D.24，10，10和 24，14，6
【答案】D
【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中，第二个被访问的两个结点的权值要么相等，要么和为根节点的权值，故B 项错误。同理，通过第三个被访问的节点排除A 项。C 项，由两条路径可推出三个叶子节点的权值分别是：3、10和11，而根据哈夫曼树的定义可知，权值为3的节点应该和权值为10的结点结合，故C 项错误。D 项，反推出有四个叶子节点，权值分别为：5、5、6和8，满足哈夫曼树的条件。
7． 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。
【答案】B
【解析】堆排序需要一个空间用于交换，因此堆排序所需要的附加存储空间为
8． 设置当前工作目录的主要目的是（ ）。
A. 节省外存空间
B. 节省内存空间
C. 加快文件的检索速度
D. 加快文件的读/写速度
【答案】C
【解析】工作目录只是指出了当前操作的默认目录，使得在每次访问的时候不需要由根目录
一层一层地解析，在文件路径比较长时，可以节省许多解析的时间，从而加快了文件的检索速度。
9． 静态链表中指针表示的是（ ）。
A. 下一元素的地址
B. 内存储器的地址
C. 下一元素在数组中的位置
D. 左链或右链指向的元素的地址
【答案】C
【解析】静态链表的一般结构为：
这种结构是预先分配一个较大的空间，类似于一次申请一个较大的数组，但是元素的增删操作都不会移动元素，只需要移动next 成员就行。因此，静态链表中的指针实际上表示的就是下一个元素在数组中的位置。
10．对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是:（ ）
A.05，46，13，55，94，17，42
B.05，13，17，42，46，55.94
C.42，13，94，05，55，46，17
D.05，13，46，55，17，42，94
【答案】C
【解析】基数排序有两种：最低位优先和最高位优先。
最低位优先的过程
先按最低位的值对记录进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向高位，每趟都是根据关键字的一位并在前一趟的基础上对所有记录进行排序，直至最高位，则完成了基数排序的整个过程。
以r 为基数的最低位优先排序的过程 假设线性表由结点序列
组成，
其中
分配：开始时，把
收集：把
的线性表。
构成，每个结点aj 的关键字由d 元组（k ，k... ，k ，k ）在排序过程中，使用r 个队列排序过程就是对i=0，1，... ，d-1，依次做一次“分配”和“收集”。 各个队列置成空队列，然后依次考察线性：表中的每一个结队列中。 各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新点（==0.1，... ，n-1）。如果的关键字k=k，就把放进
相关内容
相关标签