数据结构作业：第1章概论.docx

第一章概论一、填空题数据结构被形式地定义为（D,R）,其中D是 数据元素的有限集合,R是I）上的 关系 有限集合。
2. 数据结构包括数据的 逻辑结构 、数据的存储结构 和数据的 运算 这三个方面的内容。
3. 数据结构按逻辑结构可分为四大类，它彳门分另U是集合，线性结构，树形结构，图状结构或网状结构。
4. 线性结构中元素之间存在二双二关系，树形结构中元素之间存在一对多关系,图形结构中元素之间存在 多对多关系。
5. 在线性结构中，第一个结点递查前驱结点，其余每个结点有且只有1个前驱结点;最后一个结点壶 4_后续结点，其余每个结点有且只有1个后续结点。
6. 在树形结构中，树根结点没有结点，其余每个结点有且只有_i_个前驱结点；叶子结点没有 后续 结点,其余每个结点的后续结点数可以任意多个。
9. 数据的存储结构中顺序存储结构是通过一物理上相邻一表示元素之间的关系的;链式存储结构是通过一指针—表示元素之间的关系的。
10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。
II. 一个算法的效率可分为时间 效率和空间效率。
二、单项选择题（B ） 1.非线性结构是数据元素之间存在一种：
A） 一对多关系 B）多对多关系C）多对一关系 D） 一对一关系（C ） 2,数据结构中，与所使用的计算机无关的是数据的结构；A）存储 B）物理C）逻辑D）物理和存储（C ）3.算法分析的目的是：
A）找出数据结构的合理性 C）分析算法的效率以求改进
（A ） 4.算法分析的两个主要方面是： A）空间复杂性和时间复杂性 C）可读性和文档性
（C ） 5.计算机算法指的是：
A）计算方法B）排序方法
（B ） 6,计算机算法必须具备输入、输出和 A）可行性、可移植性和可扩充性 C）确定性、有穷性和稳定性

A）存储 B）物理C）逻辑D）物理和存储（C ）3.算法分析的目的是：
A）找出数据结构的合理性 C）分析算法的效率以求改进
（A ） 4.算法分析的两个主要方面是： A）空间复杂性和时间复杂性 C）可读性和文档性
（C ） 5.计算机算法指的是：
A）计算方法B）排序方法
（B ） 6,计算机算法必须具备输入、输出和 A）可行性、可移植性和可扩充性 C）确定性、有穷性和稳定性
（C ）3.算法分析的目的是：
A）找出数据结构的合理性 C）分析算法的效率以求改进
（A ） 4.算法分析的两个主要方面是： A）空间复杂性和时间复杂性 C）可读性和文档性
（C ） 5.计算机算法指的是：
A）计算方法B）排序方法
（B ） 6,计算机算法必须具备输入、输出和 A）可行性、可移植性和可扩充性 C）确定性、有穷性和稳定性

（C ）3.算法分析的目的是：
A）找出数据结构的合理性 C）分析算法的效率以求改进
（A ） 4.算法分析的两个主要方面是： A）空间复杂性和时间复杂性 C）可读性和文档性
（C ） 5.计算机算法指的是：
A）计算方法B）排序方法
（B ） 6,计算机算法必须具备输入、输出和 A）可行性、可移植性和可扩充性 C）确定性、有穷性和稳定性
B）研究算法中的输入和输出的关系
D）分析算法的易懂性和文档性
B）正确性和简明性
D）数据复杂性和程序复杂性
C）解决问题的有限运算序列D）调度方法
等5个特性。
B）可行性、确定性和有穷性
D）易读性、稳定性和安全性
四、判读题
1. 数据元素是数据的最小单位。（X ）
2. 健壮的算法不会因非法的输入数据而出现莫名其妙的状态q ）【大连海事大学2001 一、11（ 1分）】算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序 了o (X)【西安交通大学1996二、7 (3分)】五、【严题集1.8®］分析下面各程序段的时间复杂度

1.
答:

for (i=0; i<n; i++) for (j=0; j<m; j++)AliJUJ=O；O (m*n)2. s=0;
for i=0; i<n; i++) for(j=0;jvn;j++) s+=B[i][j]； sum=s;

4. i=l;
while(i<=n) i=i*3; 答：O (log3n)
答：O (n2)
3. x=0;
fbr(i=l; i<n; i++)
for(j=l:j<=n-i;j++)
x++;
解：因为x++共执行了 n-l+n-2++1=
n(n-1)/2,所以执行时间为O(I?)” ”T一 1)川)二 N»斗-*%22 ?=1 尸,+1i=lL