《数据结构概论》在线作业与答案

福师?数据结构概论?在线作业一答案试卷总分：100测试时间：--一、单项选择题〔共25道试题，共50分。〕1.最大容量为n的循环队列，队尾指针是rear，队头是front，那么队空的条件是〔〕A.(rear+1)MODn=frontB.rear=frontC.rear+1=frontD.(rear-l)MODn=front总分值：2分2.由3个结点可以构造出多少种不同的有向树？〔〕A.2B.3C.4D.5总分值：2分3.栈和队都是〔〕A.顺序存储的B.线性结构C.链式存储的D.非线性结构总分值：2分4.下面表达正确的选项是〔〕A.算法的执行效率与数据的存储结构无关B.算法的空间复杂度是指算法程序中指令(或语句)的条数C.算法的有穷性是指算法必须能在执行有限个步骤之后终止D.以上三种描述都不对总分值：2分5.对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为〔〕。A.(2,5,12,16)26(60,32,72)B.(5,16,2,12)28(60,32,72)C.(2,16,12,5)28(60,32,72)D.(5,16,2,12)28(32,60,72)总分值：2分6.设计一个判别表达式中左，右括号是否配对出现的算法，采用〔〕数据结构最正确。A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈总分值：2分7.假设串S=’software’,其子串的数目是〔〕。A.8B.37C.36D.9总分值：2分8.假设用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行〔〕次比拟。A.3B.10C.15D.25总分值：2分9.假设要求尽可能快地对序列进行稳定的排序，那么应选〔〕A.快速排序B.归并排序C.冒泡排序D.堆总分值：2分10.如果要求一个线性表既能较快的查找，又能适应动态变化的要求，那么可采用()查找法。A.分快查找B.顺序查找C.折半查找D.基于属性总分值：2分11.广义表运算式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分14.假设长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度〔〕(1<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)总分值：2分15.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1那么T中的叶子数为〔〕A.5B.6C.7D.8总分值：2分16.散列函数有一个共同的性质，即函数值应当以()取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率总分值：2分17.在下面的排序方法中，辅助空间为O〔n〕的是()A.希尔排序B.堆排序C.选择排序D.归并排序总分值：2分18.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是〔〕A.m-nB.m-n-1C.n+1D.条件缺乏，无法确定总分值：2分19.求解最短路径的Floyd算法的时间复杂度为()。A.O〔n〕B.O〔n+c〕C.O〔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,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop总分值：2分23.设无向图的顶点个数为n，那么该图最多有〔〕条边。A.n-1B.n(n-1)/2C.n(n+1)/2D.0总分值：2分24.要连通具有n个顶点的有向图，至少需要〔〕条边。A.n-lB.nC.n+lD.2n总分值：2分25.具有12个关键字的有序表，折半查找的平均查找长度〔〕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分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分。〕1.有关二叉树以下说法不正确的选项是〔〕A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2总分值：2分2.下面关于求关键路径的说法正确的选项是〔〕。A.求关键路径是以拓扑排序为根底的B.．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D.关键活动一定位于关键路径上总分值：2分3.下面关于二分查找的表达不正确的选项是〔〕A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序，而且只能从小到大排列C.表必须有序且表中数据必须是整型，实型或字符型D.表必须有序