好文档 - 专业文书写作范文服务资料分享网站

全国计算机二级VB公共基础知识总汇

天下 分享 时间: 加入收藏 我要投稿 点赞

1.5查找技术

考点9 顺序查找

考试链接:

考点9在笔试考试中考核几率在30%,一般出现选择题中,分值为2分,读者应该具体掌握顺序查找的算法。

查找是指在一个给定的数据结构中查找某个指定的元素。从线性表的第一个元素开始,依次将线性表中的元素与被查找的元素相比较,若相等则表示查找成功;若线性表中所有的元素都与被查找元素进行了比较但都不相等,则表示查找失败。 在下列两种情况下也只能采用顺序查找:

(1)如果线性表为无序表,则不管是顺序存储结构还是链式存储结构,只能用顺序查找。

(2)即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。

考点10 二分法查找

考试链接:

考点10在笔试考试中考核几率为30%,一般出现填空题中,分值为2分,考核比较多查找的比较次数,读者应该具体掌握二分查找法的算法。

二分法只适用于顺序存储的,按非递减排列的有序表,其方法如下: 设有序线性表的长度为n,被查找的元素为i, (1)将i与线性表的中间项进行比较; (2)若i与中间项的值相等,则查找成功;

(3)若i小于中间项,则在线性表的前半部分以相同的方法查找; (4)若i大于中间项,则在线性表的后半部分以相同的方法查找。 疑难解答:二分查找法适用于哪种情况?

二分查找法只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即

从小到大,但允许相邻元素值相等)。

这个过程一直进行到查找成功或子表长度为0为止。

对于长度为n的有序线性表,在最坏情况下,二分查找只需要比较log2n次。

1.6排序技术

考点11 交换类排序法

考试链接:

考点11属于比较难的内容,一般以选择题的形式考查,考核几率为30%,分值约为2分,读者应该熟练掌握几种排序算法的基本过程。

冒泡排序法和快速排序法都属于交换类排序法。

(1)冒泡排序法

首先,从表头开始往后扫描线性表,逐次比较相邻两个元素的大小,若前面的元素大于后面的元素,则将它们互换,不断地将两个相邻元素中的大者往后移动,最后最大者到了线性表的最后。

然后,从后到前扫描剩下的线性表,逐次比较相邻两个元素的大小,若后面的元素小于前面的元素,则将它们互换,不断地将两个相邻元素中的小者往前移动,最后最小者到了线性表的最前面。

对剩下的线性表重复上述过程,直到剩下的线性表变空为止,此时已经排好序。 在最坏的情况下,冒泡排序需要比较次数为n(n-1)/2。 (2)快速排序法

它的基本思想是:任取待排序序列中的某个元素作为基准(一般取第一个元素),通过一趟排序,将待排元素分为左右两个子序列,左子序列元素的排序码均小于或等于基准元素的排序码,右子序列的排序码则大于基准元素的排序码,然后分别对两个子序列继续进行排序,直至整个序列有序。 疑难解答:冒泡排序和快速排序的平均执行时间分别是多少?

冒泡排序法的平均执行时间是O(n2),而快速排序法的平均执行时间是O(nlog2n)。

1.7 例题详解

一、选择题

【例1】算法的时间复杂度取决于_______。(考点2)

A)问题的规模 B)待处理的数据的初态

C)问题的难度 D)A)和B)

解析:算法的时间复杂度不仅与问题的规模有关,在同一个问题规模下,而且与输入数据有关。即与输入数据所有的可能取值范围、输入各种数据或数据集的概率有关。

答案:D)

【例2】在数据结构中,从逻辑上可以把数据结构分成_______。(考点3)

A)内部结构和外部结构

C)紧凑结构和非紧凑结构

B)线性结构和非线性结构 D)动态结构和静态结构

解析:逻辑结构反映数据元素之间的逻辑关系,线性结构表示数据元素之间为一对一的关系,非线性结构表示数据元素之间为一对多或者多对一的关系,所以答案为B)。

答案:B)

【例3】以下_______不是栈的基本运算。(考点5)

A)判断栈是否为素空 B)将栈置为空栈 C)删除栈顶元素 D)删除栈底元素

解析:栈的基本运算有:入栈,出栈(删除栈顶元素),初始化、置空、判断栈是否为空或满、提取栈顶元素等,对栈的操作都是在栈顶进行的。

