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

1、WORD格式弘成*数字化学习中心批次层次：专升本专业：计算机科学与技术*：X鹏亮学号： 15940673专业资料整理WORD格式1/12专业资料整理WORD格式第一次作业三、主观题 ( 共 3 道小题 )14.数据的物理构造包括的表示和的表示。参考答案： 线性构造 , 非线性构造15.数据逻辑构造包括、和四种，树构造和图构造统称为。参考答案： 集合 、 线性构造、 树 、 图 、非线性构造16.数据构造研究的是和以及它们之间的相互关系，并对于这种构造定义相应的，设计出相应的。参考答案： 逻辑构造 ， 物理构造， 运算，算法第二次作业三、主观题 ( 共 22 道小题 )24.向一个长度为n 的顺

2、序表中的第i 个元素之前插入一个元素时，需要向后移动个元素。参考答案： n-i+125.在一个长度为n 的顺序表中删除第i 个元素时，需要向前移动元素。参考答案：n-i26.在单链表中设置头结点的作用是。参考答案： 简单插入、删除算法27.在单链中要删除某一指定结点，必须找到该结点的结点。参考答案： 直接前驱28.访问单链表中的结点，必须沿着依次进展。参考答案： 指针域29.在双链表中每个结点有两个指针域，一个指向，一个指向。参考答案： 直接前驱结点，直接后继结点30.在链表中，删除最后一个结点的算法时间复杂度为O(1) 。参考答案：双向循环31.访问一个线性表中具有给定值的时间复杂度的数量级

3、是。参考答案： O(n)32. 由 n 个数据元素生成一个顺序表，假设每次都调用插入算法把一个元素插入到表头，那么整个算法的时间复杂度插入算法把一个元素插入到表尾，那么整个算法的时间复杂度为。参考答案： O(n)， O(n2)33.在链表中，可以用表尾指针代替表头指针。参考答案：双向专业资料整理WORD格式2/12专业资料整理WORD格式34.在链表中，可以用表尾指针代替表头指针。参考答案：双向35.根据 n 个数据元素建立对应的顺序表和单链表存储构造，其算法的时间复杂度最好的情况是，是。参考答案： O(n) ， O(n2)36.求线性表的顺序存储和链式存储的长度的算法时间复杂度分别是和。参考

4、答案：O(1),O(n)37. 在一个带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否一样？参考答案： 一样38.在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否一样？。参考答案： 不一样39.阐述顺序表和链表存储方式的特点。参考答案：顺序表存储方式为数据分配连续的存储单元，数据元素按逻辑顺序依次存储到相应存储单元中，使得逻辑相此可以实现随即访问线性表的数据元素，即数据访问的时间复杂度为O(1) 。链表存储方式分配的存储单元可以不连续，通过每个结点的指针域来表示数据元素之间的逻辑关系，只能顺40. 假设频繁地对一个线性表进展插入和删除

5、操作，那么该线性表宜采用何种存储构造，为什么？参考答案： 假设频繁地对一个线性表进展插入和删除操作，那么该线性表宜采用链式存储构造。因此链式存储构造在移动数据元素，只需要修改结点的指针域就可以改变数据元素之间的逻辑关系。41.在单链表、双向循环链表和单循环链表中，假设仅知道指针p 指向某结点，不知道头指针，能否将结点p 从间复杂度各为多少。参考答案： 要实现删除p 结点的操作，必须找到其前驱结点，修改其指针域的值使其指向p 的后继结点，以实现此不知道头指针就无法找到结点p 的前驱结点。 双向循环链表和单循环链表可以可以实现删除p 结点。单循环链O(n) ，双循环链表删除P 结点的时间复杂度为O

6、(1) 。42. 对链表设置头结点的作用是什么？参考答案：对带头结点的链表，在表的任何结点之前插入结点或删除任何位置的结点，所要做的都是修改前一个结点的表中任何元素结点都有前驱结点。如果没有头结点，在首元结点前插入结点或删除首元结点都要修改头指针，其杂些。其次，带头结点的链表构造，初始化后的头指针就固定了，除撤销算法外，所有算法都不会修改头指针43. 一个线性表用含头结点的单链表做存储构造，写一个算法求单链表的长度。参考答案：int listlenght(linklist L) int length=0; P=L-next; while(p) length+;专业资料整理WORD格式3/12专

