《计算机算法基础》课后答案

《大学计算机基础与计算思维》课后习题参考答案第1章计算、计算机与计算思维............................. 第2章数据的计算基础计算机硬件系统第4章操作系统基础 (11)第5章算法与数据结构 (13)第6章程序设计及软件工程基础 (17)第7章数据库技术 (19)第8章计算机网络 (22)第9章信息安全与职业道德 (24)第10章计算软件第11章办公软件Office 2010算机科学与技术学院计算机基础教学部28 292015年9月第1章计算、计算机与计算思维1.1举例说明可计算性和计算复杂性的概念。

答：对于给定的一个输入，如果计算机器能在有限的步骤内给出答案，这个问题就是可计算的。

数值计算、能够转化为数值计算的非数值问题（如语咅、图形、图像等）都是可计算的。

汁算复杂性从数学上提出计算问题难度大小的模型，判断哪些问题的讣算是简单的，哪些是困难的，研究计算过程屮时间和空间等资源的耗费情况，从而寻求更为优越的求解复杂问题的有效规则，例如著名的汉诺塔问题。

1.2列举3种电子计算机岀现之前的计算工具，并简述其主要特点。

答:（1）算盘通过算法口诀化，加快了计算速度。

（2）帕斯卡加法器通过齿轮旋转解决了自动进位的问题。

（3）机电式计算机Z・l,全部采用继电器，第一次实现了浮点记数法、二进制运算、带存储地址的指令等设计思想。

1.3简述电子计算机的发展历程及各时代的主要特征。

答：第一代一一电子管计算机（1946—1954年）。

这个时期的计算机主要釆用电子管作为运算和逻辑元件。

主存储器采用汞延迟线、磁鼓、磁芯，外存储器采用磁带。

在软件方面，用机器语言和汇编语言编写程序。

程序的编写与修改都非常繁琐。

计算机主要用于科学和工程计算。

第二代一一晶体管计算机（1954—1964年）。

计算机逻辑元件逐步由电子管改为晶体管, 体积与功耗都有所降低。

主存储器采用铁脸氧磁芯器，外存储器釆用先进的磁盘，汁算机的速度和可靠性有所提高。

4.1：在我们所了解的早期排序算法之中有一种叫做Maxsort 的算法。

它的工作流程如下：首先在未排序序列（初始时为整个序列）中选择其中最大的元素max ，然后将该元素同未排序序列中的最后一个元素交换。

这时，max 元素就包含在由每次的最大元素组成的已排序序列之中了，也就说这时的max 已经不在未排序序列之中了。

重复上述过程直到完成整个序列的排序。

(a) 写出Maxsort 算法。

其中待排序序列为E ，含有n 个元素，脚标为范围为0,,1n -。

void Maxsort(Element[] E) { int maxID = 0;for (int i=E.length; i>1; i--) { for (int j=0; j<i; j++) {if (E[j] > E[maxID]) maxID = k; }E[i] <--> E[maxID]; } }最坏情况同平均情况是相同的都是11(1)()2n i n n C n i -=-==∑。

几遍浏览序列实现。

排序策略是顺序比较相邻元素，如果这两个元素未排序则交换这两个元素的位置。

也就说，首先比较第一个元素和第二个元素，如果第一个元素大于第二个元素，这交换这两个元素的位置；然后比较第二个元素与第三个元素，按照需要交换两个元素的位起泡排序的最坏情况为逆序输入，比较次数为11(1)()2n i n n C n i -=-==∑。

(b) 最好情况为已排序，需要(n-1)次比较。

4.3： (a)归纳法：当n=1时显然成立，当n=2时经过一次起泡后，也显然最大元素位于末尾；现假设当n=k-1是，命题也成立，则当n=k 时，对前k-1个元素经过一次起泡后，根据假设显然第k-1个元素是前k-1个元素中最大的，现在根据起泡定义它要同第k 个元素进行比较，当k元素大于k-1元素时，它为k个元素中最大的，命题成立；当k元素小于k-1元素时，它要同k-1交换，这时处于队列末尾的显然时队列中最大的元素。

2012年计算机二级公共基础知识数据结构与算法归纳及课后习题第一章数据结构与算法算法---是一组严谨地定义运算顺序的规则算法的基本要素---一是对数据对象的运算和操作，二是算法的控制结构算法设计基本方法---列举法、归纳法、递推、递归、减半递推算法的复杂度---包括时间复杂度和空间复杂度时间复杂度---执行算法所需的计算工作量空间复杂度---执行算法所需的内存空间数据结构---相互有关联的数据元素的集合。

如春、夏、秋、冬；18、11、35、23、16。

；父亲、儿子、女儿等都是数据元素。

前件---数据元素之间的关系，如父亲是儿子和女儿的前件后件---如儿子是父亲的后件结构---指数据元素之间的前后件关系数据的逻辑结构—是指反映数据元素之间逻辑关系，而与它们在计算机中的存储位置无关数据的存储结构（物理结构）---数据的逻辑结构在计算机存储空间中的存放形式，数据元素在计算机存储空间的位置关系可能与逻辑关系不同。

