当前位置：文档之家 › 算法基础样题06

算法基础样题06

  • 格式：doc
  • 大小：431.00 KB
  • 文档页数：10

算法基础样题一、单项选择题(本大题共10小题，每小题3分，共30分)1.1、对整数序列：6，5，9，3，7，1作从小到大排序，经排序算法一次处理后，该序列变成：1，5，9，3，7，6则在以下四种供选择的排序方法中，能实现这个要求的排序方法是A、选择排序B、堆排序C、插入排序D、快速排序1.2、已知一个有向图如下所示，则从顶点A出发进行深度优先遍历，不可能得到的DFS序列为A、A D E B F C .B、A C D E B FC、A E C D B FD、A D E B C F1.3、不可能生成下图所示二叉排序树(二叉检索树)的输入序列是A、8 2 13 10 15 8B、8 13 2 15 10C、8 13 10 2 15 2 13D、8 2 10 13 1510 151.4、迭代算法求方程的根时，为了防止方程无解，宜采用的措施是A、选择速度更快的计算机B、降低方程根的精度要求C、在程序中增加对迭代次数给予检测和限制的代码D、自动选择新的初始根1.5、快速排序算法是属于哪一类算法？A、试探法B、迭代法C、贪婪法D、分治法1.6、在执行操作过程中，将路径上所遇到的结点都直接挂到根结点之下，称作路径压缩，该操作是A、UnionB、FindC、InsertD、Delete1.7、如求最短路径的Dijkstra方法、求最小生成树的Prim方法和Kruskal方法等。

这类算法以局部优良为选择的依据，在每一步直接根据当前状态，确定下一步骤，而不顾及未来的整体情况，该类算法通称A、试探法B、贪婪法C、迭代法D、递推法1.8、下列排序算法中，哪一个排序算法在每趟排序后不一定能选出一个元素放到其排序好的序列的正确位置上。

A、冒泡排序B、堆排序C、直接插入排序D、选择排序1.9、在一棵具有n个结点的A VL树上，完成插入、删除等操作，一般情况的最低时间上限是A、O(n2)B、O(n)C、O(nlbn)D、O(lb n)1.10、若一个栈的进栈元素序列是1、2、3、4、5，出栈序列的第一个元素是5。

则第2个出栈元素是A、3B、4C、2D、不能确定1.1、以下序列中可以是一个堆的是A、9、5、4、2、7、1、3B、9、7、4、2、5、3、1C、9、7、4、2、3、5、1D、9、4、7、5、2、3、11.2、已知一个有向图如下所示，则从顶点A出发进行深度优先遍历，不可能得到的DFS序列为E、A D B E F C .F、A C D B E FG、 A B C D E FH、 A D B E C F1.3、不可能生成下图所示二叉排序树(二叉检索树)的输入序列是A、7 2 12 10 15 7B、7 12 2 15 10C、7 12 10 2 15 2 12D、7 2 10 12 1510 151.4、若希望尽可能快地对数值大小差异很大的整数数组进行稳定的排序，则在以下四种供选择的排序方法中，能实现这个要求的排序方法是A、堆排序B、快速排序C、基数排序D、归并排序1.5、一个只利用模式本身的性质，实现无回溯匹配的算法是A、试探法B、KMP算法C、BM算法D、逆向匹配算法1.6、在执行操作过程中，将路径上所遇到的结点都直接挂到根结点之下，称作路径压缩，该操作是A、UnionB、FindC、InsertD、Delete1.7、如求最短路径的Dijkstra方法、求最小生成树的Prim方法和Kruskal方法等。

