《数据结构》1至5章期末复习题 下载本文

内容发布更新时间 : 2024/12/24 8:34:19星期一 下面是文章的全部内容请认真阅读。

第一章

一、单项选择题 1. 数据结构是指( )。

A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2. 数据在计算机存储器内表示时,物理地址与逻辑地址不相同的,称之为( A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种( )。 A.一对一关系 B.多对多关系 C.多对一关系

D.一对多关系

4. 设语句x++的时间是单位时间,则以下语句的时间复杂度为( )。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1)

B.O( )

C.O(n)

D.O( )

5. 算法分析的目的是(1),算法分析的两个主要方面是(2)。 A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 (2) A.空间复杂度和时间复杂度 B.正确性和简明性

C.可读性和文档性 D.数据复杂性和程序复杂性 6. 计算机算法指的是(1),它具备输入,输出和(2)等五个特性。 (1) A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 (2) A.可行性,可移植性和可扩充性 B.可行性,确定性和有穷性 C.确定性,有穷性和稳定性 D.易读性,稳定性和安全性

。 ) 7. 数据在计算机内有链式和顺序两种存储方式,在存储空间使用的灵活性上,链式存储比顺序存储要( )。A.低

B.高

C.相同

D.不好说

8. 数据结构作为一门独立的课程出现是在( )年。 A.1946

B.1953

C.1964

D.1968

9. 数据结构只是研究数据的逻辑结构和物理结构,这种观点( )。 A.正确 B.错误 C.前半句对,后半句错 10. 计算机内部数据处理的基本单位是( )。 A.数据 B.数据元素

二、填空题

1. 数据结构按逻辑结构可分为两大类,分别是______________和_________________。 2. 数据的逻辑结构有四种基本形态,分别是________________、__________________、__________________和__________________。

3. 线性结构反映结点间的逻辑关系是__________________的,非线性结构反映结点间的逻辑关系是__________________的。

4. 一个算法的效率可分为__________________效率和__________________效率。

5. 在树型结构中,树根结点没有__________________结点,其余每个结点的有且只有__________________个前趋驱结点;叶子结点没有__________________结点;其余每个结点的后续结点可以__________________。

6. 在图型结构中,每个结点的前趋结点数和后续结点数可以__________________。

7. 线性结构中元素之间存在__________________关系;树型结构中元素之间存在__________________关系;图型结构中元素之间存在__________________关系。 8. 下面程序段的时间复杂度是__________________。 for(i=0;i

D.前半句错,后半句对

C.数据项 D.数据库

for(j=0;j A[i][j]=0;

9. 下面程序段的时间复杂度是__________________。 i=s=0;

while(s { i++; s+=i; }

10. 下面程序段的时间复杂度是__________________。 s=0;

for(i=0;i for(j=0;j s+=B[i][j]; sum=s;

11. 下面程序段的时间复杂度是__________________。 i=1; while(i<=n) i=i*3;

12. 衡量算法正确性的标准通常是____________________________________。

13. 算法时间复杂度的分析通常有两种方法,即___________和___________的方法,通常我们对算法求时间复杂度时,采用后一种方法。

三、求下列程序段的时间复杂度。 1. x=0;