《数据结构》填空作业题答案第 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. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切的定义，并在有穷时间内计算出结果。

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

1i=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 。

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

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

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/－。

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

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

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 。

2. 二维数组 A[0 ⋯9，0⋯ 19]采用列序为主方式存储，每个元素占一个存储单元，并且元素A[0 ，0]的存储地址是 200，则元素 A[6 ，12]的地址是332 。

3. 二维数组 A[1 0⋯20，5⋯10]采用行序为主方式存储，每个元素占 4 个存储单元，并且元素A[10 ，5] 的存储地址是 1000，则元素 A[18 ， 9]的地址是1208 。

4补充：1. 一维数组的逻辑结构是线性结构，存储结构是顺序存储结构。

2. 对于二维数组或多维数组，分为按以行为主序和按以列为主序两种不同的存储方式存储。

3. 对矩阵压缩存储是为了节省存储空间。

4. 二维数组是一种非线性结构，其中的每一个数组元素最多有二个直接前驱（或直接后继）。

第 6 章树（已校对无误）4.结点最少的树为只有一个结点的树，结点最少的二叉树为空的二叉树。

5. 根据二叉树的定义，具有三个结点的二叉树有 5 种不同的形态，它们分别是。

6. 具有 n 个结点的完全二叉树的深度为。

8. 以数据集 {4 ，5，6，7，10，12， 18}为结点权值所构造的哈夫曼树为需用图示，其带权路径长度为 165 。

9. 哈夫曼树是带权路径长度最短的树，通常权值较大的结点离根较近。

10.在先序遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。