《事业单位考试计算机专业课复习资料全集 最新》由会员分享，可在线阅读，更多相关《事业单位考试计算机专业课复习资料全集 最新（46页珍藏版）》请在金锄头文库上搜索。
1、本复习资料是根据武汉市事业单位招考笔试计算机岗位考试大纲要求编写，涉及知识涵盖了计算机专业知识包括：数据结构、计算机网络、计算机组成原理、操作系统、数据库原理等知识，本稿分为五个部分。第一部分 数据结构要点第一章 概 论*数据就是指能够被计算机识别、存储和加工处理的信息的载体。数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。*数据结构的定义：逻辑结构：从逻辑结构上描述数据，独立于计算机。线性结构：一对一关系，是数据元素之间定义了次序关系的集合（全序集合）。图状结构：多对多关系，是数据元素之间定义了网状关系的集合。存储结构：是逻辑结构用计算机语言的实现。顺序
2、存储结构：如数组。链式存储结构：如链表。索引存储结构：稠密索引：每个结点都有索引项。稀疏索引：每组结点都有索引项。散列存储结构：如散列表。数据运算。对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的有：检索、插入、删除、更新、排序。*数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。原子类型：由语言提供。结构类型：由用户借助于描述机制定义，是导出类型。抽象数据类型ADT：是抽象数据的组织和与之的操作。相当于在概念层上描述问题。优点是将数据和操作封装在一起实现了信息隐藏。*程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。*算法是指
3、的是解决问题的步骤序列，它必须具备可执行性、确定性、有穷性这三个特性，以一个或多个值输入，并以一个或多个值输出。评价算法的好坏的因素：算法是正确的；执行算法的时间；执行算法的存储空间（主要是辅助存储空间）；算法易于理解、编码、调试。*时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。【问题】时间复杂度的计算。方法：先求频度，再求时间复杂度。习题一 分析以下程序的时间复杂度for (i=1;in;i+)y=y+1; for (j=0;j=(2*n);j+)x+; 分析：语句的频度是f1(n)=n-1 语句的频度是f2n)=(n-1)(2n-1)语句和语句得时间复杂度分别是：O1
4、(1)=O(n) O2(n)=O(n2)习题二 分析下列程序段的时间复杂度i=1; While (i=1)i=i*2 分析： i=1 i=1*2 i=2 i=2*2 i=22 i=23 i=2f(n) i=2f(n)+1即：f(n)=log2n语句的时间复杂度是f(n)=log2n。习题三 求下列程序段的频度for (i=1;i=n;i+) for (j=1;j=I;j+)for (k=1;k=j;kelem=(Elemtype*)malloc(LIST_MAX_LENGTH *sizeof(Elemtype); /分配空间 if (L-elem=NULL) return ERROR; /若分
5、配空间不成功，返回ERROR L-length=0; /将当前线性表长度置0 return OK; /成功返回OK *顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。地址计算：LOC(a(i)=LOCa(1)+(i-1)*d；（首地址为1）在顺序表中实现的基本运算： 插入：平均移动结点次数为n/2；平均时间复杂度均为O(n)。删除：平均移动结点次数为（n-1）/2；平均时间复杂度均为O(n)。*线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同，为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存
6、储了其后继结点的地址信息(即指针或链)。这两部分信息组成链表中的结点结构。 一个单链表由头指针的名字来命名。*单链表运算：建立单链表头插法：s-next=head；head=s；生成的顺序与输入顺序相反。平均时间复杂度均为O(n)。尾插法：head=rear=null；if(head=null) head=s;else r-next=s;r=s; 平均时间复杂度均为O(n)加头结点的算法：对开始结点的操作无需特殊处理，统一了空表和非空表。查找按序号：与查找位置有关，平均时间复杂度均为O(n)。按值：与输入实例有关，平均时间复杂度均为O(n)。插入运算：p=GetNode(L,i-1)；s-ne
7、xt=p-next；p-next=s；平均时间复杂度均为O(n)删除运算：p=GetNode(L,i-1)；r=p-next；p-next=r-next；free(r)；平均时间复杂度均为O(n)*单循环链表是一种首尾相接的单链表，终端结点的指针域指向开始结点或头结点。链表终止条件是以指针等于头指针或尾指针。 采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是O(1)，不用遍历整个链表。双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,形成两条不同方向的链。由头指针head惟一确定。双链表也可以头尾相链接构成双(向)循环链
8、表。双链表上的插入和删除时间复杂度均为O (1)。*顺序表和链表的比较：基于空间：顺序表的存储空间是静态分配，存储密度为1；适于线性表事先确定其大小时采用。链表的存储空间是动态分配，存储密度1；适于线性表长度变化大时采用。 基于时间：顺序表是随机存储结构，当线性表的操作主要是查找时，宜采用。以插入和删除操作为主的线性表宜采用链表做存储结构。若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。第三章 栈和队列*栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为L
9、IFO表(Last In First Out)。通常栈有顺序栈和链栈两种存储结构。*栈的基本运算有六种： 构造空栈：InitStack(S)判栈空：StackEmpty(S)判栈满：StackFull(S)进栈： Push(S,x)退栈： Pop(S)取栈顶元素：StackTop(S) *队列(Queue)是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear) ,队列的操作原则是先进先出的，又称作FIFO表(First In First Out) 。队列也有顺序存储和链式存储两种存储结构。*队列的基本运算有六
10、种： 置空队：InitQueue(Q)判队空：QueueEmpty(Q)判队满：QueueFull(Q)入队：EnQueue(Q,x)出队：DeQueue(Q)取队头元素：QueueFront(Q)*顺序队列的假上溢现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了“上溢”现象。为了克服假上溢现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。判定循环队列是空还是满，方法有三种： 第一种是另设一个布尔变量来判断；第二种是少用一个元素空间，入队时先测试（(rear+1)%m = front）? 满：空； 第三种就是用一个计数器记录队列中的元素的总数。*
