数据结构期末考试复习试题(整理完的).pdf

数据结构期末考试复习试题(整理完的)

数据结构与算法》复题

一、选择题

1.数据结构可以从逻辑上分为线性结构和非线性结构。

2.数据结构在计算机内存中的表示是指数据的存储结构。

3.在数据结构中，与所使用的计算机无关的是数据的逻辑

结构。

4.在存储数据时，通常不仅要存储各数据元素的值，而且

还要存储数据元素之间的关系。

5.在决定选取何种存储结构时，一般不考虑各节点的值如

何。

6.一些表面上很不相同的数据可以有相同的逻辑结构。

7.算法分析的目的是分析算法的效率以求改进，算法分析

的两个主要方面是空间复杂度和时间复杂度。

8.下面程序段的时间复杂度是O(n²)。

s=0;

for(i=0.in。i++)

for(j=0.jn。j++)

s+=B[i][j];

sum=s;

9.下面程序段的时间复杂度是O(n*m)。

for(i=0.in。i++)

for(j=0.jm。j++)

A[i][j]=0;

10.下面程序段的时间复杂度是O(log3n)。

i=1;

while(i=n)

i=i*3;

11.二维数组是其数据元素为线性表的线性表。

12.通常要求同一逻辑结构中的所有数据元素具有相同的

特性，这意味着不仅数据元素所包含的数据项的个数要相同，

而且对应的数据项的类型要一致。

13.链表不具备的特点是可随机访问任一结点。

14.不带头结点的单链表head为空的判定条件是head==

NULL。

15.带头结点的单链表head为空的判定条件是head-next

==NULL。

16.若某表最常用的操作是在最后一个结点之后插入一个

结点或删除最后一个结点，则采用带头结点的双循环链表存储

方式最节省运算时间。

17.需要分配较大空间，插入和删除不需要移动元素的线

性表，其存储结构是静态链表。

18.非空的循环单链表head的尾结点（由p所指向）满足

p-next==head。

19.在循环双链表的p所指的结点之前插入s所指结点的

操作是在p的前面插入s，即s-prev=p-prev，s-next=p，

p-prev-next=s，p-prev=s。

D。s-next=p。s-r=p-r。p-r-next=s。p-r=s。

如果要取第i个结点及其前驱，最节省时间的存储方式是

D存储方式。

在一个具有n个结点的有序单链表中插入一个新结点并仍

然保持有序的时间复杂度是O(n)。

在一个长度为n（n1）的单链表上，设有头和尾两个指

针，执行删除单链表中的最后一个元素操作与链表的长度有关。

双链表与单链表相比的优点之一是顺序访问相邻结点更灵

活。

如果对线性表的操作只有两种，即删除第一个元素，在最

后一个元素的后面插入新元素，则最好使用只有表尾指针没有

表头指针的循环单链表。

在长度为n的顺序表的第i个位置上插入一个元素（1≤i

≤n+1），元素的移动次数为n-i+1.

对于只在表的首、尾两端进行插入操作的线性表，宜采用

的存储结构为用尾指针表示的循环单链表。

顺序存储结构的优点之一是存储密度大。

关于线性表的叙述中，错误的是“线性表采用顺序存储，

便于进行插入和删除操作”。

线性表是具有n个数据元素的有限序列。

在n个结点的线性表的数组实现中，访问第i（1=i=n）

个结点和求第i个结点的直接前驱（1i=n）的算法的时间复

杂度是O(1)。

若长度为n的线性表采用顺序存储结构，在其第i个位置

插入一个新元素的算法的时间复杂度为O(n)。

对于顺序存储的线性表，访问结点的时间复杂度为O(1)，

而增加、删除结点