- 1、本文档共4页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
全国计算机等级考试二级c语言考点解析第二部分数据结构
考点1算法的基本概念
是对特定问题求解步骤的一种描述,算法是指令的有限序列,其中每一条指令表示一个或多个操作。
基本特征:(1)可行性(2)确定性(3)有穷性(4)有足够的情报【(4)输入(5)输出】
基本方法:(1)列举法(2)归纳法(3)递推法(4)递归(5)减半递推技术(6)回溯法
设计要求:(1)正确性(2)可读性(3)健壮性(4)效率与低存储量要求
时间复杂度:一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)
空间复杂度:指算法在计算机内执行时所需存储空间的度量。记作 S(n)=O(f(n))
考点2数据结构的基本概念
数据的逻辑结构:集合、线性结构、树形结构和图(网)状结构。
数据的存储结构:数据的逻辑结构在计算机中的映像,也称为数据的物理结构。通常有顺序、链接、散列和索引等结构。
考点3线性表及顺序存储结构
线性表:n(30)个数据元素的有限???列
顺序存储结构:将线性表中的元素相继存放在一个连续的存储空间
顺序存储方式:
LOC(a i+1) = LOC( a i )+l
LOC(a i) = LOC(a1)+(i-1)*l
顺序的插入:算法的复杂度E=n/2
顺序的删除:算法的复杂度E=(n-1)/2
考点4栈和队列
栈:限定仅在表尾进行插入或删除操作的线性表。
允许插入和删除的一端
称为栈顶(top),另一端
称为栈底(bottom)
特点:后进先出 (LIFO)
队列:只允许在表的一端进行插入,而在另一端删除元素的线性表。
在队列中,允许插入的一端叫队尾(rear)
允许删除的一端称为对头(front)。
特点:先进先出 (FIFO)
考点5树与二叉树
树的定义:由 n (n 3 0) 个结点的有限集合。如果 n = 0,称为空树;如果 n 0,则
有且仅有一个特定的称之为根(Root)的结点,它只有直接后继,但没有直接前驱;
当n 1,除根以外的其它结点划分为 m (m 0) 个互不相交的有限集 T1,T2 ,…,Tm,其中每个集合本身又是一棵树,并且称为根的子树(SubTree)
二叉树:另一种树型结构,它是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
特点:每个结点至多只有两棵子树(二叉树中不存在度大于2的结点)
五种形态:
L
L
R
R
性质1:在二叉树的第 i 层上至多有 2i -1个结点。
性质2 :深度为 k 的二叉树至多有 2 k-1个结点(k 3 1)。
性质3:对任何一棵二叉树T, 如果其叶结点数为 n0, 度为2的结点数为 n2,则n0=n2+1.
满二叉树 (Full Binary Tree) :一棵深度为k且有2 k-1个结点的二叉树称为满二叉树。
完全二叉树 (Complete Binary Tree):若设二叉树的高度为h,则共有h层。除第 h 层外,其它各层 (0 ~ h-1) 的结点数都达到最大个数,第 h 层从右向左连续缺若干结点,这就是完全二叉树。
6
2
1
7
5
4
3
8
9
10
11
12
完全二叉树
2
1
5
4
3
6
7
非完全二叉树
2
1
6
5
4
3
非完全二叉树
考点6二叉树的遍历(重点)
前序遍历
方法:若二叉树为空,则执行空操作。否则:
访问根节点;
前序遍历左子树;
前序遍历右子树;
中序遍历
方法:若二叉树为空,则执行空操作。否则:
中序遍历左子树;
访问根节点;
中序遍历右子树;
后续遍历
方法:若二叉树为空,则执行空操作。否则
后序遍历左子树;
后序遍历右子树;
访问根节点;
例:
A
B
C
D
E
F
前序遍历:ABDECF
中序遍历:DBEACF
后序遍历:DEBFCA
考试常出题型:给定二叉树的某两种遍历顺序,求另外一种遍历顺序。
考点6查找技术
顺序查找、二分法查找。
考点7排序技术(重点)
交换类排序技术
冒泡排序
快速排序
选择类排序
简单选择排序
堆排序
插入类排序
简单插入排序
希尔(Shell)排序
文档评论(0)