数据结构课堂习题.pdfVIP

第一章绪论

一、单项选择题

1．数据结构是一门研究非数值计算的程序设计问题中计算机的①以

及它们之间的②和运算等的学科。

①A．操作对象B．计算方法C．逻辑存储D．数据映象

②A．结构B．关系C．运算D．算法

2．数据结构被形式地定义为（D，R），其中D是①的有限集合，R

是K上的②的有限集合。

①A．算法B．数据元素C．数据操作D．逻辑结构

②A．操作B．映象C．存储D．关系

3．在数据结构中，从逻辑上可以把数据结构分成①。

A．动态结构和静态结构B．紧凑结构和非紧凑结构

C．线性结构和非线性结构D．内部结构和外部结构

4．线性表的顺序存储结构是一种①的存储结构，线性表的链式存储

结构是一种②的存储结构。

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

5．在计算机存储器内表示时，物理地址和逻辑地址是连续的，称之

为

A．逻辑结构B．顺序存储结构

C．链表存储结构D．以上都不对

1.A，B2.B，D3.C4.A,B5.B

二、填空题

1．数据逻辑结构包括①、②、③和④四种类型。

2．线性结构中元素之间存在①关系，树形结构中元素之间存在②关

系，图形结构中元素之间存在③关系。

3．下面程序段的时间复杂度是①。

for(i=0;in;i++)

for(j=i;jn;j++)x++;

4．下面程序段的时间复杂度是①。

s＝0；

for（i=0；in；i++）

for（j=0;jn;j++）

s+=b[i][j]；

sum=s;

5．下面程序段的时间复杂度是①。

for(i=1;in;i++)

for(j=1;jn;j++)x++;

for(k=1;kn;k++)x++;

1.集合、线性、树、图2.一对一、一对多、多对多3.O(n2)

4.O(n2)5.O(n2)

线性表

一、填空题

1.设长度为n的顺序线性表在任何位置上插入或删除操作都是等概

率的，则插入一个元素时平均需要向__移动_______个元素，删除

一个元素时平均需要向___移动______个元素。

2.线性表的链式存储结构中，元素之间的线性关系是通过结点中的

________域来实现的。

3.线性表的顺序存储结构中逻辑上相邻的元素，物理位置

__________相邻；线性表的链式存储结构中逻辑上相邻的元素，

物理位置__________相邻。

4.对于顺序表，访问结点的时间复杂度为_____，增加、删除结点的

时间复杂度为_____。对于单链表，访问结点的时间复杂度为

_____，增加、删除结点的时间复杂度为_____；在已知的结点*p

后插入一个新结点的时间复杂度为____，删除已知结点*p的时间

复杂度为____。

5.双向链表中每个结点含有两个指针域，其中一个指针域指向

_______结点，另一个指针域指向______结点。

6.在一个单链表中p所指结点之前插入一个s(值为e)所指结点时，

可执行如下操作：

q=head;

while(q-next!=p)q=q-next;

s=newNode;s-data=e;

q-next=;//填空

s-next=;//填空

7.在一个单链表中删除p所指结点的后继结点时，应执行以下操作：

q=p-next;

p-next=____;