数据结构试题集（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） ２（B）２

ii?1 （C） ２

i?1 （D） i

３、设电文中出现的字母为A，B，C，D，E，每个字母在电文中出现的次数分别为９，２７，３，５，１１，按huffman编码，则字母A编码为（ ） （A） １０ （B） １１０ （C） １１１０ （D） １１１１ ４、下面关于数据结构的叙述中，正确的叙述是（ ）

（A）顺序存储方式的优点是存储密度大，且插、删除运算效率高 （B）链表中每个结点都恰好包含一个指针

（C）包含n个结点的二叉排序树的最大检索长度为log2n （D）将一棵树转为二叉树后，根结点无右子树 ５、程序段：y:＝0

while n>=(y+1)*(y+1) do y:=y+1 enddo

的时间复杂度为（ ） （A）O(n) （B）O(n) （C）O(n

21/2) （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 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分)

１、 设单链表具有头结点，且表中元素各不相同，试编程在单链表中删除值为\的结点。

２、写出在中序线索二叉树中求结点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)] (B) loc(aij)=loc(a11)+[(j-1)*m+(i-1)] (C) loc(aij)=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. p^.next=h b. p^.next=nil c. p^.next^.next=h d. p^.data=-1 10、下面关于求关键路径的说法不正确的是（ ）

a. 求关键路径是以拓扑排序为基础的

b. 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

c .一个事件的最迟开始时间同以该事件为尾的弧的活动最迟开始时间相同与该活动的持续时间的和

d. 关键活动一定在关键路径上

三、简答题：(共40分)

１、静态查找与动态查找的最大区别是什么? 相应的查找方法有哪些？

2、设a,b,c,d,e,f六个字母出现的概率分别为7,19,2,6,32,3,写出为这六个字母设计huffman编码并画出对应huffman树。

３、写出下列二叉树的前序，中序，后序遍历序列及对应的森林。 A

/ \\ B C \\ / \\ D E F / G

４、画出下列无向图的邻接表存储结构，并由邻接表写出广度优先搜索序列和深度优先搜索序列。 A / | \\ B--C—D \\ | /

E

５、用快速排序方法对下列整数序列进行排序，写出中间及最后结果。

[89,27,52,90,15,28,100,72]

四、设计或分析题：(共20分) １、 已知线性链表的头指针为S，每个结点含有数据域DATA和指针域NEXT， 写出使该

链表倒排元素次序的算法。

2、有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵二叉链表表示的二叉树，根由tree指向。

《数据结构》试卷三

一、填空题：（共２０分）

1、算法是对特定问题求解 的一种描述。

2、数据类型是一个 上的一组操作总称。

3、顺序结构下，线性表的插入操作，最坏情况下的时间复杂度为 。 4、对循环链表判空条件为 (head为头指针)。

5、广义表又称 ,它是由零个或多个 序列。 6、队列已满，但队列空间未被充分利用，此现象称 。

7、对一个树高为k，具有n个结点的完全二叉树，至多只有 层结点的度可小于

2，而 的叶结点集中在左边若干位置上。 8、一个连通图的生成树是一个 连通生成子图。 9、网即 。

10、线性表L=(a1,a2,…,an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 。

二、单项选择题：（共２０分）

1、在数据结构中，从逻辑上可以把数据结构分成---------( ) (A)动态结构和静态结构 (B)紧凑结构和非紧凑结构 (C)线性结构和非线性结构 (D)内部结构和外部结构

2、若进栈序列为1,2,3,4,假定进栈和出栈可以穿插进行，则可能出栈序列为----------( )

(A)2,4,1,3 (B)3,1,4,2 (C) 3,4,1,2 (D)1,2,3,4 3、由三个点可以组成( )种不同的二叉树。 (A) 36 (B) 18 (C)30 (D) 12

4、图 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表表长为M=100，那么应以( )为模。

(A) 97 (B) 50 (C) 200 (D)10

7、连通图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)无需任何处理. 30 74 92 /\\ 65 80 9、堆排序属于（ ）.

