软件技术基础

《计算机软件技术基础》第一章算法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.回溯法通过对问题的分析，找出一个解决问题的线索；然后沿着这个线索逐步试探。

说明每个实验题目含有一个main函数和一些函数, 与实验题目相关的基本运算的函数定义和main函数定义的代码在附录以及对应的文件夹中给出, 供上机实验参考使用。

对于每个题目, 只需要根据题目要求设计算法, 补充函数定义, 然后对程序进行编译、调试。

实验一线性表一、实验目的1．熟悉线性表的顺序和链式存储结构2．掌握线性表的基本运算3．能够利用线性表的基本运算完成线性表应用的运算二、实验内容设有一个线性表E={e1, e2, …, en-1, en}, 设计一个算法, 将线性表逆置, 即使元素排列次序颠倒过来, 成为逆线性表E’={ en , en-1 , …, e2 , e1 }, 要求逆线性表占用原线性表空间, 并且用顺序表和单链表两种方法表示, 分别用两个程序来完成。

（文件夹: 顺序表逆置、单链表逆置）已知由不具有头结点的单链表表示的线性表中, 含有三类字符的数据元素（字母、数字和其他字符）, 试编写算法构造三个以循环链表表示的线性表, 使每个表中只含有同一类的字符, 且利用原表中的结点空间, 头结点可另辟空间。

（文件夹: 分解单链表）实验二栈和队列一、实验目的1．熟悉栈和队列的顺序和链式存储结构2．掌握栈和队列的基本运算3．能够利用栈和队列的基本运算完成栈和队列应用的运算二、实验内容1．设单链表中存放有n个字符, 试编写算法, 判断该字符串是否有中心对称的关系, 例如xyzzyx是中心对称的字符串。

（提示: 将单链表中的一半字符先依次进栈, 然后依次出栈与单链表中的另一半字符进行比较。

）（文件夹: 判字符串中心对称）假设以数组sequ[m]存放循环队列的元素, 同时设变量rear和quelen 分别指示循环队列中队空的条件：sq->quelen==0；队满的条件：sq->quelen==m。

（文件夹：循环队列）实验三串一、实验目的1．熟悉串的顺序存储结构2．掌握串的基本运算及应用二、实验内容1. 串采用顺序存储结构, 编写朴素模式匹配算法, 查找在串中是否存在给定的子串。

大学计算机基础第五章第五章软件技术基础1.程序设计语言（1）机器语言和汇编语言由计算机硬件系统可以识别的指令组成的语言称为机器语言。

汇编语言是将机器指令映射为一些可以被人读懂的助记符。

由于计算机只能识别机器语言，所以汇编语言通常需要通过汇编程序翻译为机器语言。

汇编语言的翻译软件称为汇编程序，它可以将程序员写的助记符直接转换为机器指令，然后由计算机去识别和执行。

用机器语言编写的程序是计算机可以直接执行的程序。

用机器语言编写的程序，代码长度短，执行效率高。

但是，这种语言的缺点也很明显。

最主要的是编写机器语言程序必须要熟知CPU 的指令代码，编写程序既不方便，又容易出错，调试查错也非常困难。

而且编写的程序只能在特定的机器上运行，没有通用性。

（2）高级语言高级语言源程序翻译为指令代码有两种做法：编译或者解释。

编译通过编译程序来完成。

解释则是通过解释程序完成。

解释的结果产生可以直接执行的指令。

编译的结果是得到目标程序。

目标程序也是要经过连接才会得到可执行程序目前应用比较广泛的几种高级语言由FORTRAN/BASIC/PASCAL/C等。

（3）面向对象的语言（4）未来的语言2、语言处理程序语言处理程序是把源程序翻译成机器语言的程序，可分为三种：汇编程序、编译程序和解释程序。

（1）汇编程序把汇编语言源程序翻译成机器语言程序的程序称为汇编程序，翻译的过程称为汇编。

汇编程序在翻译源程序时，总是对源程序从头到尾一个符号一个符号地进行阅读分析，一般用两遍扫描完成对源程序的加工转换工作。

汇编语言在翻译的同时，还对各种形式的错误进行检查和分析，并反馈给用户，以便修改。

反汇编程序也是一种语言处理程序，它的功能与汇编程序相反，它能把机器语言程序转换成汇编语言程序。

（2）编译程序编译程序是把高级语言源程序（如Fortran、Pascal、C 等）翻译成目标程序（机器语言程序）的一种程序，翻译的过程称为编译。

（3）解释程序解释程序也是一种对高级语言源程序进行翻译处理及的程序。

软件技术基础知识第一章1、算法和算法的特点2、数据结构：指相互关联的数据元素的集合。

数据结构分为逻辑结构和物理结构。

逻辑结构：表示了数据的逻辑关系（前后件关系）。

按照逻辑关系的不同分为：线形结构和非线形结构。

物理结构：表示了数据在计算机上的存放形式，也称存储结构。

按照存放形式的不同分为：顺序存储和链式存储。

3、线形结构的条件：4、线形结构通常称之为线性表。

顺序存储的线性表称为顺序表，链式存储的线性表称为线性链表。

5、对与空的数据结构可以为线性结构也可以为非线性结构。

6、顺序表和线性链表的特点。

7、栈和队列的特点。

8、栈和队列可以采用顺序存储也可以采用链式存储。

9、双向链表和循环队列。

10、树和二叉树11、二叉树的基本性质①第k层最多具有的结点数。

②深度为k的二叉树最具有的结点数。

