《17秋福师《数据结构概论》在线作业一》由会员分享，可在线阅读，更多相关《17秋福师《数据结构概论》在线作业一（9页珍藏版）》请在金锄头文库上搜索。
1、福师数据结构概论在线作业一 试卷总分：100 测试时间：- 单选题 判断题 多选题 、单选题（共 25 道试题，共 50 分。） 1. 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为（ ） (1=i=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2)满分：2 分 2. 算法的时间复杂度是由（ ）决定的。 A. 问题的规模 B. 待处理数据的初态 C. A 和 B D. 变量个数满分：2 分 3. 对 N 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) A. （N+1）/2 B. N/2 C. N
2、D. （1+N）*N /2满分：2 分 4. 栈在（ ）中应用。 A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，满分：2 分 5. 下列排序算法中，（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位 置上。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序满分：2 分 6. 对于栈操作数据的原则是（ ） A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序满分：2 分 7. 对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是（ ） A. head=NULL B. headnext=NULL C. headnext
3、=head D. head!=NULL满分：2 分 8. 若要求尽可能快地对序列进行稳定的排序，则应选（ ） A. 快速排序 B. 归并排序 C. 冒泡排序D. 堆满分：2 分 9. 栈和队都是（ ） A. 顺序存储的 B. 线性结构 C. 链式存储的 D. 非线性结构满分：2 分 10. 求解最短路径的 Floyd 算法的时间复杂度为（ ）。 A. O（n） B. O（n+c） C. O（n*n） D. O（n*n*n）满分：2 分 11. 假设以行序为主序存储二维数组 A=array1.100，1.100，设每个数据元素占 2 个存储单元，基地 址为 10，则 LOC5，5=（ ）。 A.
4、 808 B. 818 C. 1010 D. 1020满分：2 分 12. 若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是（ ） A. 9 B. 11 C. 15 D. 不确定满分：2 分 13. 线索二叉树是一种（ ）构。 A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性满分：2 分 14. 栈在（ ）中应用。 A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，满分：2 分 15. 下面有关算法说法错误的是（ ） A. 算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指
5、令不能有二义性 D. 以上几个都是错误的满分：2 分 16. 线性表是具有 n 个（ ）的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项满分：2 分 17. 最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是（ ） A. (rear+1) MOD n=front B. rear=frontC. rear+1=front D. (rear-l) MOD n=front满分：2 分 18. 具有 12 个关键字的有序表，折半查找的平均查找长度（ ） A. 3.1 B. 4 C. 2.5 D. 5满分：2 分 19. 计算机算法指的是（ ） A.
6、 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法满分：2 分 20. 若用冒泡排序方法对序列10,14,26,29,41,52从大到小排序，需进行 （ ）次比较。 A. 3 B. 10 C. 15 D. 25满分：2 分 21. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。 A. O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)满分：2 分 22. 研究数据结构就是研究（ ）。 A. 数据的逻辑结构、存储结构及其基本操作 B. 数据的逻辑结构和存储结构 C. 数据的存储结构 D. 数据的逻辑结构满分
7、：2 分 23. 若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是（ ） A. 9 B. 11 C. 15 D. 不确定满分：2 分 24. 设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a11 为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a85 的地址为（ ） A. 13 B. 33 C. 18 D. 40满分：2 分 25. 图中有关路径的定义是（ ）。 A. 由顶点和相邻顶点序偶构成的边所形成的序列 B. 由不同顶点所形成的序列 C. 由不同边所形成的序列 D. 上述定义都不是满分：2 分 判断题 1. 队列
8、是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。A. 错误 B. 正确满分：2 分 2. 二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）（ ） A. 错误 B. 正确满分：2 分 3. 栈是实现过程和函数等子程序所必需的结构。 A. 错误 B. 正确满分：2 分 4. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大 A. 错误 B. 正确满分：2 分 5. 顺序存储方式只能用于存储线性结构（ ） A. 错误 B. 正确满分：2 分 6. 数据元素是数据的最小单位。 A. 错误 B. 正确满分：2 分 7. 二叉树的遍历结果不是唯一
9、的. A. 错误 B. 正确满分：2 分 8. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（ ） A. 错误 B. 正确满分：2 分 9. 在待排数据基本有序的情况下，快速排序效果最好。 A. 错误 B. 正确满分：2 分 10. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. A. 错误 B. 正确满分：2 分 11. 在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。 A. 错误 B. 正确满分：2 分 12. 直接选择排序算法在最好情况下的时间复杂度为 O（N）。 A. 错误 B. 正确满分：2 分 13. 若一个广义表的表头为空表，则
10、此广义表亦为空表。 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.
11、 正确满分：2 分 20. 二维以上的数组其实是一种特殊的广义表（ ） A. 错误 B. 正确满分：2 分 多选题 1. 下面关于串的的叙述中，正确的是？（ ） A. 串是字符的有限序列 B. 空串是由空格构成的串 C. 模式匹配是串的一种重要运算 D. 串既可以采用顺序存储，也可以采用链式存储满分：2 分 2. 下列哪种图的邻接矩阵不是对称矩阵？（ ） A. 有向图 B. 无向图 C. AOV 网 D. AOE 网满分：2 分 3. 下面关于二分查找的叙述不正确的是（ ） A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序，而且只能从小到大排列 C. 表必须有序且表中
12、数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储满分：2 分 4. 下面几个符号串编码集合中，是前缀编码的是（ ） 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 分 5. 下列关于 m 阶 B-树的说法正确的是( ) A. 根结点至多有 m 棵子树 B. 所有叶子都在同一层次上 C. 非叶结点至少有 m/2 (m 为偶数)或 m/2+1（m 为奇数）棵子树D. 根结点中的数据是有序的满分：2 分 福师数据结构概论在线作业一 试卷总分：100 测
13、试时间：- 单选题 判断题 多选题 、单选题（共 25 道试题，共 50 分。） 1. 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为（ ） (1=i=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2)满分：2 分 2. 算法的时间复杂度是由（ ）决定的。 A. 问题的规模 B. 待处理数据的初态 C. A 和 B D. 变量个数满分：2 分 3. 对 N 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) A. （N+1）/2 B. N/2 C. N D. （1+N）*N /2满分：2 分 4. 栈
14、在（ ）中应用。 A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，满分：2 分 5. 下列排序算法中，（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位 置上。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序满分：2 分 6. 对于栈操作数据的原则是（ ） A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序满分：2 分 7. 对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是（ ） A. head=NULL B. headnext=NULL C. headnext=head D. head!=NULL满分：2
15、分 8. 若要求尽可能快地对序列进行稳定的排序，则应选（ ） A. 快速排序B. 归并排序 C. 冒泡排序 D. 堆满分：2 分 9. 栈和队都是（ ） A. 顺序存储的 B. 线性结构 C. 链式存储的 D. 非线性结构满分：2 分 10. 求解最短路径的 Floyd 算法的时间复杂度为（ ）。 A. O（n） B. O（n+c） C. O（n*n） D. O（n*n*n）满分：2 分 11. 假设以行序为主序存储二维数组 A=array1.100，1.100，设每个数据元素占 2 个存储单元，基地 址为 10，则 LOC5，5=（ ）。 A. 808 B. 818 C. 1010 D. 1020满分：2 分 12. 若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是（ ） A. 9 B. 11 C. 15 D. 不确定满分：2 分 13. 线索二叉树是一种（ ）构。 A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性满分：2 分 14. 栈在（ ）中应用。 A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，满分：2 分 15. 下面有关算法说法错误的是（ ） A. 算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都
