《2022年2022年计算机软件技术基础知识点储备 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年计算机软件技术基础知识点储备 .pdf（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章：概述1、程序 =算法 + 数据结构2、算法的几个基本特征：能行性确定性有穷性拥有足够的情报3、算法的复杂度主要包括：时间复杂度和空间复杂度第二章：数据结构1、逻辑结构：数据集合中各数据元素之间所固有的逻辑关系（集合结构、线性结构、树形结构、图状结构），可以看作是从具体问题抽象出来的数据模型。2、物理（存储）结构：在对数据进行处理时，各数据元素在计算机中的存储关系，可分为以下四种：顺序存储结构（存储空间连续）、链式存储结构、索引结构、散列结构3、数据结构的运算是指对数据结构中的结点进行操作的集合，包括插入、删除、更新、检索、排序等。4、数据元素是数据的基本单位5、有时数据元素可由若干个数
2、据项（数据的属性）组成，在这种情况下，数据项组成的数据元素称为记录，数据项是具有独立含义的最小标识单位，不可分割6、顺序存储结构：通常定义一维数组来表示线性表的顺序存储空间7、顺序表的插入异常处理：（ m 为线性表的空间大小，n 为线性表的长度 n 时，认为在最后一个元素之后（即第n+1 个元素之前）插入；当 i1 时，认为在第1 个元素之前插入函数的代码实现：void insert （int *v,int m,int n,int i, int b） int k; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -
3、 - - - - - - 第 1 页，共 16 页 - - - - - - - - - if(n=m) cout” 出现上溢错误 !” n) i=n+1; if(i=i;k-) vk=vk-1; vi-1=b; n=n+1; 8、顺序表的删除异常处理：当线性表为空（即n=0 ）时为下溢错误，不能进行删除，算法结束；当 in 时，认为不存在该元素，不进行删除。函数的代码实现：void delete(int *v, int m,int n, int i) int k; if(n=0) cout” 出现下溢错误！ ” endl; if(in) cout” 线性表里不存在该元素，不进行删除操作！” e
4、ndl; for(k=i;knumber=b; if(head=NULL) head=p; p-next=NULL; if(head-number=x) P-next=head; Head=p; q=head; while(q-next!=NULL)&(q-next)-number)!=x) q=q-next; p-next=q-next; q-next=p; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 16 页 - - - - - - - - - 13、单链表的删除
5、函数实现删除包换元素x 的结点void delete(int x) node *p,*q; if(head=NULL) cout” 没有要删除的元素！” number)=x) p=head-next; delete head; head=p; q= head; while(q-next)!=NULL)&(q-next)-number)!=x) q=q-next; if(q-next=NULL) cout” 没有要删除的元素！” next; q-next=p-next; delete p; 14、循环链表的插入函数实现在包含元素x 的结点前插入新元素b void insert(int x,int
6、 b) node *p,*q; p=new code; p-number=b; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 16 页 - - - - - - - - - q=head; while(q-next!=NULL)&(q-next)-numbe)r!=x) q=q-next; p-next=q-next; q-next=p; 15、循环链表的删除函数实现删除包含元素x 的结点void delete(int x) node *p,*q; q=head; whi
7、le(q-next!=NULL)&(q-next)-number)!=x) q=q-next; if(q-next=head) cout” 没有要删除的元素” next; q-next=p-next; delete p; 16、单链表与循环链表的区别单链表的头指针指向线性表第一个元素的结点；而循环链表的头指针指向表头结点，表头结点的指针域指向链表的第一个结点。单链表的最后结点的指针域为空；而循环链表最后结点的指针域指向表头结点. 17、下三角矩阵的压缩存储（以行为主压缩）（以列为主压缩）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -
8、 - 名师精心整理 - - - - - - - 第 5 页，共 16 页 - - - - - - - - - 18、对称矩阵的压缩19、索引存储的方式顺序 索引顺序、顺序 索引 链接、链接 索引顺序、链接 索引链接20、二叉树的性质在二叉树的第k 层上，最多有2k1(k 1) 个结点深度为 m 的二叉树最多有2m1 个结点（深度即为层数）在任意一棵二叉树中，度为0 的结点（即叶子结点）总是比度为2 的结点多一个具有 n 个结点的二叉树，其深度至少为log2n 1，其中 log2n表示取 log2n 的整数部分21、满二叉树是指每层的结点都有两个子结点，满的不行不行的了，完全二叉数是指最后一层必
9、须是从左至右的顺序断了线的，其余层都是满的。22、前序遍历、中序遍历、后续遍历（前中后对应的是根结点的访问顺序）前序遍历：先根结点，再左再右中序遍历：先左，再根结点，再右后续遍历：先左，再右，再根结点23、若给出三种遍历中的任意两种遍历，要求写出第三种遍历，思路如下：先正确画出对应的二叉树，根据已给条件进行验证，最后写出第三种遍历24、三种遍历的程序实现前序遍历void qian_ma() node *p; p=BT; pre(p); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第
10、6 页，共 16 页 - - - - - - - - - coutendl; static qian(node *p) if(p!=NULL) coutnumberlchild); qian(p-rchild); 中序遍历void zhong_ma() node *p; p=BT; zhong(p); coutlchild); coutnumberrchild); 后续遍历名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 16 页 - - - - - - - - - voi
11、d hou_ma() node *p; p=BT; hou(p); coutlchild); hou(p-rchild); coutnumber” ; 25、有序树转二叉树最最简便的方法对于有序树中的每一个结点，保留与其第一个子结点（即最左边的子结点）的链接，断开与其他子结点的链接，且将其他子结点依次链接在第一个子结点的右边。26、private 后边的叫数据成员（私有变量），public 后边的叫成员函数，其中函数名与类名完全相同，并且无返回值（void 也不能加）的叫构造函数，这个知识点老师说占 4 分的分值，而且老师还说一打眼就可以看出答案来的，方法我都告诉小超了呢。第三章：查找与排序1
12、、无序表只能用顺序查找，有序表可用对分查找，分块查找时，各子表的长度可以相等，也可以互相不等，但要求后一个子表中的每一个元素均大于前一个子表中的所有元素。2、查找效率比较：顺序查找 分块查找 对分查找 哈希表查找3、有序表的插入函数void insert （int *v,int m,int n, int x）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 16 页 - - - - - - - - - int k; if(n=m) cout” 出现上溢错误 !” x) vk
13、+1=vk; k=k-1; vk+1=x; n=n+1; 4、有序表的删除函数void delete(int *v, int m,int n, int i) int k; if(n=0) cout” 出现下溢错误！ ” endl; if(in) cout” 线性表里不存在该元素，不进行删除操作！” endl; for(k=i;k=n;k+) vk-1=vk; n=n-1; 5、有序表的对分查找函数int search （int x,int n ） int i,j,k; i=1; j=n; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -
14、- - 名师精心整理 - - - - - - - 第 9 页，共 16 页 - - - - - - - - - while(i=j) k=(i+j)/2; if(vk-1=x) coutx) j=k-1; else i=k-1; return(-1); 6、冒泡排序的原理以及程序实现原理：相邻两个元素比较大小，要是大，往后移，要是小，不要动，这样每进行一次就可以把最大的那个移到末尾了程序实现：void maopao(int *s,int n) int i,j; int temp; for(i=1;in;i+) for(j=0;jsj+1) temp=sj; sj=sj+1; sj+1=temp
15、; 7、快速排序的原理以及程序实现名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 16 页 - - - - - - - - - 原理：我明白快速排序了，在考试的时候，老师已经明确说了将第一个元素作为关键字，所以这样的话，将第一个元素设为p（k），并将 p（k）的值赋给T，然后设置两个指针 i 和 j 分别指向表的起始与最后的位置。反复作以下两步：将 j 逐渐减小，并逐次比较P（j）与 T，直到发现一个P（j）T 为止，将 P（i）移到 P（j）的位置上。上述两个操作交替
16、进行，直到指针i 与 j 指向同一个位置（即i=j ）为止，此时将T 移到 P（i）（即 P（j）的位置上。程序实现：void quick （int *p,int n） int m,i; int *s; i=split(p,n); quick(p,i); s=p+ （i+1 ）；m=n-(i+1); quick(s,m); static int spilt(int *p,int n) int i,j,k,l; int T; i=0; j=n-1; T=p0; while(i!=j) while(i=T) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -
17、- - - - - - 名师精心整理 - - - - - - - 第 11 页，共 16 页 - - - - - - - - - j=j-1; if(ij) pi=pj;i=i+1; while(ij)&(pi=t) i=i+1; if(ij) pj=pi;j=j-1; pi=T; return(i); 8、简单插入排序的原理及程序实现原理：就是从第二个元素开始，往前插到它应该在的位置就好啦，还是蛮实用的嘛程序实现：void insert(int *p,int n) int j,k; int t; for(j=1;j=0)&(pkt) pk+1=pk;k=k-1; pk+1=t; 名师资料总结
18、 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 16 页 - - - - - - - - - 9、希尔排序的原理以及程序实现原理：每间隔一定数量的元素之间进行比较和互换，慢慢减小这个间隔，直到间隔为1 时，进行一次插入排序就搞定了。程序实现：void shel(int *p,int n) int k,j,i; int t; k=n/2; while(k0) for(j=k;j=0)&(pit) pi+k=pi;i=i-k; pi+k=t; k=k/2; 10、简单选择排序的原理以及
19、程序实现原理：对于长度为n 的序列，需要扫描n-1 遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与剩余子表的第一个元素进行互换。程序实现：void select(int *p,int n) int i,j,k; int d; for(i=0;in-1;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 16 页 - - - - - - - - - k=i; for(j=i+1;jn;j+) if(pipk) k=j; if(k!=j) d=pi;
20、pi=pk;pk=d; 11、堆排序的原理以及程序实现这个有点复杂，你只需要记住两句话就可以啦，一是堆一定是完全二叉树，二是堆中所有根结点一定是大于其对应的叶子结点的。12、二叉排序树的概念及特性概念：左子树上所有结点的值均小于根结点的值；右子树上所有结点的值均不小于根结点的值。特征：中序遍历二叉排序树即可得到有序数列。13、给定序列构造二叉排序树第 1 个你就放在根结点就可以啦，然后放第二个的时候你就看如果是大于根结点的话放在右子树，如果是小于根结点的话就放左子树，整体如此，局部也是一样，最后还要检查一下哦，按照一定的顺序检查，还是很好玩的呢。14、二叉排序树的查找方法：给你一个数，怎么在二
21、叉排序树中找到它呢？从上往下比较呗，真的很神奇呢，啦啦啦第四章：资源管理技术1、多道程序设计：在一台处理机上并发运行多个程序2、相对地址（逻辑地址）与绝对地址概念相对地址：编写程序时使用的地址绝对地址：即为物理地址，数据存储在计算机中的地址3、虚拟存储的意义：扩大逻辑内存第五章：数据库名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 16 页 - - - - - - - - - 温馨提示：该部分因为考点较为明确，所以不按照知识点进行划分，而是按照考题类型进行整理。本章考题
22、占20 分，分为两个题型，对表的操作、对表中数据的操作。一、对表的操作例：创建学生基本信息表（学号，姓名，年龄，所在系），学号为字符类型，8 个字符长，学号为该表关键字；姓名为字符类型，10 个字符长；年龄为整型，可以不输入值；所在系为字符型，12 个字符长，允许不输入值CREAME TABLE S( SNO CHAR(8) PRIMARY KEY, SNAME CHAR(10) NOT NULL, AGE INT, DEPART CHAR(12) ); 例：学生信息表S 没有记录学生性别，修改表结构，增加“性别”列SEX，此列为字符型，长度为2 ALTER TABLE S ADD SEX C
23、HAR(2) 例：将学生表S 姓名 SNAME 列字符长度修改为20 ALTER TABLE S MODIFY (SNAME CHAR(20)；例：删除 S 表DROP TABLE S 二、对表中数据的操作有如下表Employee(emp_id, name, dept, salary, skill) 雇员（雇员编号，姓名，所属部门，工资，技能）雇员编号为关键字，写出满足下面要求的SQL语句：1）查询全部雇员所属部门的信息；SELECT dept FROM Employee; 2）查询工资在2000-3000 范围内雇员的姓名和所属部门以及工资数名师资料总结 - - -精品资料欢迎下载 - -
24、- - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 16 页 - - - - - - - - - SELECT name,dept,salary FROM Employee WHERE salary BETWEEN 2000 AND 3000 3）查询“销售”部门雇员的姓名和技能SELECT name,skill FROM Employee WHERE dept=” 销售 ” ；（4）统计雇员总数SELECT COUNT(*) FROM Employee; 5）多表联合查询SELECT DISTINCT 列名 , 列名 F
25、ROM 表名 1 JOIN 表名 2 ON 连接条件 WHERE 行选择条件 GROUP BY 列名 ORDER BY 列名 ASC(升序)或 DESC（降序）6）更改数据、插入数据、删除数据更改：例：将9811102 同学的 J03 课程成绩加5 分UPDATE SC SET G=G+5 WHERE SNO= 9811102 AND CNO=“J03“；插入：例：向课程表中增加一条新的课程记录INSERT INTO C VALUES( “J05“，” C 语言“ )；删除：例：删除C 表中的“数据库”课程记录DELETE FROM C WHERE CNAME= “数据库”；第六章：编译技术编译程序的基本组成：词法分析程序语法分析程序加工程序优化修饰部分装配程序或链接程序名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 16 页 - - - - - - - - -