没有合适的资源?快使用搜索试试~ 我知道了~
全国计算机二级基础重点知识点解析.doc
需积分: 5 0 下载量 94 浏览量
2022-07-18
15:12:45
上传
评论
收藏 412KB DOC 举报
温馨提示
试读
13页
全国计算机二级基础重点知识点解析.doc
资源详情
资源评论
资源推荐
.
1 / 13
全 国 计 算 机 二 级 基 础
§1 基本数据结构和算法
1.1 算法
算法概念:是对一个问题求解步骤的一种描述,是求解问题的方法,它是指令的有限序列,其中每条指
令表示一个或者多个操作。
算法不等于程序,也不等于计算机方法,程序的编制不可能优于算法的设计。
(2011.9)(1)以下表达中正确的是()
A)算法就是程序 B)设计算法时只要考虑数据结构的设计
C)设计算法时只需要考虑结果的可靠性 D)以上说法都不对
算法的基本特征:
(1)可行性;
(2)确定性,算法中每一步骤都必须有明确定义,不允许有模棱两可的解释,不允许
有多义性;
(3)有穷性,算法必须能在有限的时间做完,取能在执行有限个步骤后终止,包括合
理的执行时间的含义; (4)输入(>=0)和输出性(>=1)。
例 一个算法应该具有“确定性”等 5 个特性,下面对另外 4 个特性的描述中错误的是( )。
A.有零个或多个输入 B.有零个或多个输出
C.有穷性 D.可行性
答案:B
算法的基本要素:
(1)算法中对数据的运算和操作
在一般的计算机系统中,基本的运算和操作有以下4类:算术运算、逻辑运算、关系运算和数据传输。
(2)算法的控制结构
一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。
算法的复杂度:算法时间复杂和算法空间复杂度。
(1)算法时间复杂度是指执行算法所需要的计算工作量。
(2)算法空间复杂度是指执行这个算法所需要的存空间。
程序设计语言是用于书写计算机程序的语言,其基本成分有以下 4 种,数据成分:用来描述程序中的数
据。运算成分:描述程序中所需的运算。控制成分:用来构造程序的逻辑控制结构。传输成分:定义数据传
输成分,如输入输出语言。
例:程序设计语言的基本成分是数据成分、运算成分、控制成分和( )。
A) 对象成分B) 变量成分
C) 语句成分D) 传输成分
1.2 数据结构的基本概念
数据结构研究的三个方面:
(1)数据集合中和数元素之间所固有的逻辑关系,即数据的逻辑结构;
(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;
(3)对各种数据结构进行的运算。(基于逻辑结构)
数据的逻辑结构包含:
(1)表示数据元素的信息;
(2)表示各数据元素之间的前后件关系。
数据的存储结构有顺序、、索引等。
线性结构条件:
.
2 / 13
(1)有且只有一个根结点;
(2)每一个结点最多有一个前件,也最多有一个后件。
非线性结构:不满足线性结构条件的数据结构。
(2011.3)(2)以下表达中正确的是()
A)有一个以上根结点的数据结构不一定是非线性结构
B)只有一个根结点的数据结构不一定是线性结构
C)循环链表是非线性结构 D)双向链表是非线性结构
1.3 线性表与其顺序存储结构
线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。
在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。
非空线性表的结构特征:
(1)且只有一个根结点 a1,它无前件;
(2)有且只有一个终端结点 an,它无后件;
(3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数 n 称为线性
表的长度,当 n=0 时,称为空表。
线性表的顺序存储结构具有以下两个基本特点:
(1)线性表中所有元素的所占的存储空间是连续的;
(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
ai 的存储地址为:ADR(ai)=ADR(a1)+(i-1)×k,,ADR(a1)为第一个元素的地址,k 代表每个元素占的字节数。
(2011.9)(2)长度为 n 的顺序存储的线性表中插入一个元素,最坏情况下需要移动表中[2]元素。
(2010.9)(1)以下表达中正确的是
A)线性表的链式存储结构与顺序存储结构所需要的空间是相同的
B)线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构
C)线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构
D)上述三种说法都不对
1.4 栈和队列
栈
是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插入与删除的另一
端称为栈底。
(2011.9)(1)数据结构分为线性结构与非线性结构,带链的栈属于[1]。
(2011.3)(1)以下关于栈表达正确的是()
A)栈顶元素最先能被删除 B)栈顶元素最后才能被删除
C)栈底元素永远不能被删除 D)以上三种说法都不对
栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据,栈具有记忆作用。用 top 表示栈顶位置,
用 bottom 表示栈底。
(2010.9)(2)以下表达中正确的是
A)在栈中,栈中元素随栈底指针不变与栈顶指针的变化而动态变化
B)在栈中,栈顶指针不变,栈中元素随栈底指针的变化而动态变化
C)在栈中,栈底指针不变,栈中元素随栈顶指针的变化而动态变化
D)上述三种说法都不对
(2010.9)(1)一个栈的初始状态为空。首先将元素 5、4、3、2、1 依次入栈,然后退栈一次,再将元素 A,
B,C,D 依次入栈,之后将所有元素全部退栈,则所有元素退栈(包括中间退栈的元素)的顺序为[1]。
队列
是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。Rear 指针指向队尾,
front 指针指向队头。
.
3 / 13
队列是“先进行出”(FIFO)或“后进后出”(LILO)的线性表。
队列运算包括(1)入队运算:从队尾插入一个元素;(2)退队运算:从队头删除一个元素。
循环队列:s=0 表示队列空,s=1 且 front=rear 表示队列满
设某循环队列的容量为 50,如果头指针 front=45(指向队头元素的前一位置),尾指针
rear=10(指向队尾元素),则该循环队列中共有()个元素?
计算公式:(rear-front+M)%M
1.5 线性链表
数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点,简称结点。
结点由两部分组成:(1)用于存储数据元素值,称为数据域;(2)用于存放指针,称为指针域,用于指向
前一个或后一个结点。
在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻
辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。
(2011.9)(2)以下关于线性链表的表达中,正确是()
A)各数据结点的存储空间可以不连续,但他们的存储顺序与逻辑顺序必须一致
B)各数据结点的存储顺序与逻辑顺序可以不一致,但他们的存储空间必须连续
C)进行插入与删除时,不需要移动表中的元素 D)以上三种说法都不对
1.6 树与二叉树
树是一种简单的非线性结构,所有元素之间具有明显的层次特性。
在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。树的最
大层次称为树的深度。
二叉树的特点:(1)非空二叉树只有一个根结点;(2)每一个结点最多有两棵子树,且分别称为该结点的
左子树与右子树。
二叉树的基本性质:
(1)在二叉树的第 k 层上,最多有 2
k-1
(k≥1)个结点; (2)深度为 m 的二叉树最多有 2
m
-1 个结点; (3)
度为 0 的结点(即叶子结点)总是比度为 2 的结点多一个;
(4)具有 n 个结点的二叉树,其深度至少为[log
2
n]+1,其中[log
2
n]表示取 log
2
n 的整数部分;
(5)具有 n 个结点的完全二叉树的深度为[log
2
n]+1;
(2011.3)(3)某二叉树共有7个结点,其中叶子结点只有1个,则该二叉树的深度为(假设根结点在第1
层)
A)3 B)4 C)6 D)7
(2010.9)(3)一棵二叉树有 10 个度为 1 的结点,7 个度为 2 的结点,则该二叉树共有[3]个结点。
(2011.9)(3)以下关于二叉树的表达中,正确的是()
A)叶子结点总是比度为 2 的结点少一个 B)叶子结点总是比度为 2 的结点多一个
C)叶子结点数是度为 2 的结点数的两倍 D)度为 2 的结点数是度为 1 的结点数的两倍
满二叉树是指除最后一层外,每一层上的所有结点有两个子结点,则 k 层上有 2
k-1
个结点,深度为 m 的
满二叉树有 2
m
-1 个结点。
完全二叉树是指除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点。
二叉树存储结构采用链式存储结构,对于满二叉树与完全二叉树可以按层序进行存储。
二叉树的遍历:
(1)前序遍历(DLR):首先访问根结点,然后遍历左子树,最后遍历右子树;
(2)中序遍历(LDR):首先遍历左子树,然后访问根结点,最后遍历右子树;
(3)后序遍历(LRD): 首先遍历左子树,然后遍历右子树, 最后访问根结点.
(2011.3)(2)一棵二叉树的中序遍历结果为 DBEAFC,前序遍历结果为 ABDECF,则后序遍历结果为[2]。
1.7 查找技术
剩余12页未读,继续阅读
智慧安全方案
- 粉丝: 3651
- 资源: 59万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0