福师11春学期《数据结构概论》在线作业一

一、单选题（共20道试题，共40分。）1.就平均性能而言，目前最好的内部排序方法是（）排序法。A.冒泡B.希尔插入C.交换D.快速2.从逻辑上可以把数据结构分为（）两大类A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构3.在完全二叉树中，若一个结点是叶结点，则它没（）A.左子结点B.右子结点C.左子结点和右子结点D.左子结点，右子结点和兄弟结点4.用二分（对半）查找表的元素的速度比用顺序法（）A.必然快B.必然慢C.相等D.不能确定5.算法的计算量的大小称为计算的（）A.效率B.复杂性C.现实性D.难度6.以下数据结构中（）是非线性数据结构A.树B.字符串C.队D.栈7.下面的程序段中，对x的赋值语句的频度为（）FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A.O(2n)B.O(n)C.O(n2)D.O(log2n)8.散列函数有一个共同的性质，即函数值应当以（）取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率9.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）A.(rear+1)MODn=frontB.rear=frontC.rear+1=frontD.(rear-l)MODn=front10.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。A.直接插入B.直接选择C.堆D.快速11.设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈12.设广义表L=（（a,b,c）），则L的长度和深度分别为（）A.1和1B.1和3C.1和2D.2和313.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（）A.不确定B.n-i+1C.iD.n-i14.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A.head==NULLB.head→next==NULLC.head→next==headD.head!=NULL15.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）A.13B.33C.18D.4016.求解最短路径的Floyd算法的时间复杂度为（）。A.O（n）B.O（n+c）C.O（n*n）D.O（n*n*n）17.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEG18.要连通具有n个顶点的有向图，至少需要（）条边。A.n-lB.nC.n+lD.2n19.由3个结点可以构造出多少种不同的二叉树（）A.2B.3C.4D.520.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。A.插入B.选择C.希尔D.二路归并二、判断题（共20道试题，共40分。）1.顺序查找法适用于存储结构为顺序或链接存储的线性表（）A.错误B.正确2.内部排序要求数据一定要以顺序方式存储（）A.错误B.正确3.消除递归不一定需要使用栈，此说法（）A.错误B.正确4.若一个广义表的表头为空表，则此广义表亦为空表（）A.错误B.正确5.两分法插入排序所需比较次数与待排序记录的初始排列状态相关（）A.错误B.正确6.顺序存储结构的主要缺点是不利于插入或删除操作（）A.错误B.正确7.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（）A.错误B.正确8.顺序存储方式只能用于存储线性结构（）A.错误B.正确9.折半查找法的查找速度一定比顺序查找法快（）A.错误B.正确10.栈是实现过程和函数等子程序所必需的结构（）A.错误B.正确11.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表（）A.错误B.正确12.采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的A.错误B.正确13.链表中的头结点仅起到标识的作用（）A.错误B.正确14.线性表的特点是每个元素都有一个前驱和一个后继（）A.错误B.正确15.当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素（）A.错误B.正确16.任何一棵二叉树都可以不用栈实现前序线索树的前序遍历（）A.错误B.正确17.在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面（）A.错误B.正确18.栈与队列是一种特殊操作的线性表（）A.错误B.正确19.用一维数组存储二叉树时，总是以前序遍历顺序存储结点（）A.错误B.正确20.二叉树的遍历结果不是唯一的（）A.错误B.正确三、判断题（共10道试题，共20分。）V1.二叉树是度为2的有序树（）A.错误B.正确2.队列和栈都是运算受限的线性表，只允许在表的两端进行运算（）。A.错误B.正确3.线性表只能用顺序存储结构实现（）A.错误B.正确4.算法的优劣与算法描述语言无关，但与所用计算机有关（）A.错误B.正确5.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的（）A.错误B.正确6.对无序表用二分法查找比顺序查找快（）A.错误B.正确7.栈和队列都是限制存取点的线性结构（）A.错误B.正确8.循环链表不是线性表（）A.错误B.正确9.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的（）A.错误B.正确10.在顺序存储结构中，有时也存储数据结构中元素之间的关系（）A.错误B.正确