计算机统考复习指导

《计算机统考复习指导》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2011年计算机统考【考查目标】计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考牛比较系统地学握上述专业基础课程的概念、基木原理和方法,能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。【考试形式和试卷结构】1.试卷满分及考试时间木试卷满分为150分，考试时间为180分钟2.答题方式闭卷、笔试3.试卷内容结构数据结构45分计算机组成原理45分操作系统35分计算机网络25分4.试卷题型结构单项选择题80分（40小题，每小题2分）

2、综合应用题70分数据结构【考查目标】1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。2.掌握基木的数据处理原理和方法的基础上，能够对算法进行设计与分析。3.能够选择合适的数据结构和方法进行问题求解。线性表大纲要求：（一）线性表的定义和基木操作（二）线性表的实现1•顺序存储结构2.链式存储结构3.线性表的应用知识点：1.深刻理解数据结构的概念，掌握数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作“运算”。2.时间复杂度和空间复杂度的定义

3、，常用计算语句频度来估算算法的时间复杂度。3.线性表的逻辑结构，是指线性表的数据元索间存在看线性关系。主要是指：除第-•及最后一个元素外，每个结点都只有一个帀j趋和只有一个后继。在顺序存储结构中，元素存储的先后位置反映出这种逻辑关系，而在链式存储结构中，是靠指针来反映这种逻辑关系的。4.顺序存储结构用向量（一维数组）表示，给定下标，可以存取相应元素，属于随机存収的存储结构。5.线性表的顺序存储方式及其在具体语言环境下的两种不同实现：表空间的静态分配和动态分配。掌握顺序表上实现插入、删除、定位等运算的算

4、法。6.尽管“只耍知道某结点的指针就町以存取该元素”，但因链表的存取都需要从头指针开始，顺链而行，故链表不属于随机存取结构。要理解头指针、头结点、首元结点和元素结点的差别。头结点是在插入、删除等操作时，为了算法的统一而设立的（若无头结点,则在第一元素前插入元素或删除第一元素时，链表的头指针总在变化）。对链表（不包括循环链表）的任何操作，均要从头结点开始，头结点的指针具有标记作用，故头指针往往被称为链表的名字，如链表head是指链农头结点的指针是heado理解循环链农中设置尾指针而不设置头指针的好处。链

5、表操作屮应注意不要使链意外“断开”。因此，若在某结点前插入一个元索或删除某元索，必须知道该元素的前驱结点的指针。7.链表是本部分学习的重点和难点。重点学握以下几种常用链表的特点利运算：单链表、循环链表、双向链表、双向循环链表的生成、插入、删除、遍历以及链表的分解和归并等操作。并能够设计出实现线性表其它运算的算法。8.从时间复杂度和空间复杂度的角度综合比较线性表在顺序和链式两种存储结构下的特点，即其各白适用的场合。9.线性表这一章里而的知识点不多，但耍做到深刻理解，能够应用相关知识点解决实际问题。链表上

6、插入、删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。2010考研真题：42.（13分）设将n（n>l）个整数存放到一维数组R中。设计一个在时间和空间两方面尽可能高效的算法。将R中的序列循环左移P（0

7、键Z处给出注释。(3)、说明你所设计算法的时间复杂度和空间复杂度。■解析：数据的存储结构，算法的时间复杂度和空间复杂度■答案：(1)建立一个可以放下p个整数的辅助队列，将数组R中的前P个整数依次进入辅助队列,将R中后面的n-p个整数依次前移p个位置，将辅助队列中的数据依次出队，依次放入R屮第n・p个整数开始的位置。(2)使用c语言描述算法如下：〃pR是指向数组R的指针，n为存放的整数个数，〃p为循环左移的个数voidShift(int*pR,intn,intp){inttemp[p];//辅助数纟R,

8、存放要移岀的整数。inti=0;while(i