答案:D)

【例4】链表不具备的特点是_______。(考点6)

A)可随机访问任意一个结点 B)插入和删除不需要移动任何元素

C)不必事先估计存储空间 D)所需空间与其长度成正比

解析:顺序表可以随机访问任意一个结点,而链表必须从第一个数据结点出发,逐一查找每个结点。所以答案为A)。

答案:A)

【例5】已知某二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC,则它的前序遍历序列是_______。(考点8)

A)ACBED

B)DEABC

C)DECAB D)EDBAC

解析:后序遍历的顺序是\左子树-右子树-根结点\;中序遍历顺序是\左子树-根结点-右子树\;前序遍历顺序是\根结点-左子树-右子树\。根据各种遍历算法,不难得出前序遍历序列是EDBAC。所以答案为D)。

答案:D)

【例6】设有一个已按各元素的值排好序的线性表(长度大于2),对给定的值k,分别用顺序查找法和二分查找法查找一个与k相等的元素,比较的次数分别是s和b,在查找不成功的情况下,s和b的关系是_______。(考点9)

A)s=b B)s>b C)s

成功的关键字比较次数为[log2n]+1。当n≥2时,显然n+1>[log2n]+1。

答案:B)

【例7】在快速排序过程中,每次划分,将被划分的表(或子表)分成左、右两个子表,考虑这两个子表,下列结论一定正确的是_______。(考点11)

A)左、右两个子表都已各自排好序

B)左边子表中的元素都不大于右边子表中的元素 C) 左边子表的长度小于右边子表的长度

D)左、右两个子表中元素的平均值相等

解析:快速排序基本思想是:任取待排序表中的某个元素作为基准(一般取第一个元素),通过一趟排序,将待排元素分为左右两个子表,左子表元素的排序码均小于或等于基准元素的排序码,右子表的排序码则大于基准元素的排序码,然后分别对两个子表继续进行排序,直至整个表有序。

答案:B)

二、填空题

【例1】问题处理方案的正确而完整的描述称为_______。(考点1)

解析:计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 答案:算法

【例2】一个空的数据结构是按线性结构处理的,则属于_______。(考点4)

解析:一个空的数据结构是线性结构或是非线性结构,要根据具体情况而定。如果对数据结构的运算是按线性结构来处理的,则属于线性结构,否则属于非线性结构。

答案:线性结构

【例3】设树T的度为4,其中度为1、2、3和4的结点的个数分别为4、2、1、1,则T中叶子结点的个数为_______。(考点7)

解析:根据树的性质:树的结点数等于所有结点的度与对应的结点个数乘积之和加1。 因此树的结点数为1×4+2×2+3×1+4×1+1=16。叶子结点数目等于树结点总数减去度不为0的结点数之和,即16-(4+2+1+1)=8。

答案:8

【例4】二分法查找的存储结构仅限于_______且是有序的。(考点10)

解析:二分查找,也称折半查找,它是一种高效率的查找方法。但二分查找有条件限制:要求表必须用顺序存储结构,且表中元素必须按关键字有序(升序或降序均可)。 答案:顺序存储结构

第2章 程序设计基础

经过对部分考生的调查以及对近年真题的总结分析,笔试部分经常考查的是结构化程

序设计的原则、面向对象方法的基本概念,读者应对此部分进行重点学习。

详细重点学习知识点:

1.结构化程序设计方法的四个原则

2.对象、类、消息、继承的概念、类与实例的区别

2.1结构化程序设计

考点1 结构化程序设计的原则

考试链接:

考点1在笔试考试中出现的几率为30%,主要是以选择题的形式出现,分值为2分,此考点为识记内容,读者应该识记结构化程序设计方法的四个主要原则。

20世纪70年代提出了\结构化程序设计\的思想和方法。结构化程序设计方法引入了工程化思想和结构化思想,使大型软件的开发和编程得到了极大的改善。结构化程序设计方法的主要原则为:自顶向下、逐步求精、模块化和限制使用goto语句。

疑难解答:如何进行自顶向下设计方法?

程序设计时,应先考虑总体,后考虑细节;先考虑全局目标,后考虑局部目标;不要一开始就过多追

求众多的细节,先从最上层总目标开始设计,逐步使问题具体化。

2.2面向对象的程序设计

