文档介绍：该【《数据结构》填空作业题(答案) 】是由【青山代下】上传分享，文档一共【7】页，该文档可以免费在线阅读，需要了解更多关于【《数据结构》填空作业题(答案) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第1章绪论(已校对无误)、数据的存储结构和数据的运算三方面的内容。:数据结构和算法。:数据结构是一个二元组:DataStructure=(D,S)。,称为数据的存储结构。。,每个结点的前驱结点数和后继结点数可以有多个。,数据元素之间存在一对多的关系。,指数据元素在计算机中的标识(映象),也即存储结构。、树形结构和图形结构3种类型,树型结构和有向图结构合称为非线性结构。,结点之间的逻辑关系由存储单元位置的邻接关系来体现。,节点之间的逻辑关系由附加的指针域来体现。,它们分别是顺序存储、链式存储、索引存储和散列存储。,非线性结构反映结点间的逻辑关系是一对多或多对多。。,它不但定义了数据的表示方式,还给出了处理数据的实现方法。。。,一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。:有穷性、确定性、可行性、输入、输出。,算法给出了解决问题的一系列操作,每一操作都有它的确切的定义,并在有穷时间内计算出结果。㏒n。3while(i<=n)i=i﹡3;第2章线性表(已校对无误):(a,a,,a,a,a,…,a),其中每个a代表一个数据元素(或12i-1ii+1ni结点)。a称为起始结点,a称为终端结点,i称为a在线性表中的位置(或序号)。1ni对任意一对相邻结点a,a,(1≤i≤n),a称为a的直接前驱,a称为a的直接后继。ii+1ii+1i+,要删除第i个元素,则在顺序表示的情况下,计算复杂性为O(n),在链式表示的情况下,计算复杂性为O(1)。,向第i个元素(1≤i≤n)之前插入一个新元素时,需向后移动n-i+1个元素。。,具体的移动次数取决于表长n和插入位置i。(1),因此,顺序表也称为随机访问的数据结构。。(n)。,若要删除第一个结点,则须执行下列三条语句:U=L->next;L->next=U->next;free(U)。。,任意结点的存储位置都由直接前驱结点中的指针指示。*p,需找到它的直接前驱结点的地址,其时间复杂度为O(n)。,减少边界条件的判断。,当删除某一指定结点时,必须找到该结点的前驱结点。,每个结点有两个指针域,一个指向前驱结点,另一个指向后续结点。->next==NULL,不带头结点的单链表L为空的判定条件是L==NULL。,指针p所指结点为最后一个结点的条件是p->next==NULL。从表中任意结点出发都可访问到表中每一个元素(或从表中任意结点出发都可遍历整个链表)。、带头结点的循环单链表的尾指针,则该链表首结点的存储位置是rear->next->next。->prior==L->next。,可根据任一结点的地址遍历整个链表,而单链表中需知道头指针才能遍历整个链表。,其最少的比较次数是1。第3章栈和队列(已校对无误),队列又称为先进先出表。,首先使栈顶指针后移一个位置,然后把待插入元素写入(或插入)到这个位置上。,需要前移一位栈顶指针。,若栈顶指针等于-1,则为空栈;若栈顶指针等于maxSize-1,则为满栈。,若栈顶指针等于NULL,则为空栈;在一个链式队列中,若队头指针与队尾指针的值相同,则表示该队列为空或该队列只含有一个结点。,首先把栈顶指针的值赋给新结点的指针域,然后把新结点的存储位置赋给栈顶指针。。,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少为3。,现输入序列为1,2,3,4,5。经过push,push,pop,push,pop,push,pop,push后,输出序列是234。-1+5*2时,最先执行的运算是*,最后执行的运算是-。,除初始化操作外,其他基本操作的初始条件都要求栈存在。。,==,->=。+a*(y-b)-c/d,该表达式的前缀表示为-+x*a-yb/cd。后缀表示为xayb-*+cd/-。,X表示出栈操作,若元素入栈顺序为1234,为了得到1342出栈顺序,相应的S、X操作串为SXSSXSXX。top的链式栈中插入一个新结点*p时,应执行p->link=top和top=p操作。,应执行top=top->link操作。,栈顶指针为1000H(十六进制。现有输入序列为1,2,3,4,5,经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后,输出序列是2,3,而栈顶指针是100CH。设栈为顺序栈,每个元素占4个字节。;在作出栈运算时应先判别栈是否空。,当前rear和front的值分别为0和994,若要达到队满的条件,还需要继续入队的元素个数是993。,删除操作在队头进行。,==,判断队满的条件为(+1)%maxSize==。,需要首先移动队尾指针,然后再向所指位置写入(或插入)新插入的元素。,若用top==n表示栈空,则表示栈满的条件为top==0。,目的是为了克服假溢出时大量移动数据元素。第4章串(已校对无误)。,其长度等于其包含的空格个数。′abaabade′的next函数值为01122341补充:。,其长度等于零。。,其特殊性表现在其数据元素都是字符。第5章数组(已校对无误)[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中,已知每个元素占4个单元,则元素A[7,5]的地址为1100。[09,0…19]采用列序为主方式存储,每个元素占一个存储单元,并且元素A[0,0]的存储地址是200,则元素A[6,12]的地址是332。[10…20,5…10]采用行序为主方式存储,每个元素占4个存储单元,并且元素A[10,1000,则元素A[18,9]的地址是1208。补充:,存储结构是顺序存储结构。,分为按以行为主序和按以列为主序两种不同的存储方式存储。。,其中的每一个数组元素最多有二个直接前驱(或直接后继)。第6章树(已校对无误),结点最少的二叉树为空的二叉树。,具有三个结点的二叉树有5种不同的形态,它们分别是。。{4,5,6,7,10,12,18}为结点权值所构造的哈夫曼树为需用图示,其带权路径长度为165。,通常权值较大的结点离根较近。,任何结点的子树上的所有结点,都是直接跟在该结点之后。第7章图(已校对无误)-1条边。,若(vi,vj)或〈vi,vj〉属于图G的边集,则对应元素A[i][j]等于1,否则等于0。,若A[i][j]等于1,A[j][i]等于1。,其从顶点v1出发的深度优先搜索序列为v1v2v3v6v5v4,其从顶点v1出发的广度优先搜索序列为v1v2v5v4v3v6。V1V2V5V4^v2v3V5^v3V6^v4^v5V4V6V3^v6^,y是图G中的两顶点,则(x,y)与(y,x)被认为无向,但〈x,y〉与〈y,x〉是有向的两条弧。,删除所有从i个结点出发的边的方法是将矩阵的第i行全部置为0。,由第i行可得到第i个结点的出度,而由第j列可得到第j个结点的入度。,如果从顶点v到顶点v有路径,则称v和v′是连通。第8章查找(已校对无误)(n+1)/2;哈希表查找法采用链接法处理冲突时的平均查找长度为1+?。,平均查找长度与结点个数n无关的查找方法是哈希表查找法。。,采用分块查找法,每块的最佳长度是15。,最大的比较次数是㏒N?。,若进行顺序查找,则时间复杂度为O(n);若采用二分法查找,则时间复杂度为O(㏒n);若采用分块查找(假定总块数和每块长度均接近),则时间复杂度为2O(n)。,装填因子a的值越大,则存取元素时发生冲突的可能性就越大;a的值越小,则存取元素时发生冲突的可能性就越小。,若根结点元素的键值大于被查元素的键值,则应该在二叉树的左子树上继续查找。。(key)=key%p中,p应取素数。第9章排序(已校对无误)(54,38,96,23,15,72,60,45,83)进行直接插入排序时,当把第8个记录45插入到有序表时,为寻找插入位置需比较5次。(12,13,11,18,60,15,7,20,25,100),用筛选法建堆,必须从键值为60的关键字开始。[1…n]进行简单选择排序,所需要进行的关键字间的比较次数为n(n-1)/2。的有希尔排序、选择排序、快速排序、堆排序。、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,平均比较次数最少的排序是快速排序,需要内存容量最多的是基数排序。,若原始记录接近正序或反序,则选用堆排序,若原始记录无序,则最好选用快速排序。,若初始数据基本正序,则选用插入排序;若初始数据基本反序,则选用选择排序。,最少的比较次数是n-1。。