2017年南华大学计算机科学与技术学院881数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 下列关于USB 总线特性的描述中，错误的是（ ）。
A. 可实现外设的即插即用和热插拔
B. 可通过级联方式连接多台外设
C. 是一种通信总线，可连接不同外设
D. 同时可传输2位数据，数据传输率高
【答案】D 。
【解析】USB 总线即通用串行总线，它的特点有：（1）即插即用；（2）热插拔；（3）有很强的链接能力能将所有外设链接起来，且不损失带宽；（4）有很好的可扩展性；（5）高速传输，速度可达480Mbps 。所有A , B, C都符合USB 总线的特点。对于选项D , USB 是串行总线，不能同时传输两位数据，所以答案为D 。
2． 执行（ ）操作时，需要使用队列做辅助存储空间。
A. 查找哈希（Hash ）表
B. 广度优先搜索网
C. 前序（根）遍历二叉树
D. 深度优先搜索网
【答案】B
【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。
3． 将线性表的数据元素进行扩充，允许带结构的线性表是（ ）。
A. 串
B. 树
C. 广义表
D. 栈
【答案】C
【解析】串、树、栈中的数据元素都是属于非结构的原子类型，元素的值是不可分解的。数组和广义表都是允许带结构的线性表。
4． 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
【解析】二叉排序树：左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。
5． 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A ，并已知A 的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（ ）型调整以使其平衡
【答案】C
【解析】A 的平衡因子此时为-1，要使插入结点不平衡，必须插在右孩子的左子树上，A 平衡因子变成了-2，则需要进行两次旋转（先右旋后左旋）。
6． 某计算机系统中有8台打印机，由K 个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K 最小值是（ ）。
A.2
B.3
C.4
D.5
【答案】C
【解析】死锁的抽屉原理一般描述是：将5个苹果放进4个抽屉，那么，必然有1个抽屉中至少有2个苹果。计算机系统的资源分配充分体现了这一原理。考察进程运行的特点，只要有一个进程能够运行，则运行结束后必然会归还资源，其余的进程也就会得到满足从而可以执行（这里考虑的资源主要是可重用的资源，不可重用的资源会消失，就不可用上述方法分析）。所以最少需要4个进程竞争使用，每个进程占用2台打印机，此时会产生死锁。
7． 设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。
A. 线性表的顺序存储结构
B. 队列
C. 线性表的链式存储结构
D. 栈
【答案】D
【解析】用栈更合适，如果是左括号，进找；如果是右括号，看栈顶是不是左括号，如果是，
则左括号出栈；否则不配对（可以直接结束算法）。处理完所有符号号，如果栈为空则配对成功。
8． 下列有关总线定时的叙述中，错误的是（ ）。
A. 异步通信方式中，全互锁协议最慢
B. 异步通信方式中，非互锁协议的可靠性最差
C. 同步通信方式中，同步时钟信号可由多设备提供
D. 半同步通信方式中，握手信号的采样由同步时钟控制
【解析】A 项正确，异步通信方式中，全互锁协议最慢，主从模块都需要等待确认后才能撤销其信号；B 项正确，异步通信方式中，非互锁协议没有相互确认机制，因此可靠性最差；C 项错误，同步通信要遵循统一的时钟信号，不能由多设备提供；D 项正确，半同步通信方式中，握手信号的采样由同步时钟控制。
9． 在OSI 参考模型中，自下而上第一个提供端到端服务的层次是（ ）。
A. 数据链路层
B. 传输层
C. 会话层
D. 应用层
【答案】B
【解析】题目中指明了这一层能够实现端到端传输，也就是端系统到端系统的传输，数据链路层主要负责传输路径上相邻结点间的数据交付，这些结点包括了交换机和路由器等数据通信设备，这些设备不能被称为端系统，因此数据链路层不满足题意。题目中指明了这一层能够实现传输，会话层只是在两个应用进程之间建立会话而已，应用层只是提供应用进程之间通信的规范，都不涉及传输。所以本题答案应该是B 项。在OSI 模型中网络层提供的是主机到主机的通信服务。
10．主机甲与乙之间已建立一个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 。
11．下列各类存储器中，不采用随机存取方式的是（ ）。
A.EPROM
B.CDROM
C.DRAM
D.SRAM
【答案】B
【解析】随机存取方式是指存储器的任何一个存储单元的内容都可以存取，而且存取时间与存储单元的物理位置无关。CDROM 是只读的光盘存储器，采用串行存取方式而不是随机存取方
相关内容
相关标签