数据结构习题及答案概论

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐数据结构习题及答案概论第1章算法

一、挑选题

1.算法的时光复杂度是指（）。

A）执行算法程序所需要的时光

B）算法程序中的指令条数

C）算法执行过程中所需要的基本运算次数

D）算法程序的长度

2.算法的空间复杂度是指（）。

A）算法程序的长度

B）算法程序所占的存储空间

C）算法执行过程中所需要的存储空间

D）算法程序中的指令条数

3.下面（）的时光复杂度最好（即执行时光最短）。

log)

A）O(n)B）O(n

2

log)D）O(n2)

C）O(nn

2

4.下面累加求和程序段的时光复杂度为（）。

intsum(inta[],intn)

{

inti,s=0;

for(i=0;ix)

return1;

else

return0;

}

log)

A）O(1)B）O(n

2

C）O(n)D）O(n)

8.下面程序段的时光复杂度为（）

intfun(intn)

{

inti=1,s=1;

while(sa2、a1==a2、a1”、“=”、“a2)

return">";

elase

if(a1==a2)

return"=";

elase

return"200)

return0;//数组中数据有错，统计失败

for(j=0;j,,,,,}

则该数据结构具有结构。

6.一种数据结构的元素集合为D，它在D上的二元关系R为：

D={a,b,c,d,e,f,g,h}

R={,,,,,,}

则该数据结构具有结构。

7.数据的规律结构分为线性结构和非线性结构，其中的非线性结构有两种基本类型。

三、简答题

1.数据结构主要讨论的三个问题是什么？

2.一个数据结构应包含两方面的信息是什么？

3.简述数据存储结构中的挨次存储方式。

4.简述数据存储结构中的链式存储方式

参考答案

一、单选题

1.①B，②D

2.C

3.D

4.A

5.C

6.A

7.C8.B9.B10.D11.C12.B

二、填空题

1.数据元素，数据项

2.链式、索引

3.线性结构与非线性结构

4.线性结构

5.线性

6.非线性（或树形）

7.树和图

三、简答题

1.答案：数据结构主要讨论的三个问题是：①数据的规律结构，②数据的存储结构，

③对各种数据结构举行的运算。

2.答案：一个数据结构应包含两方面的信息：①表示数据元素的信息；②表示各数据元素之间的前后件关系。

3.答案：在数据的存储结构中，挨次存储方式的含义如下：

挨次存储方式：把规律上相邻的数据元素存储在物理位置也相邻的存储单元里，数据元素之间的规律关系由存储单元的邻接关系来体现。

4.答案：在数据的存储结构中，链式存储方式的含义如下：

链式存储方式：使用指针表示数据元素之间的规律关系，各个数据元素的存储位置可以任意，不要求规律上相邻的数据元素在物理位置上也相邻。

第3章线性表及其存储结构

一、单选题

1.在一个长度为n的挨次存储的线性表中，向第i个元素（1≤i≤n+1）位置插入一个新元素时，需要从后向前依次后移（）个元素。

A）n-iB）n–i+1

C）n–i-1D）i

2.在一个长度为n的挨次存储的线性表中，删除第i个元素（1≤i≤n+1）时，需要先前向后依次前移（）个元素。

A）n-iB）n–i+1

C）n–i-1D）i

3.在一个长度为n的挨次表中，存在值为x的元素。在此表中用挨次搜寻法，查找值为x的元素，在等概率状况下，查找胜利时的平均查找长度为（）。

A）nB）n/2

C）(n+1)/2D）(n-1)/2

4.在一个长度为n的挨次表中，删除值为x的元素时，需要比较元素的次数和移动元素次数的和为（）。

A）n/2B）(n+1)/2

C）nD）n+1

5.在一个挨次表的表尾，插入一个元素时的时光复杂度为（）。

log)

A）O(1)B）O(n

2

C）O(n)D）O(n2)

6.在一个挨次表的随意位置，插入一个元素的时光复杂度为（）。

log)

A）O(1)B）O(n

2

C）O(n)D）O(n