数据结构1-3习题.pdfVIP

第1章绪论

1.1选择题

1.算法的时间复杂度取决于（）

A）问题的规模B）待处理数据的初态C）A和B

2.计算机算法指的是解决问题的步骤序列，它必须具备（）这三个特性。

A）可执行性可移植性可扩充性B）可执行性、确定性、有穷性

C）确定性、有穷性、稳定性D）易读性、稳定性、安全性

5．从逻辑上可以把数据结构分为（）两大类。

A）动态结构、静态结构B）顺序结构、链式结构

C）线性结构、非线性结构D）初等结构、构造型结构

6．在下面的程序段中，对x的赋值的语句频度为（）

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

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

A）O(2n)B）O(n)C．O(n2)D．O(log2n)

7．下面的程序段中，n为正整数，则最后一行的语句频度在最坏情况下是（）

for(i=n-1;i=1;i--)

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

if(A[j]A[j+1])

A[j]与A[j+1]对换；

A.O（n）B）O(nlog2n)C）O(n3)D）O(n2)

1.2填空题

2.对于给定的n个元素,可以构造出的逻辑结构有_____________，_____________，

_____________，_____________四种。

4．数据结构中评价算法的两个重要指标是_____________。

5.数据结构是研讨数据的_____________和_____________，以及它们之间的相互关系，并

对与这种结构定义相应的_____________，设计出相应的_____________。

6．一个算法具有5个特性：_____________、_____________、_____________，有零个或多

个输入、有一个或多个输出。

9．已知如下程序段

for(i=n;i0;i--){语句1}

{x=x+1;{语句2}

for(j=n;j=i;j--){语句3}

y=y+1;{语句4}

}

语句1执行的频度为_____________；语句2执行的频度为_____________；语句3执行的频

度为_____________；语句4执行的频度为_____________。

10.下面程序段中带下划线的语句的执行次数的数量级是_____________。

i=1;while(in)i=i*2;

11.下面程序段的时间复杂度为_____________。(n1)

sum=1;

for(i=0;sumn;i++)sum+=1;

第2章线性表

2.1选择题

1．对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（）最节

省时间

A）顺序表B）带头结点的双循环链表

C）单链表D）带尾结点的单循环链表

2．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复

杂度为（）(1≤i≤n+1)。

A）O(0)B）O(1)C）O(n)D）O(n2)

3．双向链表中有两个指针域，prior和next，分别指向前驱及后继，设p指向链表中的一个

结点，q指向一待插入结点，