计算机软件技术基础

《计算机软件技术基础》第一章算法1.1算法的基本概念算法：指解题方案的准确而完整的描述算法的基本特征：能行性（算法中的每一个步骤必须能够实现；算法执行的结果要能够达到预期的目的）确定性（算法中的每一个步骤都必须是有明确定义的，不能摸棱两可，也不能有多义性）有穷性（算法必须能在执行有限个步骤之后终止）拥有足够的情报（算法执行的结果总是与输入的初始数据有关。

不同输入对应不同输出）算法：是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的、明确的，此顺序将在有限的次数下终止。

算法的基本要素：1.算法中对数据的运算和操作（算术运算、逻辑运算、关系运算、数据传输【赋值、输入、输出】）2.算法的控制结构（算法中各操作之间的执行顺序）1.2算法描述语言C语言描述和简单的算法描述语言（1）符号与表达式：符号主要用以表述变量名、数组名等（2）赋值语句（3）控制转移语句：无条件转移语句形式：GOTO 标号条件转移语句形式IF C THEN SIF C THEN S1ELSE S2（4）循环语句WHILE语句：WHILE C DO SFOR语句：FOR i=init TO limit BY step DO S（5）其他语句EXIT语句：退出某个循环，使控制转到包含EXIT语句的最内层的WHILE或FOR循环后面的一个语句去执行RETURN语句：结束算法的执行（允许使用用引号括起来的注释信息）READ(INPUT)和WRITE(PRINT/OUTPUT)语句：用于输入输出（6）算法中的注释总是用一对方括号【】括起来；复合语句用一对花括号{}括起来1.3算法设计基本方法1.列举法【例1.1】基本思想：根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的（通常解决“是否存在”“有多少种可能”类型问题）特点：算法比较简单，但列举情况较多时，工作量将很大寻找路径、查找、搜索等问题采用列举法有效2.归纳法基本思想：通过列举少量的特殊情况，经过分析，最后找出一般的关系3.递推法（数学例题）指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果（本质属于归纳法）4.递归基本思想：将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些简单的问题后，再沿着原来分解的逆过程逐步进行综合【例1.3】自己调用自己的过程称为递归调用过程递归分为直接递归：一个算法P显式地调用自己间接递归：算法P调用另一个算法Q，而算法Q又调用算法P5.减半递推技术（分治法）减半：将问题的规模减半，而问题的性质不变递推：重复“减半”的过程【例1.4】6.回溯法通过对问题的分析，找出一个解决问题的线索；然后沿着这个线索逐步试探。

计算机软件技术基础复习题和思考题答案1.5.1 复习题1. 解释计算机程序的概念。

计算机程序(computer programs)，简称程序，是指计算机的指令序列。

2. 什么是源代码程序？源代码是指以程序设计语言编写的、可读的语句和声明的集合，程序设计人员的工作就是使用程序设计语言编写源代码，源代码经过编译后转变为计算机可以执行的程序。

3. 什么是可执行程序？可执行程序是指包含了计算机可以直接执行的指令的文件。

为了与源代码相区别，可执行程序又被称为二进制代码。

4. 什么是计算机软件技术？计算机软件技术是与软件的设计、实施和使用相关的多种技术的统称。

软件的设计与实施涉及到程序设计语言、算法和数据结构、数据库系统、多媒体、软件工程等技术，软件的使用涉及到质量、可靠性、专利、知识产权、道德、法律等管理和技术。

5. 如何对软件进行分类？可以根据软件的功能进行分类，也可以根据软件的不同开发方式进行划分，还可以从软件的使用方式进行分类。

根据软件的功能来划分是一种主要的分类方式，可以把软件分为系统软件、编程软件和应用软件3大类型。

6. 什么是系统软件？系统软件(system software)指管理和控制计算机硬件、使计算机工作的软件。

系统软件是一种非常重要的软件类型，它为用户提供了一种操作计算机硬件的便捷方法，为其他程序提供了运行的基础。

7. 常见的系统软件有哪些？根据系统软件的功能特点，可以继续划分为操作系统、设备驱动程序、实用工具以及其他系统软件。

8. 什么是操作系统？操作系统(operating system，OS)是位于计算机系统中的硬件和软件之间的接口，负责管理和协调计算机硬件的操作和计算机有限资源的共享。

9. 列出3个典型的操作系统。

