《数据结构(专科)课程作业与评价》由会员分享，可在线阅读，更多相关《数据结构(专科)课程作业与评价（34页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构( (专科专科) )课程作业与评价课程作业与评价仅次于选择益友，就是选择好书。考尔德数据结构（专科）课程作业与评价中央电大 徐孝凯第一次作业第一章 绪论一、单选题1. 一个数组元素 ai与_的表示等价。A *(a+i) B a+i C *a+i D ix) return 1;else return 0;(2) int sum1(int n)int p=1, s=0;for(int i=1; ix)i=x%10;ci+;(6) void mtable(int n)for(int i=1; i=2)试编写出计算 Fib(n)的递归算法和非递归算法，并分析它们的时间复杂度和空间复杂度
2、。第三次作业第五章 树和二叉树一、填空题1对于一棵具有 n 个结点的树，该树中所有结点的度数之和为_。2. 假定一棵三叉树的结点个数为 50，则它的最小深度为_，最大深度为_。3在一棵高度为 h 的四叉树中，最多含有_结点。4在一棵三叉树中，度为 3 的结点数有 2 个，度为 2 的结点数有 1 个，度为 1 的结点数为 2 个，那么度为 0 的结点数有_个。5一棵深度为 5 的满二叉树中的结点数为_个，一棵深度为 3 的满四叉树中的结点数为_个。6假定一棵树的广义表表示为 A(B(C,D(E,F,G),H(I,J)，则树中所含的结点数为_个，树的深度为_，树的度为_。7假定一棵树的广义表表示
3、为 A(B(C,D(E,F,G),H(I,J)，则度为 3、2、1、0 的结点数分别为_、_、_和_个。8. 假定一棵树的广义表表示为 A(B(C,D(E,F,G),H(I,J)，则结点 H 的双亲结点为_，孩子结点为_。9在一棵二叉树中，假定双分支结点数为 5 个，单分支结点数为 6 个，则叶子结点数为_个。10对于一棵二叉树，若一个结点的编号为 i，则它的左孩子结点的编号为_，右孩子结点的编号为_，双亲结点的编号为_。11在一棵二叉树中，第 5 层上的结点数最多为_。12假定一棵二叉树的结点数为 18，则它的最小深度为_，最大深度为_。13一棵二叉树的广义表表示为 a(b(c,d),e(f
4、(,g)，则 e 结点的双亲结点为_，左孩子结点为_，右孩子结点为_。14. 一棵二叉树的广义表表示为 a(b(c,d),e(f(,g)，它含有双亲结点_个，单分支结点_个，叶子结点_个。15对于一棵含有 40 个结点的理想平衡树，它的高度为_。16. 假定一棵二叉树顺序存储在一维数组 a 中，则 ai元素的左孩子元素为_，右孩子元素为_，双亲元素(i1)为_。17假定一棵二叉树顺序存储在一维数组 a 中，但让编号为 1的结点存入 a0元素中，让编号为 2 的结点存入 a1元素中，其余类推，则编号为 i 结点的左孩子结点对应的存储位置为_，若编号为 i 结点的存储位置用 j 表示，则其左孩子结
5、点对应的存储位置为_。18.若对一棵二叉树从 0 开始进行结点编号，并按此编号把它顺序存储到一维数组 a 中，即编号为 0 的结点存储到 a0中，其余类推，则 ai元素的左孩子元素为_，右孩子元素为_，双亲元素(i0)为_。19对于一棵具有 n 个结点的二叉树，对应二叉链表中指针总数为_个，其中_个用于指向孩子结点，_个指针空闲着。20. 一棵二叉树广义表表示为 a(b(d(,h),c(e,f(g,i(k)，该树的结点数为_个，深度为_。21在一棵高度为 5 的理想平衡树中，最少含有_个结点，最多含有_个结点。22在一棵高度为 h 的理想平衡树中，最少含有_个结点，最多含有_个结点。23. 假
6、定一棵二叉树广义表表示为 a(b(c),d(e,f)，则对它进行的先序遍历结果为_，中序遍历结果为_，后序遍历结果为_，按层遍历结果为_。24. 假定一棵普通树的广义表表示为 a(b(e),c(f(h,i,j),g),d)，则先根遍历结果为_，按层遍历结果为_。二、应用题1. 已知一棵具有 n 个结点的完全二叉树被顺序存储于一维数组的 A1?An元素中，试编写一个算法打印出编号为 i 的结点的双亲和所有孩子。2. 编写一算法，求出一棵二叉树中所有结点数和叶子结点数，假定分别用变参 C1 和 C2 统计所有结点数和叶子结点数，初值均为0。3. 对于主教材中图 5-16 所示的树：(1) 写出先根
7、遍历得到的结点序列；(2) 写出按层遍历得到的结点序列；(3) 画出转换后得到的二叉树和二叉链表。仅次于选择益友，就是选择好书。考尔德第六章 二叉树的应用一、单选题1. 从二叉搜索树中查找一个元素时，其时间复杂度大致为_。A O(n) B O(1) C O(log2n) D O(n2)2. 向二叉搜索树中插入一个元素时，其时间复杂度大致为_。A O(1) B O(log2n ) C O(n) D O(nlog2n)3. 根据 n 个元素建立一棵二叉搜索树时，其时间复杂度大致为_。A O(n) B O(log2n ) C O(n2) D O(nlog2n)4. 从堆中删除一个元素的时间复杂度为_
8、。A O(1) B O(n) C O(log2n) D O(nlog2n)5. 向堆中插入一个元素的时间复杂度为_。A O(log2n) B O(n) C O(1) D O(nlog2n)6. 由权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为_。A 24 B 48 C 72 D 51二、填空题 1. 在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定_该结点的值，右子树上所有结点的值一定_该结点的值。2对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个_。3从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明_，若元素的值小于根结点的值，
9、则继续向_查找，若元素的大于根结点的值，则继续向_查找。4在一个堆的顺序存储中，若一个元素的下标为 i，则它的左孩子元素的下标为_，右孩子元素的下标为_。5. 在一个小根堆中，堆顶结点的值是所有结点中的_，在一个大根堆中，堆顶结点的值是所有结点中的_。6当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层_调整，直到被调整到_位置为止。7当从一个小根堆中删除一个元素时，需要把_元素填补到_位置，然后再按条件把它逐层_调整。8在哈夫曼编码中，若编码长度只允许小于等于 4，则除了已对两个字符编码为 0 和 10 外，还可以最多对_个字符编码。三、应用题1. 已知一组元素为(46,25,78,6
10、2,12,37,70,29)，画出按元素排列顺序输入生成的一棵二叉搜索树。2. 已知一棵二叉搜索树如图 6-11 所示，若从中依次删除72,12,49,28 结点，试分别画出每删除一个结点后得到的二叉搜索树3. 编写一个算法，返回搜索树中的关键字最大的元素值。4. 空堆开始依次向堆中插入线性表（38,64,52,15,73,40,48,55,26,12）中的每个元素，请以线性表的形式给出每插入一个元素后堆的状态。5. 已知一个堆为（12,15,40,38,26,52,48,64） ，若需要从堆中依次删除四个元素，请给出每删除一个元素后堆的状态。6. 有七个带权结点，其权值分别为 3,7,8,2
11、,6,10,14，试以它们为叶子结点构造一棵哈夫曼树，并计算出带权路径长度 WPL。7. 在一份电文中共使用五种字符：a,b,c,d,e，它们的出现频率依次为 4,7,5,2,9，试画出对应的编码哈夫曼树，求出每个字符的哈夫曼编码，并求出传送电文的总长度。第七章 图一、填空题1在一个图中，所有顶点的度数之和等于所有边数的_倍。2在一个具有 n 个顶点的无向完全图中，包含有_条边，在一个具有 n 个顶点的有向完全图中，包含有_条边。 3. 在一个具有 n 个顶点的无向图中，要连通所有顶点则至少需要_条边。4表示图的三种存储结构为_、_和_。5. 对于一个具有 n 个顶点的图，若采用邻接矩阵表示，
12、则矩阵大小为_。6对于一个具有 n 个顶点和 e 条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为_和_条。7. 在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有_和_结点。8对于一个具有 n 个顶点和 e 条边的有向图和无向图，若采用边集数组表示，则存于数组中的边数分别为_和_条。9对于一个具有 n 个顶点和 e 条边的无向图，当分别采用邻接矩阵、邻接表和边集数组表示时，求任一顶点度数的时间复杂度依次为_、_和_。仅次于选择益友，就是选择好书。考尔德10. 假定一个图具有 n 个顶点和 e 条边，则采用邻接矩阵、邻接表和边集数组表示时，其相应的空间复杂度分别为
13、_、_和_。11. 对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为_，对用邻接表表示的图进行任一种遍历时，其时间复杂度为_。12对于图 7-1(a)所示的无向图，假定用邻接矩阵表示，则从顶点 v0 开始进行深度优先搜索遍历得到的顶点序列为_，从顶点 v0 开始进行广度优先搜索遍历得到的顶点序列为_。13. 对于图 7-1(b)所示的有向图，假定用邻接矩阵表示，则从顶点 v0 开始进行深度优先搜索遍历得到的顶点序列为_，从顶点 v0 开始进行广度优先搜索遍历得到的顶点序列为_。14. 对于一个具有 n 个顶点和 e 条边的连通图，其生成树中的顶点数和边数分别为_和_。15. 对于图 7-5(a)所示的带权图，其最小生成树的权为_。16对于图 7-5(a)所示的图，若从顶点 v0 出发，则按照普里姆算法生成的最小生成树中，依次得到的各条边为_。17. 对于图 7-5(a)所示的图，若按照克鲁斯卡尔算法产生最小生成树，则得到的各条边依次为_。18
