2017年北京物资学院物联网工程与技术911计算机学科专业基础综合之数据结构考研强化模拟题
● 摘要
一、填空题
1． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】树。故结点个数为
2．
【答案】5
3． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____; 而又根据指针的连接方式，链表又可分成_____和_____。
【答案】单链表；双链表；（动态）链表；静态链表
【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。
4． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。
；算法 【答案】逻辑结构；物理结构；操作（运算）
5． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
6． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
7． 已知一循环队列的存储空间为环队列判满的条件是（ ）
【答案】
=_____
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉
其中
队头和队尾指针分别为front 和rear , 则此循
8． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。
注：（1）图的顶点号从0开始计；
（2）indegree 是有n 个分量的一维数组，放顶点的入度， （3）函数crein 用于记算顶点入度；
（4）有三个函数push （data ）, pop（ ）, check（ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1, 否则0）。
）
.
【答案】0; j; i; 0; indegree[i]=0; [vex][i]; k==l; indegree[i]=0
【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程：首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。
9． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为
10．克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。
【答案】O （eloge ）; 边稀疏
；
（“图有回路”）
二、选择题
11．对矩阵压缩存储是为了（ ）。
A. 方便运算 B. 方便存储
C. 提高运算速度 D. 减少存储空间 【答案】D
【解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素放在一个存储空间，目的就是为了节省空间。
12．文件系统中，文件访问控制信息存储的合理位置是（ ）。
A. 文件控制块 B. 文件分配表 C. 用户口令表 D. 系统注册表 【答案】A
【解析】文件控制块是文件存在的标志，文件的相关信息（基本信息、存取控制信息以及使用信息）都存储在文件控制块中，系统对文件的管理全是依靠文件控制块里的信息。
13．下列哪一种图的邻接矩阵是对称矩阵？（ ）
A. 有向图 B. 无向图 C.AOV 网 D.AOE 网 【答案】B
【解析】邻接矩阵存储，就是用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间关系的二维数组称为邻接矩阵。因为无向图中边是没有方向的，所以所以无向图的邻接矩阵是对称矩阵。
14．若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度
【答案】C
【解析】最快查找一次成功，最慢查找n
次成功。平均查找次数为
15．某计算机有五级中断的顺序为
A.11110 B.01101 C.00011 D.01010 【答案】D
【解析】由于
则
中断屏蔽字为
表示对
屏蔽。若中断响应优先级从高到低的顺序是
那么
为（ ）。
级中断进行
且要求中断处理优先级从高到低
的中断处理程序中设置的中断屏蔽字是（ ）。
B 排除掉。的中断处理优先级下降，屏蔽字中需要3个0, 所以可以将选项A 、
相关内容
相关标签