《数据结构》填空作业题（答案解析）

范文范例 值得参考

《数据结构》填空作业题答案

第1章 绪论（已校对无误）

1．数据结构包括 数据的逻辑结构 、 数据的存储结构 和 数据的运算 三方面的内容。2．程序包括两个内容： 数据结构 和 算法 。

3. 数据结构的形式定义为：数据结构是一个二元组： Data Structure =（D，S） 。 4. 数据的逻辑结构在计算机存储器内的表示，称为数据的 存储结构 。 5. 数据的逻辑结构可以分类为 线性 结构和 非线性 结构两大类。 6. 在图状结构中，每个结点的前驱结点数和后继结点数可以 有多个 。 7. 在树形结构中，数据元素之间存在 一对多 的关系。

8. 数据的物理结构，指数据元素在 计算机 中的标识（映象），也即 存储结构 。 9. 数据的逻辑结构包括 线性结构 、 树形结构 和 图形结构 3种类型，树型结构和有向图结构合称为 非线性结构 。

10. 顺序存储结构是把逻辑上相邻的结点存储在物理上 连续 的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。

11. 链式存储结构是把逻辑上相邻的结点存储在物理上 任意 的存储单元里，节点之间的逻辑关系由附加的指针域来体现。

12. 数据的存储结构可用4种基本的存储方法表示，它们分别是 顺序存储 、 链式存储 、 索引存储 和 散列存储 。

13. 线性结构反映结点间的逻辑关系是 一对一 的，非线性结构反映结点间的逻辑关系是 一对多或多对多 。

14. 数据结构在物理上可分为 顺序 存储结构和 链式 存储结构。

15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的 表示 方式，还给出了处理数据的 实现方法 。

16. 数据元素可由若干个 数据项 组成。

17. 算法分析的两个主要方面是 时间 复杂度和 空间 复杂度。

18. 一个算法的时间复杂度是用该算法 所消耗的时间 的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的 存储空间 的大小来度量的。

19. 算法具有如下特点： 有穷性 、确定性、 可行性 、输入、输出。

20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的 确切 的定义，并在 有穷时间 内计算出结果。

word完美 整理版

范文范例 值得参考

21. 下面程序段的时间复杂度为 ㏒3n 。

i=1； while(i<=n) i= i﹡3；

第2章 线性表（已校对无误）

1. 一线性表表示如下：（a1，a2，…，ai-1，ai，ai+1，…，an），其中每个ai代表一个 数据元素（或结点） 。a1称为 起始 结点，an称为 终端 结点，i称为ai在线性表中的 位置（或序号） 。对任意一对相邻结点ai，ai+1，（1≤i≤n），ai称为ai+1的直接 前驱 ，ai+1称为ai的直接 后继 。

2. 对一个长度为n的线性表，要删除第i个元素，则在顺序表示的情况下，计算复杂性为 O(n) ，在链式表示的情况下，计算复杂性为 O(1) 。

3. 在一个长度为n的顺序表中，向第i个元素（1≤i≤n）之前插入一个新元素时，需向后移动 n－i＋1 个元素。

4. 顺序表中逻辑上相邻的元素在物理位置上 一定 相连。

5. 在n个结点的顺序表中插入一个结点需平均移动 n/2 个结点，具体的移动次数取决于 表长n和插入位置i 。

6. 在顺序表中访问任意一个结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机访问 的数据结构。

7. 顺序表相对于链表的优点有 随机访问 和 空间利用率高 。 8. 在长度为n的顺序表中插入一个元素的时间复杂度为 O(n) 。

9. 在带有头结点的单链表L中，若要删除第一个结点，则须执行下列三条语句： U＝L->next ；L->next=U->next；free（U）。

10. 链表相对于顺序表的优点有 插入 和 删除 操作方便。

11. 在单链表中除首结点外，任意结点的存储位置都由 直接前驱 结点中的指针指示。 12. 在n个结点的单链表中要删除已知结点*p，需找到 它的直接前驱结点的地址 ，其时间复杂度为 O(n) 。

13．单链表中设置头结点的作用是 简化操作，减少边界条件的判断 。

14．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的 前驱 结点。 15. 在双链表中，每个结点有两个指针域，一个指向 前驱结点 ，另一个指向 后续结点 。 16. 带头结点的单链表L为空的判定条件是 L->next==NULL ，不带头结点的单链表L为空的判定条件是 L==NULL 。

