《数据结构》填空作业题（答案）分析
《数据结构》填空作业题答案
第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 。
i=1；
while(i<=n)
i= i﹡3；
第2章线性表（已校对⽆误）
1. ⼀线性表表⽰如下：（a1，a2，…，a i-1，a i，a i+1，…，a n），其中每个a i代表⼀个数据元素（或结点）。a1称为起始结点，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(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 。
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/－。
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 。
2. ⼆维数组A[0…9，0…19]采⽤列序为主⽅式存储，每个元素占⼀个存储单元，并且元素A[0，0]的存储地址是200，则元素A[6，12]的地址是332 。
3. ⼆维数组A[10…20，5…10]采⽤⾏序为主⽅式存储，每个元素占4个存储单元，并且元素A[10，5]的存储地址是1000，则元素A[18，9]的地址是1208 。
1. ⼀维数组的逻辑结构是线性结构，存储结构是顺序存储结构。
2. 对于⼆维数组或多维数组，分为按以⾏为主序和按以列为主序两种不同的存储⽅式存储。
3. 对矩阵压缩存储是为了节省存储空间。
4. ⼆维数组是⼀种⾮线性结构，其中的每⼀个数组元素最多有⼆个直接前驱（或直接后继）。
第6章树（已校对⽆误）
4. 结点最少的树为只有⼀个结点的树，结点最少的⼆叉树为空的⼆叉树。
5. 根据⼆叉树的定义，具有三个结点的⼆叉树有 5 种不同的形态，它们分别是。
6. 具有n个结点的完全⼆叉树的深度为。
8. 以数据集{4，5，6，7，10，12，18}为结点权值所构造的哈夫曼树为需⽤图⽰，其带权路径长度为165 。
9. 哈夫曼树是带权路径长度最短的树，通常权值较⼤的结点离根较近。
10. 在先序遍历⼆叉树的序列中，任何结点的⼦树上的所有结点，都是直接跟在该结点之后。
第7章图（已校对⽆误）
1．n个顶点的连通图⾄少有n－1 条边。
2．在⽆权图G的邻接矩阵A中，若（vi，vj）或〈vi，vj〉属于图G的边集，则对应元素A[i][j]等于1 ，否则等于0 。
3. 在⽆向图G的邻接矩阵A中，若A[i][j]等于1，A[j] [i]等于 1 。
4. 已知图G的邻接表如下图所⽰，其从顶点v1出发的深度优先搜索序列为v1 v2 v3 v6 v5 v4，其从顶点v1出发的⼴度优先搜索序列为v1 v2 v5 v4 v3 v6。
5. 设x，y是图G中的两顶点，则（x，y）与（y，x）被认为⽆向，但〈x，y〉与〈y，x〉是有向的两条弧。
6. 已知⼀个图的邻接矩阵表⽰，删除所有从i个结点出发的边的⽅法是将矩阵的第i⾏全部置为0 。
7. 在有向图的邻接矩阵上，由第i⾏可得到第i 个结点的出度，⽽由第j列可得到第j 个结点的⼊度。
8. 在⽆向图中，如果从顶点v到顶点v′有路径，则称v和v′是连通。
第8章查（已校对⽆误）
1. 顺序查法的平均查长度为（n＋1）/2 ；哈希表查法采⽤链接法处理冲突时的平均查长度为1＋？。
2. 在各种查⽅法中，平均查长度与结点个数n⽆关的查⽅法是哈希表查法。
3. ⼆分查的存储结构仅限于有序的顺序存储结构。
4. 长度为255的表，采⽤分块查法，每块的最佳长度是15 。
5. N个记录的有序顺序表中进⾏折半查，最⼤的⽐较次数是㏒2N ？。
6. 对于长度为n的线性表，若进⾏顺序查，则时间复杂度为O(n) ；若采⽤⼆分法查，则时间
O(㏒2n) ；若采⽤分块查（假定总块数和每块长度均接近n），则时间复杂度为O(n) 。
7. 在散列存储中，装填因⼦a的值越⼤，则存取元素时发⽣冲突的可能性就越⼤；a的值越⼩，则存取元素时发⽣冲突的可能性就越⼩。
8. 对于⼆叉排序树的查，若根结点元素的键值⼤于被查元素的键值，则应该在⼆叉树的左⼦树上继续查。
9. ⾼度为8的平衡⼆叉树⾄少有54 个结点。
10. 在散列函数H（key）=key % p中，p应取素数。
第9章排序（已校对⽆误）
1. 在对⼀组记录（54，38，96，23，15，72，60，45，83）进⾏直接插⼊排序时，当把第8个记录45插⼊到有序表时，为寻插⼊位置需⽐较 5 次。
2. 对于关键字序列（12，13，11，18，60，15，7，20，25，100），⽤筛选法建堆，必须从键值为60的关键字开始。
3. 对n个记录的表r[1…n]进⾏简单选择排序，所需要进⾏的关键字间的⽐较次数为n(n－1)/2 。
4. 在插⼊排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有希尔排序、选择排序、快速排序、堆排序。
5. 在插⼊排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均⽐较次数最少的排序是快速排序，需要内存容量最多的是基数排序。
6. 在堆排序和快速排序中，若原始记录接近正序或反序，则选⽤堆排序，若原始记录⽆序，则最好选⽤快速排序。
7. 在插⼊排序和选择排序中，若初始数据基本正序，则选⽤插⼊排序；若初始数据基本反序，则选⽤选择排序。
8. 对n个元素的序列进⾏冒泡排序时，最少的⽐较次数是n－1 。
9. 基数排序不需要进⾏记录关键字间的⽐较。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。