考点2 面向对象方法的基本概念

考试链接:

考点2在笔试考试中,是一个经常考查的内容,在笔试考试中出现的几率为70%,主要是以填空题的形式出现,分值为2分,此考点为重点识记内容,读者应该识记几个基本要素的定义、对象的特征以及消息、继承、类的定义。

误区警示:

当使用\对象\这个术语时,既可以指一个具体的对象,也可以泛指一般的对象,但是当使用\实例\这个术语时,必须是指一个具体的对象。

面向对象方法涵盖对象及对象属性与方法、类、继承、多态性几个基本要素。 (1)对象

通常把对对象的操作也称为方法或服务。 属性即对象所包含的信息,它在设计对象时确定,一般只能通过执行对象的操作来改变。属性值应该指的是纯粹的数据值,而不能指对象。

操作描述了对象执行的功能,若通过信息的传递,还可以为其他对象使用。 对象具有如下特征:标识惟一性、分类性、多态性、封装性、模块独立性。

(2)类和实例

类是具有共同属性、共同方法的对象的集合。它描述了属于该对象类型的所有对象的性质,而一个对象则是其对应类的一个实例。

类是关于对象性质的描述,它同对象一样,包括一组数据属性和在数据上的一组合法操作。

(3)消息

消息是实例之间传递的信息,它请求对象执行某一处理或回答某一要求的信息,它统一

了数据流和控制流。

一个消息由三部分组成:接收消息的对象的名称、消息标识符(消息名)和零个或多个参数。

(4)继承

广义地说,继承是指能够直接获得已有的性质和特征,而不必重复定义它们。 继承分为单继承与多重继承。单继承是指,一个类只允许有一个父类,即类等级为树形结构。多重继承是指,一个类允许有多个父类。

(5)多态性

对象根据所接收的消息而做出动作,同样的消息被不同的对象接收时可导致完全不同的行动,该现象称为多态性。

疑难解答:能举一下现实中的对象及其属性和操作吗?

一辆汽车是一个对象,它包含了汽车的属性(如颜色、型号等)及其操作(如启动、刹车等)。一个窗口是对象,它包含了窗口的属性(如大小、颜色等)及其操作(如打开、关闭等)。

2.3 例题详解

一、选择题

【例1】结构化程序设计方法提出于_______。(考点1)

A)20世纪50年代 B)20世纪60年代

C)20世纪70年代 D)20世纪80年代

解析:20世纪70年代提出了\结构化程序设计(structured programming)\的思想和方法。结构化程序设计方法引入了工程化思想和结构化思想,使大型软件的开发和编程得到了极大的改善。

答案:C)

【例2】结构化程序设计方法的主要原则有下列4项,不正确的是_______。(考点1)

A)自下向上

B)逐步求精

C)模块化 D)限制使用goto语句 解析:结构化程序设计方法的主要原则为:

(1)自顶向下:即先考虑总体,后考虑细节;先考虑全局目标,后考虑局部目标。 (2)逐步求精:对复杂问题,应设计一些子目标作过渡,逐步细化。

(3)模块化:把程序要解决的总目标分解为分目标,再进一步分解为具体的小目标,把每个小目标称为一个模块。

(4)限制使用goto语句。 答案:A)

【例3】面向对象的开发方法中,类与对象的关系是_______。(考点2)

A)抽象与具体

C)部分与整体

B)具体与抽象 D)整体与部分

解析:现实世界中的很多事物都具有相似的性质,把具有相似的属性和操作的对象归为类,也就是说类是具有共同属性、共同方法的对象的集合,是对对象的抽象。它描述了该对象类型的所有对象的性质,而一个对象则是对应类的一个具体实例。所以本题正确答案为A)

全国计算机二级VB公共基础知识总汇

1.5查找技术考点9顺序查找考试链接:考点9在笔试考试中考核几率在30%,一般出现选择题中,分值为2分,读者应该具体掌握顺序查找的算法。查找是指在一个给定的数据结构中查找某个指定的元素。从线性表的第一个元素开始,依次将线性表中的元素与被查找的元素相比较,若相等则表示查找成功;若线性表中所有的元素都与被查找元素
推荐度:
点击下载文档文档为doc格式
  • 正文标题

  • 上下篇章

  • 相关推荐

  • 精选图文

121581c5kf721et5igy6