数据结构,,华工数据结构试卷资料,电信学院,

1.1选择题

1、数据结构是一门研究计算机解决实际问题中（ A ）以及它们之间的（ B ）

和运算等的学科。

(1)A、数据元素 B、计算方法 C、逻辑存储 D、数据映像

(2)A、结构 B、关系 C、运算 D、算法

2、数据结构可以用二元组来表示，它包括（ A ）集合K和K上的（ C ）集合R。

A、数据元素 B、存储结构 C、元素之间的关系 D、逻辑结构

3、数据结构在计算机内存中的表示是指（ A ）。

A、数据的存储结构 B、数据结构

C、数据的逻辑结构 D、数据元素之间的关系

4、在数据结构中，与所使用的计算机无关的是数据的（ A ）结构。

A、逻辑 B、存储 C、逻辑和存储 D、物理

5、以下说法中正确的是（ D ）。

A、数据元素是数据的最小单位 B、数据项是数据的基本单位

C、数据结构是带结构的各数据项的集合

D、一些表面上很不相同的数据可以有相同的逻辑结构

1.2 填空题

1、线性结构中元素之间存在（一对一）关系，树型结构中元素之间存在（一对多 ）关

系，图型结构中元素之间存在（多对多）关系。

2、数据结构是研究数据的（逻辑结构）和（存储结构）以及它们之间的相互关系，并

对这种结构定义相应的操作，设计出相应的（算法），而确保经过这些运算后所得到的新结

构是原来的结构类型。

3、一个算法的时间复杂度是该算法包含的（简单操作次数）的多少，它是一个算法运

行时间的（相对量度），一个算法的空间复杂度是指该算法在运行过程中临时占用的（存储

空间）的大小。

4、一个算法的时间复杂度通常用问题规模的（最高数量级）形式表示，当一个算法的

时间复杂度与问题的n大小无关时，则表示为（O（1））；成正比时，表示为（O（n）），成

平方时，则表示为（O（n

2

））。

5、数据结构、数据元素和数据项在计算机中的映射（或表示）分别称为存储结构、结

点和数据域。这句话是（正确）。（填写正确或错误）

2.1选择题

1、线性表的顺序存储结构是一种（ A ）的存储结构，线性表的链式存储结构是一

种（ B ）的存储结构。

A、随机存取 B、顺序存取 C、索引存取 D、散列存取

2、对于一个线性，既要求能够进行较快的插入和删除，又要求存储结构能够反映数据

元素之间的逻辑关系，则应该选择（ B ）。

A、顺序存储方式 B、链式存储方式

C、散列存储方式 D、索引存储方式

3、已知，L是一个不带头结点的单链表，p指向其中的一个结点，选择合适的语句实

现在p结点的后面插入s结点的操作（ B ）。

A、p->next=s ; s->next=p->next ; B、s->next=p->next ; p->next=s ;

C、p->next=s ; s->next=p ; D、s->next=p ; p->next=s ;

4、单链表中各结点之间的地址（ C D ）。

A、必须连续 B、部分地址必须连续

C、不一定连续 D、连续与否都可以

5、在一个长度为n的顺序表中向第i个元素（0

向后移动（ B ）个元素。

A、n-i B、n-i+1 C、n-i-1 D、i

2.2填空题

1、顺序存储的长度为n的线性表，在任何位置上插入和删除操作的时间复杂度基本上

都一样。插入一个元素大约移动表中的（ n/2 ）个元素，删除一个元素时大约移动表中的

（ (n-1)/2 ）个元素。

2、在线性表的顺序存储方式中，元素之间的逻辑关系是通过（物理顺序）来体现的；

在链式存储方式，元素之间的逻辑关系是通过（指针）体现的。

3、对于一个长度为n的单链表，在已知的p结点后面插入一个新结点的时间复杂度为

（o(1)），在p结点之前插入一个新结点的时间复杂度为（o(n)），在给定值为e的结点之后

插入一个新结点的时间复杂度为（o(n)）。

4、在双向链表中，每个结点包含两个指针域，一个指向（前驱）结点，另一个指向（后

继）结点。

5、对于循环链表来讲，逐个访问各个结点的结束判断条件是（设P为指向结点的指针，

L为链表的头指针，则p->next= =L）。

3.1 选择题

1、栈的插入和删除操作在（ A ）进行。

A、栈顶 B、栈底 C、任意位置 D、指定位置

