当前位置：搜档网 › 数据结构试题集(8套卷子+答案)

数据结构试题集(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

（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、数组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) 为了能在二叉树中方便的进行插入与删除

(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

四、设计或分析题：(共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)]

(B) loc(aij)=loc(a11)+[(j-1)*m+(i-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树。

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

/ \

B C

\ / \

D E F

４、画出下列无向图的邻接表存储结构，并由邻接表写出广度优先搜索序列和深度优先搜索序列。

/ | \

B--C—D

\ | /

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

[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不能为空集

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

(A) A (B) A

/ \ / \

B E B E

/ / \ / / \

C F G C F G

/ / \ /

D H D H

/ \

I I

/ /

J J

/ \ / \

B E B E

\ /\ / /\

C F G C F G

\ / / /\

D H D H I

\ \

I J

三、简答题：(共40分)

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

2、已知某二叉树的中序遍历序列为CBGEAFHD，后序遍历序列为CGEBHFDA，画出该二叉

树的前序线索二叉树的二叉链结构的表示。

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

请画出该森林

４、设有一个无向图（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[https://www.sodocs.net/doc/3917417379.html,ST]含线性表元素,本过程从A[https://www.sodocs.net/doc/3917417379.html,ST]中删除第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

V2 V6 V5

V3 V4

6、将n个元素的顺序表倒置，则至少需要的附加空间为－－－－( )

(A)0 (B)1 (C)n (D)n+1

7、有一棵非空的二叉树，其第i层上最多有多少个结点？－－－（）

（A）２i（B）２1-i（C）２1+i（D） i

8、n=1000，要求最快，且最省内存的排序方法为－－－－－( )

(A)快速排序 (B)shell排序 (C)归并排序 (D)堆排序

9、在构造散列表时，下面能采用的处理冲突的方法为---------( )

(A)开放定址法 (B)链地址法 (C)直接定址法 (D)再hash法

10、下面关于图的存储的叙述中正确的是

（A）用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关（B）用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关（C）用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关（D)用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关

三、简答题：(共40分)

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

２、什么是堆?试按堆的构造方法，写出对应于序列(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

／＼

V2 V3

／＼／＼

V4 V5 V6 V7

＼＼／／

＼││／

5、进行二分法查找，则线性表---------------( )

(A)必须以顺序方式存储

(B) 必须以链接方式存储,且数据元素已按值排好序

(C)必须以链接方式存储

(D) 必须以顺序方式存储,且数据元素已按值排好序

6、从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)一端，这种排序方法称为------------( )

(A) 选择排序 (B) 归并排序 (C) 直接插入排序 (D) 快速排序

7、某二叉树的前序遍历结点访问顺序为A B C D E F G，中序遍历结点访问顺序为C B D

A F G E,则其后序遍历结点访问顺序为----------------( )

(A) C D B G F E A (B) C D G F E A B

8、对n个记录的序列进行快速排序，所需的辅助空间为( )

(A) O(1) (B) O(log

n) C) O(n) (D) O(n2)

9、下列哪一个关键码序列不符合堆的定义?

A)A、C、D、G、H、M、P、Q、R、X

B)A、C、M、D、H、P、X、G、Q、R

C)A、D、P、R、C、Q、X、M、H、G

D)A、D、C、M、P、G、H、X、R、Q

10、如果要求一个线性表既能较快查找，又能适应动态变化要求，可采用查找方法-------( )

(A)分块 (B)顺序 (C)二分 (D) 散列

三、简答题：(共40分)

1、"不管是按(a) 先根顺序 (b)中根顺序 (c)后根序遍历二叉并列出二叉树的结点列, 其终结结点都以相同的相对顺序出现."试判断这句话正误,并说明理由

２、通过插入关键字序列(3,26,37,24,12,20,15)构造一棵3阶Ｂ-树的过程：

３、试写出稀疏矩阵M及其转置矩阵M'的三元组表。

┌15 0 0 22 0 -15 ┐

│0 11 3 0 0 0 │

M=│0 0 0 -6 0 0 │

│0 0 0 0 0 0 │

│91 0 0 0 0 0 │

