软件技术基础一、选择题1.算法的时间复杂度是指（ D ）。
A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法程序中的指令条数D. 算法执行过程中所需要的基本运算次数2.下面概念中，不属于面向对象方法的是（ B ）。
A. 对象B. 过程调用C. 类D. 继承3.下面叙述正确的是（ C ）。
A. 算法的执行效率与数据的存储结构无关B. 算法的空间复杂度是指算法程序中指令（或语句）的条数C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止D. 以上三种描述都不对4.下列模式中，能够给出数据库物理存储结构与物理存取方法的是（ A ）。
A. 内模式B. 逻辑模式C. 概念模式D. 外模式5.数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。
下列图符名标识的图符不属于数据流图合法图符的是（ A ）。
A.控制流B.加工C.数据存储D.数据源点和汇点6.下述关于数据库系统的叙述中正确的是（ D ）。
A. 数据库系统减少了数据冗余B. 数据库系统比文件系统能管理更多的数据C. 数据库系统中数据的一致性是指数据类型的一致D. 数据库系统避免了一切冗余7.结构化程序设计主要强调的是（ B ）。
A. 程序的规模B. 程序的易读性C. 程序的执行效率D. 程序的可移植性8.在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是（ D ）。
A. 可行性分析B. 详细设计C. 概要设计D. 需求分析9.下列叙述中，正确的是（ D ）。
A. 软件就是程序清单B. 软件就是存放在计算机中的文件C. 软件应包括程序清单及运行结果D. 软件包括程序和文档10.在深度为6的满二叉树中，叶子结点的个数为（ B ）。
A. 15B. 16C. 31D. 3211.完全不考虑程序的内部结构和内部特征，而只是根据程序功能导出测试用例的测试方法是（ A ）。
A.黑箱测试法B.白箱测试法C.错误推测法D.安装测试法12.数据库设计包括两个方面的设计内容，它们是（ C ）。
《计算机软件技术基础》第一章算法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)，是一种软件开发人员用于创建、调试、维护其他程序和应用软件的软件工具。
《计算机软件技术基础》试题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(n 2)4.设A 是一个线性表(a 1,a 2,…,a n )，采纳次序储存结构，则在等概率的前提下，均匀每插入一个元素需要挪动的元素个数为 B ，均匀每删除一个元素需要挪动的元素个数为A ；若元素插在a i 与a i+1之间(0≤I ≤n-1)的概率为)1()(2+-n n i n ，则均匀每插入一个元素所要挪动的元素个数为 C ； A. 21-n B. 2n C. 312+n D. 413+n 5.以下函数中，按它们在∞→n 时的无量大阶数，最大的是 D 。
A. log nB. nlog nC. 2n/2D. n!6.其语句应为： D 。
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,…,a n)与表B的一个次序子表(b k,b k+1,…b k+n-1)完好同样（即a1=b k,a2=b k+1,…a n=b k+n-1），则称表A包含在表B中。
