计算机统考复习指导docx.docx
- 文档编号:11695356
- 上传时间:2023-06-02
- 格式:DOCX
- 页数:102
- 大小:627.09KB
计算机统考复习指导docx.docx
《计算机统考复习指导docx.docx》由会员分享,可在线阅读,更多相关《计算机统考复习指导docx.docx(102页珍藏版)》请在冰点文库上搜索。
计算机统考复习指导docx
2011年计算机统考
【考查目标】
计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。
要求考牛比较系统地学握上述专业基础课程的概念、基木原理和方法,能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。
【考试形式和试卷结构】
1.试卷满分及考试时间
木试卷满分为150分,考试时间为180分钟
2.答题方式
闭卷、笔试
3.试卷内容结构
数据结构45分
计算机组成原理45分
操作系统35分
计算机网络25分
4.试卷题型结构
单项选择题80分(40小题,每小题2分)
综合应用题70分
数据结构
【考查目标】
1.理解数据结构的基本概念;掌握数据的逻辑结构、存储结构及其差异,以及各种基本操作的实现。
2.掌握基木的数据处理原理和方法的基础上,能够对算法进行设计与分析。
3.能够选择合适的数据结构和方法进行问题求解。
线性表
大纲要求:
(一)线性表的定义和基木操作
(二)线性表的实现
1•顺序存储结构
2.链式存储结构
3.线性表的应用
知识点:
1.深刻理解数据结构的概念,掌握数据结构的“三要素”:
逻辑结构、物理(存储)结构及在这种结构上所定义的操作“运算”。
2.时间复杂度和空间复杂度的定义,常用计算语句频度来估算算法的时间复杂度。
3.线性表的逻辑结构,是指线性表的数据元索间存在看线性关系。
主要是指:
除第-•及最后一个元素外,每个结点都只有一个帀j趋和只有一个后继。
在顺序存储结构中,元素存储的先后位置反映出这种逻辑关系,而在链式存储结构中,是靠指针来反映这种逻辑关系的。
4.顺序存储结构用向量(一维数组)表示,给定下标,可以存取相应元素,属于随机存収的存储结构。
5.线性表的顺序存储方式及其在具体语言环境下的两种不同实现:
表空间的静态分配和动态分配。
掌握顺序表上实现插入、删除、定位等运算的算法。
6.尽管“只耍知道某结点的指针就町以存取该元素”,但因链表的存取都需要从头指针开始,顺链而行,故链表不属于随机存取结构。
要理解头指针、头结点、首元结点和元素结点的差别。
头结点是在插入、删除等操作时,为了算法的统一而设立的(若无头结点,则在第一元素前插入元素或删除第一元素时,链表的头指针总在变化)。
对链表(不包括循环链表)的任何操作,均要从头结点开始,头结点的指针具有标记作用,故头指针往往被称为链表的名字,如链表head是指链农头结点的指针是heado理解循环链农中设置尾指针而不设置头指针的好处。
链表操作屮应注意不要使链意外“断开”。
因此,若在某结点前插入一个元索或删除某元索,必须知道该元素的前驱结点的指针。
7.链表是本部分学习的重点和难点。
重点学握以下几种常用链表的特点利运算:
单链表、循环链表、双向链表、双向循环链表的生成、插入、删除、遍历以及链表的分解和归并等操作。
并能够设计出实现线性表其它运算的算法。
8.从时间复杂度和空间复杂度的角度综合比较线性表在顺序和链式两种存储结构下的特点,即其各白适用的场合。
9.线性表这一章里而的知识点不多,但耍做到深刻理解,能够应用相关知识点解决实际问题。
链表上插入、删除节点时的指针操作是选择题的一个常考点,诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。
2010考研真题:
42.(13分)设将n(n>l)个整数存放到一维数组R中。
设计一个在时间和空间两方面尽可能高效的算法。
将R中的序列循环左移P(0
(1)、给出算法的基本设计思想。
(2)、根据设计思想,采用C或C++或JAVA语言描述算法,关键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,存放要移岀的整数。
inti=0;
while(i
{
〃将R小前p个数据存入辅助数at'Po
temp[i]=pR[i];
i++;
}
i=0;
while(i { 〃将R中从第p个整数开始的整数前移P个位置。 pR[i]=pR[p+i]; i++; } i=0; whilefi { 〃将辅助数组中的p个数据放到R中第n-p个数据的后Ifli。 pR[p+i]=temp[i]; i++; } return; } (3)所设计的算法的时间复杂度为0(n),空间复杂度为0(p) 二栈、队列和数组 大纲要求: (1)栈和队列的棊木概念 (二)栈和队列的顺序存储结构 (三)栈和队列的链式存储结构 (四)栈和队列的应用 (五)特殊矩阵的压缩存储 知识点: 1.栈、队列的定义及其相关数据结构的概念,包括: 顺序栈、链栈、循环队列、链队列等。 栈与队列存取数据(请注意包括: 存和取两部分)的特点。 2.掌握顺序栈和链栈上的进栈和追栈的算法,并弄清栈空和栈满的条件。 注意因栈在一端操作,故通常链栈不设头结点。 3.如何将中缀表达式转换成前缀、后缀表达式,了解对两种表达式求值的方法。 4.栈与递归的关系。 用递归解决的几类问题: 问题的定义是递归的,数据结构是递归的,以及问题的解法是递归的。 掌握典型问题的算法以及将递归算法转换为非递归算法,如n! 阶乘问题,fib数列问题,hanoi问题。 了解在数值表达式的求解、括号的配对等问题屮应用栈的工作原理。 5.掌握在链队列上实现入队和出队的算法。 注意对仅剩一个元索的链队列删除元索时的处理(令队尾指针指向队头)。 还需特別注意仅设尾指针的循环链队列的各种操作的实现。 6.循环队列队空及队满的条件。 队空定义为队头指针等于队尾指针,队满则可用牺牲一个单元或是设标记的方法,这里特别注意取模运算。 掌握循坏队列中入队与出队算法。 7.在示续章节屮多处有栈和队列的应用,如二叉树遍历的递归和非递归算法、图的深度优先遍历等都用到栈,而树的层次遍历、图的广度优先遍历等则用到队列。 这些方面的应用应重点掌握。 &数组在机器(内存)级上采川顺序存储结构。 掌握数组(主要是二维)在以行序为主和列序为主的存储11'的地址计算方法。 9.特殊矩阵(对称矩阵、对角矩阵、三角矩阵)在压缩存储是的下标变换公式。 2009考研真题: 1•为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,1何打印机则依次从该缓冲区中取出数据。 该缓冲区的逻辑结构应该是(B) A.栈 B.队列 C.树 D.图 2.设栈S和队列Q的初始状态均为空,元索abcdefg依次进入栈S。 若每个元索出栈后立即进入队列Q,且7个元素出队的顺序是bdcfeag,则栈S的容最至少是C A.1 B.2 C.3 D.4 ■解析: 理解其过程和含义 42.(15牛)已知一个带有表头结点的单链表,结点结构为 date"inlT| 假设该链表只给出了头指针listo在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。 若查找成功,算法输出该结点的data值,并返回1;否则,只返回0。 要求: (1)描述算法的基本设计思想 (2)描述算法的详细实现步骤 (3)根据设计思想和实现步骤,采用程序设计语言描述算法(使用C或C++或JAVA语言实现),关键Z处请给出简耍注禅■解析: 这种临时变量作为指针一前一后是写程序的一般技巧,必须掌握 ■答案: (1)算法基木思想如下: 从头至尾遍历单链表,并用指针p指向当前结点的而k个结点。 当遍历到链表的最后一个结点吋,指针p所指向的结点即为所查找的结点。 (2)详细实现步骤: 增加两个指针变最和一个整型变最,从链表头向后遍历,其中指针pl指向当前遍历的结点,指针p指向pl所指向结点的前k个结点,如果plZ前没冇k个结点,那么p指向表头结点。 用整型变量i表示当前遍历了多少个结点,当i>k时,指针p随着何次遍历,也向询移动一个结点。 当遍历完成时,p或者指向表头结点,或者指向链表中倒数第k个位置上的结点。 (3)算法描述: intLocateElement(Linklistlist,intk) { pl=list->link; p=list;i=l; while(pl) { pl=pl->link; i++; if(i>k) p=p->next;〃如果i>k,则p也往后移 } 讦(p==list) return0;//说明链表没有k个结点 else { printf("%d\n",p・>data); return1; } } 2010考研真题: 1、若元索a,b,c,d,e,f依次进栈,允许进栈、退栈操作交替进行。 但不允许连续三次进行退栈工作,则不可能得到的出栈序列是(D) A: dcebfa B: cbdaef C: dbcaef D: afedcb ■解析: 1: 这种题目太常见了,一定要掌握,同时一定要明白“允许进栈、退栈操作交替进行”对于这个题目,我的评价是“下马威”,我的很多学习跟我说今年的题目很难,其实在我看来是很烦。 2: 这里的出栈序列,不要搞反了啊。 2、某队列允许在•其两端进行入队操作,但仅允许在一端进行出队操作,则不可能得到的顺序是(C) A: bacde B: dbace C: dbcae D: ecbad ■解析: 知道队列长什么样 这里有个技巧: a和b—定是在一块的啊! 知道为什么有这个技巧吗? 三树与二叉树 大纲要求: (一)树的概念 (二)二义树 1.二叉树的定义及其主耍特征 2.二义树的顺序存储结构和链式存储结构 3•二叉树的遍历 4.线索二叉树的基木概念和构造 5•二叉排序树 6.平衡二叉树 (三)树、森林 1.树的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 (四)树的应用 1•等价类问题 2.哈夫曼(Huffman)树和哈夫曼编码 知识点: 1.二叉树的概念、性质 (1)掌握树和二叉树的定义。 (2)理解二叉树与普通双分支树的区别。 二叉树是一种特殊的树,这种特殊不仅仅在于其分支最多为2以及其它特征,一个最重要的特殊之处是在于: 二叉树是有序的。 即二叉树的左右孩子是不可交换的,如果交换了就成了另外一棵二叉树,这样交换Z后的二叉树与原二叉树是不相同的两棵二叉树。 但是,对于普通的双分支树而言,不具有这种性质。 (3)满二叉树和完全二叉树的概念。 (4)重点掌握二叉树的五个性质及证明方法,并把这种方法推广到K叉树。 普通二叉树的五个性质: 第i层的最多结点数,深度为k的二叉树的最多结点数,n0=n2+l的性质,n个结点的完全二叉树的深度,顺序存储二叉树时孩子结点与父结点之间的换算关系(序号i结点的左孩子为: 2*i,右孩子为: 2*i+l)0 2.掌握二叉树的顺序存储结构和二叉链表、三叉链表存储结构的各自优缺点及适用场合,以及二叉树的顺序存储结构和二叉链表存储结构的相互转换的算法。 3.熟练掌握二叉树的先序,中序和后序遍历算法以及按层次遍历 二叉树的先序、中序和后序三种遍历算法,划分的依据是视其每个算法中对根结点数据的访问顺序而定。 不仅要熟练掌握这三种遍历的递归算法,理解具执行的实际步骤,并且应该熟练掌握三种遍历的非递归算法。 4.遍历是基础,重点掌握在三种基本遍历算法的慕础上实现二叉树的其它算法 如求二叉树叶子结点总数,求二叉树结点总数,求度为1或度为2的结点总数,复制二叉树,建立二叉树,交换左右子树,查找值为n的某个指定结点,删除值为n的某个指定结点等等。 5.线索二叉树的引出,是为避免如二叉树遍历时的递归求解。 递归虽然形式上比较好理解,但是消耗了大虽的内存资源,如果递归层次一多,势必带来资源耗尽的危险。 二叉树线索化的实质是建立结点在相应序列中少其前驱和后继Z间的直接联系。 对于线索二叉树,应该掌握: 线索化的实质,三种线索化的算法,线索化后二叉树的遍历算法,基本线索二叉树的其它算法问题(如: 查找某一类线索二叉树中指定结点的前驱或后继结点)。 6.二叉排序树的屮序遍历结果是一个递增的有序序列。 二叉排序树的形态取决于元索的输入顺序,二叉排序树在最差情况下形成单支树。 熟练掌握其建立、查找、插入和删除算法,以及判断某棵二叉树是否二叉排序树这一问题的递归与非递归算法。 7.平衡二叉树是二义排序树的优化,平衡二叉树对左右子树的深度有了限定: 深度之差的绝对值不得大于学握平衡二义树的四种调整算法。 8.树与森林的遍历,只冇两种遍历算法: 先根与后根(对于森林而言称作: 先序与中序遍历)。 二者的先根与后根遍历与二叉树屮的遍历算法是有对应关系的: 先根遍历对应二叉树的先序遍历,而后根遍历対应二叉树的中序遍历。 二义树使用二叉链表分别存放它的左右孩子,树利用二叉链表存储孩子及兄弟(称孩子兄弟链表),而森林也是利川二义链表存储孩子及兄弟。 掌握树、森林和二义树间的相互转换。 9.简单掌握等价类的生成算法。 10•哈夫.曼树为了解决特定问题引出的特殊二叉树结构,它的前提是给二叉树的每条边赋予了权值,这样形成的二叉树按权相加之和是最小的,一般來说,哈夫曼树的形态不是唯一的。 理解哈夫曼编码的基本原理,掌握基于哈夫曼树生成哈夫曼编码的方法。 11.树和二叉树C这一章屮我们从顺序式的数据结构,转向层次式的数据结构,要掌握树、二叉树的各种性质、树和二叉树的不同存储结构、淼林、树和二叉树Z间的转换、线索化二叉树、二叉树的应用(二叉排序树、平衡二叉树和Huffman树),重点耍熟练掌握的,是森林、树以及二叉树的而中后三种遍历方式,要能进行和应的算法设计。 这一部分是数据结构考题历来的重点和难点,复习时要特别关注。 一些常见的选择题考点包括: 满二叉树、完全二叉树节点数的计算,由树、二叉树的示意图给出相应的遍历序列,依据二叉树的遍历序列还原二叉树,线索化的实质,计算采用不同的方法线索化后二叉树剩余空指针域的个数,平衡二叉树的定义、性质、建立和四种调整算法以及回溯法相关的问题。 常见的综合应用题考点包括: 二叉树的遍历算法,遍历基础上针对二叉树的一些统计和操作(比如结点数统计、左右了树对换等等),判断某棵二叉树是否二叉排序树,以上这些都要求能用递归的和非递归的算法解决,特别要重视非递归的算法,线索化后二叉树的遍历算法,如查找某结点线索化后的前驱或后继结点的算法以及给出Huffman编码等等。 2009考研真题: 3. 给定二叉树图所示。 设N代表二叉树的根,L代表根结点的左子树,R代表根结点的右了树。 若遍历后的结点序列为3,1,7,5,6,2,4,则其遍历方式是(D) A.LRN B.NRL C.RLN D.RNL ■解析: 为什么是这个序列的输出 程序怎么写 4. 下列二叉排序树中,满足平衡二叉树定义的是(B) ■解析: 什么叫平衡二叉树: 平衡二叉树,又称AVL树。 它或者是一棵空树,或者是具有下列性质的二叉树: 它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度之差的绝对值不超过lo 5.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则完全二叉树的结点个数最多是(C) A.39 B.52 C.111 D.119 ■解析: 计算公式及理由 6.将森林转换为对应的二叉树,若在二叉树中,结点u是结点v的父结点的父结点,则在原來的森林中,u和v可能具有的关系是(B) I.父子关系II.兄弟关系川・u的父结点与v的父结点是兄弟关系 A.只有II B.I和II C.I和III D.kII和III ■解析: 需要理解怎么转换 2010考研真题: 3、下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是(B) ■解析: 什么是后序线索树? 4、在下列所示的平衡二义树中插入关键字48后得到一棵新平衡二义树,在新平衡二义树中,关键字37所在结点的左、右子结点屮保存的关键字分别是(C) A: 13,48 B: 24,48 C: 24,53 D: 24,905、在棵度为4的树T屮,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶节点个数是(B) A: 41 B: 82 C: 113 D: 1226、对n(n人于等于2)个权值均不相同的字符构成哈夫曼树,关于该树的叙述屮,错i吴的是 (B) A: 该树一定是一棵完全二叉树 B: 树中一定没有度为1的结点 C: 树中两个权值最小的结点一定是兄弟结点 D: 树中任-非叶结点的权值一定不小于下一任一结点的权值 大纲要求: (一)图的概念 (二)图的存储及基木操作 1.邻接矩阵法 2.邻接表法 (三)图的遍历 1.深度优先搜索 2.广度优先搜索 (四)图的基本应用及其复朵度分析 1.最小(代价)牛成树 2.最短路径 3.拓扑排序 4.关键路径 知识点: 1.图的基木概念,包括: 图的定义和特点、无向图、有向图、入度、出度、完全图、生成树、路径长度、回路、(强)连通图、(强)连通分量等概念。 掌握与这些概念相联系的 相关计算题。 在基本概念中,完全图、连通分量、生成树和邻接点是重点。 2.图的存储形式。 图是复杂的数据结构,冇顺序和链式两种存储结构: 数组表示法(重点是邻接矩阵),邻接表与逆邻接表,这两种存储结构对无向图和有向图均使川。 3.熟练掌握图的两种遍历算法: 深度遍历和广度遍历。 深度遍历和广度遍历是图的两种基本的遍历算法,这两个算法对图一章的重要性等同于“先序、中序、后序遍历“对于二叉树一章的重要性。 掌握图的两种遍历算法的应用,图一章的算法设计题常常是基于这两种基本的遍历算法而设计的。 例如,在(强)连通图屮,主过程一次调用深(广)度优先遍历过程(DFS/BFS),即可遍历全部顶点,故可以用此方法求出连通分量的个数,要会画岀遍历屮形成的深(广)度优先生成树和生成森林。 乂如,"求最长的最切路径问题〃和“判断两顶点间是否存在长为K的简单路径问题〃,就用到了广度遍历和深度遍历算法。 4.最小生成树的概念。 连通图的最小牛成树通常是不唯一的,但最小生成树边上的权值之和是唯一的。 掌握最小生成树的构造方法: PRIM算法和KRUSKAL算法,根据这两种算法思想用图示法表示出求给定网的一棵最小生成树的过程。 5.拓扑排序是在有向图上对入度(先、后)为零的顶点的一种排序,通常结果不唯-。 拓扌卜排序有两种方法,一是无前趋的顶点优先算法,二是无后继的顶点优先算法。 换句话说,一种是“从前向后〃的排序,一种是"从后向前〃排。 后一种排序出来的结果是“逆拓扑有序〃的。 用拓扑排序和深度优先遍历都可判断图是否存在环路。 6.关键路径问题是图一章的难点问题。 理解关键路径的关键有三个方而: 一是何谓关键路径,二是最早时间的含义及求解方法,三是最晩时间的含义及求解方法。 简单地说,M早时间是通过“从前向后〃的方法求的,而最晩吋间是通过“从后向前〃的方法求解的,并n,要想求最晩时间必须是在所冇的最早时间都已经求出來z后才能进行。 熟练掌握求解的过程和步骤。 关键路径问题是工程进度控制的重要方法,具有很强的实丿ij性。 理解 “减少关键活动吋间可以缩短工期”是指该活动为所有关键路径所共有,且减少到尚未改变关键路径的前提下冇效。 7.最短路径问题也是为图一章的难点问题。 最短路径问题分为两种: 一是求从某一点出发到其余各点的最短路径;二是求图中每一对顶点之间的最短路径。 解决笫一个问题用DIJSKTRA算法,解决第二个问题用FLOYD算法,注意区分。 掌握这两个算法,并能手工熟练模拟。 掌握用求最短路径问题来解决的M用问题(如旅游景点及旅游路线的选择问题)。 8.在这一章中需耍识记的是图以及基于图的各种定义,存储方式。 要熟练掌握图的深度遍历和广度遍历算法,这是用图來解决应用问题时常用的算法基础。 需要掌握基于图的多个算法,能够以手工计算的方式在一个给定的图上执行特定的算法求解问题。 常见的应用问题肓接给出或经过抽象,会成为下列问题: 最小生成树求解(PRIM算法和KRUSKAL算法,两种方法思想都很简单,但要注意不要混淆这两种方法),拓扑排序问题(这里会用到数组实现的链表,可以注意一下),关键路径问题(数据结构的较大难点,要把概念理解透,能做出表格找出关键路径),最短路径问题(冇重要的应川背景,也是贪心法不多的能给出最优解的典型问题之一)。 2009考研真题: 7.下列关于无向连通图特性的叙述中,正确的是(A) I.所有顶点的度之和为偶数 11・边数大于顶点个数减1 III•至少有一个顶点的度为1 A.只有I B.只有II C.l和II D.l和III 41.(10分)帯权图(权值非负,表示边连接的两顶点间的距离)的最範路径问题是找出从初始顶点到冃标顶点Z间的一条最短路径。 假定从初始顶点到冃标顶点Z间存在路径,现有一种解决该问题的方法: 1设最短路径初始时仅包含初始顶点,令当询顶点U为初始顶点; 2选择离U最近R尚未在最短路径中的一个顶点V,加入到最短路径中,修改当前顶点U"; 3重复步骤②,直到U是日标顶点时为止。 请问上述方法能否求得最短路径? 若该方法可行,请证明之;否则,请举例说明。 ■解析: 最短路径问题,典型的送分题。 ■答案: 该方法求得的路径不一定是最短路径。 例如,对于下图所示的带权图,如果按照题中的原则,从A到C的最短路径为ATBTC,事实上其最短路径为ATDTC。 dI ■A: Bi <■ I•/ 210 "丄丿、 : D■: •: C: X../弋丿 2010考研真题: 7、若无向图G-(V.E)屮含7个顶点,则保证图G在任何情况卜•都是连通的,则需要的边数最少是(A) A: 6 B: 15 C: 16 D: 21 8、对下图进行拓补排序,可以得到不同的拓补序列的个数是(B) A: 4 B: 3 C: 2 D: 1 ■解析: 这个题目还是涉及的东西比较多的 五查找 大纲要求: (一)查找的基本概念 (二)顺序查找法 (三)折半查找法 (四)B■树 (五)散列(Hash)表及其查找 (六)查找算法的分析及应用知识点: 1.线性表上的杳找。 对于顺序表采用顺序杳找方法,逐个比较,顺序表设置了监视哨使查找效率大大提高。 対于有序顺序表采用折半查找法,其判定树是唯一的。 对于索引结构,采川索引顺序查找算法,此算法综合了上述两者的优点,既能较快速地查找,又能适应动态变化的要求。 注意这三种杏找的平均杏找长度。 掌握顺序杏找和折半查找算法的实现,其中,折半查找还要特别注意适用条件以及其递归实现方法。 2.B■树是多
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 统考 复习 指导 docx