计算机习题答案_20140621

12.1什么是数据结构？它对算法有什么影响？答：数据结构是指同一数据对象中各数据元素间存在的关系，可以看作是相互之间存在着某种特定关系的数据元素的集合。对算法是影响：算法的效率与数据结构有关，数据结构的选择对算法实现的效率起至关重要的作用。2.2何谓算法？它与程序有何区别？算法是解决某一特定类型问题的有限运算序列。和程序的区别：一个程序包括数据结构和算法两个方面的内容，算法是程序的一个要素。2.6数据的存储结构主要有哪两种?它们之间的本质区别是什么？数据的存储结构主要有顺序存储结构和链式存储结构。本质区别：顺序存储结构的存储空间是连续的，数据元素间的逻辑关系借助存储的相对位置来表示；链式存储结构不需要一组连续的存储单元，其数据元素可以分散存放在存储空间中，其数据元素之间的逻辑关系借助指针来表示。2.12试编写算法求已知单链表的长度，并考虑表空的情况intGetListLength(Node*pHead){inti=0;Node*pCur=pHead;while(pCur!=NULL){i++;pCur=pCur-next;}returni;}2.13试编写算法删除单链表中的第K个节点//2.13删除单链表中的第k个节点。注：节点序号从1开始voidRemoveNode(Node*&pHead,intk){Node*pPre=NULL;Node*pCur=NULL;pCur=pHead;inti=1;while(pCur!=NULL){//不是要删的节点序号，则继续下一个节点if(k!=i){pPre=pCur;pCur=pCur-next;2i++;continue;}//要删除的就是第一个节点if(k==1){pHead=pCur-next;}else{//要删除的是中间某个节点pPre-next=pCur-next;}deletepCur;}}2.14已知一单向链表中数值已按递增有序排列，先要插入一个新节点，并使插入后链表仍为有序序列//可参考胶片19页TypedefstructtagNode{Intdata;Node*next;}Node;voidInsertNode(Node*&pHead,Node*pNewNode){//链表为空时，将该节点作为链表的第一个节点if(pHead==NULL){pHead=pNewNode;return;}Node*pPre=NULL;Node*pCur=pHead;while(pCur!=NULL){//新节点的数据比单链表的头节点的数据小，则将新节点插入到最开头if(pCur-datapNewNode-data){pNewNode-next=pCur;pHead=pNewNode;break;}3Node*pNext=pCur-next;//将新节点插入到单链表的表尾if(pNext==NULL){pCur-next=pNewNode;break;}//将新节点插入到单链表的中间if(pNext-datapNewNode-data){pNewNode-next=pNext;pCur-next=pNewNode;break;}pPre=pCur;pCur=pNext;}return;}2.28将下列的一般树化为二叉树转换后的二叉树如右图所示转换后2.30设一棵二叉树其中序和后序遍历为，中序：BDCEAFHG后序：DECBHGFA画出这棵二叉树的逻辑结构，并写出先序遍历结果。先序遍历：ABCDEFGH。其逻辑结构如下：42.32给定一组元素｛17，28,36,54,30,27,94,15,21,83,40｝，画出由此生成的二叉排序树。2.33定一组权值W={8，2，5，3，2，17，4}，画出由此生成的哈夫曼树。生成的哈夫曼树为：或者2.34有一图如下图所示：由节点V1作深度优先搜索和广度优先搜索。深度：1543210111213141567891819201617广度：187651718916151021413201911431232.42对于给定的一组关键字：41，62，13，84，35，96，57，39，79，61，15，83。分别写出：插入排序，简单选择排序、堆排序、冒泡排序、快速排序、二叉树排序的排序过程，并对排序方法进行分析。ABFCDEGH5插入1341628435,96,57,39,79,61,15,83133541628496573979611583133541576284963979611583133539415762849679611583133539415762798496611583133539415761627984961583131535394157616279849683131535394157616279838496对于具有n个记录的文件，要进行n-1趟排序就地排序稳定的排序方法简单选择排序416213843596573979611583134162843596573979611583131541628435965739796183131535416284965739796183131535394162849657796183131535394157628496796183131535394157616284967983131535394157616279849683131535394157616279838496堆排序41621384359657397961158396,84,83,79,62,61,57,41,39,35,15,13冒泡排序41,13,62,35,84,57,39,79,61,15,83,9613,41,35,62,57,39,79,61,15,83,84,9613,35,41,57,39,62,61,15,79,83,84,9613,35,41,39,57,61,15,62,79,83,84,9613,35,39,41,57,15,61,62,79,83,84,9613,35,39,41,15,57,61,62,79,83,84,9613,35,39,15,41,57,61,62,79,83,84,9613,35,15,39,41,57,61,62,79,83,84,9613,15,35,39,41,57,61,62,79,83,84,9613,15,35,39,41,57,61,62,79,83,84,9613,15,35,39,41,57,61,62,79,83,84,9613,15,35,39,41,57,61,62,79,83,84,96快速排序13,35,39,15,41,96,57,83,79,61,84,6213,35,39,15,41,96,57,83,79,61,84,6213,15,35,39,41,96,57,83,79,61,84,62613,15,35,39,41,96,57,83,79,61,84,6213,15,35,39,41,96,57,83,79,61,84,6213,15,35,39,41,62,57,83,79,61,84,9613,15,35,39,41,57,61,62,79,84,83,9613,15,35,39,41,57,61,62,79,84,83,9613,15,35,39,41,57,61,62,79,84,83,9613,15,35,39,41,57,61,62,79,84,83,9613,15,35,39,41,57,61,62,79,83,84,96二叉树排序二叉树建立过程4141,6213,41,6213,41,62,8413,35,41,62,8413,35,41,62,84,9613,35,41,57,62,84,9613,35,39,41,57,62,84,9613,35,39,41,57,62,79,84,9613,35,39,41,57,61,62,79,84,9613,15,35,39,41,57,61,62,79,84,9613,15,35,39,41,57,61,62,79,83,84,963.1操作系统的基本功能是什么？它包括哪些部分？操作系统具有处理机管理、存储管理、设备管理和文件管理，同时，为了使用户能方便地使用机器，操作系统还应提供用户接口功能。处理机管理：负责处理及资源的管理，包括进程控制、进程同步、进程通信及调度。内存管理：负责内存资源管理，包括内存分配及回收、信息保护、地址映射及内存扩充。7设备管理：负责设备资源的管理，包括设备分配回收、缓冲管理、设备处理、设备独立性。文件管理：负责信息资源管理，包括文件存储空间管理、目录管理、文件操作、文件共享保护。用户接口：命令接口及程序接口。3，3通常操作系统有哪几种基本类型？各有什么特点及适用于何种场合？课本P109（1）多道批处理系统：计算机内存中同时可以存放多道作业，用户与作业之间没有交互作用，用户不能直接控制作业的运行。此类系统一般用于计算中心等较大型的计算机系统中。（2）分时系统：多个用户分享同一台计算机，它把处理机的时间分成很短的时间片，按时间片轮流把处理机分配给各联机作业使用。用户感觉好像只有自己独占计算机一样。此类系统适用于程序的开发。（3）实时系统：实时系统是指系统能及时响应外部事件的请求，在规定的时间范围内完成对该事件的处理，并控制实时任务协调一致地运行。此类系统一般用于工业控制系统或事物处理系统。3.6什么是重定位？静态重定位和动态重定位的区别是什么？各举一例说明。当用户程序要调入内存时，必须把程序的逻辑地址转换为绝对地址，同时要包括对程序中与地址有关的指令进行修改，这一过程称为重定位。静态重定位：地址变换在程序装入时由重定位装入程序一次完成，以后不再改变；不需硬件支持，但程序运行时不能在内存移动，程序需要连续存储空间，难以共享。动态重定位：在程序执行过程中，每次访问内存之前将要访问程序地址转换成内存地址；需要硬件支持，不需连续空间，可以实现虚拟存储。3.7存储管理器的功能是什么？为什么要引入虚拟存储器的概念？虚存的容量由什么决定？存储管理的功能主要分为：内存分配、地址转换、存储保护和内存扩充。虚拟存储器可以在不扩充物理内存的情况下，能提供给用户一个比实际内存大得多的存储空间，使用户在编制程序时可以不必考虑存储空间的限制，达到即扩充内存又不增加成本的目的。虚存的容量受两个条件约束：指令中地址场长度的限制、外存储器容量的限制。3.11处理器管理主要解决什么问题？解决用户提交的作业何时调入内存，在调入内存的各作业之间如何分配处理机。3.12什么是进程的同步和互斥？什么是临界区？同步：多个相关合作的进程，在一些关键点上可能需要互相等待或互相交换信息。这种相互制约关系称为进程同步。互斥：当一个进程正在访问某共享资源时，就不允许其他进程对其访问，这种相互制约关系称为互斥。临界区：进程中访问临界资源的那段代码称为临界区，又称临界段。3.16死锁产生的必要条件是什么？死锁的预防、避免和检测各有什么不同？各举一种相应的方法。死锁产生的必要条件：8互斥条件：在一段时间内某资源仅为一个进程所占有。不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走。请求和保持条件：又称部分分配条件。当进程因请求资源被阻塞时，已分配资源保持不放。循环等待条件：死锁发生时，存在一个进程资源的循环。不同点：死锁的预防：设置某些限制条件，通过破坏死锁产生的四个必要条件之一来预防死锁。死锁的避免：在资源的动态分配过程中，用某种方法来防止系统进入不安全状态。死锁的检测及解除：系统定期检测是否出现死锁，若出现则解除死锁。举例：死锁预防：静态资源分配法、有序资源分配法死锁避免：银行家算法死锁检测：资源剥夺法、撤销进程法3.19设备管理的功能是什么？怎样把一台物理设备虚拟为多台设备？设备管理的功能：设备分配：根据用户的I/O请求，为之分配设备。包含控制器和通道。设备处理：负责启动设备及I/O操作完成时的中断处理。缓冲管理：为缓和CPU与I/O速度不匹配的矛盾常设置缓