2、利用大小为N的数组顺序存储一个队列时，该队列最大长度为（ B ）。

A、N－2 B、N－1 C、N D、N＋1

3、若已知一个栈的入栈序列是1，2，3，„，n，其输出序列为p1，p2，p3，„，pn, 那

么p1=n；pi为（ C ）。

Ａ、i Ｂ、n-i Ｃ、n－i＋1 Ｄ、不确定

4、假设以I和O分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操

作序列可表示为仅由I和O组成的序列。下列序列（ A ）是合法的。

Ａ、IOIIOIOO Ｂ、IOOIOIIO C、IIIOIOIO D、OIIOIOIO

5、递归函数可以调用自身（ B ）次。

Ａ、只多1次 Ｂ、任意次数 Ｃ、0 次 Ｄ、至多2次

3.2 填空题

1、线性表、栈和队列都是（线性）结构，可以在线性表的（任意）位置插入和删除元

素；对于栈只能在（栈顶）插入和删除元素；对于队列只能在（队尾）插入元素和在（队首）

删除元素。

2、对于一个顺序栈作进栈运算时，应先判别栈是否为（满），作退栈运算时，应先判

别栈是否为（空），当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量

为（m）。

3、设有一个空栈，现有输入序列1，2，3，4，5，经过push，push，pop，push，pop，

push，push后，输出序列是（2，3）。

4、无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除操作的时间复杂

度均相同为（o(1)）。

5、有一个循环队列，分配到的存储空间大小为n，则其队满条件是

（(rear+1)%QueueMaxSize= =front），队列为空的条件是（rear= =front）。

4.1选择题

1、空串与空格串是（ B ）。

A、相同 B、不相同 Ｃ、不能确定

2、串是一种特殊的线性表，其特殊性体现在（ B ）。

A、可以顺序存储 B、数据元素是一个字符

C、可以链式存储 D、数据元素可以是多个字符

3、设有两个串p和q，求q在p中首次出现的位置的操作是（ B ）。

A、连接 B、模式匹配 C、求子串 D、求串长

4、设串s1=“ABCDEFG”，s2=“PQRST”函数strconcat（s，t）返回s和t串的连接

串，strsub（s，i，j）返回串s中从第i个字符开始的、由连续j个字符组成的子串。strlength(s)

返回串s的长度。则strconcat（strsub（s1，2，strlength（s2）），strsub（s1，strlength（s2），

2））的结果串是（ D ）。

A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF

5、若串s=“software”，其子串个数是（ B ）。

A、8 B、37 C、36 D、9

4.2简答题

1、简述空串与空格串、主串与子串、串名与串值每对术语的区别？

答：空串是指长度为0的串，即没有任何字符的串。

空格串是指由一个或多个空格组成的串，长度不为0。

子串是指由串中任意个连续字符组成的子序列，包含子串的串称为主串。

串名是串的一个名称，不指组成串的字符序列。

串值是指组成串的若干个字符序列，即双引号中的内容。

2、两个字符串相等的充要条件是什么？

答：条件一是两个串的长度必须相等

条件二是串中各个对应位置上的字符都相等。

3、串有哪几种存储结构？

答：有三种存储结构，分别为：顺序存储、链式存储和索引存储。

4、已知两个串：s1=”fg cdb cabcadr”, s2=”abc”, 试求两个串的长度，判断串s2是否是

串s1的子串，并指出串s2在串s1中的位置。

答：（1）串s1的长度为14，串s2的长度为3。

（2）串s2是串s1的子串，在串s2中的位置为9。

5、已知：s1=〃I’m a student〃，s2=〃student〃，s3=〃teacher〃，试求下列各操作的结

果：

strlength(s1)； 答：13

strconcat(s2,s3)； 答：”studentteachar”

strdelsub(s1,4,10)； 答：I’m

6、设s1=”AB”，s2=”ABCD”，s3=”EFGHIJK，试画出它们在各种存储结构下的结构图。

答：

顺序存储方式下：

‘A’

‘B’

‘0’

S1

‘A’

‘B’

‘C’

‘D’

‘0’

S2

‘E’

‘F’

‘G’

‘H’

‘I’

‘J’

‘K’

‘0’

S3

链式存储方式：

S1

‘A’ ‘B’ ‘0’ ∧

S2

S3

‘A’

‘E’

‘B’

‘F’

