2016年信阳师范学院数学与信息科学、计算机与信息技术计算机学科专业基础综合之数据结构复试笔试仿真模拟题
● 摘要
一、选择题
1． 对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。
A.4
B.3
C.2
D.1
【答案】B
【解析】拓扑排序的步骤为：
（1）在有向图中选一个没有前驱的顶点并且输出它；
（2）从图中删除该顶点和以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑棑序序列，分别为abced ，abecd ，aebcd 。
2． 假定编译器规定int 和short 类型长度分别为32位和16位，执行下列C
语言语句
得到y 的机器数为（ ）。
【答案】B 。
【解析】X 和y 均为无符号数，其中X 为16位，y 为32位，将16位无符号数转化成32位
无符号数，前面要补零。因为所以
3． 本地用户通过键盘登录系统时，首先获得的键盘输入信息的程序是（ ）。
A. 命令解释程序
B. 中断处理程序
C. 系统调用服务程序
D. 用户登录程序
【答案】B
【解析】外部设备在与计算机连接时有多种方式，中断技术就是一种常用方式。其工作原理是：利用处理机中断信号线，外部设备在需要服务的时候将该线设置为有效，计算机若同意接受
，中断则会停止当前进程的运行，转而服务发出中断的物理设备（注意与陷阱，即软中断有区别）
那么对不同外部设备进行服务的程序代码是不同的，如何找到这些代码呢? 这就要借助中断向量，中断向量一般是由硬件根据中断的类型（不同外设不同）计算所得，或计算机系统在开机配置时所配置的。处理机取得中断向量，其实就是一个物理地址，该地址下存放的是为此中断服务的代码的起始地址。所以，当键盘按下的时候，键盘控制器获得该操作动作，先将键盘扫描码读入键盘缓冲区，再向处理机发出键盘中断，适当的时候（一条指令的末尾或一条原语结束）处理机会响应中断，调用指定服务程序将键盘缓冲区中的键盘扫描码输入到登录进程中去。如此，最先响应键盘的必然是中断处理程序。本题中，像命令解释器（例如cmd 窗口）、系统调用服务和用户登录程序都在中断处理程序后面。
4． 主机甲与乙之间已建立一个TCP 连接，双方持续有数据传输，且无差错与丢失。若甲收到1个来自乙的TCP 段，该段的序号为1913、确认序号为2046、有效载荷为100字节，则甲立即发送给乙的TCP 段的序号和确认分别是（ ）
A.2046、 2012
B.2046、 2013
C.2047、 2012
D.2047、 2012
【答案】B
【解析】若甲收到1个来自乙的TCP 段，该段的序号seq=1913、确认序号ack=2046、有效载荷为100字节，则甲立即发送给乙的TCP 段的序号seql=ack=2046和确认序号ackl =seq+100=2013, 答案为B 。
5． 若一棵二叉树的前序遍历序列为a ，e ，b ，d ，c ，后序遍历序列为b , c, d, e, a, 则根结点的孩子结点（ ）。
A. 只有e
B. 有 e 、b
C. 有 e 、c
D. 无法确定
【答案】A 。
b , d, c, 后序遍历序列为b ，c , d, 【解析】由题目可知，若一棵二叉树的前序遍历序列为a , e，
e , a , 其中a 为这棵二叉树的根结点，接下来，在前序遍历的第二个结点为e , 而后序遍历的倒数第二个结点为e , 说 明a 的孩子结点只有e 。
6． 下列网络设备中，能够抑制广播风暴的是（ ）。
中继器
集线器
网桥
路由器
A. 仅和
B. 仅
D. 仅 C. 仅和
【答案】D
【解析】中继器和集线器工作在物理层，不能抑制网络风暴。为了解决冲突域的问题，提高共享介质的利用率，通常利用网桥和交换机来分隔互联网的各个网段中的通信量，以建立多个分离的冲突域。但是，当网桥和交换机接收到一个未知转发信息的数据帧时，为了保证该帧能被目的结点正确接收，将该帧从所有的端口广播出去。于是可以看出，网桥和交换机的冲突域等于端口的个数，广播域为1。因此网桥不能抑制网络风暴。
7． 某同步总线的时钟频率为宽度为32位，地址/数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输128位数据所需要的时间至少是（ ）。
A.20ns
B.40ns
C.50ns
D.80ns
【答案】C 。
【解析】总线的时钟频率为100MHz ，贝时钟周期为10ns 。数据是128位，总线宽度是32位，所以需要4个时钟周期，而传输地址还需要一个周期，所以传输一个128位的数据至少需要5个时钟周期，所以至少需要10ns*5=50ns。
8． 基于比较方法的n 个数据的内部排序。 最坏情况下的时间复杂度能达到的最好下界是（ ）。
A.0（nlogn ）
B.O （logn ）
C.O （n ） D.
【答案】A
【解析】在内部排序中，最坏情况下的时间复杂度为0（nlogn ）。
已知待排序的n 个元素可分为
大干前一
个组，每个组包含k 个元素，且任一组内的各元素均分别
相关内容
相关标签