-2011年河北工业大学802数据结构考研试题

数据结构试题集（8套卷子+答案）《数据结构》试卷一一、填空题：（共２０分）1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。

2、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是。

3、在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。

4、二叉树的前序遍历序列等同于该二叉树所对应森林的遍历序列5、对一棵二叉排序树，若以遍历该树，将得到一个以关键字递增顺序排列的有序序列。

6、三个结点a,b,c组成二叉树，共有种不同的结构。

7、在AVL树中，由于在Ａ结点的右孩子的右子树上插入结点，使Ａ结点的平衡因子由-1变为-2，使其失去平衡，应采用型平衡旋转。

8、图的遍历有两种,它们是。

9、堆排序的时间复杂度为。

10、在含有N个结点的二叉链表中有空链域，通常用这些空链域存储线索，从而得另一种链式存储结构----线索链表。

二、单项选择题（共２０分）１、若进栈序列为１，２，３，４，假定进栈和出栈可以穿插进行，则可能的出栈序列是（）（A）２，４，１，３（B）３，１，４，２（C）３，４，１，２（D）１，２，３，４２、有一棵非空的二叉树，（第０层为根结点），其第i层上最多有多少个结点？（）（A）２i（B）２1-i（C）２1+i（D） i ３、设电文中出现的字母为A，B，C，D，E，每个字母在电文中出现的次数分别为９，２７，３，５，１１，按huffman编码，则字母A编码为（）（A）１０（B）１１０（C）１１１０（D）１１１１４、下面关于数据结构的叙述中，正确的叙述是（）（A）顺序存储方式的优点是存储密度大，且插、删除运算效率高（B）链表中每个结点都恰好包含一个指针（C）包含n个结点的二叉排序树的最大检索长度为logn2（D）将一棵树转为二叉树后，根结点无右子树５、程序段：y:＝0while n>=(y+1)*(y+1) doy:=y+1enddo的时间复杂度为（）（A）O(n) （B）O(n2) （C）O(n2/1) （D）O(1)6、排序方法中,关键码比较的次数与记录的初始排列无关的是( )(A) shell排序 (B) 归并排序 (C) 直接插入排序 (D) 直接选择排序7、数组q[0..n-1]作为一个环行队列,f 为当前队头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数总小于n,则队列中元素个数为( )(A) r-f (B) n+f-r (C) n+r-f (D) (n+r-f) mod n8、为了有效的利用散列查找技术,需要解决的问题是:( )Ⅰ:找一个好的散列函数Ⅱ:设计有效的解决冲突的方法Ⅲ:用整数表示关键码值(A) Ⅰ和Ⅲ (B) Ⅰ和Ⅱ (C) Ⅱ和Ⅲ (D)Ⅰ,Ⅱ和Ⅲ9、引入线索二叉树的目的是（）(A) 加快查找结点的前驱或后继的速度(B) 为了能在二叉树中方便的进行插入与删除(C) :为了能方便的找到双亲(D) 使二叉树的遍历结果唯一10、用二分（折半）查找表的元素的速度比用顺序法（）(A) 必然快(B) 必然慢(C): 相等(D): 不能确定三、简答题：（共40分）１、已知某二叉树按中序遍历序列为BFDAEGC，按前序遍历序列为ABDFCEG,试画出该二叉树形状，并写出它的后序遍历序列。