(A) 插入排序. (B)交换排序 (C)归并排序 (D)选择排序 10、将下图的森林转换成二叉树,所得结果中正确的是（ ）. A E G / | \\ | / \\ B C D F H I \\ J (A) A (B) A / \\ / \\ B E B E / / \\ / / \\ C F G C F G / / \\ / D H D H / \\ I I / / J J (C) A (D) A / \\ / \\ B E B E \\ /\\ / /\\ C F G C F G \\ / / /\\ D H D H I \\ \\ I J / J

三、简答题：(共40分)

1、什么是稳定排序?什么是不稳定排序?

2、已知某二叉树的中序遍历序列为CBGEAFHD，后序遍历序列为CGEBHFDA，画出该二叉树的前序线索二叉树的二叉链结构的表示。

３、已知某森林转化成二叉树后所对应的顺序存储结构为

序号 数据 请画出该森林

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G H I

４、设有一个无向图 （1） 画出其邻接表，（2）在该邻接表基础上求DFS的顶点序列，（3） 在该邻接表基础上求BFS的顶点序列。 2 3 1 4 5 6

５、试画出对长度为10的有序表进行折半查找的判定树形，并求等概率时查找成功的平均查找长度。

四、 设计或分析题：(共20分)

1、指出以下算法中的错误和低效(费时)之处,并将它改正为一个既正确又高效的算法: PROC DELK(A:ARRAY[1..ARRSIZE] OF INTEGER;LAST,I,K:INTEGER)

{A[1..LAST]含线性表元素,本过程从A[1..LAST]中删除第I个元素起的K个元素}

IF (I<1) OR (I>LAST) OR (K<0) OR (LAST>ARRSIZE) THEN ERROR('ARGUMENT INVAILD')

ELSE FOR COUNT:=1 TO K DO {删除一个元素} [FOR J:=LAST DOWNTO I+1 DO A[J-1]:=A[J]; LAST:=LAST-1] ENDP;{DELK}

2、试以二叉链表作存储结构，编写求二叉树深度的递归算法。

《数据结构》试卷四

一、填空题：（共20分）

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

2、设有字母序列{Q,D,F,X,A,P,N,B,,Y,M,C,W}，请写出按归并排序方法对该序列进行一趟扫描后的结果 。 3、程序 for i:=1 to n do for j:=1 to n do A[i,j]:=0;

的算法复杂度为 。

4、具有m个叶结点的huffman树共有 个结点。

5、完全二叉树T按顺序存放，编号依次为1,2,...,n,则编号为i的结点左孩子如果存在的话，其编号为 。

6、n个顶点的连通图构成一棵生成树，有 条边。 7、图的邻接表中，每个链内结点代表 。

8、AOV-网中的弧和顶点分别表示 。 9、串是由零个或多个 序列。 10、递归有直接和间接两种，其中直接递归是指 。 二、单项选择题：(共20分)

1、在数据结构中，从逻辑上可以把数据结构分成---------( ) (A)动态结构和静态结构 (B)紧凑结构和非紧凑结构 (C)线性结构和非线性结构 (D)内部结构和外部结构

2、编号为1,2,3,4的四辆列车，顺序开进一个栈式结构栈台，则开出栈台顺序有( )种。

(A) 1 (B) 3 (C) 5 (D) 7

3、一维数组和线性表的区别为:---------( )

(A)前者长度固定,后者长度可变. (C)两者长度均固定 (B) 前者长度可变,后者长度固定. (D)两者长度均可变.

4、设用一维数组A[1..n]来存储一个栈,令A[n]为栈底,用整型变量T指示当前栈顶位置,A[T] 为栈顶元素,当从栈中弹出一个元素时,变量T的变化为-------( ) (A)T=T+1 (B)T=T-1 (C)T不变 (D)T=n 5、对所示图,顶点V6的入度为-----------( ) (A)2 (B)3 (C)5 (D)0

V1

V2 V6 V5

V3 V4 6、将n个元素的顺序表倒置，则至少需要的附加空间为－－－－( ) (A)0 (B)1 (C)n (D)n+1

7、有一棵非空的二叉树，其第i层上最多有多少个结点？－－－（ ） （A） ２i （B）２i?1 （C） ２i?1 （D） i

