2024年5月26日发(作者：)
《数据结构》填空作业题答案
第1章绪论
（已校对无误）
数据的逻辑结构
数据结构
、
和
数据的存储结构
算法。
Data Structure =（D，S）。
存储结构
结构两大类。
有多个。
。
和数据的运算三方面的内容。1．数据结构包括
2．程序包括两个内容：
3. 数据结构的形式定义为：数据结构是一个二元组：
4. 数据的逻辑结构在计算机存储器内的表示，称为数据的
5. 数据的逻辑结构可以分类为线性结构和非线性
6. 在图状结构中，每个结点的前驱结点数和后继结点数可以
7. 在树形结构中，数据元素之间存在
8. 数据的物理结构，指数据元素在
9. 数据的逻辑结构包括
图结构合称为非线性结构
线性结构
。
连续
一对多
计算机
、
的关系。
中的标识（映象），也即
和图形结构
存储结构。
树形结构3种类型，树型结构和有向
10. 顺序存储结构是把逻辑上相邻的结点存储在物理上
关系由存储单元位置的邻接关系来体现。
11. 链式存储结构是把逻辑上相邻的结点存储在物理上
关系由附加的指针域来体现。
的存储单元里，结点之间的逻辑
任意的存储单元里，节点之间的逻辑
12. 数据的存储结构可用4种基本的存储方法表示，它们分别是
存储和散列存储。
13. 线性结构反映结点间的逻辑关系是
对多或多对多。
顺序存储结构和链式
一对一
顺序存储、链式存储、索引
的，非线性结构反映结点间的逻辑关系是一
14. 数据结构在物理上可分为存储结构。
表示方式，还给出了处理数15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的
据的实现方法。
数据项组成。
时间复杂度和空间
16. 数据元素可由若干个
17. 算法分析的两个主要方面是复杂度。
的多少来度量的，一个算法的空间复杂18. 一个算法的时间复杂度是用该算法
度是用该算法在运行过程中所占用的
19. 算法具有如下特点：有穷性
所消耗的时间
存储空间的大小来度量的。
可行性、输入、输出。
确切
、确定性、
20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的
的定义，并在有穷时间内计算出结果。
㏒
3
n 。
1
21. 下面程序段的时间复杂度为
i=1；
while(i<=n)
i= i﹡3；
第2章线性表
（已校对无误）
，其中每个a
i
代表一个数据元素（或
1. 一线性表表示如下：（a
1
，a
2
，…，a
i-1
，a
i
，a
i+1
，…，a
n
）
结点）。a
1
称为起始结点，a
n
称为终端结点，i称为a
i
在线性表中的
前驱
位置（或序号）
后继
。
。对任意一对相邻结点a
i
，a
i+1
，（1≤i≤n），a
i
称为a
i+1
的直接，a
i+1
称为a
i
的直接
2. 对一个长度为n的线性表，要删除第i个元素，则在顺序表示的情况下，计算复杂性为
在链式表示的情况下，计算复杂性为O(1) 。
O(n) ，
3. 在一个长度为n的顺序表中，向第i个元素（1≤i≤n）之前插入一个新元素时，需向后移动
－i＋1 个元素。
4. 顺序表中逻辑上相邻的元素在物理位置上一定相连。
n/2 个结点，具体的移动次数取决于
n
5. 在n个结点的顺序表中插入一个结点需平均移动
长n和插入位置i 。
6. 在顺序表中访问任意一个结点的时间复杂度均为
的数据结构。
7. 顺序表相对于链表的优点有随机访问和
表
O(1) ，因此，顺序表也称为随机访问
空间利用率高。
8. 在长度为n的顺序表中插入一个元素的时间复杂度为
9. 在带有头结点的单链表
L->next=U->next；free（U）。
10. 链表相对于顺序表的优点有插入和删除
O(n) 。
U＝L->next ；L中，若要删除第一个结点，则须执行下列三条语句：
操作方便。
直接前驱结点中的指针指示。
，其时间复
11. 在单链表中除首结点外，任意结点的存储位置都由
12. 在n个结点的单链表中要删除已知结点
杂度为O(n) 。
*p，需找到它的直接前驱结点的地址
13．单链表中设置头结点的作用是简化操作，减少边界条件的判断。
前驱结点。
。
14．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的
15. 在双链表中，每个结点有两个指针域，一个指向
16. 带头结点的单链表L为空的判定条件是
定条件是L==NULL 。
17. 在单链表中，指针p所指结点为最后一个结点的条件是
2
前驱结点，另一个指向后续结点
L->next==NULL ，不带头结点的单链表L为空的判
p->next==NULL 。
发布者：admin，转转请注明出处：http://www.yc00.com/news/1716719625a2730605.html
评论列表（0条）