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

谋学网福师《数据结构概论》在线作业一一、单选题（共25道试题，共50分。）1.下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。.堆排序.冒泡排序.快速排序.插入排序正确答案：2.以下数据结构中，（）是非线性数据结构.树.字符串.队.栈正确答案：3.线性表（1,2,…,n）以链接方式存储时，访问第i位置元素的时间复杂性为（）.O（i）.O（1）.O（n）.O（i-1）正确答案：4.设给定权值总数有n个，其哈夫曼树的结点总数为（）.不确定.2n.2n+1.2n-1正确答案：5.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。.插入.选择.希尔.二路归并正确答案：6.就平均性能而言，目前最好的内排序方法是()排序法。.冒泡.希尔插入谋学网交换.快速正确答案：7.对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（）。.(2,5,12,16)26(60,32,72).(5,16,2,12)28(60,32,72).(2,16,12,5)28(60,32,72).(5,16,2,12)28(32,60,72)正确答案：8.适用于折半查找的表的存储方式及元素排列要求为().链接方式存储，元素无序.链接方式存储，元素有序.顺序方式存储，元素无序.顺序方式存储，元素有序正确答案：9.线索二叉树是一种（）构。.逻辑.逻辑和存储.物理.线性正确答案：10.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。.O(n)O(n).O(n)O(1).O(1)O(n).O(1)O(1)正确答案：11.若串S=’softwr’,其子串的数目是（）.8.37.36.9正确答案：12.要连通具有n个顶点的有向图，至少需要（）条边。.n-l.n.n+l.2n正确答案：13.已知串S=‘’,其Nxt数组值为（）.0123.1123.1231谋学网正确答案：14.在下面的程序段中，对x的赋值语句的频度为（）FORi:=1TOnOFORj:=1TOnOx:=x+1;.O(2n).O(n).O(n2).O(log2n)正确答案：15.设森林F对应的二叉树为，它有m个结点，的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）.m-n.m-n-1.n+1.条件不足，无法确定正确答案：16.线索二叉树是一种（）结构。.逻辑.逻辑和存储.物理.线性正确答案：17.串的长度是指（）.串中所含不同字母的个数.串中所含字符的个数.串中所含不同字符的个数.串中所含非空格字符的个数正确答案：18.已知广义表L=（（x,y,z），，（u，t，w）），从L表中取出原子项t的运算是（）.h（til（til（L）））.til（h（h（til（L））））.h（til（h（til（L））））.h（til(h（til（til（L）））)）正确答案：19.一个递归算法必须包括（）.递归部分.终止条件和递归部分.迭代部分.终止条件和迭代部分正确答案：20.若串S=’softwr’,其子串的数目是（）。.8.37.36谋学网正确答案：21.对稀疏矩阵进行压缩存储目的是（）。.便于进行矩阵运算.便于输入和输出.节省存储空间.降低运算的时间复杂度正确答案：22.下列排序算法中，占用辅助空间最多的是：().归并排序.快速排序.希尔排序.堆排序正确答案：23.由3个结点可以构造出多少种不同的二叉树（）.2.3.4.5正确答案：24.输入序列为，可以变为时，经过的栈操作为（）.push,pop,push,pop,push,pop.push,push,push,pop,pop,pop.push,push,pop,pop,push,pop.push,pop,push,push,pop,pop正确答案：25.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（）(1=i=n+1)。.O(0).O(1).O(n).O(n2)正确答案：福师《数据结构概论》在线作业一二、判断题（共20道试题，共40分。）谋学网广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值（）.错误.正确正确答案：2.用树的前序遍历和中序遍历可以导出树的后序遍历（）.错误.正确正确答案：3.队列和栈都是运算受限的线性表，只允许在表的两端进行运算（）。.错误.正确正确答案：4.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（）.错误.正确正确答案：5.任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间..错误.正确正确答案：6.数据元素是数据的最小单位。.错误.正确正确答案：7.数据结构的抽象操作的定义与具体实现有关。.错误.正确正确答案：8.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表（）.错误.正确正确答案：9.线性表只能用顺序存储结构实现（）.错误.正确正确答案：10.在顺序存储结构中，有时也存储数据结构中元素之间的关系（）.错误.正确正确答案：11.循环队列通常用指针来实现队列的头尾相接。.错误谋学网正确正确答案：12.二叉树是度为2的有序树.错误.正确正确答案：13.在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面（）.错误.正确正确答案：14.队列逻辑上是一个下端和上端既能增加又能减少的线性表。.错误.正确正确答案：15.链表中的头结点仅起到标识的作用（）.错误.正确正确答案：16.栈和队列都是限制存取点的线性结构（）.错误.正确正确答案：17.链表中的头结点仅起到标识的作用。.错误.正确正确答案：18.二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）（）.错误.正确正确答案：19.对一棵二叉树进行层次遍历时，应借助于一个栈.错误.正确正确答案：20.广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。.错误.正确正确答案：福师《数据结构概论》在线作业一谋学网三、多选题（共5道试题，共10分。）1.以下数据结构中，哪些不是线性结构（）.广义表.二叉树.稀疏矩阵.串正确答案：2.下列说法正确的是（）.图的遍历是从给定的源点出发每一个顶点仅被访问一次.图的深度遍历不适用于有向图.遍历的基本算法有两种：深度遍历和广度遍历.图的深度遍历是一个递归过程正确答案：3.下面几个符号串编码集合中，是前缀编码的是（）.{0,10,110,1111}.{11,10,001,101,0001}.{00,010,0110,1000}.{,,,,,,}正确答案：4.下列哪种图的邻接矩阵不是对称矩阵？（）.有向图.无向图.OV网.O网正确答案：5.下面几个符号串编码集合中，是前缀编码的是（）.{0,10,110,1111}.{11,10,001,101,0001}.{00,010,0110,1000}.{,,,,,,}正确答案：谋学网