8、n=1000，要求最快，且最省内存的排序方法为－－－－－( ) (A)快速排序 (B)shell排序 (C)归并排序 (D)堆排序

9、在构造散列表时，下面能采用的处理冲突的方法为---------( ) (A)开放定址法 (B)链地址法 (C)直接定址法 (D)再hash法 10、下面关于图的存储的叙述中正确的是

（A）用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关 （B）用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 （C）用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关 （D)用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 三、简答题：(共40分)

1、已知按前序遍历二叉树的结果为ABCD，试问：有几种不同的二叉树可得到这种遍历结果?并依次画出相应树形。

２、什么是堆?试按堆的构造方法，写出对应于序列(26,5,77,1,61,11,59,15,48,19) 的初始堆。

3. 已知如下所示长度为12的表

(jan,fab,mar,apr,may,june,july,aug,sep,oct,nov,dec)

按表中元素顺序构造一棵平衡二叉树,并求出等概率情况下查找成功平均查找长度.

４、已知6行7列稀疏矩阵A的三元组表表示为 N=((1,4,6),(2,3,5),(2,6,2), (4,2,7),(5,1,2),(5,5,1),(5,6,4),(6,1,8),(6,7,8))，试写出该稀疏矩阵及A的对称矩阵的三元组表示。

5、设a,b,c,d,e,f六个字母出现的次数分别为7,19,2,6,32,3,写出为这六个字母设计huffman编码并画出对应huffman树。

四、分析或设计题：(20分)

１、首先根据从键盘上输入的n个整数建立一个单链表，然后按递增次序打印出所有结点的值。

2、假设二叉树用二叉链表作存储结构，设计一个算法计算并输出每个结点的子孙个数。

《数据结构》试卷五

一、填空题：（共２０分） 1、“好”算法应达到的目标正确性，易读性，健壮性和 。 2、广义表的尾元素为 。

3、一维数组存储地址计算公式为 (设b为基地址，每个元素所占存储单元数为l，下标取值范围为(c1,d1))

4、栈简称 结构，它是一种后进先出结构。

5、一棵深度为K，且有2k-1个结点的二叉树称为 。

6、树的带权路径长度为 。 7、P='BEIJING'，R='JING'，则R在P中位置为 。

8、关键字是数据元素中用以标识一个数据元素的某一个 的值， 若此关键字可唯一标识一个记录，则称此关键字为 。

9、设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，已知T1、T2和T3的结点个数分别n1、n2和n3，则二叉树B的根结点的左子树和右子树中的结点个数分别为n1—1和 。

10、如果对于给定的一组权值，所构造出的二叉树的带权路径长度最小，则该树称为________。

二、单项选择题:（共２０分）

1、下列各种结构的物理存储必须占用连续的存储空间的是-----------( ) (A)数组 (B)栈 (C)二叉树 (D)链表

2、用顺序方法将完全二叉树的结点逐层放在数组A[1..n]中，结点A[i]若有右子女，则该右子女是结点------------( )

(A) A[2i-1] (B) A[2i+1] (C) A[i/2](D) A[2i]

3、若进栈序列为1,2,3,4,假定进栈和出栈可以穿插进行，则可能出栈序列为----------( )

(A)2,4,1,3 (B)3,1,4,2 (C) 3,4,1,2 (D)1,2,3,4

4、对如下无向图G，若从顶点V1开始，按深度优先搜索进行遍历，则可能的访问顺序为-----------( )

(A) V1,V2,V3,V4,V5,V6,V7,V8 (C) V1,V2,V3,V4,V8,V5,V6,V7 (B) V1,V2,V4,V8,V5,V6,V3,V7 (D) V1,V2,V4,V5,V8,V3,V6,V7 V1 ／ ＼ V2 V3 ／ ＼ ／ ＼

V4 V5 V6 V7 ＼ ＼ ／ ／ ＼ ││ ／ ＼││／

V8

5、进行二分法查找，则线性表---------------( ) (A)必须以顺序方式存储

本文来源：https://www.bwwdw.com/article/5zdt.html