2018年西安电子科技大学网络与信息安全学院833计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。
A. 线性表的顺序存储结构
B. 队列
C. 线性表的链式存储结构
D. 栈
【答案】D
【解析】用栈更合适，如果是左括号，进栈；如果是右括号，看栈顶是不是左括号，如果是，则左括号出栈；否则不配对(可以直接结束算法) 。处理完所有符号号，如果栈为空则配对成功。
2． 设n 是描述问题规模的非负整数, 下面程序片段的时间复杂度是（ ）。
A. B. C. D.
【答案】A
【解析】其中, 以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语
句, 设其执行时间为, 则有即。
3． 内部异常(内中断) 可分为故障(fault)、陷阱(trap)和终止(abort)三类。下列有关内部异常的叙述中, 错误的（ ）。
A. 内部异常的产生与当前执行指令相关
B. 内部异常的检测由CPU 内部逻辑实现
C. 内部异常的响应发生在指令执行过程中
D. 内部异常处理后返回到发生异常的指令继续执行
【答案】D
【解析】内中断分为:
①由软中断指令启动的中断; ②在一定条件下由CPU 自身启动的中断。
D 项错误, 如突然掉电引发的内中断经处理后不会继续执行。
第 2 页，共 52 页
4． 下列有关RAM 和ROM 的叙述中, 正确的是（ ）。
Ⅰ.RAM 是易失性存储器, ROM 是非易失性存储器
Ⅱ.RAM 和ROM 都采用随机存取方式进行信息访问
Ⅲ.RAM 和ROM 都可用作Cache
Ⅳ.RAM 和ROM 都需要进行刷新
A. 仅Ⅰ和Ⅱ
B. 仅Ⅱ和Ⅲ
C. 仅Ⅰ、Ⅱ和Ⅳ
D. 仅Ⅱ、Ⅲ和Ⅳ
【答案】A
【解析】RAM 中的内容断电后即丢失(易失性) , ROM 中的内容断电后不会丢失(非易失性) , 同时RAM 和ROM 都采用随机存取方式(即CPU 对任何一个存储单元的存取时间相同) , 区别在于RAM 可读可写, ROM 只读不写。而ROM 显然不可用作Cache , 也不需要刷新, 所以Ⅲ和Ⅳ的叙述都是错误的。
5． 在采用中断
A. 打印字符
B. 主存地址
C. 设备状态
D. 控制命令
【答案】B 【解析】接口的功能包括:①选址功能; ②传送命令功能; ③传送数据功能; ④反映
要的, 因此, 它不可能是CPU 和打印控制接口中的端口之间交换的信息。
6． 下列排序算法中，占用辅助空间最多的是（ ）。
A. 归并排序
B. 快速排序
C. 希尔排序
D. 堆排序
【答案】A
【解析】归并排序的辅助空间为O(n)，快速排序所占用的辅助空间为
用的辅助空间为O(1)。
，堆排序所占设备工作状态功能。A 项为数据, C 项为设备状态, D 项为命令。B 项, 主存地址在中断方式控制下是不需方式控制打印输出的情况下, CPU 和打印控制接口中的端口之间交换的信息不可能是（ ）。
第 3 页，共 52 页
7． 已知程序如下:
{
}
voidmain （ ）
{
>
}
程序运行时使用栈来保存调用过程的信息, 自栈底到桟顶保存的信息依次对应的是（ ）。
A. B. C. D.
【答案】A
【解析】函数S(int n)是一个递归函数:
①当实际参数小于等于零时则返回0, 并终止递归;
②当实际参数大于零时则递归调用S(n-1), 并将S(n-1)的结果加上n 作为返回值。程序从main （ ）函数开始, 首先调用main （ ）函数; 在main （ ）函数中调用S(1)函数时, 将main （ ）函数的上下文保存到栈中, 并进入函数S(1); 由于函数S(1)的实际参数大于零, 需要调用S(0), 故将S(1)函数的上下文保存到栈中, 进入S(0); 在S(0)中, 实际参数小于等于零, 递归终止。
8． 有关二叉树下列说法正确的是（ ）。
A. 二叉树的度为2
B. 一棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
【答案】B
【解析】树的度＝MAX(结点1的度，结点2的度，结点3的度结点n 的度) 。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。
9． 若某通信链路的数据传输速率为2400bps , 采用4相位调制, 则该链路的波特率是（ ）。
A.600波特
B.1200波特
C.4800波特
D.9600波特
【答案】B
【解析】注意无噪声下的码元速率极限值B 与信道带宽H 的关系:
第 4 页，共 52 页 , 而奈奎斯