└ 0 0 28 0 0 0 ┘

４、对图中的每一棵树，给出其二叉树表示，并把相应森林转换为一棵整二叉树，

1 9 11

2 10 12 13

3 4 5 14 15

6 7

５、已知一AOV网，求出：

⑴：每个事件最早发生时间，最迟发生时间?

⑵：完成整个工程至少需要多少时间?

6 2 1 9

7 2

1 4 5 9

3 1 7 8 4

5 2

4 6 4

五、算法分析与设计：(20分)

１、向单链有序表中插入元素为X的结点，使得插入后仍然有序。

2、试以二叉链表作存储结构，编写计算二叉树中叶子结点数目的递归算法。

《数据结构》试卷六

一、填空题：（共20分）

１、在计算机中可使用一批连续的存储单元来存放数组，称为数组的顺序分配，一般有两种存储方式：分别是为主存储，

２、两栈合用空间，判栈满的条件为。

３、ADT称为。

４、线性表有两种存储结构，分别为。

５、Head(Tail(Head(((a,b),(c,d))))= 。

６、队列简称结构，循环队列判队空条件为。

７、如图：该树度为，树深度为，树的路径长度为。

/ │\

B C D

／＼

E F

＼

８、集合结构中的数据元素之间，除了的联系之外，没有其他关系。

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

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

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

1、若进栈序列为１，２，３，４，假定进栈和出栈可以穿插进行，则可能的出栈序列是－－－－－（）

（A）２，４，１，３（B）３，１，４，２

（C）３，４，１，２（D）１，２，３，４

2、有一棵非空的二叉树，（第０层为根结点），其第i层上最多有多少个结点？

－－－－－－－－－－－－－－－－－（）

（A）２i（B）２1-i（C）２1+i（D） i

3、设电文中出现的字母为A，B，C，D，E，每个字母在电文中出现的次数分别为9，27，3，5，11，按huffman编码，则字母E编码为－－－－－－（）

（A）１０（B）１１０（C）１１１０（D）１１１１

4、下面关于数据结构的叙述中，正确的叙述是－－－－－－－（）

（A）顺序存储方式的优点是存储密度大，且插、删除运算效率高

（B）链表中每个结点都恰好包含一个指针

（C）包含n个结点的二叉排序树的最大检索长度为log-2n

（D）将一棵树转为二叉树后，根结点无右子树

5、程序段FOR I:=N-1 DOWNTO 1 DO

FOR J:=1 TO I DO

IF A[J]>A[J+1] THEN

A[J]与A[J+1] 对换；

其中n为正整数，则最后一行的语句频度在最坏情况下是（）

（A）O(n)（B）O(nlogn)（C）O(n3)（D）O(n2)

6、某二叉树的前序遍历结点访问顺序为A B C D E F G，中序遍历结点访问顺序为C B D

A F G E,则其后序遍历结点访问顺序为----------------( )

(A) C D B G F E A (B) C D G F E A B

7、对n个记录的序列进行快速排序，所需的辅助空间为--------------( )

(A)O(1) (B)O(log

n) (C)O(n) (D)O(n2)

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

(A) V1 V2 V3 V4 V5 V6 V7 V8 (B) V1 V2 V6 V3 V4 V7 V8 V5

／＼

V2 V3

／＼／＼

V4 V5 V6 V7

＼＼／／

＼││／

9、如果要求一个线性表既能较快查找，又能适应动态变化要求，可采用查找方法-------( )

(A) 分块 (B) 顺序 (C) 二分 (D) 散列

10、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S 的容量至少应该是（）

（A）6 （B）4 （C）3 （D)2

三、简答题：(共40分)

１、设F是一个森林，B是按自然对应关系，由F构成的二叉树，试问F中非终端结点的个数与B中空右链的个数之间有什么数量关系?

２、试画出对应于公式 y=3ln(x+1)-a/x2的树和相应的中序后继线索二叉树：

３、假设字符a,b,c,d,e,f出现的概率分别为0.07,0.09,0.12,0.22,0.23,0.27,求最优huffman编码，并画出huffman树。

