西南交大数据结构主观题作业

1、弘成无锡数字化学习中心批次层次：专升本专业：计算机科学与技术姓名：刘鹏亮学号：第一次作业三、主观题(共3道小题)数据的物理结构包括的表示和的表示。参考答案：线性结构，非线性结构数据逻辑结构包括、和四种，树结构和图结构统称为。参考答案：集合、线性结构、树、图、非线性结构数据结构研究的是和以及它们之间的相互关系，并对于这种结构定义相应的，设计出相应的。参考答案：逻辑结构,物理结构，运算，算法第二次作业三、主观题(共22道小题)向一个长度为n的顺序表中的第i个元素之前插入一个元素时，需要向后移动个元素。参考答案：n-i+1在一个长度为n的顺序表中删除第i个元素时，需要向前移动元素。参考答案：n_i_

2、在单链表中设置头结点的作用是。参考答案：简单插入、删除算法在单链中要删除某一指定结点，必须找到该结点的结点。参考答案：直接前驱访问单链表中的结点，必须沿着依次进行。参考答案：指针域TOC o 1-5 h z在双链表中每个结点有两个指针域，一个指向，一个指向。参考答案：直接前驱结点，直接后继结点在链表中，删除最后一个结点的算法时间复杂度为0(1)。参考答案：双向循环访问一个线性表中具有给定值的时间复杂度的数量级是。参考答案：O(n)由n个数据元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂插入算法把一个元素插入到表尾，则整个算法的时间复杂度为。参考答案：O(n)

3、，O(n2)在链表中，可以用表尾指针代替表头指针。参考答案：双向在链表中，可以用表尾指针代替表头指针。参考答案：双向TOC o 1-5 h z根据n个数据元素建立对应的顺序表和单链表存储结构，其算法的时间复杂度最好的情况，最是。参考答案：0(n)，0(n2)求线性表的顺序存储和链式存储的长度的算法时间复杂度分别和。参考答案：0(1),0(n)在一个带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？参考答案：相同在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？。参考答案：不相同阐述顺序表和链表存储方式的特点。参考答案：顺序表存

4、储方式为数据分配连续的存储单元，数据元素按逻辑顺序依次存储到相应存储单元中，使得逻辑因此可以实现随即访问线性表的数据元素，即数据访问的时间复杂度为0(1)。链表存储方式分配的存储单元可以不连续，通过每个结点的指针域来表示数据元素之间的逻辑关系，只能素。若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什么？参考答案：若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用链式存储结构。因此链式存储结构要移动数据元素，只需要修改结点的指针域就可以改变数据元素之间的逻辑关系。在单链表、双向循环链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从时间复杂度

5、各为多少。参考答案：要实现删除p结点的操作，必须找到其前驱结点，修改其指针域的值使其指向p的后继结点，以实因此不知道头指针就无法找到结点p的前驱结点。双向循环链表和单循环链表可以可以实现删除p结点。单循.度为O(n)，双循环链表删除P结点的时间复杂度为O(1)。对链表设置头结点的作用是什么？参考答案：对带头结点的链表，在表的任何结点之前插入结点或删除任何位置的结点，所要做的都是修改前一个结点链表中任何元素结点都有前驱结点。如果没有头结点，在首元结点前插入结点或删除首元结点都要修改头指针法复杂些。其次，带头结点的链表结构，初始化后的头指针就固定了，除撤销算法外，所有算法都不会修改头指针已知一个线

