盐城师范学院算法与数据结构期末复习题及参考答案.docx

盐城师范继续教育学院算法与数据结构普通用卷一单项选择题（共50题，总分值75分）1.以下随机算法中运行时有时候成功有时候失败的是 （）（1.5 分）A.数值概率算法B.舍伍德算法C.拉斯维加斯算法D.蒙特卡罗算法2.下面关于m阶B树说法正确的选项是（）。每个结点至少有两棵非空子树；树中每个结点至多有m；个关键字；所有叶子在同一层上；当插入一个数据项引起B树结点分裂后，树长高一层。（1.5 分） AB.CD.3.在树形结构中，数据元素间存在（）的关系。(1.5分）A. 一对一B. 一对多D. 0（n2）36.串的长度是指（）。（1.5分）A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数37.以下排序算法中（）不能保证每趟排序至少能将 一个元素放到其最终的位置上。（1. 5分）A.快速排序B. shell 排序C.堆排序D,冒泡排序38.设有一个二维数组假设A00存放位 置在644（10）, A2 2存放位置在676（10）,每个 元素占一个空间，问A3 3 （10）存放在什么位 置？脚注（10）表示用10进制表示。（）（L5分）A. 688B. 678C. 692D. 696.下面问题（）不能使用贪心法解决。（1.5分）A.单源最短路径问题8. N皇后问题C.最小花费生成树问题D.背包问题.设有k个关键字互为同义词，假设用线性探测法把这 k个关键字存入散列表，至少要进行（）次探测。（1.5 分）A. k-1B. kC. k+1D. k（k-l）/2.二叉树的第k层的结点数最多为（）.（1.5分）A. 2k-lB. 2K+1C. 2K-1D. 2k-l.以下哪一种算法不是随机化算法（）（1.5分）A.蒙特卡罗算法B.拉斯维加斯算法C.动态规划算法D.舍伍德算法43.常见的两种分支限界法为（D）（1.5分）A.广度优先分支限界法与深度优先分支限界法B.队列式（FIFO）分支限界法与堆栈式分支限界法C.排列树法与子集树法D.队列式（FIFO）分支限界法与优先队列式分支 限界法44.以下说法中错误的选项是（）。（1.5分）A.栈是一种非线性结构8. 一个数据元素由一或多个数据项构成C.在顺序存储结构中，结点间的逻辑关系由存储单元的邻接关系来表达D.语句的频度就是语句的执行次数.（）是贪心算法与动态规划算法的共同点。（1.5 分）A.重叠子问题B.构造最优解C.贪心选择性质D.最优子结构性质.顺序表中数据元素的存取方式为（）。（1.5分）A.随机存取B.顺序存取C.索引存取D,连续存取.对n个记录的文件进行快速排序，所需要的辅助存 储空间大致为（）（1.5分）A. 0 （1）B. 0 （n）C. 0 （log2n）D. O （n2）. 一棵高为k的二叉树最少有（）个结点。（1.5分）A. k-1B. kC. k+1D. 2匕1E. 2k-l.应用Johnson法那么的流水作业调度采用的算法是（）（1.5 分）A.贪心算法B.分支限界法C.分治法D.动态规划算法50.秦始皇吞并六国使用的远交近攻，逐个击破的连横 策略采用了以下哪种算法思想（L5分）归治代拟 递分迭模 AB.GD.一单项选择题（共50题，总分值75分）.答案：C1 .答案：B.答案：B2 .答案：A.答案：D3 .答案：A.答案：A4 .答案：A.答案：A5 .答案：C.答案：B6 .答案：D.答案：A7 .答案：A.答案:B8 .答案：D.答案：B9 .答案：C.答案：B10 .答案：C.答案：A11 .答案：B.答案：B12 .答案：C.答案：A13 .答案:B.答案：B14 .答案：A.答案：A15 .答案：B.答案:D16 .答案：D.答案：B17 .答案：A.答案：D18 .答案：B.答案:B19 .答案：C.答案：B20 .答案：B.答案：D21 .答案：C.答案：D22 .答案：A.答案：D23 .答案：A.答案：C24 .答案：B.答案：D25 .答案：BC.多对多D.除同属一个集合外别无关系.不带头结点的单链表（头指针为head）为空的判定 条件是（）。（1.5分）A. head=NULLB. head->next=headC. head->next=NULLD. head!=NULL.以下表达中错误的选项是（）。（1.5分）A.对数组一般不做插入和删除操作B.顺序存储的数组是一个随机存取结构C.空的广义表没有表头和表尾D.广义表的表尾可能是原子也可能是子表. m阶B树中的一个分支结点最多含（）个关键字。（）（1.5 分）A. m-1B. mC. m/2D. m/2+l.将一个AL. 100, L.100的三对角矩阵，按行优 先存入一维数组BL.298中,那么A中的元素A66, 65在数组B中的位置K二（）o （1.5分）A. 195B. 196C. 197D. 198.以下算法中不能解决0/1背包问题的是（）（1.5 分）A.贪心法B.动态规划C.回溯法D.分支限界法9.队列的删除操作是在（）进行。（1.5分）A.队首B.队尾C.队首前一单元D.队尾后一单元. 一棵二叉树中第6层上最多有（）个结点。（1.5 分）A. 2B. 31C. 32D. 64.对一个算法的评价，不包括如下（）方面的内容。（）（1.5 分）A.健壮性和可读性B.并行性C.正确性D.时空复杂度12.设哈希表地址范围为019,哈希函数H（key）=key%17,使用二次探测再散列法处理冲突。假设表中已存放有关键字值为6、22、38、55的记录, 那么再放入关键字值为72的记录时，其存放地址应为（）o （1.5 分）A. 2B. 3C. 4D. 7E. 8F.以上都不对13. Strassen矩阵乘法是利用（）实现的算法。（1. 5 分）A.分治策略B.动态规划法C.贪心法D.回溯法.设对以下图从顶点a出发进行深度优先遍历，那么（）是可能得到的遍历序列。 分）(1. 5A. acfgdeb B. abcdefg C. acdgbef D. abefgcd. k带图灵机的空间复杂性S（n）是指（）（1.5分）A. k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最大方格数B.k带图灵机处理所有长度为n的输入时，在k 条带上所使用过的方格数的总和C.k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数D. k带图灵机处理所有长度为n的输入时，在某 条带上所使用过的最小方格数.设有一组关键字值（46,79,56,38,40,84）,那么用 快速排序的方法，以第一个记录为基准得到的一次 划分结果为（）。（1.5分）A. 38,40,46,56,79,84B. 40,38,46,79,56,84C. 40,38,46,56,79,84D. 40,38,46,84,56,79.以下关于栈的表达中，正确的选项是（）。（1.5分）A.栈底元素一定是最后入栈的元素B.栈操作遵循先进后出的原那么C.栈顶元素一定是最先入栈的元素D.以上三种说法都不对. 一个栈的输入序列为123,那么以下序列中不可能是 栈的输出序列的是（）（1.5分）A. 231B. 321C. 312D. 123.以下算法中通常以自底向下的方式求解最优解的 是（）。（1.5 分）A.分治法B.动态规划法C.贪心法D.回溯法.对于单链表，在两个结点之间插入一新结点需要修 改的指针共（）个。（L5分）A. 0B. 1C. 2D. 4.栈和队列的共同特点是（）。（1.5分）A.只允许在端点处插入和删除元素B,都是先进后出C.都是先进先出D.没有共同点.每一趟都能选出一个元素放在其最终位置上，并且 不稳定的排序算法是（）（1.5分）A.冒泡排序B.简单项选择择排序C.希尔排序D.直接插入排序.设连通图G中的边集E= （a, b） , （a, e） , （a, c） , （b, e） , （e, d） ， （d, f） , （f, c） ,那么从顶点a出发可以得到一种深度优先遍历的顶点 序列为（）（1.5分）A. abedfcB. acfebdC. aebdfcD. aedfcb.线性表假设采用顺序结构时，要求内存中可用存储单 元的地址（）。（1. 5分）A. 一定是不连续的B.局部地址是连续的C. 一定是连续的D.连续不连续都可以25.分支限界法解旅行售货员问题时，活结点表的组织 形式是（）。（1.5分）A.最小堆B.最大堆C.栈D.数组.背包问题的贪心算法所需的计算时间为（）（1.5 分）A. O （n2n）B. 0 （nlogn）C. 0 （2n）D. 0 （n）.由树转换而得的二叉树，根结点（）。（1.5分）A.没有左子树B.没有右子树C.左右子树都有D.视树的形态而定.设表中含100个数据元素，用折半查找法进行查找，那么所需最大比拟次数为（）。（1.5分）A. 50B. 25C. 10D. 7. ISAM文件和VSAM文件属于（）。（1.5分）A.索引非顺序文件B.索引顺序文件C.顺序文件D.散列文件.设无向图的顶点个数为n,那么该图最多有（）条 边。（1.5分）A. n-1B. n(n-l)/2C. n(n+l)/2D. n2.以下表达中错误的选项是()。(1.5分)A.由树的先序遍历序列和后序遍历序列可以惟一确定一棵树B.二叉树不同于度为2的有序树C.深度为k的二叉树上最少有k个结点D.在结点数目相同的二叉树中，最优二叉树的 路径长度最短32.适用于折半查找的表的存储方式及元素排列要求为（）。（1.5 分）A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序33.实现最长公共子序列利用的算法是（）（1.5分）A.分治策略B.动态规划法C.贪心法D.回溯法.将两个各有n个元素的有序表归并成一个有序表,最少进行（）次比拟。（1.5分）A. nB. 2n-lC. 2nD. n-1.直接插入排序在最好情况下的时间复杂度为（）o（1.5 分）A. O（logn）B. 0（n）C. O（n*logn）