当前位置:文档之家 > 数据结构考试题目及答案

数据结构考试题目及答案

数据结构试题6

一、单项选择题(每小题3分,共30分)

1.设栈的输入序列是1、2、3、4,则______不可能是其出栈序列。( )

[A] 1234 [B] 2134 [C] 1432 [D] 4312

2.在一个具有n个结点的线性链表中查找某个结点,若查找成功,需要平均比较_____个结点。( )

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

3.设每个字符占一个字节,二维数组A中每个元素有6个字符组成,其行下标从0到9,列下标从0到3,元素_____当A按行优先存储起始地址与当A按列优先存储的起始地址相同。( )

[A] A[3][0] [B] A[3][1] [C] A[3][2] [D] A[2][3]

4.具有2000个结点的非空二叉树的最小深度为_______。( )

[A] 9 [B] 10 [C] 11 [D] 12

5.已知某二叉树的后根序列是dabec,中根序列是debac,则先根序列是_____。

( )

[A] acbed [B] decab [C] deabc [D] cedba

6. 无向图中所有边的数目等于所有顶点的度数之和的_____倍。( )

[A] 1 [B] 2 [C] 1/2 [D] 不一定

7.递归函数F(n)=F(n-1)+n+1(n>1)的递归体是_______。( )

[A] F(0)=0 [B] F(1)=1 [C] F(n)=n+1 [D] F(n)=F(n-1)+n+1

8. 若需要在O(nlog2n)的时间内完成对n个元素的排序,且要求排序是稳定的,

则可选择的排序方法是_______。( )

[A] 快速排序[B] 堆排序[C] 归并排序[D] 直接插入排序9.在对n个元素的序列进行排序时,堆排序所需要的附加存储空间是__。( )

[A] O(1) [B] O(log2n) [C] O(n) [D] O(n log2n)

10.假定有K个关键字互为同义词,若用线性探查法把这K个关键字存入散列表中,则总的探查次数至少为______。( )

[A] K-1 [B] K [C] K+1 [D] K(K+1)/22

二、填空题(每小题2分,共20分)

1.对于一个长度为n的顺序存储的线性表,在表头插入元素的时间复杂度为______,在表尾插入元素的时间复杂度为________。

2. 在一棵二叉树中,第5层(根结点为1层)上的结点数最多为____________。

3. 一棵高度为h的理想平衡树中,最少含有______个结点,最多含有________

个结点。

4. 在一个小根堆中,堆顶结点的值是所有结点中的_________,在一个大根堆中,

堆顶结点的值是所有结点中的_________。

5. 在一个具有n个顶点的无向图中,要连通所有顶点则至少需要_________条边。6.假定一个图具有n个顶点和e条边,贝采用邻接矩阵、邻接表表示时,其相应的空间复杂度分别为__________和___________。

7.以二分查找方法查找一个线性表时,此线性表必须是_________存储的________表。

8.在线性表的散列存储中,处理冲突有___________和___________两种方法。9.快速排序在平均情况下的空间复杂度为_____,在最坏情况下的空间复杂度为_____。

10.在一棵20阶B_树中,每个非树根结点的关键字数目最少为_______个,最多为____ 。

三、判断题(认为对的,在题后的括号内打“√”,错的打“ⅹ”,每小题1分,

共10)

1.线性表中,每个结点都有一个前驱和一个后继。()2.有向图的邻接表和逆邻接表中的结点数一定相同。()3. 单链表中要取得某个元素,只要知道该元素的指针即可,因此单链表是随机

存取的存储结构。()

4. 在快速排序、归并排序和shell排序中,稳定的是shell排序。()

5. 对不同的存储结构,检索的方法不同。()

6. 在散列表中,负载因子值越小则存元素时发生冲突的可能性就越大。()

7. 由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树。()

8. 若一棵二叉树的树叶是某子树对称序周游序列中的第一个结点,则它必是该

子树后序周游序列中的第一个结点。()

9. 二叉树按线索化后,任一结点均有指向其前驱和后继的线索。()

10.在采用线性探查法处理冲突的散列表中,所有同义词在表中相邻。()

四、简答题(每题10分,共60分)

1.说明数组和链表的区别,各有何优缺点?

2.回答下列关于堆的一些问题:

(1)堆的定义是什么?

(2)存储表示是顺序的,还是链式的?

(3)设有一个最小堆,其具有最小值、最大值的元素分别可能在什么地方?3.完全二叉树用什么数据结构实现最合适,为什么?

4. 在直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序

和归并排序中,哪些易于在链表(包括各种单、双、循环链表)上实现?5.用下列三种表示法画出下图G的存储结构

数据结构考试题目及答案

(1)相邻矩阵

(2)邻接表

(3)邻接多重表

6.已知序列(70,83,100,65,10,32,7),请给出采用插入排序法对该序列作升序排序时的每一趟结果。

五、算法设计题(每题15分,共30分)

说明:可以使用任何高级程序设计语言或伪(类)程序设计语言。

1.已知非空单链表第一个结点由list 指出,写一算法,交换p 所指结点(不是链表中第一个结点,也不是链表中最后的那个结点)与其下一个结点在链表中的位置,并给出算法的时间复杂度。

2.设计一个算法,统计一个采用邻接矩阵存储、具有n个顶点的无向无权图所有顶点的度。