主要的操作系统包括微软公司的Windows系列操作系统、Unix和类Unix操作系统、苹果公司的Mac OS X操作系统、Linux操作系统等。

任意列出3个即可。

10. 什么是编程软件？编程软件(programming software)又称为编程工具(programming tool)或软件开发工具(software development tool)，是一种软件开发人员用于创建、调试、维护其他程序和应用软件的软件工具。

计算机软件技术基础是指计算机软件开发的基础知识，它是计算机系统软件开发的基础。

计算机软件技术基础包括计算机程序设计语言、计算机系统结构、数据库技术、网络技术和操作系统等，这些基础知识都是计算机软件开发的基础。

计算机程序设计语言是计算机软件开发的基础，它是程序员使用的语言，可以用来描
述或定义计算机系统的结构和行为。

常用的计算机程序设计语言有C、C++、Java、Python等。

计算机系统结构是计算机系统的基本框架，它定义了计算机系统的硬件、软件、操作
系统和应用软件之间的关系，以及计算机系统的运行原理。

数据库技术是计算机软件开发的基础，它是用来管理大量数据的技术，可以帮助用户
存储、组织和检索数据。

常用的数据库技术有MySQL、Oracle、Microsoft SQL Server等。

网络技术是指将计算机系统连接到网络的技术，它可以帮助用户在不同的计算机系统
之间共享信息、文件和资源。

常用的网络技术有TCP/IP、HTTP、FTP等。

操作系统是计算机软件开发的基础，它是一种计算机软件，可以管理计算机系统的软
硬件资源，并支持用户运行应用程序。

常用的操作系统有Windows、Mac OS、Linux等。

计算机软件技术基础是计算机系统软件开发的基础，它包括计算机程序设计语言、计
算机系统结构、数据库技术、网络技术和操作系统等。

这些基础知识对计算机软件开发至
关重要，只有充分理解和掌握这些知识，才能开发出高质量的计算机软件。

第1章 概 述教学提示：本章主要讲授计算机的发展概况；计算机软件发展的几个阶段；计算机系统的组成；计算机软件的分类以及常用的系统软件和应用软件的介绍。

教学要求：了解计算机的发展过程；掌握计算机软件发展经历的几个阶段；了解常用的高级语言；了解计算机网络软件及数据库软件；掌握软件的分类；简单介绍常用的工具软件。

1.1 计算机软件的发展计算机是由一系列电子元件组成的、具有处理信息能力的机器。

世界上第一台计算机是1946年在美国的宾西法尼亚大学研制成功的。

计算机诞生60多年来，发展极为迅速，更新换代非常快。

计算机先后以电子管、晶体管、集成电路、大规模和超大规模集成电路为主要元器件，共经历了四代变革，现在已进入第五代的研制时期。

每一代的变革在技术上都是一次新的突破，在性能上都是一次质的飞跃。

第一代为电子管时代(1946年—1957年)。

在这个阶段计算机的逻辑器件采用电子管，通常称为电子管计算机。

它的内存容量很小，仅有几千字节，运算速度低，且成本很高。

第二代为晶体管时代(1958年—1964年)。

与第一代相比，该阶段计算机的主要逻辑器件采用晶体管，即晶体管计算机。

存储器由磁心构造，内存容量扩大到几十千字节。

第三代为集成电路时代(1965年—1972年)。

在这个阶段计算机的主要逻辑器件采用集成电路。

不仅使计算机体积大大减小，耗电显著降低，而且使运算速度大大提高。

第四代为大规模和超大规模集成电路时代(1972 年至今)。

在这个阶段计算机的逻辑器件采用大规模集成电路(LSI)。

这一代计算机的性能较前三代有较大提高，主要依靠器件的变革和系统结构的改进，而新一代计算机总是朝着体积小、耗电少、速度快、最优性价比及使用方便等方向发展。

第五代为超大规模集成电路和人工智能计算机时代，目前尚处于研制阶段。

第五代计算机是超大规模集成电路、高级软件工程、人工智能、新型计算机系列的综合产物。

它是一种更接近人的人工智能计算机，它能理解人的语言、文字和图形，无须编写程序，靠讲话就能对计算机下达命令，驱使它工作。

标题：深度解读《计算机软件技术基础教程刘彦明》1.引言在当今信息化社会，计算机软件技术已经成为人们生活中不可或缺的一部分。