这类算法以局部优良为选择的依据，在每一步直接根据当前状态，确定下一步骤，而不顾及未来的整体情况，该类算法通称A 、试探法B 、贪婪法C 、迭代法D 、递推法1.8、著名的Ackerman 函数定义如下：n+1， 当m = 0时akm(m, n) = akm(m-1, 1)， 当m ≠0, n = 0时akm(m-1, akm(m, n-1))， 当 m ≠0, n ≠ 0时根据上述递归定义，akm(1, 1)的值等于A 、2B 、6C 、1D 、31.9、在一棵具有n 个结点的A VL 树上，完成插入、删除等操作，一般情况的最低时间上限是A 、O(n2)B 、O(n)C 、O(nlbn)D 、O(lb n)1.10、一个能大大减少索引项数量，在数据表上插入与删除操作又很少影响索引表存储结构的是A 、动态索引结构B 、稀疏索引结构C 、线性索引结构D 、索引顺序结构1.1、对整数序列5， 4， 9， 3， 6， 2，作从小到大的堆排序，堆排序算法首先对该序列构造初始堆，所构造的初始堆序列是A 、9、6、5、4、3、2B 、9、6、5、3、4、2C 、2、3、4、5、6、9D 、2、3、5、4、6、91.2、已知一个有向图如下所示，则从顶点A 出发进行深度优先遍历，不可能得到的DFS序列为I 、 A D B E C F . J 、 A D E C F B K 、 A D E F C B L 、 A D E B C F1.3、不可能生成下图所示二叉排序树(二叉检索树)的输入序列是A 、7 2 3 1 9 7B 、7 2 9 3 1C 、7 9 2 1 3 9D 、7 9 3 1 21 31.4、为实现递归，系统要为每次递归调用分配一个活动记录。

通常，在活动记录中包括的主要内容除有实参、局部变量外，至少还要有A 、递归调用队列B 、递归函数的返回值C 、递归调用的返回地址D 、递归调用的工作栈1.5、把复杂问题分解出一系列子问题，为不重复求相同子问题，子问题的解答存于一个数组中，待再次解同样子问题时，就从数组中取出该子问题的解答，这类算法通称A 、试探法B 、迭代法C 、贪婪法D 、动态规划法1.6、在解“Hanoi”塔问题的算法中，将搬n张金片分为搬上面的n-1张金片和搬最下面的一张金片，从而将n张金片的移动转换成更少张数金片的移动。

这类将大问题分解成若干子问题，然后分别解决各个子问题得到大问题的求解方法，统称A、试探法B、迭代法C、分治法D、贪婪法1.7、求最短路径的Dijkstra方法、求最小生成树的Prim方法和Kruskal方法等。

这类算法以局部优良为选择的依据，在每一步直接根据当前状态，确定下一步骤，而不顾及未来的整体情况，该类算法通称A、试探法B、贪婪法C、迭代法D、递推法1.8、设有递归函数p()定义如下，则函数调用p(4)的值是int p(int t){ if (t == 1) return 1;return 1 + t*p(t-1);}A、7B、9C、31D、411.9、对数据表的数据量大，数据增删变化又特别频繁的，宜采用的索引结构是A、动态索引结构B、非线性索引结构C、线性索引结构D、动态多路索引结构1.10、5路搜索树的高度为3，有最多结点数的搜索树是除叶结点之外，每个结点都有5个子树，故高度为3的一棵5路搜索树中，最多关键码数是A、624B、626C、625D、25二、简答题(本大题共5小题，每小题4分，共20分)2.1、试写出以下序列的冒泡排序过程。

7，3，8，9，22.2、在回溯算法中，为了确保算法能够终止，回溯调整时，必须保证的要求是什么？2.3、对关键字序列（48、30、63、54、58、27、37）进行SHELL排序，设第一次取间隔g为3，则进行第一趟处理之后得到的结果为2.4、若待排序的整数序列是已排好序的，用插入排序、选择排序和冒泡排序三种排序算法对该序列作排序处理，则能最快结束排序的排序方法是哪一种排序方法？简单指出理由。

_2.5、设4路搜索树的高度为3，有最多结点数的搜索树是除叶结点之外，每个结点都有4个子树。

这棵搜索树最多结点数是多少？2.1、在m路B树上查找一个给定键值k的记录的地址时，若当前结点有n个键值，它的键值序列是k1，k2，…，k n。

查找时需考虑哪4种情况?2.2、在回溯算法中，为了确保算法能够终止，回溯调整时，必须保证的要求是什么？2.3、对关键字序列（32、30、53、23、48、22）进行基数排序，需作两趟处理。

其中进行第一趟处理之后得到的结果为。

2.4、设二叉树的后序为3、4、7、2、5；中序为3、4、7、5、2。

试画出这棵二叉树。

2.5、设5路搜索树的高度为3，有最多结点数的搜索树是除叶结点之外，每个结点都有5个子树。

