计算机等级考试中的数据结构.docVIP

计算机等级考试中的数据结构摘要：由于计算机技术的广范普及，越来越多的人报考计算机等级考试，等级考试分为基础知识和上机操作两部分，其中基础知识中的数据结构考点，对于非计算机专业的考生来说是一个难点，本文主要介绍等级考试中如何解决数据结构相关知识点，以便圆满的结束考试。1、 计算机等级考试的重要性随着计算机技术的迅速发展，计算机在各个领域的应用逐步推广，操作和应用计算机成为人们必须掌握的一种基本技能。一些企事业部门把计算机理论知识和实践操作能力作为上岗资格、职称评定、人员录用的依据之一，可见操作和应用计算机对于日常生活和工作尤为重要。全国计算机等级考试（NationalComputerRankExamination，简称NCRE），是经原国家教育委员会（现教育部）批准，由教育部考试中心主办，面向社会，用于考查应试人员计算机应用知识与技能的全国性计算机水平考试体系。NCRE考试采用全国统一命题，统一考试的形式。一年组织两次考试，一般为3月倒数第一个周六和9月倒数第二个周六。等级考试分为两个部分，一是公共基础知识，二是上机操作，其中公共基础知识由30分改为40分，上机操作由70分改为60分，二级公共基础知识分为四个部分：数据结构与算法、程序设计基础、软件工基础、数据库设计基础。这里我们仅对数据结构常考查知识点进行剖析。二、数据结构知识点剖析计算机科学是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示，信息的处理。信息的表示又影响到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序（核心论文快速发表找论文发表向导网江编辑加扣二三三五一六二五九七）的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。数据结构在计算机专业基础课中也属于比较难的一门课程，学习时不能死记硬背，必须进行理解。数据结构在各年等级考试中所占的分值很高，下图是笔者统计的最近四次二级考试中数据结构所占的分值，可以看出，对于总分为40分的基础知识中，数据结构所占的比例是很高的，考生应该重视起来。数据结构知识的考核点主要有两部分：（1）栈和队列：此知识点基本年年出题，可以看作是必考题，一般都是考查相关概念，栈是后进先出表即FILO表，而队列是先进先出表即FIFO表，考生只要牢记概念及基本性质就可以得满分。（2）二叉树性质：此知识点基本也是年年出题，可以看作是必考题，主要考查四个性质，其中性质3考查率比较高。除此之外还有二叉数的遍历，排序和查找在考试中也会涉及到，对于二叉数的遍历，一般是给出树求某种遍历，考生只要熟记三种遍历的规则就可以了，排序主要考查时间复杂度，查找主要考查最坏比较次数，考生需要认真看书并加以理解。三、经典例题（1） 下列关于栈叙述正确的是（）A）栈顶元素最先能被删除；B）栈顶元素最后才能被删除；C）栈底元素永远不能被删除；D）以上三种说法都不对。这道题主要考查栈的基本概念，对于概念考生不应只是死记，要深刻的理解。栈和队列（核心论文快速发表找论文发表向导网江编辑加扣二三三五一六二五九七）都是操作受限的线性表，其中栈是只能在表尾进行插入和删除操作，表尾端对应栈顶，而表头端对应栈底，栈又叫后进先出表（FILO），根据栈的概念我们可以找出正确答案，A是正确的，栈顶元素最先被删除，它是后进先出表。（2） 下列关于二叉树的叙述中，正确的是（）A）叶子结点总是比度为2的结点少一个；B）叶子结点总是比度为2的结点多一个；C）叶子结点数是度为的结点数的两倍；D）度为2的结点数是度为1的结点数的两倍。这道题主要考查数据结构中二叉数的性质3的应用，对于任意一棵二叉数，度为2的结点n2个，度为0的结点n0个，则n0=n2+1。度为0的结点即为叶子结点，也就是说叶子结点永远比度为2的结点多一个，根据性质3，我们可以给出正确答案B。（3） （二）对下列二叉树进行前序遍历的结果为（）（4） A）DYBEAFCZX；B）YDEBFZXCA；C）ABDYECFXZ；D）ABCDEFXYZ。这道题主要考查二叉树的遍历，二叉树的遍历有三种：前序遍历、中序遍历、后序遍历，其中都是以根结点为基准，前序遍历的规则是DLR，也就是先遍历根，再遍历（核心论文快速发表找论文发表向导网江编辑加扣二三三五一六二五九七）左子树，最后遍历右子树，对于其子树也要遵循这个原则。由图可知A是根，所以先序遍历应该是A-左子树-右子树，其中左子树先序遍历也应该满足规则，即BDYE，右子树先序遍历是CFXZ，