数据结构期末速成复习资料 (一)

路漫漫其修远兮，吾将上下而求索

• 今天是2020年的倒数第二天，此时的我还窝在寝室复习数据结构，莫得办法，为了部落为了胜利
• 然后以下是一些我复习数据结构时的习题，分享给大家！

一、填空题

1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科
2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合
3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容
4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构
5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系
6. 数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列
7. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序
8. 一个算法的效率可分为 时间 效率和 空间 效率

二、选择题

1. 非线性结构是数据元素之间存在一种：
   A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系
2. 数据结构中，与所使用的计算机无关的是数据的 结构；
   A) 存储 B) 物理 C) 逻辑 D) 物理和存储

数据的逻辑结构反映的是数据元素之间的逻辑关系，与使用的计算机无关

3. 算法分析的目的是：
   A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系
   C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性
4. 算法分析的两个主要方面是：
   A) 空间复杂性和时间复杂性 B) 正确性和简明性
   C) 可读性和文档性 D) 数据复杂性和程序复杂性

算法分析是对一个算法需要多少计算时间和存储空间作定量的分析

5. 计算机算法指的是：
   A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法

在计算机中，算法是指解题方案的准确而完整的描述。是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。

6. 计算机算法必须具备输入、输出和 __________ 等5个特性。
   A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性
   C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性

三、简述题

1. 数据结构和数据类型两个概念之间有区别吗？
   解: 简单地说，数据结构定义了一组按某些关系结合在一起的数据元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。
2. 简述线性结构与非线性结构的不同点
   解：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的

四、分析时间算法度

# 首先声明以下有些题目可能会有点格式不规范哈，千万不要被误导了!
# 第一题: 
# 两个嵌套的for循环，所有时间复杂度用大O表示法为: O(m*n)
for(i=0;i<n;i++)
	for(j=0;j<m;j++)
		A[i][j]=0;

# 第二题
# x++这一行语句一共执行了(n-1)+(n-2)+...+1 = n(n-1)/2
# 时间复杂度为O(n^2)
x = 0;
for(i=1; i<n;i++)
	for(j=1; j<=n-i;j++)
		x++;

# 第三题
# 执行k次i=i*3，i*3^k<=n (i=1)--> k<=log3(n)
# 因此时间复杂度为O（log3(n))
i=1;
while(i<=n)
	i=i*3;
	

• 在这个星球上，你很重要，请珍惜你的珍贵 ~~~~夜斗小神社