计算机软件技术基础第三版沈被娜电子教材

主讲人：岑鹏瑞 包胡斯楞 丁学东2013年4月16日

数据结构分为两大类：线性结构与非线性结构

如果一个非空的数据结构满足下列两个条件： 1.有且只有一个根节点； 2.每一个节点最多有一个前件，也最多有一个后件。 则称该数据结构为线性结构(线性表)。 线性表是最简单，最常用的一种数据结构。

非空线性表有如下一些结构特征： 1.有且只有一个根节点a1,它无前件； 2.有且只有一个终端节点an,它无后件； 3.除根节点与终端节点外，其他所有节点有且只有一个 前件，也有且只有一个后件，线性表中节点的个数n 称为线性表的长度。当n=0时，称为空表。

线性表的顺序存储结构 线性表的顺序存储结构具有以下两个基本特点： 1.线性表中所有元素所占的存储空间是连续的； 2.线性表中各数据元素在存储空间中是按逻辑顺序依次存放 的； 线性表中第i个元素ai在计算机存储空间中的存储地址为： ADR(ai)=ADR(a1)+(i-1)k 即在顺序存储结构中，线性表中每一个数据元素在计算机 存储空间中的存储地址由该元素在线性表中的位置序号唯 一确定。 在程序设计语言中，通常定义一个一维数组来表示线 性表的顺序存储空间。 在实际应用中，可以根据线性表动态变化过程中的一 般规模来决

6.1 操作系统原理

1 操作系统概论 2 操作系统的特性 3 操作系统的功能 4 操作系统的类型 5 进程管理 6.2 常见的操作系统 6.3 小节

操作系统是加到计算机硬件上的第一层软件，它是直接操作计算机的硬件的软件,从而使计算机硬件的功能首次能够发挥出来。一台纯粹由硬件构成的计算机(称之为“裸机”)在加载操作系统之后，就变成了一台与“裸机”大相径庭的“虚拟”的计算机。其他的所有软件，如编译软件、数据库系统、软件开发工具等系统软件以及浏览器、字处理软件、办公软件等应用软件都是以操作系统为基础，运行于“虚拟”机上的。只有首先运行操作系统之后，才能运行其他软件。

操作系统是用户与计算机硬件设备之间的接口，用户通过操作系统操纵计算机硬件设备完成自己的工作。计算机启动并加载操作系统之后，变成了一台“虚拟”(逻辑)的计算机。用户看到的“计算机”是一台逻辑计算机，用户看

计算机软件技术基础

第二章 智能0801班 2.1数据结构概论

一、选择题

1、数据的逻辑结构是（ A ）。 A．数据的组织形式 B．数据的存储形式 C．数据的表示形式

D．数据的实现形式

2、组成数据的基本单位是（ C ）。

A．数据项 B．数据类型 C．数据元素 D．数据变量 3、下面程序的时间复杂度为（ ）。 x=0；

for（i=1；i

x++；

A．O（ ） B．O（n2） C．O（1） D．O（n） 4、下面程序的时间复杂度为（ ）。 for（i=0；i

D．O（m+n）

5、下面程序段的执行次数为（ ）。 for（i=0；ii；j++） state； A．n（n+1）/2 B．（n-1）（n+2）/2 C．n（n+1）/2 D．（n-1）（n+2）

6、下面程序的时间复杂度为（A

《计算机软件技术基础》复习题

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)

2

C. 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??时的无穷大阶数，最大的

第二章

2.1 什么是数据结构？它对算法有什么影响？

数据结构是指同一数据对象中各数据元素间存在的关系。

数据结构对算法的影响：算法的实现必须借助程序设计语言中提供的数据

类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。 2.2 何谓算法？它与程序有何区别？

广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。 和程序的区别：一个程序包括两个方面的内容： （1）对数据的描述，即数据结构。 （2）对操作的描述，即算法。 所以算法是程序的一个要素。

2.3 何谓频度，时间复杂度，空间复杂度？说明其含义。

频度：在某个算法中某个语句被重复执行的次数就是此语句的频度。 时间复杂度：是用来估算一个算法的执行时间的量，以算法中频度最大的语句来度量。

