数据结构习题答案

数据结构习题答案

选择题:

1-5 DAACB 6-10 CDBDC 11-15 CCABD 16-20 ABBDC 21-25

BCABB

26-30 CCBAC 31-35 ACCDB 36-40BDBDC 41-45CBCCC 46-50

DBCBA

51-55 ACCCA 56-60ADDBC 61-65BCDDB 66A 71A 72D 73B

74B

75-80 AABDCC 81-85DCCAC 86-90DDBDA 91-95DBCCA

96-100 ADDAC 101-105BCBAA 106-110 AABBA 111-115

AADBA

116-120 CB118无答案119A 120 A 121-125DDCCA 126-130

CCBDA

131-135BBCDB 136-140 BBBCC 141-145CDABB 146-150DCDBD

151-160CBADC 156-160DABCD 161-165CCDAD 166-170DBBCD

171-175BCAAC 176-180ACBCD 181-185DDBCB 186-190ABDBA

191-195CCDAC 196-200BDCBD 201-203DAB

填空题：

1、数据的逻辑结构包括（线性结构）和非线性结构。

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

多）关系。

3、在单链表中设置头结点的作用是（简化插入、删除算法）。

4、访问单链表中的结点，必须沿着（指针域）依次进行。

5、在双向链表中，每个结点有两个指针域，一个指向（前驱结点），另一个指向（后 继结点）。

6、在一个单链表中的p所指向结点之前插入一个s所指的结点时，可以执行如下操作：

（1）s->next= p->next ;

（2）p->next=s;

（3）t=p->data;

（4）p->data= s->data ;

（5）s->data= t ;

7、栈和队列的区别在于（删除运算不同）。

8、通常元素进栈的顺序是（先移动栈顶指针，然后存入元素）。

9、通常元素出栈的顺序是（先取出栈顶元素，然后移动栈顶指针）。

10、从一个循环队列中删除一个元素，通常的操作是（先取出元素，然后移动队

头指针）。

11、向一个循环队列中插入一个元素，通常的操作是（先存放元素，然后移动队尾

指针）。

12、设树T的度为4，其中度为1，2，3和4的结点的个数分别为4，2，1，1，

则T中叶子结点的个数为（8 ）。

13、针对线性链表的基本操作有很多，但其中最基本的4

种操作分别为（插入）、删除、查找和排序。

14、树和二叉树的3个主要差别（）；树中的最大

度数没有限制，而二叉树结点的最大度数为2；树的结点无左右之分，而二叉树的结点有左右之分。

15、从概念上说，树与二叉树是两种不同的数据结构，通

过某种算法将树转化成二叉树的基本目的是（树可采用K1

K2

K5 K3 K4 K6

K7

a

b

c

d

g e

f

h

i

二叉树的存储结构并利用二叉树的已有的算法解决树的有关问题）。

16、深度为k的完全二叉树至少有( 2k-1 )个结点，至多有（2k-1 ）个结点，若按自

上而下，从左向右的次序编号（从1开始），则编号最小的叶子结点的编号是（2k-1）。

17、在一棵二叉树中，叶子结点的个数为n0,度为2的结点的个数为n2,则有n0=

（n2+1 ）。

18、结点最少的树为（只有一个结点的树），结点最少的二叉树为（空的

二叉树）。

19、现有按中序遍历二叉树的结果为abc，问有（5 ）种不同形态的二叉树可

以得到这一遍历结果。

20、在n个记录的有序顺序表中进行二分法查找，最大的比较次数是

（[log2n]+1 ）。

21、设线性表（a1,a2,……,a500）元素的值由小到大排列，对一个给定的k值用二分 法查找线性表，在查找不成功的情况下至多需比较（9 ）次。

22、二分法查找的存储结构公限于（顺序存储结构），且是有序的。

23、已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用二

分法查找90时，需进行（2 ）次查找可确定成功；查找47时，需进行（4 ）次查找可确定成功；查找100时，需进行（ 3 ）次查找可确定不成功；

24、在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，

当把第7个记录60插入到有序表时，为寻找插入位置需比较（3 ）次。

25、每次从无序子表中取出一个元素，然后把它插入到有序子表中的适当位置，此

种排序方法叫做（插入）排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种方法叫做（删除）排序。

26、对有n个记录的表r[1……n]进行直接选择排序，所需要进行的关键字间的比

较次数为n(n-1)/2 。

27、在插入和选择排序中，若初始数据基本正序，则选用（插入排序）；若初

始数据基本反序，则选用（选择排序）。