这棵搜索树最多结点数是多少？2.1、简述在二叉检索树上查找关键字值为x结点的查找过程。

2.2、集合S上定义的等价关系R，必须满足的条件是。

2.3、对关键字序列（32、30、53、23、48、22）进行基数排序，需作两趟处理。

其中进行第一趟处理之后得到的结果为。

2.4、设二叉树的后序为6、7、2、3、5；中序为7、6、2、5、3。

试画出这棵二叉树。

2.5、写出使用归并排序法对下列数据进行从小到大排序的前两步的中间过程。

{73，45，63，13，64，35，96，57，39，79，61，15}三、算法理解题(本大题共5小题，每小题6分，共30分)3.1、对关键字序列（29、20、52、61、25、35、27、28）进行从小到大的堆排序，试给出排序时建立的初始堆。

3.2、设输入记录的关键码依次为:8，14，3，7，16，5，6，构造一棵3阶B树。

试画出按所给出的关键码顺序输入记录，从空的B树开始，构造一棵3阶B树的构造过程。

3.3、输入一组记录构造一棵A VL树。

设输入记录的关键码依次为：12，9，3，7，4，5试画出按所给出的关键码顺序输入记录，从空A VL树开始，构造一棵A VL树的构造过程。

3.1、对关键字序列（47、20、52、61、25、15、27、28）进行从小到大的堆排序，试给出排序时建立的初始堆。

3.2、设输入记录的关键码依次为:7，14，3，8，17，5，6，构造一棵3阶B树。

试画出按所给出的关键码顺序输入记录，从空的B树开始，构造一棵3阶B树的构造过程。

3.3、输入一组记录构造一棵A VL树。

设输入记录的关键码依次为：11，8，2，7，3，4试画出按所给出的关键码顺序输入记录，从空A VL树开始，构造一棵A VL树的构造过程。

3.1、对关键字序列（47、20、52、61、25、15）进行快速排序，并设在快速排序过程中作分划的基准数为分划序列的第一个数、中间数和末位置数，这三个数中的中间大小的哪一个数作为分划的基准数。

算法在确定基准数的同时，已将最小的数放于数列的最前端，最大的数放在数列的最后端。

划分开始时，又先将基准数存于划分序列最后(数例最后第二个位置)。

这样，进行一次分划后，得到的关键字序列为。

3.2、设输入记录的关键码依次为:8，15，3，7，19，2，6，构造一棵3阶B树。

试画出按所给出的关键码顺序输入记录，从空的B树开始，构造一棵3阶B树的构造过程。

3.3、输入一组记录构造一棵A VL树。

合集下载

算法考试题目及答案解析

算法考试题目及答案解析

算法考试题目及答案解析一、单项选择题1. 在算法中，以下哪个选项不是算法的特性？A. 有穷性B. 确定性C. 可行性D. 随机性答案：D解析：算法的特性包括有穷性、确定性和可行性。

有穷性指的是算法必须在执行有限步骤后终止；确定性指的是算法的每一步操作都是明确的，不存在二义性；可行性指的是算法的每一步操作都必须足够基本，以至于可以准确地执行。

随机性并不是算法的特性之一。

2. 以下哪个排序算法的时间复杂度是O(n^2)？A. 快速排序B. 归并排序C. 冒泡排序D. 堆排序答案：C解析：冒泡排序是一种简单的排序算法，其时间复杂度为O(n^2)，在最坏的情况下，需要比较每一对元素。

快速排序的平均时间复杂度为O(n log n)，归并排序的时间复杂度为O(n log n)，堆排序的时间复杂度为O(n log n)。

3. 在图的遍历中，深度优先搜索（DFS）使用的栈是什么类型的栈？A. 后进先出栈B. 先进后出栈C. 先进先出栈D. 随机进随机出栈答案：B解析：深度优先搜索（DFS）使用的数据结构是栈，遵循的是先进后出的原则，即后进先出栈。

4. 哈希表解决冲突的方法不包括以下哪一项？A. 分离链接法B. 开放寻址法C. 链地址法D. 二分查找法答案：D解析：哈希表解决冲突的方法主要包括分离链接法、开放寻址法和链地址法。

二分查找法是一种查找算法，不是用来解决哈希表冲突的方法。