空间复杂度：指在算法中所需的辅助空间的单元，而不包括问题的原始数据占用的空间。

2.4试编写一个求多项式Pn =anxn +an-1 xn-1+a1x+a0的值Pn(x 0)的算法，要求用乘法次数最少，并说明算法中主要语

山东建筑大学实验报告

学院： 信电学院 班级： 姓名： 学号：

课程： 计算机软件技术基础 实验日期：2013年 11月 22日 成绩：

实验七 SQL 简单查询、连接查询和子查询

一、实验目的

1.掌握在查询分析器中使用SELECT语句进行简单查询。

2.熟练掌握简单表的数据查询、数据排序和数据连接查询的操作方法。 3.熟练掌握数据查询中的分组、统计、计算和组合的操作方法。 4.观察查询结果, 体会SELECT语句实际应用

二、实验用软件和工具

1．计算机。实验软件 VC++ 6.0 2．SQL Server2005软件。

三、实验步骤

1 简单查询操作

此部分查询包括投影、选择条件表达、数据排序、使用临时表等。 对EDUC（shiyan6）数据库实现以下查询： （1）求信电学院的学生学号和姓名； （2）求选修了课程的学生学号；

（3）求选修C1 课程的学生学号和成绩，并要求对查询结果按成绩的降序排列，如果成绩相同则按学号的升序排列；

（4）求选修课程C1 且成绩在80－90 之间的学生学号和成绩，并将成绩乘以系数0.75 输出；

（5）求计算机系和数学系的姓张的学生的信息；

昆

明

理

工

大

学

理

学

院

电科071

宋庆和songqinghe@f8da80707fd5360cba1adb78

137********

操作系统的概念

定义：操作系统是控制和管理计算机硬件和软件资源、合理组织计算机工作流程、方便用户使用计算机并提高计算机响应速度而设计的一套程序的集合。

资源角度：是计算机资源管理系统，负责计算机系统的全部资源的分配、控制、调度和回收。

用户角度：操作系统是计算机与用户之间的接口。

进程角度：是动态、合理地组织计算机工作流程的软件。

评价（地位和作用）：

操作系统是直接与硬件相邻的第一层软件，是其他软件运行的基础，是系统软件中最基本、最核心的部分

2

操作系统的两大基本职能

§面向计算机：

?管理和操控全部计算机资源(CPU、设备、

存储器、文件)；

?提高系统效率。

§面向用户：

提供人机界面；提供便捷的操作环境。

3

操作系统的五大功能

操作系统功能

用户接口

文件管理

设备管理

存储管理

处理器管理

4

操作系统的发展

OS是伴随计算机技术的发展而发展的。其发展大致经历了四个阶段。（1）手工操作阶段，从20世纪40年代末到50年代中期——无操作系统，几乎无外部设备,软件只用机器语言。上机完全是手工操作，用户既是

程序员，又是操作员，在上机时独占全部计算机资源，系统资

数据结构习题答案 第一节 概 论

一、选择题

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．

《计算机软件技术基础(1)》在线作业一

天津大学

一、单选题（共 20 道试题，共 100 分。）

V

1. 以下叙述中正确的是（）。

A. 一个记录中所包含的各个元素的数据类型必须相同 B. 随机文件中每个记录的长度是固定的 C. Open命令的作用是打开一个已经存在的文件 D. 使用Input #语句可以从随机文件中读取数据 满分：5 分

2. 下列哪一个是日期型常量（）。 A. ”2/1/99” B. 2/1/99 C. #2/1/99# D. {2/1/99} 满分：5 分

3. 如果在模块的声明段中有Option Base 0语句，则在该模块中使用Dim a(7,3 To 5)声明的数组有（）个元素。 A. 21 B. 28 C. 24 D. 32

满分：5 分

4. 下面几对数据类型中，哪一对所占的内存大小一致：（）。 A. Integer、Single B. Integer、Boolean C. Date、Single

D. Long、Variant 满分：5 分

5. 假定bln1是逻辑型变量，下面赋值语句中正确的是（）。 A. bln1=’True

数据结构习题答案 第一节 概 论 一、选择题

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．顺