2016年中国民航大学航空工程学院数据结构复试笔试仿真模拟题
● 摘要
一、选择题
1． 对线性表进行折半查找时，要求线性表必须（ ）。
A. 以顺序方式存储B. 以顺序方式存储，且数据元素有序 C. 以链接方式存储D. 以链接方式存储，且数据元素有序 【答案】B
【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
2． 在OSI 参考模型中，直接为会话层提供服务的是（ ）
A. 应用层 B. 表示层 C. 传输层 D. 网络层 【答案】C
【解析】OSI 参考模型中，下层直接为上层提供服务，而会话层的下层为传输层。
3． 给定二叉树如下图所示。设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树，若遍历后的节点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）
A.LRN B.NRL C.RLN
D.RNL
图
【答案】D
【解析】对“二叉树”而言，一般有三条搜索路径； ①先上后下的按层次遍历；
②先左（子树）后右（子树）的遍历；
③先右（子树）后左（子树）的遍历；
其中第1种路径的搜索方式就是常见的层次遍历，第2种搜索路径方式包括常见的NLR 、中序遍历LNR 、后序遍历LRN , 第3种搜索路径方式则是不常使用的NRL 、RNL 、RLN 。本题考查的是第3种搜索路径方式的一种情况。根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D 。
4． 假定有4个整数用8位补码分别表示为
存放在一个8位寄存器中，则下列运算会发生溢出的是（ ）。
A.r1xr2 B.r2xr3 C.r1xr4 D.r2xr4
【答案】B
【解析】用补码表示时8位寄存器所能表示的整数范围为
在4个选项中，只有
现在4个整数都是负数
，结果溢出，其余3个算式结果
若将运算结果
都未超过127, 不发生溢出。
5． 某数采用IEEE754单精度浮点数格式表示为C640 0000H, 则该数的值是（ ）
A. B. C. D. 【答案】A
IEEE754单精度浮点数格式为C640 0000H表示为二进制格式为1100 0110 0100 0000 【解析】
0000 0000 0000 0000, 转换为标准的格式为：
. 因此，浮点数的值为
6． 下列关于SMTP 协议的叙述中，正确的是（ ）
I. 只支持传输7比特ASCII 码内容 II. 支持在邮件服务器之间发送邮件 III. 支持从用户代理向邮件服务器发送邮件 IV. 支持从邮件服务器向用户代理发送邮件 A. 仅 I 、II 和 III B. 仅 I 、II 和 IV C. 仅 I 、III 和 IV D. 仅 II 、III 和 IV
【答案】A
【解析】根据下图可知，SMTP 协议支持在邮件服务器之间发送邮件，也支持从用户代理向邮件服务器发送信息。SMTP 协议只支持传输7比特的ASCII 码内容
7． 下列选项中，会导致用户进程从态切换到内核的操作是（ ）
I. 整数除以零 II. Sin（ ）函数调用 III. read系统调用 A. 仅 I 、II B .仅 I 、III C. 仅II 、III D. I、II 和III 【答案】B
【解析】对于I ，系统发生异常，需要进入内核态由操作系统进行处理，而read 系统调用函数也是在内核态执行，sin （ ）就是普通的用户函数，在用户态执行，故答案为C 。
8． 用邻接表存储图所用的空间大小（ ）。
A. 与图的顶点数和边数都有关 B. 只与图的边数有关 C. 只与图的顶点数有关 D. 与边数的平方有关 【答案】A
【解析】邻接表就是对图G 中的每个顶点Vi 建立一个单链表，第i 个单链表中的结点表示依附于顶点V i 的边，这个单链表就称为顶点Vi 的边表。因此邻接表既存储图的所有顶点，也存储顶点之间的边的信息。
9． 对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（ ）。
A. B. C. D. 【答案】C 。
【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间
为
其中n 为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为
其
相关内容
相关标签