程序设计基础复习指导

作者: 来源: 发布时间:2010年11月02日 点击数:
 

1.         世界公认的第一台通用电子数字计算机是美国宾夕法尼亚大学莫尔学院的莫奇利和埃克特领导的科研小组建造的,取名为 ENLAC

2.         第一代电子计算机(1946—1958)采用的基本逻辑元件是 电子管 。第二代电子计算机(1958~1964)采用的是基本逻辑元件是 晶体管 。第三代电子计算机(1964~1974)采用的基本逻辑元件是 半导体中小规模集成电路。第四代电子计算机(1974年以后)采用的基本元件是 大规模集成电路

3.         世界上最早的高级程序程序语言是 FORTRAN  

4.         计算机按照工作原理进行分类可以分为 数字计算,和 模拟计算

5.         当前计算机的最基本原理采用的是,冯`诺依曼的“存储程序原理”。

6.         计算机存储器一般分为两级,它们是主存储器,和外存储器

7.         计算机系统中的软件包括,所有程序相关的文档

8.         计算机硬件通常由5大功能部件组成,它们是:存储器,运算器,控制器,输入设备和输出设备。

9.         计算机语言有3种类型,它们是:机器语言,汇编语言和高级语言

10.     高级语言源程序的翻译有两种方式,一种是解释方式,另一种是编译方式。

11.     微机中常用的高级语言主要有3类:它们是:面向过程的程序设计语言,面向问题的程序设计语言 和面向对象的程序设计语言。

12.     程序设计过程的3个阶段是编程阶段,编译阶段和执行阶段。

13.     最基本的程序控制有三种,它们是顺序执行,分支控制和循环控制。   

14.     C语言中分支语言是  if   语句和  switch  语句。

15.     C语言中循环语言是 while 语句,  for  语句和 do—while语句。

16.     C语言中自增运算符是  ++  ,求余数的运算符号是  % 

17.     C语言中要改变循环语句的流程可以使用语句 break  ,   continue    go to .

18.     数据的 逻辑结构 是指数据元素之间的逻辑关系,与数据的存储无关,它独立于计算机,如用户在电话号码表中的先后次序关系;数据的 存储结构 是指数据元素在计算机存储设备中的存储方式。

19.     数据的存储结构可以用 顺序 存贮方式和 链式 存贮方式。

20.     数据的逻辑结构可分为线性结构,和非线性结构两大类。

21.     21,的性结构有 线性表,栈 和队列。等   其主要特征为各个结点之间“先后”有序。

22.     常见的非线性结构包括 图型 构。

23.     树型结构的主要特征是结点之间存在着一种层次的关系,数据元素之间的关系是 一对多。 在图型结构中,任何两个结点之间都可能存在着联系。数据元素之间存在着多对多的关系。

24.     对于一个线性表来说,如果它的表长为0,则我们称它为    表。

25.     若循环队列的头指针为 front ,尾指针为 rear, rear ,指向队队尾元素,front 指向当前队头元素的前一个位置。则队空的条件是 front=rear   , 队满的条件是 (rear+1)% maxsize=front .  入队操作时队尾指针应进行的操作是 rear=(rear+1)% maxsize .   ,.出队时队头指针应进行的操作是,front=(front+1)% maxsize.

26.     算法描述的常见方法是伪码,流程图和NS图。

27.     评价算法效率的主要指标是时间复杂度和空间复杂度

28.     当前流行的程序设计方法是:结构化程序设计和面向对象程序设计。

29.     软件开发模型大体上可分为两种类型,第一种是以软件需求完全确定,为前提的瀑布模型。第二种是在软件开发初始阶段  只能提供基本需求时采用的渐进式开发模型,如原型模型,螺旋模型等。

30.     要编写高质量的程序,判断程序质量的首要标准是程序的正确性,要保证程序在多次反复使用过程中不发生错误,应该保证程序的可靠性。

31.     对图进行遍历的方法有两种,它们是:深度优先搜索,和广度优先搜索。

                            

                                                                                 简答题

1 名词解释:CADCAMCAICPUCASE

CAD计算机辅助设计(Computer Aided Design

CAM: 计算机辅助制造(Computer Aided  Manufacturing

CAI: 计算机辅助教学Computer Aided Instructiom

CPU: 中央处理器

CASE计算机辅助软件工程

2 简术计算机硬件与软件的关系。

计算机硬件与软件的关系主要体现在以下三个方面:

(1)       互相依存。计算机硬件与软件的产生与发展本身就是相辅相成,互相促进的,二者密不可分。硬件是软件的基础和依托,软件是发挥硬件功能的关键,是计算机的灵魂。在实际应用中更是缺一不可,硬件与软件,缺少哪一部分,计算机都是无法使用的。

(2)       无严格界面。虽然计算机的硬件与软件各有分工,但是在很多情况下软硬件之间的界面是浮动的。计算机某些功能既可由硬件实现,也可以由软件实现的功能,随着计算技术的发展,一些过去只能用软件实现的功能,现在也可以用硬件来实现,而且速度和可靠性都大为提高。

(3)       相互促成。无论从实际应用还是从计算技术的发展看,计算机的硬件与软件之间都是相互依赖,相互影响,相互促进的。硬件技术的发展会对软件提出新的要求,促进软件的发展;反之,软件的发展又对硬件提出新的课题。

3简述计算机程序设计语言的分类和各类的特点。

一般分为三类:机器语言,汇编语言和高级语言。

机器语言是每台计算机出厂时,厂家都为它配备一套机器语言,不同的计算机,其机器语言通常是不同的。由于机器语言是面向具体机器的,所以其程序缺乏通用性,编写程序的过程繁琐复杂,易出错,错了又不易查找和修改,编出的程序可读性极差。

汇编语言是机器语言的符号化形式。用汇编语言编写的程序(又称源程序)经汇编器加工处理后,就转换成可由计算机直接执行的目标程序。汇编语言提高了程序设计效率和计算机利用率。汇编语言仍属面向机器的一种低级语言,其程序的通用性和可读性较差。

高级程序设计语言是指通用性好, 不必对计算机的指今系统有深入的了解就可以编写程序。采用高级语言编写的程序在不同型号的计算机上只需做某些微小的改动便可运行,只要采用这些计算机上的编译程序重新编译即可。高级语言具有通用性,与具体的机器无关。

 

4`诺伊曼原理的主要思想是什么?有什么意义?冯`诺伊曼的结构是什么?

(1)       用二进制形式表示数据和指今;

(2)       将程序(数据和指今序列)预先存放在主存储器中,使计算机在工作时能够自动高速地从存储器中取出反指今,并加以执行,这是“存储程序控制”的基本特点?

(3)       确立了计算机系统的5大基本部件:存储器,控制器,运算器,输入设备和输出设备,同时也规定了5大部件的基本功能。

(4)       `诺依曼型计算机的两大特征是“程序存储”和“采用二进制”。

