计算机习题答案 10页

2.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;10\ni++;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->data>pNewNode->data){pNewNode->next=pCur;pHead=pNewNode;break;}10\nNode*pNext=pCur->next;//将新节点插入到单链表的表尾if(pNext==NULL){pCur->next=pNewNode;break;}//将新节点插入到单链表的中间if(pNext->data>pNewNode->data){pNewNode->next=pNext;pCur->next=pNewNode;break;}pPre=pCur;pCur=pNext;}return;}2.28将下列的一般树化为二叉树转换后的二叉树如右图所示转换后2.30设一棵二叉树其中序和后序遍历为，中序：BDCEAFHG后序：DECBHGFA画出这棵二叉树的逻辑结构，并写出先序遍历结果。先序遍历：ABCDEFGH。其逻辑结构如下：10\nABFCDEGH2.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。分别写出：插入排序，简单选择排序、堆排序、冒泡排序、快速排序、二叉树排序的排序过程，并对排序方法进行分析。10\n插入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,6210\n13,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操作系统的基本功能是什么？它包括哪些部分？操作系统具有处理机管理、存储管理、设备管理和文件管理，同时，为了使用户能方便地使用机器，操作系统还应提供用户接口功能。处理机管理：负责处理及资源的管理，包括进程控制、进程同步、进程通信及调度。内存管理：负责内存资源管理，包括内存分配及回收、信息保护、地址映射及内存扩充。10\n设备管理：负责设备资源的管理，包括设备分配回收、缓冲管理、设备处理、设备独立性。文件管理：负责信息资源管理，包括文件存储空间管理、目录管理、文件操作、文件共享保护。用户接口：命令接口及程序接口。3，3通常操作系统有哪几种基本类型？各有什么特点及适用于何种场合？课本P109（1）多道批处理系统：计算机内存中同时可以存放多道作业，用户与作业之间没有交互作用，用户不能直接控制作业的运行。此类系统一般用于计算中心等较大型的计算机系统中。（2）分时系统：多个用户分享同一台计算机，它把处理机的时间分成很短的时间片，按时间片轮流把处理机分配给各联机作业使用。用户感觉好像只有自己独占计算机一样。此类系统适用于程序的开发。（3）实时系统：实时系统是指系统能及时响应外部事件的请求，在规定的时间范围内完成对该事件的处理，并控制实时任务协调一致地运行。此类系统一般用于工业控制系统或事物处理系统。3.6什么是重定位？静态重定位和动态重定位的区别是什么？各举一例说明。当用户程序要调入内存时，必须把程序的逻辑地址转换为绝对地址，同时要包括对程序中与地址有关的指令进行修改，这一过程称为重定位。静态重定位：地址变换在程序装入时由重定位装入程序一次完成，以后不再改变；不需硬件支持，但程序运行时不能在内存移动，程序需要连续存储空间，难以共享。动态重定位：在程序执行过程中，每次访问内存之前将要访问程序地址转换成内存地址；需要硬件支持，不需连续空间，可以实现虚拟存储。3.7存储管理器的功能是什么？为什么要引入虚拟存储器的概念？虚存的容量由什么决定？存储管理的功能主要分为：内存分配、地址转换、存储保护和内存扩充。虚拟存储器可以在不扩充物理内存的情况下，能提供给用户一个比实际内存大得多的存储空间，使用户在编制程序时可以不必考虑存储空间的限制，达到即扩充内存又不增加成本的目的。虚存的容量受两个条件约束：指令中地址场长度的限制、外存储器容量的限制。3.11处理器管理主要解决什么问题？解决用户提交的作业何时调入内存，在调入内存的各作业之间如何分配处理机。3.12什么是进程的同步和互斥？什么是临界区？同步：多个相关合作的进程，在一些关键点上可能需要互相等待或互相交换信息。这种相互制约关系称为进程同步。互斥：当一个进程正在访问某共享资源时，就不允许其他进程对其访问，这种相互制约关系称为互斥。临界区：进程中访问临界资源的那段代码称为临界区，又称临界段。3.16死锁产生的必要条件是什么？死锁的预防、避免和检测各有什么不同？各举一种相应的方法。死锁产生的必要条件：10\n互斥条件：在一段时间内某资源仅为一个进程所占有。不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走。请求和保持条件：又称部分分配条件。当进程因请求资源被阻塞时，已分配资源保持不放。循环等待条件：死锁发生时，存在一个进程资源的循环。不同点：死锁的预防：设置某些限制条件，通过破坏死锁产生的四个必要条件之一来预防死锁。死锁的避免：在资源的动态分配过程中，用某种方法来防止系统进入不安全状态。死锁的检测及解除：系统定期检测是否出现死锁，若出现则解除死锁。举例：死锁预防：静态资源分配法、有序资源分配法死锁避免：银行家算法死锁检测：资源剥夺法、撤销进程法3.19设备管理的功能是什么？怎样把一台物理设备虚拟为多台设备？设备管理的功能：设备分配：根据用户的I/O请求，为之分配设备。包含控制器和通道。设备处理：负责启动设备及I/O操作完成时的中断处理。缓冲管理：为缓和CPU与I/O速度不匹配的矛盾常设置缓冲区。缓冲管理负责缓冲区的分配和释放及有关管理工作。设备独立性：又称设备无关性，是指用户编制程序时所使用的设备与物理设备无关。假脱机系统利用高速的直接存储设备来模拟低速的独占设备，并使其转换成共享设备，这种技术被称为虚拟设备技术，其基本实现思想是：输入Spooling：系统把原来使用独占设备的输入过程分成两步：首先将用户的作业由输入设备以文件形式保存在磁盘的专门区域（输入井）中，这由Spooling系统的输入收存程序来完成；当运行的进程需要输入信息时，由Spooling系统中的输入发送程序负责从输入井中将有关文件读入内存。在这里输入井起到了虚拟输入机的作用。输出Spooling：当作业执行过程中需要输出时，由Spooling系统中的输出收存程序负责将要求输出的信息以文件形式暂存到磁盘的专门区域（输出井）中，等待该作业运行完毕，Spooling系统的输出发送程序将对应该作业的输出文件通过输出设备输出。因此输出井起到了虚拟输出机的作用。补充题目：什么是设备独立性，有何好处？又称设备无关性，是指用户编制程序时使用的设备与实际使用的物理设备无关。使用设备独立性的优点：设备分配的灵活性。进程在执行时可利用该类设备中任一物理设备，而不必仅限于使用具体的某一设备，可提高设备的利用率。易于实现I/O重定向。程序的I/O操作不必指出在哪台输入、输出设备上进行。3.22什么是文件目录？有几种目录结构形式？各有什么特点？文件目录是计算机对文件进行管理的一种数据结构。通常有一级目录、二级目录和多级目录结构。一级目录：最简单的结构形式，整个文件系统只建立一张目录表，每个文件占据其中一个表项，查找时要扫描这个歌目录，增加查找时间。目录中的文件符号名不能重复10\n二级目录：由主目录文件和用户目录文件组成。主文件目录记录用户名及相应用户文件目录所在的存储位置；用户文件目录记录该用户文件的有关信息。多级目录：第一级目录称为根目录（树根），目录树中的非叶节点均为目录文件（又称子目录），叶结点为文件。4.1试比较数据库系统与文件系统，说明两者的异同。相同点：A、都是以文件为基本单位存储数据B、数据都有逻辑结构与物理结构之分C、都有专门的软件系统管理数据不同点：A、文件系统中的文件是面向应用组织的，一个文件基本对应一个应用程序，数据间的联系弱；数据库系统中的文件是面向整个应用系统组织的，减少了数据冗余，实现了数据共享。B、数据库系统中的逻辑结构又分成局部数据逻辑结构和全局数据逻辑结构两级C、DBMS管理数据的功能比OS中的文件系统要强得多。4，3数据库系统的三级结构模式各起什么作用。外模式（子模式）对局部数据逻辑结构和特征的描述。（多个）概念模式（模式）对全局数据逻辑结构和特征的描述。（一个）。定义模式时不仅要定义数据的逻辑结构，还要定义与数据有关的安全性、完整性要求。内模式（存储模式、物理模式）对数据物理结构和存储方式的描述。（一个）4.4试说明数据库设计的主要步骤，各完成什么工作。主要步骤：A、需求分析：了解用户需求；B、概念设计：对用户需求进行综合抽象，形成独立于具体DBMS的概念模型；C、逻辑设计：将概念结构转换为所用DBMS支持的数据模型并进行优化；D、物理设计：选择合适的物理数据库结构（包括物理结构和存取方法）E、数据库实施：用DBMS提供的数据语言描述逻辑设计及物理设计，编制及调试应用程序，组织数据入库F、数据库运行和维护：收集和记录系统实际运行数据，评价数据库系统的性能，修正系统。4.7（5）查询为工程号Ｊ－１提供零件号P-1的供应商号Ｓ－ＮＯSELECTS-NOFROMSPJWHEREJ-NO=‘J-1’ANDP-NO=‘P-1’（6）查询提供零件名ＰＮ３的供应商号Ｓ－ＮＯ10\nSELECTS-NOFROMSPJWHEREP-NOIN(SELECTP-NOFROMPARTWHEREPNAME=‘PN3’)　（7）查询供应商号Ｓ－３提供的零件名ＰＮＡＭＥ　SELECTPNAMEFROMPARTWHEREP-NOIN(SELECTP-NOFROMSPJWHERES-NO=‘S-3’)（8）查询为工程号Ｊ－１和Ｊ－２提供零件的供应商号Ｓ－ＮＯSELECTS-NOFROMSPJWHEREJ-NO=‘J-1’ANDS-NOIN(SELECTS-NOFROMSPJWHEREJ-NO=‘J-2’)　（10）取出上海供应商为在上海的工程提供零件的所有供应商号Ｓ－ＮＯ　SELECTS-NOFROMSPJWHERES-NOIN(SELECTS-NOFROMSUPPWHERECITY=‘上海’)ANDJ-NOIN(SELECTJ-NOFROMPROJWHERECITY=‘上海’)(11）取出北京供应商不提供红色零件的供应商号Ｓ－ＮＯSELECTS-NOFROMSUPPWHERECITY=‘北京’ANDS-NONOTIN(SELECTS-NOFROMSPJWHEREP-NOIN(SELECTP-NOFROMPARTWHERECOLOR=‘红’))10