2023年数据结构概论在线作业与答案.pdf
福 师 数据结构概论在线作业一答案试卷总分:100 测试时间:-一、单选题（共2 5道试题，共 5 0 分。）1 .最大容量为n 的循环队列，队尾指针是rear,队头是fro n t,则队空的条件是（）A.（rear+1）MOD n=f r o n tB.rear=f rontC.re a r+1=f r ontD.（re a r1）MOD n=fron t满分：2 分2.由 3 个结点可以构造出多少种不同的有向树？（）A.2B.3C.4D.5满分：2 分3.栈和队都是（）A.顺序存储的B.线性结构C.链式存储的D.非线性结构满分：2 分4.下面叙述对的的是（）A.算法的执行效率与数据的存储结构无关B.算法的空间复杂度是指算法程序中指令（或语句）的条数C.算法的有穷性是指算法必须能在执行有限个环节之后终止D.以上三种描述都不对满分：2 分5 .对关键码序列2 8,1 6,3 2,1 2,6 0,2 ,5,7 2 快速排序，从小到大一次划分结果为()。A.(2,5,1 2,1 6)2 6 (6 0,3 2,7 2)B.(5,1 6,2,1 2)2 8 (6 0,3 2,7 2)C.(2,l 6 ,1 2,5)2 8 (6 0,3 2 ,7 2)D.(5,1 6,2 ,1 2)2 8(3 2 ,6 0,7 2)满分:2分6 .设计一个判别表达式中左,右括号是否配对出现的算法，采 用()数据结构最佳。A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈满分：2 分7.若串S=s o f t wa r e 淇子串的数目是()。A.8B.3 7C.3 6D.9满分：2 分8.若用冒泡排序方法对序列 1 0,1 4,2 6,2 9,4 1 ,5 2 从大到小排序，需进行()次比较。A.3B.1 0C.1 5D.2 5满分：2 分9.若规定尽也许快地对序列进行稳定的排序，则 应 选()A.快速排序B.归并排序C.冒泡排序D.堆满分：2分1 0.假如规定一个线性表既能较快的查找，又能适应动态变化的规定，则可采用()查找法。A.分快查找B.顺序查找C.折半查找D.基于属性满分：2分1 1.广义表运算式Tail(a,b),(c,d)的操作结果是()A.(c,d)B.c,dC.(c,d)D.d满分：2分12.在下面的排序方法中，辅助空间为O(n)的 是()A.希尔排序B.堆排序C.选择排序D.归并排序满分：2分13.以下数据结构中()是非线性数据结构A.树B.字符串C.队D.栈满分:2 分1 4.若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间 复 杂 度()(1=i=n+1)。A.0(0)B.0(1)C.0 (n)D.0 (n2)满分：2 分1 5.设树T 的度为4,其中度为1,2,3 和 4 的结点个数分别为4,2,1,1 则 T 中的叶子数 为()A.5B.6C.7D.8满分：2分16.散列函数有一个共同的性质，即函数值应当以()取其值域的每个值。A.最大约率B.最小概率C.平均概率D.同等概率满分：2 分1 7.在下面的排序方法中，辅助空间为0 (n)的是()A.希尔排序B.堆排序C.选择排序D.归并排序满分：2分1 8.设森林F 相应的二叉树为B,它有m 个结点，B 的根为p,P 的右子树结点个数为n,森林F 中第一棵树的结点个数是()A.m-nB.m-n-1C.n+1D.条件局限性，无法拟定满分：2分1 9.求解最短途径的F 1 oyd算法的时间复杂度为()。A.0(n)B.O(n+c)C.0(n*n)D.O(n*n*n)满分：2分20.下列排序算法中，占用辅助空间最多的是:()A.归并排序B.快速排序C.希尔排序D.堆排序满分：2分21.若二叉树采用二叉链表存储结构，要互换其所有分支结点左、右子树的位置，运用()遍历方法最合适。A.前序B.中序C.后序D.按层次满分：2 分22.输入序列为ABC,可以变为CBA时，通过的栈操作为（）A.push,p o p,pu s h,pop,pu s h,popB.pus h,p u s h,p us h,pop,p op,p opC.pus h,p u s h,pop,pop,pus h,popD.push,pop,p u s h,p ush,po p,p op满分:2 分23.设无向图的顶点个数为n,则该图最多有（）条边。A.n-1B.n（n1）/2C.n（n+l）/2D.0满分：2 分24.要连通具有n 个顶点的有向图，至少需要（）条边。A.n-1B.nC.n+1D.2n满分：2 分25.具 有 1 2 个关键字的有序表，折半查找的平均查找长度（）A.3.1B.4C.2.5D.5满分：2 分二、判 断 题（共 20道试题，共 40分。）1 .二叉树是度为2的有序树（）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 分1 0 .任一查找树（二叉分类树）的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间（）A.错误B.对的满分：2 分1 1.排序的稳定性是指排序算法中的比较次数保持不变，且算法可以终止A.错误B.对的满分：2 分1 2.对任何数据结构链式存储结构一定优于顺序存储结构（）。A.错误B.对的满分：2 分1 3 .用一维数组存储二叉树时，总是以前序遍历顺序存储结点。A.错误B.对的满分:2 分1 4 .顺序查找法合用于存储结构为顺序或链接存储的线性表（）A.错误B.对的满分：2 分15.当待排序的元素很大时，为了互换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的重要因素A.错误B.对的满分：2 分1 6.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。A.错误B.对的满分：2 分17.广义表中的元素或者是一个不可分割的原子,或者是一个非空的广义表。A.错误B.对的满分:2 分1 8 .二叉树以后序遍历序列与前序遍历序列反映的同样的信息（他们反映的信息不独立）()A.错误B.对的满分:2 分1 9 .对一棵二叉树进行层次遍历时，应借助于一个栈A.错误B.对的满分：2分2 0 .当待排序记录己经从小到大排序或者已经从大到小排序时,快速排序的执行时间最省。A.错误B.对的满分：2分三、多 选 题（共5道试题，共1 0分。）1.有关二叉树下列说法不对的的是（）A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2满分：2分2.下面关于求关键途径的说法对的的是（）。A.求关键途径是以拓扑排序为基础的B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的连续时间的差D.关键活动一定位于关键途径上满分：2分3.下面关于二分查找的叙述不对的的是（）A.表必须有序，表可以顺序方式存储,也可以链表方式存储B.表必须有序，并且只能从小到大排列C.表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只能以顺序方式存储满分:2 分4.下述哪些不是顺序存储结构的优点？（）A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表达满分：2 分5.在下列情况中，不能为二叉树的是（）A.每个结点至多有两棵子树的树B.哈夫曼树C.每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树满分:2 分
