《2017年西南交通大学信息科学与技术学院840数据结构与程序设计考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年西南交通大学信息科学与技术学院840数据结构与程序设计考研导师圈点必考题汇编.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年西南交通大学信息科学与技术学院840数据结构与程序设计考研导师圈点必考题汇编一、选择题1 执行（ ）操作时，需要使用队列做辅助存储空间。A. 查找哈希（Hash ）表B. 广度优先搜索网C. 前序（根）遍历二叉树D. 深度优先搜索网【答案】B【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。 2 下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（ ）。 【答案】D【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息，解题思路较简单。题中所给二叉树的后序序列为dbca 。结点d 无前
2、驱和左子树，左链域空，无右子树，右链域指向其后继结点b ; 结点b 无左子树，左链域指向其前驱结点山结点c 无左子树，左链域指向其前驱结点b ，无右子树，右链域指向其后继结点a 。所以正确选项为D 。 3 某基于动态分区存储管理的计算机，其主存容量为55MB （初始为空闲）采用最佳适配（Bestfit ）算法，分配和释放的顺序为：分配15MB 、分配30MB 、释放15MB 、分配8MB 、分配6MB , 此时主存中最大空闲分，区的大小是（ ）。A.7MBB.9MBC.10MBD.15MB【答案】B【解析】对于简单分区内存分配，需要将进程的所有代码和数据装入内存。故55MB 先分配15MB 余
3、40MB , 再分配30MB 后余10MB , 释放15MB 后出现一个15MB 和一个10MB 的空闲空间，分配8MB 时按最佳适配（BestFit ）算法应该使用10MB 的空闲块，余2MB 的碎片，分配6MB，因此最大空闲区为9MB 。 时占用15MB 的空间余9MB 的碎片（空闲空间） 4 次总线事物中，主设备只需给出一个首地址，从设备就能从首地址开始的若干连续单元格读出或写入的个数，这种总线事务方式称为（ ）A. 并行传输B 串行传输C. 突发D. 同步【答案】C【解析】猝发数据传输方式：在一个总线周期内传输存储地址连续的多个数据字的总线传输方式 5 在任意一棵非空二叉排序树T1中，
4、删除某结点v 之后形成二叉排序树T2, 再将v 插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是（ ）I. 若v 是T1的叶结点，则T1与T3不同II. 若v 是T1的叶结点，则T1与T3相同III. 若v 不是T1的叶结点，则T1与T3不同IV . 若v 不是T1的叶结点，则T1与T3相同A. 仅 I 、IIIB .仅 I 、IVC. 仅 II 、IIID. 仅 II 、IV【答案】C【解析】在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点，那么再插入这个结点
5、后，后来的二叉树可能发生变化，不完全相同。 6 若一个用户进程通过read 系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（ ）。I. 若该文件的数据不在内存，则该进程进入睡眠等待状态；II. 请求read 系统调用会导致CPU 从用户态切换到核心态；III. read系统调用的参数应包含文件的名称A. 仅 I 、IIB. 仅 I 、IIIC. 仅 II 、IIID.I 、II 和III【答案】A，原进程【解析】对于I ，当所读文件的数据不再内存时，产生中断（缺页中断、缺段中断），直到所需数据从外村调入内存后，将该进程唤醒，使其变为就绪进入睡眠等待状态（阻塞状态）状态。对
6、于II , read系统调 用CPU 将从用户态切换到核心态，从而获取操作系统提供的服务。对于III ，在操作系统中，要读一个文件首先要open 系统调用将该文件打开。Open 系统调用的参数需要包含文件的路径名与文件名，而read 系统调用只需使用open 返回的文件描述符，并不使用Read 系统调用要求用户提供三个输入参数：文件名作为参数。文件描述 符；buf 缓冲区首址；传送的字节数n 。read 系统调用的功能是试图从fd 所指示的文件中读入n 个字节的数据，并将它们送至由指针buf 所指示的缓冲区中。 7 对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。 A.4B.3C.2D.1【答案】B【解析】拓扑排序的步骤为：（1）在有向图中选一个没有前驱的顶点并且输出它；（2）从图中删除该顶点和以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑棑序序列，分别为abced ，abecd ，aebcd 。 8 分区分配内存管理方式的主要保护措施是（ ）。A. 界地址保护B. 程序代码保护C. 数据保护D. 栈保护【答案】A一、选择题考研试题
