数据结构（本）期末综合练习2016年6月

(2)40,73,101,81,92。共5个元素比较

(3) 29/10

282．

(1) 11 69

1 15 30

2 24 56

图7

(2)28,69,30,56 (3)4次 3． (1) 33

18

9 9

5 4

2 3 图8

(2) 2：0000 3 0001 4 001 7 10 8 11 9 01

39 (3)

41 46

80 47 57 第9页 70 80 15 7 8 图9

4． (1)

50

51 56

90

57 67

图10

(2) 46,51,54,56,71,106

(3) (47 , 60 ) ( 57 , 80 ) ( 39 , 41 ) ( 30 , 46 )

(47, 57, 60, 80 ) ( 30,39,41,46 )

( 30,39,41,46,47,57,60,80)

四、程序填空题 1． （1）&a

（2）d->next=NULL （3）p->data （4）p=p->next （5）P指向NULL head 6 10 16 2．

（1）p->data （2）p=p->next （3）p!=NULL

3．

（1） if(BT!=NULL)

（2） printf(“%c”,BT->data); （3） a,b,d,e,f,c

4． （1）n-1 （2）n （3）k=j

（4）a[i]=a[k] (5) a[k]=temp

第10页

4 NULL练习二

一、单项选择题

1栈和队列的共同特点是（ ）。

A. 元素都可以随机进出 B. 都是操作受限的线性结构 C. 都是先进后出 D. 都是先进先出 2．设有头指针为head的不带头结点的非空的单向循环链表, 指针p指向其尾结点, 要 删除第一个结点,则可利用下述语句 head=head->next;和（ ）。 A．p =head; B．p=NULL; C．p->next =head; D．head=p;

3.对一个栈顶指针为top的链栈进行入栈操作，通过指针变量 p生成入栈结点，则执 行：p=(struct node *)malloc(sizeof(struct node); p->data=a; 和（ ）。 A. p->nex=top; top=p; B. top->next=p; p=top;

C. top=top->next; p=top; D. p->next=top; p=top; 4. 以下说法正确的是( )。

A. 线性表的链式存储结构必须占用连续的存储空间 B. 一种逻辑结构可以有不同的存储结构

C．一种逻辑结构只能有唯一的存储结构 D．线性表的顺序存储结构不必占用连续的存储空间

5.设头指针为head的非空的单向链表, 指针p指向尾结点,则通过以下操作( ) 可使其成为单向循环链表。

A．p->next = NULL ; B．head = p;

C．p->next=head ; D．p=head;

6．把数据存储到计算机中，并具体体现( )称为物理结构。

A．数据的处理方法 B．数据的性质 C．数据的运算 D. 数据元素间的逻辑关系 7．一种逻辑结构（ ）。

A．只能有唯一的存储结构 B．可以有不同的存储结构 C．与存储该逻辑结构的计算机相关 D．是指某一种数据元素的性质 8．顺序表所具备的特点之一是（ ）。

A．可以随机访问任一结点 B．不需要占用连续的存储空间 C．插入元素的操作不需要移动元素 D．删除元素的操作不需要移动元素

9．把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（ ）。 A．存储结构 B．逻辑结构

C．数据元素的存储 D. 给数据元素分配存储空间

10．图状结构中数据元素的位置之间存在（ ）的关系。 A．一对一 B．一对多 C．多对多 D．每一个元素都有一个直接前驱和一个直接后继

11．图状结构中数据元素的位置之间存在（ ）的关系。 A．一对一 B．一对多

C．多对多 D．每一个元素都有一个且只有一个直接前驱和一个直接后继 12．元素20，14，16，18按顺序依次进栈，则该栈的不可能输出序列是（ ） （进栈出栈可以交替进行）。

A．18，16，14，20

第11页

B．20，14，16，18

C．18，16，20，14 D．14，20，18，16

13．一个单链表中,在p所指结点之后插入一个s所指的结点时，可执行: s->next=p->next;和（ ）。 A．s= p->next ; B．p->next=s->next; C．p=s->next ; D．p->next=s; 14．设有一个12阶的对称矩阵A(左上角第一个元素为a1,1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a5,4在一维数组B中的下标是（ ）。

A．14 B．12 C．13 D．11 15．元素12，14，16，18顺序依次进栈，则该栈的不可能输出序列是（ ）。 （进栈出栈可以交替进行）。

A．18，16，14，12 B．12，14，16，18 C．18，16，12，14 D．14，12，18，16

16．设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为（ ）。 A．25 B．14 C．15 D．23

17．设有一个30阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其 下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元 素a9,2在一维数组B中的下标是（ ）。

A．41 B．32 C．18 D．38

18．在一棵二叉树中，若编号为5的结点存在右孩子，则右孩子的顺序编号为（ ）。 A．12 B．9 C．11 D．10

19．设有一个长度为32的顺序表，要删除第8个元素需移动元素的个数为（ ）。

A．15 B．22 C．14 D．24 20．一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（ ）个结点。 A．14 B．15 C．19 D．18 21.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ ）。 A．2i B．2i-1 C．2i+1 D．2i+2 22 .如图1所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一

种顶点序列为（ ）。

A．abcdfge B．abcedfg C．acbfedg D．abcfgde a

b c

e

d f

第12页

g 图1