下载文档原格式
《计算机软件技术基础》试题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.将下图所示的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 域由大到小链接的。
数据结构习题答案 2 第一节概论 2 第二节线性表 5 第三节栈和队列15 第五节树18 第七节查找24 第八节排序28 操作系统练习题参考答案31数据结构习题答案第一节概论一、选择题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．在以下的叙述中，正确的是( )。
第1章习题部分答案1. 操作系统的发展分为那几个阶段？解：操作系统的发展经历了三个阶段：操作系统的酝酿阶段、操作系统的形成阶段、操作系统的理论化和标准化阶段。
2. 计算机软件技术开发系统包括那几个阶段？解：计算机软件开发系统的发展经历了四个阶段：机器语言阶段、汇编语言阶段、高级语言阶段、面向对象语言和可视化语言阶段。
3. 计算机软件技术的主要范畴是什么？解：计算机软件技术的主要范畴包括软件工程技术、程序设计技术、软件工具环境技术、系统软件技术、数据库技术、实时软件技术、网络软件技术、与实际工作相关的软件技术等八个领域的内容。
4. 从软件技术的发展现状来看有哪些值得我们注意的问题？解：从软件技术的发展现状来看有以下几个值得我们注意的问题：1）软件危机2）软件技术标准，软件版权和软件价值评估3）软件技术的基础研究。
1第2章习题部分答案1. 什么是软件危机？软件危机的表现有哪些？解：软件开发技术的进步为能满足发展的要求，在软件开发中遇到的问题找不到解决的方法，问题积累起来形成了尖锐的矛盾，导致了软件危机。
2. 软件危机产生的原因是什么？解：造成软件危机的原因是由于软件产品本身的特点以及开发软件的方式、方法、技术和人员引起的。
1）软件规模越来越大，结构越来越复杂。
2）软件开发管理困难而复杂。
3）软件开发费用不断增加。
4）软件开发技术落后。
5）生产方式落后。
6）开发工具落后，生产率提高缓慢。
3. 常见的软件过程模型有哪些？解：常见的软件过程模型有瀑布模型、增量模型、演化过程模型、敏捷开发4. 如何对软件质量进行评价？解：软件质量的评价主要围绕可维护性、可靠性、可理解性和效率这几个方面进行。
2第3章习题部分答案1. 软件可行性研究的目的是什么？软件可行性研究的任务又是什么？解：软件可行性研究的目的就是用最小的代价在尽可能短的时间内确定该软件项目是否能够开发，是否值得去开发。
可行性研究的任务首先需要进行概要的分析研究，初步确定项目的规模和目标，确定项目的约束和限制，把他们清楚地列举出来。
1数据库的三级模式和两级映像体系结构中，模式/内模式映像存在于概念级和内部级之间，用于定义概念模式和内模式间的对应性，其主要作用是什么。
答：作用是保证了数据与程序的物理独立性，模式/内模式之间的映像是数据的全局逻辑结构和数据的存储结构之间的映像，当数据库的存储结构发生了变化，由于模式/内模式之间的映像使数据的逻辑结构可以保持不变，因此应用程序可以不必修改。
2简述逻辑数据的独立性答：逻辑数据独立性是指应用程序与数据库的逻辑结构之间的相互独立性。
当数据的逻辑结构改变时，通过修改外模式——模式映像，保持数据的局部逻辑结构不变，应用程序是依据数据的局部逻辑结构编写的，所以应用程序不必修改。
即模式变，应用程序不变。
3何谓算法？它与程序有何区别？答：算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。
它与程序的区别⑴一个程序不一定满足有穷性，但算法是有穷性的。
⑵程序中指令必须是机器可以执行的，而算法中的指令则无此限制。
⑶算法代表了对问题的解，而程序是算法在机器上的特定实现。
4试说明栈和队列的异同。
答：相同：从数据结构的角度看，都是线性结构，都可以通过顺序表，列表实现。
不同点：⑴队列先进先出，栈先进后出。
⑵对插入和删除操作的"限定"。
栈是限定只能在表的一端进行插入和删除操作的线性表。
队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。
⑶遍历数据速度不同。
栈只能从头部取数据也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性队列怎不同，他基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影像数据结构，速度要快的多。
5何谓进程？请图示具有基本进程状态的状态转移图，并指出转移原因。
计算机软件技术基础课后答案【篇一：《计算机软件技术基础》复习题(含答案)】txt>1.线性表的链式存储结构与顺序存储结构相比优点是a. 所有的操作算法实现简单c. 便于插入和删除 b. 便于随机存取d. 便于利用零散的存储器空间2.线性表是具有n个的有限序列。
a. 表元素d. 数据项 b. 字符 c. 数据元素e. 信息项3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为c 。
（1≤i≤n+1）a. o(0)b. o(1)2c. o(n) d. o(n)4.设a是一个线性表(a1,a2,?,an)，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为 b，平均每删除一个元素需要移动的元素个数为 a；若元素插在ai与ai+1之间(0≤i≤n-1)的概率为元素所要移动的元素个数为 c； 2(n?i)，则平均每插入一个n(n?1) n?1 22n?1c.3a. n 23n?1d. 4b.5.下列函数中，按它们在n??时的无穷大阶数，最大的是 d。
a. lognb. nlognn/2c. 2 d. n!6.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. nc. n-1b. 2n-1 d. 2n13.用单链表表示的链式队列的队头在链表的a 位置。
a. 链头b. 链尾c. 链中14.若用单链表表示队列，则应该选用。
a. 带尾指针的非循环链表b. 带尾指针的循环链表c. 带头指针的非循环链表d. 带头指针的循环链表15.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，先放入打印缓冲区的数据先被打印。
《计算机软件技术基础》参考答案A一、单项选择题(每空1分，共50分)1-5 CBCBD 6-10 ADDCB11-15 ACABB 16-20 BLJCI21-25 CCABC 26-30 BADAB31-35 BCDBA 36-40 DDCDA41-45 DDCAC 46-50 BBCAB评分标准：本题每空1分，多选、少选、错选均不得分。
二、本题10分(1) v != NULL或v(2) x > v->val 或x != v->val(3) p->next(4) u->next(5) head->next评分标准：本题10分，每空2分，在(3)-(5)中未写出next扣1分三、本题10分(1) A!=NULL && B!=NULL(2) A->data==B->data(3) B=B->next;(4) A!=NULL(5) last->next=NULL;评分标准：本题10分，每空2分，在(2)中未写出data扣1分，在(3)和(5)中未写出next扣1分四、本题10分解：(1) A、B、C三个进程之间存在互斥的制约关系。
因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。
(2)mutex：用于互斥的信号量，初值为1。
各进程的代码如下：进程A 进程B 进程C... … ...... … ...P(mutex) P(mutex) P(mutex)申请打印机申请打印机申请打印机使用打印机使用打印机使用打印机V(mutex) V(mutex) V(mutex)… … …评分标准：本题10分，(1)题3分，(2)题7分，其中给出信号量含义和初值1分，三个进程代码各2分五、本题10分解：FIFO淘汰算法：内存块为3时，缺页中断（或称缺页次数、页面故障）为9；内存块为4时，缺页中断为10。
LRU淘汰算法：内存块为3时，缺页中断为10评分标准：本题10分，FIFO淘汰算法两种情况各3分,LRU淘汰算法1分,要求有分析过程六、本题10分解：段式存储管理的地址转换过程为：（1）根据逻辑地址中的段号查段表的相应栏目；（2）根据段内地址<段长度，检查地址是否越界；（3）若不越界，则绝对地址=该段的主存起始地址+段内地址。
数据结构习题答案第一节概论一、选择题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．根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式，其中解释错误的是( )。
《计算机软件技术基础》试题答案一、选择题（每题5分，共30分）1. 下列关于软件工程的描述，错误的是（D）。
A. 软件工程是计算机科学的一个分支B. 软件工程的目标是提高软件质量和生产率C. 软件工程包括软件开发、维护和管理等方面D. 软件工程只关注大型软件的开发2. 下列哪种编程范式主要用于描述程序逻辑和数据的结构？（B）A. 面向过程编程B. 面向对象编程C. 函数式编程D. 逻辑编程3. 下列关于软件测试的描述，错误的是（C）。
A. 软件测试是软件开发过程中的重要环节B. 软件测试的目的是发现和修正软件中的错误C. 软件测试无需考虑软件的性能和稳定性D. 软件测试分为单元测试、集成测试和系统测试等阶段4. 下列关于软件维护的描述，正确的是（B）。
A. 软件维护是指对软件进行升级和优化B. 软件维护包括纠正软件错误、改进软件性能和增加新功能等C. 软件维护不需要考虑软件的可维护性D. 软件维护仅限于软件开发完成后5. 下列关于软件项目管理工具的描述，错误的是（D）。
A. 软件项目管理工具可以协助项目经理进行项目规划B. 软件项目管理工具可以协助项目经理进行项目监控C. 软件项目管理工具可以协助项目经理进行项目沟通D. 软件项目管理工具无法协助项目经理进行项目风险管理二、填空题（每题5分，共30分）1. 软件生命周期可以分为______、______、______、______和______五个阶段。
答案：需求分析、设计、实现、测试、维护2. 在面向对象编程中，一个对象通常包括______和______两部分。
答案：属性、方法3. 软件测试的目的是______、______和______。
答案：发现错误、修正错误、提高软件质量4. 软件维护的类型包括______、______、______和______。
答案：纠错性维护、适应性维护、完善性维护、预防性维护5. 软件项目管理工具主要包括______、______、______和______。
第一章信息与计算机1.1 什么是信息？信息与数据的区别和联系在何处？信息定义之一：信息是现实世界中存在的客观实体、现象、关系进行描述的数据。
信息定义之二：信息是经过加工后并对实体的行为产生影响的数据。
与数据的区别和联系：数据定义：数据是现实世界客观存在的实体或事物的属性值，即指人们听到的事实和看到的景象。
我们把这些数据收集起来，经过处理后，即得到人们需要的信息。
信息和数据的关系可以归结为： 1. 信息是有一定含义的数据。
2. 信息是经过加工（处理）后的数据。
3. 信息是对决策有价值的数据。
1.2 信息有哪些基本属性？信息的基本属性有： 1. 事实性。
2. 等级性。
3. 可压缩性。
4. 可扩散性。
5. 可传输性。
6. 共享性。
7. 增值性和再生性。
8. 转换性。
1.3 计算机的主要特点是什么？计算机最主要的特点是： 1. 高速自动的操作功能。
2. 具有记忆的能力。
3. 可以进行各种逻辑判断。
4. 精确高速的计算能力。
1.5 完整的计算机系统应该包括哪几部分？目前最完整的计算机系统学说认为由五部分组成： 1. 人员 2. 数据 3. 设备 4. 程序 5. 规程1.6 什么是计算机硬件？什么是计算机软件？硬件：泛指实际存在的物理设备，包括计算机本身及其外围设备。
微型计算机的硬件系统：主机、外存储器、输入设备、输出设备、微机的系统总线。
软件：是指计算机程序、方法、规则的文档以及在计算机上运行它时所必须的数据。
计算机软件一般分为系统软件和应用软件。
1.8 软件技术发展的几个阶段各有什么特点？它与硬件的关系如何？第一阶段：高级语言阶段特点：这一时期，编译技术代表了整个软件技术，软件工作者追求的主要目的是设计和实现在控制结构和数据结构方面表现能力强的高级语言。
但在这一时期内，编译系统主要是靠手工编制，自动化程度很低。
硬件关系：此时期计算机的硬件要求仅能用机器指令来编制可运行的程序。
第二阶段：结构程序设计阶段特点：在程序的正确性方面，提出了结构化程序设计思想使程序的可靠性提高了。
《计算机软件技术基础(1)》在线作业一试卷总分:100 得分:100一、单选题1.设标签Label1的Caption属性值为默认值，则该标签控件Name属性和Caption属性的值分别为（）。
A. “Label”、“Label”B. “Label1”、“Label1”C. “Label”、“Label1”D. “Label1”、“Label”正确答案:B2.下面算术运算符中，优先级最高的是（）。
A. NOTB. ORC. ANDD. XOR正确答案:A3.下面列出的语句中，没有错误的语句是（）。
A. txt1.Text+txt2.Text=txt3.TextB. 12Label1.Caption=1234C. =cmdSubD. frmFirst.Move 1000,1000,2000,1200正确答案:D4.假定bln1是逻辑型变量，下面赋值语句中正确的是（）。
A. bln1=’True’B. bln1=.True.C. bln1=#TrueD. bln1=True正确答案:D5. 声明一个函数的时候，不可能用到的关键字是（）。
A. ExitB. AsC. SubD. End满分：5 分正确答案:C6. 设在菜单编辑器中定义了一个菜单项，名为menu1。
为了在运行时隐藏该菜单项，应使用的语句是（）。
A. menu1.Enabled=TrueB. Munu1.Enabled=FalseC. Menu1.Visible=TrueD. Menu1.Visible=False满分：5 分正确答案:D7. 一个菜单项是不是一个分隔条，是由：（）属性决定的。
A. NameB. CaptionC. EnabledD. Visible满分：5 分正确答案:B8. Sub过程和Function过程最根本的区别是：（）。
A. 前者可以使用Call或直接使用过程名调用，后者不可以B. 后者可以有参数，前者不可以C. 两种过程参数的传递方式不同D. 前者无返回值，但后者有满分：5 分正确答案:D9. 以下叙述中错误的是（）。
数据结构习题答案 2 第一节概论 2 第二节线性表 5 第三节栈和队列15 第五节树18 第七节查找24 第八节排序28 操作系统练习题参考答案31数据结构习题答案第一节概论一、选择题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．在以下的叙述中，正确的是( )。
《计算机软件技术基础》试题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.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 域由大到小链接的。
合并后新链表的结点仍按此方式链接。
请填写下述空框，使程序能正确运行。
计算机软件技术基础（第三版）课后习题答案较全第一章信息与计算机1.1 什么是信息？信息与数据的区别和联系在何处？信息定义之一：信息是现实世界中存在的客观实体、现象、关系进行描述的数据。
信息定义之二：信息是经过加工后并对实体的行为产生影响的数据。
与数据的区别和联系：数据定义：数据是现实世界客观存在的实体或事物的属性值，即指人们听到的事实和看到的景象。
我们把这些数据收集起来，经过处理后，即得到人们需要的信息。
信息和数据的关系可以归结为：1. 信息是有一定含义的数据。
2. 信息是经过加工（处理）后的数据。
3. 信息是对决策有价值的数据。
1.2 信息有哪些基本属性？信息的基本属性有： 1. 事实性。
2. 等级性。
3. 可压缩性。
4. 可扩散性。
5. 可传输性。
6. 共享性。
7. 增值性和再生性。
8. 转换性。
1.3 计算机的主要特点是什么？计算机最主要的特点是： 1. 高速自动的操作功能。
2. 具有记忆的能力。
3. 可以进行各种逻辑判断。
4. 精确高速的计算能力。
1.5 完整的计算机系统应该包括哪几部分？目前最完整的计算机系统学说认为由五部分组成： 1. 人员 2. 数据3. 设备 4. 程序 5. 规程1.6 什么是计算机硬件？什么是计算机软件？硬件：泛指实际存在的物理设备，包括计算机本身及其外围设备。
微型计算机的硬件系统：主机、外存储器、输入设备、输出设备、微机的系统总线。
软件：是指计算机程序、方法、规则的文档以及在计算机上运行它时所必须的数据。
计算机软件一般分为系统软件和应用软件。
1.8 软件技术发展的几个阶段各有什么特点？它与硬件的关系如何？第一阶段：高级语言阶段特点：这一时期，编译技术代表了整个软件技术，软件工作者追求的主要目的是设计和实现在控制结构和数据结构方面表现能力强的高级语言。
但在这一时期内，编译系统主要是靠手工编制，自动化程度很低。
硬件关系：此时期计算机的硬件要求仅能用机器指令来编制可运行的程序。
计算机软件技术基础-习题一解答————————————————————————————————作者：————————————————————————————————日期：∑∑∑====n 1i n 1j 3n 1k n 162)1)(n n(n 21)n(n 2161)1)(2n n(n 21 i 21i 2121)i(i j 1n1i n 1i n 1i 2n 1i i 1j n 1i i 1j j 1k ++=++++==+=⎪⎭⎫ ⎝⎛+==∑∑∑∑∑∑∑∑========习题解答3.设n 为正整数, 分析下列各程序段中加下划线的语句的执行次数。
(1) for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) {c[i][j] = 0.0;for (int k = 1; k <= n; k++)c[i][j] = c[i][j] + a[i][k] * b[k][j];}(2) x = 0; y = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)for (int k = 1; k <= j; k++)x = x + y;(3) int i = 1, j = 1;while (i<=n && j<=n) {i = i + 1; j = j + i;}(4)* int i =1;do{for (int j = 1; j <= n; j++)i = i + j;}while(i<100 + n);【解答】(1)(2)(3)i = 1时，i = 2，j = j + i = 1 + 2 = 2 + 1，i = 2时，i = 3，j = j + i = ( 2 + 1 ) + 3 = 3 + 1 + 2，i = 3时，i = 4，j = j + i = ( 3 + 1 + 2 ) + 4 = 4 + 1 + 2 + 3，i = 4时，i = 5，j = j + i = ( 4 + 1 + 2 + 3 ) + 5 = 5 + 1 + 2 + 3 + 4， ……i = k 时，i = k + 1，j = j + i = ( k + 1 ) + ( 1 + 2 + 3 + 4 + … + k )，解出满足上述不等式的k 值，即为语句i = i + 1的程序步数。
数据结构习题答案 2 第一节概论 2 第二节线性表 5 第三节栈和队列16 第五节树19 第七节查找25 第八节排序29 操作系统练习题参考答案32数据结构习题答案第一节概论一、选择题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．在以下的叙述中，正确的是( )。
数据结构习题答案 2 第一节概论 2 第二节线性表 5 第三节栈和队列16 第五节树19 第七节查找25 第八节排序29 操作系统练习题参考答案32数据结构习题答案第一节概论一、选择题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．在以下的叙述中，正确的是( )。
∑∑∑====n 1i n 1j 3n 1k n 162)1)(n n(n 21)n(n 2161)1)(2n n(n 21 i 21i 2121)i(i j 1n1i n 1i n 1i 2n 1i i 1j n 1i i 1j j 1k ++=++++==+=⎪⎭⎫ ⎝⎛+==∑∑∑∑∑∑∑∑========习题解答3.设n 为正整数, 分析下列各程序段中加下划线的语句的执行次数。
(1) for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) {c[i][j] = 0.0;for (int k = 1; k <= n; k++)c[i][j] = c[i][j] + a[i][k] * b[k][j];}(2) x = 0; y = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)for (int k = 1; k <= j; k++)x = x + y;(3) int i = 1, j = 1;while (i<=n && j<=n) {i = i + 1; j = j + i;}(4)* int i =1;do{for (int j = 1; j <= n; j++)i = i + j;}while(i<100 + n);【解答】(1)(2)(3)i = 1时，i = 2，j = j + i = 1 + 2 = 2 + 1，i = 2时，i = 3，j = j + i = ( 2 + 1 ) + 3 = 3 + 1 + 2，i = 3时，i = 4，j = j + i = ( 3 + 1 + 2 ) + 4 = 4 + 1 + 2 + 3，i = 4时，i = 5，j = j + i = ( 4 + 1 + 2 + 3 ) + 5 = 5 + 1 + 2 + 3 + 4， ……i = k 时，i = k + 1，j = j + i = ( k + 1 ) + ( 1 + 2 + 3 + 4 + … + k )，解出满足上述不等式的k 值，即为语句i = i + 1的程序步数。
()()()n 233k k 21k k 1k ni 1k j 2k1i ≤++=+++∴≤++=∑=(4) for 语句每执行一次，语句i=i+j 将执行n 次，而i 的值会增加(1)2n n + 因此，当for 语句执行k 次后，i 的值将变为 (1)12n n k++ 故最终for 语句的执行次数k 为满足 (1)11002n n k n ++≥+ 的最小整数k ，语句i = i + j 的程序步数为n*k 。
4.试编写一个函数计算n!*2n 的值，结果存放于数组A[arraySize]的第n 个数组元素中，0 ≤n ≤ arraySize 。
若设计算机中允许的整数的最大值为maxInt ，则当n>arraySize 或者对于某一个k (0 ≤ k ≤ n)，使得k!*2k > maxInt 时，应按出错处理。
可有如下三种不同的出错处理方式：(1) 用printf 显示错误信息及exit(1)语句来终止执行并报告错误；(2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回；(3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。
试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。
【解答】#include <stdio.h>const int arraySize = 100;const int MaxInt = 0x7fffffff;int calc( int T[ ], int n ) {int i, value = 1;T[0]=1;if ( n != 0 ) {int edge = MaxInt / n / 2;for ( i = 1; i < n; i++ ) {value *= i*2;T[i] = value;if ( value > edge ) return 0;}value *= n * 2;}T[n] = value;printf("A[ %d ]= %d\n”,n,T[n]);return 1;}void main ( ) {int A[arraySize];int i;for ( i = 0; i < arraySize; i++ )if ( !calc ( A, i ) ) {printf("failed at %d .\n", i );break;}}/*---------顺序表结构的定义.为简化起见，表元素我们使用整型数据----------- -----------数据元素从data[0]处开始存储---------------------------------*/ typedef struct /*注意typedef 的使用*/{int data[MAXSIZE]; /*数据域*/int length; /*表长*/}listtype;5.设有一个线性表 (a 0, a 1, …, a n-2, a n-1) 存放在一个一维数组A[arraySize]中的前n 个数组元素位置。
请编写一个函数将这个线性表原地逆置，即将数组的前n 个原址内容置换为 (a n-1, a n-2, …, a 1, a 0)。
最后分析此算法的时间复杂度及空间复杂度。
【解答】void inverse (listtype * A) {int tmp;int n= A->length;for( int i = 0; i <= ( n-1 ) / 2; i++ ){tmp = A->data[i]; A->data[i] = A->data[n-i-1]; A->data[n-i-1] = tmp; }}时间复杂度：需进行n/2次循环，因此时间复杂度为O(n)；空间复杂度：使用一个整形辅助存储单元tmp ，因此空间复杂度为O(1)。
6.顺序表的插入和删除要求仍然保持各个元素原来的次序。
设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素?【解答】若设顺序表中已有n 个元素。
又设插入或删除表中各个元素的概率相等，则在插入时因有n+1个插入位置(可以在表中最后一个表项后面追加)，每个元素位置插入的概率为1/(n+1)，但在删除时只能在已有n 个表项范围内删除，所以每个元素位置删除的概率为1/n 。
插入时平均移动元素个数AMN(Averagy Moving Number )为()5.632n 21)n(n 1n 1)01)1n (n (1n 1i n 1n 1AMN n 0i ==++=+++-++=-+=∑=删除时平均移动元素个数AMN 为6321n 21)n (n n 10)12)(n 1)((n n 11)i (n n 1AMN 1n 0i =-=-=+++-+-=--=∑-=7.利用顺序表的操作，实现以下的函数。
并分析你所编制的函数的时间复杂度，并分析(2)与(3)的时间复杂度出现差异的原因。
(1) 从顺序表中删除具有给定值x 的所有元素。
(2) 从顺序表中删除其值在给定值s 与t 之间（要求s 小于t ）的所有元素。
(3) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。
(4) 将两个有序顺序表la,lb合并成一个新的有序顺序表lc。
(5) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。
【解答】(1) 从顺序表中删除具有给定值x的所有元素。
void DelValue(listtype * L, int x ){int i = 0, j;while ( i < L->length ) /*循环, 寻找具有值x的元素并删除它*/if (L->data[i] == x ) { /*删除具有值x的元素, 后续元素前移*/ for (j = i;j < L->length-1; j++ ) L->data[j] = L->data[j+1];L-length--; /*表长减1*/}else i++;}(2) 实现删除其值在给定值s与t之间（要求s小于t）的所有元素的函数如下：void DelValue_s_to_t (listtype *L,int s, int t){int i,j;if ( L->length == 0 || s >= t ) {printf(“List is empty or parameters are illegal!\n”); exit(1); }i = 0;while ( i < L->length) /*循环, 寻找具有值x的元素并删除它*/ if (L->data[i]>=s &&L->data[i]<= t){/*删除满足条件的元素, 后续元素前移*/ for ( j = i; j < L->length-1; j++ ) L->data[j] = L->data[j+1];L->length--; /*表长减1*/}else i++;}(3) 实现从有序顺序表中删除其值在给定值s与t之间的所有元素的函数如下：void DelValue_s_to_t_1 (listtype *L,int s int t){int i,j,k;if ( L->length == 0 || s >= t ){printf(“List is empty or parameters are illegal!\n”); exit(1); } for (i = 0; i < L->length; i++ ) /*循环, 寻找值≥s 的第一个元素*/ if ( L->data[i] >= s ) break; /*退出循环时, i指向该元素*/ if ( i < L->length ) {for (j = 1; i + j < L->length; j++ )/*循环, 寻找值 > t 的第一个元素*/if (L->data[i+j] > t ) break; /*退出循环时, i+j指向该元素*/for (k = i+j; k < L->length; k++ ) /*删除满足条件的元素, 后续元素前移*/ L->data[k-j] = L->data[k];L->length-= j; /*表长减j*/}}(4) 实现将两个有序顺序表合并成一个新的有序顺序表的函数如下：listtype * Merge(listtype *LA,listtype *LB ){/*合并有序顺序表LA与LB成为一个新的有序顺序表并由函数返回listtype *LC;int value1,value2;int i,j,k;initiatelist(LC);if (LA->length + LB->length > MAXSIZE) {printf(“表上溢/n”; exit(1);}i = 0, j = 0, k = 0;value1 = LA->data[i];value2 = LB->data[j];while (i < LA->length && j < LB->length ) {/*循环, 两两比较, 小者存入结果表*/if (value1 <= value2){LC->data[k] = value1; i++; value1=LA->data[i];}else {LC->data[k] = value2; j++; value2=LB->data[j];}k++;}while( i < LA->length){ /*当LA表未检测完, 继续向结果表传送*/ LC->data[k] = value1; i++; k++; value1 = LA->data[i];}while( j < LB->length){ /*当LB表未检测完, 继续向结果表传送*/ LC->data[k] = value2; j++; k++; value2 = LB->data[j];}LC->length = k;return LC;}(5) 实现从表中删除所有其值重复的元素的函数如下：void DelDouble(listtype *L){int i,j,k;int tmp;if(L->length == 0 ){printf(“表空\n”; exit(1);}i=0;while ( i < L->length ) { /*循环检测*/j = i + 1;tmp = L->data[i];while( j < L->length ) { /*对于每一个i, 重复检测一遍后续元素*/ if( tmp == L->data[j]) { /*如果相等,删除此结点，后续元素前移*/ for( k = j+1; k < L->length; k++ ) L->data[k-1] = L->data[k];L->length--; /*表最后元素位置减1*/}else j++;}i++; /*检测完L->data[i], 检测下一个*/ }}8.线性表可用顺序表或链表存储。