而《计算机软件技术基础教程刘彦明》作为一本权威的教材，为学习者提供了全面而深入的计算机软件技术知识。

本文将从不同角度对此教材进行评估和解读，以帮助读者更好地理解和运用其中的知识。

2.教材内容概述《计算机软件技术基础教程刘彦明》一书内容丰富，主要涵盖了计算机软件技术的基础知识、原理和应用。

从计算机基础概念、数据结构与算法、操作系统原理、数据库技术到软件工程等方面进行了系统而全面的教学。

该教材由浅入深地介绍了计算机软件技术的重要概念和核心知识，适合初学者和进阶者学习使用。

3.深度学习与广度拓展在深度方面，《计算机软件技术基础教程刘彦明》对每个知识点都进行了详细的解释和案例分析，让读者能够逐步理解和掌握其中的核心概念。

与此教材还注重广度拓展，通过丰富的实例和案例，让读者能够将知识应用于实际问题中，提高自己的综合素质和解决问题的能力。

4.个人观点与理解在我看来，《计算机软件技术基础教程刘彦明》不仅是一本教学用书，更是一本实用性强、知识系统性广的专业参考书。

通过学习这本教材，我不仅提高了自己的计算机软件技术水平，还培养了严谨的思维和解决问题的能力。

我相信这本教材将成为我未来学习和工作的重要参考资料，对我个人和职业发展有着重要的意义。

5.总结与回顾《计算机软件技术基础教程刘彦明》不愧为一本优秀的教材，它不仅内容深入浅出，系统全面，而且实用性强，适合不同层次的读者学习使用。

通过认真学习和实践，读者能够从中获得关于计算机软件技术的全面知识和实际经验，为个人的学习和职业发展打下坚实的基础。

在撰写本文的过程中，我通过对《计算机软件技术基础教程刘彦明》的深入研究和思考，更加全面、深刻和灵活地理解了其中的知识。

相信读者在阅读本文后，也能对这本教材有一个更深入的认识和理解。

愿本文能成为您对《计算机软件技术基础教程刘彦明》的一次深度认识和全面理解的引导。

数据结构习题答案第一节概论一、选择题1．要求同一逻辑结构的所有数据元素具有相同的特性，这意味着( )。

A．数据元素具有同一的特点 *B．不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等2．数据结构是一门研究非数值计算的程序设计问题中计算机的( (1) )以及它们之间的( (2) )和运算的学科。

(1) A．操作对象 B．计算方法 *C．物理存储 D．数据映像(2) A．结构 *B．关系 C．运算 D．算法3．数据结构被形式地定义为(D，R)，其中D是( (1) )的有限集合，R是D上( (2) )的有限集合。

(1) A．算法 *B．数据元素 C．数据操作 D．逻辑结构(2)A．操作 B．映像 C．存储 *D．关系4．在数据结构中，从逻辑上可以把数据结构分为( )。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构 *C．线性结构和非线性结构 D．内部结构和外部结构5．线性表的顺序存储结构是一种( )的存储结构。

*A．随机存取 B．顺序存取 C．索引存取 D．Hash存取6．算法分析的目的是( )。

A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 *C．分析算法的效率以求改进 D．分析算法的易懂性和文档性7．计算机算法指的是( (1) )，它必须具备输入、输出和( (2) )等五个特征。

(1) A．计算方法 B．排序方法 *C．解决某一问题的有限运算序列D．调度方法(2) A．可行性、可移植性和可扩充性 *B．可行性、确定性和有穷性 C．确定性，有穷性和稳定性 D．易读性、稳定性和安全性8．线性表若采用链表存储结构，要求内存中可用存储单元的地址( )。

A．必须是连续的 B．部分必须是连续的 C．一定是不连续的 *D．连续不连续都可以9．在以下的叙述中，正确的是( )。

A．线性表的线性存储结构优于链式存储结构 *B．二维数组是它的每个数据元素为一个线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出10．根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式，其中解释错误的是( )。

一、单项选择题(1)一个算法应该是（）。

A) 程序B) 问题求解步骤的描述C) 要满足五个基本属性D) A和C(2)算法指的是（）。

A) 计算机程序B) 解决问题的计算方法C) 排序算法D) 解决问题的有限运算序列。

(3)与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。

