2017年北方工业大学计算机学院861数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． 在一棵m
阶
的个数是_____。 【答案】
最少 【解析】m
阶树除根结点和叶子结点外，结点中关键字个数最多是
2． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。 【答案】 树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字
【解析】哈夫曼树只有度为0和2的节点。
3． 设单链表的结点结构为为指针域，已知指针px 指向单链表中data 为x 的结
_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：
_____; 【答案】
4． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n
个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
（1）若是边，则的值等于_____，若不是边，则的值是一个比任何边的权，矩阵的对角线元素全为0。
（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若
【答案】（1） 已包括进生成树，就把矩阵元素A （i ，j ）置成 边上的权值；都大的数；（2）1; 负值；（3）为负；边 （3）算法结束时，相邻矩阵中。
5． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
6． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
7． 一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
8． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
9． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构（网状结构）
10．求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】
二、判断题
11．在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。（ ）
【答案】×
【解析】伙伴系统的伙伴不一定是位置相邻的内存块。
起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
只要符合公式的内存块都是伙伴。
12．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ） 【答案】
【解析】数据的逻辑结构是指数据元素之间的逻辑关系。
13．顺序存储结构的主要缺点是不利于插入或删除操作。（ ） 【答案】
【解析】因为顺序表的插入删除会移动大量的元素。
14．通常使用队列来处理函数或过程的调用。（ ） 【答案】
【解析】经常使用栈来处理函数或过程的调用。
15．一般来说，若深度为k 的n 个结点的二叉树只有最小路径长度，那么从根结点到第
的最多结点数为【答案】√
【解析】求最小路径长度，即构成哈夫曼树，当哈夫曼树为
层具有最大的结点数为
层具有余下的个结点在第k 层的任一位置上。（ ） 层全满时，
此时从根结点到第
16．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ） 【答案】
【解析】前者正确，后者错误。顺序存储方式在插入、删除元素时需要挪动大量的元素，执行效率较低。
17．数据结构的抽象操作的定义与具体实现有关。（ ） 【答案】
【解析】数据结构的抽象操作定义取决于客观存在的一组逻辑特性，与其在计算机内具体表示和实现无关。
18．设栈采用顺序存储结构。若已有
杂性为（ ） 【答案】个元素入栈，则将第i 个元素入栈时，入栈算法的时间复【解析】由于该栈采用顺序存储结构，时间复杂度应该为0（1）。
19．对磁带机而言，ISAM 是一种方便的文件组织方法。（ ）
【答案】×
【解析】ISAM 是一种专为磁盘存取设计的文件组织方式。
20．若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（ ）
【答案】×
【解析】在含有N 个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也叫做最优二叉树。关键字有序，可能叶子结点部分的关键字最大，根结点的关键字部分最小，此时就不是哈夫曼树。
21．深度为k 的二叉树中结点总数小于等于
【答案】√
【解析】深度为K 的二叉树，当结点数最多时为满二叉树，此时结点数为
22．最小生成树的Krusakl 算法是一种贪心法。（ ）
【答案】√
【解析】在构建最小生成树常见的有三种贪心算法：kruskal , prim , soilion 。
（ ）
三、算法设计题
23．试编写一算法对二叉树按前序线索化。
【答案】算法如下：
相关内容
相关标签