1、2016 年第二炮兵工程大学 843 数据结构 考研真题 一、填空题（ 110题，每空 2 分，共 20分） 1带头结点的单链表 L为空表的条件是（ ）。 2已知深度为 7的完全二叉树，第 7层上有 10个叶子结点，则整个二叉树的结点数是（ ）。 3已知二叉树有 50个叶子结点，则该二叉树度为 2的结点数是（ ）。 4假定一组记录的排序码为（ 46,79,56,38,40,80），对其进行起泡排序的过程中，第二趟排序的结果为（ ）。 5在有序表 A118 中，采用折半查找算法查找元素值等于 A7的元素，所比较过的元素的下标依次为（ ）。 6 设有一棵 Huffman 树的节点总数为 35， 则
2、该 Huffman 树共有 （ ） 个叶子节点 。 7 高度为 h的完全二叉树最少有 （ ） 个节点 。 8在一个具有 n个顶点的无向完全图中，包含有（ ）条边。 9已知一个栈的输入序列为 1、 2、 3 n，则其输出的第一个元素为 n的输出序列的个数是（ ）。 10简单选择排序算法所执行的元素交换次数最少为（ ）。 二、单项选择题（ 1130题，每题 2分，共 40分） 11一个算法的执 行时间为 T(3n2+2nlog2n+4n-7)/(10n)，其时间复杂度为 _。 A O(3n2) B O(2nlog2n) C O(3n/10) D O(n) 12设 n是描述问题规模的非负整数，下面程
3、序片段的时间复杂度为 _。 x=2; while (xnext ; p-next = q-next; B p = q-next ; q-next = p; C p = q-next ; q-next = p-next; D q-next = q-next-next; q-next = q; 22有 n个结点的二叉树若符合条件 _则是完全二叉树。 A深度为 n2log +1 B树的路径长度最短 C叶子 只出现在最下面的两层上 D结点编号与满二叉树的前 n个结点一一对应 23折半查找方法适用于 _ A单链表的查找 B顺序表的查找 C双向链表的查找 D任意线性表的查找 24二叉树有 _种形态。 A
4、3 B 5 C 7 D 9 25快速排序算法在最坏情况下的时间复杂度为 _。 A O（ n） B O（ n2） C O（ nlog2n） D O（ log2n） 26在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 _倍。 A 1/2 B 1 C 2 D 4 27顺序查找法适合于存储结构为 _的线性表。 A顺序存储 B顺序存储或链式存储 C链式存储 D索引存储 28若待排序列已按关键字非递减有序排列，则 _算法的比较次数最少。 A直接插入排序 B快速排序 C归并排序 D选择排序 29 在问题规模很大的情况下， _时间复杂度的时间性能最好。 A 线性阶 B 平方阶 C 指数阶 D 对数
5、阶 30 在一棵二叉树中，度为 0的结点数有 25个，则度为 2的结点数为 _个。 A 24 B 25 C 26 D 不确定 三、简答题（ 3135题，共 50 分） 31（ 10 分）对如下所示的图，完成下列操作： （ 1）求每个顶点的入度和出度； （ 2）画出相应的邻接矩阵； （ 3）画出相应的邻接表； （ 4）画出相应的逆邻接表； （ 5）写出采用邻接表存储时，从 2出发的深度优先搜索的顶点访问序列。 说明：第（ 1）问 1分，第（ 2） -（ 4）问各 2分，第（ 5）问 3分。 32（ 10 分）已知二叉树的中序与后序遍历序列如下： 中序： cbedahgijf 后序： cedbhj
6、igfa （ 1）构造此二叉树，要求画出该二叉树示意图，并有过程说明。 （ 2）其先序遍历序列为？ 说明：第（ 1）问 6分，第（ 2）问 4分。 33（ 10 分）对如下所示的无向网的邻接矩阵，要求 ： （ 1）画出该无向网； （ 2）用克鲁斯卡尔（ kruskal）算法构造相应的最小生成树，要求写出过程。 16418567104872315241032142说明：第（ 1）问 4分，第（ 2）问 6分。 34（ 10 分）以下面数据做叶子结点的权值构造一棵赫夫曼树： 6， 7， 8， 9， 10， 18， 20， 22 （ 1）给出构造的赫夫曼树； （ 2）计算出其带权路径长度。 说明：第
7、（ 1）问 5分，第（ 2）问 5分。 35（ 10 分）对于下图： （ 1）求出图中的所有拓扑有序序列； （ 2）指出哪一种是采用邻接表存储时拓扑排序算法的运行结果，要求有分析说明。 说明：第（ 1）问 4分，第（ 2）问 6分。 四、综合应用题（ 3638题，共 40分） 36（ 15分） 假设以二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示： typedef char DataType; typedef struct BiTNode DataType data; struct BiTNode *lchild, *rchild; /左右孩子指针 BiTNode; typedef
8、 BiTNode *BiTree; 编写递归算法：对于二叉树中每一个元素值为 x的节点，删去以它为根的子树，并释放相应的空间。 37（ 15分） 已知线性表中的元素以值递增有序排列，并以单链 表作为存储结构。试写一高效的算法，删除表中所有值大于 mink 且小于 maxk 的元素（若表中存在这样的元素），同时释放被删结点空间，并分析算法的时间复杂度（注意： mink和 maxk 是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。要求：关键之处给出注释。 单链表的类型定义如下： typedef struct node DataType data; struct node *next LinkNode, *LinkList; 38（ 10分） 试编写一个算法，识别依次读入的一个以 为结束符的字符序列是否为形如序列 1&序列 2模式的字符序列。其中序列 1和序列 2中都不含字符 &，且序列 2是序列 1 的逆序列。例如： a+b&b+a是属该模式的字符序列，而 1+3&3-1则不是。