(5)       `诺依漫思想实际上是电子计算机设计的基本思想,奠定了现代电子计算机的基本结构,开创了程序设计的步骤。

5 请简述程序设计的一般步骤。

 程序设计的基本过程一般由分析所求解的问题,抽象数学模型,选择合造算法,编写程序,调试通过直至得到正确结果等几个阶段所组成。其设计步骤可以分为:

(1)       确定要解决的问题。

(2)       分析问题,建立数学模型。

(3)       选择计算的方法。

(4)       确定数据结构和算法。

(5)       绘制流程图。

(6)       编写程序。

(7)       调试程序。

(8)       整理资料,交付使用。

6 何谓算法,算法有什么性质?

  算法就是为解决一个特定问题而采取的特定的有限步骤。一个完整的计算机算法必须满足下述5个准则或标准:有穷性,确定性,可行性,输入性,输出性。

  具有上述5个特性才能称为算法,而其中最重要的是算法的有穷性,如果不具备有穷性的性质,仅具有另外4种性质,吸能称为计算过程或计算方法,而不是算法。

 

7 执行高级语言编写的程序一般要经过怎样的编译过程?

  高级语言源程序经编译后得到目标码程序,但它还不能立即装入机器执行,编译后得到的目标模块还需进行连接。连接程序找出需要连接的外部模块并到模块库中找出被调用的模块,调入内存并连接到目标模块上,形成可执行程序。执行时,把可执行程序加载到内存中合适的位置(?些时得到的是内存中的绝对地址)就可执行产生运行结果。

8 高级语言解释执行的一般步骤是什么?解释招待有什么缺点?

  解释执行需要一个解释程序,它将源代码程序逐句读入,然后直接分析语句的含义,立刻给出执行结果。由于解释执行只看到一个语句,难于优化,执行效率较低。

9请简要介绍面向过程式语言中的三种程序设计的基本结构。

   顺序结构是指按先后顺序从前到后执行的语句序列。这些语句,也可能有明确的顺序关系,即后一个程序语句依赖于前一个语句,也可能它们之间没有明确有顺序关系,即某些语句的先后顺序并不太重要,一个语句逻辑性并不从属于另一些语句。

   选择结构是指根据判定条件控制一些语句是否执行的语句。选择结构可用if-then, if –then-elsecase(switch)等语句进行描述。当判定条件成立时需要一组语句,且不成立时不需要执行这些语句,那么应采用if-then语句。当判定条件成立时需要执行一组语句,否则需要执行另一组语句,可采用if-thdn-else语句。当根据表达式的取值情况在多个动作中选取其一执行时,可采用case语句。

  循环结构是指可重复执行一组语句(称为循环体)的程序语句。根据重复方式的不同,循环结构可分为while型循环,until型循环和for型循环。While型循环是在指定的条件(称为循环条件)成立时,重复执行循环体,其特点是执行循环体前先判定循环体,直到循环条件成立才结束该重复,其特点是每执行一次循环体后判定循环条件,因此至少执行一次循环体,for型循环将循环体重复执行给定次数,其特点是循环开始前可确定循环次数。

10什么是面向过程式语言?有什么特点?

面向过程式语言,也叫命今式语言或强制式语言,它是通过指明一列可执行的运算及运算的次序来描术计算过程的语言。

命立式语言以冯`诺依曼式计算机体系结构为背景。机器语言与汇编语言是最早问世的命立式语言。FORTRANALGOLGOBOLPASCALCADA等高级语言也属过程式语言,其变量对应于存储单元。对变量的访问就是对相应存储单元的访问。各个语句在程序中的顺序以及转向语句等控制语句则明确规定了机器的执行步骤,这就是冯`诺依曼式体系结构的思维方式,在程序设计中的反映。

过程式语言程序的本质是重复地,按步地计算低级(非抽象)值并将之赋给变量(对象),这就迫使程序人员去关心比较低级的细节,而这不适用于设计复杂算法。因此,几十年来过程式语言一直向着隐蔽低级机器属性,提高程序层次与抽象性的方向发展。

11 结构化程序设计方法的主要技术是什么?

     结构化程序设计方法的主要技术是自顶向下,逐步求精。具体地说, 就是在接受一个任务之后,纵观全局,先设想好整个任务分为几个子任务。每一个子任务又可以进行细分,直到不需要细分为止。这种方法就叫做“自顶向下,逐步求精”。

采用这方法考虑问题比较周全,结构清晰,层次分明。用这种方法也便于验正算法的正确性。在向下一层细分之前应检查本层分时都不太复杂。因此容易保证整个算法的正确性。由于每一层向下细分时都不太复杂,因此容易保证整个算法的正确性。检查时也是由上而下逐层检查,这样做思路清晰,可以有条不紊地一步一步地进行,既严谨又方便。

12结构化程序设计的主要特征与风格是什么?

  结构化程序设计的主要特征与风格如下所述。

(1)       一个程序按结构化程序设计方式构造时,由三种基本控制结构:顺序结构,选择结构和循环结构构成。

(2)       有限制地使用goto语句。鉴于goto语句的存在使程序的静态书写顺序与动态执行顺序十分不一致,导致程序难读难理解,容易存在潜在的错误,难于证明正确性,有人主张程序中禁止使用goto语句,但有人则认为goto语句是一种有效设施,不应全盘否定而完全禁止使用。结构程序设计并不在于是否使用goto语句,因此作为一种折哀,允许在程序中有限地使用goto语句。

(3)       往往籍助于体现结构化程序设计思想的所谓结构化程序设计语言来书写结构程序,并采用一定的书写格式以提高程序结构的清晰性,增进程序的易读性。

(4)       它强调了程序设计过程中人的思维方式与规律,是一种自顶向下的程序设计策略,它通过一组规则,规律与特有的风格对程序设计细分和组织,对于小规模程序设计,它与逐步精化的设计策略相联系,即采用自顶向下,逐步求精的方法对其进行分析和设计;对于大规模程序设计,它则与模块化程序设计策略相结合,即将一个大规模的问题划分为几个模块,每一个模块完成一定的功能。

13什么是软件?什么是软件工程?

   计算机系统中的程序及其文档称为软件。其中,程序是计算机任务的处理对象和处理规则的描述,文档是为了理解程序所需的阐述性资料。细言之,软件一词具有三层含义。一为个体含义,即指计算机系统中的程序及其文档:二为整体含义,即指在特定计算机系统中所有上述个体含义下的软件的总称,亦即计算机系统中硬件除外的所有成分。三为学科含义,即指在研究,开发,维护以及使用前述含义下的软件所涉及的理论,方法,技术所构成的学科。

   软件工程是应用计算科学数学及管理科学等原理,开发软件的工程,它借鉴传统工程的原则,方法,以提高软件质量,降低开发成本为目的。其中,计算科学数学用于构造模型和算法,工程科学用于制订规范,设计范型,评估成本等。管理科学用于计划,资源,质量,成本等管理。

软件工程是一门交叉性学科,迄今为止,软件工程的研究与应用已取得很大成就,大大绥解了软件危机,但是软件的开发还是一项艰巨任务。对于软件的如何组织和开发还在不断地发展之中。

14在软件工程过程中围绕工程设计,工程支持和工程管理应当遵循什么基本原则?

围绕工程设计,工程支持以及工程管理,提出了以下四条基本原则。

第一条原则是选取适宜的开发模型。该原则与系统设计有关。在系统设计中,软件需求,硬件需求以及其它因素之间是相互制约,相互影响的,经常需要权衡。因此,必须认识需求定义易变性,采用适宜的开发模型予以控制,以保证软件产品满足用户的要求。

第二条原则是采用合适的设计方法。在软件设计中通常要考虑软件的模块化,抽象与信息隐蔽,局部化,一致性以及适应性等。特征。合适的设计方法有助于这些特征的实现,以达到软件工程的目标。

第三条原则是提供高质量的工程支持。在软件工程中,软件工具与环境对软件过程的支持颇为重要。软件工程项目的质量与开销直接取决于对软件工程所提供的支撑质量和效用。

第四条原则是重视开发过程的管理,直接影响可用资源的有效利用。生产满足目标的软件产品,提高软件组织的和产能力等问题。因此,仅当软件过程予以有效管理时,才能实现有效有效的软件工程。

15,什么是软件的生存周期?如何划分软件的生存周期?

  软件产品从形成概念开始,经过开发,使用和维护,直至最后退役的全过程称为软件生存周期。

根据软件所处的状态,特征及软件开发活动的目的,任务可以将生存周期划分为若干阶段。一般说来,软件生存周期包括软件定义,软件开发,软件使用与维护三个部分,并可进一步细分为可行性研究。需求分析,概要设计,详细设计,实现,组装测试,确认测试,使用,维护和退役十个阶段。

16瀑布模型的主要思想和特点是什么?

  瀑布模型也称软件生存周期模型,根据软件生存周期各个阶段的任务,瀑布模型从可行性研究(或称系统需求分析)开始,逐步进行阶段性变换,直至通过确认测试并得到用户确认的软件产品为止,瀑布模型上一阶段的变换结果是下一阶段变换的输入,相邻的两个阶段具有因果关系,紧密相联。一个阶段工作的失误将蔓延到以后的各个阶段。

为了保证软件开发的正确性,每一阶段任务完成后,都必须对它的阶段性产品进行评审,确认之后再转入到一阶段的工作,评审过程发现错误和疏漏后,应该反馈到前面的有关阶段修正错误,弥补疏漏,然后再重复前面的工作,直至某一阶段通过评审后再进入下一阶段,这种形式的瀑布模型是带有反馈的瀑布模型。

瀑布模型在软件工程中占有重要的地位,它提供了软件开发的基本框架,这比依靠“个人技艺”开发软件好得多。它有利于大型软件开发过程中人员的组织和管理,有利于软件开发方法和工具的研究与使用,从而提高了大型软件项目开发的质量和效率。

瀑布模型的主要特点是:阶段间的顺序性和依赖性,开发过程是一个严格的下导式过程,即前一阶段的输出最后一阶段的输入,每一个阶段工作的完成需要确认,而确认过程是严格的追溯式过程,后一阶段发现得越晚解决问题要通过前一阶段的重前确认来解决。因此,问题发现得越得解决问题的代价就越高。

瀑布模型的主要缺点是:

(1)       在软件开发初始阶段指明软件系统的全部需求是困难的,有时甚至是不现实的。

(2)       软件开发是个知识密集型的开发活动,需要人们合作交流才能完成,但在瀑布模型中没有这方面的体现 ,随着软件开发项目规模的日益庞大,由此引发的问题显得更为严重。

17快速原型法的主要思想各特点是什么?

快速原型法是针对瀑布模型(即传统的生存周期法)提出来的一种方法,它的基本思想是回避(或暂时回避)传统的生存周期法中的一些难点,顺从用户需求出发,快速建立一个原型。使用户通达这个原型初步表达出自已的要求,在征求用户对原型意见的过程中,进一步修改,完善,逐步靠近用户的全部需求,最终形成一个完全全满足用户要求的新体系。因此,快速原型濡的最大特点是快捷,且避免了许多由于不同理解而造成的错误。

快速开发原型的途径有三种。

(1)       利用计算机模拟软件系统的人机界面和人机交互方式。

(2)       开发一个工作原型,实现软件系统的部门功能,而这部分功能是重要的,也可能是容易产生误解的。

(3)       利用类似软件向客房展示软件需求中的部分或全部功能。

为了快速开发原型,要尽量采用软件重用技术,在算法时/空开销方面也可以让步,以便争取时间,尽快向用户提供原型。原型应充分展示软件的可见部分,如数据的输入方式,人机界面,数据的输出格式等。

原型模型在各个阶段用户反馈活动的基础上,突出了快速的改进过程,它改变了瀑布模型的线性结构,采用逐步求精方法使原型逐步完善,以满足用户的要求,是一种在新的高层次上不断反复推进的过程。

由于原型是用户和软件开发人员共同设计和评审的,因此利用原型能统一用户和软件开发人员对软件项目需求的理解,有助于需求的定义和确认,利用原型定义和确认软件需求之后,就可以对软件系统进行设计,编码,测试和维护。

原型系统的不足之处有以下两点:

(1)                  为了使系统尽快运行起来,系统开发人员在初期往往考虑不周全,有可能使原型不能成为最终软件产品的一部分,只是一个示例而已,这样,在实际开发软件产品是,仍有许多工作要做。

(2)                  原型模型需要大量完备和实用的软件工具的支持才能实现,即原型模型对工具和环境依赖性较高。

                                                                         程序设计题

1,小明有5本新书,要借给AB C ,三位小朋友,若每人每次只能借一本, 则可有多少种不同的借法?

main ( )

{ int a , b , c , count=0

for ( a=1 ; a<=5 ; a++ )

for(b=1;b<=5; b++ )

for (c=1 ; a !=b && c<=5 ; c++ )

/*当前两个人借不同的书时,穷举第三个人的借本情况*/

If ( c !=A. && c ! =b )

Printf (count%8 ? ”%2d:%d,%d,%d,” : ’’ %2d:%d,%d,%d\n”,++count,a,b,c);

}

 

2百钱百鸡问题。中国古代数学家张丘建在他的《算经》中提出了著名的“百钱百鸡问题”:鸡翁一,值钱五:鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡,翁,母,雏,各几何?

  #include <stdio.h>

  main  ( )

{int x , y , z , j =0 ;

for  (x=o; x<=20; x++)

for (y=0 ; y<= (100-5*x)/3;y++ )

{z=100-x-y ;

If (z%3==0 && 5 *x+3 * y +z/3==100 )

Printf (“%2d:cock=%2d hen=%2d chicken =%2d\n”,++j,x , y, z

}

 

三、编程题
1
、从键盘输入3个整数,输出其中最大数。
答:#include <stdio.h>
      void main()
            {
            int a,b,c,max;
            printf(“Please input 3 integers:\n”);
            scanf(“%d %d %d”,&a,&b,&c);
            max=a;
            if(b>a) max=b;
            if(c>x) max=c;
            printf(“Max=%d”,max);
            }
2
、由36块砖,共36人搬,成年男子一次搬4块砖,成年女子一次搬3块砖,儿童两个人抬1块砖,恰好一次全部搬完,编程求出成年男子、成年女子和儿童各有多少人?
答:#include <stdio.h>
      void main()
        {
         int x,y,z;
         for(x=0;x<=36/4;x++)
            for(y=0;y<=36/3;y++)
             {
              z=36-x-y;
              if(4*x+3*y+z/2==36 && z%2==0)
                printf(“x=%d,y=%d,z=%d”,x,y,z);
              }
         }


3
、按下列公式sn12+22……+n2
编写计算并输出s值,其中的n值由键盘输入。
答:#include <stdio.h>
      void main()
            {
            int x,i,s=0;
            for(i=1;i<=x;i++)
                s=s+i*i;
            printf(“s=%d”,s);
            }
4
、编写一程序,从键盘输入10个实数,计算并输出算数平均数
答:#include <stdio.h>
      void main()
            {
            float x, s=0;
            for(i=0;i<10;i++)
            {
                scanf(“%f”,&x);
            s=s+x;
                }
            printf(“The average is %f”,s/10);
            }
5
、求方程ax2+bx+c=0的根。其中abc由键盘输入,设b2-4ac>0
#include <math.h>
#include <stdio.h>
void main()
{
  float a,b,c,disc,x1,x2,x3,p,q;
  printf("please input float a,b,c:\n");
  scanf("%f%f%f",&a,&b,&c);
  disc=b*b-4*a*c;
  p=-b/(2*a);
  q=sqrt(disc)/(2*a);
  x1=p+q;
  x2=p-q;
  printf("x1=%5.2f,x2=%5.2f\n",x1,x2);  
}

6
、编写程序。从键盘输入h值,输出h行用*号组成的平行四边形。例:输入h=4,输出的图形如下:
            * * * *
             * * * *
           * * * *
         * * * *
答:#include <stdio.h>
      void main ( )
{ int h, k, j;
  scanf ("%d", &h);
for ( k=1; k<=h; k++)
{ for ( j=1; j<=h-k; j++)
         printf (" ");
     for ( j=1; j<=h; j++)
         printf ("*");
     printf("\n");
}
}
7
、利用穷举法编写一个算法判断给定的正整数n是否是素数,即判断n是否只能被1和自身整除。
答:#include <math.h>
#include <stdio.h>
      void main()
{
int m,i,k;
scanf("%d",&m);
k=sqrt(m);
for(i=2;i<=k;i++)
if(m%i==0) break;
if(i>=k+1)
printf("%d is a prime number\n",m);
else
printf("%d is not a prime number\n",m);   
}