5. 以下哪个算法不是动态规划算法？A. 斐波那契数列B. 0-1背包问题C. 最短路径问题D. 快速排序答案：D解析：斐波那契数列、0-1背包问题和最短路径问题都可以使用动态规划算法来解决。

快速排序是一种排序算法，不属于动态规划算法。

二、多项选择题1. 以下哪些是算法设计中常用的数据结构？A. 数组B. 链表C. 栈D. 队列E. 树答案：ABCDE解析：数组、链表、栈、队列和树都是算法设计中常用的数据结构，它们各自有不同的特点和适用场景。

算法初步练习试题[附详细答案解析]

算法初步练习试题[附详细答案解析]

算法初步练习题一、选择题：1．阅读下面的程序框图，则输出的S =A ．14B ．20C ．30D ．552．阅读图2所示的程序框图，运行相应的程序，输出的结果是A ．1 B. 2 C. 3 D. 43．阅读右图所示的程序框图，运行相应的程序，输出的结果是A ．2B ．4C ．8D ．162题1题4．某程序框图如图所示，该程序运行后输出的k 的值是A ．4B ．5C ．6D ．75．执行右面的程序框图，输出的S 是 A ．378- B ．378 C ．418- D ．4183题4题6．如图的程序框图表示的算法的功能是A ．计算小于100的奇数的连乘积B ．计算从1开始的连续奇数的连乘积C ．从1开始的连续奇数的连乘积，当乘积大于100时，计算奇数的个数D ．计算100531≥⨯⋅⋅⋅⨯⨯⨯n 时的最小的n 值.7．右图是把二进制数)2(11111化为十进制数的一个程序框图,判断框内应填入的 条件是A ．4i >B ．4i ≤C ．5i > D．5i ≤5题 6题8．某程序框图如图所示，则该程序运行后输出的B 等于 A ．15 B ．29 C ．31 D ．639．如果执行右边的程序框图，输入2,0.5x h =-=，那么输出的各个数的和等于 A ．3 B ．3.5 C ．4 D ．4.57题8题10．某店一个月的收入和支出总共记录了N 个数据1a ，2,,N a a ⋅⋅⋅，其中 收入记为 正数，支出记为负数。

该店用右边的程序框图计算月总收入S 和月 净盈利V ，那么在图中空白的判断框和处理框中，应分别填入下列四个选项中 的A ．0,A V S T >=-B ．0,A V S T <=-C ．0,A V S T >=+D ．0,A V S T <=+ 11. 如图1所示，是关于闰年的流程，则 以下年份是闰年的为A ．1996年B ．1998年C ．2010年D ．2100年12. 某流程如右上图所示，现输入如下四个函数，则可以输出的函数是10题11题9题A ．2)(x x f =B ．xx f 1)(=C ．62ln )(-+=x x x fD ．x x f sin )(=二、填空题：13．程序框图（即算法流程图）如图所示，其输出结果是_______.12题 13题14．执行右边的程序框图，输出的T = .15．下面的程序框图表示的算法的结果是 1616．阅读右上面的流程图，若输入6,1a b ==，则输出的结果是 214题15题17右面的程序框图，如果输入三个实数a ，b ，c ，要求输出这三个数中最大的数，那么在空白的判断框中，应该填入下面四个选项中的 ①c x > ②x c >③C ．c b >④b c >三、解答题：18．已知数列{a n }的各项均为正数，观察程序框图，若10,5==k k 时，分别有2110115==S S 和 （1）试求数列{a n }的通项；（2）令m a n b b b b n +++=...,221求的值.参考答案1．C ．【解读与点评】当1=i 时， S =1;当i =2时， S =5;循环下去，当i =3时， S =14； 当i =4时,S =30；本试题考查了程序框图的运用．2．D 【解读与点评】本题考查是算法的重新框图与算法的语句识别．易错点是 不懂得运行顺序．当1,2n S ==代入程序中运行第一次是1S =-，然后赋值此时2n =；返回运 行第二次可得111(1)2S ==--，然后赋值3n =； 再返回运行第三次可得12112S ==-，然后赋值4n =，判断可知此时2S =，故输出4n =．故选D ．3．C 【解读与点评】本题考查是算法的重新框图与算法的语句识别．考查学生 运算求解能力．本题的易错点是要注意是先赋值再输出．当1,2n S ==代入程序中运行第一次是1S =-，然后赋值此时2n =；返回运 行第二次可得111(1)2S ==--，然后赋值4n =； 再返回运行第三次可得12112S ==-，然后赋值8n =，判断可知此时2S =，故输出8n =． 4．A ．【解读与点评】对于0,1,k s ==1k ∴=.对于1,3,2k s k ==∴=，则 2,38,3k s k ==+∴=，后面是113,382,4k s k ==++∴=，不符合条件时输出 的4k =．此题是新课程新增内容，考查了程序语言的概念和基本的应用，通 过对程序语言的考查，充分体现了数学程序语言中循环语言的关键． 9．B ．【解读与点评】循环9次，对应输出值如下表。

算法入门测试题及答案高中

算法入门测试题及答案高中

算法入门测试题及答案高中一、选择题（每题2分，共20分）1. 以下哪个不是算法的基本特征？A. 有穷性B. 确定性C. 通用性D. 可行性2. 递归算法的基本原理是什么？A. 循环B. 迭代C. 分治D. 重复3. 在排序算法中，以下哪个算法的时间复杂度是O(n^2)？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. 选择排序B. 插入排序C. 快速排序E. 拓扑排序10. 以下哪个算法是解决旅行商问题的？A. 动态规划B. 贪心算法C. 回溯算法D. 分治算法答案：1-5 CADBA 6-10 BDDDC二、填空题（每空2分，共20分）1. 算法的时间复杂度是指算法执行所需时间与输入规模的______关系。

2. 在数据结构中，______是一种特殊的线性表，只允许在表的一端进行插入和删除操作。

3. 快速排序是一种______排序算法，它通过一个划分操作将待排序的数组分为两部分，然后递归地在子数组上重复这个过程。

4. 动态规划算法通常用于解决具有______性质的问题。

5. 在图的深度优先搜索中，如果存在环，可能会陷入______。

答案：1. 函数 2. 栈 3. 分治 4. 重叠子问题 5. 无限循环三、简答题（每题10分，共20分）1. 请简述什么是贪心算法，并给出一个实际应用的例子。

算法设计基础考试题及答案

算法设计基础考试题及答案

算法设计基础考试题及答案一、单项选择题（每题2分，共20分）1. 在算法设计中，下列哪个选项不是算法的特性？A. 有穷性B. 确定性C. 可行性D. 随机性答案：D2. 递归算法的基本思想是？A. 重复执行相同的操作B. 将问题分解成更小的子问题C. 顺序执行所有操作D. 随机选择操作答案：B3. 在排序算法中，时间复杂度为O(nlogn)的算法是？A. 冒泡排序B. 快速排序C. 选择排序D. 插入排序答案：B4. 哈希表解决冲突的方法不包括以下哪一项？A. 开放定址法B. 链地址法C. 再哈希法D. 顺序存储法答案：D5. 动态规划算法的核心思想是什么？A. 贪心选择B. 分治策略C. 回溯搜索D. 存储子问题的解答案：D6. 在图的遍历算法中，深度优先搜索（DFS）使用的栈是什么类型的？A. 后进先出栈B. 先进后出栈C. 后进后出栈D. 先进先出栈答案：B7. 以下哪个算法不是贪心算法？A. 霍夫曼编码B. 迪杰斯特拉算法C. 克鲁斯卡尔算法D. 快速排序答案：D8. 在算法分析中，大O表示法描述的是？A. 算法的运行时间B. 算法的空间复杂度C. 算法的最坏情况时间复杂度D. 算法的平均情况时间复杂度答案：C9. 以下哪个数据结构最适合实现优先队列？A. 链表B. 数组C. 二叉搜索树D. 哈希表答案：C10. 算法的时间复杂度为O(1)意味着什么？A. 算法运行时间与输入大小无关B. 算法运行时间与输入大小成正比C. 算法运行时间与输入大小成对数关系D. 算法运行时间与输入大小成平方关系答案：A二、填空题（每题2分，共20分）1. 算法的时间复杂度为O(n^2)的排序算法是________。

答案：冒泡排序2. 在图的遍历中，广度优先搜索（BFS）使用的队列是________类型的。

答案：先进先出3. 动态规划与分治法的主要区别在于________。

答案：存储子问题的解4. 递归算法的终止条件是________。