A) 存储结构B) 逻辑结构C) 算法D)操作(4)从逻辑上可以把数据结构分为（）两大类。

A) 动态结构、静态结构B) 顺序结构、链式结构C) 线性结构、非线性结构D) 初等结构、构造型结构(5)下列叙述中正确的是( )。

A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率(6)数据的基本单位是（）A) 数据项B) 数据类型C) 数据元素D) 数据变量(7)下列程序的时间复杂度为（）i=0；s=0；while（s<n）{ i++；s=s+i；}A) O（n）B) O（n2）C) O（n）D) O（n2）(8)下列程序段的渐进时间复杂度为（）。

for( int i=1;i<=n;i++)for( int j=1;j<= m; j++)A[i][j] = i*j ;A）O(m2) B）O(n2) C）O(m*n) D）(m+n) (9)程序段如下：sum=0；for(i=1;i<=n;i++)for(j=1;j<=n;j++)sum++；其中n为正整数，则最后一行的语句频度在最坏情况下是（）。

A）O(n）B) O(nlogn) C) O(n3) D) O(n2) (10)在下面的程序段中，对x的赋值语句的频度为（）。

for ( i=1; i>=n ; i++)for ( j=1; j>=n ; j++)x:=x+1;A) O(2n) B)O(n) C) O(n2) D) O(log2n)(11)程序段for ( i:=n-1; i<=1; i--）for ( j:=1; j>=i ; j++)if (a[j]>a[j+1] ){ t=a[j]; a[j]= a[j+1]; a[j+1]= t; }其中n为正整数，则最后一行的语句频度在最坏情况下是（）。

《计算机软件技术基础》试题1.线性表的链式储存结构与次序储存结构对比优点是CD 。

A.所有的操作算法实现简单B.便于随机存取C.便于插入和删除D.便于利用零落的储存器空间2.线性表是拥有n个 C 的有限序列。

A.表元素B.字符C.数据元素D.数据项E.信息项3.若长度为n的线性表采纳次序储存结构, 在其第I个地点插入一个新元素的算法的时间复杂度为 C 。

（1≤I≤n+1）A.O(0)B.O(1)C.O(n)D.O(n2)4.设A是一个线性表(a1,a2,…,an), 采纳次序储存结构, 则在等概率的前提下, 均匀每插入一个元素需要挪动的元素个数为 B , 均匀每删除一个元素需要挪动的元素个数为A ；若元素插在ai与ai+1之间(0≤I≤n-1)的概率为, 则均匀每插入一个元素所要挪动的元素个数为 C ；A. B.C. D.5.以下函数中, 按它们在时的无量大阶数, 最大的是 D 。

A.lognB.nlognC.2n/2D.n!6.将以下图所示的s所指结点加到p所指的结点以后, 其语句应为: D 。

A.s->next=p+1.p->next=s;B.(*p).next=s.(*s).next=(*p).next;C.s->next=p->next.p->next=s->next;D.s->next=p->next.p->next=s;7.将两个各有n个元素的有序表合并为一个有序表时, 其最少的比较次数是A 。

A.nB.2n-1C.n-1D.2n8.下边的程序段是合并两个无头结点链表(ha和hb)为一个无头结点链表ha的过程, 作为参数的两个链表都是按结点的data域由大到小链接的。

合并后新链表的结点仍按此方式链接。

请填写下述空框, 使程序能正确运转。

#define NULL 0typedef struct node{int data;struct node *next;}node, linklisttype;void combine(linklisttype *ha, linklisttype *hb){linklisttype *h, *p;h = (linklisttype *)malloc(sizeof(linklisttype));h->next = NULL;p = h;while(ha != NULL && hb != NULL)if(ha->data>=hb->data){ /*较大的元素先插入*/p->next = (1) ;p = (2) ;(3) ;}else{p->next = (4) ;p = (5) ;(6) ;}if(ha==NULL) (7) ;if(hb==NULL) (8) ;ha = h->next;free(h);}参照答案: (1) ha (2) p->next (3) ha=ha->next(4) hb (5) p->next (6) hb=hb->next(7) p->next=hb (8) p->next=ha9.假如表A中所有元素(a1,a2,…,an)与表B的一个次序子表(bk,bk+1,…bk+n-1)完好同样（即a1=bk,a2=bk+1,…an=bk+n-1）, 则称表A包含在表B中。