6、性表用含头结点的单链表做存储结构，写一个算法求单链表的长度。参考答案：intlistlenght(linklistL)intlength=0;P=L-next;while(p)length+;p=p-next;return(length);已知一个顺序表L,其中的元素按值递增有序排列，设计一个算法插入一个值为X的元素后保持该顺序表仍为0(1)。参考答案：voidinsertsq(sqlistL,elemtypex)n=L.length-1;if(LT(L.elemn,x)n+;L.elemn=x;elsewhile(n=0<(x,L.elemn)L.elemn+1=L.elemn;n-;L

7、.elemn+1=L.elemn;return;写一个算法，从顺序表中删除值为X的所有元素。参考答案：voiddelallsq(Sqlist&L)inti=0,j=0;while(jL.length)if(L.elemj!=x)L.elemi+=L.elemj;j+;L.longth=i;第三次作业三、主观题(共50道小题)循环队列的引入，目的是为了克服。参考答案：顺序队列的假溢出区分循环队列的空与满有3种方法，它们是、。参考答案：少用一个元素、设空满标志、用计数器记录队列中元素个数TOC o 1-5 h z栈和队列的区别是，参考答案：栈只能在表一端进行插入和删除操作，队列限制在表的一端进行插

8、入操作，在另一端进行删除操作一个栈的输入序列是12345,贝9栈的输出序列43512是。参考答案：错误的设栈采取顺序存储结构，栈中已有卜1个元素，则第i个元素进栈操作的算法时间复杂度是。参考答案：0(1)栈的特点是【】，队列的特点是【】；栈和队列都是【】若入栈序列是1,是不可能的出栈序列；若进队列的序列是1,2，3，4,则【】是可能的出队序列。参考答案：后进先出先进先出限制存取点的线性结构3,2,1,41,2,3,4TOC o 1-5 h z若用不带头结点的单链表表示栈，则创建一个空栈要执行的操作是。参考答案：top=NULL从循环队列中删除一个元素的操作是。参考答案：Q.front二(Q.f

9、ront+1)%QSize从循环队列中插入一个元素的操作是。参考答案：Q.rear=(Q.rear+1)%QSize判断链队列中只有一个结点的条件是。参考答案：Q.front-next=二Q.rear如果栈的最大长度难以估计，最好使用。参考答案：链栈为什么说栈是一种后进先出表？参考答案：因为栈是限定在表的一端进行插入和删除操作，所以后入栈的数据元素总是先出栈，所以说栈是一对于一个栈，其输入序列是A,B,C,试给出全部可能的输出序列。参考答案：可能的出栈序列是：ABC、ACB、BAC、BCA、CBA。何谓队列上溢？何为假溢出现象？有哪些解决假溢出问题的方法，并分别阐述其工作原理。参考答案：队列上

10、溢指在队列的顺序存储分配中，按照队列的操作规则，需要进队的元素因找不到合适的存储单元而假溢出指在队列的顺序存储分配中，分配给队列的存储空间有存储单元未被占用，但按照操作规则而使进象。解决假溢出问题的方法是在队列的顺序存储分配中，分配给队列的存储空间可以循环使用，其进本原理是给队列的存储空间长度进行取模运算。即：入队操作：Q.rear=(Q.rear+1)%MSize出队操作：Q.front=(Q.front+1)%MSize队列可以用单循环链表来实现，故可以只设一个头指针或只设一个尾指针，请分析用哪种方案最合适。参考答案：使用循环链表来表示队列，设置尾指针比较合适，因为入队操作可以直接在尾结点

11、后进行插入操作，出队找到链表的头结点，入队出队操作的算法时间复杂度均为0(1)。若只设头指针，则出队操作的算法时间复杂度复杂度为0(n)。深度为k的完全二叉树至少有个结点，至多有个结点。TOC o 1-5 h z参考答案：2k-1,2k-1在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2,则有nO二。参考答案：n2+1一棵二叉树第i层最多有个结点，一棵有n个结点的满二叉树共有个结点，共有_个叶结点。参考答案：2-1,2k1,2k-1根据二叉树的定义，具有3个结点的二叉树共有种不同形态，它们分别是有一棵如下图所示的树，回答下列问题：TOC o 1-5 h z这棵树的根结点。这棵树的

12、叶子结点是结点c的度为。这棵树的深度是。结点c的孩子结点结点c的双亲结点是参考答案：ab,e,g,d24efa3树与二叉树的两个主要差别是、参考答案：树中结点的最大度没有限制，二叉树结点的最大度限定为2、树的结点无左右之分，二叉树设有如下图所示的二叉树，给出其前序、中序和后序遍历结果。参考答案：前序序列：eadcbifghj中序序列：abcdiefhgj后序序列：bcidahjgfe给出下图所示的树的二叉树表示。参考答案：下图为其树的二叉树表示。有一份电文共有5个字符：a,b,c,d,e,它们出现的频率依次为4,7,5,2,9,构造对应的哈夫曼树，求哈字符的哈夫曼编码。参考答案：a：011b：

13、10c：00d：010e：11字符编码：字符编码：84.假设一棵二叉树采用顺序存储结构，如下图所示。05101520eafdgcjhib回答些列问题：画出二叉树表示。写出先序、中序和后序遍历结果写出结点c的双亲结点和左、右孩子结点画出此二叉树还原成森林的图参考答案：二叉树表示如下图所示。先序序列为：eadcbjfghi中序序列为：acbdjefhgi后序序列为：bcjdahigfe结点c的双亲结点是d,左孩子为b,无右孩子有n个顶点的无向图最多有条边。参考答案：n(n-l)/2一个图的表示法是唯一的，而表示法是不唯一的。参考答案：邻接矩阵，邻接表TOC o 1-5 h z具有10个顶点的无向图

14、，边的总数最多为。参考答案：45在有n个顶点的有向图中，每个顶点的度最大可达。参考答案：2(n-l)已知一个有向图采用邻接矩阵表示，计算第i个顶点的入度的方法是。参考答案：求第i列非0元素个数从占用的存储空间来看，对于稠密图和稀疏图，采用邻接矩阵和邻接表那个更好些？参考答案：从占用存储空间看，稠密图采用邻接矩阵更好，稀疏图采用邻接表更好。用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？为什么？。参考答案：用邻接矩阵表示图，矩阵元素的个数与图的定点个数直接相关，与边的条数无关。因为假设定点个数为n,则邻对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的

15、大小为【】；所有邻接表参考答案：TOC o 1-5 h zn2e93顺序查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多次；若查找不丿为次。参考答案：n,n+1在含有n个元素的有序顺序表中进行二分查找，最大的比较次数。参考答案：.I_logn_|+1-2用二分查找一个查找表，该查找表必须具有的特点是。参考答案：顺序存储且关键字有序96.分块查找发将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间。参考答案：关键字有序在分块查找方法中，首先查找，然后再查找相应的。参考答案：关键字表，对应的块用二叉排序树在n个元素中进行查找，最坏情况下查找时间复杂度为，最好情况的查

16、找时间复杂度为参考答案：o(n)，O(log,n)折半查找的存储结构仅限于，且是。参考答案：顺序存储结构，关键字有序排列一个无序序列可以通过构造一棵树而变成有序序列，构造树的过程即是对无序序列进行排序的过程参考答案：二叉排序画出对长度为10的右序表进行折半查找的一棵判定树，并求其等概率时查找成功的平均查找长度。参考答案：平均查找长度=(1+2*2+4*3+3*4)/10=2.9102.设有数据集合d=1，12，5，8，3，10，7，13，9，回答下列问题依次取d中各数据，构造一棵二叉排序树；如何依据此二叉排序树得到d的一个有序序列。参考答案：构造的二叉排序树如下图所示。对该二叉排序树进行中序遍历，就可以得到d的一个有序序列：1，3，5，7，8，9，10，12，13每次从无序子表中取出一个元素，把它插入到有序子表中恰当位置，此种排序方法叫彳排序；若每次大元素，把它交换到有序表的一端，此种排序方法叫彳排序。参考答案：插入:直接选择每次通过基准元素间接比较两个元素，不满足约定要求时就交换位置，该排序方法叫彳排序；每次使两序表的排序方法叫做排序。参考答案：快速：归并排序方法采用二分法的思想，排序方法将数据的组织采用完全二叉树的结构。参考答案：快速，堆