武汉纺织大学848数据结构考研真题

1、误 5 往链表中插入一个元素，平均要移动大约一半的元素。
（ A）正确 （ B）错误 6 将一个树转换为二叉树后，根结点没有右孩子。
（ A）正确 （ B）错误 7 由二叉树的中序遍历序列和后序遍历序列可以得到该树的前序遍历序列。
（ A）正确 （ B）错误 8 堆的存储即可以是顺序的，也可以是链接的。
（ A）正确 （ B）错误 9 稀疏炬阵压缩存储后，必会失去随机存取功能。
（ A）正确 （ B）错误 10 若散列表的装载因子小于 1，则可以避免冲突的产生。
（ A）正确 （ B）错误 二、单项选择题 11 计算机所处理的数据一般具备某种内在联系性，这是指 ( )。
（ A）数据和数据之间存在某种关系 （ B）元素和元素之间存在某种关系 （ C）元素内部具有某种结构 （ D）数据项和数据项之间存在某种关系 12 算法的时间复杂度与 ( )有关。
（ A）问题规模 （ B）计算机硬件性能 （ C）编译程序质量 （ D）程序设计语言 13 顺序表的长度与 ( )有关。
（ A）线性表中有多少个结点 （ B）每个结点有多少个字段 （ C）每个结点中各字段的类型 （ D）存储线性表的数。

2、正好等于按（ ）遍历对应的二叉树。
4衡量一个查找算法效率的主要标准是（ ）。
5快速排序的时间复杂度是（ ）。
6两个串相等的充分必要条件是两个串的长度相等且（ ）。
7已知广义表 LS为空表，则其深度为（ ）。
8如果排序过程不改变（ ）之间的相对次序，则称该排序方法是稳定的。
9能够成功完全拓扑排序的图一定是一个（ ）。
10在含 100个结点的完全二叉树中，叶子结点的个数为（ ）。
二、单项选择题（ 1130题，每题 2分，共 40分） 11如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ） A栈 B队列 C树 D图 12算法指的是（ ） A计算机程序 B解决问题的计算方法 C排序算法 D解决问题的有限运算序列 13在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ ） A队列 B栈 C线性表 D有序表 14算术表达式 a+b*(c+d/e)转为后缀表达式后为（ ） A ab+cde/* B abcde/+*+ C。

3、80），对其进行起泡排序的过程中，第二趟排序的结果为（ ）。
5在有序表 A118 中，采用折半查找算法查找元素值等于 A7的元素，所比较过的元素的下标依次为（ ）。
6 设有一棵 Huffman 树的节点总数为 35， 则该 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是描述问题规模的非负整数，下面程序片段的时间复杂度为 _。
x=2; while (xnext ; 。

4、错误4.前缀编码指的是任意字符的编码都是另一个编码的前缀。
（分数：2.00）A.正确B.错误5.往链表中插入一个元素，平均要移动大约一半的元素。
（分数：2.00）A.正确B.错误6.将一个树转换为二叉树后，根结点没有右孩子。
（分数：2.00）A.正确B.错误7.由二叉树的中序遍历序列和后序遍历序列可以得到该树的前序遍历序列。
（分数：2.00）A.正确B.错误8.堆的存储即可以是顺序的，也可以是链接的。
（分数：2.00）A.正确B.错误9.稀疏炬阵压缩存储后，必会失去随机存取功能。
（分数：2.00）A.正确B.错误10.若散列表的装载因子小于 1，则可以避免冲突的产生。
（分数：2.00）A.正确B.错误二、单项选择题(总题数：10，分数：20.00)11.计算机所处理的数据一般具备某种内在联系性，这是指( )。
（分数：2.00）A.数据和数据之间存在某种关系B.元素和元素之间存在某种关系C.元素内部具有某种结构D.数据项和数据项之间存在某种关系12.算法的时间复杂度与( )有关。
（分数：2.00）A.问题规模B.计算机硬件性能C.编译程序质量D.程序设计语言13.顺序表的长度与( )有关。

5、据元素之间关系的不同特性，通常有下列四类基本结构：集合、 _、树形结构和图状结构。
2、算法具有五个重要特性：有穷性、确定性、 _、输入和输出。
3、以下程序段中语句“ +x;”的频度是 _。
for(i=1;i=n;+i)for(j=1;j=n;+j)+x;s+=x;4、在长度为 n 的顺序表中，在第 i(1 i n)个元素之前插入一个元素时，需将_个元素依次向后移动一个位置。
5、已知队列的入队序列是 ABCD，则出队序列是 _。
6、树中结点 A 有 8 个兄弟，结点 B 是结点 A 的双亲，结点 B 的度是 _。
7、在含有 100 个结点的二叉链表中有 _个空链域。
共页第页共 4 页；第 1 页8、在有 200 个顶点的无向图中，边的数目最少是 0，最多是 _。
9、在以下有序表中，采用“折半查找” ，找到 32 需比较 _次。
(5, 8, 11, 12, 15, 20, 32, 41, 57, 60, 80)10、设待排序序列中记录的个数为 n，则堆排序在最坏情况下，其时间复杂度为_。
二、解答。

6、DCBA(10 )2 (10 )AB DCE F GHI KJL MN3 15 8 3 20 36 25 10(Huffman) (10 )4 45 24 53 12 37 93(10 )5(Prim) C (10 )(Kruskal) (10 )ABCDE F21 39 104 75 686 10 30 50 20 40 60(10 )(10 )3 220 401 1002 100 t 1 x x-1 x 3 3。