计算机软件技术基础安徽工业大学

计算机软件技术基础

课下作业*部分考试内容

1：什么是线性数据结构？

答：数据结构是指相互有关联的数据元素的集合。

线性结构是指c++实现的采用动态数组为基础的线性顺序表。

形式：逻辑结构；存储结构。

线性结构是n个数据元素的有序（次序）集合,指的是数据元素之间存在着“一对一”的线性关系的数据结构。如（a1,a2,a3,.....,an）,a1为第一个元素，an为最后一个元素，此集合极为一个线性结构的集合。

它有四个基本特征：

a．集合中必存在唯一的一个"第一个元素"；

b．集合中必存在唯一的一个"最后的元素"；

C．除最后元素之外，其它数据元素均有唯一的"后继"；

d．除第一元素之外，其它数据元素均有唯一的"前驱"。

常用的线性结构有：线性表，栈，队列，双队列，数组，串。

非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后驱。 常见的非线性结构有：树(二叉树等)，图(网等) ，广义表。

如题目

下列叙述中正确的是 B

A 有一个以上根结点的数据结构不一定是非线性结构

B 只有一个根结点的数据结构不一定是线性结构

C 循环链表是非线性结 D 双向链表是非线性结构

根据以上定义，你的选择题答案为B。

A违反了线性特征的第一条，有两个根节点，一定是非线性

C D都是线性结构！

追问

请问一下 线性结构有没有可能有多个结点？

回答

当然有多个结点，但是没有多个根结点，如果有就有多个“头节点”违反了线性结构特征 2：队列的运算有哪些？

答：队列的初始化；入队运算；退队运算。

3：什么时存储结构？常用的结构有哪些？

答：数据的逻辑结构在计算机中的表示。

解析：比如二维数组，数据结构是一个二维的平面结构，但实际上，内存是线性的，不可能存二维结构，所以，这个二维的数据结构要转换成一维的线性结构来存储。

像树或网这样的结构更明显了，在内存中更不可能将数据存成为树状的或是网状的，必须都转换成线性的结构。

所以，数据的逻辑结构都必须转换成在计算机内存中实际存储的存储结构。

常用的结构：顺序存储结构；链式存储结构。

4：线性链表是什么？线性链表的运算有哪些？

答：是线性表的链式存储结构。

运算：插入；删除；合成；分解；逆转；复制；排序；查找。

5： 并行：在操作系统中是指，一组程序按独立异步的速度执行，不等于时间上的重叠（同一个时刻发生)。

并发：在同一个时间段内，两个或多个程序执行，有时间上的重叠（宏观上是同时，微观上仍是顺序执行）。

“并行”是指无论从微观还是宏观，二者都是一起执行的，就好像两个人各拿一把铁锨在挖坑，一小时后，每人一个大坑。而“并发”在微观上不是同时执行的，只是把时间分成若干段，使多个进程快速交替的执行，从宏观外来看，好像是这些进程都在执行，这就好像两个人用同一把铁锨，轮流挖坑，一小时后，两个人各挖一个小一点的坑，要想挖两个大一点得坑，一定会用两个小时。

从以上本质不难看出，“并发”执行，在多个进程存在资源冲突时，并没有从根本提高执行效率。

临界资源：临界资源是指每次仅允许一个进程访问的资源。属于临界资源的硬件有打印机、磁带机等,软件有消息缓冲队列、变量、数组、缓冲区等。 诸进程间应采取互斥方式，实现对这种资源的共享。每个进程中访问临界资源的那段代码称为临界区。显然，若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。为此，每个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看它是否正被访问。如果此刻该临界资源未被访问，进程便可进入临界区对该资源进行访问，并设置它正被访问的标志；如果此刻该临界资源正被某进程访问，则本进程不能进入临界区。

6：什么时顺序存储结构？

答：在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。

顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构，通常顺序存储结构是借助于计算机程序设计语言（例如c/c++）的数组来描述的。

顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。

优点：随机存取表中元素。缺点：插入和删除操作需要移动元素。

7：什么是链式存储结构？

答：又叫链接存储结构。在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).

它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点.

链式存储结构特点：

1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。

2、逻辑上相邻的节点物理上不必相邻。

3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。

4、查找结点时链式存储要比顺序存储慢。

5、每个结点是由数据域和指针域组成。

8：什么是多道操作系统？

答：自己百度，我找不到。

9：什么是通道？什么是中断？

答：通道：计算机系统中传送信息和数据的装置。主要有主存储器读写通道和输入、输出通道。能接收中央处理机的命令，独立执行通道程序，协助中央处理机控制与管理外部设备。

中断：当出现需要时，CPU暂时停止当前程序的执行转而执行处理新情况的程序和执行过程。即在程序运行过程中，系统出现了一个必须由CPU立即处理的情况，此时，CPU暂时中止程序的执行转而处理这个新的情况的过程就叫做中断。

10：什么是进程？有哪些状态？转换关系是什么？

答：进程是操作系统结构的基础；是一次程序的执行；是一个程序及其数据在处理机上顺序执行时所发生的活动。

状态：

1）就绪状态（Ready）：

进程已获得除处理器外的所需资源，等待分配处理器资源；只要分配了处理器进程就可执行。就绪进程可以按多个优先级来划分队列。例如，当一个进程由于时间片用完而进入就绪状态时，排入低优先级队列；当进程由I/O操作完成而进入就绪状态时，排入高优先级队列。

2）运行状态(Running)：

进程占用处理器资源；处于此状态的进程的数目小于等于处理器的数目。在没有其他进程可以执行时(如所有进程都在阻塞状态)，通常会自动执行系统的空闲进程。

3）阻塞状态(Blocked)：

由于进程等待某种条件（如I/O操作或进程同步），在条件满足之前无法继续执行。该事件发生前即使把处理机分配给该进程，也无法运行。

转换关系：进程在运行中不断地改变其运行状态。通常，一个运行进程必须具有以下三种基本状 …… 此处隐藏：2601字，全部文档内容请下载后查看。喜欢就下载吧 ……