A、 d,c,a,bB、
b,c,d,a C、
c,d,b,a D、
a,c,b,d
4、 若用一个大小为 6的数组来实现循环队列,且 当前 rear和 fr0矶 的值分别为 0和 3,当 从队列中删
除一个元素,再加入两个元素后,rear和 front的 值分别为多少?( )
A、 1和 5
B、 2和 4
C、 4和 2
11)装入下标范围为 0到 6的 Hash表 中,则该表中各关键字的次序为 (
)。
A、 72, 11, 37, 38, 56, 98, 48
B、 11, 48, 37, 38, 72, 98, 56
C、 98, 11, 37, 38, 72, 56, 48
D、 98, 56, 37, 38, 72, 11, 48
河北工业大学 2012年 攻读硕士学位研究生入学考试试题 [口 卷
科目名称 数据结构与程序设计
科目代码 80s 共 3 页
适用专业、领域
计算机技术 (专业学位)
注:所 有试题答案一律写在答题纸上,答 案写在试卷、草稿纸上-律 无效。
一、 填空题 (共 ⒛ 分,每空 2分 。答案一律写在答题纸上,否则无效。)
8 A、 B、 9 C、 10 D、 11
8、 高度为 6的满二叉树,总共具有的结点数是 ( )。
A、 15
B、 25
C、 20
D、 63
( 9、 树的后根遍历序列等同于该树对应的二叉树的
)
A、 先序序列 B、 中序序列 C、 后序序列
1O、 在一非空二叉树的中序遍历序列中,根结点的右边 ( )
A、 只有右子树上的所有结点
1、 写出下面稀疏矩阵的三元组表存储表示

)长 度相等的两个串一定是相等的。
60分 )
四 、 简 答 题 (共
1、
(6分 )如 果关键字是主关键字的话 ,则 对一个无序的数据元素序列经按主关键字排序后得到的 (8分 )由 于线性表的链式存储结构可 以见缝插针的有效地利用存储 空间,所 以线性表的链式存
结果是否是唯一 的?为 什么 ?
2、
储结构的存储密度大于线性表的顺序存储结构 ,这 种说法对吗 ?为 什么 ?
2分 。答 案 一 律 写在 答 题 纸 上 ,否 则 无 效 。 )
的两个数据元素 ,在 物理存储上赋予 位置的一种存
线性表的顺序映象就是逻辑上
储分配方式 。
2、
我们把图中所有顶点加上遍历时经过的所有边构成的子图称为
。
3、
在直接插入排序 、希尔排序 、直接选择排序 、堆排序 、快速排序和基数排序中 ,需 要 内存量最 。
( )虽 说静态链表是用数组来实现的,但 对其进行插入和删除操作时,却 并不涉及数组元素
查找快。
4、
的移动问题 。
5、
6、
( (
(
)线 性表的顺序存储结构是一种随机存取的存储结构 。 )二 叉排序树的形态与记录的读入顺序无关 。
)Hash表 查找是一种不需 比较或需很少 比较的查找方法 。
7、
8、
(
4、
均匀的 Hash函 数 ?
5、
(10分 )请 问什么是稳定排序 ?和 非稳定排序相 比,它 有什么优点 ?为 什么说快速排序 、希尔
(6分 )二 叉排序树 T的 各元素值均不相同,请 问用什么有效方法 ,才 能按递增次序打印出元素
(10分 )什 么是队列的假溢出?通 常可以采用什么办法解决假溢出?

河北工业大学2010年攻读硕士学位研究生入学考试试题[A]卷科目名称数据结构科目代码802 共 4 页适用专业、领域控制科学与工程注：所有试题答案一律写在答题纸上，答案写在试卷、草稿纸上一律无效。

一、填空题（共20分，每空2分。

答案一律写在答题纸上，否则无效。

）1、所谓的双向链表，是指在每一个结点中，有两个指针域。

其中一个指向该结点的直接后继结点，而另一个则指向_____________________。

2、线性表的顺序存储结构是一种____________存取的存储结构。

3、若一棵根树的每个结点最多只有____________孩子，且孩子又有____________之分，次序不能倾倒，则称此根树为____________。

4、满二叉树是指高度为k。

且有____________个钻点的二叉树。

二叉树的每一层上，最多有____________个结点。

5、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是____________。

6、广义表（a，（a，b），d.e，（（i，j），k）的长度是____________，深度是____________。

二、单选题（共18分，每题3分。

答案一律写在答题纸上，否则无效。

）1、下面哪一种情况不利于发挥堆排序的优势____________。

A、待排序的数据量很大B、待排序的数据量小C、待排序的数据中有的数值很大D、待排序的数据相同率高2、如果采用直接选择排序法来排序一个长度为5，且已按相反顺序排序的数组，共需的比较次数是____________。

A、1B、15C、8D、103、在一棵包含n个结点的顺序二义树上，最远的两个结点有多远____________。

A、大约1og2nB、大约21og2nC、大约n2D、大约nlog2n4、折半查找不成功时，指针Low和High的关系是____________。

A、Low<HighB、Low>lighC、Low与High无关 D.Lon=High5、在待排元素序列基本有序的前提下，下面给出的几种排序方法效率最高的是1/ 4。