根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据结构分两类---线性结构与非线性结构线性结构（线性表）---满足下列两个条件（1）有且只有一个根结点（2）每一个结点最多有一个前件和后件。

则称该数据结构为线性结构，否则为非线性结构。

线性表是最简单、最常用的一种数据结构，其数据元素之间的相对位置是线性的，其存储方式为顺序存储的，如数组栈---是限定在一端进行插入与删除的线性表，一端封闭，另一端开口，其操作原则是“先进后出”，栈的运算有入栈、退栈、读栈顶元素队列---是指在一端进行插入（称为队尾）而在另一端进行删除（称为队头）的线性表，其操作规则是“先进先出”，其运算有入队和退队。

树---是一种简单的非线性结构，而且是层次结构，是倒立的大树，有根结点、父结点、子结点、叶子结点。

根结点在第一层，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度，树的最大层次称为树的深度。

二叉树---（1）非空二叉树只有一个根结点（2）每一个结点最多有两棵子树（左子树和右子树），其存储结构为链式。

计算机算法设计与分析习题及答案一．选择题1、二分搜索算法是利用 A 实现的算法;A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是 A ;A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是A 的一搜索方式;A、分支界限法B、动态规划法C、贪心法D、回溯法4. 回溯法解旅行售货员问题时的解空间树是 A ;A、子集树B、排列树C、深度优先生成树D、广度优先生成树5．下列算法中通常以自底向上的方式求解最优解的是B ;A、备忘录法B、动态规划法C、贪心法D、回溯法6、衡量一个算法好坏的标准是 C ;A 运行速度快B 占用空间少C 时间复杂度低D 代码短7、以下不可以使用分治法求解的是 D ;A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题8. 实现循环赛日程表利用的算法是A ;A、分治策略B、动态规划法C、贪心法D、回溯法9．下面不是分支界限法搜索方式的是D ;A、广度优先B、最小耗费优先C、最大效益优先D、深度优先10．下列算法中通常以深度优先方式系统搜索问题解的是D ;A、备忘录法B、动态规划法C、贪心法D、回溯法11.备忘录方法是那种算法的变形; BA、分治法B、动态规划法C、贪心法D、回溯法12．哈夫曼编码的贪心算法所需的计算时间为B ;A、On2nB、OnlognC、O2nD、On13．分支限界法解最大团问题时,活结点表的组织形式是B ;A、最小堆B、最大堆C、栈D、数组14．最长公共子序列算法利用的算法是B;A、分支界限法B、动态规划法C、贪心法D、回溯法15．实现棋盘覆盖算法利用的算法是A ;A、分治法B、动态规划法C、贪心法D、回溯法16.下面是贪心算法的基本要素的是C ;A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解17.回溯法的效率不依赖于下列哪些因素 DA.满足显约束的值的个数B. 计算约束函数的时间C.计算限界函数的时间D. 确定解空间的时间18.下面哪种函数是回溯法中为避免无效搜索采取的策略BA．递归函数 B.剪枝函数 C;随机数函数 D.搜索函数19. D是贪心算法与动态规划算法的共同点;A、重叠子问题B、构造最优解C、贪心选择性质D、最优子结构性质20. 矩阵连乘问题的算法可由 B 设计实现;A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法21. 分支限界法解旅行售货员问题时,活结点表的组织形式是 A ;A、最小堆B、最大堆C、栈D、数组22、Strassen矩阵乘法是利用A 实现的算法;A、分治策略B、动态规划法C、贪心法D、回溯法23、使用分治法求解不需要满足的条件是 A ;A 子问题必须是一样的B 子问题不能够重复C 子问题的解可以合并D 原问题和子问题使用相同的方法解24、下面问题 B 不能使用贪心法解决;A 单源最短路径问题B N皇后问题C 最小生成树问题D 背包问题25、下列算法中不能解决0/1背包问题的是 AA 贪心法B 动态规划C 回溯法D 分支限界法26、回溯法搜索状态空间树是按照 C 的顺序;A 中序遍历B 广度优先遍历C 深度优先遍历D 层次优先遍历27．实现合并排序利用的算法是A ;A、分治策略B、动态规划法C、贪心法D、回溯法28．下列是动态规划算法基本要素的是D ;A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质29．下列算法中通常以自底向下的方式求解最优解的是 B ;A、分治法B、动态规划法C、贪心法D、回溯法30．采用广度优先策略搜索的算法是A ;A、分支界限法B、动态规划法C、贪心法D、回溯法31、合并排序算法是利用 A 实现的算法;A、分治策略B、动态规划法C、贪心法D、回溯法32、背包问题的贪心算法所需的计算时间为 BA、On2nB、OnlognC、O2nD、On33．实现大整数的乘法是利用的算法C ;A、贪心法B、动态规划法C、分治策略D、回溯法34．0-1背包问题的回溯算法所需的计算时间为AA、On2nB、OnlognC、O2nD、On35．采用最大效益优先搜索方式的算法是A;A、分支界限法B、动态规划法C、贪心法D、回溯法36．贪心算法与动态规划算法的主要区别是B;A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解37. 实现最大子段和利用的算法是B ;A、分治策略B、动态规划法C、贪心法D、回溯法38.优先队列式分支限界法选取扩展结点的原则是 C ;A、先进先出B、后进先出C、结点的优先级D、随机39.背包问题的贪心算法所需的计算时间为 B ;A、On2nB、OnlognC、O2nD、On40、广度优先是A 的一搜索方式;A、分支界限法B、动态规划法C、贪心法D、回溯法41. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的 B ;A、重叠子问题B、最优子结构性质C、贪心选择性质D、定义最优解42．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序,故算法的时间复杂度为 B ;A 、On2nB 、OnlognC 、O2nD 、On43. 以深度优先方式系统搜索问题解的算法称为 D ;A 、分支界限算法B 、概率算法C 、贪心算法D 、回溯算法44. 实现最长公共子序列利用的算法是B ;A 、分治策略B 、动态规划法C 、贪心法D 、回溯法45. Hanoi 塔问题如下图所示;现要求将塔座A 上的的所有圆盘移到塔座B 上,并仍按同样顺序叠置;移动圆盘时遵守Hanoi 塔问题的移动规则;由此设计出解Hanoi 塔问题的递归算法正确的为：B46. 动态规划算法的基本要素为 CA. 最优子结构性质与贪心选择性质 B ．重叠子问题性质与贪心选择性质C ．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 47. 能采用贪心算法求最优解的问题,一般具有的重要性质为： AA. 最优子结构性质与贪心选择性质 B ．重叠子问题性质与贪心选择性质C ．最优子结构性质与重叠子问题性质 D. 预排序与递归调用48. 回溯法在问题的解空间树中,按 D 策略,从根结点出发搜索解空间树;A.广度优先B. 活结点优先C.扩展结点优先D. 深度优先49. 分支限界法在问题的解空间树中,按 A 策略,从根结点出发搜索解空间树;A.广度优先B. 活结点优先C.扩展结点优先D. 深度优先50. 程序块 A 是回溯法中遍历排列树的算法框架程序;A.B. C. D. 51. 常见的两种分支限界法为DA. 广度优先分支限界法与深度优先分支限界法；B. 队列式FIFO 分支限界法与堆栈式分支限界法；C. 排列树法与子集树法；D. 队列式FIFO 分支限界法与优先队列式分支限界法；1.算法的复杂性有 时间 复杂性和 空间 ;2、程序是 算法用某种程序设计语言的具体实现;3、算法的“确定性”指的是组成算法的每条 指令 是清晰的,无歧义的;4. 矩阵连乘问题的算法可由 动态规划 设计实现;5、算法是指解决问题的 一种方法 或 一个过程 ;6、从分治法的一般设计模式可以看出,用它设计出的程序一般是 递归算法 ;7、问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征;8、以深度优先方式系统搜索问题解的算法称为 回溯法 ;9、计算一个算法时间复杂度通常可以计算 循环次数 、 基本操作的频率 或计算步; Hanoi 塔A. void hanoiint n, int A, int C, int B{ if n > 0{ hanoin-1,A,C, B;moven,a,b; hanoin-1, C, B, A; }} B. void hanoiint n, int A, int B, int C { if n > 0 { hanoin-1, A, C, B; moven,a,b; hanoin-1, C, B, A; } }C. void hanoiint n, int C, int B, int A { if n > 0 { hanoin-1, A, C, B; moven,a,b; hanoin-1, C, B, A; } }D. void hanoiint n, int C, int A, int B { if n > 0 { hanoin-1, A, C, B; moven,a,b; hanoin-1, C, B, A; } } void backtrack int t{ if t>n outputx; else for int i=t;i<=n;i++ { swapxt, xi; if legalt backtrackt+1; swapxt, xi; } } void backtrack int t { if t>n outputx;elsefor int i=0;i<=1;i++ { xt=i; if legalt backtrackt+1; } }void backtrack int t { if t>n outputx; else for int i=0;i<=1;i++ { xt=i; if legalt backtrackt-1; } }voidbacktrack int t{ if t>n outputx; else for int i=t;i<=n;i++ { swapxt, xi; if legalt backtrackt+1;}}10、解决0/1背包问题可以使用动态规划、回溯法和分支限界法,其中不需要排序的是动态规划 ,需要排序的是回溯法 ,分支限界法 ;11、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界,N皇后问题和0/1背包问题正好是两种不同的类型,其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题 ,只使用约束条件进行裁剪的是 N皇后问题 ;12、贪心选择性质是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别;13、矩阵连乘问题的算法可由动态规划设计实现;14.贪心算法的基本要素是贪心选择性质和最优子结构性质 ;15. 动态规划算法的基本思想是将待求解问题分解成若干子问题 ,先求解子问题 ,然后从这些子问题的解得到原问题的解;16.算法是由若干条指令组成的有穷序列,且要满足输入、输出、确定性和有限性四条性质;17、大整数乘积算法是用分治法来设计的;18、以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法 ;19、贪心选择性质是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别;20.快速排序算法是基于分治策略的一种排序算法;21.动态规划算法的两个基本要素是. 最优子结构性质和重叠子问题性质 ;22.回溯法是一种既带有系统性又带有跳跃性的搜索算法;23.分支限界法主要有队列式FIFO 分支限界法和优先队列式分支限界法;24.分支限界法是一种既带有系统性又带有跳跃性的搜索算法;25.回溯法搜索解空间树时,常用的两种剪枝函数为约束函数和限界函数 ;26.任何可用计算机求解的问题所需的时间都与其规模有关;27.快速排序算法的性能取决于划分的对称性 ;28.所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到 ;29.所谓最优子结构性质是指问题的最优解包含了其子问题的最优解 ;30.回溯法是指具有限界函数的深度优先生成法 ;31.用回溯法解题的一个显着特征是在搜索过程中动态产生问题的解空间;在任何时刻,算法只保存从根结点到当前扩展结点的路径;如果解空间树中从根结点到叶结点的最长路径的长度为hn,则回溯法所需的计算空间通常为 Ohn ;32.回溯法的算法框架按照问题的解空间一般分为子集树算法框架与排列树算法框架;33.用回溯法解0/1背包问题时,该问题的解空间结构为子集树结构;34.用回溯法解批处理作业调度问题时,该问题的解空间结构为排列树结构;35.旅行售货员问题的解空间树是排列树 ;三、算法填空1.背包问题的贪心算法void Knapsackint n,float M,float v,float w,float x{//重量为w1..n,价值为v1..n的 n个物品,装入容量为M的背包//用贪心算法求最优解向量x1..nint i; Sortn,v,w;for i=1;i<=n;i++ xi=0;float c=M;for i=1;i<=n;i++{if wi>c break;xi=1;c-=wi;}if i<=n xi=c/wi;}2.最大子段和: 动态规划算法int MaxSumint n, int a{int sum=0, b=0； //sum存储当前最大的bj, b存储bjfor int j=1； j<=n； j++{ if b>0 b+= aj ；else b=ai; ； //一旦某个区段和为负,则从下一个位置累和 ifb>sum sum=b;}return sum；}3.贪心算法求活动安排问题template<class Type>void GreedySelector int n, Type s, Type f, bool A{A1=true;int j=1;for int i=2;i<=n;i++if si>=fj{ Ai=true;j=i;}else Ai=false;}4.快速排序template<class Type>void QuickSort Type a, int p, int r{if p<r{int q=Partitiona,p,r;QuickSort a,p,q-1; //对左半段排序QuickSort a,q+1,r; //对右半段排序}}5. 回溯法解迷宫问题迷宫用二维数组存储,用'H'表示墙,'O'表示通道int x1,y1,success=0; //出口点void MazePathint x,int y{//递归求解:求迷宫maze从入口x,y到出口x1,y1的一条路径mazexy=''; //路径置为if x==x1&&y==y1 success=1; //到出口则成功else{if mazexy+1=='O' MazePathx,++y;//东邻方格是通路,向东尝试if success&&mazex+1y=='O' MazePath++x,y;//不成功且南邻方格是通路,向南尝试if success&&mazexy-1=='O' MazePathx,--y;//不成功且西邻方格是通路,向西尝试if success&&mazex-1y=='O' MazePath--x,y;//不成功且北邻方格是通路,向北尝试}if success mazexy=''; //死胡同置为}四、算法设计题1. 给定已按升序排好序的n个元素a0:n-1,现要在这n个元素中找出一特定元素x,返回其在数组中的位置,如果未找到返回-1;写出二分搜索的算法,并分析其时间复杂度;template<class Type>int BinarySearchType a, const Type& x, int n{//在a0:n中搜索x,找到x时返回其在数组中的位置,否则返回-1Int left=0; int right=n-1;While left<=right{int middle=left+right/2;if x==amiddle return middle;if x>amiddle left=middle+1;else right=middle-1;}Return -1;}时间复杂性为Ologn2. 利用分治算法写出合并排序的算法,并分析其时间复杂度void MergeSortType a, int left, int right{if left<right {//至少有2个元素int i=left+right/2; //取中点mergeSorta, left, i;mergeSorta, i+1, right;mergea, b, left, i, right; //合并到数组bcopya, b, left, right; //复制回数组a}}算法在最坏情况下的时间复杂度为Onlogn;3.N皇后回溯法bool Queen::Placeint k{ //检查xk位置是否合法for int j=1;j<k;j++if absk-j==absxj-xk||xj==xk return false;return true;}void Queen::Backtrackint t{if t>n sum++;else for int i=1;i<=n;i++{xt=i;if 约束函数 Backtrackt+1;}}4.最大团问题void Clique::Backtrackint i // 计算最大团{ if i > n { // 到达叶结点for int j = 1; j <= n; j++ bestxj = xj;bestn = cn; return;}// 检查顶点 i 与当前团的连接int OK = 1;for int j = 1; j < i; j++if xj && aij == 0 // i与j不相连{OK = 0; break;}if OK { // 进入左子树xi = 1; cn++;Backtracki+1;xi = 0; cn--; }if cn+n-i>bestn { // 进入右子树xi = 0;Backtracki+1; }}5. 顺序表存储表示如下：typedef struct{RedType rMAXSIZE+1; //顺序表int length; //顺序表长度}SqList;编写对顺序表L进行快速排序的算法;int PartitionSqList &L,int low,int high //算法10.6b{//交换顺序表L中子表L.rlow..high的记录,枢轴记录到位,并返回其所在位置, //此时在它之前后的记录均不大小于它.int pivotkey;L.r0=L.rlow; //用子表的第一个记录作枢轴记录pivotkey=L.rlow.key; //枢轴记录关键字while low<high //从表的两端交替地向中间扫描{while low<high&&L.rhigh.key>=pivotkey --high;L.rlow=L.rhigh; //将比枢轴记录小的记录移到低端while low<high&&L.rlow.key<=pivotkey ++low;L.rhigh=L.rlow; //将比枢轴记录大的记录移到高端}L.rlow=L.r0; //枢轴记录到位return low; //返回枢轴位置}void QSortSqList &L,int low,int high{//对顺序表L中的子序列L.rlow..high作快速排序int pivotloc;if low<high //长度>1{pivotloc=PartitionL,low,high; //将L.rlow..high一分为二QSortL,low,pivotloc-1; //对低子表递归排序,pivotloc是枢轴位置 QSortL,pivotloc+1,high; //对高子表递归排序}}void QuickSortSqList &L{//对顺序表L作快速排序QSortL,1,L.length; }。

《计算机数学基础》（第二版）习题参考答案习题1.11.42,23,42---x x ，1722++x x ，4682-+x x ，h x 234++。

2. （1）]14,6[,]3,2[-=-=R D 。

（2）]1,0[,]1,1[=-=R D 。

（3）),0[,),(∞+=∞+-∞=R D 。

（4）),0[,),(∞+=∞+-∞=R D 。

（5）]1,1[,),(-=∞+-∞=R D 。

3.（1）不同，因为定义域不同。

（2）不同，因为对应规则不同。

（3）相同，因为定义域和对应规则均相同。

4.（1）]2,2[-=D 。

（2）}1|{≠=x x D 。

（3）),(D ∞+-∞=。

（4）),(D ∞+-∞=。

图略5.（1）2010h T +-=。

（2）10k =。

（3）C 5︒-。

6.（1）有界；（2）有界；（3）无界；（4）有界。

7.（1）非奇非偶函数；（2）奇函数；（3）偶函数；（4）偶函数。

8.（1）周期函数，周期是π2；（2）非周期函数；（3）周期函数，周期是π。

习题1.21.（1）),(,)13(2))((223∞+-∞=-±+=±±g f D x x x x g f ； ),(,263))((2345∞+-∞=--+=∙fg D x x x x x g f ；}33|{,132))(/(/223±≠=-+=x x D x x x x g f g f 。

（2）]1,1[,11))((-=-±+=±±g f D x x x g f ；]1,1[,1))((2-=-=∙fg D x x g f ；)1,1[,11))(/(/-=-+=g f D xx x g f 。

2.（1）),(,62118))((2∞+-∞=++=g f D x x x g f ， ),(,236))((2∞+-∞=+-=f g D x x x f g ， ),(,88))((34∞+-∞=+-=f f D x x x x f f ，),(,89))((∞+-∞=+=g g D x x g g 。

大学计算机基础（第2版）习题参考答案第一章习题及参考答案一．单选题（附参考答案）(1) 我们讨论的计算思维中的计算一词，指英语中的：（a）computation (b) computing(c) computation and computing (d) neither computation no computing参考答案:C(2) 移动通信与地理信息系统的结合，产生了新的计算模式：(a)与位置有关的计算(b)与时间有关的计算(c)与空间有关的计算(d)与人群有关的计算参考答案:A(3) 当交通灯会随着车流的密集程度，自动调整而不再是按固定的时间间隔放行时间时，我们说，这是计算思维___________的表现。

(a)人性化(b)网络化(c)智能化(d)工程化参考答案:C(4) 计算思维服务化处于计算思维层次的：(a)基础层次(b)应用层次(c) 中间层次(d) 工程技术层参考答案:B(5) 计算思维的智能化处于计算思维层次的：(a)基础层次(b)应用层次(c) 顶层层次(d) 工程技术层参考答案:D(6) 以下列出的方法哪一项不属于科学方法：(a) 理论(b) 实验(c) 假设和论证(d) 计算参考答案:C(7) 以下列出的哪一项不属于公理系统需要满足的基本条件？(a) 无矛盾性(b) 独立性(c) 完备性(d) 不完备性参考答案:D(8) 以下哪一项不属于伽利略的实验思维方法的基本步骤之一：(a)设计基本的实验装置(b)从现象中提取量的概念(c)导出易于实验的数量关系(d)通过实验证实数量关系参考答案:A(9) 对于实验思维来说，最为重要的事情有三项，但不包括以下的：(a) 设计实验仪器(b)制造实验仪器(c) 保证实验结果的准确性(d) 追求理想的实验环境参考答案:C(10) 计算思维最根本的内容为：(a) 抽象(b) 递归(c) 自动化(d) a和c参考答案:D(11) 计算机科学在本质上源自于：(a) 数学思维(b) 实验思维(c) 工程思维(d) a和c参考答案:D(12) 计算理论是研究使用计算机解决计算问题的数学理论。

习题一一、用适当容填空1. 机器2. 1283. 24.19465. ①读操作②写操作6. 多媒体7. ①取指令②执行指令8. 地址总线9. 源程序 10. ①系统软件②应用软件 11. ①82 12. 2213. ①操作码②操作数 14. ①R-1 15. 8 16. 二进制17. 中小规模集成电路 18. 程序 19. ①系统②用户③计算机20. 快 21. CPU〔中央处理器22. ①控制器②运算器③存储器④输入设备⑤输出设备⑥控制器⑦运算器23. 现行程序的指令和数据 24. 1024×1024 25. 操作系统26. ①字长②主频③运算速度④存储容量⑤存储周期27. ①数据流②控制流 28. ASCⅡ 29. 830. ①硬件五大基本功能模块②采用二进制③存储程序控制31. 高级 32. 只读型光盘 33. 存 34. 机码二、从参考答案中选择一个最佳答案1．A 2. C 3. A 4. B 5. B 6. A 7. C 8. B 9. C 10. B11. B 12. C 13. C 14. B 15. D 16. B 17. D 18. B 19. C 20. B 21. D 22. B三、从参考答案中选择全部正确答案1．AD 2. AC 3. BDE 4. AB 5. ACD 6. BD7. BDE 8. BCD 9. ABC 10. C DE习题二一、用适当容填空1. 主板2. ①控制器②运算器3. ①部②系统③外部〔按位置和功能划分①数据②地址③控制〔按传输信息的不同4. 分辨率5. ①CRT〔阴极射线管显示器②LCD〔液晶显示器二、从参考答案中选择一个最佳答案1．A 2.B 3.D 4.D 5.B 6.B 7.B 8.A 9.D 10.A1． AB 2． ABD 3． ABC 4．BCD 5． BCD6．BC 7． ACE 8．ABE 9．BCD 10．ACD习题三一、用适当容填空1．硬件软件2．软件硬件3．作业管理进程管理存储管理文件管理设备管理4．单道批处理系统多道批处理系统5．共享性6．进程以不可预知的速度向前推进程序完成时间不可预知7．CPU 输入输出设备8．实时性高可靠性9．系统吞吐量人机交互10．批处理11．联机12．通道中断机制13．进程14．进程控制块15．动态性并发性16．动态的静态的17．就绪态运行态等待态18．系统态或管态用户态或目态用户19．存储分配存储保护虚拟存储器管理地址映射20．程序局部性21．缓冲区管理设备分配设备控制22．独占型设备共享型设备23．缓和CPU和I/O设备之间速度不匹配的矛盾减少对CPU的中断频率和放宽对CPU响应时间限制24．虚拟设备25．系统文件库文件用户文件26．逻辑结构物理结构27．流式文件28．字符型设备块设备1．C 2．A 3．A 4．A 5．B 6．B7．B 8．D 9．B 10．A 11．A三、从参考答案中选择全部正确答案1．ABD 2．BCE 3．CD 4．ABC5．CE 6．ABC 7．BCD习题四一、用适当容填空1.①计算机及辅助设备②通信设备③传输线路④网络软件⑤资源共享以及信息通信2. ①局域网②广域网③资源子网④通信子网3. TCP/IP4.①服务器②客户机5. 超文本传输协议6.①模拟信号②频带传输7.①〔,edu,mil,net,gov②〔cn,us,jp8. 统一资源定位标识〔URL9.①②ftp<telnet,mailto,news,gophee>10. 连接Internet主要方式有①终端方式、②拨号方式、③局域网方式和④宽带网方式。

《大学计算机基础》课后题答案完整版习题一一、用适当内容填空1. 【机器】语言是计算机唯一能够识别并直接执行的语言。

2. 标准ASCⅡ字符集总共有【128】个编码。

3. 在计算机内用【2】个字节的二进制数码代表一个汉字。

4. 第一台电子计算机ENIAC诞生于【1946】年。

5. 对存储器而言有两种基本操作：【读操作】和【写操作】。

6. 【多媒体】技术是处理文字、声音、图形、图像和影像等的综合性技术。

7. 执行一条指令的时间称为机器周期，机器周期分为【取指令】周期和【执行指令】周期。

8. 用于传送存储器单元地址或输入/输出接口地址信息的总线称为【地址总线】。

9. 用计算机高级语言编写的程序通常称为【源程序】。

10. 计算机软件系统由【系统软件】和【应用软件】两部分组成。

11. 八进制数整数（从右数）第三位的位权是【82】。

12. 二进制数10110转换为十进制数是【22】。

13. 一个指令规定了计算机能够执行一个基本操作，它的组成包括【操作码】和【操作数】。

14. 对于R进制数来说，其基数（能使用的数字符号个数）中最大数是【R-1】。

15. 3位二进制数可以表示【8】种状态。

16. 在计算机内部，数字和符号都用【二进制】代码表示。

17. 第三代电子计算机采用的电子器件是【中小规模集成电路】。

18. 按相应的顺序排列、使计算机能执行某种任务的指令集合是【程序】。

19. 操作系统是一种【系统】软件，它是【用户】和【计算机】的接口。

20. 计算机内存的存取速度比外存储器【快】。

21. 计算机硬件中最核心的部件是【CPU（中央处理器）】。

22. 计算机由【控制器】、【运算器】、【存储器】、【输入设备】和【输出设备】5部分组成，其中【控制器】和【运算器】组成CPU。

23. 计算机在工作时,内存储器用来存储【现行程序的指令和数据】。

24. KB、MB、GB都是存储容量的单位，1GB=【1024×1024】KB。

Program算法设计与分析基础中文版答案习题5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:如果d整除u和v, 那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。

故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次..对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.(农夫过河)P—农夫 W—狼 G—山羊 C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法 DectoBin(n).n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进.算法 MinDistance(A[0..n-1])n-1]a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count[]4.(古老的七桥问题)习题1.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度.a.删除数组的第i个元素(1<=i<=n)b.删除有序数组的第i个元素(依然有序)hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array’s element., 0 for an array of positive numbers ) to mark the i th position is empty. (“lazy deletion”)第2章习题7.对下列断言进行证明:(如果是错误的,请举例)a. 如果t(n)∈O(g(n),则g(n)∈Ω(t(n))b.α>0时,Θ(αg(n))= Θ(g(n))解:a. 这个断言是正确的。

《计算机算法设计与分析》习题及答案一．选择题1、二分搜索算法是利用（ A ）实现的算法。

A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（ A ）。

A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（ A ）的一搜索方式。

A、分支界限法B、动态规划法C、贪心法D、回溯法4. 回溯法解旅行售货员问题时的解空间树是（ A ）。

A、子集树B、排列树C、深度优先生成树D、广度优先生成树5．下列算法中通常以自底向上的方式求解最优解的是（ B ）。

A、备忘录法B、动态规划法C、贪心法D、回溯法6、衡量一个算法好坏的标准是（ C ）。

A 运行速度快B 占用空间少C 时间复杂度低D 代码短7、以下不可以使用分治法求解的是（ D ）。

A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题8. 实现循环赛日程表利用的算法是（ A ）。

A、分治策略B、动态规划法C、贪心法D、回溯法9．下面不是分支界限法搜索方式的是（ D ）。

A、广度优先B、最小耗费优先C、最大效益优先D、深度优先10．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。

A、备忘录法B、动态规划法C、贪心法D、回溯法11.备忘录方法是那种算法的变形。

（ B ）A、分治法B、动态规划法C、贪心法D、回溯法12．哈夫曼编码的贪心算法所需的计算时间为（ B ）。

A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）13．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。

A、最小堆B、最大堆C、栈D、数组14．最长公共子序列算法利用的算法是（ B ）。

A、分支界限法B、动态规划法C、贪心法D、回溯法15．实现棋盘覆盖算法利用的算法是（ A ）。

A、分治法B、动态规划法C、贪心法D、回溯法16.下面是贪心算法的基本要素的是（ C ）。

A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解17.回溯法的效率不依赖于下列哪些因素（ D ）A.满足显约束的值的个数B. 计算约束函数的时间C.计算限界函数的时间D. 确定解空间的时间18.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ）A．递归函数 B.剪枝函数 C。

4.2在下列情况下求解递归关系式T(n)= ()2(/2)()g n T n f n ⎧⎨+⎩ 否则足够小n当①n=2k g(n)= O (1)和f(n)= O (n)；②n=2k g(n)= O (1)和f(n)= O (1)。

解: T(n)=T(2k )=2 T(2k-1)+f(2k )=2(2 T(2k-2)+f(2k-1)) +f(2k ) =22T(2k-2)+21 f(2k-1)+ f(2k ) =……=2k T(1)+2k-1f(2)+2k-2f(22)+…+20f(2k ) =2k g(n)+ 2k-1f(2)+2k-2f(22)+…+20f(2k ) ①当g(n)= O (1)和f(n)= O (n)时，不妨设g(n)=a ，f(n)=bn ，a ，b 为正常数。

则T(n)=T(2k )= 2k a+ 2k-1*2b+2k-2*22b+…+20*2k b =2k a+kb2k=an+bnlog 2n= O (nlog 2n) ②当g(n)= O (1)和f(n)= O (1)时，不妨设g(n)=c ，f(n)=d ，c ，d 为正常数。

则 T(n)=T(2k )=c2k + 2k-1d+2k-2d+…+20d=c2k +d(2k -1)=(c+d)n-d= O (n)4.3根据教材中所给出的二分检索策略，写一个二分检索的递归过程。

Procedure BINSRCH(A, low, high, x, j) integer midif low ≤high thenmid ←⎣⎦2/)(high low +if x=A(mid) then j ←mid; endifif x>A(mid) then BINSRCH(A, mid+1, high, x, j); endif if x<A(mid) then BINSRCH(A, low, mid-1, x, j); endif else j ←0; endif end BINSRCH4.5作一个“三分”检索算法。

部分习题参考答案第1章二、1. E 2. C 3. B 4. BDEFLJ 5. C 6. ABEFH 7. BD 8.D 9. A 10. C 11. A 12.B第2章一、4. 1101100100011110100000000000.01111.00110.1017. 10 55 157 0.625 0.3125 0.8125 2.25 10.12510. (233.154)8 (1252.144)8 (9B.36)16 (2AA.32)1611. 111101.110001010 11001001010.11000011111113. 设以一个字节来存储，最高位为符号位，其中0.567和-0.567为十进制数01100100 01100100 0110010011100100 10011011 1001110001111100 01111100 0111110011111100 10000011 1000010001001000 01001000 0100100011001000 10110111 10111000二、1. B 2. C 3. B 4.A 5.A第3章二、1.主存、辅存、容量、存取周期、寄存器、高速缓冲存储器、主存、辅存2.超级计算机、大中型计算机、小型计算机、工作站、微机、嵌入式计算机、MIPS3.运算器、控制器、主频、字长、外频4. 频率5. 接收数据包、发送数据包6.易失、RAM、读取7.FAT328. 150K9. RAM 10.人、计算机11. Universal Serial Bus三、1.B 2.C 3.AC 4.CDEF 5.C 6.B 7.D 8.D 9.D 10.A 11.D 12.B 13.D 14.B 15.B第4章二、1. B 2. C 3. D 4.D 5.C 6.C 7.D 8. D 9. B 10. D 11. C第5章二、1.A 2. B 3. B 4.C 5.D 6.C 7.C 8. D 9. C 10. C 11. B三、1. 文件 2. 属性 3.文件 4.* ? 5.文件系统6.名字7.文件夹8. 图形、文本、可控制9.交换技术、外存、外存、分区、分页、低一些第6章二、1. 顺序、条件、循环 2. 当型、直到型3.机器、汇编、面向过程、面向对象 4. 封装、继承、多态性 5. 自然语言、流程图、伪代码 6.逻辑、代码、文档、运行和维护7.理解问题、设计方案、执行方案、检验方案8. 顺序、循环9.一对一10.一对多11.存储单元、变量12.不同、链13. 先进先出、后进先出14.入栈、出栈、满、空三、1.D 2. D 3. C 4.C 5.A 6.A第7章一、1.B 2. A 3. B 4.D 5.A 6.A 7. B 8 . A 9.C第8章一、1.D 2.D 3.B 4.C 5.B 6.B 7.C 8. B 9.D 10.D 11.C 12. D 13.D 14.B 15.B 16. A17.A 18. C 19.B 20. A 21. AD 22.ACDF 23.ACD二、1.× 2.× 3.× 4.√ 5. × 6.√7.√8.×9.×10.√11.√12.√13.√14. √15.×16.√17.√18.√19.×20.√21.√22.√23.×24.√第9章一、1.C 2.D 3.D 4.D 5.C 6.D 7.D 8. A 9.D 10.A 11.C 12. D 13.D 14.B 15.C16. D 17.B 18. D 19.C 20. C 21. D 22.AB 23.C 24.D 25.D 26.A二、1..√ 2..√ 3.√ 4.√ 5. × 6.×7.√8.×9.√10.×11.×12.×13.√14.×15.×16.×17.×18.×19.×20.×21.×22.×23.×第10章一、1.C 2.C 3.C 4.C 5.C 6B 7.C 8.A 9.C 10.B 11.D 12. D 13.A第11章二、1.D 2.C 3.C 4.B 5.C 6.D 7.B 8. C三、1.ABC 2.BE 3.AEIJ 4.BD四、1.√2.√3.×4.×5.×6.×7.×8.√9.×10.×11.×12.√13.×14.×。

Program算法设计与分析基础中文版答案习题1.15..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint:根据除法的定义不难证明:如果d整除u和v, 那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。

故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint:对于任何形如0<=mgcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次) b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次) gcd(5,8)习题1.2 1.(农夫过河)P—农夫 W—狼 G—山羊 C—白菜 2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法 //输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*c If D>0temp←2*ax1←(-b+sqrt(D))/temp x2←(-b-sqrt(D))/temp return x1,x2else if D=0 return –b/(2*a) else return “no real roots” else //a=0if b≠0 return –c/b else //a=b=0if c=0 return “no real numbers” else return “no real roots”5. 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法 DectoBin(n)//将十进制整数n转换为二进制整数的算法 //输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中 i=1while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; }while i!=0 do{ print Bin[i]; i--; }9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1]) //输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.31. 考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表‖60,35,81,98,14,47‖排序b.该算法稳定吗?c.该算法在位吗? 解:a. 该算法对列表‖60,35,81,98,14,47‖排序的过程如下所示:b.该算法不稳定.比如对列表‖2,2*‖排序c.该算法不在位.额外空间for S and Count[] 4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i个元素(1<=i<=n)b.删除有序数组的第i个元素(依然有序) hints:a. Replace the ith element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array’s element(e.g., 0 for an array of positive numbers ) to mark the ith position is empty. (―lazy deletion‖)第2章习题2.17.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n)∈O(g(n),则g(n)∈Ω(t(n))b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断言是正确的。