7、业资料整理WORD格式p=p-next;return(length);44.一个顺序表L，其中的元素按值递增有序排列，设计一个算法插入一个值为x 的元素后保持该顺序表仍0 1 。参考答案：void insertsq(sqlist L,elemtype x) 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.elemn+1=L.elemn;return;45.写一个算法，从顺序表中删除值为x 的所有元素。参考答案：void delallsq(Sqlist

8、&L) int i=0,j=0; while(jnext=Q.rear70.如果栈的最大长度难以估计，最好使用。参考答案： 链栈71. 为什么说栈是一种后进先出表？参考答案： 因为栈是限定在表的一端进展插入和删除操作，所以后入栈的数据元素总是先出栈，所以说栈是一种72. 对于一个栈，其输入序列是 A,B,C, 试给出全部可能的输出序列。参考答案：可能的出栈序列是： ABC、 ACB、 BAC、 BCA、CBA。73. 何谓队列上溢？何为假溢出现象？有哪些解决假溢出问题的方法，并分别阐述其工作原理。参考答案：队列上溢指在队列的顺序存储分配中，按照队列的操作规那么，需要进队的元素因找不到适宜的存储

9、单元而无假溢出指在队列的顺序存储分配中，分配给队列的存储空间有存储单元未被占用，但按照操作规那么而使进队解决假溢出问题的方法是在队列的顺序存储分配中， 分配给队列的存储空间可以循环使用， 其进本原理是用队列的存储空间长度进展取模运算。即：入队操作： Q.rear=(Q.rear+1)%MSize出队操作： Q.front=(Q.front+1)%MSize74. 队列可以用单循环链表来实现，故可以只设一个头指针或只设一个尾指针，请分析用哪种方案最适宜。参考答案：使用循环链表来表示队列， 设置尾指针比较适宜， 因为入队操作可以直接在尾结点后进展插入操作，出队操专业资料整理WORD格式5/12专业

10、资料整理WORD格式到链表的头结点，入队出队操作的算法时间复杂度均为O(1) 。假设只设头指针，那么出队操作的算法时间复杂度为杂度为 O(n) 。75.深度为 k 的完全二叉树至少有个结点，至多有个结点。参考答案： 2K-1,2 K-176.在一棵二叉树中，度为0 的结点个数为 n0，度为 2 的结点个数为 n2, 那么有 n0=。参考答案：n2+177.一棵二叉树第i 层最多有个结点，一棵有n 个结点的满二叉树共有个结点，共有个叶结点。参考答案：i-1K,K-12,2 -1278.根据二叉树的定义，具有3 个结点的二叉树共有种不同形态，它们分别是。参考答案： 5,79. 有一棵如以下列图所示

11、的树，答复以下问题：这棵树的根结点是。这棵树的叶子结点是。结点 c 的度为。这棵树的深度是。结点 c 的孩子结点是。结点 c 的双亲结点是。这棵树的度是。参考答案： a b,e,g,d 2 4 e,f专业资料整理WORD格式6/12专业资料整理WORD格式 a 380.树与二叉树的两个主要差异是、参考答案： 树中结点的最大度没有限制，二叉树结点的最大度限定为2、树的结点无左右之分，二叉树81.设有如以下列图所示的二叉树，给出其前序、中序和后序遍历结果。参考答案：前序序列： eadcbifghj中序序列： abcdiefhgj后序序列： bcidahjgfe82. 给出以下列图所示的树的二叉树表

12、示。专业资料整理WORD格式7/12专业资料整理WORD格式参考答案：以下列图为其树的二叉树表示。83.有一份电文共有5 个字符： a,b,c,d,e,它们出现的频率依次为4，7， 5， 2， 9，构造对应的哈夫曼树，求哈字符的哈夫曼编码。参考答案：专业资料整理WORD格式8/12专业资料整理WORD格式字符编码：a： 011b： 10c： 00d： 010e： 1184.假设一棵二叉树采用顺序存储构造，如以下列图所示。05101520eafdgcjhib答复些列问题：画出二叉树表示。写出先序、中序和后序遍历结果写出结点c 的双亲结点和左、右孩子结点画出此二叉树复原成森林的图参考答案：二叉树表

13、示如以下列图所示。专业资料整理WORD格式9/12专业资料整理WORD格式先序序列为：eadcbjfghi中序序列为：acbdjefhgi后序序列为：bcjdahigfe结点 c 的双亲结点是d，左孩子为b，无右孩子该二叉树对应的森林为85.有 n 个顶点的无向图最多有条边。参考答案： n(n-1)/286.一个图的表示法是唯一的，而表示法是不唯一的。参考答案： 邻接矩阵 ,邻接表87.具有 10个顶点的无向图，边的总数最多为。参考答案： 4588.在有 n 个顶点的有向图中，每个顶点的度最大可达。参考答案： 2(n-1)89.一个有向图采用邻接矩阵表示，计算第i 个顶点的入度的方法是。参考答

14、案： 求第 i 列非 0元素个数90. 从占用的存储空间来看，对于稠密图和稀疏图，采用邻接矩阵和邻接表那个更好些？参考答案： 从占用存储空间看，稠密图采用邻接矩阵更好，稀疏图采用邻接表更好。91. 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？为什么？。参考答案：用邻接矩阵表示图，矩阵元素的个数与图的定点个数直接相关，与边的条数无关。因为假设定点个数为n，那么邻92.对于一个具有n 个顶点和e 条边的无向图，假设采用邻接表表示，那么表头向量的大小为【】；所有邻接表参考答案：n2e93.顺序查找含n 个元素的顺序表，假设查找成功，那么比较关键字的次数最多为次；假设查找

15、不成为次。参考答案： n,n+1专业资料整理WORD格式10/12专业资料整理WORD格式94.在含有 n 个元素的有序顺序表中进展二分查找，最大的比较次数是。参考答案：n. log 2 +195.用二分查找一个查找表，该查找表必须具有的特点是。参考答案： 顺序存储且关键字有序96.分块查找发将待查找的表均匀地分成假设干块且块中诸记录的顺序可以是任意的，但块与块之间。参考答案： 关键字有序97.在分块查找方法中，首先查找，然后再查找相应的。参考答案： 关键字表，对应的块98.用二叉排序树在n 个元素中进展查找，最坏情况下查找时间复杂度为，最好情况的查找时间复杂度为参考答案：O(n)n， O(l

16、og 2 )99.折半查找的存储构造仅限于，且是。参考答案：顺序存储构造，关键字有序排列100.一个无序序列可以通过构造一棵树而变成有序序列，构造树的过程即是对无序序列进展排序的过程参考答案：二叉排序101. 画出对长度为 10 的右序表进展折半查找的一棵判定树，并求其等概率时查找成功的平均查找长度。参考答案：平均查找长度 =(1+2*2+4*3+3*4)/10=2.9102.设有数据集合d=1， 12 ，5 ， 8，3 ， 10 ，7 ，13 ， 9，答复以下问题：依次取 d 中各数据，构造一棵二叉排序树；如何依据此二叉排序树得到d 的一个有序序列。参考答案：构造的二叉排序树如以下列图所示。

17、专业资料整理WORD格式11/12专业资料整理WORD格式对该二叉排序树进展中序遍历，就可以得到d 的一个有序序列：1 ， 3， 5， 7， 8， 9， 10， 12， 13103.每次从无序子表中取出一个元素，把它插入到有序子表中恰当位置，此种排序方法叫做排序；假设每次大元素，把它交换到有序表的一端，此种排序方法叫做排序。参考答案： 插入；直接选择104.每次通过基准元素间接比较两个元素，不满足约定要求时就交换位置，该排序方法叫做排序；每次使两表的排序方法叫做排序。参考答案： 快速； 归并105.排序方法采用二分法的思想，排序方法将数据的组织采用完全二叉树的构造。参考答案： 快速 ，堆106.对 n 个元素的表进展直接选择排序，所需要的关键字的比较次数为。参考答案