2018年东北农业大学电气与信息学院838数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． —个栈的入栈序列为1, 2, 3, ……, n , 其出栈序列是
取值的个数是（ ） A. B. C.
D. 无法确定
【答案】C
【解析】除了3本身以外, 其他的值均可以取到, 因此可能取值的个数为n-1。
2． 在下面的排序方法中，辅助空间为O(n)的是（ ）。
A. 希尔排序
B. 堆排序
C. 选择排序
D. 归并排序
【答案】D
3． 一个C 语言程序在一台32位机器上运行. 程序中定义了3个变量x 、Y 和z ，其中x 和z 为int
Y 为short 型. 当x ＝127，Y ＝-9时，x 、Y 和z 的值分别是. 型，执行赋值语句z ＝x ＋Y 后，（ ）
A.x ＝0000007FH ， Y ＝FFF9H ， z ＝00000076H
B.x ＝0000007FH ， Y ＝FFF9H ， z ＝FFFF0076H
C.x ＝0000007FH ， Y ＝FFF7H ， z ＝FFFF0076H
D.x ＝0000007FH ， Y ＝FFF7H ， z ＝00000076H
【答案】D
【解析】当两个不同长度的数据，要想通过算术运算得到正确的结果，必须将短字长数据转换成长字长数据，这被称为“符号扩展”.例如，x 和z 为int 型，数据长32位，Y 为short 型，数据长16位，因此首先应将y 转换成32位的数据，然后再进行加法运算.
运算采用补码的形式，而x 的补码是0000007FH ，Y 的补码是FFFFFFF7H ，所以x ＋Y ＝00000076H.
4． 某计算机存储器按字节编址, 采用小端方式存放数据。假定编译器规定int 和short 型长度分别为32位和16位, 并且数据按边界对齐存储。某C 语言程序段如下:
第 2 页，共 62 页 。若, 则, 则可能
若record 变量的首地址为0xC008, 则地址A. B. C. D.
【答案】D 。 中内容及的地址分别为（ ）。 32位整数a 需要占4个字节, 16位整数c 需要占2个字节, 而字符数据b 占一个字节。【解析】
a=273, 转换成十六进制是111H , 采用小端方式存放数据, 地址
边界对齐存储,
地址
中存放c 。
5． 下列有关总线定时的叙述中, 错误的是（ ）。
A. 异步通信方式中, 全互锁协议最慢
B. 异步通信方式中, 非互锁协议的可靠性最差
C. 同步通信方式中, 同步时钟信号可由多设备提供
D. 半同步通信方式中, 握手信号的采样由同步时钟控制
【答案】C
A 项正确, 异步通信方式中, 全互锁协议最慢, 主从模块都需要等待确认后才能撤销其【解析】
信号; B 项正确, 异步通信方式中, 非互锁协议没有相互确认机制, 因此可靠性最差; C 项错误, 同步通信要遵循统一的时钟信号, 不能由多设备提供; D 项正确, 半同步通信方式中, 握手信号的采样由同步时钟控制。
6． 设图的邻接矩阵A 如下所示, 各顶点的度依次是（ ）
中存放a ,
地址中的内容为11H 。由于数据按中存放b ,
地址中空闲,
地址
A.1, 2, 1, 2
B.2, 2, 1, 1
C.3, 4, 2, 3
D.4, 4, 2, 2
【答案】C
【解析】当图用邻接矩阵存储时, 各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。
第 3 页，共 62 页
7． 在支持多线程的系统中, 进程P 创建的若干个线程不能共享的是（ ）。
A. 进程P 的代码段
B. 进程P 中打开的文件
C. 进程P 的全局变量
D. 进程P 中某线程的栈指针
【答案】D
【解析】现代操作系统中, 进程是资源分配的基本单位, 线程是处理机调度的基本单位。因此, 进程是线程运行的容器, 本题中, 进程的代码段, 进程打开的文件, 进程的全局变量等都是进程的资源, 唯有进程中某线程的栈指针是属于线程的, 那么, 属于进程的资源可以共享, 属于线程的栈是独享的, 不能共享。
8． 折半查找的时间复杂性为（ ）。 A.
B.O(n) C. D.
【答案】D
【解析】顺序查找的事件复杂度为, 因为折半查找是查找效率最髙的算法，它的事件复杂度为。
9． 采用指令Cache 与数据Cache 分离的主要目的是（ ）
A. 减低Cache 的缺失损失
B. 提高Cache 的命中率
C. 减低CPU 平均访问时间
D. 减少指令流水线资源冲突
【答案】D
【解析】指令流水线不会断流, 预取过来的都是指令
10．某系统有n 台互斥使用的同类设备, 3个并发进程需要3, 4, 5台设备, 可确保系统不发生死锁的设备数n 最小为（ ）
A.9
B.10
C.11
D.12
【答案】B 【解析】
第 4 页，共 62 页
相关内容
相关标签