‘C’

„

‘D’

‘K’

‘0’ ∧

‘0’ ∧

5.1 选择题

1、一维数组和线性表的区别是（ A ）。

A、前者长度固定，后者长度可变 B、后者长度固定，前者长度可变

C、两者长度均固定 D、两者长度均可变

2、设W为一个二维数组，其每个数据元素W

ij

占用6个字节，行下标i从0到8，列

下标j从2到5，则二维数组W的数据元素共占用（ C ）个字节。

A、480 Ｂ、192 Ｃ、216 Ｄ、144

3、在稀疏矩阵的行逻辑链式存储中，每个行单链表中的结点都具有相同的（ A ）。

A、行号 B、列号 Ｃ、元素值 D、地址

4、二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的

范围从0到4，列下标j的范围从0到5，M按行序存储时元素M[3][5]的起始地址与M按

列序存储时的元素（ ）的起始地址相同。

A 、M[2][4] B、 M[3][4] C、 M[3][5] D、M[4][4]

5、稀疏矩阵一般的压缩存储方法有两种，即（ C ）。

A、二维数组和三维数组 B、三元组和散列

C、三元组和十字链表 D、散列和十字链表

5.2 填空题

1、一维数组的逻辑结构是（线性表），存储结构是（顺序存储）；对于二维或多维数组，

分为按（行序）和（列序）两种不同的方式存储。

2、对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]

的地址为（A+(i*m+j)*每个元素所占字节数）。

3、已知广义表A=((a,b,c),(d,e,f))，则运算head(tail(tail(A)))=（e）。

4、三维数组R[c1‥d1,c2‥d2,c3‥d3]共含有（（d1-c1+1）*(d2-c2+1)*(d3-c3+1)）个

元素。（c1≤d1,c2≤d2,c3≤d3）

5、二维数组A[10‥20][5‥10]以行序为主序存储，每个元素占4个存储单元，且A[10][5]

的存储地址是1000，则A[18][9]的地址是（1368）。

5.3 应用题

1、按行优先存储方式，写出三维数组A[3][2][4]在内存中的排列顺序及地址计算公式（假

设每个数组元素占用L个字节的内存单元，a[0][0][0]的内存地址为Loc(a[0][0][0])）。

答：内存中的排列顺序为：

A[0][0][0],A[0][0][1],A[0][0][2],A[0][0][3], A[0][1][0],A[0][1][1],A[0][1][2],A[0][1][3],

A[1][0][0],A[1][0][1],A[1][0][2],A[1][0][3], A[1][1][0],A[1][1][1],A[1][1][2],A[1][1][3],

A[2][0][0],A[2][0][1],A[2][0][2],A[2][0][3], A[2][1][0],A[2][1][1],A[2][1][2],A[2][1][3]

地址计算公式为：

Loc(a[i][j][k])= Loc(a[0][0][0])+（i*2*4+j*4+k）*L

2、给定矩阵A如下，写出它的三元组表示、行逻辑链式存储和十字链表存储。

答：三元组表示法：m=5,n=5,t=6,data数组为：

行 列 值 下标

1

2

2

3

3

5

1

3

4

2

5

5

1

2

3

4

5

6

1

2

3

4

5

6

┇

MaxTerms

行逻辑链式存储方式：

1

1 1 1 ∧

2 3 2

3 2 4

5 5 6 ∧

2 4 3 ∧

3 5 5 ∧

2

3

4

5

十字链表存储方式：

1 2 3 4 5

1

2

3

4

5

1 1 1

∧ ∧

1 1 1

∧

1 1 1

∧ ∧

1 1 1

∧

1 1 1

∧ ∧

1 1 1

∧

3、求下列广义表的运算的结果

（1）head((p,h,w)) 结果为：(p,h,w)

（2）tail ((b,k,p,h)) 结果为：( )

（3）head(((a,b),(c,d))) 结果为：((a,b),(c,d) )

（4）tail (((b),(c,d))) 结果为：( )

（5）head (tail (head(( (a,d),(c,d))))) 结果为：c

（6）tail (head (tail (((a,b),(c,d))))) 结果为：( )

4、求出下列广义表的长度和深度。

（1）A=（（）） 结果为：1 2

（2）B=（a，（b，（c））） 结果为：2 3

（3）C=（a，（b，（c，d）），（e）） 结果为：3 3