数据结构试题6答案

一、1. D 2. C 3.B 4. C 5.D 6.C 7.D 8. C 9.A 10. D

二、1.O(n)O(1)2.16 3.2 h 一12 h一1

4.最小值最大值5.n一1 6.O(n 2 )O(n十e)、

7.顺序有序8.开放定址法链接法(次序无先后)

9.O(1og2n)O(n)10.9 19

三、1.X 2.√ 3.X 4.X 5.√ 6.X 7.X 8.√9.X 10.X

四、1.区别:数组占用连续的内存空间,链表不要求结点的空间连续。

各有何优缺点:(1)插入和删除操作。数组插入和删除需移动数据元素,链表插入和删除不移动数据元素,链表比数组易于实现插入和删除操作;

(2)在空间占用方面,数组优于链表;

(3)在数据存取方面,数组是随机存取方式,而2 链表是顺序存取方式。2.(1)堆是n个元素的有限序列K1,K2,…, KN,且满足以下条件:

K i <= K2i且K i <= K2i+1I=1,2,…, n/2 (最小堆)

或K i >= K2i且K i >= K2i+1I=1,2,…, n/2 (最大堆)

(2)因为完全二叉树采用顺序存储更加有效,所以堆应采用顺序存储结构。(3)最小堆的最小值元素必在堆顶,最大值的元素只有在叶结点上。

3.完全二叉树用一维数组实现最合适。(1)不存在空间浪费问题;(2)顺序存储方式下,父子结点之间的关系可用公式描述,访问结点方便。采用链表存储存在空间浪费问题,且不易寻找父结点。

4.在上述排序方法中,只有直接插入排序、冒泡排序、直接选择排序易于在

链表上实现。

5.相邻矩阵:

数据结构考试题目及答案

邻接表:

数据结构考试题目及答案

邻接多重表:

数据结构考试题目及答案

6.初始:(70),83,100,65,10,32,07

第1趟:(70,83),100,65,10,32,07

第2趟:(70,83,100),65,10,32,07

第3趟:(65,70,83,100),10,32,07

第4趟:(10,65,70,83,100),32,07

第5趟:(10,32,65,70,83,100),07

第6趟:(07,10,32,65,70,83,100)

五、算法的ADL描述如下:

算法CHANGE(list,p)

q←list

WHILE(next(q)<>p) DO

q←next(q)

r←next(p)

next(q)←r

next(p)←next(r)

next(r)←p

算法的时间复杂度为O(n)

2.假设邻接矩阵为adjacency (二维数组),顶点的度保存在一维数组A中。

算法的ADL描述如下:

[初始化]

FOR i=1 TO n DO

A[i]←0

FOR i=1 TO n DO

FOR j=1 TO n DO

IF adjacency[i,j]=1 THEN

A[i]←A[i]+1

数据结构试题7

一、单项选择题(每小题2 分,共20 分)

1.序列A,B,C,D,E 顺序入栈,不能获得的序列是: ( )

A.ABCDE B. CDEBA C. EDCBA D.DECAB

2. 通常算法分析中算法的空间复杂度是指: ( )

A. 所需全部空间大小

B. 完成运算所需辅助空间大小

C. 待处理数据所需全部空间大小

D. 存储空间的复杂程度

3. Huffman树是: ( )

A. 最佳二叉树

B. 路径长度最短的二叉树

C. 最佳二叉排序树

D. 加权路径长度最短的二叉树

4. 在单链表中删除P指针後的节点Q 需要修改的指针域个数为: ( )

A.2 B. 4 C. 6 D. 1

5.设n0,n1,n2 分别是二叉树中度为0,1,2 的结点数,则有: ( )

A.n0=n2+1 B. n0=n2-1 C. n0=n1+1 D. n0=n1-1

6.下列说法中错误的是:( )

A. n 个结点的树的各结点度数之和为n-1

B. n 个结点的有向图最多有n*(n-1)条边

C. 用相邻矩阵存储图时所需存储空间大小与图中边数有关

D. 散列表中碰撞的可能性大小与负载因子有关

7.若线性表采用顺序存储结构,每个元素占用4个存储单元,第一个元素的存储地址为100,则第12 个元素的存储地址是:( )

A.113 B. 144 C. 148 D. 412

8. 下列哪一种排序方法的比较次数与纪录的初始排列状态无关?( )

A. 直接插入排序

B. 起泡排序

C. 快速排序

D. 直接选择排序

9. 设有5000 个无序的元素,希望用最快的速度挑选出其中前50个最大的元素,最好选用: ( ) A.冒泡排序B.快速排序C.堆排序D.基数排序

10. 用某种排序方法对序列(25,84,21,47,15,27,68,35,20)进行排序时,序列的

变化情况如下,则所采用的排序方法是: ()

20,15,21,25,47,27,68,35,84

15,20,21,25,35,27,47,68,84

15,20,21,25,27,35,47,68,84

A.选择排序B.希尔排序C.归并排序D.快速排序

二、判断题(每小题1 分,共10 分,对的打√,错的打×)

1. 给出不同输入序列建造二叉排序树,一定得到不同二叉排序树。( )

2. 有向图的邻接表和逆邻接表中的结点数一定相同。( )