４、对下面有向图，求⑴强连通分量⑵邻接矩阵：

F B A

G D C

５、试回答在插入排序，起泡排序，选择排序，shell排序，堆排序，二路归并排序，快速排序和基数排序的排序方法中，哪些是稳定的?哪些是不稳定的?并为任一种不稳定的排序方法举出一个不稳定实例?

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

1、试以单链表作存储结构：实现线性表的就地逆置算法：即在原表的存储空间内将线性表(a1,a2,....an)逆序为(an,an-1,...,a1)

2、以二叉链表作存储结构，编写复制一棵二叉树的递归算法。

《数据结构》试卷七

一、填空题：(共20分)

1、数据对象指具有的数据元素集合。

2、TAIL(HEAD((a,b),(c,d))))= 。

3、二维数组存储地址计算公式(以行序为主)为 (b为基地址，每个元素占存储单元数为l，下标取值范围为(c1,d1),(c2,d2))。

4.一个连通图的生成树是一个 .

5、顺序存储结构下，当时表示栈空。

6、二叉树结点的度 2,且树中子树有左右之分，不能颠倒，故二叉树是一

棵树。

7、高度为Ｋ的二叉树中至多有个结点。

8、对树的遍历有两种。

9.对长度为12的有序表进行折半查找,等概率时查找成功的平均查找长度为 .

10、○如图，树中叶子结点中的数值即该结点的权值，树的带权路径长度、树的 / ＼路径长度分别为。

①○

/ ＼

②○

/ ＼

③④

二、选择题：(共２０分)

1、下面关于线性表的叙述中，错误的是（）

（A）线性表采用顺序存储，必顺占用一片连续的存储单元。

（B）线性表采用顺序存储，便于进行插入和删除操作。

（C）线性表采用链接存储，不必占用一片连续的存储单元

（D）线性表采用链接存储，便于插入和删除操作。

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

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

3、将n个元素的顺序表倒置，则至少需要的附加空间为( )

(A)0 (B)1 (C)n (D)n+1

4、n=1000，要求最快，且最省内存的排序方法为（）

(A)快速排序 (B)shell排序 (C)归并排序 (D)堆排序

5、在构造散列表时，下面能采用的处理冲突的方法为( )

(A)开放定址法 (B)链地址法 (C)直接定址法 (D)再hash法

6、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是

（A）M1（B）M1+M2（C）M3（D）M2+M3

7、在下列存储形式中，哪一个不是树的存储形式

A）双亲表示法 B）孩子链表表示法

B）孩子兄弟示法 D）顺序存储表示法

8、以下哪一个不是队列的基本运算?（）

（A）从队尾插入一个新元素

（B）从队列中删除第i个元素

（C）判断一个队列是否为空

（D）读取队头元素的值

9、下面关于图的存储的叙述中正确的是（）

（A）用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关（B）用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关（C）用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关（D）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10、对线性表进行二分法查找，其前提条件是

（A）线性表以顺序方式存储，并且按关键码值排好序

（B）线性表以顺序方式存储，并且按关键码值的检索频率排好序

（C）线性表以链接方式存储，并且按关键码值排好序

（D）线性表以链接方式存储，并且按关键码值的检索频率排好序

三、简答题：(共4０分)

１、把图所示树表示成二元组形式和广义表形式：

／＼

b c

／＼＼

d e f

／／＼

g h I

２、画出下列无向图的邻接表存储结构，并由邻接表写出广度优先搜索序列和深度优先搜索序列：

／│＼

B─C─D

＼│／

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

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

４、如图所示的５阶B-树，试画出插入96后B-树的形状。

│10 15││35 40││55 60 68││72 75 80 85││92 95 98 100│

└───┘└───┘└────┘└──────┘└──────┘

５、如图所示，对图G用prim算法构造一棵最小生成树，(由顶点a开始)要求能反映出树中顶点与边加入的顺序：

b e

6 5 5

a d 6

5 1 4 6

c f

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

1、已知n个数据存入数组A[1..n]中，使用简单选择排序方法对数组中数据进行从大到小排序，写出算法。