word完美 整理版

范文范例 值得参考

17. 在单链表中，指针p所指结点为最后一个结点的条件是 p->next==NULL 。

18. 循环链表的最大优点是 从表中任意结点出发都可访问到表中每一个元素（或从表中任意结点出发都可遍历整个链表） 。

19. 设rear是指向非空、带头结点的循环单链表的尾指针，则该链表首结点的存储位置是 rear->next->next 。

20. 带头结点的双向循环表L为空表的条件是 L->prior== L->next 。

21. 在循环链表中，可根据任一结点的地址遍历整个链表，而单链表中需知道 头指针 才能遍历整个链表。

22. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 1 。

第3章 栈和队列（已校对无误）

1. 栈又称为 后进先出 表，队列又称为 先进先出 表。

2. 向一个顺序栈插入一个元素时，首先使 栈顶指针 后移一个位置，然后把待插入元素 写入（或插入） 到这个位置上。

3. 从一个栈删除元素时，需要前移一位 栈顶指针 。 4. 在一个顺序栈中，若栈顶指针等于 －1 ，则为空栈； 若栈顶指针等于 maxSize－1 ，则为满栈。

5. 在一个链式栈中，若栈顶指针等于NULL，则为 空栈 ；在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列为 空 或该队列 只含有一个结点 。

6. 向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给 新结点的指针域 ，然后把新结点的存储位置赋给 栈顶指针 。

7．在求表达式值的算符优先算法中使用的主要数据结构是 栈 。

8．设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为 3 。

9. 设有一个空栈，现输入序列为1，2，3，4，5。经过push，push，pop，push，pop，push，pop，push后，输出序列是 2 3 4 。

10. 在按算符优先法求解表达式3－1＋5*2时，最先执行的运算是 * ，最后执行的运算是 － 。 11. 在栈的ADT定义中，除初始化操作外，其他基本操作的初始条件都要求 栈存在 。 12. 仅允许在同一端进行插入和删除的线性表称为 栈 。

13. 在顺序栈s中，栈为空的条件是 s.top==s.base ，栈为满的条件是 s.top－s.base＞=s.stacksize 。

14. 设有算术表达式x＋a*（y－b）－c/d，该表达式的前缀表示为 －＋x*a－yb/cd 。 后缀表示为 xayb－*＋cd/－ 。

word完美 整理版

范文范例 值得参考

15. 用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S、X操作串为 SXSSXSXX 。

16. 向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行 p->link＝top 和 top＝p 操作。

17. 从一个栈顶指针为top的非空链式栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行 top＝top->link 操作。

18. 设有一个空栈，栈顶指针为1000H（十六进制。现有输入序列为1，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，输出序列是 2，3 ，而栈顶指针是 100C H。设栈为顺序栈，每个元素占4个字节。

19. 在作入栈运算时应先判别栈是否 满 ；在作出栈运算时应先判别栈是否 空 。 10. 用一个大小为1000的数组来实现循环队列，当前rear和front的值分别为0和994，若要达到队满的条件，还需要继续入队的元素个数是 993 。

20. 队列的插入操作在 队尾 进行，删除操作在 队头 进行。

21. 在一个循环队列Q中，判断队空的条件为 Q.front==Q.rear ，判断队满的条件为 (Q.rear＋1)％maxSize==Q.front 。

22. 向一个循环队列中插入元素时，需要首先移动 队尾指针 ，然后再向所指位置 写入（或插入） 新插入的元素。

23. 当用长度为n的数组顺序存储一个栈时，若用top==n表示栈空，则表示栈满的条件为 top==0 。

24. 循环队列的引入，目的是为了克服 假溢出时大量移动数据元素 。

第4章 串（已校对无误）

1. 两个串相等的充分必要条件是 两个串的长度相等且对应位置的字符相同 。 2. 空格串是 由一个或多个空格字符组成的串 ，其长度等于 其包含的空格个数 。 3. 模式串′abaabade′的next函数值为 01122341 补充：

1. 串的两种最基本的存储方式是 顺序存储方式和链接存储方式 。 2. 空串是 零个字符的串 ，其长度等于 零 。 3. 组成串的数据元素只能是 字符 。

4. 串是一种特殊的线性表，其特殊性表现在 其数据元素都是字符 。

第5章 数组（已校对无误）

1. 将下三角矩阵A[1..8，1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则元素A[7，5]的地址为 1100 。

word完美 整理版