福师11秋《数据结构概论》在线作业二答案

福师《数据结构概论》在线作业二答案试卷总分：100测试时间：--一、单选题（共25道试题，共50分。）1.一个算法应该是（）。A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A和C.满分：2分2.下列排序算法中（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。A.堆排序B.冒泡排序C.快速排序D.插入排序满分：2分3.算法的时间复杂度是由（）决定的。A.问题的规模B.待处理数据的初态C.A和BD.变量个数满分：2分4.在用邻接表表示图时，拓扑排序算法时间复杂度为()。A.O(n)B.O(n＋e)C.O(n*n)D.O(n*n*n)满分：2分5.线索二叉树是一种（）结构。A.逻辑B.逻辑和存储C.物理D.线性满分：2分6.广义表（（a,b,c,d））的表头是（），表尾是（）。A.aB.（）C.（a,b,c,d）D.（b,c,d）满分：2分7.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）A.13B.33C.18D.40满分：2分8.在用邻接表表示图时，拓扑排序算法时间复杂度为（）A.O(n)B.O(n＋e)C.O(n*n)D.O(n*n*n)满分：2分9.从逻辑上可以把数据结构分为（）两大类A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构满分：2分10.字符串‘ababaabab’的nextval为（）A.(0,1,0,1,04,1,0,1)B.(0,1,0,1,0,2,1,0,1)C.(0,1,0,1,0,0,0,1,1)D.(0,1,0,1,0,1,0,1,1)满分：2分11.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。A.3B.10C.15D.25满分：2分12.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（）A.不确定B.n-i+1C.iD.n-i满分：2分13.线性表是具有n个（）的有限序列。A.表元素B.字符C.数据元素D.数据项满分：2分14.下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。A.堆排序B.冒泡排序C.快速排序D.插入排序满分：2分15.关键路径是事件结点网络中（）A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长回路D.最短回路满分：2分16.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。A.前序B.中序C.后序D.按层次满分：2分17.对于栈操作数据的原则是（）A.先进先出B.后进先出C.后进后出D.不分顺序满分：2分18.有n个叶子的哈夫曼树的结点总数为（）。A.不确定B.2nC.2n+1D.2n-1满分：2分19.若串S=’software’,其子串的数目是（）。A.8B.37C.36D.9满分：2分20.连续存储设计时，存储单元的地址（）A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续满分：2分21.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。A.p-next=s;s-next=p-next;B.s-next=p-next;p-next=s;C.p-next=s;p-next=s-next;D.p-next=s-next;p-next=s;满分：2分22.连续存储设计时，存储单元的地址（）。A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续满分：2分23.用二分（对半）查找表的元素的速度比用顺序法()A.必然快B.必然慢C.相等D.不能确定满分：2分24.散列函数有一个共同的性质，即函数值应当以（）取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率满分：2分25.一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分满分：2分二、判断题（共20道试题，共40分。）1.任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间.A.错误B.正确满分：2分2.任何一棵二叉树都可以不用栈实现前序线索树的前序遍历（）A.错误B.正确满分：2分3.当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素A.错误B.正确满分：2分4.通常使用队列来处理函数或过程的调用。A.错误B.正确满分：2分5.对无序表用二分法查找比顺序查找快（）A.错误B.正确满分：2分6.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表（）A.错误B.正确满分：2分7.顺序查找法适用于存储结构为顺序或链接存储的线性表（）A.错误B.正确满分：2分8.数据元素是数据的最小单位。A.错误B.正确满分：2分9.栈与队列是一种特殊操作的线性表（）A.错误B.正确满分：2分10.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大A.错误B.正确满分：2分11.消除递归不一定需要使用栈，此说法（）A.错误B.正确满分：2分12.广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值（）A.错误B.正确满分：2分13.对无序表用二分法查找比顺序查找快A.错误B.正确满分：2分14.任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间（）A.错误B.正确满分：2分15.广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。A.错误B.正确满分：2分16.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（）A.错误B.正确满分：2分17.排序算法中的比较次数与初始元素序列的排列无关。A.错误B.正确满分：2分18.对任何数据结构链式存储结构一定优于顺序存储结构（）。A.错误B.正确满分：2分19.两分法插入排序所需比较次数与待排序记录的初始排列状态相关（）A.错误B.正确满分：2分20.线性表的特点是每个元素都有一个前驱和一个后继。A.错误B.正确满分：2分三、多选题（共5道试题，共10分。）1.下面关于哈希(Hash)查找的说法不正确的是（）A.哈希函数构造的越复杂越好，因为这样随机性好，冲突小B.除留余数法是所有哈希函数中最好的C.不存在特别好与坏的哈希函数，要视情况而定D.若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可满分：2分2.在下列情况中，不能为二叉树的是（）A.每个结点至多有两棵子树的树B.哈夫曼树C.每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树满分：2分3.下面几个符号串编码集合中，是前缀编码的是（）A.{0,10,110,1111}B.{11,10,001,101,0001}C.{00,010,0110,1000}D.{b,c,aa,ac,aba,abb,abc}满分：2分4.下列关于m阶B-树的说法正确的是()A.根结点至多有m棵子树B.所有叶子都在同一层次上C.非叶结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树D.根结点中的数据是有序的满分：2分5.下列哪种图的邻接矩阵不是对称矩阵（）A.有向图B.无向图C.AOV网D.AOE网满分：2分