数据结构试题集（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个结点的二叉排序树的最大检索长度为log
n
2
（D）将一棵树转为二叉树后，根结点无右子树
５、程序段：y:＝0
while n>=(y+1)*(y+1) do
y:=y+1
enddo
的时间复杂度为（）
（A）O(n) （B）O(n2) （C）O(n2/1) （D）O(1)
6、排序方法中,关键码比较的次数与记录的初始排列无关的是( )
(A) shell排序 (B) 归并排序 (C) 直接插入排序 (D) 直接选择排序
7、数组-1]作为一个环行队列,f 为当前队头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数总小于n,则队列中元素个数为( )
(A) r-f (B) n+f-r (C) n+r-f (D) (n+r-f) mod n
8、为了有效的利用散列查技术,需要解决的问题是:( )
Ⅰ:一个好的散列函数
Ⅱ:设计有效的解决冲突的方法
Ⅲ:用整数表示关键码值
(A) Ⅰ和Ⅲ (B) Ⅰ和Ⅱ (C) Ⅱ和Ⅲ (D) Ⅰ,Ⅱ和Ⅲ
9、引入线索二叉树的目的是（）
(A) 加快查结点的前驱或后继的速度
(B) 为了能在二叉树中方便的进行插入与删除
(C) :为了能方便的到双亲
(D) 使二叉树的遍历结果唯一
10、用二分（折半）查表的元素的速度比用顺序法（）
(A) 必然快(B) 必然慢(C): 相等(D): 不能确定
三、简答题：（共40分）
１、已知某二叉树按中序遍历序列为BFDAEGC，按前序遍历序列为ABDFCEG,试画出该二叉树形状，并写出它的后序遍历序列。
２、取适当Hash函数及处理冲突的方法，试在0--10散列地址空间中对关键字序列(2,41,53,46,30,13,01,67)构造Hash表，并求出等概率下查成功的平均查长度。
３、已知一组元素为(46,25,78,62,12,37,70,29)，画出按元素排列输入生成的一棵二叉排序树，（要求写出每插入一个元素时二叉排序树形状）
４、对下面数列{51,28,39,75,63,11,37,42,31}利用shell排序算法进行排序，试画出每遍排序结束时数列状态。并注明选用的增量序列d1,d2,......
５、如图所示，对图Ｇ用prim算法构造最小生成树（由顶点f开始），要求能反映出树中顶点与边加入的顺序。
b 6 e
2 5
a d 4
3 3
c f
5
四、设计或分析题：(共20分)
１、设单链表具有头结点，且表中元素各不相同，试编程在单链表中删除值为"x"的结点。
２、写出在中序线索二叉树中求结点p^的中序后继结点的算法。（注：该树是己中序线索化了的二叉树，且p^结点己知）
《数据结构》试卷二
一、填空题：（共２０分）
数据结构与算法分析答案1、数据结构研究数据的结构。
2、对算法从时间和空间两方面进行度量，分别称为分析。
3、线性表是n个元素的。
4、线性表的存储结构有。
5、栈和队列分别称为的线性表。
6、二叉树第i层上最多有个结点。
7、一个二叉树中每个结点最多只有个孩子。
8、Hash技术关键是两个方面。
9、二叉排序树若左子树不空，则左子树上的所有结点值均它的根结点值。
10、AOV一网以结点和有向边分别代表。
二、单项选择题：（共２０分）
1、下列各种结构的物理存储必须占用连续的存储空间的是-----------( )
(A)数组 (B)栈 (C)二叉树 (D)链表
2、由前根排序序列和中根排序序列( )唯一确定一棵二叉树。
(A)能 (B)不能 (C)不一定。
3、同一记录结构中的各数据项的类型( )一致。
(A)必须 (B) 不必 (C)不能 (D)不可能。
4、4个元素进S栈的顺序是A,B,C,D,经运算POP(S)后栈顶元素是----------( )
(A) A (B) B (C) C (D) D
5、有n个顶点e条边的无向图G,它的邻接表中的表结点总数是----------( )
(A) 2n (B)n (C) 2e (D) e
6、二维数组Amn按行序为主序存放在内存,每个数组元素占1 个存储单元 , 则元素 aij 的地址计算公式是:________( )
(A) loc(aij)=loc(a11)+[(i-1)*m+(j-1)]

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。