《数据结构试题集(8套卷子+答案)》由会员分享，可在线阅读，更多相关《数据结构试题集(8套卷子+答案)（28页珍藏版）》请在金锄头文库上搜索。
1、一、填空题：(共2 0分)1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存 取线性表中的元素时，应采用存储结构。2、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是。3、在一棵二叉树中，度为0的结点个数为nO，度为2的个数为n2，则nO二。4、二叉树的前序遍历序列等同于该二叉树所对应森林的遍历序列5、对一棵二叉排序树，若以遍历该树，将得到一个以关键字递增顺序排列的有序序列。6、三个结点a,b,c组成二叉树，共有种不同的结构。7、在AVL树中，由于在A结点的右孩子的右子树上插入结点，使A结点的平衡因子由-1变为-2，使其失去平衡，应采用型平衡旋
2、转。8、图的遍历有两种,它们是。9、堆排序的时间复杂度为。10、在含有N个结点的二叉链表中有空链域，通常用这些空链域存储线索，从而得另一种链式存储结构线索链表。二、单项选择题(共20分)1、若进栈序列为1 ,2,3, 4,假定进栈和出栈可以穿插进行，贝y可能的出栈序列 是( )(A) 2，4，1，3(B)3，1，4，2(C)3，4，1，2(D)1，2，3，42、有一棵非空的二叉树，(第0层为根结点)，其第i层上最多有多少个结点？()(A) 2 i (B)2 i-1 (C) 2 i+i (D) i3、设电文中出现的字母为A，B，C，D，E,每个字母在电文中出现的次数分别为9,2 7,3,5,1
3、1,按huffma n编码，则字母A编码为()(A) 10(B)110(C)1110(D)11114、下面关于数据结构的叙述中，正确的叙述是()(A) 顺序存储方式的优点是存储密度大，且插、删除运算效率高(B) 链表中每个结点都恰好包含一个指针(C) 包含n个结点的二叉排序树的最大检索长度为log2n(D) 将一棵树转为二叉树后，根结点无右子树5、程序段：y: =0while n=(y+1)*(y+1) doy:=y+1enddo的时间复杂度为( )(A)O(n) (B)O(n2 ) (C)O(n1/2) (D)O(1)6、排序方法中,关键码比较的次数与记录的初始排列无关的是( )(A) sh
4、ell排序(B)归并排序(C)直接插入排序(D)直接选择排序7、数组q0. n-1作为一个环行队列,f为当前队头元素的前一位置,r为队尾元素的位 置，假定队列中元素的个数总小于n,则队列中元素个数为()(A) r-f (B) n+f-r (C) n+r-f (D) (n+r-f) mod n8、为了有效的利用散列查找技术,需要解决的问题是:()I :找一个好的散列函数II :设计有效的解决冲突的方法III：用整数表示关键码值(A) I 和III (B) I 和 II (C) II 和III (D) I ,11和III9、引入线索二叉树的目的是()(A) 加快查找结点的前驱或后继的速度(B) 为
5、了能在二叉树中方便的进行插入与删除(C) :为了能方便的找到双亲(D) 使二叉树的遍历结果唯一10、 用二分(折半)查找表的元素的速度比用顺序法()(A) 必然快 (B) 必然慢 (C): 相等 (D): 不能确定三、简答题：(共40分)1、已知某二叉树按中序遍历序列为BFDAEGC,按前序遍历序列为ABDFCEG，试画出该二 叉树形状，并写出它的后序遍历序列。2、取适当Hash函数及处理冲突的方法，试在0-10散列地址空间中对关键字序列 (2,41,53,46,30,13,01,67)构造Hash表,并求出等概率下查找成功的平均查找长度。3、已知一组元素为(46,25,7& 62,12,37
6、,70,29),画出按元素排列输入生成的一棵二 叉排序树，(要求写出每插入一个元素时二叉排序树形状)4、对下面数列51,28,39,75,63,11,37,42,31利用shell排序算法进行排序，试画出每遍排序结束时数列状态。并注明选用的增量序列d1,d2,5、如图所示，对图G用prim算法构造最小生成树(由顶点f开始)，要求能反映出树 中顶点与边加入的顺序。a四、设计或分析题：(共20分)1、设单链表具有头结点，且表中元素各不相同，试编程在单链表中删除值为x的结 点。2、写出在中序线索二叉树中求结点p的中序后继结点的算法。(注：该树是己中序线 索化了的二叉树，且p结点己知)数据结构试卷二、
7、填空题：(共2 0分)1、数据结构研究数据的结构。2、对算法从时间和空间两方面进行度量，分别称 分析。3、线性表是n个元素的。4、线性表的存储结构有。5、 栈和队列分另H称为的线性表。6、二叉树第i层上最多有个结点。7、一个二叉树中每个结点最多只有个孩子。8、Hash技术关键是两个方面。9、二叉排序树若左子树不空，则左子树上的所有结点值均它的根结点值。10、A0V 网以结点和有向边分别代表。、单项选择题：(共2 0分)1、下列各种结构的物理存储必须占用连续的存储空间的是()(A)数组(B )栈(C)二叉树(D)链表2、由前根排序序列和中根排序序列()唯一确定一棵二叉树。(A )能(B)不能(C
8、)不一定。3、同一记录结构中的各数据项的类型()一致。(A)必须 (B)不必(C)不能(D)不可能。4、4个元素进S栈的顺序是A,B,C,D，经运算POP(S)后栈顶元素是()(A) A (B) B (C) C (D) D5、有n个顶点e条边的无向图G,它的邻接表中的表结点总数是()(A) 2n (B)n (C) 2e (D) e6、二维数组Amn按行序为主序存放在内存，每个数组元素占1个存储单元，则元素aij的地址计算公式是:()(A) loc(aij)=loc(a11)+(i-1)*m+(j-1)(B) loc(aij)=loc(a11)+(j-1)*m+(i-1)(C) loc(aij)
9、=loc(a11)+(i-1)*n+(j-1)(D) loc(aij)=loc(a11)+(j-1)*n+(i-1)7、连通图G中有n个顶点,G的生成树是()连通子图.(A)包含G的所有顶点(B)包含G的所有边(C)不必包含G的所有顶点(D) 必须包含G的所有顶点和所有的边8、n=1000,要求最坏情况速度最快的排序方法为()(A)快速排序(B)起泡排序(C)归并排序(D)shell排序9、在一个以h为头的单循环链表中，p指针指向链尾的条件是( )a. pA.next=hb. pA.next=nilc. pA.nextA.next=hd. pA.data=-110、 下面关于求关键路径的说法不
10、正确的是()a. 求关键路径是以拓扑排序为基础的b. 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同c .一个事件的最迟开始时间同以该事件为尾的弧的活动最迟开始时间相同与该活动的 持续时间的和d. 关键活动一定在关键路径上三、简答题：（共40分）1、静态查找与动态查找的最大区别是什么？相应的查找方法有哪些？2、设a,b,c,d,e,f六个字母出现的概率分别为7,19,2,6,32,3,写出为这六个字母设计 huffman编码并画出对应huffman树。3、写出下列二叉树的前序，中序，后序遍历序列及对应的森林。A/ B C / D E F/G4、画出下列无向图的邻接表存储结构，并
11、由邻接表写出广度优先搜索序列和深度优先 搜索序列。A/ | B-CD | /E5、用快速排序方法对下列整数序列进行排序，写出中间及最后结果。89,27,52,90,15,28,100,72四、设计或分析题：（共20分）1、已知线性链表的头指针为S,每个结点含有数据域DATA和指针域NEXT,写出使该 链表倒排元素次序的算法。2、有n个结点的完全二叉树存放在一维数组Al.n中，试据此建立一棵二叉链表表示 的二叉树，根由 tree 指向。一、填空题：(共2 0分)1、算法是对特定问题求解的一种描述。2、数据类型是一个上的一组操作总称。3、顺序结构下，线性表的插入操作，最坏情况下的时间复杂度 。4、
12、对循环链表判空条件为(head为头指针)。5、广义表又称，它是由零个或多个序列。6、队列已满，但队列空间未被充分利用，此现象不。7、对一个树高为k,具有n个结点的完全二叉树，至多只 层结点的度可小于2, 而的叶结点集中在左边若干位置上。8、一个连通图的生成树是一个连通生成子图。9、网即。10、线性表L=(a1,a2, an)用数组表示，假定删除表中任一元素的概率相同，贝V删除一 个元素平均需要移动元素的个数。二、单项选择题：(共20分)1、在数据结构中，从逻辑上可以把数据结构分成()(A) 动态结构和静态结构(B )紧凑结构和非紧凑结构(C )线性结构和非线性结构(D)内部结构和外部结构2、若
13、进栈序列为 1,2,3,4,假定进栈和出栈可以穿插进行，贝可能出栈序列为 ( )(A) 2,4,1,3(B)3,1,4,2(C) 3,4,1,2(D)1,2,3,43、由三个点可以组成()种不同的二叉树。(A) 36(B) 18(C)30(D) 124、图G =(V,R)，其中V是顶点集，R是边集，那么：()(A) V,R均为可空集(B) V可为空集,R不能为空集(C) R可为空集,V不能为空集 (D)V和R均不为空集5、在有序表中使用折半查找法的平均时间是( )(A) O(1)(B) O(n) (C)O(log2n) (D)O(n2)6、用除留余数法求关键字K的Hash函数值时，若Hash表
14、表长为M=100,那么应以()为模。(A) 97(B) 50(C) 200(D)107、连通图G中有n个顶点，G的生成树是()的连通子图。(A)包含G的所有顶点(B)包含G的所有边(C)不必包含G的所有顶点(D)必须包含G的顶点和所有边8、如图所示平衡二叉树 ,插入元素 78 后,应作什么处理,使其仍为一棵平衡二叉树 ( ).(A) LR型平衡调整.56(B) RL型平衡调整./(C) RR型平衡调整.34 85(D)LL型平衡调整./(E)无需任何处理.3074 92/65 809、堆排序属于().(A)插入排序.(B)交换排序(C )归并排序(D)选择排序10、将下图的森林转换成二叉树,所得结果中正确的是().AEG/ | |/ B C DFHIJ(A)A(B)A/ / B EB E/ / / /CF GCFG/ /DHDH/II
