东师《算法分析与设计16秋在线作业1

东北师范大学东师算法分析与设计16秋在线作业1一、单选题（共 20 道试题，共 40 分。）1. n个结点的完全有向图含有边的数目（）。A. n*nB. n（n）C. n2D. n*（nl）正确答案：2. 在一个无向图中，所有顶点的度数之和等于所有边数（B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。A. 1/2B. 2C. 1D. 4正确答案：3. 将递归算法转换成对应的非递归算法时，通常需要使用()。A. 栈B. 队列C. 链表D. 树正确答案：4. 分治法是把一个复杂的问题分成相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题解的()A. 合并B. 最大值C. 最小值D. 平均值正确答案：5. strcmp(a,b)返回的值是（）A. 2B. 1C. 0D. -1正确答案：6. 一个算法中的语句的()被称为语句频度或时间频度。A. 执行时间B. 占用空间C. 执行速度D. 执行次数正确答案：7. 与二进制数101.01011等值的十六进制数为( )。A. A.BB. 5.51C. A.51D. 5.58正确答案：8. 下面选项中比较著名的命名规则有()。A. 匈牙利命名法B. 匈牙利命名法和骆驼命名法C. 有匈牙利命名法、骆驼命名法和帕斯卡命名法D. 匈牙利命名法、骆驼命名法、帕斯卡命名法以及下划线命名法正确答案：9. 数制中表示基本数值大小的不同数字符号称为（）。A. 进制B. 基数C. 位权D. 数码正确答案：10. ()是用户在程序中使用的名字，它是一种用于命名一些具有特定含义的对象的符号，通常用来标识程序中的变量，常量，函数，语句块。A. 对象B. 标识符C. 符号D. 命名规则正确答案：11. IDE的全程是()。A. 集成开发环境B. 集成环境C. 开发软件D. 调试过程正确答案：12. 有以下程序，程序的运行结果是()。 #include int f(int x ) int y; if (x=0|x=1) return (3); y=x*x- f(x-2); return y; main() int z; z=f(3); printf(“%dn”,z); A. 0B. 9C. 6D. 8正确答案：13. ()嵌在源程序体中，用于描述其后的语句或程序段做什么工作，也就是解释下面要做什么，或是执行了下面的语句会怎么样。而不要解释下面怎么做，因为程序本身就是怎么做。A. 文件注释B. 函数注释C. 功能注释D. 程序注释正确答案：14. 下列叙述中，正确的是()。A. 对长度为n 的有序链表进行查找，最坏情况下需要的比较次数为nB. 对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为(n/2)C. 对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为(log2n)D. 对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为(nlog2n)正确答案：15. 图中有关路径的定义是（）。A. 由顶点和相邻顶点序偶构成的边所形成的序列B. 由不同顶点所形成的序列C. 由不同边所形成的序列D. 上述定义都不是正确答案：16. ()是一个开放源代码的、基于Java的可扩展开发平台。A. VSB. Dev-C+C. EclipseD. JDK正确答案：17. 设无向图的顶点个数为n，则该图最多有（）条边。A. n-1B. n(n-1)/2C. n(n+1)/2D. n2正确答案：18. 九进制，就表示某一位置上的数运算时是逢（）进一位。A. 2B. 8C. 9D. 10正确答案：19. 某内排序方法的稳定性是指()。A. 该排序算法不允许有相同的关键字记录B. 该排序算法允许有相同的关键字记录C. 平均时间为0（n log n）的排序方法D. 以上都不对正确答案：20. 递归算法是()。A. 简单方程B. 标准方程C. 简单公式D. 标准公式正确答案： 算法分析与设计16秋在线作业1二、多选题（共 5 道试题，共 20 分。）1. 字符串有关的格式字符有（ ）。A. %cB. %dC. %fD. %s正确答案：2. 高精度运算主要解决（）。A. B. 加数C. 减数D. 运算结果的输入E. 运算结果的存储正确答案：3. 设计递归算法有两点最为关键()和()。A. 确定递推公式B. 确定边界（终了）条件（递归出口）C. 每次递归调用，都必须向基本条件前进D. 如果结果已知，那么，不用再重复调用递归正确答案：4. 递归算法的执行过程分()和()两个阶段。A. 递归B. 递推C. 回归D. 回溯正确答案：5. 顺序结构、选择结构、循环结构三种结构共同特点是()A. 只有一个入口B. 只有一个出口C. 结构内的每一部分都有机会被执行到（不存在死语句）D. 结构内不存在死循环（永远执行不完的循环）。正确答案： 算法分析与设计16秋在线作业1三、判断题（共 20 道试题，共 40 分。）1. C语言中，字符串作为字符数组来处理。A. 错误B. 正确正确答案：2. 有n个数存放在一维数组A1.n中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。A. 错误B. 正确正确答案：3. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为n次。A. 错误B. 正确正确答案：4. C语言允许对数组的大小作动态定义，即定义行中的数组长度能包括变量。A. 错误B. 正确正确答案：5. 递推就是在函数里调用自身。A. 错误B. 正确正确答案：6. 一个函数直接或间接调用自己本身，这种函数叫递归函数。A. 错误B. 正确正确答案：7. 使用冒泡排序法对n个数进行排序必须要进行n趟比较。A. 错误B. 正确正确答案：8. 一个算法的评价只要考虑时间复杂度。A. 错误B. 正确正确答案：9. 求n的阶乘的表示方法n!=n*(n-1)! ，其中0!=1，对应的是递归的思想。A. 错误B. 正确正确答案：10. 在计算机上中有符号整数和无符号整数表示的数值范围是相同的。A. 错误B. 正确正确答案：11. 在待排数据基本有序的情况下，快速排序效果最好。A. 错误B. 正确正确答案：12. 高精度计算时可以用数组来存储运算结果。A. 错误B. 正确正确答案：13. 按“先进后出”原则组织数据的数据结构是队列。A. 错误B. 正确正确答案：14. 注释内容太多会影响程序的执行效率。A. 错误B. 正确正确答案：15. 深度为k(k=1)的二叉树至多有2k-1个结点。A. 错误B. 正确正确答案：16. 一个scanf函数输入多个字符串，输入时以“空格”键作为字符串间的分隔。A. 错误B. 正确正确答案：17. 在顺序表中进行结点的删除操作平均须移动一半结点。A. 错误B. 正确正确答案：18. 为提高在外排序过程中，对长度为N的初始序列进行“置换选择”排序时，可以得到的最大初始有序段的长度不超过N/2。A. 错误B. 正确正确答案：19. 能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解很容易构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。A. 错误B. 正确正确答案：20. 字符串的结束标记在输出时也会被输出。A. 错误B. 正确正确答案： 算法分析与设计16秋在线作业1一、单选题（共 20 道试题，共 40 分。）1. 下列数据结构中，属于非线性结构的是（ ）。A. 循环队列B. 带链队列C. 二叉树D. 带链栈正确答案：2. tolower（）函数用来（）。A. 小写字母转换为大写字母B. 大写字母转换为小写字母C. 小写字母转换为大写字母，同时大写字母转换为小写字母D. 判断大小写正确答案：3. 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是()。A. 选择排序法B. 插入排序法C. 快速排序法D. 堆积排序法正确答案：4. 排序算法是按照某个或某些关键字的()，递增或递减的排列起来的操作A. 类别B. 属性C. 名称D. 大小正确答案：5. 伪代码是用介于自然语言和()之间的文字和符号来描述算法。A. 面向过程语言B. 面向对象语言C. 编程语言D. 计算机语言正确答案：6. ()是一个开放源代码的、基于Java的可扩展开发平台。A. VSB. Dev-C+C. EclipseD. JDK正确答案：7. 变量名=属性 + 类型 + 对象描述，其中每个对象的名称都要有明确含义，可以取对象的名字全称或名字的一部分，这种命名规则是()。A. 匈牙利命名法B. 骆驼命名法C. 下划线命名法D. 帕斯卡命名法正确答案：8. 注释从功能上可以分为文件注释、函数注释和()。A. 程序员注释B. 功能注释C. 时间注释D. 版权注释正确答案：9. 二进制的1110，0的位权是（）。A. 0B. 1C. 2D. 4正确答案：10. 广度优先搜索的原则()。A. 按时间遍历解空间B. 按代价遍历解空间C. 按层遍历解空间D. 按速度遍历解空间正确答案：11. 字符数组在初始化时若数据个数少于数组长度,多余元素自动为（）。A. 空B. 0C. nullD. 随机正确答案：12. 十六进制数C1B转换为二进制数是（）。A. 1100101101011B. 110000011011C. 10110101010D. 11101001011正确答案：13. 一般情况下，程序中所有注释的行数占到整个源程序的()比较适宜。A. 1/2到2/3B. 1/3C. 1/3到1/2D. 1/2正确答案：14. 下面不是批处理文件的特点是()。A. 批处理，也称为批处理脚本，其文件扩展名为.batB. 它是无格式的文本文件，每一行可视为一个命令，每个命令里可以含多条子命令，从第一行开始执行，直到最后一行结束，它运行的平台是DOS。C. 在命令提示下键入批处理文件的名称，或者单击该批处理文件，系统就会调用cmd.exe按照该文件中各个命令出现的顺序来逐个运行它们。D. 使用批处理文件，可以简化日常或重复性任务，使用方便、灵活，功能强大，自动化程度高正确答案：15. 在深度为7的满二叉树中，叶子结点的个数为（）。A. 32B. 31C. 64D. 63正确答案：16. 对有序数组5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100进行二分查找，等概率的情况下查找成功的平均查找长度（平均比较次数）是（）。A. 35/11B. 34/11C. 33/11D. 32/11正确答案：17. 十进制的123，1的位权是（）。A. 1B. 2C. 10D. 100正确答案：18. 使用简单选择排序法对n个数进行排序要进行()趟比较。A. nB. n-1C. n+1D. 不一定正确答案：19. 如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。()就是不稳定的排序方法。A. 起泡排序B. 归并排序C. Shell排序D. 直接插入排序正确答案：20. 递归函数f(n)=f(n-1)+n(n1)的递归出口是()。A. f(1)=0B. f(1)=1C. f(0)=1D. f(n)=n正确答案： 算法分析与设计16秋在线作业1二、多选题（共 5 道试题，共 20 分。）1. 设计递归算法有两点最为关键()和()。A. 确定递推公式B. 确定边界（终了）条件（递归出口）C. 每次递归调用，都必须向基本条件前进D. 如果结果已知，那么，不用再重复调用递归正确答案：2. 高精度运算主要解决（）。A. B. 加数C. 减数D. 运算结果的输入E. 运算结果的存储正确答案：3. 顺序结构、选择结构、循环结构三种结构共同特点是()A. 只有一个入口B. 只有一个出口C. 结构内的每一部分都有机会被执行到（不存在死语句）D. 结构内不存在死循环（永远执行不完的循环）。正确答案：4. 递归算法的执行过程分()和()两个阶段。A. 递归B. 递推C. 回归D. 回溯正确答案：5. 字符串有关的格式字符有（ ）。A. %cB. %dC. %fD. %s正确答案： 算法分析与设计16秋在线作业1三、判断题（共 20 道试题，共 40 分。）1. 下列程序段实现的是顺序查找功能（） int Search(int array, int n, int key) int i; arrayn = key; for(i=0;key!=arrayi;i+); return(i=1)的二叉树至多有2k-1个结点。A. 错误B. 正确正确答案：5. 在使用递归策略时，必须有一个明确的递归结束条件，称为递归入口。A. 错误B. 正确正确答案：6. 在深度为7的满二叉树中，度为2的结点个数为64。A. 错误B. 正确正确答案：7. 冒泡排序是一种不稳定排序方法。A. 错误B. 正确正确答案：8. 下列程序段实现的是顺序查找功能（） int Search(int array, int n, int key) int i; arrayn = key; for(i=0;key!=arrayi;i+); return(in?i:-1); A. 错误B. 正确正确答案：9. 递推分倒推法和顺推法两种形式。A. 错误B. 正确正确答案：10. 简单选择排序和冒泡排序都是一种不稳定排序方法。A. 错误B. 正确正确答案：11. 归并排序是一种稳定的排序方法。A. 错误B. 正确正确答案：12. 函数atoi(1