2、写出对二叉树进行中序遍历的非递归算法

proc inorder(bt);{bt为二叉树根结点指针}

《数据结构》试卷八

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

1、线性结构是数据元素的非空有限集,存在唯一的最后一个元素,除该元素外,其余元素有直接后继.

2、Head[Tail[(b,k,m,g)]]= .

3、对n阶对称矩阵进行压缩存储,一般只存储中元素,此时只需个元素的存储空间.

4.带权路径长度最小的二叉树称做 .

5、若P指向单链表的尾结点时，则有P^.NEXT= 。

6、如图： a 该树中叶子结点,分支结点, 该树度分别为。 / | \

b c d

/ \

e f

7、对顺序栈,当时表示栈满.若再有新元素入栈,则栈溢出。

8、对二叉树以某种遍历并加上线索的过程称为。

9、有序表是线性表(a1,a2,....an),并且表中元素关键字值ai.key有下列关系

10、AOV-网结点和有向边分别表示 .

二、选择题：（共20分）

1、下面关于线性表的叙述中，错误的是（）

（A）线性表采用顺序存储，必顺占用一片连续的存储单元。

（B）线性表采用顺序存储，便于进行插入和删除操作。

（C）线性表采用链接存储，不必占用一片连续的存储单元

（D）线性表采用链接存储，便于插入和删除操作。

2、用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（）

（A）94、32、40、90、80、46、21、69 （B）32、40、21、46、69、94、90、80 （C）21、32、46、40、80、69、90、94 （C）90、69、80、46、21、32、94、40 3、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）

（A）M1（B）M1+M2（C）M3（D）M2+M3

4、用快速排序法对包含n个关键字的序列进行排序，最环情况下的执行时间为（）

（A）O(log2n) （B）O(n) （C）O(nlog2n) （D）O(n2)

5、以下数据结构中哪一个是线性结构?（）

（A）有向图（B）栈（C）线索二叉树（D）B树

6、单链表的每个结点中包括一个指针link，它指向该结点的后继结点。现要将指针q指向的新结点插入到指针p指向的单链表结点之后，下面的操作序列中哪一个是正确的?（）

A)q:=p^.link; p^.link:=q^.link;

B)p^.link:=q^.link; q:=p^.link;

C)q^.link:=p^.link; p^.link:=q;

D)p^.link:=q; q^.link:=q^.link;

7、以下哪一个不是队列的基本运算?（）

（A）从队尾插入一个新元素

（B）从队列中删除第i个元素

（C）判断一个队列是否为空

（D）读取队头元素的值

8、对线性表进行二分法查找，其前提条件是（）

（A）线性表以顺序方式存储，并且按关键码值排好序

（B）线性表以顺序方式存储，并且按关键码值的检索频率排好序（C）线性表以链接方式存储，并且按关键码值排好序

（D）线性表以链接方式存储，并且按关键码值的检索频率排好序 9、下列哪一个关键码序列不符合堆的定义?（）

（A）A、C、D、G、H、M、P、Q、R、X

（B）A、C、M、D、H、P、X、G、Q、R

（C）A、D、P、R、C、Q、X、M、H、G

（D）A、D、C、M、P、G、H、X、R、Q

10、将下图的森林转换成二叉树,所得结果中正确的是( )。

A E G

/ | \ | / \

B C D F H I

(A) A (B) A

/ \ / \

B E B E

/ / \ / / \

C F G C F G

/ / \ /

D H D H

/ \

I I

/ /

J J

/ \ / \

B E B E

\ /\ / /\

C F G C F G

\ / / /\

D H D H I \ \ I J /

三、简答题（共40分）

数据结构试题及答案10套

