2023年数据结构概论在线作业与答案

福师《数据结构概论》在线作业一答案试卷总分:100测试时间:--一、单选题(共２5道试题，共50分。）１.最大容量为ｎ的循环队列,队尾指针是ｒear,队头是froｎｔ，则队空的条件是（）A.（rear＋1)ＭOＤｎ=ｆrｏｎｔB.rear＝ｆrontC.reａr+１=fｒontD.（reａr－l)MODｎ＝fronｔ满分：２分2.由3个结点可以构造出多少种不同的有向树?（）A.2Ｂ．３Ｃ.４D.５满分：２分3.栈和队都是()A.顺序存储的B.线性结构C.链式存储的D.非线性结构满分：2分4．下面叙述对的的是（）A.算法的执行效率与数据的存储结构无关B.算法的空间复杂度是指算法程序中指令（或语句）的条数C.算法的有穷性是指算法必须能在执行有限个环节之后终止Ｄ.以上三种描述都不对满分：2分5.对关键码序列2８，１6,3２，12，60,２，5,72快速排序，从小到大一次划分结果为（)。Ａ.(2，5，12，16)26（6０,32,72)Ｂ.（5,16,２,12)28（60,32,７2)Ｃ.(2,1６,12,5)２８(60,3２,72)D.(5,16,２，12）2８(３２,6０,７2)满分:２分6．设计一个判别表达式中左,右括号是否配对出现的算法,采用（)数据结构最佳。A．线性表的顺序存储结构B．队列C．线性表的链式存储结构D.栈满分:2分7.若串S＝’softwaｒe’,其子串的数目是（)。A.8Ｂ.37C.36D.9满分:2分8.若用冒泡排序方法对序列{10,１4，26,29,４１，5２｝从大到小排序,需进行（)次比较。A．3B．１0C.15Ｄ.25满分:2分9．若规定尽也许快地对序列进行稳定的排序,则应选()A.快速排序B.归并排序Ｃ．冒泡排序D.堆满分:2分１0.假如规定一个线性表既能较快的查找，又能适应动态变化的规定，则可采用()查找法。A．分快查找Ｂ.顺序查找C.折半查找D.基于属性满分：２分1１．广义表运算式Ｔail(((ａ,b)，(c,d）））的操作结果是()A．(c，d)B.c,ｄC.((c,d）)Ｄ．ｄ满分：2分12.在下面的排序方法中,辅助空间为Ｏ(n)的是（）Ａ．希尔排序B．堆排序C.选择排序D．归并排序满分:2分13.以下数据结构中(）是非线性数据结构A.树B.字符串C．队Ｄ.栈满分:２分１4．若长度为ｎ的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度()(１<=i<=n+１)。A．O(0)B.O(１）C.O（n)D.O（n2）满分：２分15.设树T的度为４，其中度为1，2，3和4的结点个数分别为4，２,1,1则T中的叶子数为（）A.5B.6C.7Ｄ.8满分:2分16．散列函数有一个共同的性质,即函数值应当以()取其值域的每个值。A．最大约率B.最小概率C.平均概率D.同等概率满分：2分17.在下面的排序方法中，辅助空间为O（n)的是()A.希尔排序B.堆排序Ｃ.选择排序D.归并排序满分:2分18.设森林F相应的二叉树为Ｂ，它有m个结点，B的根为p，ｐ的右子树结点个数为ｎ,森林F中第一棵树的结点个数是（)A.ｍ-ｎB.m－ｎ-1C.n+１D.条件局限性,无法拟定满分：2分19.求解最短途径的Ｆｌoyd算法的时间复杂度为(）。Ａ.O(n)B．O(n+c）C.Ｏ（ｎ＊n）D．O（n*n*n）满分：2分20．下列排序算法中，占用辅助空间最多的是:(）A.归并排序B．快速排序C.希尔排序D．堆排序满分：2分21.若二叉树采用二叉链表存储结构，要互换其所有分支结点左、右子树的位置，运用(）遍历方法最合适。A.前序Ｂ.中序C．后序D.按层次满分：２分22.输入序列为ABC,可以变为CBＡ时，通过的栈操作为(）A.push,pｏｐ,puｓｈ,pop，puｓｈ,popB.pusｈ,pｕｓh,ｐusｈ,pop,ｐop,ｐopC.pusｈ,ｐｕｓh，pop，pop,pusｈ，popＤ.push,pop，pｕｓh,ｐush,poｐ，ｐop满分:２分23．设无向图的顶点个数为n,则该图最多有（）条边。A．n-1Ｂ.n(n－1)／2C.n(n+1)/２D.0满分：２分24．要连通具有n个顶点的有向图,至少需要()条边。A．n-lＢ.nC.n+lD.2n满分：2分25.具有１2个关键字的有序表,折半查找的平均查找长度（）Ａ.3.1B.４C．２.5Ｄ．5满分：2分二、判断题（共20道试题，共40分。)1.二叉树是度为2的有序树()A.错误B．对的满分：2分2.集合与线性表的区别在于是否按关键字排序。Ａ.错误B.对的满分:2分3.队列逻辑上是一个下端和上端既能增长又能减少的线性表(）。A.错误Ｂ.对的满分：２分4.顺序存储方式只能用于存储线性结构。A.错误B.对的满分:２分5.采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是同样的Ａ.错误B.对的满分：2分６．二叉树的遍历结果不是唯一的（)A.错误B.对的满分：２分７．线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的（）Ａ.错误Ｂ.对的满分:2分８．队列逻辑上是一个下端和上端既能增长又能减少的线性表。A.错误B.对的满分:2分9.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。A.错误Ｂ.对的满分:2分10．任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间(）A．错误B.对的满分:2分１1.排序的稳定性是指排序算法中的比较次数保持不变,且算法可以终止A.错误B．对的满分：2分12．对任何数据结构链式存储结构一定优于顺序存储结构（)。Ａ．错误B.对的满分:2分1３.用一维数组存储二叉树时,总是以前序遍历顺序存储结点。A.错误B.对的满分:２分1４．顺序查找法合用于存储结构为顺序或链接存储的线性表(）Ａ.错误B.对的满分：2分1５.当待排序的元素很大时,为了互换元素的位置，移动元素要占用较多的时间,这是影响时间复杂度的重要因素A.错误B.对的满分:2分１6.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动,则该算法是不稳定的。Ａ.错误Ｂ.对的满分:2分1７.广义表中的元素或者是一个不可分割的原子,或者是一个非空的广义表。Ａ.错误B.对的满分:２分1８．二叉树以后序遍历序列与前序遍历序列反映的同样的信息（他们反映的信息不独立)（）A．错误B.对的满分:2分19．对一棵二叉树进行层次遍历时，应借助于一个栈A．错误B.对的满分:2分20.当待排序记录已经从小到大排序或者已经从大到小排序时,快速排序的执行时间最省。Ａ．错误Ｂ．对的满分:2分三、多选题（共5道试题,共1０分。)1．有关二叉树下列说法不对的的是()A.二叉树的度为2B.一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2Ｄ.二叉树中任何一个结点的度都为2满分:2分2．下面关于求关键途径的说法对的的是（）。A.求关键途径是以拓扑排序为基础的B..一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的连续时间的差D．关键活动一定位于关键途径上满分:2分3．下面关于二分查找的叙述不对的的是()A.表必须有序,表可以顺序方式存储,也可以链表方式存储B.表必须有序,并且只能从小到大排列C.表必须有序且表中数据必须是整型，实型或字符型D．表必须有序