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

PAGEPAGE3《数据结构》填空作业题答案第1章绪论（已校对无误）1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。2．程序包括两个内容：数据结构和算法。3.数据结构的形式定义为：数据结构是一个二元组：DataStructure=（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，…，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。操作。17.从一个栈顶指针为top的非空链式栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行top＝top->link操作。18.设有一个空栈，栈顶指针为1000H（十六进制。现有输入序列为1，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，输出序列是2，3，而栈顶指针是100CH。设栈为顺序栈，每个元素占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出发的深度优先搜索序列为v1v2v3v6v5v4，其从顶点v1出发的广度优先搜索序列为v1v2v5v4v3v6。V1V1v2v3v4^v5v6^V2V5V4^v3V5^V4V6V3^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)；若采用分块查找（假定总块数和每块长度均接近），则时间复杂度为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.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有希尔排序、选择排序、快