2017年北京师范大学教育学部894程序设计与数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。
【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。 2． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。free_tree在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；
首
先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。
【答案】
3． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。
【答案】左子树；右子树 【解析】二叉排序树
或者是一棵空树，或者是具有下列性质的二叉树：①若它
的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。
4． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。
【答案】n （n-l ）/2
【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。
5． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。
【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
6． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
7． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。
【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。
8． 在哈希函数中，P 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
9． 中缀式对应的前缀式为_____，若运算结果为_____。
【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
10．一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
11．属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
则后缀式的
12．设数组数组中任一元素均占内存48个二进制位，从首地址2000开始
连续存放在主内存里，主内存字长为16位，那么
（1）存放该数组至少需要的单元数是_____；
（2）存放数组的第8列的所有元素至少需要的单元数_____； （3）数组按列存储时，元素【答案】270; 27; 2204 【解析】数组的元素个数为需要
第8列有9个元素，共占个单元。按列存储时，
因为每个元素占内存48个二进制位，即6个字节。故总
个单元数。
个字节，因此至少需要的起始地址为
个单元数。由题知，每个元素占3
个字节，因为主内存字长为16位，即2个字节，所以至少需要
的起始地址是_____。
二、判断题
13．内排序要求数据一定要以顺序方式存储。（ ）
【答案】×
【解析】由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：一类是内部排序；另一类是外部排序。因此，内部排序没有要求数据一定是以顺序方式存储。
14．对磁带机而言，ISAM 是一种方便的文件组织方法。（ ）
【答案】×
【解析】ISAM 是一种专为磁盘存取设计的文件组织方式。
15．循环队列也存在空间溢出问题。（ ）
【答案】
【解析】循环队列的存储空间也是有限的，因此也存在空间溢出问题。
16．堆肯定是一棵平衡二叉树。（ ）
【答案】×
【解析】堆是n 个元素的序列，可以看成是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会是平衡二叉树。
17．排序算法中的比较次数与初始元素序列的排列无关。（ ）
【答案】×
【解析】这个要看是哪个排序算法，比如快速排序，初始序列为有序的情况比较的次数就相对于无序的多。
相关内容
相关标签