2017年湖南大学信息科学与工程学院866数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 设有一个n 行n 列的对称矩阵A ，将其下三角部分按行存放在一个一维数组B 中，放于
中，那么第i 行的对角元素【答案】A
【解析】
中列标不大于行标，
又
存放在
中，
所以
存放的位置为
存放于B 中（ ）处。
存
2． 假定变量i 、f 和d 的数据类型分为int 、float 和double （int 用补码表不，float 和double 分，已知别用IEEE754单精度和双精度浮点数格式表示）
位机器中执行下列关系表达式，则结果为“真”的是（ ）。
A. 仅I 和II B. 仅I 和III C. 仅II 和III D. 仅III 和IV 【答案】B
II 中，f 的数据类型从float 【解析】数据类型不同的数据在运算之前需要进行数据类型的转换。转换为int 时，小数点后面4位会丢失，故II 的结果不为真；IV 中，d+f时需要对阶，对阶后f 的尾数有效位被舍去而变为0, 故d+f仍然为d , 再减去d 后结果为0, 故IV 的结果也不为真。I 和II 进行数据类型的转换的时候并没有改变其值。
3． 设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，储地址为1，每个元素占一个地址空间，则
A.13 B.33 C.18 D.40
【答案】B
【解析】对于对称矩阵，
的地址为（ ）。
若在32
为第一元素，其存
为了节省存储空间，为多个相同的元素只分配一个存储空间。
时，
当
时，
其
对于对称矩阵，元素下表之间的对应关系为：当
中k 相当于地址空间的标号，i 为行号，j 为列号。因为第一个元素存储地址为1，所以最后计算
的k 需要加1。所以
的存储位置为
4． 若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则X 的前驱为（ ）。
A.X 的双亲
B.X 的右子树中最左的结点 C.X 的左子树中最右的结点 D.X 的左子树中最右的叶结点 【答案】C
【解析】中序线索，只有把其左子树最右结点遍历完后，才会遍历自己，所以X 的前驱为X 的左子树中最右的结点。
5． 下列选项中，用于提高RAID 可靠性的措施有（ ）
I. 磁盘镜像 II. 条带化 III. 奇偶校验 IV . 增加Cache 机制 A. 仅 I 、II B. 仅 I 、III C. 仅 I 、III 和IV D. 仅II 、III 和IV 【答案】B
【解析】能够提高RAID 可靠性的措施主要是对磁盘进行镜像处理和进行奇偶校验。其余选项不符合条件。
6． 下列选项中，不可能在用户态发生的事件是（ ）。
A. 系统调用 B. 外部中断 C. 进程切换 D. 缺页 【答案】C 。
【解析】我们在学习操作系统中知道，任何一个进程在现代操作系统中为了共享和保护，设，在用户态运行用户的程序，在内核定了用户态和内核态（可以通过设置软、硬件标志位来实现）
运行系统的程序。所以，从选 项来看，系统调用可以在任何态发生，用户可以发起系统调用，系统也可以；外部中断是不可控的，也会在任何时刻发生，缺页的发生也是不可控的，可以发生在用户代码之间；而进程切换却不会在用户态发生。我们可以考虑一下情形，进程切换是在什么时候发生的，进程切换前必定运行的是进程调度，只有进程调度选择了下一次被调度的进程，进程切换才可以进行。进程调度是scheduler , 进程切换是dispather , 这体现了现代操作系统策略与机制，必定分离的设计思想。所以，进程切换必定不会在用户态发生（所谓发生指其起始的源头时刻）是在内核态（进程调度）发生的。
7． 无向图G=（V , E ）, 其中：V={a, b , c , d , e , f ）}, E={（a , b ）, （a , e ）, （a , c ），，（b , e ）, （c , f ），（f , d ）（e , d ）, 对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A.a , b , e , c , d , f B.a , c , f , e , b , d C.a , e , b , c , f , d D.a , e , d , f , c , b
【答案】D
【解析】图的深度优先遍历过程是：从图中某个初始顸点V 出发，首先访问初始顶点V ，然后选择一个与顶点V 相邻且没被访问过的顶点U 为初始顶点。再从U 出发进行深度优先搜索，直到图中与当前顶点V 邻接的所有顶点都被访问过为止。
，，，，，根据E={（a , b ）（a ，e ）（a ，c ）（b ，e ）（c , f ）（f ，d ）, （e ，d ）}可知各顶点之间的邻接关系。依据上面的原则遍历，得出遍历顺序a , e ，d ，f ，c , b 。
8． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。
A.0（n ） B.0（n+e） C.0（n*n） D.0（n*n*n） 【答案】B
【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0（n+e）
9． 用有向无环图描述表达式（A+B）*（，至少需要顶点的数目为（ ）（A+B）/A）。
A.5 B.6 C.8 D.9 【答案】A
【解析】一共5个结点
6条边
10．现在有一颗无重复关键字的平衡二叉树（A VL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）。
A. 根节点的度一定为2 B. 树中最小元素一定是叶节点 C. 最后插入的元素一定是叶节点 D. 树中最大元素一定是无左子树 【答案】D
【解析】二叉树的中序遍历定义是“若二叉树为空，则空操作；否则：①中序遍历左子树；②访问根节点；③中序遍历右子树”。A 项错误，当树中仅有一个或者两个结点时，根节点的度就可能不为2；B 项错误，树中最小元素是中序遍历时最后访问的节点，当没有右子树时，最后访问的节点是根节点；C 项错误，当最后插入的元素破坏树的平衡后，树会进行调整，使其成为中间节点；D 项正确，由中序遍历的特点可知，左子树的值大于根节点，所以最大元素一定没有左子树。
二、填空题
相关内容
相关标签