2017年武汉科技大学生物医学研究院856数据结构(C语言版)考研题库
● 摘要
一、选择题
1． 用有向无环图描述表达式（A+B）*（，至少需要顶点的数目为（ ）（A+B）/A）。
A.5 B.6 C.8 D.9
【答案】A
6条边【解析】一共5个结点
2． 下述文件中适合于磁带存储的是（ ）。
A. 顺序文件
B. 索引文件
C. 哈希文件
D. 多关键字文件
【答案】A
【解析】磁带存储是一种顺序存储，顺序文件
序文件适合磁带存储。
3． 单处理机系统中，可并行的是（ ）。
I. 进程与进程
II. 处理机与设备
III. 处理机与通道
IV . 设备与设备
A.I 、II 和III
B.I 、II 和IV
C.I 、III 和IV
D.II 、III 和IV
【答案】D
【解析】注意区分并发和并行。在单处理机系统中，进程只能并发。微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的。通道是独立于CPU 控制的输入/输出的设备，处理机与通道两者是可以并行。显然，设备和设备之间也是可以并行的。
是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。因此顺
4． 主机甲与主机乙之间使用后退N 帧协议（GBN ）传输数据，甲的发送窗口尺寸为1000, 数据帧长为1000字节，信道宽带为100Mbps ，乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲乙之间 的单向传播延迟是50ms ，则甲可以达到的最大平均数据传输速率约为（ ）
A .10 Mbps
B. 20 Mbps
C.80 Mbps
D.100 Mbps
【答案】C 【解析】
5．
用户程序发出磁盘
是（ ）
A. 用户程序
B. 系统调用处理程序
C. 设备驱动程序
D. 中断处理程序
【答案】C
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的，所以答案选C 。
6． 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法。
A. 分块
B. 顺序
C. 折半
D. 哈希
【答案】A
【解析】分块查找，把线形表分成若干块，块间是顺序存储的，所以查找速度较快。在每一块中的数据元素的存储顺序是任意的，所以便于线性表的动态变化。
7． 若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不会是（ ）。
A.1, 2.3.4
B.2，3, 4.1
C.3, 2, 4, 1
D.4, 3, 2, 1
【答案】C
【解析】题目中的二叉树的先序序列和后序序列正好相反，这样的二叉树每层只有一个结点。
请求后，系统的处理系统的处理流程是：用户程序一系统调用处理程序一设备骆动程序一中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序
该二叉树的形态如下图所示。
从左至右，这8棵二叉树的中序序列分别为：
（1）4. 3. 2. 1，
（2）3, 4, 2, 1
（3）2, 4, 3, 1
（4）2, 3, 4，1
（5）1，4，3, 2
（6）1, 3, 4, 2
（7）1，2, 4, 3
（8）1, 2, 3, 4
显然选项C 的中序序列不会出现。
8． 若元素a ，b , c, d, e，f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（ ）。
A.d ，c ，e ，b ，f ，a
B.c ，b ，d ，a ，e ，f
C.b ，c ，a ，e ，f ，d
D.a ，f ，e ，d ，c ，b
【答案】D
【解析】4个选项所给序列的进、出栈操作序列分别为：
选项A.Push , Push , Push ，Push , Pop, Pop, Push，Pop , Pop, Push , Pop ，Pop
选项B.Push , Push , Push , Pop , Pop , Push, Pop, Pop, Push, Pop , Push, Pop
选项C.Push , Push , Pop , Push , Pop , Pop, Push, Push, Pop, Push , Pop , Pop
选项D.Push , Pop , Push, Push , Push , Push, Push, Pop, Pop，Pop , Pop , Pop
按照题目要求，不允许连续三次进行退栈操作，所以选项D 所给序列为不可能得到的出栈顺序。
9． 由3个“1”和5个“0”组成的8位二进制补码，能表示的最小整数是（ ）。
A.-126
B.-125
C.-32
D.-3