3. 图G 的拓扑序列唯一,则其弧数必为n-1(其中n为G 的顶点数)。( )

4. 在索引顺序文件中插入新的记录时,必须复制整个文件。( )

5. 如果某种排序算法是不稳定的,则该方法没有实际的应用价值。( )

6. 对n 个记录进行冒泡排序,在最坏情况下所需要的时间是O(n 2 ) ( )

7. 在线性结构中,每个结点都有一个直接前驱和一个直接后继。( )

8. A VL 树的任何子树都是A VL树。( )

9. B+树既适于随机检索,也适于顺序检索。( )

10. 两个字符串相等的充要条件是两个串包含的字符相同。( )

三、填空题(每空1 分,共15分)

1.用起泡法对n 个关键码排序,在最好情况下,只需做__次比较和_______次移动;在最坏的情况下要做___ _ _ _次比较。

2.若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号,那么当i为_____且大于1时,结点I 的左兄弟是结点___ _,否则结点i 没有左兄弟。

3.具有N 个结点的完全二叉树的深度为________。

4. 树的三种主要的遍历方法是:__ __ ____、____ ____和层次遍历。

5.采用散列技术实现散列表时,需要考虑的两个主要问题是:_____和解决_____ ___。6.在一个带头结点的单循环链表中,p 指向尾结点的直接前驱,则指向头结点的指针head

可用p 表示为head=_______。

7.栈顶的位置是随着_______、_________操作而变化的。

8.已知一棵完全二叉树中共有768 结点,则该树中共有_______个叶子结点。

四、简答题(第1、2 题每小题6 分,第3、4、5 题每小题8 分,共36 分)

1.已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下图1 所示

(1)画出该图的图形;