（4）F=（（a，（b，（），c），（（d）,e）） 结果为：3 3

5、画出下列广义表的图形表示

（1）A(b,(A,a,C(A)),C(A))

（2）D(A( ),B(e),C(a,L(b,c,d)))

D

A

A

B C

b

C

e

a

L

答：

a

b

c

d

( 1 ) ( 2 )

6、画出第5题的广义表的单链表表示。

答：

A

0 b 1

1

1 ∧

0 a

1 ∧

1∧

1 ∧

（ 1 ）

D

1 ∧

1

0 e ∧

1 ∧

0 a

1 ∧

0 b

0 c

0 d ∧

（ 2 ）

6.1选择题

1、假定在一棵二叉树中，度为2的分支结点个数为15，度为1的分支结点个数为30

个，则叶子结点数为（ B ）。

A、15 B、16 C、17 D、47

2、设n，m为一棵树上的两个结点，在中根遍历时，n在m前的条件是（ C ）。

A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙

3、由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带树路径长度为（ D ）。

A、23 B、37 C、46 D、44

4、如果F是由树T转换而来的二叉树，则T中结点的前根就是F中结点的（ B ）。

A、中根遍历 B、先根遍历 C、后根遍历 D、按层遍历

5、某二叉树的先根遍历结点序列和后根遍历结点序列刚好相反，则该二叉树一定是

（ D ）。

A、空树或只有一个根结点 B、完全二叉树

C、二叉排序树 D、高度等于其结点数

6.2填空题

1、在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有（一）个前驱

结点；叶子结点没有（后继）结点，其余结点的后继结点可以（任意多个）。

2、在具有n个结点的二叉树中，有（n+1）个空指针。

3、深度为k的完全二叉树至少有（2

k-1

）个结点，至多有（2

k

-1）个结点，若按自上而

下，从左到右次序给结点从1开始编号，则编号最小的叶子结点的编号是（ n/2+1 ）。

4、由a，b，c三个结点构成的二叉树，共有（5）种不同形态。

5、树所对应的二叉树其根结点的（右）子树一定为空。

6.3应用题

1、给定的树如图6-24（a）所示，回答以下问题：

（1）哪个是根结点，哪些是叶子结点？

答：根结点是A，叶子结点是B，K，L，M，G，D，H，I，J。

（2）哪个是结点F的双亲结点，哪些是结点F 的祖先结点，哪些是结点F的孩子结点？

答：结点F的双亲结点是C，祖先结点是A，C，孩子结点是K，L，M。

（3）哪些是结点C的子孙结点，哪些是结点C的兄弟结点？

答：结点C的子孙结点是F，G，K，L，M，结点C的兄弟结点是B，D，E。

（4）给定树的层数是多少，结点I所在的层数是多少？

答：树的层数为4，结点I在第三屋。

（5）写出先根遍历、后根遍历和按层遍历的结点序列。

答：先根：ABCFKLMGDEHIJ。后根：BKLMFGCDHIJEA。按层：

ABCDEFGHIJKLM。

2、给定的二叉树如图6-25所示：

（1）写出先根遍历、后根遍历、中根遍历和按层遍历的结点序列。

答：先根：ABDIKECFGN。中根：DIKBEAFCNG。后根：KIDEBFNGCA。按层：

ABCDEFGTNK。

（2）画出先根遍历和中根遍历的线索二叉树。

答：

A

B

D

I

K

E F

N

C

G

NULL

D

I

K

A

B

E F

N

C

G

NULL

先根遍历的线索二叉树 中根遍历的线索二叉树

A

B

A

B

C

D

E

C

D

F

G

F

K

L

G

H

I

J

E

I

H

（a）将图中给定的树转换成二叉树 （b）将图中给定的二叉树转换成树

M

A

I N

B

C

D

E

J 0

F

G

H

K

L

M

P

Q

（c）将图中给定的森林转换成二叉树

图6-24 题6.3.5

A

B

D

I

K

E F

N

C

G

图6-25 题6.3.2

3、图6-24中的树、森林与二叉树之间进行转换：

（1）将图（a）中给定的树转换成二叉树

（2）将图（b）中给定的二叉树转换成树

答：

B

C

F

K

L

M

G

H

C F I

A

D

E

B

A

D G

I

J

E

H

（1） （2）

（3）将图（c）中给定的森林转换成二叉树

（4）将图6-24中给定的二叉树转换成森林

答：