福师12春《数据结构概论》在线作业答案
福师《数据结构概论》在线作业二试卷总分：100 测试时间：-- 试卷得分：100
一、单选题（共25道试题，共50分。）得分：50
1.若要求尽可能快地对序列进行稳定的排序，则应选（ ）
A. 快速排序
B. 归并排序
C. 冒泡排序
D. 堆
答案:
满分：2分得分：2
2.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）
A. （N+1）/2
B. N/2
C. N
D. [（1+N）*N ]/2
答案:
满分：2分得分：2
3.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
A. 9
B. 11
C. 15
D. 不确定
答案:
满分：2分得分：2
4.数组A中含有元素的个数（ ）
A. 55
B. 45
C. 36
D. 16
答案:
满分：2分得分：2
5.线性表是具有n个（ ）的有限序列。
A. 表元素
B. 字符
C. 数据元素
D. 数据项
答案:
满分：2分得分：2
6.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）
A. m-n
B. m-n-1
C. n+1
D. 条件不足，无法确定
答案:
满分：2分得分：2
7.在下列存储形式中，哪一个不是树的存储形式（ ）
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法
答案:
满分：2分得分：2
8.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）(1<=i<=n+1)。
A. O(0)
B. O(1)
C. O(n)
D. O(n2)
答案:
满分：2分得分：2
9.具有10个叶结点的二叉树中有（ ）个度为2的结点，
A. 8
B. 9
C. 10
D. ll
答案:
满分：2分得分：2
10.设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
A. 线性表的顺序存储结构
B. 队列
C. 线性表的链式存储结构
D. 栈
答案:
满分：2分得分：2
11.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A. 求子串
B. 联接
C. 匹配
D. 求串长
答案:
满分：2分得分：2
12.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A. 插入
B. 选择
C. 希尔
D. 二路归并
答案:
满分：2分得分：2
13.若串S=’software’,其子串的数目是（ ）
A. 8
B. 37
C. 36
D. 9
答案:
满分：2分得分：2
14.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）
A. (rear+1) MOD n=front
B. rear=front
C. rear+1=front
D. (rear-l) MOD n=front
答案:
满分：2得分：2
15.从逻辑上可以把数据结构分为（ ）两大类
A. 动态结构、静态结构
B. 顺序结构、链式结构
C. 线性结构、非线性结构
D. 初等结构、构造型结构
答案:
满分：2分得分：2
16.有n个叶子的哈夫曼树的结点总数为（ ）
A. 不确定
B. 2n
C. 2n+1
D. 2n-1
答案:
满分：2分得分：2
17.一个递归算法必须包括（ ）
A. 递归部分
B. 终止条件和递归部分
C. 迭代部分
D. 终止条件和迭代部分
答案:
满分：2分得分：2
18.在完全二叉树中，若一个结点是叶结点，则它没（ ）
A. 左子结点
B. 右子结点
C. 左子结点和右子结点
D. 左子结点，右子结点和兄弟结点
答案:
满分：2分得分：2
19.下面的程序段中，对x的赋值语句的频度为（ ）FOR i:=1 TO n DOFOR j:=1 TO n DO x:=x+1;
A. O(2n)
B. O(n)
C. O(n2)
D. O(log2n)
答案:
满分：2分得分：2
20.下列排序算法中，占用辅助空间最多的是（ ）
A. 归并排序
B. 快速排序
C. 希尔排序
D. 堆排序
答案:
满分：2分得分：2
21.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）
A. O（i）
B. O（1）
C. O（n）
D. O（i-1）
答案:
满分：2分得分：2
22.设给定权值总数有n 个，其哈夫曼树的结点总数为（ ）
A. 不确定
B. 2n
C. 2n+1
D. 2n-1
答案:
满分：2分得分：2
23.链表不具有的特点是（ ）
A. 插入、删除不需要移动元素
B. 可随机访问任一元素
C. 不必事先估计存储空间
D. 所需空间与线性长度成正比
答案:
满分：2分得分：2
24.适用于折半查找的表的存储方式及元素排列要求为（ ）
A. 链接方式存储，元素无序
B. 链接方式存储，元素有序
C. 顺序方式存储，元素无序
D. 顺序方式存储，元素有序
答案:
满分：2分得分：2
25.就平均性能而言，目前最好的内部排序方法是（ ）排序法。
A. 冒泡
B. 希尔插入
C. 交换
D. 快速
答案:
满分：2分得分：2
二、判断题（共20道试题，共40分。）得分：40
1.算法的优劣与算法描述语言无关，但与所用计算机有关（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
2.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构（ ）。
A. 错误
B. 正确
答案:A
满分：2分得分：2
3.通常使用队列来处理函数或过程的调用（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
4.顺序查找法适用于存储结构为顺序或链接存储的线性表（ ）
A. 错误
B. 正确
答案:B
满分：2分得分：2
5.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
6.健壮的算法不会因非法的输入数据而出现莫名其妙的状态（ ）。
A. 错误
B. 正确
答案:B
满分：2分得分：2
7.任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
8.栈和队列都是限制存取点的线性结构（ ）
A. 错误
B. 正确
答案:B
满分：2分得分：2
9.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
10.排序算法中的比较次数与初始元素序列的排列无关（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
11.顺序存储方式只能用于存储线性结构（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
12.循环队列通常用指针来实现队列的头尾相接（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
13.二叉树的遍历结果不是唯一的（ ）
A. 错误
B. 正确
答案:B
满分：2分得分：2
14.对任何数据结构链式存储结构一定优于顺序存储结构（ ）。
A. 错误
B. 正确
答案:A
满分：2分得分：2
15.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（ ）
A. 错误
B. 正确
答案:B
满分：2分得分：2
16.两分法插入排序所需比较次数与待排序记录的初始排列状态相关（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
17.在顺序存储结构中，有时也存储数据结构中元素之间的关系（ ）
A. 错误
B. 正确
答案:
满分：2分得分：2
18.若一个广义表的表头为空表，则此广义表亦为空表（ ）
A. 错误
B. 正确
答案:
满分：2分得分：2
19.用一维数组存储二叉树时，总是以前序遍历顺序存储结点（ ）
A. 错误
B. 正确
答案:
满分：2分得分：2
20.内部排序要求数据一定要以顺序方式存储（ ）
A. 错误
B. 正确
答案:
满分：2分得分：2
三、多选题（共5道试题，共10分。）得分：10
1.下面关于哈希(Hash)查找的说法不正确的是（ ）
A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B. 除留余数法是所有哈希函数中最好的
C. 不存在特别好与坏的哈希函数，要视情况而定
D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
答案:
满分：2分得分：2
2.有关二叉树下列说法不正确的是（ ）
A. 二叉树的度为2
B. 一棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
答案:
满分：2分得分：2
3.下列说法正确的是（ ）
A. 图的遍历是从给定的源点出发每一个顶点仅被访问一次
B. 图的深度遍历不适用于有向图
C. 遍历的基本算法有两种：深度遍历和广度遍历
D. 图的深度遍历是一个递归过程
答案:
满分：2分得分：2
4.在下列情况中，不能为二叉树的是（ ）
A. 每个结点至多有两棵子树的树
B. 哈夫曼树
C. 每个结点至多有两棵子树的有序树
D. 每个结点只有一棵右子树
答案:
满分：2分得分：2
5.下面关于串的的叙述中，正确的是（ ）
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
答案:
满分：2分得分：2
福师《数据结构概论》在线作业一
试卷总分：100 测试时间：-- 试卷得分：100
一、单选题（共25道试题，共50分。）得分：50
1.图中有关路径的定义是（ ）
A. 由顶点和相邻顶点序偶构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
答案:
满分：2分得分：2
2.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）(1<=i<=n+1)。
A. O(0)
B. O(1)
C. O(n)
D. O(n2)
答案:
满分：2分得分：2
3.下面给出的四种排序法中（ ）排序法是不稳定性排序法。
A. 插入
B. 冒泡
C. 二路归并
D. 堆
答案:D
满分：2分得分：2
4.链表不具有的特点是（ ）
A. 插入、删除不需要移动元素
B. 可随机访问任一元素
C. 不必事先估计存储空间
D. 所需空间与线性长度成正比
答案:
满分：2分得分：2
5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
A. 9
B. 11
C. 15
D. 不确定
答案:B
满分：2分得分：2
6.栈和队都是（ ）
A. 顺序存储的
B. 线性结构
C. 链式存储的
D. 非线性结构
答案:
满分：2分得分：2
7.连续存储设计时，存储单元的地址（ ）
A. 一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
答案:A
满分：2分得分：2
8.下面有关算法说法错误的是（ ）
A. 算法最终必须由计算机程序实现
B. 为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性
D. 以上几个都是错误的
答案:
满分：2分得分：2
9.关键路径是事件结点网络中（ ）
A. 从源点到汇点的最长路径
B. 从源点到汇点的最短路径
C. 最长回路
D. 最短回路
答案:A
满分：2分得分：2
10.输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）
A. push,pop,push,pop,push,pop
B. push,push,push,pop,pop,pop
C. push,push,pop,pop,push,pop
D. push,pop,push,push,pop,pop
答案:B
满分：2分得分：2
11.设无向图的顶点个数为n，则该图最多有（ ）条边。
A. n-1
B. n(n-1)/2
C. n(n+1)/2
D. 0
答案:
满分：2分得分：2
12.在下列存储形式中，哪一个不是树的存储形式（ ）
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法
答案:D
满分：2分得分：2
13.以下数据结构中（ ）是非线性数据结构
A. 树
B. 字符串
C. 队
D. 栈
答案:
满分：2分得分：2
14.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。
A. 直接插入
B. 直接选择
C. 堆
D. 快速
答案:A
满分：2分得分：2
15.广义表运算式Tail(((a,b),(c,d)))的操作结果是（ ）
A. (c,d)
B. c,d
C. ((c,d))
D. d
答案:C
满分：2分得分：2
16.设给定权值总数有n 个，其哈夫曼树的结点总数为（ ）
A. 不确定
B. 2n
C. 2n+1
D. 2n-1
答案:
满分：2分得分：2
17.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）
A. 不确定
B. n-i+1
C. i
D. n-i
答案:B
满分：2分得分：2
18.由3 个结点可以构造出多少种不同的二叉树（ ）
A. 2
B. 3
C. 4
D. 5
答案:
满分：2分得分：2
19.设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）
A. 1和1
B. 1和3
C. 1和2
D. 2和3
答案:C
满分：2分得分：2
20.对关键码序列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分得分：2
21.在完全二叉树中，若一个结点是叶结点，则它没（ ）
A. 左子结点
B. 右子结点
C. 左子结点和右子结点
D. 左子结点，右子结点和兄弟结点
答案:C
满分：2分得分：2
22.栈在（ ）中应用。
A. 递归调用
B. 子程序调用
C. 表达式求值
D. A，Ｂ，Ｃ
答案:
满分：2分得分：2
23.对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。
A. 选择
B. 快速
C. 希尔
D. 冒泡
答案:C
满分：2分得分：2
24.就平均性能而言，目前最好的内部排序方法是（ ）排序法。
A. 冒泡
B. 希尔插入
C. 交换
D. 快速
答案:
满分：2分得分：2
25.下面叙述正确的是（ ）
A. 算法的执行效率与数据的存储结构无关
B. 算法的空间复杂度是指算法程序中指令(或语句)的条数
C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止
D. 以上三种描述都不对
答案:C
满分：2分得分：2
二、判断题（共20道试题，共40分。）得分：40
1.栈是实现过程和函数等子程序所必需的结构（ ）
A. 错误
B. 正确
答案:
满分：2分得分：2
2.对一棵二叉树进行层次遍历时，应借助于一个栈（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
3.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
4.对于有N个结点的二叉树，其高度为log2n（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
5.若一个广义表的表头为空表，则此广义表亦为空表（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
6.循环队列通常用指针来实现队列的头尾相接（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
7.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
8.链表中的头结点仅起到标识的作用（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
9.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
10.二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）（ ）
A. 错误
B. 正确
答案:B
满分：2分得分：2
11.内部排序要求数据一定要以顺序方式存储（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
12.二维以上的数组其实是一种特殊的广义表（ ）
A. 错误
B. 正确
答案:B
满分：2分得分：2
13.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
14.循环链表不是线性表（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
15.队列和栈都是运算受限的线性表，只允许在表的两端进行运算（ ）。
A. 错误
B. 正确
答案:A
满分：2分得分：2
16.采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的
A. 错误
B. 正确
答案:B
满分：2分得分：2
17.当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省（ ）。
A. 错误
B. 正确
答案:A
满分：2分得分：2
18.任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
19.折半查找法的查找速度一定比顺序查找法快（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
20.二叉树是度为2的有序树（ ）
A. 错误
B. 正确
答案:A
满分：2分得分：2
三、多选题（共5道试题，共10分。）得分：10
1.某堆栈的输入序列为a, b，c ，d,下面的四个序列中，可能是它的输出序列的是（ ）
A. a，c，b，d
B. b, c，d，a
C. c, d，b, a
D. d, c，a，b
答案:
满分：2分得分：2
2.以下数据结构中（ ）不是线性结构
A. 广义表
B. 二叉树
C. 稀疏矩阵
D. 串
答案:
满分：2分得分：2
3.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形可能出现的是（ ）
A. G中有弧<Vi，Vj>
B. G中有一条从Vi到Vj的路径
C. G中没有<Vi,Vj>
D. G中有一条从Vj到Vi的路径
答案:
满分：2分得分：2
4.在下列情况中，不能为二叉树的是（ ）
A. 每个结点至多有两棵子树的树
B. 哈夫曼树
C. 每个结点至多有两棵子树的有序树
D. 每个结点只有一棵右子树
答案
满分：2分得分：2
5.下述哪些不是顺序存储结构的优点（ ）
A. 存储密度大
B. 插入运算方便
C. 删除运算方便
D. 可方便地用于各种逻辑结构的存储表示
答案:
满分：2分得分：2
页:
[1]