(2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历,写出相应的遍历序列。

数据结构考试题目及答案

数据结构考试题目及答案

(图1)(图2)

2.将上图2所示的二叉树转换为树或树林(画出连线-删线图和结果图)。

3:设有一组关键码序列:

{6097,3485,8129,407,8136,6615,6617,526,12287,9535,9173,2134,1903,99}

和散列函数:H(key)=key MOD 19。采用线性探测法解决冲突,试在0~18 的散列地址空间中对该关键码序列构造散列表。

4.设有关键码集合K={72,73,71,23,94,16,05,68},将其建成一个堆(画出每步所得的图即可)。

5.从一棵空的A VL 树开始,将关键码xal,wan,wil,zol,yo,xum 逐个插入,画出每插入一个关键码后得到的A VL 树。

五、算法设计(19 分)

用类PASCAL语言或类 C 语言写出将n 个记录用冒泡排序法进行升序排序的算法(第一次冒泡将排序码最小的记录放在第一个位置,第二次冒泡将排序码次最小的记录放在第二个位置……)。

数据结构试题7答案

一.1. D 2. A 3. D 4. D 5. A 6. C 7. B 8. D 9. C 10. D

二.1.×2. √ 3. √4. × 5. ×6. √7. ×8. √9. ×10. ×

三.1.n-1 0 n(n-1)/2 2.奇数i-1 3.[log2N]+1 4.先根后根5.选取好的散列函数冲突(碰撞)6.P↑.next↑.next 7.进栈退栈8.384 四.1. 2、

数据结构考试题目及答案

数据结构考试题目及答案

深度:a,b,d,e,c 广度:a,b,e,d,c 3、

数据结构考试题目及答案

4、

数据结构考试题目及答案

数据结构考试题目及答案

5、

数据结构考试题目及答案

数据结构考试题目及答案

五、TYPE node=RECORD V AR i,j:integer;

key:integer; flag:0..1;

info:datatype X:node;

END; R:arrar[1..n] of node;

FOR i:=1 TO n DO

Begin

flag:=0;

FOR j:=n-1 TO I DO

if R[j+1].key

then begin

flag:=1;

X:=R[j];R[j]:=R[j+1];R[j+1]:=X

End;

if flag

then 算法结束

End

数据结构试题8

一.单项选择题(每小题1 分,15 分)

1. 编号为A,B,C,D 的四辆列车,顺序开进栈式结构的站台,则开出车站的顺序中,不可能出现的次序为: ( )

A. BDAC

B. CBAD

C. ACBD

D. DCBA

2. 两个同义词子表结合在一起的现象称为: ( )

A. 碰撞

B. 拉链

C. 链接

D. 堆积

3. 一棵二叉树若前序和对称序周游得到的节点序列相同,则这棵二叉树满足: ( )

A. 只能是一个节点的二叉树

B. 为空二叉树或者该树所有节点的左子树为空二叉树

C. 只能是空二叉树

D. 为空二叉树或者该树所有节点的右子树为空二叉树

4. 一棵深度为m的满三叉树定义为:或者是空三叉树,或者是第m层有3 1 ? m 个叶节点,其余各层的节点均有三棵(左,中,右)非空子三叉树.对该树按层自左向右从 1 开始顺序编号, 则编号为n的节点,其父节点若存在,则父节点编号为: ( )

数据结构考试题目及答案

5. 有n 个节点的有向完全图的边数为: ( )

A. n

B. n(n-1)

C. 2n

D. n(n-1)/2

6. 广义表L=(((),()),(),())的长度为: ( )

A. 3

B. 0

C. 4

D. 5

7. 设H(key)为散列函数,key 为记录的关键字.在散列表中,记录R1 和R2 的关键字分别为key 1 和key 2 ,称他们为同义词的条件是: ( )

A. key 1 =key 2

B. key 1 =key 2 且H(key 1 )=(key 2 )

C. R1=R2

D. key 1 ≠key 2 且H(key 1 )=(key 2 )

8. 下面那一个不是存储管理考虑的问题: ( )

A.压缩碎片问题

B. 无用节点收集

C. 表节点的顺序

D. 空间溢出管理

9. 不能存储二叉树的存储结构为: ( )

A. 三叉链表

B. 散列表

C. 顺序表

D. 二叉链表2

10.A VL 数不平衡后要调整的情形有: ( )

A. 2 种

B. 4 种

C. 6 种

D. 8 种

11.在排序过程序中,使用辅助存储空间为O(n)的算法是: ( )

A. 插入排序

B. 归并排序

C.起泡排序

D. 快速排序

12.若无向图中有n 个结点,e 条边,则它的邻接表需要表节点数目为: ( )

A. 2e

B. 2e+n

C. 2e+1

D.e+2n

13.字符串的紧缩存储形式是每个字符占: ( )

A. 1 个二进制位

B. 1 个字节

C. 1 个字

D. 1 个结点单元

14.循环队列SQ有m 个单元,其满队条件是: ( )

A. (SQ.rear+1) MOD M=SQ.front

B. SQ.rear=SQ.front

C. SQ.rear=m

D. SQ.front=m

15.通常算法分析中算法的空间复杂度是指: ( )

A. 所需全部空间大小C. 完成运算所需辅助空间大小

B. 待处理数据所需全部空间大小D. 存储空间的复杂程度

二.填空题(每空1 分,共10 分)

1. 数据结构中的节点可分为两大类:___________和___________.

2. 结构的____________是指数据本身所占存储量/整个结构所占存储量.

3. 散列存储方法的关键问题是________________和________________.

4. 一棵树删去根节点就变成_______________.

5. 用二分检索法进行检索时,要求节点事先________________.

6. 设图G 有n个节点,t条边,若d i 为节点v i 的度数,则t=___________.

7. 对于不连通的无向图和不是强连通的有向图进行周游,得到的是:________.

8. 排序方法的稳定性是指排序关键字值相同的记录在排序过程中不改变其原有的_____________关系.

三.多项选择题(错选,多选,漏选均不得分.每小题2 分,共6 分)

1. 根据描述算法的语言不同,可将算法分为:()

A. 形式算法

B.非形式算法

C. 伪语言算法3

D. 运行不终止的程序可执行部分

E. 运行终止的程序可执行部分

2. 能够从任意节点出发访问到其余结点的结构有: ( )

A. 单链表

B. 循环链表

C. 双链表

D. 二叉链表

E. 邻接表

3. 图的常见存储结构可以选取: ( ) A.邻接表B. 邻接矩阵C. 逆邻接表D. 邻接多重表E. 散列表

四.简答题(每小题 4 分,共12 分)

1. 快速排序算法是否稳定?举一个具有六个记录(只考虑排序码)的例子予以说明.

2. 穿线树的最大优点是什么?

3. 简述关键码和排序码的概念.

五.分析计算题(每小题7 分,共21分)

1. 计算如下程序段的时间复杂度.

……

s:=0;

FOR i:=1 TO n DO

BEGIN

t:=1;

WHILE t<=i DO

BEGIN

t:=t*2;

s:=s+t

END

END;

2. 将上三角矩阵(a ij ) n * n的上三角元素逐行存放于数组B[1..m]中(m 充分大),使得B[k]=a ij ,且k=f 1 (i)+f 2 (j)+C,试推导出函数f 1 (i), f 2 (j)和常数C,要求f 1 (i)和f 2 (j)中不含常数项.

3. 关键码序列{Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec},按字母序号排号序为{Apr,Aug,Dec,Feb,Jan,Jul,Jun,Mar,May,Nov,Oct,Sep},然后用二分发进行检索,计算在等概率条件下检索成功的平均查找长度.

六.综合题(5+5+8+10+8)

1. 分步写出将下面树林转换成二叉树的过程.

数据结构考试题目及答案

2.对于下图给出其邻接表,并从顶点1 出发依据存储结构进行深度遍历,写出遍历结果.

数据结构考试题目及答案

3.程序填空:在横线处填入适当的内容,将程序补充完整.

程序功能:在有序表中用二分检索法查找关键码为K的记录,若找到则返回其位置, 找不到则返回零.

类型说明如下:

TYPE node=RECORD

Key: integer;

Info :datatype

END;

table=ARRAY[1..n] OF node;

FUNCTION binfind(r:table;k:integer):integer;

BEGIN

Low:=1; hig:=n; _______1_____

WHILE (______2_____) AND (Y=0) DO

BEGIN

mid : = (low+hig) DIV 2

IF k=r[mid].key THEN y:=mid

ELSE

IF k>r[mid].key THEN _____3______

ELSE _____4_______

END;

Binfind:=y;

END;

4.修改起泡排序算法,反方向进行扫描,即第一趟把排序码最小的记录放到最前头,第二趟把排序码次小的放到第二个位置, 第三趟把排序码第三小的放到第三个位置, 如此反复进行.用类pascal语言给出该算法的程序.(类型说明与上面第3小题相同)

5.试编写一个交换二叉树T中节点的左右子树的类PASCAL语言算法,设节点的类型为:TYPE bitree=^node;

Node=RECORD

Data:datatype;

Lchild,rchild:bitree

END;

数据结构试题8答案

一、1、A 2、D 3、B 4、C 5、B 6、A 7、D 8、C 9、B 10、B 11、B 12、

B 13、B 14、A 15、A

二、1、初等,组合2、存储密度3、散列函数的选取,冲突(碰撞)的解决4、树(森)林5、按关键码排序6、1/2Σdi 7、生成树林8、相对位置

三、1、B C E 2、B C 3、A B C D

四、1、快速排序是不稳定的如对初始类排序码:81 2 5 82 4 1

经第一趟快排后为:〔1 2 5 82 4〕81

经第二趟快排后为:1 〔2 5 82 4〕81

经第三趟快排后为:1 2 〔5 82 4〕81

经第四趟快排后为:1 2 4 5 828181和82相对位置发生了变化2、由于有了线索的存在而使的周游树形结构和找结点在指定次序下的前驱、后继的算法变得很简单、直截了当。

3、关键码是其值能唯一确定一个记录的字段或字段组合,两个记录的关键码不可能相等排序码是排序运算的依据,是结构中的一个或多个字段,两个记录的排序码可以相同

五、1、I=1 时WHILE 循环执行1 次故总排序时间为:Σ[㏒2(i+1)]=Σ[㏒2i]

I=2 时WHILE 循环执行2 次≈n㏒2 n

I=3 时WHILE 循环执行2 次

I=4 时WHILE 循环执行3 次

I=5,6,7 时WHILE 循环执行3 次

I=8 时WHILE 循环执行4 次…

2、k=n+(n-1)+(n-2)+…+〔n-(i-2)+(j-i+1)〕

=n(i-1)-〔i+2+…+(i-1)〕+j=ni-n-(i+1)(i+2)/2+j=〔i 2 +(2n+3)i〕/2+j-(n+1)

所以f1(i)=〔i 2 +(2n+3)i〕/2 ; f2(j)=j ; c=-(n+1)

3、

数据结构考试题目及答案

检索次数

平均查找长度为:1/12(1+2*2+3*4+4*5)=37/12

六、1、

数据结构考试题目及答案

得到:

数据结构考试题目及答案

2、

数据结构考试题目及答案

深度遍历结果为:1,2,3,5,4,6,7,8

3、1、Y=0 2、Low≤High 3、Low:=Mid+1

4、High:=Mid-1

4、V AR R:table;X:node;

i,j:integer;flag:0..1;

1. 循环,i 以-1 为步长,从1 到n-1,执行(n-1 次冒泡)

(1) flag ←0

(2) 循环,j以-1 为步长,从n到i+1 执行

若R〔j〕.key<R〔j-1〕.key

则flag<-1

x ←R〔j〕;R〔j〕←R〔j-1〕;R〔j-1〕←x

(3) 若flag=0 则跳出循环

2.算法结束

5、Procedure exchange_lr_node(t:bitree);

begin

if t=nil

then 算法结束

else begin

q ←t ↑.lchild;

t↑.lchild←t↑.rchild;

t↑.rchild←q;

exchange_lr_node(t↑.lchild);

exchange_lr_node(t↑.rchild)

end;

end;

数据结构试题9

一.单项选择题(每小题1 分,15 分)

1. 作为一个算法必须满足: ( )

A. 2 个要素

B. 4 个要素

C. 5 个要素

D. 7 个要素

2. 双链表中,删除节点P之后的节点Q 需要修改的指针域的个数为: ( )

A. 1

B. 2

C. 3

D. 4

3. 队列是一种: ( )

A. 链表

B. LIFO 表

C. 顺序表

D. FIFO表

4. 串的求子串运算SUBSTR(‘ABCDEF’,2,3) 的引用结果是: ( )

A.‘BCD’B. ‘BC’C. ‘CDE’D. ‘CD’

5. 循环队列SQ有m 个单元,其满队条件是: ( )

A. SQ.rear=SQ.front C. SQ.rear MOD M+1=SQ.front

B. SQ.rear+1=SQ.front

D. SQ.rear =SQ.front MOD M+1

6. 在列主序下顺序的存储数组A 4 * 4 的上三角元素A(3,2)的位置是第: ( )

A. 10 个

B. 7 个

C. 6 个

D. 5 个

7. 广义表D=(a,D)的深度为: ( )

A. 2

B. 1

C. +

D. –

8. 有三个节点A,B,C 可以构成多少种二叉树: ( )

A. 5

B. 8

C. 32

D. 30

9. 有n 个节点的完全二叉树,其深度为: ( )

数据结构考试题目及答案

10.中序序列和后序序列相同的二叉树是: ( )

A. 完全二叉树

B. 满二叉树

C. 所有结点无左孩子的二叉树

D. 所有结点无右孩子的二叉树

11.若有向图中有n 个结点,e 条边,则它的邻接表需要表节点数目为: ( ) A. e

B. 2e

C. e-1

D.e+1

12.克鲁斯卡尔(KRUSKAL)算法求最小生成树,是针对那种图的: ( )

A. 无向图

B. 有向图

C. 连通无向图

D. 连通带权图

13.在排序过程中,使用辅助空间为O(n)的算法是: ( )

A. 插入法

B. 归并法

C. 快速

D. 分配

14.在散列结构中,同义词是指: ( )

A. R1.KEY≠R2.KEY 且HASH(RI.KEY)=HASH(R2.KEY)

B. R1.KEY=R2.KEY

C. R1.KEY=R2.KEY 且HASH(RI.KEY)=HASH(R2.KEY)

D. R1.DA TA=R2.DATA 15.ISAM 文件属于: ( )

A. 顺序文件

B. 散列文件

C. 索引文件

D. 多关键字文件

二.多项选择题(错选,多选,漏选均不得分.每小题1 分,共5 分)

1. 在下列算法中,涉及到栈运算的有: ( )

A. 二叉树的遍历

B. 广度优先搜索遍历

C. 深度优先搜索遍历

D. 表达式求值

E. 基数排序

2. 排序算法在最坏执行情况下,算法的时间复杂度是O(n 2 )的有: ( )

A.插入排序法

B. 块序排序法

C. 堆排序法

D. 归并排序法

E. 基数排序法

3. 稀疏矩阵通常采用的存储方式有: ( )

A. 单链表

B. 循环链表

C. 三元组表

D. 散列表

E. 十字链表

4. 根据排序期间数据规模的大小及数据所处存储器的不同,可以将排序分为:( )

A. 插入排序

B. 希尔排序

C. 交换排序

D. 内部排序

E.外部排序

5. 能够从任一节点访问到其余节点的结构有: ( )

A. 单链表

B. 循环链表

C. 双链表

D. 二叉链表

E. 邻接表

三.填空题(每空1 分,共10 分)

1. 数据的基本存储结构有_________,________,_________,________四种.

2. 排序方法的稳定性是值排序关键字值相同的记录在排序过程中不改变其原有的_____________关系.

3. 算法的确定性是指每条__________________.

4. 散列结构中处理冲突的方法基本上可分为两大类: __________和_________.

5. 文件的操作主要有:___________和__________两类.

四.判断改错题(对的打”√”,错的打”╳”,并说明理由.每小题2 分,判断和说明各得1 分,判断3 错误,全题无分.共10分)

1. 二叉树是度为2 的树. ( )

2. 堆排序是不稳定的,其时间复杂度为O(n log 2 n). ( )

3. 队列是受限的线性表,限制在于节点的位置相对固定. ( )

4. 要完成树的层次遍历一般要利用栈作为辅助结构. ( )

5. 图的最小生成树如果存在,则一般唯一. ( )

五.解释概念题(每小题3 分,共9 分)

1. 三元组表

2. 拓扑排序

3.A VL树

六.简答题(共31分)

1. 把下图森林转化为一棵二叉树,并画出主要转化过程图示.(4 分)

数据结构考试题目及答案

2. 给定权集W={2,3,4,7,8},试构造关于W 的一棵哈夫曼树,并求其加权路径长度WPL 的值.(6 分)

3. 对于下图给出其邻接表,并从顶点 1 出发依据存储结构进行广度遍历,写出遍历结果.

数据结构考试题目及答案

4. 有一棵二叉树其前序序列为ABCDEF,中序序列为BCAEDF,画出此二叉树的示意图,并给出其后序序列的线索树.(6 分)

5. 对于关键字集合{51,28,36,86,7},请建立一个堆,要求画出堆形成的示意图.(6 分)

6. 在双链表H中,现在要在节点P之后插入一个节点Q,请写出插入动作的具体语句. (4分)

七.算法设计(共20 分)

1. 数组A[1..m]作为循环队列的存储区域,试编写一个出队的类PASCAL 语言算法.(6 分) 2.利用类pascal 语言写出统计二叉树中节点个数的算法(6 分). 3.利用类pascal 语言写出快速排序中一趟块排的算法(8 分).

数据结构试题9答案

一、1、C 2、B 3、D 4、A 5、D 6、B 7、C 8、D 9、A 10、D 11、A 12、D

13、B 14、A 15、C

二、1、A C D 2、A B 3、A C D E 4、D E 5、B C

三、1、顺序,链接,索引,散列2、相对位置3、指令必须有确切含义,无歧义性4、开地址法,拉链法5、修改,检索

四、1、×2、√3、×4、×5、×

五、1、三元组表P244 2、拓扑排序P229 3、A VL树P180

六、

数据结构考试题目及答案

4、

数据结构考试题目及答案

5、

数据结构考试题目及答案

6、q↑.llink←p

q↑.rlink←p↑.rlink

p↑.rlink↑.llink←q

p↑.rlink←q

七、算法设计( 6+6+8=20′)

1、1. if R=F

then print(‘underflow’)

else F←F MOD m+1

算法结束

2、TYPE pointer=↑node

node=RECORD

info: datatype;

llink, rlink: pointer

END

V AR t: pointer;

Count: integer; 进入算法时,二叉树已用二叉链表存储,t指向根结点,count初值为0 Procedure node_Count (t: pointer; V AR count: integer);

begin

if t=nil

then 算法结束

else

begin count:=count+1;

node_count(t↑.llink,count);

node_count(t↑.rlink,count) end end;

3、TYPE node=RECORD

Key: integer;

Info: datatype

End;

List=ARRAP〔1..N〕OF node;

V AR X:node; j:0..n;

Procedure quickpass(V AR R:list;l,r:integer;VAR i:integer);

begini:=l;j:=r;x:=R〔i〕;

repeatwhile (R〔i〕.key>=x.key)and(i<j=doj:=j-1; if i<j then

R〔j〕:=R〔j〕;i:=i+1;

while (R〔i〕.key<=x.key=and (i<j=do i:=i+1; if i<j then

〔R〔j〕:= R〔i〕;j:=j-1〕until i=j R〔i〕:=x end

注:整个快速排序Procedure quicksort (V AR R:list;s,t:integer);

Begin If s<t Then 〔quickpass(R,s,t,i); quicksort(R,s,i-1); quicksort(R,i+1,t)〕

end;

数据结构试题10

一.单项选择题(每小题1 分,共20分)

1. 设n为正整数,以下程序段的执行次数是: ( )

k:=0;s:=1;

REPEAT

s:=s+k; k:=k+1

UNTIL (k=-n)

A. (2n+3)次

B. 2(n+1)次

C. 无限多次

D.1 次

2. 序列A,B,C,D,E 顺序入栈,不能获得的序列是: ( )

A. ABCDE

B. CDEBA

C. EDCBA

D.DECAB

3. 数据结构的内容包括: ( )

A. 三层次五要素 C. 五层次三要素

B. 三层次三要素 D. 五层次五要素

4. 在双链表中要在p 所指的结点后插入一个新结点q,要修改的指针域个数为:( )

A. 2 个

B. 4 个

C. 6 个

D. 8 个

5. 在列主序下顺序的存储数组A 4 * 4 的下三角元素A(3,2)的位置是第: ( )

A. 5 个

B. 6 个

C. 7 个

D. 10 个

6. n 个结点顺序存储的完全二叉树, i (1

数据结构考试题目及答案

7. 对任何二叉树,设n0,n1,n2 分别是度数为0,1,2的结点数,则有: ( )

A. n0=n2+1

B. n0=n2-1

C. n0=n1+1

D. n0=n1-1

8. 对图(一)的二叉树,其后续遍历结果为: ( )

数据结构考试题目及答案

图(一)

A. ABDCEF

B. ABCDEF

C. DBAECF D . DBEFCA

9. 结点可以排在拓扑序列中的图是: ( )

A.无向图

B.有向图

C.有向无环图

D.无向有环图

10.串的求子串运算SUBSTR(‘ABCDEFGH’,4,5) 的引用结果是: ( )

A. ‘DE’

B. ‘DEFGH’

C. ‘EFGH’

D. ‘BCDE’

11.对于记录R1,R2其健值分别是K1和K2,数据为D1和D2,称R1和R2是同义词的条件是

( )

A. K1=K2 C. K1=K2且H(K1)≠H(K2)

B.D1=D2 D.K1≠K2 且H(K1)=H(K2)

12.快速排序属于: ( )

A. 插入排序

B. 交换排序

C. 选择排序

D. 归并排序

13.A VL 数不平衡后要调整的情形有: ( )

A. 2种

B. 4 种

C. 6 种

D. 8 种

14.PRIM 算法是求图的: ( )

A. 连通分量

B. 最短路径

C. 最小生成树

D. 拓扑序列

15.在排序过程序中,使用辅助存储空间为O(n)的算法是: ( )

A. 插入排序

B. 归并排序

C. 起泡排序

D. 快速排序

16.若无向图中有n 个结点,e 条边,则它的邻接表需要表节点数目为: ( )

A. 2e

B. 2e+n

C. 2e+1

D.e+2n

17.字符串的紧缩存储形式是每个字符占: ( )

A. 1 个二进制位

B. 1 个字节

C. 1 个字

D. 1 个结点单元

18.循环队列SQ有m 个单元,其满队条件是: ( )

A. (SQ.rear+1) MOD M=SQ.front C. SQ.rear=m

B. SQ.rear=SQ.front D. SQ.front=m

19.VSAM 文件属于: ( )

A. 顺序文件

B. 散列文件

C. 多关键字文件

D. 索引文件

20.下列说法中错误的是:( )

B. n 个结点的有向图最多有n*(n-1)条边

C. 用相邻矩阵存储图时所需存储空间大小与图中边数有关

D. 散列表中碰撞的可能性大小与负载因子有关

二.多项选择题(错选,多选,漏选均不得分,每小题2 分,共14 分)

1. 根据描述算法的语言不同,可将算法分为:()

A. 形式算法

B.非形式算法

C. 伪语言算法

D. 运行终止的程序可执行部分

E. 运行不终止的程序可执行部分

2. 图的常见存储结构可以选取: ( )

A. 邻接表

B. 邻接矩阵

C. 逆邻接表

D. 邻接多重表

E. 散列表

3. 在下列算法中,涉及到栈运算的有: ( )

A. 二叉树遍历

B. 广度优先搜索

C. 深度优先搜索

D. 构造哈夫曼树

E. 表达式求值算法

4. 某表组织如下:将元素均匀的分成块,块内元素不排序,块之间排序,则查找块及块内某元素

实施的方法是: ( )

A. 折半查块顺序查元素

B. 顺序查块顺序查元素

C. 顺序查块折半查元素

D. 散列法查找数据元素

E. 折半查块折半查元素

5. 能够从任意节点出发访问到其余结点的结构有: ( )

A. 单链表

B. 循环链表

C. 双链表

D. 二叉树表

E. 散列表

6. 数据的逻辑结构与: ( )

A. 数据元素本身的形式,内容有关

B. 数据元素本身的形式,内容无关

C. 数据元素的相对位置有关

D. 数据元素的相对位置无关

E.所含节点个数无关

7. 稀疏矩阵通常采用的存储方式有: ( )

A. 单链表

B. 循环链表

C. 三元组

D. 散列表

E. 正交表

三.判断说明题(对的打”√”,错的打”╳”,并说明理由.判断和说明各得 1 分,判断错误,全

题无分.共10 分)

1. 在队列中,新插入的结点只能插到队头. ( )

2. 二叉树是度数最大为2 的树. ( )

3. 在哈希表中,相同的关键字散列在不同的地址空间上的现象称为冲突. ( )

4. 堆排序是不稳定的,其时间复杂度为:O(n log2n). ( )

5. 完成树的深度遍历一般要利用队列作为辅助结构. ( )

四.解释概念题(每小题4 分,共12分)

1. A VL 树

2. 稀疏矩阵

3. 哈夫曼树

五.简答题(每小题5 分,共20 分)

1. 将图(二)所示二叉树转化成森林.

数据结构考试题目及答案

数据结构考试题目及答案

图(二) 图(三)

2. 什么是串的压缩存储(紧缩格式)? 他有哪些优缺点?

3. 已知图G如图(三)所示,给出其邻接表,并写出从1出发进行深度优先和广度优先遍历的

数据结构考试题及答案资料
2012 年数据结构期末考试题及答案 一、选择题 1.在数据结构中,从逻辑上可以把数据结构分为 A.动态结构和静态结构 C.线性结构和非线性结构 C 。 B.紧凑结构和......
数据结构期末考试题目及答案
数据结构期末考试题目及答案_幼儿读物_幼儿教育_教育专区。一个线性表为B=(12...
数据结构-数据结构历年考题及答案2
数据结构-数据结构历年考题及答案2_数学_高中教育_教育专区。中国矿业大学 2011-2012 学年 《数据结构》试卷(A 卷)(考试时间:100 分钟) 一. 填空(每空 2 ......
数据结构期末考试试题及答案
标签: 工学| 数据结构| 数据结构期末考试试题及答案_工学_高等教育_教育专区。计算机参考资料 数据结构期末考试试题及答案 期末样卷参考答案 一.是非题(每题 1......
数据结构期末考试试题及答案
标签: 工学| 数据结构| 数据结构期末考试试题及答案_工学_高等教育_教育专区。这是江西师大08级数据结构考试真题 江西师范大学计算机科学技术专业 09-10 第 1 ......
数据结构期末考试题目及答案
数据结构期末考试题目及答案_理学_高等教育_教育专区 4298人阅读|22次下载 数据结构期末考试题目及答案_理学_高等教育_教育专区。南昌大学数据结构期末考试题目及......
数据结构考试试题(带答案)
数据结构算法中,通常用时间复杂度和__空间复杂度___两种方法衡量其效率。 2....} 全真模拟试题(一) 一、 填在 单项选择题(在每小题的 4 个备选答案中,......
2019年数据结构期末考试题及答案
A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结 2012 年数据结构期末考试题及答案 一、选择题 1.在数据结构中,从逻辑上可以......
数据结构考研真题及其答案
【武汉交通科技大学 1996 一、4(2 分)】 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 8.以下与数据的存储......
数据结构考试复习题目及答案
数据结构考试复习题目及答案_IT认证_资格考试/认证_教育专区。一、选择题 9、...
数据结构复习题目及答案
数据结构复习题目及答案_IT认证_资格考试/认证_教育专区。WORD 格式 《数据结构-C 语言版》 第一章 绪论 单项选择题 1.在数据结构中,数据的基本单位是 ___。...
自考数据结构02331历年试题及答案(2009--2015个人整理版)
数据结构试题一、单项选择题(本大题共 15 小题,每小题 2 分,共 30 分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的......
自考数据结构试题及答案解析
自考数据结构试题及答 案解析文档编制序号:[KK8UY-LL9IO69-TTO6...
数据结构考研真题和答案
数据结构考研真题和答案_研究生入学考试_高等教育_教育专区。、选择题 1. 算法...
数据结构考研真题及其答案
数据结构考研真题及其答案_研究生入学考试_高等教育_教育专区。一、选择题 1. ...
2015年10月自考数据结构试题及答案解析
2015年10月自考数据结构试题及答案解析_自考_成人教育_教育专区。2015 ...
自考数据结构 试题及答案解析
自考数据结构 试题及答案解析_自考_成人教育_教育专区。2015 年 lO 月高...
数据结构考研真题及其答案
数据结构考研真题及其答案_研究生入学考试_高等教育_教育专区。一、选择题 1.算...
14级数据结构考试真题及答案
14级数据结构考试真题及答案_理学_高等教育_教育专区。一、选择填空题(每题 2...