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

2017秋福师《数据结构概论》在线作业二试卷总分:100得分:100一、单选题(共25道试题,共50分)1.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（）A.选择排序法B.插入排序法C.快速排序法D.堆积排序法满分：2分正确答案:A2.数组A[0..4,-1..-3,5..7]中含有元素的个数（）A.55B.45C.36D.16满分：2分正确答案:B3.下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序A.冒泡B.希尔C.快速D.堆满分：2分正确答案:C4.如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用()查找法。A.分快查找B.顺序查找C.折半查找D.基于属性满分：2分正确答案:A5.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A.m-nB.m-n-1C.n+1D.条件不足，无法确定满分：2分正确答案:A6.对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。A.选择B.快速C.希尔D.冒泡满分：2分正确答案:C7.若串S=’software’,其子串的数目是（）A.8B.37C.36D.9满分：2分正确答案:B8.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。()A.选择排序法B.插入排序法C.快速排序法D.堆积排序法满分：2分正确答案:A9.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A.head==NULLB.head→next==NULLC.head→next==headD.head!=NULL满分：2分正确答案:B10.具有12个关键字的有序表，折半查找的平均查找长度（）A.3.1B.4C.2.5D.5满分：2分正确答案:A11.已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（）。A.head（tail（tail（L）））B.tail（head（head（tail（L））））C.head（tail（head（tail（L））））D.head（tail(head（tail（tail（L）））)）满分：2分正确答案:D12.对于栈操作数据的原则是（）A.先进先出B.后进先出C.后进后出D.不分顺序满分：2分正确答案:B13.关键路径是事件结点网络中（）A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长回路D.最短回路满分：2分正确答案:A14.散列函数有一个共同的性质，即函数值应当以（）取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率满分：2分正确答案:D15.假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。A.808B.818C.1010D.1020满分：2分正确答案:B16.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A.13B.33C.18D.40满分：2分正确答案:B17.在单链表指针为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分正确答案:B18.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.234156满分：2分正确答案:C19.在下列存储形式中，哪一个不是树的存储形式（）A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法满分：2分正确答案:D20.设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈满分：2分正确答案:D21.一个算法应该是（）A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A和C.满分：2分正确答案:B22.具有10个叶结点的二叉树中有（）个度为2的结点，A.8B.9C.10D.ll满分：2分正确答案:B23.若串S=’software’,其子串的数目是（）。A.8B.37C.36D.9满分：2分正确答案:B24.数组A[0..4,-1..-3,5..7]中含有元素的个数（）。A.55B.45C.36D.16满分：2分正确答案:B25.设广义表L=（（a,b,c）），则L的长度和深度分别为（）A.1和1B.1和3C.1和2D.2和3满分：2分正确答案:C二、判断题(共20道试题,共40分)1.二叉树是度为2的有序树A.错误B.正确满分：2分正确答案:A2.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表（）A.错误B.正确满分：2分正确答案:A3.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的（）A.错误B.正确满分：2分正确答案:A4.用树的前序遍历和中序遍历可以导出树的后序遍历（）A.错误B.正确满分：2分正确答案:A5.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大A.错误B.正确满分：2分正确答案:A6.栈与队列是一种特殊操作的线性表（）A.错误B.正确满分：2分正确答案:B7.队列和栈都是运算受限的线性表，只允许在表的两端进行运算。A.错误B.正确满分：2分正确答案:A8.二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）。A.错误B.正确满分：2分正确答案:B9.任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间.A.错误B.正确满分：2分正确答案:A10.在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面（）A.错误B.正确满分：2分正确答案:A11.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。A.错误B.正确满分：2分正确答案:B12.当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省（）。A.错误B.正确满分：2分正确答案:A13.顺序存储方式只能用于存储线性结构。A.错误B.正确满分：2分正确答案:A14.顺序存储结构的主要缺点是不利于插入或删除操作（）A.错误B.正确满分：2分正确答案:B15.广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值（）A.错误B.正确满分：2分正确答案:A16.链表中的头结点仅起到标识的作用。A.错误B.正确满分：2分正确答案:A17.数据元素是数据的最小单位。A.错误B.正确满分：2分正确答案:A18.折半查找法的查找速度一定比顺序查找法快（）A.错误B.正确满分：2分正确答案:A19.二维以上的数组其实是一种特殊的广义表（）A.错误B.正确满分：2分正确答案:B20.队列和栈都是运算受限的线性表，只允许在表的两端进行运算（）。A.错误B.正确满分：2分正确答案:A三、多选题(共5道试题,共10分)1.下面关于二分查找的叙述不正确的是()A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序，而且只能从小到大排列C.表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只能以顺序方式存储满分：2分正确答案:ABC2.下面关于线性表的叙述中，正确的是？（）A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。满分：2分正确答案:ACD3.下面几个符号串编码集合中，是前缀编码的是（）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分正确答案:ACD4.以下数据结构中，哪些不是线性结构（）A.广义表B.二叉树C.稀疏矩阵D.串满分：2分正确答案:ABC5.下面关于求关键路径的说法正确的是（）A.求关键路径是以拓扑排序为基础的B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D.关键活动一定位于关键路径上满分：2分正确答案:ABD