首页 › 福建师范大学 › 福师13秋《数据结构概论》在线作业答案

黄老师 发表于 2014-1-21 09:43:11

福师13秋《数据结构概论》在线作业答案

福师13秋《数据结构概论》在线作业一
试卷总分：100   测试时间：--
一、单选题（共25道试题，共50分。）
1.表达式a*(b+c)-d的后缀表达式是( )
A. abcd*+-
B. abc+*d-
C. abc*+d-
D. -+*abcd
满分：2分
2.关键路径是事件结点网络中（ ）
A. 从源点到汇点的最长路径
B. 从源点到汇点的最短路径
C. 最长回路
D. 最短回路
满分：2分
3.具有10个叶结点的二叉树中有（ ）个度为2的结点，
A. 8
B. 9
C. 10
D. ll
满分：2分
4.下列排序算法中（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。
A. 堆排序
B. 冒泡排序
C. 快速排序
D. 插入排序
满分：2分
5.图中有关路径的定义是（ ）
A. 由顶点和相邻顶点序偶构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
满分：2分
6.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）
A. 不确定
B. n-i+1
C. i
D. n-i
满分：2分
7.若串S=’software’,其子串的数目是（ ）
A. 8
B. 37
C. 36
D. 9
满分：2分
8.算法的时间复杂度是由（ ）决定的。
A. 问题的规模
B. 待处理数据的初态
C. A和B
D. 变量个数
满分：2分
9.就平均性能而言，目前最好的内部排序方法是（ ）排序法。
A. 冒泡
B. 希尔插入
C. 交换
D. 快速
满分：2分
10.下列排序算法中，在待排序数据已有序时，花费时间反而最多的是（ ）排序
A. 冒泡
B. 希尔
C. 快速
D. 堆
满分：2分
11.在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）
A. O(n)
B. O(n＋e)
C. O(n*n)
D. O(n*n*n)
满分：2分
12.算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）
A. ab+cde/*
B. abcde/+*+
C. abcde/*++
D. abcde*/++
满分：2分
13.输入序列为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
满分：2分
14.广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）Head(Tail(Head(Tail(Tail(A)))))
A. （a）
B. A
C. a
D.
d
满分：2分
15.连续存储设计时，存储单元的地址（ ）
A. 一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
满分：2分
16.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）
A. 选择排序法
B. 插入排序法
C. 快速排序法
D. 堆积排序法
满分：2分
17.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。
A. 直接插入
B. 直接选择
C. 堆
D. 快速
满分：2分
18.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）
A. (rear+1) MOD n=front
B. rear=front
C. rear+1=front
D. (rear-l) MOD n=front
满分：2分
19.若要求尽可能快地对序列进行稳定的排序，则应选（ ）
A. 快速排序
B. 归并排序
C. 冒泡排序
D. 堆
满分：2分
20.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A. 求子串
B. 联接
C. 匹配
D. 求串长
满分：2分
21.字符串‘ababaabab’ 的nextval 为（ ）
A. (0,1,0,1,04,1,0,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分
22.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列（ ）
A. 5 4 3 6 1 2
B. 4 5 3 1 2 6
C. 3 4 6 5 2 1
D. 2 3 4 1 5 6
满分：2分
23.设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）
A. 1和1
B. 1和3
C. 1和2
D. 2和3
满分：2分
24.对关键码序列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分
25.已知串S=‘aaab’,其Next数组值为（ ）
A. 0123
B. 1123
C. 1231
D. 1211
满分：2分
二、判断题（共20道试题，共40分。）
1.在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面（ ）
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. 二叉树的度为2
B. 一棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
满分：2分
2.以下数据结构中属于线性数据结构的有哪些（ ）
A. 队列
B. 线性表
C. 二叉树
D. 栈
满分：2分
3.下面说法正确的是（ ）
A. 广义表的表头总是一个广义表
B. 广义表的表尾总是一个广义表
C. 广义表难以用顺序存储结构
D. 广义表可以是一个多层次的结构
满分：2分
4.下面关于串的的叙述中，正确的是（ ）
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
满分：2分
5.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形可能出现的是（ ）
A. G中有弧<Vi，Vj>
B. G中有一条从Vi到Vj的路径
C. G中没有<Vi,Vj>
D. G中有一条从Vj到Vi的路径
福师《数据结构概论》在线作业二
试卷总分：100   测试时间：--
一、单选题（共25道试题，共50分。）
1.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ ）
A. p->next=s;s->next=p->next;
B. s->next=p->next;p->next=s;
C. p->next=s;p->next=s->next;
D. p->next=s->next;p->next=s;
满分：2分
2.对关键码序列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分
3.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A. 插入
B. 选择
C. 希尔
D. 二路归并
满分：2分
4.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）
A. 不确定
B. n-i+1
C. i
D. n-i
满分：2分
5.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）
A. CABDEFG
B. ABCDEFG
C. DACEFBG
D. ADCFEG
满分：2分
6.从逻辑上可以把数据结构分为（ ）两大类
A. 动态结构、静态结构
B. 顺序结构、链式结构
C. 线性结构、非线性结构
D. 初等结构、构造型结构
满分：2分
7.算法的时间复杂度是由（ ）决定的。
A. 问题的规模
B. 待处理数据的初态
C. A和B
D. 变量个数
满分：2分
8.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）
A. m-n
B. m-n-1
C. n+1
D. 条件不足，无法确定
满分：2分
9.表达式a*(b+c)-d的后缀表达式是( )
A. abcd*+-
B. abc+*d-
C. abc*+d-
D. -+*abcd
满分：2分
10.对于栈操作数据的原则是（ ）
A. 先进先出
B. 后进先出
C. 后进后出
D. 不分顺序
满分：2分
11.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）
A. 5
B. 6
C. 7
D. 8
满分：2分
12.在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）
A. O(n)
B. O(n＋e)
C. O(n*n)
D. O(n*n*n)
满分：2分
13.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。
A. 前序
B. 中序
C. 后序
D. 按层次
满分：2分
14.具有12个关键字的有序表，折半查找的平均查找长度（ ）
A. 3.1
B. 4
C. 2.5
D. 5
满分：2分
15.下列排序算法中，占用辅助空间最多的是（ ）
A. 归并排序
B. 快速排序
C. 希尔排序
D. 堆排序
满分：2分
16.已知串S=‘aaab’,其Next数组值为（ ）
A. 0123
B. 1123
C. 1231
D. 1211
满分：2分
17.求解最短路径的Floyd算法的时间复杂度为（ ）。
A. O（n）
B. O（n+c）
C. O（n*n）
D. O（n*n*n）
满分：2分
18.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）
A. O(n) O(n)
B. O(n) O(1)
C. O(1) O(n)
D. O(1) O(1)
满分：2分
19.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）
A. （N+1）/2
B. N/2
C. N
D. [（1+N）*N ]/2
满分：2分
20.散列函数有一个共同的性质，即函数值应当以（ ）取其值域的每个值。
A. 最大概率
B. 最小概率
C. 平均概率
D. 同等概率
满分：2分
21.若串S=’software’,其子串的数目是（ ）
A. 8
B. 37
C. 36
D. 9
满分：2分
22.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）(1<=i<=n+1)。
A. O(0)
B. O(1)
C. O(n)
D. O(n2)
满分：2分
23.设给定权值总数有n 个，其哈夫曼树的结点总数为（ ）
A. 不确定
B. 2n
C. 2n+1
D. 2n-1
满分：2分
24.算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）
A. ab+cde/*
B. abcde/+*+
C. abcde/*++
D. abcde*/++
满分：2分
25.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A. 求子串
B. 联接
C. 匹配
D. 求串长
满分：2分
二、判断题（共20道试题，共40分。）
1.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大（ ）
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.完全二叉树一定存在度为1的结点（ ）
A. 错误
B. 正确
满分：2分
17.用树的前序遍历和中序遍历可以导出树的后序遍历（ ）
A. 错误
B. 正确
满分：2分
18.循环链表不是线性表（ ）
A. 错误
B. 正确
满分：2分
19.用一维数组存储二叉树时，总是以前序遍历顺序存储结点（ ）
A. 错误
B. 正确
满分：2分
20.顺序存储方式只能用于存储线性结构（ ）
A. 错误
B. 正确
满分：2分
三、多选题（共5道试题，共10分。）
1.下面几个符号串编码集合中，是前缀编码的是（ ）
A. {0,10,110,1111}
B. {11,10,001,101,0001}
C. {00,010,0110,1000}
D. {b,c,aa,ac,aba,abb,abc}
满分：2分
2.下面关于求关键路径的说法正确的是（ ）
A. 求关键路径是以拓扑排序为基础的
B. ．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D. 关键活动一定位于关键路径上
满分：2分
3.某堆栈的输入序列为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分
4.下面说法正确的是（ ）
A. 广义表的表头总是一个广义表
B. 广义表的表尾总是一个广义表
C. 广义表难以用顺序存储结构
D. 广义表可以是一个多层次的结构
满分：2分
5.下述哪些不是顺序存储结构的优点（ ）
A. 存储密度大
B. 插入运算方便
C. 删除运算方便
D. 可方便地用于各种逻辑结构的存储表示
满分：2分

查看完整版本: 福师13秋《数据结构概论》在线作业答案