当前位置：文档之家 › 网上农大数据结构A-D作业答案—均为满分哟!

网上农大数据结构A-D作业答案—均为满分哟!

  • 格式：doc
  • 大小：1.28 MB
  • 文档页数：43

数据结构（第2版）-在线作业_A 用户名：W360201121011最终成绩：100.0设有数据逻辑结构为：Data=(D,R);D={d1,d2,d3,d4,d5,d6,d7 }R={<d1,d2>,<d2,d1>,<d1,d4>,<d4,d1>,<d2,d3>,<d3,d2>,<d2,d6>,<d6,d2>,<d2,d7>,<d 7,d2>,<d3,d7><d7,d3><d4,d6><d6,d4>,<d5,d7>,<d7,d5>}试分析该数据结构属于哪种逻辑结构？（）n-i-1n-in-i+1i判断下列程序段的时间复杂度数量级（）。

for(i=1;i<n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;在一个长度为n的顺序存储线性表中，向第i个元素（1<=i<=n+1）位置插入一个新元素2134本题分值： 5.0 用户得分：5.0 用户解答： 2知识点： 2.3 链接存储结构线性表top-- top++ top=N-1 top=0在一个单链表中，若要在p 所指向的结点之后插入一个新结点，则需要相继修改（ ）个当利用大小为N 的数组顺序存储一个栈时，假定用top==N 表示栈空，则向这个栈插入一front == 0rear+1 == frontfront+1 == rear front == rear本题分值： 5.0用户得分： 5.0用户解答： front == rear知识点： 3.1 顺序存储结构队列{00,01,10,11} {0,01,00,11}{1,01,000,001} {0,10,110,111}本题分值： 5.0 用户得分： 5.0在规定顺序环形队列一般状态队头指针指向第一个数据元素之前的空位，队尾指针指向末尾元素的前提下，假定一个顺序循环队列的队首和队尾指针分别用front 和rear 表示，下述编码中不是前缀编码的是（ ）。

在一个具有n个顶点的有向图中，若所有顶点的出度之和为S，则所有顶点的入度之和为1-4-2-3-6-51-2-4-6-3-5 1-4-6-2-5-3 1-2-3-4-5-6本题分值： 5.0 用户得分： 5.0用户解答： 1-4-6-2-5-3 知识点： 5.6 拓扑排序13.adefbc adcbef已知有向图如下，则该图的一种拓扑序列为（ ）。

对下图从顶点a 出发进行深度优先遍历，正确的广度优先遍历结点序列为（ ）。

插入排序，选择排序对长度为3的顺序表进行查找，查找第一个元素的概率是1/2，查找第二个元素的概率是多种排序方法中：（ ）法从未排序的序列中依次取出元素，与已排序序列（初始为空）中的元素作比较，将其放入已排序序列的正确位置；（ ）法从未排序的序列中挑选元素，23 1 4本题分值： 5.0 用户得分：5.0 用户解答： 4知识点： 7.2 希尔排序38,40,46,56,79,84用希尔排序对数据序列{15,9,7,8,20，-1,4}进行排序，进行第一趟排序后，数据序列变一组记录关键字为{46,79,56,38,40,84}，应用快速排序法，以第一个关键字作为排序对80,36,20,12,55,4180,36,15,20,12,41 80,12,55,20,36,4180,12,20,55,36,41本题分值： 5.0 用户得分： 5.0用户解答： 80,36,15,20,12,41 知识点： 7.3 堆排序一个无序数据序列12,36,41,20,80,55 采用顺序表存储数据，采用堆排序算法建立的初内部结构和外部结构紧凑结构和非紧凑结构线性结构和非线性结构动态结构和静态结构本题分值： 5.0用户得分： 5.0用户解答：线性结构和非线性结构知识点： 1.2 基本概念和术语给定三个算法频度函数：f(n)=100n3+n2+1000g(n)=25n3+4000n2h(n)=n1.01+1000nlg(n)指出算法时间复杂度数量级描述中错误的是（）。

在数据结构中，从逻辑上可以把数据结构分成（）。

数据结构（第2版）-在线作业_B 用户名：W360201121011最终成绩：100.0易读性、安全性、稳定性确定性、有穷性和稳定性可行性、可移植性和可扩展性可行性、确定性和有穷性本题分值： 5.0设有数据逻辑结构为：Data=(D,R);D={d1,d2,d3,d4,d5,d6,d7,d8,d9,d10}R={<d1,d2>,<d1,d3>,<d1,d4>,<d2,d5>,<d2,d6>,<d3,d7>,<d3,d8>,<d3,d9>,<d4,d10>}试分析该数据结构属于哪种逻辑结构？（）计算机算法必须具备输入、输出、（）等5个特征。

(n+1)/2n n/2 n+1本题分值： 5.0 用户得分： 5.0 用户解答： n知识点： 2.2 顺序存储结构线性表在一个长度为n 的顺序存储线性表中，删除值为x 的元素，问进行比较和数据移动的总操0 2-1在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据一次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。

该缓冲区应该树中所有结点的度的总和等于结点总数加（ ）。

29 58 55某二叉树先序遍历结点访问顺序是 abcdgcefh,中序遍历的节点访问顺序是 dgbaechf, 利用3,6,8,12这四个值，作为叶子结点的权重，生成一棵Huffman 树，该树的带权路径定点相对较少的生成树所有生成树中权值之和最低的生成树边数最少的生成树连通子图本题分值： 5.0 用户得分： 5.0用户解答： 所有生成树中权值之和最低的生成树 知识点： 5.1 图的基本术语与定义a,b,c,d,e a,d,c,b,e a,b,d,c,e d,a,b,c,e本题分值： 5.0最小生成树指的是连通图中（ ）。

无向图G=（V ，E ），V={a,b,c,d,e}，E={<a,b>, <a,c>, <d,c>, <d,e>, <b.e>, <c,e>},用户得分： 5.0用户解答： a,b,c,d,e 知识点： 5.6 拓扑排序12.1-3-4-5-2 1-2-3-4-5 1-4-3-5-2 1-2-3-5-4本题分值： 5.0 用户得分： 5.0用户解答： 1-3-4-5-2知识点： 5.2 图的存储|5.3 图的遍历13.已知有向图的邻接表如下：根据有向图深度优先遍历原则，从定点V1出发，所得到的定点序列是（ ）。

adbefcadcbfe adcefb adefbc本题分值： 5.0 用户得分： 5.0 用户解答： adbefc 知识点： 5.3 图的遍历14.【68,11,18,69】【23,93,73】【68,11,69,23,18】【93,73】【93,73】【68,11,69,23,18】 【68,11,69,23】【18,93,73】本题分值： 5.0 用户得分： 5.0对下图从顶点a 出发进行深度优先遍历，不可能的深度优先遍历结点序列为（ ）。

下述序列中，（ ）是执行第一趟快速排序后所得到的序列。

以顺序存储结构存储 以顺序存储结构存储，且数据元素有序以链接式存储结构存储，且数据元素有序 以链接式存储结构存储本题分值： 5.0 用户得分： 5.0用户解答： 以顺序存储结构存储，且数据元素有序 知识点： 6.2 查找算法如果待排序序列中两个数据元素具有相同的值在排序前后他们的相互位置发生颠倒，则称对线性表进行折半查找时，要求线性表必须（ ）。

给出下列典型时间复杂度数量级从低到高的顺序。

（）O(1), O(n), O(n2), O(n3), O(nlg(n)), O(lg(n)), O(2n)一个无限序列，不能为空一个有限序列，不能为空一个有限序列，可以为空一个无限序列，可以为空本题分值： 5.0用户得分： 5.0用户解答：一个有限序列，可以为空知识点： 2.2 顺序存储结构线性表数据结构是一门研究非数值计算程序设计问题中（）以及它们之间的关系和运算等的课程。

线性表是（）。

数据结构（第2版）-在线作业_C 用户名：W360201121011最终成绩：100.0O(n2)O(lg(n))O(nlg(n))O(n)本题分值： 5.0设有数据逻辑结构为：line=(D,R);D={d1,d2,d3,d4,d5,d6,d7,d8,d9,d10}R={<d5,d1>,<d1,d3>,<d3,d8>,<d8,d2>,<d2,d7>,<d7,d4>,<d4,d6>,<d6,d9>,<d9,d10>}试分析该数据结构属于哪种逻辑结构？（）下面（）的时间复杂度最好。

q->next=p->next ，p->next =p->next->next q->next=NULL ，p->next = q q->next=p->next ，p->next = q q->next=p ，p->next = q在一个长度为n 的顺序存储线性表中，当在任何位置插入或删除一个元素的概率相等时，插入一个元素所需要移动元素的平均个数为（ ），删除一个元素需要移动元素的平均个设链表中指针p 指向结点a i ，指针q 指向将要插入的新结点x ，若要将新结点插入到a iIIIOIOIO IIIOOIOO IIOIOIIO IOIIOIIO IOOIOIIO本题分值： 5.0 用户得分： 5.0假设以I 和O 分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列38 55 32 36本题分值： 5.0 用户得分： 5.0两个具有n 结点的（n>1）二叉树的先序遍历序列和后序遍历序列的结点顺序正好相反，利用3,7,5,4这四个值，作为叶子结点的权重，生成一棵Huffman 树，该树的带权路径长用户解答： 38知识点：4.4 Huffman 树及应用9.9 68 7本题分值： 5.0 用户得分： 5.0 用户解答： 9知识点： 5.1 图的基本术语与定义10.a-d-f-c-b-e a-b-c-d-e-f a-c-e-f-d-b a-f-d-b-c-e本题分值： 5.0 用户得分： 5.0G 是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。

合集下载

最新数据结构作业题参考答案

最新数据结构作业题参考答案

东北农业大学网络教育学院数据结构作业题参考答案习题一答案一、选择题（每题2分，共20分）二、填空题（每题1分，共20分）1．n(n-1)/2；02． 13．54．2i-15．2i；2i+1；i/26．顺序；链接；索引；散列7．10；4；38．n-19．一对一；一对多；多对多10．10三、运算题（每题5分，共10分）1．根据题意，矩阵A中当元素下标I与J满足I≥J时，任意元素A[I][J]在一维数组B中的存放位置为I * (I + 1) / 2 + J，因此，A[8][5]在数组B中位置为8 * (8 + 1) / 2 + 5 = 41。

四、应用题（每题10分，共50分）1．答：(1)直接插入排序第一趟(3)[8,3],2,5,9,1,6 第二趟(2)[8,3,2],5,9,1,6第三趟(5)[8,5,3,2],9,1,6 第四趟(9)[9,8,5,3,2],1,6第五趟(1)[9,8,5,3,2,1],6 第六趟(6)[9,8,6,5,3,2,1](2)直接选择排序（第六趟后仅剩一个元素，是最小的，直接选择排序结束）第一趟(9)[9],3,2,5,8,1,6 第二趟(8)[9,8],2,5,3,1,6第三趟(6)[9,8,6],5,3,1,2 第四趟(5)[9,8,6,5],3,1,2第五趟(3)[9,8,6,5,3],1,2 第六趟(2)[9,8,6,5,3,2],12．(1)是大堆；(2)是大堆；（4）是小堆；(3)不是堆，调成大堆100，98，66，85，80，60，40，77，82，10，203．答：先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则，本题解答如下：（1）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树（2）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树． （3）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树． （4）若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树4．答：（1）T 树的最大深度Kmax=6（除根外，每层均是两个结点）T 树的最小深度Kmin=4（具有6个叶子的完全二叉树是其中的一种形态） （2）非叶子结点数是5。

2022年江西农业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年江西农业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年江西农业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下述文件中适合于磁带存储的是（）。

A.顺序文件B.索引文件C.哈希文件D.多关键字文件2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.403、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表4、已知串S='aaab'，其next数组值为（）。

A.0123B.1123C.1231D.12115、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。

8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。

2022年中国农业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年中国农业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年中国农业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。

A.n*nB.n(n+1)C.n/2D.n*(n-1)2、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。

A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理3、静态链表中指针表示的是（）。

A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置D.左链或右链指向的元素的地址4、已知串S='aaab'，其next数组值为（）。

A.0123B.1123C.1231D.12115、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4507、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。

A．只有e B．有e、b C．有e、c D．无法确定8、有n（n>0）个分支结点的满二叉树的深度是（）。

A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）9、在下述结论中，正确的有（）。

①只有一个结点的二叉树的度为0。

②二叉树的度为2。

③二叉树的左右子树可任意交换。

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A.①②③B.⑦③④C.②④D.①④10、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

(完整版)数据结构课后习题答案(可编辑修改word版)

(完整版)数据结构课后习题答案(可编辑修改word版)

第1 章绪论1.简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，… }，字母字符数据对象是集合C={‘A’，‘B’，… ，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

2.试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。

每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。