2016年沈阳建筑大学信息科学与工程学院数据结构(同等学力加试)复试笔试最后押题五套卷
● 摘要
一、选择题
1． 对线性表进行折半查找时，要求线性表必须（ ）。
A. 以顺序方式存储B. 以顺序方式存储，且数据元素有序
C. 以链接方式存储D. 以链接方式存储，且数据元素有序
答:B
【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
2． 已知循环队列存储在一维数组中，且队列非空时front 和rear 分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front 和rear 的值分别是（ ）。
A.0, 0
B.0, n-1
C.n-1, 0
D.n-1, n-1
答:B
【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素，若初始时队列为空，且要求第1 个进入队列的元素存储在A[0]处，则此时front 和rear 的值都为0。由于进队操作要执行（rear+1） % n，则初始 时front 的值为0、rear 的值为n-1。
3． 已知一算术表达式的中缀表达式为其后缀形式为（ ）。
答:D
【解析】后缀表达式：在程序语言中，运算符位于两个操作数后面的表达式。
4． 冯. 诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是（ ）。
A. 指令操作码的译码结果
B. 指令和数据的寻址方式
C. 指令周期的不同阶段
D. 指令和数据所在的存储单元
答:C
【解析】在冯•诺依曼结构计算机中指令和数据均以二进制形式存放在同一个存储器中，CPU 可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，其他阶段（分析取数阶段、执行阶段）取出的是数据。所以，CPU 区分指令和数据的依据是指令周期的不同阶段。
5． 若串
A.8
B.37
C.36
D.9
答:B 其子串的数目是（ ）。
【解析】子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为
长为长为n 的子串有1个，长为的子串有2个，的子串有3个，……，长为1的子串有n 个。由于空串是任何串的子串，所以本题的答案为：故选B 。
6． 设有两个串S1和S2, 求S2在S1中首次出现的位置的运算称作（ ）。
A. 求子串
B. 判断是否相等
C. 模型匹配
D. 连接
答:C
【解析】常用的串的基本操作有七种，INDEX （s ，t ）是其中的定位函数，这种运算就是所说的模式匹配。
7． 在系统总线的数据线上，不可能传输的是（ ）。
A. 指令
B. 操作数
C. 握手（应答）信号
D. 中断类型号型号
答:C
【解析】握手（应答）信号属于通信联络控制信号应该在通信总线上传输，不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。
8． 若系统S1采用死锁避免方法，S2采用死锁检测方法，下列叙述中正确的是（ ）。
I . S1会限制用户申请资源的顺序
II. S1需要进行所需资源总量信息，而S2不需要
III. S1不会给可能导致死锁的进程分配资源，S2会
A. 仅
B. 仅
C. 仅
D.
答:
【解析】死锁避免的策略是：必须知道将来的资源需求，以寻找可能的安全允许顺序，如果不存在安全序列就阻塞；死锁检测的策略是：只要允许就分配资源，它指定期检查死锁是否已经发生，如果发生就通过剥夺解除死锁。两种方式都需要所需资源的总量信息，但S1是用于在分配资源时判断是否会导致死锁，而S2是用于检测是否出现死锁。
9． 当字符序列作为图输入时，输出长度为3的且可用作C 语言标识符的序列的有（ ） 。
A.4个
B.5个
C.3个
D.6个
图
答:C
【解析】首先需要明白C 语言标识符的命名规则。数字不能作为标识符的开头，因此第一个字符只能为t 或者下划线。若首字符为t , 有两种结果若首字符为则只有一种结果因此总共有3种结果。
10．采用指令Cache 与数据Cache 分离的主要目的是（ ）
A. 减低Cache 的缺失损失
B. 提高Cache 的命中率
C. 减低CPU 平均访问时间
D. 减少指令流水线资源冲突
答:D
【解析】指令流水线不会断流，预取过来的都是指令
二、填空题