2015福师《数据结构概论》在线作业二92分

一、单选题（共25道试题，共50分。）V1.字符串‘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分2.下列排序算法中（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。A.堆排序B.冒泡排序C.快速排序D.插入排序满分：2分3.连续存储设计时，存储单元的地址（）。A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续满分：2分4.动态存储管理系统中，通常可有（）种不同的分配策略。A.1B.2C.3D.4满分：2分5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A.9B.11C.15D.不确定满分：2分6.线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A.O（i）B.O（1）C.O（n）D.O（i-1）满分：2分7.下面给出的四种排序法中（）排序法是不稳定性排序法。A.插入B.冒泡C.二路归并D.堆满分：2分8.求解最短路径的Floyd算法的时间复杂度为()。A.O（n）B.O（n+c）C.O（n*n）D.O（n*n*n）满分：2分9.广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（）。Head(Tail(Head(Tail(Tail(A)))))A.（a）B.AC.aD.d满分：2分10.广义表（（a,b,c,d））的表头是（），表尾是（）。A.aB.（）C.（a,b,c,d）D.（b,c,d）满分：2分11.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A.求子串B.联接C.匹配D.求串长满分：2分12.一个算法应该是（）。A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A和C.满分：2分13.栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点E.限制存取点的线性结构F.限制存取点的非线性结构满分：2分14.图中有关路径的定义是（）A.由顶点和相邻顶点序偶构成的边所形成的序列B.由不同顶点所形成的序列C.由不同边所形成的序列D.上述定义都不是满分：2分15.下面的程序段中，对x的赋值语句的频度为（）FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A.O(2n)B.O(n)C.O(n2)D.O(log2n)满分：2分16.串的长度是指（）A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数满分：2分17.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A.5B.6C.7D.8满分：2分18.就平均性能而言，目前最好的内部排序方法是（）排序法。A.冒泡B.希尔插入C.交换D.快速满分：2分19.在一棵二叉树上第5层的结点数最多是（）A.8B.16C.32D.15满分：2分20.散列函数有一个共同的性质，即函数值应当以()取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率满分：2分21.树的后根遍历序列等同于该树对应的二叉树的().A.先序序列B.中序序列C.后序序列D.都不正确满分：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分。）V1.在顺序存储结构中，有时也存储数据结构中元素之间的关系（）A.错误B.正确满分：2分2.直接选择排序算法在最好情况下的时间复杂度为O（N）。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.直接选择排序算法在最好情况下的时间复杂度为O（N）（）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分。）V1.下面关于线性表的叙述中，正确的是？（）A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。满分：2分2.下列关于m阶B-树的说法正确的是()A.根结点至多有m棵子树B.所有叶子都在同一层次上C.非叶结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树D.根结点中的数据是有序的满分：2分3.下面关于二分查找的叙述不正确的是（）A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序，而且只能从小到大排列C.表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只能以顺序方式存储满分：2分4.有关二叉树下列说法不正确的是（）A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2满分：2分5.下面几个符号串编码集合中，是前缀编码的是（）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分