2017年武汉大学计算机学院932软件工程专业基础综合之数据结构教程考研强化模拟题
● 摘要
一、填空题
1． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
2． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
3． 设有一个10阶对称矩阵A 采用压缩存储方式，（以行为主序存储：）则
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若的地址为将代入得33。
4． 外排序的基本操作过程是_____和_____。 则
；归并 【答案】生成有序归并段（顺串）
5． 表达式
【答案】
6． 在有n 个顶点的有向图中，每个顶点的度最大可达。
【答案】2（n-l ）
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。
7． 在二叉树中，指针p 所指结点为叶结点的条件是_____。
【答案】
【解析】叶子节点的左右孩子都不存在。
8． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。
；算法 【答案】逻辑结构；物理结构；操作（运算）
的地址为_____。
若
则的地址为
的后缀表达式是_____。
9． 在一棵m
阶的个数是_____。
【答案】
树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的
关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字
最少
【解析】m
阶树除根结点和叶子结点外，结点中关键字个数最多是
10．—个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
二、选择题
11．下列关于管道（Pipe ）通信的叙述中，正确的是（ ）
A. —个管道可实现双向数据传输 B. 管道的容量仅受磁盘容量大小限制
C. 进程对管道进行读操作和写操作都可以被阻塞 D. —个管道只能有一个读写进程或一个写进程对其操作 【答案】C
【解析】只有写进程才能对管道写入数据，读进程对管道进行读取数据，只能半双工通信，即某一时刻只能单向传输。管道为空，则读操作被堵塞，而如果有写操作对管道进行写的话那就要堵塞了。那么C 正确
12．有六个元素6, 5, 4, 3, 2, 1顺序入栈，下列不是合法的出栈序列的是（ ）。
A.543612 B.453126 C.346521 D.234156 【答案】C
【解析】根据栈的后进先出的特点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出找。
13．分区分配内存管理方式的主要保护措施是（ ）。
A. 界地址保护 B. 程序代码保护 C. 数据保护 D. 栈保护 【答案】A
【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护。通常的界地址保
护方法采用软硬件结合的方法。考生要注意本题与虚拟存储方法的区别。
14．对n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ）。
A. 每次分区后，先处理较短的部分 B. 每次分区后，先处理较长的部分 C. 与算法每次分区后的处理顺序无关 D. 以上三者都不对 【答案】A
【解析】令递归函数为f ，第一次进行递归函数认为递归深度为1，以后从深度为n 的递归函数f 中再调用递归函数f ，此时深度为整个f 的最大深度为递归深度。
15．设有向图G= （V ，E ），顶点集V={V0, VI ，V2, V3}，边
集
若从顶点V0开始对图进行深度优先遍历，则可
能得到的不同遍历序列个数是（ ）。
A.2 B.3 C.4 D.5
【答案】D
【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可 能得到的不同遍历序列分别是：
16．在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）
【答案】C
【解析】两个循环嵌套，那么语句x :=x＋l :
则被执行了次。
17．若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A.257 B.258 C.384 D.385 【答案】C