福师15春《数据结构概论》在线作业答案
福师15春《数据结构概论》在线作业二一、单选题【共25道,总分:50分】
1.字符串‘ababaabab’ 的nextval 为( )
1)B.(0,1,0,1,0,2,1,0,1)C.(0,1,0,1,0,0,0,1,1)D.(0,1,0,1,0,1,0,1,1 )满分：2分 2.下列排序算法中( )算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。
A.(0,1,0,1,04,1,0,A. 堆排序
B. 冒泡排序
C. 快速排序
D. 插入排序
3.连续存储设计时，存储单元的地址（
A. 一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
4.动态存储管理系统中，通常可有( )种不同的分配策略。
A. 1
B. 2
C. 3
D. 4
5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( )
A. 9
B. 11
C. 15
D. 不确定
6.线性表（ a1,a2an）以链接方式存储时，访问第i位置元素的时间复杂性为( )
A. O（i）
B. O（1）
C. O（n）
D. O（i-1
7.下面给出的四种排序法中( )排序法是不稳定性排序法。
A. 插入
B. 冒泡
C. 二路归并
D. 堆
8.求解最短路径的Floyd算法的时间复杂度为( )。
A. O（n）
B. O（n+c）
C. O（n*n）
D. O（n*n*n
9.广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（Head(Tail(Head(Tail(Tail(A)))))
A. （a）
B. A
C. a
D. d
10.广义表a,b,c,d的表头是（ 表尾是（
A. a
B.
C. （a,b,c,d）
D. （b,c,d
11.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为( )
A. 求子串
B. 联接
C. 匹配
D. 求串长
12.一个算法应该是（
A. 程序
B. 问题求解步骤的描述
C. 要满足五个基本特性
D. A和
C.
13.栈和队列的共同点是（
A. 都是先进先出
B. 都是先进后出
C. 只允许在端点处插入和删除元素
D. 没有共同点
E. 限制存取点的线性结构
F. 限制存取点的非线性结构
14.图中有关路径的定义是( )
A. 由顶点和相邻顶点序偶构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
15.下面的程序段中，对x的赋值语句的频度为( )FOR i:=1 TO n DOFOR j:=1 TO n DO x:=x+1;
2)D. O(log2n)满分：2分 16.串的长度是指( )
A. O(2n)
B. O(n)
C. O(nA. 串中所含不同字母的个数
B. 串中所含字符的个数
C. 串中所含不同字符的个数
D. 串中所含非空格字符的个数
17.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为( )
A. 5
B. 6
C. 7
D. 8
18.就平均性能而言，目前最好的内部排序方法是( )排序法。
A. 冒泡
B. 希尔插入
C. 交换
D. 快速
19.在一棵二叉树上第5层的结点数最多是( )
A. 8
B. 16
C. 32
D. 15
20.散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。
A. 最大概率
B. 最小概率
C. 平均概率
D. 同等概率
21.树的后根遍历序列等同于该树对应的二叉树的( ).
A. 先序序列
B. 中序序列
C. 后序序列
D. 都不正确
22.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( )
A. 选择排序法
B. 插入排序法
C. 快速排序法
D. 堆积排序法
23.线索二叉树是一种( )结构。
A. 逻辑
B. 逻辑和存储
C. 物理
D. 线性
24.下面关于算法说法错误的是( )
A. 算法最终必须由计算机程序实现
B. 为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性
D. 以上几个都是错误的
25.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。
A. 插入
B. 选择
C. 希尔
D. 二路归并
二、判断题【共20道,总分:40分】
1.在顺序存储结构中，有时也存储数据结构中元素之间的关系( )
A. 错误 B. 正确
2.直接选择排序算法在最好情况下的时间复杂度为O（N
A. 错误 B. 正确
3.队列逻辑上是一个下端和上端既能增加又能减少的线性表。
A. 错误 B. 正确
4.循环队列也存在空间溢出问题。
A. 错误 B. 正确
5.在顺序存储结构中，有时也存储数据结构中元素之间的关系。
A. 错误 B. 正确
6.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。
A. 错误 B. 正确
7.若一个广义表的表头为空表，则此广义表亦为空表( )
A. 错误 B. 正确
8.对无序表用二分法查找比顺序查找快( )
A. 错误 B. 正确
9.直接选择排序算法在最好情况下的时间复杂度为O（N ）
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. 正确
三、多选题【共5道,总分:10分】
1.下面关于线性表的叙述中，正确的是 ）
A. 线性表采用顺序存储，必须占用一片连续的存储单元。
B. 线性表采用顺序存储，便于进行插入和删除操作。
C. 线性表采用链接存储，不必占用一片连续的存储单元。
D. 线性表采用链接存储，便于插入和删除操作
2.下列关于m阶B-树的说法正确的是( )
A. 根结点至多有m棵子树
B. 所有叶子都在同一层次上
C. 非叶结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树
D. 根结点中的数据是有序的
3.下面关于二分查找的叙述不正确的是( )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序，而且只能从小到大排列
C. 表必须有序且表中数据必须是整型，实型或字符型
D. 表必须有序，且表只能以顺序方式存储
4.有关二叉树下列说法不正确的是( )
A. 二叉树的度为2
B. 一棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
5.下面几个符号串编码集合中，是前缀编码的是( )
A. {0,10,110,1111}
B. {11,10,001,101,0001}
C. {00,010,0110,1000}
D. {b,c,aa,ac,aba,abb,abc
页:
[1]