28、对n个元素的序列进行冒泡排序时，最少的比较次数是（n-1 ）。

29、设二叉树根结点的层次为0，对含有100个结点的二叉树，可能的最大树深和

最小树深分别是（99 ）和（6）。

30、数据的基本单位是（数据元素）。

31、数据结构研究的主要内容包括（数据存储结构）、（数据逻辑结构）、数

据元素之间的联系三方面。

32、从逻辑结构上讲，数据结构主要分为两大类，它们是（线性数据结构）和

（非线性数据结构）。

33、一个数据结构在计算机中的表示（映象）称为数据的存储结构。

34、数据的逻辑结构被分为（集合）、线性结构、树型结构和图形结构四种。

35、数据的存储结构主要分为（顺序存储结构）和（链式存储结构）。

36、在线性结构和树型结构中，前驱结点和后继结点之间分别存在着（一对一）

和（一对多）的联系。

37、算法的5个重要特性是：输入、输出、可行性、确定性和（有穷性）。

38、算法的复杂度分为（时间复杂度）和（空间复杂度）两种。

39、若一个算法中的语句频度之和为T(n)=4nlog2n,则算法的时间复杂度为

O(log2n) 。

40、逻辑结构通常可以用一个二元组B=(K,R)来表示，其中K表示（有限个结点

所构成的集合），R表示（K上的关系的有限集合）。

41、线性表中（数据元素的个数）称为表的长度。

42、如果向一个长度为n的顺序表中的第I个元素（1<=I<=n）之前插入一个元素，

需向后移动（n- I +1 ）个元素。

43、在一个长度为n的顺序表中删除表中的第I个元素（1<=I<=n）时，需向前移

动（n- I ）个元素。 44、栈又称为（后进先出）表，队列又称为（先进先出）表。

45、栈中元素的进出原则是（后进先出）。

46、队列中元素的进出原则是（先进先出）。

47、一个栈的输入序列是12345，则栈的输出序列43512是（不可能的）。

48、从循环队列中删除一个元素时，通常的操作是（先取出元素，然后移动队

头指针）。

49、向循环队列中插入一个元素时，通常的操作是（先存放元素，然后移动队尾

指针）。

50、在单链表中，要删除某一指定的结点，必须找到该结点的（前驱结点）。

51、在非循环的（双向）链表中，可以用表尾指针代替表头指针。

52、在线性表的单链接存储结构中，每个结点都包含有两个域，一个域叫做（数

据）域，另一个叫做（指针）域。

53、在线性表的链式存储结构中，我们通常讲的头指针与头结点的根本区别是：头

结点是加在线性表的（第一个）元素所在结点之前的一个附设结点，而头指针是链表中第一个结点的地址变量；头结点与首元素结点的关系是若有头结点的单链表不为空，则头结点的指针域的值就是首元素结点的地址。

54、针对线性表的基本操作有很多，但其中最基本的四种操作分别为插入、删除、

查找和（排序）操作。

55、线性表的顺序存储结构是通过（数组下标）来直接反映数据元素之间的逻

辑关系，而链式存储结构是通过（结点指针）来间接反映数据元素之间的逻辑关系。 56、若对线性表进行的操作主要不是插入和删除，则该线性表宜采用（顺序）

存储结构；若频繁地对线性表进行插入和删除操作，则该线性表宜采用（链式）存储结构。

57、顺序表中逻辑上相邻的元素的物理位置（一定）紧邻。单链表中逻辑上相邻

的元素的物理位置（不一定）相邻。

58、线性表的链式存储结构主要包括单链表、（双向链表）和( 循环链表)三

种形式。

59、循环单链表与非循环单链表的主要不同是循环单链表的尾结点指针（指向链表

头结点），而非循环单链表的尾结点指针（指向空）。

60、若已知一个栈的入栈顺序是1，2，3，……，n，其输出序列为p1,p2,p3,……,p n,

若p1=n，则p i(1

61、向一个链栈插入一个p所指向的结点时，需要把栈顶指针的值赋给p所指向的

结点的（指针域），然后把p赋给（栈顶指针）。

62、在线性表的单链接存储中，若一个元素所在结点的地址为p,则其直接后继结点

的地址为（p->next ）；若假定p为一个数组a中的下标，则其直接后继结点的

下标为（p+1 ）。

63、当用长度为N的数组顺序存储一个栈时，假定用top=N表示栈空，则表示栈

满的条件为（top=0 ）。

64、在用一维数组A[N]存储一个顺序循环队列时，若队列的首、尾指针分别用f

和r表示，则队列长度为(r-f+N) mod N 。