13春福建师范大学《数据结构概论》在线作业一

福师《数据结构概论》在线作业一
试卷总分：100
单选题
判断题
多选题
一、单选题（共 25 道试题，共 50 分。）
V
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. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）
A. 5
B. 6
C. 7
D. 8
此题选: D 满分：2 分
3. 具有10个叶结点的二叉树中有（ ）个度为2的结点，
A. 8
B. 9
C. 10
D. ll
满分：2 分
4. 一个算法应该是（ ）
A. 程序
B. 问题求解步骤的描述
C. 要满足五个基本特性
D. A和C.
满分：2 分
5. 字符串‘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 分
6. 一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）
A. CABDEFG
B. ABCDEFG
C. DACEFBG
D. ADCFEG
满分：2 分
7. 若串S=’software’,其子串的数目是（ ）
A. 8
B. 37
C. 36
D. 9
满分：2 分
8. 一个递归算法必须包括（ ）
A. 递归部分
B. 终止条件和递归部分
C. 迭代部分
D. 终止条件和迭代部分
满分：2 分
9. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。
A. 前序
B. 中序
C. 后序
D. 按层次
满分：2 分
10. 已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（ ）
A. head（tail（tail（L）））
B. tail（head（head（tail（L））））
C. head（tail（head（tail（L））））
D. head（tail(head（tail（tail（L）））)）
此题选: D 满分：2 分
11. 要连通具有n个顶点的有向图，至少需要（ ）条边。
A. n-l
B. n
C. n+l
D. 2n
满分：2 分
12. 若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。
A. 直接插入
B. 直接选择
C. 堆
D. 快速
满分：2 分
13. 下面的程序段中，对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 分
14. 下面叙述正确的是（ ）
A. 算法的执行效率与数据的存储结构无关
B. 算法的空间复杂度是指算法程序中指令(或语句)的条数
C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止
D. 以上三种描述都不对
满分：2 分
15. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A. 求子串
B. 联接
C. 匹配
D. 求串长
满分：2 分
16. 设给定权值总数有n 个，其哈夫曼树的结点总数为（ ）
A. 不确定
B. 2n
C. 2n+1
D. 2n-1
此题选: D 满分：2 分
17. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
A. 线性表的顺序存储结构
B. 队列
C. 线性表的链式存储结构
D. 栈
此题选: D 满分：2 分
18. 连续存储设计时，存储单元的地址（ ）
A. 一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
满分：2 分
19. 对于栈操作数据的原则是（ ）
A. 先进先出
B. 后进先出
C. 后进后出
D. 不分顺序
满分：2 分
20. 求解最短路径的Floyd算法的时间复杂度为（ ）。
A. O（n）
B. O（n+c）
C. O（n*n）
D. O（n*n*n）
此题选: D 满分：2 分
21. 图中有关路径的定义是（ ）
A. 由顶点和相邻顶点序偶构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
满分：2 分
22. 下面有关算法说法错误的是（ ）
A. 算法最终必须由计算机程序实现
B. 为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性
D. 以上几个都是错误的
此题选: D 满分：2 分
23. 设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）
A. 1和1
B. 1和3
C. 1和2
D. 2和3
满分：2 分
24. 散列函数有一个共同的性质，即函数值应当以（ ）取其值域的每个值。
A. 最大概率
B. 最小概率
C. 平均概率
D. 同等概率
此题选: D 满分：2 分
25. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）
A. m-n
B. m-n-1
C. n+1
D. 条件不足，无法确定
满分：2 分
福师《数据结构概论》在线作业一
试卷总分：100
单选题
判断题
多选题
二、判断题（共 20 道试题，共 40 分。）
V
1. 在顺序存储结构中，有时也存储数据结构中元素之间的关系（ ）
A. 错误
B. 正确
满分：2 分
2. 对任何数据结构链式存储结构一定优于顺序存储结构（ ）。
A. 错误
B. 正确
满分：2 分
3. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止（ ）
A. 错误
B. 正确
满分：2 分
4. 二叉树是度为2的有序树（ ）
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 分
福师《数据结构概论》在线作业一
试卷总分：100
单选题
判断题
多选题
三、多选题（共 5 道试题，共 10 分。）
V
1. 以下数据结构中属于线性数据结构的有哪些（ ）
A. 队列
B. 线性表
C. 二叉树
D. 栈
满分：2 分
2. 下面几个符号串编码集合中，是前缀编码的是（ ）
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 分
3. 下面说法正确的是（ ）
A. 广义表的表头总是一个广义表
B. 广义表的表尾总是一个广义表
C. 广义表难以用顺序存储结构
D. 广义表可以是一个多层次的结构
满分：2 分
4. 下述哪些不是顺序存储结构的优点（ ）
A. 存储密度大
B. 插入运算方便
C. 删除运算方便
D. 可方便地用于各种逻辑结构的存储表示
满分：2 分
5. 以下数据结构中（ ）不是线性结构
A. 广义表
B. 二叉树
C. 稀疏矩阵
D. 串
满分：2 分