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

《2023年数据结构概论在线作业与答案.docx》由会员分享，可在线阅读，更多相关《2023年数据结构概论在线作业与答案.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、福师数据结构概论在线作业一答案试卷总分:100测试时间一一、单选题（共25道试题，共50分。）.最大容量为n的循环队列，队尾指针是rear,队头是fro n t ,则队空的条件是（）A. （rear+1） MOD n= f r o n trear= f rontB. re a r+ 1 =f r ont（re a r1） MOD n =fron t满分：2 分2,由3个结点可以构造出多少种不同的有向树？（）A. 23B. 45满分：2 分.栈和队都是（）A.顺序存储的B.线性结构C.链式存储的D.非线性结构满分：2 分.下面叙述对的的是（）A.算法的执行效率与数据的存储结构无关B.算法的空间复

2、杂度是指算法程序中指令（或语句）的条数C.算法的有穷性是指算法必须能在执行有限个环节之后终止A.错误B.对的满分：2 分19 .对一棵二叉树进行层次遍历时，应借助于一个栈A.错误B.对的满分：2分20 .当待排序记录已经从小到大排序或者已经从大到小排序时,快速排序的执行时间最省。A. 错误B.对的满分：2分三、多选题（共5道试题，共10分。）1. 有关二叉树下列说法不对的的是（）A.二叉树的度为2B. 一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2满分：2分2. 下面关于求关键途径的说法对的的是（）oA.求关键途径是以拓扑排序为基础的B. .一个事

3、件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的连续时间 的差D.关键活动一定位于关键途径上满分：2分3. 下面关于二分查找的叙述不对的的是（）A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序，并且只能从小到大排列C.表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只能以顺序方式存储满分:2 分4. 下述哪些不是顺序存储结构的优点？（）A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表达满分：2 分5. 在下列情况中，不能为二叉树的是（）A.每个结点至

4、多有两棵子树的树B.哈夫曼树C.每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树满分:2分D.以上三种描述都不对满分：2 分5.对关键码序列28, 1 6,3 2, 12, 60, 2 , 5,72快速排序，从小到大一次划分结果为()。A.(2, 5, 12, 16)26 (6 0,32,72)B. (5,16,2,12)28 (60,32,7 2)C.(2,l 6,12,5) 2 8 (60,3 2,72)D. (5,16,2 , 12) 28 (3 2,6 0,72)满分:2 分6.设计一个判别表达式中左,右括号是否配对出现的算法，采用()数据结构最佳。A.线性表的顺序存储结构队列

5、C.线性表的链式存储结构D.栈满分：2分7.若串S= software,其子串的数目是()。A. 8B.37B. 36D.9满分：2分8.若用冒泡排序方法对序列10,1 4, 26,29,4 1 , 5 2 从大到小排序，需进行 ()次比 较。A. 31 0B. 15D.25满分：2 分9.若规定尽也许快地对序列进行稳定的排序，则应选()A.快速排序B.归并排序C.冒泡排序D.堆满分：2分1 0.假如规定一个线性表既能较快的查找，又能适应动态变化的规定，则可采用()查找法。A.分快查找B.顺序查找C.折半查找D.基于属性满分：2 分1 1 .广义表运算式Tail(a,b), (c,d)的操作结

6、果是()A. (c, d)c, dB. (c,d)d满分：2分.在下面的排序方法中，辅助空间为O(n)的是()A.希尔排序B.堆排序C.选择排序D.归并排序满分：2分.以下数据结构中()是非线性数据结构A.树B.字符串C.队D.栈满分:2 分1 4. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时 间复杂度()(1 =i=n+ 1 )o0(0)A. 0(1 )O (n)B. O (n2)满分：2 分15.设树T的度为4,其中度为1, 2, 3和4的结点个数分别为4, 2,1则T中的叶子 数为()A. 5B.6C. 7D.8满分：2分16. 散列函数有一个共同的性质，

7、即函数值应当以()取其值域的每个值。A. 最大约率B.最小概率C.平均概率D.同等概率满分：2 分.在下面的排序方法中，辅助空间为O (n)的是()A.希尔排序B.堆排序C.选择排序D.归并排序满分：2分.设森林F相应的二叉树为B,它有m个结点，B的根为p, P的右子树结点个数为n, 森林F中第一棵树的结点个数是()A. m- nm n -1B. n+ 1D.条件局限性，无法拟定满分：2分19.求解最短途径的F loyd算法的时间复杂度为()。A. O(n)O(n+c)B. 0 ( n *n)0 (n*n*n)满分：2分.下列排序算法中，占用辅助空间最多的是:()A.归并排序B.快速排序C.希

8、尔排序D.堆排序满分：2分.若二叉树采用二叉链表存储结构，要互换其所有分支结点左、右子树的位置，运用() 遍历方法最合适。A.前序B.中序C.后序D.按层次满分：2 分.输入序列为ABC,可以变为CB A 口寸，通过的栈操作为（）A. push,p o p ,pu s h ,pop, pu s h ,poppus h ,p u s h, p us h ,pop, p op, p opB. pus h , p u s h, pop, pop,pus h , poppush,pop, p u s h, p ush,po p , p op满分:2 分.设无向图的顶点个数为n,则该图最多有（）条边。A

9、. n-1n（n_ 1）/2B. n（n+l）/20满分：2 分.要连通具有n个顶点的有向图，至少需要（）条边。A. n-1nB. n+12n满分：2 分.具有12个关键字的有序表，折半查找的平均查找长度（）4B. 2.55 满分：2 分二、判断题（共20道试题，共40分。）.二叉树是度为2的有序树（）A.错误B.对的满分：2分.集合与线性表的区别在于是否按关键字排序。A.错误B.对的 满分：2分1 .队列逻辑上是一个下端和上端既能增长又能减少的线性表（）oA.错误B.对的 满分：2 分.顺序存储方式只能用于存储线性结构。A.错误B.对的 满分:2 分2 .采用二叉链表作存储结构，树的前序遍历

10、和其相应的二叉树的前序遍历的结果是同样的A.错误B.对的满分：2分二叉树的遍历结果不是唯一的（）A.错误B.对的满分：2分7. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（）A.错误B.对的满分：2分8. 队列逻辑上是一个下端和上端既能增长又能减少的线性表。A.错误B.对的满分：2 分线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。A.错误B.对的满分：2 分任一查找树（二叉分类树）的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间（）A.错误B.对的满分：2分1 1.排序的稳定性是指排序算法中的比较次数保持不变，且算法可以终止A.错误B.对的满

11、分：2分12.对任何数据结构链式存储结构一定优于顺序存储结构（）。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 . 二叉树以后序遍历序列与前序遍历序列反映的同样的信息（他们反映的信息不独立） （）