③任何二叉树对为0的结点数和度为2的结点数的关系。

12、满二叉树的特点。

13、完全二叉树的特点。

14、二叉树的遍历15、顺序查找适用的情况。

对长度为n的线形表进行顺序查找最坏的情况需要查找的次数。

16、二分法查找适用的情况。

对长度为n的线形表进行二分法查找最坏的情况需要查找的次数。

17、排序的分类。

交换类排序：冒泡排序法，最坏的情况需要比较的次数。

插入类排序法，堆排序法。

第二章1、编程的良好习惯要求：根据需要添加相应的注释，应该有良好的视觉组织，在完成功能的前提下，优先考虑可读性和清晰性，然后在考虑效率。

2、注释的分类：序言性注释和功能性注释。

3、结构化程序设计的原则。

4、结构化程序设计的基本结构。

5、对象是属性和行为的封装体。

6、对象的基本特点：标识唯一性，分类性，多态性，封装性，摸快独立性。

7、类和实例之间的关系。

类是具有共同属性和方法对象的集合，是关于对象的抽象，一个具体的对象则称之为类的一个实例。

8、消息。

9、继承、多态性。

第三章1、软件的定义及软件的特点软件是程序、数据及相关文档的集合。

特点：2、软件危机是开软件过程中所遇到的一系列的严重问题。

《操作系统》一、判断题：（bs30）√1. 能影响中断响应次序的技术是中断优先级和中断屏蔽。

（bs30）√3. 在操作系统中，进程是一个具有独立运行功能的程序在某个数据集合上的一次运行过程。

（bs30）×4. 操作系统的存储器管理部分负责对进程进行调度。

（bs30）√5. 分时操作系统通常采用时间片轮转策略为用户服务。

（bs30）√6. 作业与进程的主要区别是前者是由用户提交，后者是由系统自动生成。

（bs29）×1. 在设备管理中通道是处理输入、输出的软件。

（bs29）√3. 若无进程处于运行状态，则就绪队列为空。

（bs29）√4. 在单处理器系统中，程序的并发执行，实质上是程序的交替执行。

（bs29）×5. 分页存储管理中，页面不能映射到不连续的内存块中。

（bs28）×3. Windows是多用户多任务操作系统。

（bs28）√4. 能影响中断响应次序的技术是中断优先级和中断屏蔽。

（bs28）√6. 作业与进程的主要区别是前者是由用户提交，后者是由系统自动生成。

（bs28）×8. 中断控制方式适用于外存同CPU之间进行大量数据交换。

（bs27）√3. 进程调度按一定的调度算法，从就绪队列中挑选出合适的进程。

（bs27）√4. 在单处理器系统中，程序的并发执行，实质上是程序的交替执行。

（bs27）√6. 分页存储管理中，页面可以映射到不连续的内存块中。

（bs27）√7. 通道方式能实现外设与CPU之间直接进行数据交换。

（bs26）×1. Windows是多用户多任务操作系统。

（bs26）√4. 在计算机系统中，操作系统是处于裸机之上的第一层软件。

（bs26）×7. 中断控制方式适用于外设同CPU之间进行大量数据交换。

（bs26）×9. 进程把程序作为它的运行实体，没有程序也就没有进程。

（bs25）×1. 在操作系统中，作业调度和进程调度没有区别。

软件技术基础1. 引言软件技术基础是指软件开发过程中所必需的基本知识和技能。

为了能够高效地开发出可靠的软件系统，软件开发人员需要掌握一系列与软件开发相关的技术和概念。

本文将介绍软件技术基础的概念、原理以及其中的一些重要组成部分。

2. 软件开发生命周期软件开发生命周期是软件开发过程中的一个重要概念。

它描述了软件从概念到退役的整个过程，包括需求分析、设计、编码、测试和部署等步骤。

不同的软件开发方法和模型可能有不同的生命周期，但基本的原则是相同的。

以下是一个常见的软件开发生命周期模型：2.1 需求分析需求分析阶段是软件开发生命周期的第一步。

在这个阶段，开发人员与客户一起讨论和确定软件系统的需求。

这涉及到收集用户需求、定义系统功能和确定软件的特性。

2.2 设计设计阶段侧重于将系统需求转化为可执行的设计方案。

在这个阶段，开发人员会制定一个系统的整体架构，绘制系统的详细设计图，并确定软件的模块和组件。

编码阶段是将设计方案转化为可执行代码的过程。

在这个阶段，开发人员使用编程语言和开发工具来实现系统功能。

编码过程需要遵循一定的编码规范和设计原则，以确保代码的质量和可维护性。

2.4 测试测试阶段是对软件系统进行功能测试和性能测试的过程。

在这个阶段，开发人员会对软件进行单元测试、集成测试和系统测试，以确保软件的功能正常运行，并满足用户的需求。

2.5 部署部署阶段是将测试通过的软件部署到目标环境的过程。

这包括将软件安装在用户计算机上，并进行系统配置和调试。

3. 编程语言编程语言是软件开发的基础工具之一。

它们用于编写软件的代码，并定义了程序的结构和行为。

常见的编程语言包括C++、Java、Python等。

3.1 C++C++是一种通用的编程语言，广泛应用于系统级软件开发和高性能计算中。

它提供了面向对象的编程模型以及强大的内存控制功能。

Java是一种跨平台的编程语言，广泛用于Web开发和企业级应用开发。

它的特点是具有良好的可移植性和安全性。

《计算机软件技术基础》试题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中。