数据结构与算法练习试卷2 (题后含答案及解析)
全部题型 2. 填空题
填空题（每空2分，共30分）请将每一个空的正确答案写在答题卡上。注意：以命令关键字填空的必须拼写完整。
1． 数据元素之间______的整体称为逻辑结构。
正确答案：逻辑关系 涉及知识点：数据结构与算法
2． 一个算法的时间复杂性是______的函数。
正确答案：算法输入规模 涉及知识点：数据结构与算法
3． 在单链表中，NULL称为______，它不指向任何结点，只起______作用。
正确答案：空指针、标志 涉及知识点：数据结构与算法
4． 对长度为n的顺序表的删除算法，它的最坏情况时间复杂度及其量级分别是和______，平均时间复杂性及其量级分别为______和______。
正确答案：n-1、O(n)、(n-1)/2、O(n) 涉及知识点：数据结构与算法
5． 存储结点中数据域占用的存储量与整个结点占用存储量之比称为______。
正确答案：存储密度 涉及知识点：数据结构与算法
6． 一般地，二叉树可以有______种基本形态。
正确答案：5 涉及知识点：数据结构与算法
7． 按照排序过程涉及的存储设备的不同，排序可分为______和______。
正确答案：内部排序、外部排序 涉及知识点：数据结构与算法
8． 评价排序算法优劣的主要标准是______和______。
正确答案：时间复杂度、算法需要的附加空间 涉及知识点：数据结构与算法
9． 稳定的排序算法有______、______和______。
正确答案：直接插入排序、冒泡排序、归并排序 涉及知识点：数据结构与算法
10． 第一趟排序后序列中关键字最大的记录交换到最后的排序方法是______。
正确答案：冒泡排序 涉及知识点：数据结构与算法
计算机⼆级数据结构与算法答案（1）
第⼀章数据结构与算法
⼀、选择题：1、栈和队列的共同特点是()
A、都是先进先出
B、都是后进先出
C、只允许在端点处插⼊和删除数据
D、没有共同点
2、已知⼆叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是()
A、acbed
B、decab
C、debac
D、cedba
3、下⾯叙述正确的是()
A、算法的执⾏效率与数据的存储结构⽆关。
B、算法的空间复杂度是指算法程序中指令(或语句)的条数。
C、算法的有穷性是指算法必须能在执⾏有限个步骤之后终⽌。
D、算法的时间复杂度是指执⾏算法程序所需要的时间。
4、以下数据结构属于⾮线性数据结构的是()
A、队列
B、线性表
C、⼆叉树
D、栈
5、算法⼀般都可以⽤哪⼏种控制结构组合⽽成?()
A、循环、分⽀、递归
B、顺序、循环、嵌套
C、循环、递归、选择
D、顺序、选择、循环
6、数据的存储结构是指()
A、数据所占的存储空间量
B、数据的逻辑结构在计算机中的表⽰
C、数据在计算机中的顺序存储⽅式
D、存储在外存中的数据
7、链表不具有的特点是()
A、不必事先估计存储空间B、可随机访问任⼀元素
C、插⼊删除不需要移动元素
D、所需空间与线性表长度成正⽐
8、算法的时间复杂度是指()
A、执⾏算法程序所需要的时间
B、算法程序的长度
C、算法执⾏过程中所需要的基本运算次数
D、算法程序中的指令条数
9、在⼀棵⼆叉树上第⼋层的结点数最多是()
A、8
B、16
C、128
D、256
10、若⼀棵⼆叉树中只有叶结点和左右⼦树皆⾮空的结点，设叶结点的个数为k，则左右⼦树皆⾮空的结点个数是()
A、2k
B、k-1
C、2k-1
D、2k-1
11、设⽆向树T有7⽚树叶，其余顶点数均为3，则T中3度顶点的个数为()
A、3
B、4
C、5
D、6
12、已知⼀棵⼆叉树前序遍历和中序遍历分别为ABDEGCFH 和DBGEACHF，则该⼆叉树
的后序遍历为()A、GEDHFBCA
B、DGEBFCA
C、ABCDEFGH
全国计算机二级考试
第一章 数据结构与算法
1.一个算法一般都可以用_____、_____ 、 _____三种控制结构组合完成;
解析顺序、选择分支、循环重复
一个算法通常由两种基本要素组成：一是对数据对象的运算和操作,二是________;
解析算法的控制结构
在一般的计算机系统中,有算术运算、逻辑运算、关系运算和________四类基本的操作和运算;
解析数据传输
2.常用于解决“是否存在”或“有多少种可能”等类型的问题例如求解不定方程的问题的算法涉及基本方法是
A．列举法 B.归纳法 C.递归法 D.减半递推法
解析列举就是列举出所有可能性,将所有可能性统统列举出来,然后解决问题的方法;所以A
3.根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的,这是算法设计基本方法中的____;
解析列举法
4.通过列举少量的特殊情况,经过分析,最后找出一般的关系的算法设计思想是
A．列举法 B.归纳法 C.递归法 D.减半递推法
解析B
5.在用二分法求解方程在一个闭区间的实根时,采用的算法设计技术是
A．列举法 B.归纳法 C.递归法 D.减半递推法
解析二分法就是从一半处比较,减半递推技术也称分治法,将问题减半;所以D
6.将一个复杂的问题归结为若干个简单的问题,然后将这些较简单的问题再归结为更简单的问题,这个过程可以一直做下去,直到最简单的问题为止,这是算法设计基本方法中的___;如果一个算法P显式地调用自己则称为___;如果算法P调用另一个算法 Q,而算法Q又调用算法P,则称为_____.
解析 递归法 直接递归 间接递归调用
7.算法中各操作之间的执行顺序称为_____;描述算法的工具通常有_____、_____ 、 _____;
解析控制结构 传统流程图、N-S结构化流程图、算法描述语言
数据结构与算法(一)
(总分78,考试时间90分钟)
一、选择题
1. 计算机算法指的是 ______，它必须具备输入、输出，可执行性、确定性和有穷性。
A. 计算方法 B. 排序方法
C. 解决问题的有限运算序列 D. 调度方法
2. 设计一个“判别在表达式中左、右括号是否配对出现”的算法，采用 ______ 数据结构最佳。
A. 线性表的顺序存储结构 B. 栈
C. 队列 D. 线性表的链式存储结构
3. 若对一棵二叉树进行中序遍历得到的结果是(B，D，A，G，H，E，C，F)，进行后序遍历的结果是DBHGEFCA，那么这棵二叉树进行前序遍历得到的结果是 ______。
A. (A， B， D， C， E， G， H，
B. (A， B， D， C， E， H， G，
C. (D，B，A，C，E，G，H，
D. 无法确定
4. 一个队列的入列序号是1，2，3，4，则队列的输出系列是 ______。
A. 4，3，2，1 B. 1，2，3，4
C. 1，4，3，2 D. 3，2，4，1
5. 对关键字序列(11，12，13，14，15)采用对半查找算法查找关键字11，则关键字之间比较次数为 ______。
A. 1 B. 2
C. 3 D. 4
6. 如果以链表为栈的存储结构，则出栈操作是 ______。
A. 必须判别栈是否为满 B. 必须判别栈是否为空
C. 判别栈元素的类型 D. 对栈不作任何判别
7. 在算法设计基本方法中， ______ 是从初始条件出发，逐次推出所需求的结果。
A. 递推 B. 递归
C. 列举法 D. 归纳法
8. 分析算法的目的是 ______。
A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系
C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档
9. 若完全二叉树共有n个结点，且从根结点开始，按层序(每层从左到右)用正整数 0，1，2，…，n-1，从小到大对结点编号，则对于编号为k的结点，错误的是 ______。
