2017年福建师范大学软件学院842软件工程专业基础综合考研导师圈点必考题汇编
● 摘要
目录
2017年福建师范大学软件学院842软件工程专业基础综合考研导师圈点必考题汇编（一）.... 2 2017年福建师范大学软件学院842软件工程专业基础综合考研导师圈点必考题汇编（二）.. 12 2017年福建师范大学软件学院842软件工程专业基础综合考研导师圈点必考题汇编（三）.. 24 2017年福建师范大学软件学院842软件工程专业基础综合考研导师圈点必考题汇编（四）.. 36 2017年福建师范大学软件学院842软件工程专业基础综合考研导师圈点必考题汇编（五）.. 46
第 1 页，共 56 页
一、填空题
1
．
求REPLACE （S ，V , m ）=_____。
【答案】
2． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
3． 对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。
【答案】n （n-1）/2
【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n（n-l ）/2。
4． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。
【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
5． 在一棵m
阶树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。
【答案】
最少
【解析】m
阶树除根结点和叶子结点外，结点中关键字个数最多是
6． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
7． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。
；算法 【答案】逻辑结构；物理结构；操作（运算）
第 2 页，共 56 页
已
知
8． 串是一种特殊的线性表，其特殊性表现在_____; 串的两种最基本的存储方式是_____、_____; 两个串相等的充分必要条件是_____。
【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等
9． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。 10．分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ） 而快速排序算法需要比较的次数达到最大，时间复杂度为
11．在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。 12．在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。
【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）
二、选择题
13．对矩阵压缩存储是为了（ ）。
A. 方便运算 B. 方便存储 C. 提高运算速度 D. 减少存储空间 【答案】D
【解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素放在一个存储空间，目的就是为了节省空间。
14．已知广义表
用
第 3 页，共 56 页
和数取出LS 中原子e 的运算是（ ）。
【答案】C 【解析】
操作就是得到广义表中第一个的原子。
得
到得到e 。
15．若元素a ，b , c, d, e，f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（ ）。
A.d ，c ，e ，b ，f ，a B.c ，b ，d ，a ，e ，f C.b ，c ，a ，e ，f ，d D.a ，f ，e ，d ，c ，b
【答案】D
【解析】4个选项所给序列的进、出栈操作序列分别为：
选项A.Push , Push , Push ，Push , Pop, Pop, Push，Pop , Pop, Push , Pop ，Pop 选项B.Push , Push , Push , Pop , Pop , Push, Pop, Pop, Push, Pop , Push, Pop 选项C.Push , Push , Pop , Push , Pop , Pop, Push, Push, Pop, Push , Pop , Pop 选项D.Push , Pop , Push, Push , Push , Push, Push, Pop, Pop，Pop , Pop , Pop
按照题目要求，不允许连续三次进行退栈操作，所以选项D 所给序列为不可能得到的出栈顺序。
16．一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A. 其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子 C. 其中只有一个叶结点
D. 其中度为2的结点最多为一个 【答案】C
【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A 项或B 项都不全。
17．在支持多线程的系统中，进程P 创建的若干个线程不能共享的是（ ）。
A. 进程P 的代码段 B. 进程P 中打开的文件 C. 进程P 的全局变量 D. 进程P 中某线程的栈指针 【答案】D
【解析】现代操作系统中，进程是资源分配的基本单位，线程是处理机调度的基本单位。因
第 4 页，共 56 页
操作就是得到除第一个原子外剩下元得
到
得
到
素构成的表
。
相关内容
相关标签