2017年南京农业大学信息科学技术学院853计算机专业基础综合之数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。
【答案】顺序
【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。
2．
【答案】5
3． 设数组
数组中任一元素
均占内存48个二进制位，从首地址2000开始
=_____
连续存放在主内存里，主内存字长为16位，那么
（1）存放该数组至少需要的单元数是_____；
（2）存放数组的第8列的所有元素至少需要的单元数_____； （3）数组按列存储时，元素【答案】270; 27; 2204 【解析】数组的元素个数为需要
第8列有9个元素，共占
因为每个元素占内存48个二进制位，即6个字节。故总
个单元数。
个字节，因此至少需要
个单元数。由题知，每个元素占3
个字节，因为主内存字长为16位，即2个字节，所以至少需要
的起始地址是_____。
个单元。按列存储时，的起始地址为
4． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。
【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。
5． 试利用下列栈和串的基本操作完成下述填空题。
initstack （S ） 置S 为空找；
push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数；
置串 判串 返回联接
empty （st ） 判串空函数
{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。）
注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（6）（7）exp （8）
若ch 是操作数且栈非空，则形成部分中缀表达式
为空串；
是否相等的函数；
之后的串；
length （st ） 返回串st 的长度；
sub （S , i , 1） 返回S 中第i 个字符；
栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符
如ch 是运算符，则入操作符栈s 判栈8是否为空
若读出ch 是操作数且栈为空，则按出错处理
（9）exp （10）（11
）（12） 6． 中缀式运算结果为_____。
【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
7． 索引顺序文件既可以顺序存取，也可以_____存取。
【答案】随机
8． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
9． 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
10．二进制地址为011011110000，大小为
【答案】011011110100；011011100000
011011110000是块的起始地址，【解析】大小分别为式如下：
当大小为4时，起始地址
为
当大小为16时，起始地址为
：和
其伙伴块的起始地址计算公
和
块的伙伴地址分别为：_____
取栈顶操作符 操作符取出后，出栈
将pre 的最后一个字符（操作数）加入到中缀式exp 的最后 对应的前缀式为_____，若
则后缀式
的
二、选择题
11．下列选项中，在
I.
A. 仅 I 、II B. 仅 I 、III C. 仅 II 、III D.I 、II 、III
总线的数据线上传输的信息包括（ ）。
接口中的状态字III. 中断类型号
接口中的命令字
II.