香港大学中文论坛

 找回密码
 注册
搜索
查看: 21542|回复: 3

[计算机等级考试] 一级公共基础知识章节分析

[复制链接]
发表于 2007-1-12 13:19:52 | 显示全部楼层 |阅读模式
第一章数据结构与算法1.1 算法
算法:是指解题方案的准确而完整的描述。
算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。
算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括:
(1)可行性;
(2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性;
(3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义;
(4)拥有足够的情报。
算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。
指令系统:一个计算机系统能执行的所有指令的集合。
基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。
算法的控制结构:顺序结构、选择结构、循环结构。
算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。
算法复杂度:算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
算法空间复杂度是指执行这个算法所需要的内存空间。
1.2 数据结构的基本基本概念
数据结构研究的三个方面:
(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;
(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;
(3)对各种数据结构进行的运算。
数据结构是指相互有关联的数据元素的集合。
数据的逻辑结构包含:
(1)表示数据元素的信息;
(2)表示各数据元素之间的前后件关系。
数据的存储结构有顺序、链接、索引等。
线性结构条件:
(1)有且只有一个根结点;
(2)每一个结点最多有一个前件,也最多有一个后件。
非线性结构:不满足线性结构条件的数据结构。
1.3 线性表及其顺序存储结构
线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。
在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。
非空线性表的结构特征:
(1)且只有一个根结点a1,它无前件;
(2)有且只有一个终端结点an,它无后件;
(3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当n=0时,称为空表。
线性表的顺序存储结构具有以下两个基本特点:
(1)线性表中所有元素的所占的存储空间是连续的;
(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
ai的存储地址为:ADR(ai)=ADR(a1)+(i-1)k,,ADR(a1)为第一个元素的地址,k代表每个元素占的字节数。
顺序表的运算:插入、删除。 (详见14--16页)
1.4 栈和队列
栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。
栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据,栈具有记忆作用。用top表示栈顶位置,用bottom表示栈底。
栈的基本运算:(1)插入元素称为入栈运算;(2)删除元素称为退栈运算;(3)读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。
队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。Rear指针指向队尾,front指针指向队头。
队列是“先进行出”(FIFO)或“后进后出”(LILO)的线性表。
队列运算包括(1)入队运算:从队尾插入一个元素;(2)退队运算:从队头删除一个元素。
循环队列:s=0表示队列空,s=1且front=rear表示队列满
1.5 线性链表
数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点,简称结点。
结点由两部分组成:(1)用于存储数据元素值,称为数据域;(2)用于存放指针,称为指针域,用于指向前一个或后一个结点。
在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式即可用于表示线性结构,也可用于表示非线性结构。
线性链表,HEAD称为头指针,HEAD=NULL(或0)称为空表,如果是两指针:左指针(Llink)指向前件结点,右指针(Rlink)指向后件结点。
线性链表的基本运算:查找、插入、删除。
1.6 树与二叉树
树是一种简单的非线性结构,所有元素之间具有明显的层次特性。
在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的根。每一个结点可以有多个后件,称为该结点的子结点。没有后件的结点称为叶子结点。
在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。树的最大层次称为树的深度。
二叉树的特点:(1)非空二叉树只有一个根结点;(2)每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。
二叉树的基本性质:
(1)在二叉树的第k层上,最多有2k-1(k≥1)个结点;
(2)深度为m的二叉树最多有2m-1个结点;
(3)度为0的结点(即叶子结点)总是比度为2的结点多一个;
(4)具有n个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分;
(5)具有n个结点的完全二叉树的深度为[log2n]+1;
(6)设完全二叉树共有n个结点。如果从根结点开始,按层序(每一层从左到右)用自然数1,2,….n给结点进行编号(k=1,2….n),有以下结论:
①若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点编号为INT(k/2);
②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(也无右子结点);
③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。
满二叉树是指除最后一层外,每一层上的所有结点有两个子结点,则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。
完全二叉树是指除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点。
二叉树存储结构采用链式存储结构,对于满二叉树与完全二叉树可以按层序进行顺序存储。
二叉树的遍历:
(1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树;
(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树;
(3)后序遍历(LRD)首先遍历左子树,然后访问遍历右子树,最后访问根结点。
1.7 查找技术
顺序查找的使用情况:
(1)线性表为无序表;
(2)表采用链式存储结构。
二分法查找只适用于顺序存储的有序表,对于长度为n的有序线性表,最坏情况只需比较log2n次。
1.8 排序技术
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。
交换类排序法:(1)冒泡排序法,需要比较的次数为n(n-1)/2; (2)快速排序法。
插入类排序法:(1)简单插入排序法,最坏情况需要n(n-1)/2次比较;(2)希尔排序法,最坏情况需要O(n1.5)次比较。
选择类排序法:(1)简单选择排序法,
最坏情况需要n(n-1)/2次比较;(2)堆排序法,最坏情况需要O(nlog2n)次比较。

转帖自:http://blog.sina.com.cn/u/4bebf9a60100078c
发表于 2007-1-12 21:06:16 | 显示全部楼层
呵呵  这个是什么一级啊  楼主没有说清楚啊
 楼主| 发表于 2007-1-13 09:36:45 | 显示全部楼层
不好意思了,这个是全国计算机等级考试一级公共基础

学生考的比较少,一般都是干部\医生\部队的朋友们会报考一级,一般是用来晋级用的:)
发表于 2007-1-13 23:47:39 | 显示全部楼层
一级还真没听说过  只知道2\3\4级呵呵:)
您需要登录后才可以回帖 登录 | 注册

本版积分规则

全国大学论坛友情链接
北京高校排名 上海高校排名 天津高校排名 重庆高校排名 广东高校排名 江苏高校排名 山东高校排名
河南高校排名 浙江高校排名 河北高校排名 辽宁高校排名 四川高校排名 湖北高校排名 福建高校排名
广西高校排名 湖南高校排名 黑龙江高校排名 安徽高校排名 江西高校排名 吉林高校排名 云南高校排名
陕西高校排名 山西高校排名 内蒙古高校排名 新疆高校排名 贵州高校排名 甘肃高校排名 海南高校排名
青海高校排名 宁夏高校排名 西藏高校排名 香港高校排名 澳门高校排名 台湾高校排名 TOP100高校排名
安徽农业大学论坛
安徽建筑工程学院论坛
安徽医科大学论坛
安徽师范大学论坛
安徽工程大学论坛
安徽科技学院论坛
安徽大学论坛
安徽工业大学论坛
安徽中医药大学论坛
安庆师范大学论坛
安徽财经大学论坛
安徽理工大学论坛
合肥师范学院论坛
合肥学院论坛
合肥工业大学论坛
淮北师范大学论坛
中国科学技术大学论坛
北京农学院论坛
北京城市学院论坛
北京舞蹈学院论坛
北京电影学院论坛
北京吉利学院论坛
北京服装学院论坛
北京印刷学院论坛
北京信息科技大学论坛
北京第二外国语学院论坛
北京警察学院论坛
北京工业大学论坛
北京民族大学论坛
北京体育大学论坛
北京工商大学论坛
北京建筑工程学院论坛
北京中医药大学论坛
北京化工大学论坛
北京联合大学论坛
中央戏剧学院论坛
中央美术学院论坛
中国科学院大学论坛
中国农业大学论坛
中国音乐学院论坛
首都医科大学论坛
中央音乐学院论坛
中国信息大学论坛
现代音乐学院论坛
中国医科大学论坛
首都师范大学论坛
中国药科大学论坛
中国社会科学院论坛
首都经济贸易大学论坛
中央财经大学论坛
中国矿业大学论坛
中国政法大学论坛
中华女子学院论坛
中国青年政治学院论坛
外交学院论坛
中央民族大学论坛
华北电力大学论坛
北方工业大学论坛
北京交通大学论坛
北京大学论坛
清华大学论坛
国际关系学院论坛
中国石油大学论坛
北京科技大学论坛
北京林业大学论坛
北京理工大学论坛
北京师范大学论坛
北京邮电大学论坛
对外经济贸易大学论坛
北京外国语大学论坛
北京语言大学论坛
北京航空航天大学论坛
中国传媒大学论坛
中国人民大学论坛
福建农林大学论坛
福建医科大学论坛
福州师范大学论坛
福建工程学院论坛
福建中医药大学论坛
福州大学 论坛
华侨大学论坛
集美大学论坛
闽江大学论坛
闽南师范大学论坛
闽南理工学院论坛
莆田学院论坛
泉州师范学院论坛
厦门大学 论坛
厦门理工学院论坛
仰恩大学论坛
兰州工业学院论坛
兰州交通大学论坛
兰州大学论坛
兰州财经大学论坛
西北师范大学论坛
西北民族大学论坛
东莞理工学院论坛
广州美术学院论坛
广东女子职业技术学院论坛
广东技术师范学院论坛
广东医科大学论坛
广东海洋大学论坛
广东石油化工学院论坛
广东药学院论坛
广东金融学院论坛
广东财经大学论坛
广东外语外贸大学论坛
广东工业大学论坛
广州工商学院论坛
广州商学院论坛
广州医科大学论坛
广州体育学院论坛
广州中医药大学论坛
惠州学院论坛
岭南师范学院论坛
广东培正学院论坛
华南农业大学论坛
韶关学院论坛
南方医科大学论坛
南方科技大学论坛
广州大学论坛
暨南大学论坛
华南师范大学 论坛
华南理工大学 论坛
深圳大学 论坛
中山大学 论坛
汕头大学论坛
五邑大学论坛
星海音乐学院论坛
仲恺农业工程学院论坛
肇庆学院论坛
桂林理工大学论坛
桂林电子科技大学论坛
广西大学论坛
广西师范大学论坛
广西财经学院论坛
南宁职业学院论坛
贵州师范大学论坛
贵州大学论坛
海南职业技术学院论坛
海口经济学院论坛
海南外国语职业学院论坛
海南经贸学院论坛
海南科技职业学院论坛
海南医学院论坛
海南师范大学论坛
海南软件职业学院论坛
琼州学院论坛
海南大学论坛
河北大学论坛
河北农业大学论坛
河北工程大学论坛
河北医科大学论坛
河北师范大学论坛
河北科技大学论坛
河北工业大学论坛
河北经贸大学论坛
河北理工大学论坛
唐山大学论坛
石家庄经济学院论坛
唐山师范学院论坛
燕山大学论坛
河南科技大学论坛
河南农业大学论坛
河南师范大学论坛
河南大学论坛
黄河科技学院论坛
河南工程学院论坛
河南中医学院论坛
河南理工大学论坛
河南财经政法大学论坛
洛阳理工学院论坛
南阳师范学院论坛
郑州大学论坛
郑州轻工业学院论坛
哈尔滨商业大学论坛
黑龙江科技大学论坛
黑龙江中医药学院论坛
哈尔滨工程大学论坛
哈尔滨医科大学论坛
哈尔滨师范大学论坛
哈尔滨学院论坛
哈尔滨理工大学论坛
东北农业大学论坛
东北林业大学论坛
东北石油大学论坛
齐齐哈尔大学论坛
黑龙江大学论坛
哈尔滨工业大学 论坛
华中师范大学 论坛
中国地质大学 论坛
汉口学院论坛
湖北师范学院论坛
湖北经济学院论坛
湖北工业大学论坛
湖北中医药大学 论坛
湖北美术学院论坛
湖北汽车工业学院论坛
湖北大学论坛
湖北民族学院论坛
华中科技大学 论坛
华中农业大学论坛
江汉大学论坛
中南民族大学论坛
武汉音乐学院 论坛
武汉工业学院论坛
武汉大学论坛
武汉理工大学论坛
武汉体院学院论坛
武汉工程大学 论坛
武汉工商学院论坛
武汉纺织大学论坛
武汉科技大学论坛
武昌理工学院论坛
长江大学论坛
中南财经政法大学论坛
长沙学院论坛
中南大学论坛
中南林业科技大学论坛
长沙理工大学论坛
湖南农业大学论坛
湖南工程学院论坛
湖南师大论坛
湖南商学院论坛
湖南科技大学论坛
湖南文理学院论坛
湖南中医药大学论坛
湖南工业大学论坛
衡阳师范学院论坛
吉首大学论坛
国防科技大学论坛
南华大学论坛
湖南大学论坛
湘潭大学论坛
长春工程大学论坛
长春大学论坛
长春工业大学论坛
长春理工大学论坛
吉林农业大学论坛
吉林建筑工程学院论坛
吉林大学论坛
东北电力大学论坛
东北师范大学论坛
延边大学论坛
中国矿业大学(徐州)论坛
常州大学论坛
河海大学论坛
淮阴工学院论坛
淮阴师范学院论坛
江苏师范大学论坛
江苏科技大学论坛
南京审计学院论坛
南京体育学院论坛
南京农业大学论坛
南京林业大学论坛
南京工程学院论坛
南京医科大学论坛
南京师范大学论坛
南京财经大学论坛
南京邮电大学论坛
南京理工大学论坛
南京工业大学论坛
南京晓庄学院论坛
南京中医药大学论坛
南通大学论坛
南京艺术学院论坛
南京航空航天大学论坛
南京信息工程大学论坛
苏州工艺美术学院论坛
东南大学论坛
苏州工业学院论坛
苏州大学论坛
江南大学 论坛
江苏大学论坛
苏州科技学院论坛
南京大学论坛
盐城工业学院论坛
扬州职业大学论坛
扬州大学 论坛
东华理工大学论坛
华东交通大学论坛
景德镇陶瓷学院论坛
九江学院论坛
江西师范大学论坛
江西财经论坛
江西理工大学论坛
江西科技学院论坛
南昌航空大学论坛
南昌大学论坛
南昌理工学院论坛
井冈山大学论坛
新余学院论坛
宜春学院论坛
大连医科大学论坛
大连交通大学论坛
大连海事论坛
大连工业大学论坛
大连大学论坛
大连外国语学院论坛
大连理工大学论坛
大连职业技术学院论坛
东北财经大学论坛
鲁迅美术学院论坛
辽宁广告职业学院论坛
辽宁工业大学论坛
辽宁师范大学论坛
辽宁工程技术大学论坛
辽宁大学论坛
辽宁中医院大学论坛
辽宁对外经贸学院论坛
辽宁科技大学论坛
东北大学论坛
沈阳航空航天大学论坛
沈阳工程学院论坛
沈阳建筑大学论坛
沈阳工业大学论坛
沈阳农业大学论坛
沈阳音乐学院论坛
沈阳理工大学论坛
沈阳医学院论坛
沈阳师范大学论坛
沈阳药科大学论坛
沈阳大学论坛
沈阳化工大学论坛
内蒙古农业大学论坛
内蒙古电子信息学院论坛
内蒙古财经学院论坛
内蒙古化工职业学院论坛
内蒙古机电学院论坛
内蒙古医学院论坛
内蒙古师范大学论坛
内蒙古大学论坛
内蒙古工业大学论坛
内蒙古商贸职业学院论坛
北方民族大学论坛
宁夏大学论坛
聊城大学论坛
鲁东大学论坛
临沂大学论坛
中国海洋大学论坛
青岛农业大学论坛
青岛理工大学论坛
青岛大学论坛
曲阜师范大学论坛
青海师范大学论坛
齐鲁师范学院论坛
齐鲁工业大学论坛
青岛远洋船员学院论坛
青岛科技大学论坛
山东农业大学论坛
山东艺术学院论坛
山东城建学院论坛
山东交通学院论坛
山东建筑大学论坛
山东师范大学论坛
山东警察学院论坛
山东大学 论坛
山东财经大学论坛
山东科技大学论坛
山东理工大学论坛
山东政法学院论坛
山东中医药大学论坛
山东工商学院论坛
济南大学论坛
烟台大学论坛
中北大学论坛
山西建筑职业学院论坛
山西农业大学论坛
山西医科大学论坛
山西大学论坛
山西财经大学论坛
山西职业技术学院论坛
太原工业学院论坛
太原师范学院论坛
太原科技大学论坛
太原理工大学论坛
宝鸡文理学院论坛
西北农林科技大学论坛
西北工业大学 论坛
西北大学论坛
西北政法大学论坛
西安思源学院论坛
陕西师范大学论坛
陕西科技大学论坛
陕西中医药大学论坛
西安音乐学院论坛
西安美术学院论坛
长安大学论坛
西安外事学院论坛
西安工业大学论坛
西安财经学院论坛
西安理工大学论坛
西安电子科技大学论坛
西安欧亚学院论坛
西京学院论坛
西安外国语大学论坛
西安邮电学院论坛
西安建筑科技大学论坛
西安交通大学论坛
西安工程大学论坛
西安石油大学论坛
西安科技大学论坛
延安大学论坛
上海震旦学院论坛
东华大学论坛
华东师范大学论坛
华东政法大学论坛
华东理工大学论坛
上海东海学院论坛
上海建桥学院论坛
上海立信会计学院论坛
上海杉达学院论坛
上海商学院论坛
上海电机学院论坛
上海海关学院论坛
上海音乐学院论坛
上海金融学院论坛
上海电力学院论坛
上海外国语大学论坛
上海旅游专科学校论坛
上海海事大学论坛
上海师范大学论坛
上海海洋大学论坛
上海科技大学论坛
上海大学论坛
上海城建学院论坛
上海财经大学论坛
上海政法大学论坛
上海中医药大学论坛
上海应用技术学院论坛
上海视觉艺术学院论坛
上海第二工业大学论坛
上海戏剧学院论坛
上海工程技术大学论坛
上海对外经贸大学论坛
上海健康医学院论坛
上海体育学院论坛
天华学院论坛
上海理工大学论坛
复旦大学论坛
上海交通大学 论坛
同济大学论坛
成都艺术职业学院论坛
成都文理学院论坛
成都航空职业技术学院论坛
成都师范学院论坛
成都农业科技职业学院论坛
成都体育学院论坛
成都纺织专科学校论坛
成都工业学院论坛
成都学院论坛
成都理工大学论坛
成都医学院论坛
成都信息工程学院论坛
西华师范大学论坛
锦城学院论坛
乐山师范学院论坛
泸州医学院论坛
绵阳师范学院论坛
内江师范学院论坛
川北医学院论坛
四川建筑学院论坛
四川音乐学院论坛
四川美术学院论坛
四川传媒学院论坛
四川警察学院论坛
四川工商学院论坛
四川旅游学院论坛
锦江学院论坛
四川民族学院论坛
四川农业大学论坛
四川师范大学论坛
四川工业科技学院论坛
四川邮电学院论坛
四川文理学院论坛
四川文化艺术学院论坛
四川理工学院论坛
四川水利职业学院论坛
西南医科大学论坛
西南民族大学论坛
西南科技大学论坛
成都中医药大学论坛
电子科技大学论坛
西南财经大学论坛
西南石油大学论坛
西南交通大学论坛
四川大学论坛
西华大学论坛
宜宾职业学院论坛
宜宾学院论坛
四川影视学院论坛
中国民航大学论坛
天津美术学院论坛
天津农学院论坛
天津音乐学院论坛
天津商业大学论坛
天津外国语大学论坛
天津医科大学论坛
天津师范大学论坛
天津工业大学论坛
天津城市建设大学论坛
天津财经大学论坛
天津体育学院论坛
天津理工大学论坛
天津中医药大学论坛
天津科技大学论坛
南开大学 论坛
天津大学 论坛
香港大学论坛
石河子大学论坛
新疆医科大学论坛
新疆财经大学论坛
昆明医科大学论坛
昆明理工大学论坛
云南农业大学论坛
云南民族大学论坛
云南大学论坛
云南财经大学论坛
玉溪师范学院论坛
中国美术学院论坛
中国计量学院论坛
杭州电子科技大学论坛
杭州师范大学论坛
杭州职业技术学院论坛
宁波大学论坛
宁波理工学院论坛
温州大学论坛
浙江农林大学论坛
浙江中医药大学论坛
浙江工商大学论坛
浙江外国语学院论坛
浙江经贸学院论坛
浙江师范大学论坛
浙江海洋学院论坛
浙江树人大学论坛
浙江大学论坛
浙江工业大学论坛
浙江水利水电学院论坛
浙江理工大学论坛
浙江财经学院论坛
浙江传媒学院论坛
浙江科技学院论坛
重庆通信学院论坛
重庆电子工程职业技术学院论坛
重庆电力高专论坛
重庆工业职业学院论坛
重庆警察学院论坛
重庆房地产学院论坛
重庆工商大学融智学院论坛
重庆三峡学院论坛
重庆工商职业技术学院论坛
重庆大学城市科技学院论坛
重庆第二师范学院论坛
重庆科技学院论坛
重庆理工大学论坛
重庆工程职业技术学院论坛
重庆医药学院论坛
重庆城市管理职业学院论坛
重庆后勤工程学院论坛
四川外国语大学论坛
第三军医大学论坛
重庆交通大学论坛
重庆大学论坛
重庆师范大学论坛
重庆工商大学论坛
重庆邮电大学论坛
西南政法大学 论坛
重庆医科大学论坛
西南大学论坛
长江师范学院论坛
家庭车论坛
考研论坛论坛
论文网论坛
留学去论坛论坛
个个游论坛
觅优工作网论坛
大学综合信息网
手机访问本页请
扫描左边二维码
         本网站声明
本网站所有内容为网友上传,若存在版权问题或是相关责任请联系站长!
站长电话:0898-66661599    站长联系QQ:7123767   myubbs.com
         站长微信:7123767
请扫描右边二维码
www.myubbs.com

小黑屋|手机版|Archiver|香港大学中文论坛 ( 琼ICP备09001418号 )

GMT+8, 2019-11-13 14:49 , Processed in 0.156947 second(s), 14 queries .

Powered by 高考信息网 X3.3

© 2001-2013 大学排名

快速回复 返回顶部 返回列表