软件基础基本概念问答2012.doc

软件基础基本概念问答1一个完整的计算机系统由那几个基本组成部分。由计算机硬件子系统和计算机软件子系统组成2什么是计算机软件。计算机软件：包含与数据处理系统操作有关的程序、规程、规则以及相关文档。3从应用的角度出发，将软件分为那几类。从应用的角度出发，将软件分为：系统软件；支撑软件；应用软件。系统软件：给其他程序提供服务的程序集合（如各种操作系统、编译程序）。系统软件的主要特征：与具体的应用领域无关而与计算机硬件系统有很强的交互性，要对硬件共享资源进行调度管理。系统软件中的数据结构复杂，外部接口多样化，用户能够对它反复使用。支撑软件：用于支持软件开发与维护的软件。人们常把1970年代中、后期发展起来的软件开发环境作为支撑软件的代表，它主要包括数据库管理系统、各种接口软件、网络软件和工具组件，这些软件形成一个整体，协同支持各类软件的开发与维护。 应用软件：针对多种应用需求出现的用于解决各种不同具体应用问题的专门软件。4计算机软件的发展大致经历了那几个主要阶段。软件的发展大致经历了三个主要阶段：（1）第一阶段（1940年代到1950年代中期）：从第一台计算机上的第一个程序开始到实用的高级语言程序出现以前，是计算机软件发展初期。（2）第二阶段（1950年代中期到1960年代后期）：出现了高级程序语言、操作系统、数据库管理系统、“软件”术语等。（3）第三阶段（1960年代迄今）：软件工程：软件领域工作新的特点：随着应用领域的不断拓广，出现了嵌入式应用软件、网络软件及分布式应用软件。5什么是软件工程。软件工程：软件工程是指导计算机软件开发和维护的工程学科。采用工程的概念、原理、技术和方法来开发与维护软件，把经过时间考验而证明正确的管理技术和当前能够得到的最好技术方法结合起来，这就是软件工程。6软件生命周期由那几个时期组成，每个时期又划分为那几个阶段。软件生命周期由软件定义、软件开发和运行维护三个时期组成，每个时期又划分若干个阶段。1软件定义：问题定义，可行性研究，需求分析。 2软件开发：总体设计，详细设计，编码和单元测试，综合测试。3软件维护：维护阶段的关键任务是，通过各种必要的维护活动使系统持久地满足用户的需要。通常有四类维护活动：7什么是操作系统，操作系统的作用是什么。操作系统（Operating System，简称OS）：用于控制、管理、调配计算机的所有资源。是给计算机配置的一种必不可少的系统软件。 操作系统的作用：（1）管理系统中的各种（软、硬件）资源。（2）为用户提供各种服务界面。用户界面：也称用户接口或人机界面，是计算机系统实现用户与计算机通信的软、硬件部分的总称。图形用户界面（GUI）：采用窗口、图符、菜单及指点设备技术和多窗口系统等软件，并以直接操纵为主要使用方法，使得用户能够灵活、方便、有效地使用计算机。（3）为应用程序的开发和运行提供一个高效的平台。8操作系统提供那五种主要功能。操作系统通过内部命令和外部命令提供五种主要功能：任务管理存储管理文件管理设备管理作业管理9什么是多进程技术。计算机中同时有多个进程，如果一个进程因等待某一条件而不能运行下去时，就将处理机占用权转给另一个可运行进程。或者，当出现了一个比当前运行进程更重要的可运行进程时，后者应能抢占CPU资源。操作系统按照一定的调度策略，通过进程管理来协调多道程序之间的关系，解决CPU资源的分配和回收等问题，以使CPU资源得到最充分利用。10常用的操作系统有那几种。Windows操作系统，UNIX操作系统，Linux操作系统等。11Linux操作系统有那些特点。具有与UNIX相似的可移植操作系统服务功能。Linux操作系统的优势反映在网络服务器方面，其内核中包含许多网络协议，已成为网络上最普遍的服务器架构模式。Linux操作系统作为一个多用户、多任务的操作系统，支持多工作平台和多处理器。它不仅可提供多达4TB的文件系统，同时还可支持多种其他的文件系统。Linux系统是一种“自由软件”。或者说，它属于一种GPL（General Public License）软件。其源代码向世人公开，吸引对该系统感兴趣的人们共同工作。12 计算机语言是如何分类的，各类语言的特点是什么。程序设计语言按其级别可以划分为机器语言、汇编语言和高级语言三大类。机器语言：使用计算机指令系统的程序语言。用机器语言编写的程序，全部都是二进制代码形式，可以被计算机直接执行。机器语言直接依赖机器的指令系统，不同类型甚至不同型号的计算机，其机器语言是不同的。机器语言不易记忆和理解，所编写的程序也难于修改和维护。 汇编语言：用助记符来代替机器指令的操作码和操作数，如用表示加法，用表示减法等。这样就能使它的每条指令都有明显的符号标识。用汇编语言编写程序与编写机器语言程序相比，比较直观和易记忆，但汇编语言仍然是面向机器指令系统的，还保留了机器语言的各项缺点。 高级语言：又称算法语言，其表示方法接近解决问题的表示方法，而且具有通用性，在一定程度上与机器无关。高级语言的特点：易学、易用，易维护。人们可以更有效、更方便地用它来编制各种用途的计算机程序。13 语言处理系统包括那些程序，各自的作用是什么。语言处理系统包括：翻译程序；对源程序进行翻译正文编辑程序：用于建立和修改源程序文件；联接编辑程序：将多个分别编译或汇编过的目标程序和库文件进行组合装入程序：将目标程序装入内存并启动执行14什么是编译程序，编译程序有何优点。编译程序：编译程序对源程序进行翻译的方法相当于“笔译”。在编译程序的执行过程中，要对源程序扫描一遍或几遍，最终形成一个可在具体计算机上执行的目标程序。优点：通过编译程序的处理可以一次性地产生高效运行的目标程序，并把它保存在磁盘上，以备多次执行。15主要的程序语言有那几种。FORTRAN语言：ALGOL语言：PASCAL语言：Java语言：C语言：C+语言：等16C语言有什么特点。C语言：1972年至1973间由ATT公司Bell实验室的D.M.Ritchie 在BCPL语言基础上设计而成的，著名的UNIX操作系统就是用C语言编写的。特点：语言与运行支撑环境分离、可移植性好、语言规模小因而相对简单、具有指针类型等，C语言本身简洁、高度灵活、程序运行效率高。此外，在C语言中，有不少操作直接对应实际机器所执行的动作，并在许多场合可以代替汇编语言。17C+语言和C语言有何关系。C+语言：以C语言为基础发展起来的通用程序设计语言。C+语言是对C语言的扩充，扩充的内容绝大部分来自其他著名语言（如Simula、ALGOL68、Ada等）的最佳特性。由于C+语言既有数据抽象和面向对象能力，运行性能高，又能与C语言相兼容，使得数量巨大的C语言程序能方便地在C+语言环境中重用。因而近年来C+语言迅速流行，成为当前面向对象程序设计的主流语言。18FORTRAN语言有什么特点。接近数学公式、简单易用。在处理功能上，允许复数与双精度实数运算，由于具有程序定义机制、I/O的格式说明，允许布尔表达式，函数和子例程名作参数传递，扩充的字符处理等功能，使之也能应用于非数值运算领域。FORTRAN语言还具有块IF结构，DO循环结构等，使写出的程序趋于结构化，是进行大型科学和工程计算的有力工具。19数据结构研究的问题是什么，研究的内容可分为那几方面的问题。获得用计算机处理数据的有效方法是数据结构研究的问题。其研究的对象是包括非数值信息在内的数据，研究的内容是对数据的计算机处理，具体可分为如下四个方面的问题：数据本身的结构和数据间存在的逻辑关系，即数据的逻辑结构。对在各种具有不同逻辑结构的数据上可能进行的处理操作，提供相应的处理方式和方法，即算法设计与分析。根据数据的逻辑结构和可能进行的处理操作，设计有利于处理操作的、在计算机中存储这些数据的存储方式，即数据的物理结构。最后，把与数据的逻辑结构和物理结构相关的处理算法转化为高级程序设计语言的相应代码。20. 叙述基本概念:数据、数据项、数据元素、关键字、数据对象、数据结构。数据:是信息的载体，可以用文字、字符、声音、图象等形式加以表示，通过编码可以被计算机所识别、存储和处理。数据项:是构成数据的基本单位，具有相对独立的含义而且是不可再分。数据元素:是在数据处理的过程中作为整体看待和处理的一部分数据，通常由一个或多个数据项构成，与一个客观事物相对应。根据不同情况，有时也称数据元素为记录或结点。关键字:是构成数据元素的满足下列条件的数据项：若该数据项的内容（或称为值）能唯一标识一个数据元素，则称其为关键字或主关键字；若该数据项的内容（或称为值）不能唯一标识一个数据元素，则称其为次关键字。数据对象:是数据元素的集合，其中的每一个数据元素都有相同的结构（如多个人对应的数据元素构成的集合就是一个数据对象）。数据结构:是指数据对象中数据元素间存在的一种或多种关系，可分为逻辑结构和物理结构（也称存储结构）分别讨论。21. 常用的逻辑结构有哪几种,在计算机中存储数据的常用方法有哪几种。常用的逻辑结构有：（1）集合结构，数据元素间只有同属一个集合这样一种关系。（2）线性结构，元素间存在严格的次序关系。（3）树形结构，元素间存在特定的层次关系。（4）图形逻辑结构,元素间存在相对复杂的关系。数据在计算机中的存储方法有顺序存储、链式存储、索引存储和散列存储等方法。22. 什么是顺序存储，顺序存储结构的主要特点有那些。顺序存储：是把逻辑上相邻的元素存储在物理位置相邻的存储单元中，称此存储表示为顺序存储结构。程序设计中常用数组实现顺序存储。 顺序存储结构的主要特点是：存储密度大，存储空间利用率高。可以通过计算直接确定数据对象中第i个数据元素的存储地址Li，计算公式为：Li=L0+(i-1)*m。其中L0为第一个数据元素的存储地址，m为一个数据元素占用的存储单元的个数。插入和删除数据时，会引起大量的数据移动。23什么是算法，一个算法应该具有的特性是什么。算法（Algorithm）是求解问题的方法的步骤序列。一个算法应该具有下列特性：有穷性：一个算法必须在有穷步之后结束。确定性：算法的每一步必须有确切的定义。可行性：算法中的每一步都可以通过基本运算得以实现。输入：一个算法具有零个或多个输入。 输出：一个算法具有一个或多个输出，输出同输入之间存在某种特定的关系。24对一个算法要求有那些。设计一个算法通常要考虑以下的要求。正确：算法的执行结果应当满足预先规定的功能和性能要求。可读：一个算法应当思路清晰、层次分明、简单明了、易读易懂。 健壮：当输入不合法数据时，应能作适当处理，不至引起严重后果。 高效：有效使用存储空间和有较高的时间效率。25. 什么是算法的时间复杂度和空间复杂度。算法的时间复杂度：指执行算法时所需的时间（与问题的规模有关）。算法的空间复杂度：指在实现算法时所需的存储量。26. 叙述线性表的定义及其逻辑特征。线性表：由n(n0)个相同类型的数据元素a1，a2，.，an组成的有限序列，记作： L=（a1，a2， an）线性表的逻辑特征为：有且仅有一个开始数据元素a1，它没有直接前驱，y有且仅有一个直接后继a2；有且仅有一个最后数据元素an，它没有直接后继，仅有一个直接前驱an-1；其余的数据元素 ai (1iLength的值为0，图2-6 中的条件（i=1 且 idatas-top=x; s-top+; return 0; 顺序栈出栈： int Pop_SeqStack(SeqStack *s, DataType *x) if (Empty_SeqStack (s) ) return -1; /*栈空，返回-1 */ else s-top-; *x=s-datas-top; /*栈顶元素存入*x */ return 0; 链栈入栈： void Push_LinkStack（LinkStack *top, DataType x） LinkStack *s; s=(LinkStack *)malloc(sizeof（LinkStack）; s-data=x; s-next=top-next; top-next=s;链栈出栈：int Pop_LinkStack (LinkStack *top, DataType *x)StackNode *p; if （Empty_LinkStack(top)） return -1; /*栈空，返回-1 */ else p=top-next; /*p指向栈顶元素 */ top-next=p-next; /*将p所指结点从链栈中删除*/ *x = p-data; /*栈顶元素值存入*x中 */ free(p); /*释放p所指结点占用的空间*/ return 0; /*操作成功，返回0 */ 顺序队入队操作： int In_SeqQueue ( c_SeqQ *q , DataType x) int result; if (q-num=MAXSIZE) printf(队满); result=-1; /*队满不能入队*/ else q-dataq-rear=x; q-rear=(q-rear+1)%MAXSIZE; q-num+; result=0; /*入队成功*/ return result;顺序队出队操作： int Out_SeqQueue (c_SeqQ *q , DataType *x) int result; if (num=0) printf(“队空”);result=-1; /*队空不能出队*/ else *x=q-dataq-front; /*读出队头元素*/ q-front=(q-front+1) % MAXSIZE; q-num-; result=0; return result;链队入队：void In_LinkQueue(LinkQ *q , DataType x) QNode *p;p=(QNode*)malloc(sizeof(QNode); /*申请新结点*/p-data=x;p-next=NULL;q-rear-next=p;q-rear=p;链队出队：int Out_LinkQ(LinkQ *q , DataType *x) QNode *p; int result; if (q-front-next=NULL) printf (队空);result=-1; /*出队失败*/ else p=q-front-next; q-front-next=p-next; *x=p-data;/*队头元素放x中*/ free(p); /*当队列中只有一个元素时，出队后队空，此 if (q-front-next=NULL)时还要修改队尾指针*/ q-rear=q-front; result=0; return result;31. 叙述数组的定义及其逻辑特征。数组是由同类型数据元素组成的有序集合，称构成数组的各数据元素为数组元素，每一个数组元素都有自己的编号，称为该数组元素的下标，数组元素在数组中的位置由数组元素的下标确定。称其元素只有一个下标的数组为一维数组，元素有两个下标的数组为二维数组，依次类推。数组可以看作线性表的推广。比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，依此类推32. 叙述数组与矩阵和向量的关系。程序设计语言中，用一维数组表示向量，用二维数组表示矩阵。33. 叙述特殊矩阵的存储策略。为了节省存储空间，根据特殊矩阵的特征，使存储的数据尽可能的少。34. 叙述树的定义及其逻辑特征树是n（n0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n1时，其余结点被分成m（m0）个互不相交的子集T1,T2,.,Tm，每个子集又是一棵树。树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。树中所有结点可以有零个或多个后继结点35. 叙述二叉树的定义及其逻辑特征二叉树：a) 每个结点最多有两棵子树；b) 子树有左右之分。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使结点只有一棵子树也要区分是左子树还是右子树。36. 什么是满二叉树和完全二叉树满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。完全二叉树叶子结点只出现在最下层和次最下层，且最下层的叶子结点集中在树的左部的二叉树。37. 叙述实现顺序存储二叉树的方法a) 对于完全二叉树和满二叉树：按照二叉树结点从上至下、从左到右的顺序依次把各结点存储到一组连续的存储单元中。由二叉树的性质知，完全二叉树和满二叉树中结点的序号可以唯一地反映出结点之间的逻辑关系。可以利用数组元素的下标值确定结点在二叉树中的位置及结点之间的关系。b) 对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系。可通过增添一些并不存在的空结点，使之成为一棵完全二叉树后，再用一维数组顺序存储。38. 什么是树的先序遍历，中序遍历，后序遍历(1)先序遍历 若二叉树为空，则结束遍历操作；否则访问根结点；遍历左子树；遍历右子树。(2) 中序遍历 若二叉树为空，则结束遍历操作；否则遍历左子树；访问根结点；遍历右子树。(3) 后序遍历 若二叉树为空，则结束遍历操作；否则遍历左子树；遍历右子树；访问根结点。39. 叙述哈夫曼树的定义哈夫曼树又称为最优二叉树:由n个带权叶结点构成的所有二叉树中带权路径长度WPL最小的二叉树。40. 叙述构造一棵哈夫曼树的方法构造哈夫曼树的过程：1.将给定的n个权值w1,w2,.,wn作为n个根结点的权值构造一个具有n棵二叉树的森林T1,T2,.,Tn，其中每棵二叉树只有一个根结点；2.在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；3.在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；4.重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。41. 举例说明图的三种表示方法几何表示法：集合表示法：图G1的顶点集和边集分别为： V(G1)=v1,v2,v3,v4,v5 E(G1)=(v1,v2),(v2,v5),(v1,v4),(v3,v4),(v3,v5)矩阵表示法：42. 给出一个图的最小生成树设G=（V，E）是一带权图，其中V为G中所有顶点的集合，E为G中所有带权边的集合。T=（U，TE）为将要构造的生成树，其中集合U用于存放G的最小生成树中的顶点，集合TE存放G的最小生成树中的边。令集合U的初值为Uu1（假设构造最小生成树时，从顶点u1出发，且u1V），集合TE的初值为空集。普里姆算法描述如下： (1)U=u1,TE=; (2)选择权数最小的边(u，v)，其中uU, vV-U,将v加入U中，(u，v) 加入TE中； (3)重复步骤 (2)，直至U=V为止，这时最小生成树构造完毕，集合TE中包含了最小生成树的所有边。43. 给出一个图中一顶点到其他顶点的最短路径著名科学家迪杰斯特拉提出一个按路径长度递增的次序产生最短路径的算法。描述如下（假设顶点个数大于1）： (1) 设置顶点的集合S和TVS，S中存放已找到最短路径的顶点，T存放还未找到最短路径的顶点。初始时，S=v0,仅包含源点v0； (2) 计算v0到T中各顶点的最短路径长度值：若T中顶点u与v0相连，则v0到该顶点的最短路径长度值为该边的权值，否则v0到该顶点的最短路径长度为。 (3) 从T中选择一个从v0到T中各顶点的最短路径长度值中值最小的顶点u，将u加入到S中； (4) T=V-S, 若T为空，则求解完成，转 (6); (5) 计算v0经过顶点u到达T中各顶点的最短路径长度是否比原先的长度值小，若是则用新的最短路径长度修改原长度的值，转 (3)； (6) 输出v0到各顶点的最短路径及其长度值。44.叙述基本的排序方法直接插入排序方法 先将存放于数组中的第一个数据