数据结构第4次作业

1、数据结构第4次作业主观题(共50道小题)60.循环队列的引入，目的是为了克服顺序队列的假溢出 。61.区分循环队列的空与满有3种方法，它们是少用一个元素、设空满标志 、用计数器记录队列中元素个数 。62.栈和队列的区别是 栈只能在表一端进行插入和删除操作，队列限制在表的一端进行插入操作，在另一端进行删除操作 。63.一个栈的输入序列是12345，则栈的输出序列43512是 错误的 。64.设栈采取顺序存储结构，栈中已有i-1个元素，则第i个元素进栈操作的算法时间复杂度是 o（1） 。65.栈的特点是【后进先出 】，队列的特点是【先进先出 】；栈和队列都是【限制存取点的线性结构 】若入栈序列是1

2、，2，3，4 ，则【3,2,1,4 】是不可能的出栈序列；若进队列的序列是1，2，3，4，则【1,2,3,4 】是可能的出队序列。 66.若用不带头结点的单链表表示栈，则创建一个空栈要执行的操作是top=null 。 67.从循环队列中删除一个元素的操作是 q.front=(q.front+1)%qsize 。68.从循环队列中插入一个元素的操作是 q.rear=(q.rear+1)%qsize 。69.判断链队列中只有一个结点的条件是 q.front-next=q.rear 。70.如果栈的最大长度难以估计，最好使用链栈 。71.为什么说栈是一种后进先出表？答：因为栈是限定在表的一端进行插入

3、和删除操作，所以后入栈的数据元素总是先出栈，所以说栈是一种后进先出表。72.对于一个栈，其输入序列是a,b,c,试给出全部可能的输出序列。答：可能的出栈序列是：abc、acb、bac、bca、cba。 73.何谓队列上溢？何为假溢出现象？有哪些解决假溢出问题的方法，并分别阐述其工作原理。答：队列上溢指在队列的顺序存储分配中，按照队列的操作规则，需要进队的元素因找不到合适的存储单元而无法进入队列。 假溢出指在队列的顺序存储分配中，分配给队列的存储空间有存储单元未被占用，但按照操作规则而使进队的数据元素无法进队的现象。 解决假溢出问题的方法是在队列的顺序存储分配中，分配给队列的存储空间可以循环使用

4、，其进本原理是用表示队头和队尾指针与分配给队列的存储空间长度进行取模运算。即： 入队操作：q.rear=(q.rear+1)%msize 出队操作：q.front=(q.front+1)%msize 74.队列可以用单循环链表来实现，故可以只设一个头指针或只设一个尾指针，请分析用哪种方案最合适。答：使用循环链表来表示队列，设置尾指针比较合适，因为入队操作可以直接在尾结点后进行插入操作，出队操作时可以根据尾指针很容易找到链表的头结点，入队出队操作的算法时间复杂度均为o(1)。若只设头指针，则出队操作的算法时间复杂度为o(1)，入队操作的算法时间复杂度为o(n)。 75.深度为k的完全二叉树至少有

5、2k-1 个结点，至多有2k-1 个结点。76.在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2,则有n0= n2+1 。 77.一棵二叉树第i层最多有2i-1 个结点，一棵有n个结点的满二叉树共有 2k-1 个结点，共有2k-1 个叶结点。78.根据二叉树的定义，具有3个结点的二叉树共有 种不同形态，它们分别是5 。 79.有一棵如下图所示的树，回答下列问题： 这棵树的根结点是 a 。这棵树的叶子结点是 b,e,g,d 。结点c的度为 2 。这棵树的深度是 4 。结点c的孩子结点是 e,f 。结点c的双亲结点是 a 。这棵树的度是 3 。80.树与二叉树的两个主要差别是 树中结

6、点的最大度没有限制，二叉树结点的最大度限定为2 、 树的结点无左右之分，二叉树的的节点又左右之分 。81.设有如下图所示的二叉树，给出其前序、中序和后序遍历结果。 答：前序序列：eadcbifghj中序序列：abcdiefhgj后序序列：bcidahjgfe82.给出下图所示的树的二叉树表示。 答：下图为其树的二叉树表示。83.有一份电文共有5个字符：a,b,c,d,e,它们出现的频率依次为4，7，5，2，9，构造对应的哈夫曼树，求哈夫曼树的带权路径长度和每个字符的哈夫曼编码。答： 字符编码： a：011 b：10 c：00 d：010 e：1184. 假设一棵二叉树采用顺序存储结构，如下图所

7、示。 0 5 10 15 20 e a f d g c j h i b 回答些列问题： 画出二叉树表示。 写出先序、中序和后序遍历结果 写出结点c的双亲结点和左、右孩子结点 画出此二叉树还原成森林的图 答：二叉树表示如下图所示。先序序列为：eadcbjfghi 中序序列为：acbdjefhgi 后序序列为：bcjdahigfe结点c的双亲结点是d，左孩子为b，无右孩子该二叉树对应的森林为 85.有n个顶点的无向图最多有n(n-1)/2 条边。86.一个图的 邻接矩阵 表示法是唯一的，而邻接表 表示法是不唯一的。87.具有10个顶点的无向图，边的总数最多为 45 。88.在有n个顶点的有向图中，

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

9、【 】 。 答： n2e 93.顺序查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多为n 次；若查找不成功，则比较关键字的次数为n+1 次。 94.在含有n个元素的有序顺序表中进行二分查找，最大的比较次数是.log2n+1 。 95.用二分查找一个查找表，该查找表必须具有的特点是 顺序存储且关键字有序 。 96. 分块查找发将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间 关键字有序 。 97.在分块查找方法中，首先查找 关键字表 ，然后再查找相应的 对应的块 。98.用二叉排序树在n个元素中进行查找，最坏情况下查找时间复杂度为o(n) ，最好情况的查找时间复

10、杂度为 o(log2n) 。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的一个有序序列。答： 构造的二叉排序树如下图所示。对该二叉排序树进行中序遍历，就可以

11、得到d的一个有序序列： 1，3，5，7，8，9，10，12，13103.每次从无序子表中取出一个元素，把它插入到有序子表中恰当位置，此种排序方法叫做插入 排序；若每次从无序子表中挑选出最小或最大元素，把它交换到有序表的一端，此种排序方法叫做 直接选择 排序。104.每次通过基准元素间接比较两个元素，不满足约定要求时就交换位置，该排序方法叫做快速 排序；每次使两个相邻有序表合并成一个有序表的排序方法叫做归并 排序。105. 快速 排序方法采用二分法的思想， 堆 排序方法将数据的组织采用完全二叉树的结构。 106.对n个元素的表进行直接选择排序，所需要的关键字的比较次数为 n(n-1)/2 。107.在堆和快速排序中，若原始记录接近正序或反序，则选用 堆 ，若原始记录无序，则选用 快速 。 108.在