一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价,不包括如下（B ）方面的内容。Ａ.健壮性和可读性Ｂ．并行性C。正确性Ｄ．时空复杂度 2.2．在带有头结点的单链表ＨL中,要向表头插入一个由指针p指向的结点，则执行（A ). Ａ. p－〉ｎｅxt=HL->nexｔ; ＨL-〉nexｔ=p; B． p-〉next=HL；ＨL=p；Ｃ。p-＞ｎext=HＬ； p＝HL；Ｄ. HL=p; ｐ－〉next＝ＨL； 3.3．对线性表,在下列哪种情况下应当采用链表表示？( B ）Ａ.经常需要随机地存取元素 B。经常需要进行插入和删除操作 C。表中元素需要占据一片连续的存储空间D．表中元素的个数不变 4. 4.一个栈的输入序列为１ 2 3，则下列序列中不可能是栈的输出序列的是( C ） A. 2 3 1 ??? B. ３ 2 1 C。 3 １ 2 ??? D. 1 ２３ 5. 5.AＯV网是一种（D ）。 A．有向图Ｂ．无向图Ｃ．无向无环图D．有向无环图 6.6。采用开放定址法处理散列表的冲突时,其平均查找长度（Ｂ)。 A．低于链接法处理冲突B．高于链接法处理冲突Ｃ.与链接法处理冲突相同 D。高于二分查找 7.7。若需要利用形参直接访问实参时，应将形参变量说明为（D ) 参数. Ａ。值Ｂ。函数 C.指针 D。引用 8.８．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ A )。 A。行号 B.列号 C．元素值 D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为( D )。 A。O（loｇ 2n) B．Ｏ（nlog 2 n） C。０（n) D.0 （n2） 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C ). Ａ．O(n） B. Ｏ(1） C。 O（log 2 n） D. O(n2)二、运算题（每题 6 分，共２４分）

十套数据结构试题及答案55426知识讲解

十套数据结构试题及答案55426

数据结构试卷（一）一、单选题（每题 2 分，共20分） 1.栈和队列的共同特点是( a )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( d ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( d ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。c A．688 B．678 C．692 D．696 5.树最适合用来表示( c )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( d ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1] 中，现进行二分查找，则查找A［3］的比较序列的下标依次为( c d ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 c n） D. O A. O（1） B. O（n） C. O（1og 2 （n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ c d）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( a )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：____时间正确性_____、____占用内存_ 易读性____、____复杂度__强壮性___和_____准确度_ 高效率___。

数据结构试卷带答案

数据结构试卷（一）一、选择题（20分） 1．组成数据的基本单位是（ 1.C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（D）的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（.A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（.C ）。 (A) 6 (B) 4 (C) 3 (D) 2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（B）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（B ）的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序二、填空题(30分) 1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________，在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i

数据结构期末考试试题及答案

《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 、 1. 对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 (c )。 (A)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和根结点的值 b ■

东南大学十套数据结构试题及答案

数据结构试卷（一）三、计算题（每题 6 分，共24分） 1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。 A 0 1 2 3 4 5 6 7 dat a nex t 2. 3.已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 4.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。四、阅读算法（每题7分，共14分） 1.LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； } return L； } 请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a 1,a 2 , …,a n ）,写出算法执行后的返回值所表示的线性表。 2.void ABC(BTNode * BT) {

if BT { ABC (BT->left); ABC (BT->right); cout<data<<' '; } } 该算法的功能是：五、算法填空（共8分）二叉搜索树的查找——递归算法: bool Find(BTreeNode* BST,ElemType& item) { if (BST==NULL) return false; //查找失败 else { if (item==BST->data){ item=BST->data;//查找成功 return ___________;} else if(itemdata) return Find(______________,item); else return Find(_______________,item); }//if } 六、编写算法（共8分）统计出单链表HL中结点的值等于给定值X的结点数。 int CountX(LNode* HL,ElemType x)

数据结构试卷带答案

数据结构试卷带答案问题说明部分题目或答案有问题，现将已经发现的公布如下，同学在作这些模拟题的时候应着重做题方法的理解，遇到问题以教材或课件为准，不确定的地方可找同学商量或问我（1）试卷1第一套填空题第1题，试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致，以教材或课件为准，实际上front指向的是队头元素，rear指向当前尚未被占用的第一个队列空间，队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材（2）试卷1第一套应用题第5题，不声明邻接点顺序时默认编号最小的邻接点为第一邻接点，该图的深度优先遍历序列为123465,答案错。此外，当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定，如试卷1第二套填空题第8题（3）试卷1第五套应用题第4题，两种方法处理冲突的方法下所求ASL值相等都为7/6 （4）试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件，大顶堆满足ki>=k2i p->rlink->llink=p->llink;此外，注意课堂中讲的指针名和操作方法（12）第4套填空题第6题答案错，设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有__100___个空指针域。

（13）第5套选择第8题答案应为A:设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为(A) abedfc (14)第5套应用题第3题题目未指明查找方法，没法作（15）第6套选择第5题应选B，实际是任意结点至多只有一个孩子：设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是(B) 高度等于其结点数（16）第7套填空1题问题本身错，设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为____s->left_____=p；s->right=p->right；___p->right_______=s；s->right->left=s；（设结点中的两个指针域分别为left和right）。（17）第8套填空题第8题答案错（18）第7套选择第3题题目错，应以60为基准关键字，答案为C．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字60为基准而得到的一趟快速排序结果是（）。 (C) 42，40，55，60，80，85 （17）第6套填空9题．快速排序算法的空间复杂度平均情况下为_O(logn)_，最坏的情况下为_O(n)_。(18)第9套填空第3题，题目说循环队列有m个元素实际指循环队列总长为m，此外，该题关于队头和队尾指针的约定不同于教材（19）第9套填空第4题答案错，9个元素冒泡排序，第一趟比较次数为8，最多8趟

数据结构试卷和答案

《数据结构》试题参考答案（开卷）（电信系本科2001级 2002年12月）一、回答下列问题 (每题4分，共36分) 1. 某完全二叉树共有15381个结点，请问其树叶有多少个？答：n2=?n/2?=?15381/2?=7691(个) 2. 假设有二维数组A 7×9，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1000，末尾元素A[6][8]的第一个字节地址为多少？若按列存储时，元素A[4][7]的第一个字节地址为多少？答：① 末尾元素A[6][8]的第一个字节地址＝1000＋（7行×9列—1）×6B ＝1000＋62×6=1372 ②按列存储时，元素A[4][7]的第一个字节地址＝1000＋（7列×7行＋4）×6B ＝1000＋53×6=1318 3. 在KMP 算法中，已知模式串为ADABBADADA ，请写出模式串的next[j]函数值。答：根据 0 当j ＝1时 next[ j ]＝ max { k |1

数据结构试题(含答案)

数据结构试题（含答案） 1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称非线性结构 2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。 4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没． 6．数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点，其余每个结点的后续结点可以任意多个。 7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8．评估一个算法的优劣，通常从时间复杂度和空间复杂度两个方面考察。 9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 11．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。13．在顺序表中插入或删除一个数据元素，需要平均移动 n 个数据元素，移动数据元素的个数与位置有关 14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用顺序存储结构 15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。 16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的 17．带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18．栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循后进先出的原则。19．空串是零个字符的串，其长度等于零。空白串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。 20．组成串的数据元素只能是单个字符。 21．一个子串”str”在主串”datastructure”中的位置是 5 。 22．字符串中任意个连续字符构成的部分称为该串的子串。 23．二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 540个字节；M的第8列和第5行共占108个字节24．稀疏矩阵一般的压缩存储方法有两种，即三元组表和十字链表。 25．广义表（（a），（（b），c），（（（d））））的长度是 3 ，深度是 4 。 26．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0＝ n2+1 。 27．在有n个结点的二叉链表中，空链域的个数为__n+1__。 28．一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29．深度为5的二叉树至多有 31 个结点。 30．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为69 。

数据结构试题及答案

第一章概论一、选择题 1、研究数据结构就是研究（Ｄ）。Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i

数据结构试题(含答案)

一．是非题（正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’)

十套数据结构试题与答案

数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷（一）（二）（三）（四）（五）（六）（七）（八）（九）（十） 9 12 15 17 19 21 24 数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷（一）（二）（三）（四）（五）（六）（七）（八）（九）（十） 27 28 29 31 33 35 37 38 39 40 数据结构试卷(一) 、单选题(每题栈和队列的共同特点是(A ) 。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点用链接方式存储的队列，在进行插入运算时 (C ). 头、尾指针都要修改头、尾指针可能都要修改 (D ) 线性表 2分，共20分) 1. 2. A. C. 3. A. 4. 仅修改头指针 B. 仅修改尾指针 D. 以下数据结构中哪一个是非线性结构? 队列 B.栈 C. 设有一个二维数组 A[m][ n]，假设个空间，问 676(10)，每个元素占制表示。 .688 D. 二叉树 A[2][2]存放位置在 (10)存放在什么位置？脚注(10)表示用10进 A[0][0] 存放位置在644(10), A[3][3] .678 C C ）。 B. A 5.树最适合用来表示( A.有序数据元素 C.元素之间具有分支层次关系的数据二叉树的第k 层的结点数最多为(D ). k .2 -1 B.2K+1 C.2K-1 若有18个元素的有序表存放在一维数组 6. A 7. 692 D . 696 D. 无序数据元素乙间无联系的数据元素之 f k-1 D. 2 A[19]中，第一个元素放 A[1]中，现进行二分查找，则查找 A : 3 ]的比较序列的下标依次为 (C ) A. 1 , 2, 3 B. 9 , 5, 2, 3 C. 9 , 5, 3 D. 9 , 4, 2, 3 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 D. O 8. A. O (1) B. O (n ) C. O (1og 2n ) D. O (n2) 9. 对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时，若选用 H (K ) =K %9作为散列函数，则散列地址为 1的元素有(D )个， A . 1 B . 2 C . 3 10. 设有6个结点的无向图，该图至少应有 ( A.5 B.6 C.7 D.8 二、填空题(每空 1分，共26分) 1.通常从四个方面评价算法的质量： _ 高效率 _______ 和―强壮性 _______ 。 1. 一个算法的时间复杂度为(n 3 +nlog 2n+14n)/ n 2 ,其数量级表示为 —o(n) ____________________ 。 2. 假定一棵树的广义表表示为 A (C, D (E , F , G , H( I , J )),则树中所含的结点数为 __________ 个，树的深度为 ____________ ，树的度为 ___________ 。 .4 条边才能确保是一个连通图。正确性易读性

数据结构试卷B卷(含答案)

《数据结构》试卷B 一、填空题（每空1分，共15分） 1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入和删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。 3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 5. 在具有n个单元的循环队列中，队满时共有个元素。 6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分）（）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）2. 在表结构中最常用的是线性表，栈和队列不太常用。（）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）5.线性表的逻辑顺序与存储顺序总是一致的（）6. 栈和队列是一种非线性数据结构。（）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。（）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

数据结构试题及答案(10套最新)

单选题(每题2分，共20分) 1. 1. 对一个算法的评价，不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中，要向表头插入一个由指针 p 指向的结点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、运算题(每题6分，共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之间存在M 对N (M N)的联系时，称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行，删除操作是在队列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表，在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间一个栈的输入序列为1 2 3， 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网是一种(D ) 有向图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图采用开放定址法处理散列表的冲突时，其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。若需要利用形参直接访问实参时，应将形参变量说明为( B .函数 C .指针 D .引用在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点 9. .0(n 2) (C )。 2 )

数据结构试题及答案

一、判断题： 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（） 8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（） 9、栈和队列逻辑上都是线性表。（） 10、单链表从任何一个结点出发，都能访问到所有结点（） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（） 12、快速排序是排序算法中最快的一种。（） 13、多维数组是向量的推广。（） 14、一般树和二叉树的结点数目都可以为0。（） 15、直接选择排序是一种不稳定的排序方法。（） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（） 19、堆栈在数据中的存储原则是先进先出。（） 20、队列在数据中的存储原则是后进先出。（） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（） 22、哈夫曼树一定是满二叉树。（） 23、程序是用计算机语言表述的算法。（） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（）

数据结构试卷及答案压缩版

《数据结构》试卷及答案 1．算法分析的目的是( )。 A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2．（）是具有相同特性数据元素的集合，是数据的子集。 A.数据符号 B.数据对象 C.数据 D.数据结构 3．用链表表示线性表的优点是( )。 A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 4．输入序列为（A,B,C,D）不可能的输出有（）。 A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D) 5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( )。 A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front 6．设有串t='I am a good student '，那么Substr(t,6,6)=（）。 A. student B. a good s C. good D. a good 7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（）。 A.23 B.33 C.18 D. 40 8．已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（）。 A. Gethead(Gethead(LS)) B. Gettail(Gethead(LS)) C. Gethead(Gethead(Gettail(LS))) D. Gethead(Gettail(LS)) 9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( ) A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10．下列存储形式中，( ) 不是树的存储形式。 A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法 11．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( )。 A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序 12．采用折半查找方法进行查找，数据文件应为（），且限于（）。

大数据结构试题集(含答案)

程序复杂性 3、具有线性结构的数据结构是（ D ）。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（C）。 for(i=0;i=(y+1)*(y+1))

数据结构试题及答案.docx

数据结构试题及答案一、选择题（每小题2分，共20分），每个题的备选答案中，只有一个是正确的，请将答案填写在试题的括号中。 1、对顺序存储的线性表，设其长度为20，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ A ）个元素。 A．10 B．9 C．11 D．12 2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 3、当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行（ B ）语句修改top指针。 A．top++ B．top-- C．top = 0 D．top 4、设入栈顺序为A，B，C，D，E，则出栈序列不可能是（ C ）。A．EDCBA B．ABCDE C．ADEBC D．ABDEC 5、已知关键字序列（46, 79, 56, 38, 40, 84），采用快速排序（以位于最左位置的关键字为基准）得到的第一次划分结果为：（ A ） A．{ 40, 38, 46, 56, 79, 84 } B．{ 38, 46, 79, 56, 40, 84 } C．{ 38, 46, 56, 79, 40, 84 } D．{ 40, 38, 46, 79, 56, 84 } 6、一个有n个顶点和n条边的无向图一定是（ C ）。 A．不连通的 B．连通的 C．有环的 D．无环的 7、在一棵具有n个结点的二叉树的第i层上，最多具有（ B ）个结点。 A．2i B．2i-1 C．2i+1 D．2n 8、对线性表采用折半查找法，该线性表必须（ B ）。 A．采用顺序存储结构B．采用顺序存储结构，且元素按值有序 C．采用链式存储结构 D．采用链式存储结构，且元素按值有序 9、在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（ C ）。A．?(n-1)/2? B．?n/2? C．?n/2? D．?n/2? -1 10、在一个无向图中，所有顶点的度数之和等于所有边数的 ( D ) 倍。 A．3 B．1/2 C．1 D．2 二、填空题（每小题2分，共20分），请将正确的结果，填写在试题的横线上。 1、带头结点的循环链表L为空的条件是。 2、序列A={12, 70, 33, 65, 24, 56}给出对应于序列A的大顶堆HA（以线性数组表示）。 3、每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做________ 排序。 4、设循环队列Q的队头和队尾指针分别为front和rear，队列的最大容量为MaxSize，且规定判断队空的条件为Q.front = = Q.rear，则队列的长度为。 5、已知数组A[0..11][0..8]按行优先存储，每个元素占有5个存储单元，且 A[0][0]的地址为1000（十进制），则A[6][7]的地址为________________。 6、已知广义表A=(a，()，(b，(c)))，则其深度为。 7、在一棵二叉树中，假定度为2的结点个数为5个，度为1的结点个数为6 个，则叶子结点数为__ ____个。

数据结构试题集(8套卷子+答案)

数据结构试题及答案10套

十套数据结构试题及答案55426知识讲解

数据结构试卷带答案

数据结构期末考试试题及答案

东南大学十套数据结构试题及答案

数据结构试卷带答案

数据结构试卷和答案

数据结构试题(含答案)

数据结构试题及答案

数据结构试题(含答案)

十套数据结构试题与答案

数据结构试卷B卷(含答案)

数据结构试题及答案(10套最新)

最新十套数据结构试题及答案

数据结构试题及答案

数据结构试卷及答案压缩版

大数据结构试题集(含答案)

数据结构试题及答案.docx

相关文档

最新文档