2017年河北大学电子信息工程学院929数据结构(电)考研导师圈点必考题汇编
● 摘要
一、选择题
1． 以下数据结构中，（ ）是非线性数据结构。
A. 树 B. 字符串 C. 队 D. 栈 【答案】A
【解析】非线性结构是指存在一对多或者多对一的关系。常见的非线性结构有树结构和图结构。
2． n 个结点的完全有向图含有边的数目（ ）。
A.n*n
B.n （n+l） C.n/2
D.n*（n-l ）
【答案】D
【解析】在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n 的无向图，最多有
条边。如是有向图，需要在无向图的最多边的基础上乘以2，则
为n （n-l ）。
3． 若将关键字1，2, 3, 4, 5, 6, 7依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0的分支结点的个数是（ ）
A.0 B.1 C.2 D.3
【答案】D
【解析】将图中给定的关键字序列依次插入到平衡树中，构成的平衡树如下图所示，由图可知平衡因子为0的分支结点为3个叶子结点，故答案为D 。
4．
用户程序发出磁盘是（ ）
A. 用户程序 B. 系统调用处理程序 C. 设备驱动程序 D. 中断处理程序 【答案】C
请求后，系统的处理系统的处理流程是：用户程序一系统调用处理程
序一设备骆动程序一中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的，所以答案选C 。
5． 希尔排序的组内排序采用的是（ ）。
A. 直接插入排序 B. 折半插入排序 C. 快速排序 D. 归并排序 【答案】A
【解析】希尔排序基本思想是：先将整个待排元素序列按某个增量分割成若干个子序列，在子序列内进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
6． 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。
A. 选择排序法B. 插入排序法C. 快速排序法D. 堆排序法 【答案】A
【解析】选择排序的基本思想是：
第i 趟排序开始时，当前有序区和无序区分别为则是从当前无序区中选出关键字最小的记录和
分别变为新的有序区和新的无序区。
和
该趟排序
交换，使
将它与无序区的第1个记录
7． 下列关于RISC 的叙述中，错误的是（ ）。
A.RISC 普遍采用微程序控制器
B.RISC 大多数指令在一个时钟周期内完成 C.RISC 的内部通用寄存器数量相对CISC 多
D.RISC 的指令数、寻址方式和指令格式种类相对CISC 少 【答案】A
【解析】B 项、C 项、D 项都是RISC 的特点之一，所以它们都是正确的，只有A 项是CISC 的特点，因为RISC 的速度快，所以普遍采用硬布线控制器，而非微程序控制器。
8． 下列选项中，不属于网络体系结构中所描述的内容是（ ）。
A. 网络的层次 B. 每一层使用的协议 C. 协议的内部实现细节 D. 每一层必须完成的功能 【答案】C
【解析】体系结构仅规定协议的功能和消息格式，但对具体的实现细节由具体设备厂商来确定，对于网络的层次，以及每一个层次的协议及其功能都是网络体系结构所要描述的内容，因此答案为选项C 。
9． 下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（ ）。
【答案】D
【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息，解题思路较简单。题中所给二叉树的后序序列为dbca 。结点d 无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b ; 结点b 无左子树，左链域指向其前驱结点山结点c 无左子树，左链域指向其前驱结点b ，无右子树，右链域指向其后继结点a 。所以正确选项为D 。
10．某设备中断请求的相应和处理时间为100m ，每400ns 发出一次中断请求，中断相应所容许的最长延迟时间为50ns , 贝U 在该设备持续工作过程中CPU 用于该设备的百分比至少是（ ）
A.
B.
C.
D. 【答案】B
【解析】每400m 响应一次中断并且用100m 进行处理，所以该设备的百分比为
时间占用CPU 时间
中断响应容许的延迟时间对此没有影响，属于干扰条件。
时间占整个CPU 时间
相关内容
相关标签