什么是数据结构.docx

什么是数据结构？它对算法有什么影响？数据结构是指同一数据对象中各数据元素间存在的关系。对算法是影响：算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。何谓算法？它与程序有何区别？广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。和程序的区别：一个程序包括两个方面的内容：（1）、对数据的描述，即数据结构。（2）、对操作的描述，即算法。所以算法是程序的一个要素。数据的存储结构主要有哪两种?它们之间的本质区别是什么？数据的存储结构：向量和链表。本质区别：向量是连续存放的，其存储空间是静态分配的，以存放顺序来表达元素的前后件的关系。链式存储结果不需要一组连续的存储单元，其数据元素可以分散存放在存储空间中，其元素关系由指针来指向。试比较顺序表和链表的优缺点。1. 线性表的长度是否固定方面：由于向量的存储空间是静态分配的，链表的存储空间是动态分配的，因此若表长不固定时采用线性链表较好。2. 线性表的主要操作是什么：由于向量是连续存放的，所以适用于查找操作，不适用插入、删除操作。由于线性链表只能顺序存取，所以适用于插入、删除操作，不适用于查找操作。3. 采用的算法语言：线性链表要求所使用的语言工具提供指针类型变量。设一棵二叉树其中序和后序遍历为中序：BDCEAFHG后序：DECBHGFA画出这棵二叉树的逻辑结构，并写出先序遍历结果。先序遍历：ABCDEFGH其逻辑结构如下：ABFCDEGH通常操作系统有哪几种基本类型？各有什么特点及适用于何种场合？三大类：（1）多道批处理系统：计算机内存中同时可以存放多道作业，用户与作业之间没有交互作用，用户不能直接控制作业的运行。此类系统一般用于计算中心等较大型的计算机系统中。（2）分时系统：多个用户通过终端分享同一台计算机，并通过终端直接控制程序运行，进行人与机器之间的交互。此类系统适用于程序的开发。（3）实时系统：对外部发生的随机事件作出及时的响应，并对它进行处理。此类系统一般用于工业控制系统或事物处理系统。什么是进程的同步和互斥？什么是临界区？“同步”是指两个事件的发生存在某种时序上的关系，如果系统中有若干个进程要共同完成某一任务，那么它们相互之间必须协调配合。“互斥”是指当多个进程要求共享系统中某些硬件或软件资源，而这些资源却又要求排它性使用时，这样往往引起由于多个进程竞争同一资源使运行结果出现问题。如果在两个进程P1、P2中加入P、V操作后，可以实现对公用变量count的互斥使用。其中P（s）、V（s）之间的程序段称为临界区死锁产生的必要条件是什么？死锁的预防、避免和检测各有什么不同？各举一种相应的方法。死锁产生的必要条件有：1.所涉及的资源是非共享的；2.进程在等待新资源时，继续占用已分配到的资源；3.一个进程占有的资源不能被别的进程强行抢占；4.一个进程获得的资源同时被另一个进程所请求，从而形成一个进程的循环链。死锁的预防是研究如何破坏产生死锁的必要条件之一，从而达到不使死锁发生地目的。死锁的避免与死锁的预防区别在于，死锁的预防是严格破坏形成死锁的必要条件之一，使得死锁不在系统中出现。预防方法之一，采用假脱机技术将非共享设备变成共享设备来实现。而死锁的避免并不严格限制必要条件的存在，因为必要条件存在并不一定产生死锁。而进程推进顺序不当，也可以导致系统发生死锁，因此死锁的避免是考虑万一当死锁有可能出现时，就小心地避免这种情况的最终发生。避免方法有采用相应的银行算法和方法。死锁的检测和恢复，这是一种变通的方法，它允许死锁的发生，但能在适当时间检测出来，并设法进行恢复。利用化简进程-资源有向图的方法来检测系统在某一特定状态时是否处于死锁状态。什么是文件目录？有几种目录结构形式？各有什么特点？为了便于对文件进行存取和管理，所有计算机系统都设置一个文件目录，每个文件目录中都有一个表目，存放描述该文件的有关信息。通常有一级目录、二级目录和多级目录结构。一级目录：把系统中所有文件都建立在一张目录表中，整个目录结构是一个线性表，所以查找的时间会增加，不允许用户对不同的文件取相同的名字，主要用于单用户的操作系统中。二级目录：在主目录文件中每一个用户有一个表目，指出各用户文件目录的所在位置，而各用户文件目录才指出其所属