【例1-1】分析以下程序段的时间复杂度。
for(i=0;ifor(j=0;j a[i][j]=0;
解：该程序段的时间复杂度为o(m*n)。
例1-2】分析以下程序段的时间复杂度。
i=s=0; ①
while(s
解：设fact（n）的运行时间函数是t(n)。该函数中语句①的运行时间是o(1)，语句②的运行时间是t(n-1)+ o(1)，其中o(1)为常量运行时间。
由此可得fact（n）的时间复杂度为 o(n)。
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++;5. 算法分析的目的是（ ）算法分析的两个主要方面是（ ）
1） a.找出数据结构的合理性b.研究算法中的输入和输出关系。
c.分析算法的效率以求改进 d.分析算法的易懂性和文档性。
2） a.空间复杂度和时间复杂度 b.正确性和简明性。
c.可读性和文档性d.数据复杂性和程序复杂性。
6. 计算机算法指的是（ ）它具备输入，输出和（ ）等五个特性。
1） a.计算方法b.排序方法。
c.解决问题的有限运算序列 d.调度方法。
2） a.可行性，可移植性和可扩充性 b.可行性，确定性和有穷性。
c.确定性，有穷性和稳定性 d.易读性，稳定性和安全性。
7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ ）
a.低b.高c.相同d.不好说。
8. 数据结构作为一门独立的课程出现是在（ ）年。
a.1946b.1953c.1964d.1968
9. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（ ）
a.正确b.错误。
c.前半句对，后半句错d.前半句错，后半句对。
10. 计算机内部数据处理的基本单位是（ ）
a.数据b.数据元素 c.数据项 d.数据库。
1. 数据结构按逻辑结构可分为两大类，分别是和。
2. 数据的逻辑结构有四种基本形态，分别是和。
3. 线性结构反映结点间的逻辑关系是的，非线性结构反映结点间的逻辑关系是的。
4. 一个算法的效率可分为效率和效率。
5. 在树型结构中，树根结点没有结点，其余每个结点有且只有个前驱结点；叶子结点没有结点；其余每个结点的后续结点可以有个。
6. 在图型结构中，每个结点的前趋结点数和后续结点数可以。
7. 线性结构中元素之间存在关系；树型结构中元素之间存在关系；图型结构中元素之间存在关系。
8. 下面程序段的时间复杂度是。
for(i=0;ifor(j=0;ja[i][j]=0;
9. 下面程序段的时间复杂度是。
i=s=0;
while(s
while(j<=m) /表a已结束，表b没有结束，链入表b的剩余部分。
c).elem[k]＝(b).elem[j];
i++;k++;
return (1);
例2-2】写一算法实现单链表的逆置。
解：假设单链表的表头指针用head表示，其类型为下面定义的linklist，并且单链表不带头结点。逆置后原来的最后一个结点成为第一个结点，于是从第一个结点开始逐个修改每个结点的指针域进行逆置，且刚被逆置的结点总是新链表的第一个结点，故令head指向它（如图2-1所示）。
typedef struct node
elemtype data;
struct node *next;
linklist;
具体算法描述如下：
void contray(linklist *head)
线性结构练习题
概论。1.单选题。1 从逻辑上可以将数据结构分为两大类，即 a 动态结构 静态结构 b 顺序结构 链式结构。c 线性结构 非线性结构 d 初等结构 构造型结构。2 数据结构中讨论有关数据的最小单位是 a 数据对象 b 数据元素 c 数据项 d 以上都不对。3 数据结构中组成数据的基本单位是 a 数据...
线性结构与非线性结构
数据结构 逻辑结构 存储结构。逻辑结构分为四种 数据元素间没有任何关系 集合。数据元素间有线性关系 线性结构。所谓线性关系 除第一个元素外，其他元素有且只有一个前驱 除最后一个元素外，其他元素有且只有一个后继！数据元素间有层状关系 树结构。数据元素间有网状关系 图结构。非线性结构。传统文本 例如书籍...
线性结构在非线性结构中的应用
摘要 数据结构课程中数据的逻辑结构分为线性结构和非线性结构。数据结构中线性结构指的是数据元素之间存在着 一对一 的线性关系的数据结构。相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后驱。关键字 线性表，树，图。1.引言。数据元素相互之间的关系称为结构。有四类基本结构 ...