内蒙古工业大学计算机导论习题作业答案

欧拉路径与欧拉回路的判定条件？在一幅图中如果能找到一条只通过每条边一次的路径叫做欧拉路径。如果该路径的起点与终点是同一点，那这条路径叫做欧拉回路。 课后题 6.（1）将图像化成节点 可知，a有10条路，b有6条路， c有7条路， d有7条路；所以该图不可能是欧拉回路，所以不能经过15座桥之后回到出发点。该问题问的是图示是否存在欧拉路径。 根据欧拉路径的定义。符合，所以我们可以找到这样的路径。 D= A=D=A=D=A=C=A=C=A=B=D=B=C=B=C=B=C。 7. 梵天塔。利用递归思想可知n个盘子的汉诺塔问题需要移动的盘子数是n-1个盘子的汉诺塔问题需要移动的盘子数的2倍加1如此 可推算出移动盘子的总次数。为2的64次方-1，因为电脑的计算能力是有限的，正如书上所言，假设计算机以每秒1000万个盘子速度移动，也需要花费大约58490年。所以说理论上可行的计算问题，实际上不一定行。 什么是NP问题？ 举例说明。 NP是在多项式时间内可以验证的问题。 P是在多项式时间内可以求解的问题。P类问题采用的是确定性算法，而NP类问题采用的是非确定性算法。确定性算法是非确定性算法的一种特例。因此P=NP;通俗地说，一个判定问题属于：对回答为肯定的实例，存在一个有效的“证明”，且对该“证明”的有效性的检验能够在关于原实例规模的多项式时间内完成。一个自然数是否质数问一个自然数是否合数。都属于问题。 请找出合数41891的两个真因子。 （1）真因子，就是该数的一个因数，所以我们可以简化运算范围，求出根号41891的近似值，根号41891大约为205， 又因为41891的个位数是1，是奇数，则它是奇数与奇数的乘积。 这样的话只要查看奇数即可。205中有103个奇数在除去1和205本身就有101个数，然后除去由奇数与奇数（因为真因子是只有1和本身的约数的数）（其中奇数1不算）相乘的数。然后求出真因子。 结果为47和210.利用a2-b2=合数的方法，找到两个数相减的结果是合数41891然后对a，b两个数再次进行求真因子的方法。 结果为210和47。19 简述找零问题、背包问题、贪婪算法。贪婪算法是一种传统的启发式算法，他采取逐步构造最优解的方法，在每一步决策中采取最优的方法（即在每一步中看到最好的方法）贪婪算法是从局部到整体的解决方案。 但这是从细节来看的，所以可以说是一种蒙的概念， 也不能保证问题结局是最优的，有可能蒙对其解为最优解，有可能蒙错不是最优解。找零问题例如在超市，收银员用最少的钞票找顾客零钱。这是典型的贪婪算法。（对每一步采取最优解）背包问题的叙述； 给定N个物品和一个背包，设a为物品b的重量，v为其价值，c为背包的总重量容量，尽可能的使装入的物品总价最大。26， 查资料，了解更多图灵测试的实例，并给自己设计一个例子。图灵测试就是研究计算机是否能思维。是否能像人一样，对于这个问题，现在，我感觉这是不可能的，因为电脑运行的是程序。程序是有人编出来的。但知道现在就是没有电脑自己编程续的。假如电脑能够根据自己储存的的资料中自己创造程序去执行，那么电脑就是能够思维啦。（只是个人观点）例子。 我问 ； 我先讲一篇语文课文。（此处省略很多字）。根据上面的数学知识请你求2*3等于多少？如果是人的话，会说这是一篇语文啊，不是数学。如果是电脑的话，就可能说2*3=6.28，举例说明计算机博弈问题。 设计程序使计算机下国际象棋、跳棋、 1913年，数学家策墨洛(E.Zermelo) 发表了关于集合论在象棋博弈理论中的应用(On an Application of Set Theory to Game ofChess)的著名论文。现代数学出现了一个新的理论-博弈论。1970年开始，ACM每年举办一次计算机国际象棋锦标直到1994年(1992年中断过一次)，每年产生一个计算机国际象棋赛冠军，1991年，冠军由IBM的“深思(DeepThought)”获得。就像中国象棋，国际象棋，跳棋等。就是将所有的情况都找出来。进行下棋。 1.哥尼斯堡七桥寻找走遍这7座桥，且每座桥只许走过一次，最后又回到原出发点的路径。将问题本质考虑，忽视问题非本质的东西（如桥的长度，宽度等），从而将哥尼斯堡七桥问题抽象为一个数学问题。 2.梵天塔(1) 每次只能移动一个盘子。(2) 盘子只能在3根柱子上来回移动，不能放在他处。(3) 在移动过程中，3根柱子上的盘子必须始终保持大盘在下，小盘在上递归问题：是讲一个较大问题归约为一个或多个子问题的求解方法，而这些子问题比原问题简单，且在结构上与原问题相同。3. 算法复杂性中的难解性问题（1）算法复杂性包括算法的空间以及时间两方面的复杂度问题，梵天塔问题主要讲的是算法的时间复杂度。（2）难解性问题：一个问题求解算法的时间复杂度大于多项式（如指数函数）时，算法的执行时间将随n的增加而急剧增长,以致即使是中等规模的问题也无法求解，于是将这一类问题成为难解性问题 4.P类问题和NP类问题 P类问题和NP类问题：在计算复杂性理论中，将所有可以在多项式时间内求解的问题称为P类问题，而将所有在多项式时间内可以验证的问题成为NP类问题。p类问题采用的是确定性算法，NP类问题采用的是非确定性算法，而确定性算法是非确定性算法的一中特例，一次，可以断定P属于NP.5.证比求易算法 证比求易算法，顺序算法和并行算法掌握对于难解性问题，单纯地提高计算机系统的速度是远远不够的，而降低算法复杂度的数量级才是最关键的问题，根据阿姆达尔定律可知最多中能提高100倍的处理速度。6.旅行商问题与组合爆炸问题这类问题是一个NP完全性问题，必须要解决的问题需要我们找到一个河里的办法，就是寻找其启发式算法，近似算法，概率算法等.7.生产者消费者问题与哲学家共餐问题 （1）生产者消费者问题：找零问题，背包问题这一类问题可以用启发式的贪婪算法来处理额典型问题。（就是用最短的时间，最少的步骤，最低的投入换取最大的价值）并发程序设计中进程同步的最基本问题对多进程提供(或释放)以及使用计算机系统软硬件资源的机制(2)哲学家共餐问题：类似的读写这问题，睡眠的理发师问题程序并发执行时进程同步的两个问题以上两个方面的问题，其实反映的是程序并发执行时进程同步的两个问题，一个是死锁(Deadlock)，另一个是饥饿(Starvation)。哲学家共餐问题实际上反映了计算机程序设计中多进程共享单个处理机资源时的并发控制问题。8.GOTO语句的问题以及程序设计方法学滥用GOTO语句是有害的，完全禁止也不明智，在不破坏程序良好结构的前提下，有控制地使用一些GOTO语句，就有可能使程序更清晰，效率也更高。程序设计方法学是对程序的性质及其设计的理论和方法进行研究的学科，是计算机科学与技术方法论中的重要内容9.人工智能的若干哲学问题图灵测试: 图灵测试”只是从功能的角度来判定机器是否能思维，也就是从行为主义角度来对“机器思维”进行定义 尽管图灵对“机器思维”的定义是不够严谨的，但他关于“机器思维”定义的开创性工作对后人的研究具有重要意义，“中文屋子”的寓意形式化的计算机仅有语法，没有语义。因此，西尔勒认为，机器永远也不可能代替人脑！10.博弈问题博弈问题属于人工智能中一个重要的研究领域。从狭义上讲，博弈是指下棋、玩扑克牌、掷骰子等具有输赢性质的游戏；从广义上讲，博弈就是对策或斗智。计算机中的博弈问题，一直是人工智能领域研究的重点内容之一。深蓝”的胜利北京时间1997年5月3日到11日，在美国纽约公平大厦，“深蓝”与国际象棋冠军卡斯帕罗夫交战，前者以两胜一负三平战胜后者。 课后作业3.1 以“学生选课”为例，分析人们对客观世界的认识过程。答：“学生选课”管理系统的研制过程蕴含了人们对客观世界从感性认识（通过E-R图，实现对例子的抽象）到理性认识（在关系数据理论的指导下，通过建立更为适合的关系模型而实现对例子的理性认识），再由理性认识回到实践（在实现对“例子”的感性认识和理性认识后，编写程序完成“学生选课”管理信息系统的工作）中来的科学思维方式2概念模型：概念模型用于信息世界的建模，是客观世界到信息世界的抽象。（1） 关系模型：关系模型支持的是一种二维表结构的数据模型，它由关系数据结构、关系数据操作和关系数据的完整性约束条件3部分组成。1.。存在插入异常。存在删除异常。存在数据冗余。这是第一范式。学号姓名年龄性别系名系主任这是第二范式。学号姓名年龄姓名系名系主任这是第三范式。学号姓名年龄性别系名系名系主任数据冗余可解决2. R表示向右转一个，l表示想左移一个，n表示不动。Bbbbbbb 1 1 1 0 0 1 0 1 bbbbbb （由于最右为1所以q1状态为q1 1 0 Lq3） Q1Bbbbbbb 1 1 1 0 0 1 0 0 bbbbbb （由于接下来为0所以 为 q3 0 0 L q2） Q3Bbbbbbb 1 1 1 0 0 1 0 0 bbbbbb （由于接下来为1所以为 q2 1 0 L q2） Q2Bbbbbbb 1 1 1 0 0 0 0 0 bbbbbb (接下来为0所以为 q2 0 0 L q2) Q2Bbbbbbb 1 1 1 0 0 0 0 0 bbbbbb （由于接下来为 0 q2 0 0 L q2） Q2Bbbbbbb 1 1 1 0 0 0 0 0 bbbbbb （接下来为1 q2 1 0 L q2） Q2Bbbbbbb 1 1 0 0 0 0 0 0 bbbbbb （接下来为1 q2 1 0 L Q2） Q2Bbbbbbb 1 0 1 0 0 0 0 0 bbbbbb （接下来为1 q2 1 0 L Q2） Q2Bbbbbbb 0 0 1 0 0 0 0 0 bbbbbb Q2 b b n q4 结束。 0 0 0 0 0 0 0 0。3 答：该计算机有216个不同的地址空间； 一次总线传送的数据位数是32位，最大值是232-1。3. 如果一个指令系统有12 条指令，请问操作码至少需要 4 位，操作码有5位，最多可以设计 32 条指令。 （2的操作码位数的方）。4. 9000停机(halt)。 6205 将二号寄存器向左移5位，用0填充腾空的数。(shl 2,5) 5123将寄存器2 和寄存器3用补码相加存放在寄存器1中。(Add 1,2,3)12A0将主存A0单元中的数取出，存放在寄存器2中。(Load 1,A0)3312 将寄存器3中的数取出存入地址为12的单元中。(Store 3,12)6 a. 20A0 b.6103 C.10E8 d. 8100 e.5201 f.31D27 13AA. 变化为AA中的数消失。22AA 变化为AA中的数不变30AA 变化为AA中的数变为寄存器0中的数50AA 变化为AA中的数不变82AA 变化为AA中的数不变。8 执行指令8000 后 程序计数器中的值为00.9 因为到最后出现9000的指令，所以终止。10A. 。 11A0（将A0单元的数取出，存入寄存器1中） 5321 （将寄存器2和寄存器1的补码和存入寄存器3中） 33A0 (将寄存器3中得值存入地址A0中) 9000 （结束）B. 【A0】=40; R1=20; R2=20; R3=401110A0(将A0里的值存入寄存器0中 )6001（将寄存器0中的数左移1位，移位后，用零填充腾空的）30A0（将寄存器中的数取出，存入A0里）9000 （停机）A. 10B. 改为02时，为100 改为03，为1000C 10倍D 改为07 为10000000 改为08 =时 为1000000001220A8 （将数A8(十六进制数)存入寄存器0中）21A8 （将数A8存入寄存器1中）2220 （将数20存入寄存器2中）5301 （将寄存器0和寄存器1中的补码之和给寄存器3）5523 （将寄存器2和寄存器3的补码之和给寄存器5）9000 （停机）A 需要6微秒B 如上。C 寄存器5的值为20+A8+A8D 操作码为1是地址 操作码为2是十六进制数。 13 a。5312 3320 b.1225 5312 c. 3100 4021 120014A 5312 3320 Add 3,1,2 Store 3,20B 1225 5312 Load 2,25 Add 3,1,2C 3101 4021 2201 Store 1,01 Mov 2,1 Load 2,0115100E (将0E单元的数取出存入寄存器0中)7000（将寄存器0中得数去反，再存到寄存器0中）3008 （将寄存器0中得数取出，存入08的单元中）110F （将单元0F中的数取出，存入寄存器1中）7100 （将寄存器1中的数取反，在存入寄存器1中）3110 （将寄存器1中得数存入10地址）9000（停机）16LOAD R0,01 (将数01存入寄存器0)LOAD R1,FF (将数FF存入寄存器1)lLOAD R2,02 (将数02存入寄存器2)LABELI:ADD R3,R1,R0 （定义lable1为寄存器1和寄存器0补码之和凡在寄存器3中）JMP R3,LABEL2 (如果寄存器3与寄存器0中的值相等，则将label2(由于最后为停机)存入程序计数器中停机）ADDR4,R1,R2 （将R1和R2 的值之和凡在R4中）JMP R4,LABLE2 (如果寄存器4与寄存器0的值相等的，则将LABLE2由于最后为停机)存入程序计数器中停机）存入程序计数器中)SHL R0,01 (将寄存器0向左移1位，用0填充腾空的位)JMP R2,LABLE2 (如果寄存器2与寄存器0的值相等，则将LABLE2（由于最后为停机)存入程序计数器中停机）存入程序计数器中)SHL R0,08 (将寄存器0向左移8位，用0填充腾空的位)NOT R0 (将寄存器0中的数取反在存入)JMP R1,LABLE1 （如果寄存器1与寄存器0的值相等，则将LABLE1LABLE2:HALT （定义lable2为停机）B 200121FF2202Lable2:531083停机541284停机600182停机6008700081到531017 S NP VP N VP N V S N V NP VP N V N VP N V N V NP N V N V N 他 V N V N 他 教 N V N 他 教 我 V N 他 教 我 学 N 他 教 我 学 英语 18（1） 概念模型：概念模型用于信息世界的建模，是客观世界到信息世界的抽象。（2） 关系模型：关系模型支持的是一种二维表结构的数据模型，它由关系数据结构、关系数据操作和关系数据的完整性约束条件3部分组成。19学号姓名年龄性别201320201029201320201002201320201003201320201004201320201005201320201006学号课程号成绩201320201029201320201001201320201002201320201003201320201004201320201005 课程号成绩 第四章课后练习4.5 设e=1+1/1！+1/2!;试分别用自然语言，流程图，和伪代码写出求解e的近似值的算法。自然语言。将阶乘看作一个整体，然后随着阶乘的增加就可表示为上一阶乘乘以下一个数。然后将这些阶乘分之一看作一个整体，则可表示为整体加上下一个阶乘分之一。设阶乘分之一的和为s，阶乘表示为a，一直加到n的阶乘分之一。流程图。设s=0； a=1； 输入一个n值，假设n为100；建立一个循环，有两个循环，分为外循环和内循环。外循环控制的是有多少个阶乘分之一的，内循环控制的是阶乘到另一个阶乘，然后在求和。第三方是水电费是谁的 设 设 流程图：I=nI=I+1X=X+1/I I=1 X=0 开始 结束 N 伪代码：BEGIN0=X1=I Do x=x+1/1 I=i+1While(in)Print xEnd4.8 就“兔子问题”而言，一对兔子14个月内可繁殖成多少对兔子？这是斐波那契数列，所以根据其公式。即可求出。0 1 1 2 3 5 8 13 21 34 55 89 144 233. 所以为233对。4.11 采用折半搜索算法在一个有10000件商品的超市中查找1件特定的产品，为什么最多子需要14次？根据书上的折半搜索算法的介绍可知。2的14次方为16384且2的13次方为8192；10000处于这两个数之间，所以最多需要14次。4.12 设数组A有9个元素，分别是13,42,25,106,87,102,91,49,17.请采取归并排序的算法对该数组按升序进行排列。13,42,25,106,87102,91,49,1713,4225,106,87102,9149,171342251068710291491713,4225,10687,10217,49，9113,25,42,10617，49,87,91,10213,17,25,42,49,87,91,102,1064.13 给定4输入正排序网络如图所示。（1） 使用具体自然数N=0,1,2,3，n验证之；（2） 解释其工作原理； 4个数为1，2，3，4此4输入倒排序网络分为3个阶段，第一阶段t1中两个2输入倒排序网络并行计算，第二阶段t2中同样有两个倒排序网络并行计算，第三阶段t3中也是两个2输入倒排序网络并行计算，最后倒排序输出为1,2,3,4 工作原理，分为六个阶段中都为 一个二输入正排序网络工作，最后输出为1234.4,14 给定4输入倒排序网络（1） 使用具体自然数N=1,2,3，n验证之（2） 是解释其工作原理。（1）Comp3Comp2Comp1 4 4 3 3Comp6Comp5Comp4 2 2 1 1 （2）分为3个阶段，每个阶段都有一个2输入正排序和一个2输入倒排序两个网络工作，最后输出为43214.15 从8个数中找出最大的两个数的网络如图所示（1） 使用具体自然数N=1,2,N验证之（2） 试解释其工作原理。Comp4Comp3Comp2Comp18 87 7Comp6Comp565Comp10Comp9Comp8Comp743Comp12Comp1121（2）分为4个阶段，第一阶段有两个2输入正排序，与两个2输入倒排序网络工作，第二阶段有4个2输入倒排序网络工作，第三阶段有一个2输入正排序，与一个2输入倒排序网络工作，第四阶段为两个正排序网络工作，结果为87.4.16 Google将网页分成几个等级？把自己网站的PR值定为多少？将网页分为10个等级。PR为十，因为我将来的网站是最受欢迎的。4.21 试想在除计算机学科以外的领域中，那些案例可以用线性表，栈，队列，和树这样的概念来描述。？ 在大公司中，职位的形态可以用树来描述。 线性表用每个成员的信息的总合来形容。栈可以用每个职员的工作年龄（看一看谁的经验多）队列可以看成那个职员的任务完成量。4.23假设一空栈，首先数值3A入栈，然后数值2B.8C依次入栈，随后执行一次出栈操作，最后数值9D，8E依次输入。 3A 2B 9D 8E 3A 2B 8C 1. 2. 执行出栈操作后取出的数据为8C.4.26 假设一仅含数据8A的队列，8B和2C一次入列，然后执行一次出队操作，最后数据7D和6E依次入队。1 8A 8B 2C 出队操作变为 8E 2C 7D 6E 2 取出的数据为8A.4.28 设某一含有四个节点的树形结构，节点中的数据分别为A3 3B 8C D7 。已知A3 8C为兄弟关系，而D7 为A3的子节点。请问；该树中的叶子节点有哪些。根结点有哪些。 3B A3 8C D7叶子节点为 D7 8C 根节点为 3B4.29 请列出下面数组的分别按照行主序，列主序，的方式在主存中的存放方式。 行主序 5E 6A C5 8C 9B B4 7E B3 55 列主序 5E 8C 7E 6A 9B B3 C5 B4 554.39 如书上120页所说的，若移走，则将刚开始的数据“删除”如要插入1项，则在队尾处开辟新的存储空间。所以首地址为11 队尾为16.4.40、1。因为储存在 (队尾) （队头） 队头为75队尾为72. 71 72 73 74 75 76 77 78 4D 9E 00 00 36 3B 82 4C2 会出现异常的。4.43。 #includeInt main()Int a10,b;For(b=0;b=0;b-)Printf(“%d”,ab);Return 0;4.44 如果我们将名字存放在同一个栈，那么每一个元素的内存的大小不同，那么这不利于输出查找。 所以利用储存地址的栈既可以就可以方便的找到结果。4.45 80 00 81 00 82 00 83 00 84 00 85 00 86 00 87 00 88 00 89 00 8A 00 8B 36 8C 00 8D 00 8E 79 8F 71 70 00 71 78 72 73 73 68 74 75 75 57 76 77 77 45 78 8B 79 98 7A 8E 7B 00 7C 00 7D 00 7E 00 7F 004.46 00 00 01 00 02 F5 03 00 04 00 05 00 06 00 07 68 08 D4 09 00 0A 00 0B 00 0C 00 0D 00 0E 000F 00 F0 00 F1 00 F2 00 F3 00 F4 00 F5 00 F6 00 F7 00 F8 00 F9 00 FA 00 FB CD FC 02 FD 00 FE 00 FF 00 D0 00 D1 00 D2 00 D3 00 D4 7C D5 DA D6 00 D7 00 D8 00 D9 00 DA 8A DB FB DC 00 DD 00 DE 00 DF 00 C0 00 C1 00 C2 00 C3 00 C4 00 C5 00 C6 00 C7 00 C8 27 C9 07 CA 00 CB 00 CC 00 CD 00 CE 00 CF 004.47 D2-B1-A2-A0-9C-80-7A-78-08升序地址为BC 降序地址为BD 因为该表中有9个数，那么我们就去其中位数9C。（不唯一。因为如果这些书中表示的是地址则不会是九个数啦） F0 00 F1 00 F2 7A F3 C9 F4 00 F5 00 F6 00 F7 00 F8 00 F9 00 FA 00 FB 80 FC F2 FD 00 FE 00 FF 00 C0 00 C1 00 C2 00 C3 00 C4 05 C5 00 C6 00 C7 00 C8 00 C9 78 CA C4 CB 00 CC 00 CD 00 CE 00 CF 00 B0 A0 B1 01 B2 00 B3 00 B4 00 B5 00 B6 00 B7 00 B8 00 B9 00 BA 00 BB 9C BC B0 BD FB BE 00 BF 00 00 00 01 A2 02 07 03 00 04 00 05 00 06 00 07 B1 08 0D 09 00 0A 00 0B 00 0C 00 0D D2 0E 00 0F 00 4.48 驱车的数值为45 ， 执行出栈操作后栈顶地址为73.4.49 96 6F A0 53 AE 4D 90 00