《《数据结构》填空作业题(答案)-设有一个空栈.docx》由会员分享，可在线阅读，更多相关《《数据结构》填空作业题(答案)-设有一个空栈.docx（6页珍藏版）》请在第壹文秘上搜索。
1、数据结构填空作业题答案第1章绪论（已校对无误）1 .数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。2 .程序包括两个内容：数据结构和算法。3 .数据结构的形式定义为：数据结构是一个二元组：DataStructure=（D,S）。4 .数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。5 .数据的逻辑结构可以分类为线性结构和非线性结构两大类。6 .在图状结构中，每一个结点的前驱结点数和后继结点数可以有多个。7 .在树形结构中，数据元素之间存在一对多的关系。8 .数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。9 .数据的逻辑结构包括线性结构、树形结
2、构和图形结构3种类型，树型结构和有向图结构合称为非线性结构O10 .顺序存储结构是把逻辑上相邻的结点存储在物理上型的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。11 .链式存储结构是把逻辑上相邻的结点存储在物理上的存储单元里，节点之间的逻辑关系由附加的指针域来体现。12 .数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。13 .线性结构反映结点间的逻辑关系是一对一的,非线性结构反映结点间的逻辑关系是:对多或者多对多。14 .数据结构在物理上可分为顺序存储结构和链式存储结构。15 .我们把每种数据结构均视为抽象类型，它非但定义了数据的
3、表示方式,还给出了处理数据的实现方法。16 .数据元素可由若干个数据项组成。17 .算法分析的两个主要方面是时间复杂度和空间复杂度。18 .一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的,一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。19 .算法具有如下特点：行穷性、确定性、一行性、输入、输出。20 .对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的切当的定义，并在有穷时间内计算出结果。21 .下面程序段的时间复杂度为Iog叩。while(inext；L-next=U-next;free(U)O10 .链表相对于顺序表的优点有32-和
4、删除操作方便。11 .在单链表中除首结点外，任意结点的存储位置都由直接前驱结点中的指针指示。12 .在n个结点的单链表中要删除已知结点*p,需找到它的直接前驱结点的地址，其时间复杂度为0(n)。13 .单链表中设置头结点的作用是简化操作，减少边界条件的判断.14 .在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的前驱结点。15 .在双链表中，每一个结点有两个指针域，一个指向前驱结点,另一个指向后续结点o16 .带头结点的单链表L为空的判定条件是L-Mext=NULL,不带头结点的单链表L为空的判定条件是L=NULL。17 .在单链表中，指针P所指结点为最后一个结点的条件是p-ne
5、xt=NULL018 .循环链表的最大优点是从表中任意结点出发都可访问到表中每一个元素（或者从表中任意结点出发都可遍历整个链表）。19 .设rear是指向非空、带头结点的循环单链表的尾指针，则该链表首结点的存储位置是rear-next-next。20,带头结点的双向循环表L为空表的条件是L-prior=L-nexto21 .在循环链表中，可根据任一结点的地址遍历整个链表，而单链表中需知道头指针才干遍历整个链表。22 .将两个各有n个元素的有序表归并成一个有序表，其至少的比较次数是1。第3章栈和队列（已校对无误）1 .栈又称为后进先出表，队列又称为先进先出表。2 .向一个顺序栈插入一个元素时，首
6、先使栈顶指针后移一个位置，然后把待插入元素写入（或者插入）到这个位置上。3 .从一个栈删除元素时，需要前移一位栈顶指针o4 .在一个顺序栈中，若栈顶指针等于一1,则为空栈；若栈顶指针等于maxSize-1,则为满栈。5 .在一个链式栈中，若栈顶指针等于NULL,则为空栈；在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列为空或者该队列只含有一个结点。6 .向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给栈顶指针。7 .在求表达式值的算符优先算法中使用的主要数据结构是栈。8 .设有一个顺序栈S,元素s1,s2,s3,s4,s5,s6挨次进栈
7、，如果6个元素的出栈顺序为s2,S3,s4,s6,s5,s1,则顺序栈的容量至少为3。9 .设有一个空栈，现输入序列为1,2,3,4,5o经过push,push,pop,push,pop,push,pop,PUSh后，输出序列是234o10 .在按算符优先法求解表达式31+5*2时，最先执行的运算忠丁，最后执行的运算是。11 .在栈的ADT定义中，除初始化操作外，其他基本操作的初始条件都要求栈存在。12 .仅允许在同一端进行插入和删除的线性表称为栈。13 .在顺序栈S中，栈为空的条件是s.top=s.base,枝为满的条件是s.top-s.base=s.stacksize。14 .设有算术表达
8、式x+a*（yb）cd,该表达式的前缀表示为一+x*a-ybcd。后缀表示为xayb*+cd-。15 .用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234,为了得到1342出栈顺序，相应的S、X操作串为SXSSXSXXo16 .向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行p-link=top和top=p操作。17 .从一个栈顶指针为top的非空链式栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行top=top-link操作。18 .设有一个空栈，栈顶指针为WOOH（十六进制。现有输入序列为1,2,3,4,5,经过PUSH,PUSH,POP,PUSH,POP,PU
9、SH,PUSH之后，输出序列是2,3,而栈顶指针是IooCHo设栈为顺序栈，每一个元素占4个字节。19 .在作入栈运算时应先判别栈是否满；在作出栈运算时应先判别栈是否空。10.用一个大小为100O的数组来实现循环队列，当前rear和front的值分别为。和994,若要达到队满的条件，还需要继续入队的元素个数是993o20 .队列的插入操作在队尾进行,删除操作在队头进行。21 .在一个循环队列Q中，判断队空的条件为Q.front=Q.rear,判断队满的条件为（Q.rear1）%maxSize=Q.front。22 .向一个循环队列中插入元素时，需要首先挪移队尾指针，然后再向所指位置写入（或者插
10、入）新插入的元素。23 .当用长度为n的数组顺序存储一个栈时，若用top=n表示栈空，则表示栈满的条件为top=0o24 .循环队列的引入，目的是为了克服假溢出时大量挪移数据元素o第4章串（己校对无误）1 .两个串相等的充分必要条件是两个串的长度相等且对应位置的字符相同。2 .空格串是由一个或者多个空格字符组成的串,其长度等于其包含的空格个数。3 .模式串abaabade,的next函数值为01122341补充：1 .串的两种最基本的存储方式是顺序存储方式和链接存储方式。2 .空串是零个字符的串，其长度等于零o3 .组成串的数据元素只能是字符。4 .串是一种特殊的线性表，其特殊性表现在其数据元
11、素都是字符。第5章数组（己校对无误）1 .将下三角矩阵A1.8,1.8的下三角部份逐行地存储到起始地址为100O的内存单元中，已知每一个元素占4个单元，则元素A7,5的地址为f00o2 .二维数组A0.9,019采用列序为主方式存储，每一个元素占一个存储单元，并且元素A0,0的存储地址是200,则元素A6,12的地址是332。3 .二维数组A10.20,5.10采用行序为主方式存储，每一个元素占4个存储单元，并且元素A10,5的存储地址是IOo0,贝阮素A18,9的地址是1208。补充：1 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构O2 .对于二维数组或者多维数组，分为按以行为主序
12、和按以列为主序两种不同的存储方式存储。3 .对矩阵压缩存储是为了节省存储空间o4,二维数组是一种非线性结构，其中的每一个数组元素最多有二个直接前驱（或者直接后继）。第6章树（己校对无误）4 .结点至少的树为惟独一个结点的树，结点至少的二叉树为空的二叉树。5 .根据二叉树的定义，具有三个结点的二叉树有3种不同的形态，它们分别是o6 .具有n个结点的彻底二叉树的深度为，8 .以数据集4,5,6,7,10,12,18为结点权值所构造的哈夫曼树为需用图示，其带权路径长度为165。9 .哈夫曼树是带权路径长度最短的树，通常权值较大的结点离根较近。10 .在先序遍历二叉树的序列中，任何结点的子树上的所有结
13、点，都是直接跟在该结点之后。第7章图（己校对无误）1 .n个顶点的连通图至少有n-1条边。2 .在无权图G的邻接矩阵A中，若（vi,Vj）或者vi,vj属于图G的边集，则对应元素Aij等三1，否则等于0o3 .在无向图G的邻接矩阵A中，若Aij等于1,Aji等于1。4 .已知图G的邻接表如下图所示，其从顶点v1出发的深度优先搜索序列为v1v2v3v6v5v4,其从顶点v1出发的广度优先搜索序列为v1v2v5v4v3v6o5 .设x,y是图G中的两顶点，则(x,y)与(y,x)被认为无向，伸x,y与y,x)是也向的两条弧。6 .已知一个图的邻接矩阵表示，删除所有从i个结点出发的边的方法是将矩阵的第i行全部置为O。7 .在有向图的邻接矩阵上，由第i行可得到第_L个结点的出度，而由第j列可得到第一个结点的入度。8 .在无向图中，如果从顶点V到顶点U有路径，则称V和V，是一连通。第8章查找(已校对无误)1 .顺序查找法的平均查找长度为(n+1)/2；哈希表查找法采用链接法处理冲突时的平均查找长度为1+?02 .在各种查找方法中，平均查找长度与结点个数n无关的查找方法是一哈希表查找法。3 .二分查找的存储结构仅限于有序的顺序存储结构。4 .长度为255的表，采用分块查找法，每块的最佳长度是15。5 .N个记录的有
