(完整)计算机软件技术基础知识点储备,推荐文档

1、第一章：概述1、程序 = 算法 + 数据结构2、算法的几个基本特征：能行性确定性有穷性拥有足够的情报3、算法的复杂度主要包括：时间复杂度和空间复杂度第二章：数据结构1、逻辑结构：数据集合中各数据元素之间所固有的逻辑关系（集合结构、线性结构、树形结构、图状结构），可以看作是从具体问题抽象出来的数据模型。2、物理（存储）结构：在对数据进行处理时，各数据元素在计算机中的存储关系，可分为以下四种：顺序存储结构（存储空间连续）、链式存储结构、索引结构、散列结构3、数据结构的运算是指对数据结构中的结点进行操作的集合，包括插入、删除、更新、检索、排序等。4、数据元素是数据的基本单位5、有时数据元素可由若干个

2、数据项（数据的属性）组成，在这种情况下，数据项组成的数据元素称为记录，数据项是具有独立含义的最小标识单位，不可分割6、顺序存储结构：通常定义一维数组来表示线性表的顺序存储空间7、顺序表的插入异常处理：（ m 为线性表的空间大小， n 为线性表的长度 <=m ，插入的位置为i， i 表示在第 i 个元素之前插入）当存储空间已满（即 n=m ）时为上溢错误，不能进行插入，算法结束；当 i>n时，认为在最后一个元素之后（即第n+1 个元素之前）插入；当 i<1时，认为在第 1 个元素之前插入函数的代码实现：void insert （int *v,int m,int n,int i,

3、 int b）int k;if(n=m) cout<<”出现上溢错误 !”<<endl;if(i>n)i=n+1;if(i<1) i=1;for(k=n;k>=i;k-)vk=vk-1;vi-1=b;n=n+1;8、顺序表的删除异常处理：当线性表为空（即n=0 ）时为下溢错误，不能进行删除，算法结束；当 i<1 或 i>n 时，认为不存在该元素，不进行删除。函数的代码实现：void delete(int *v, int m,int n, int i)int k;if(n=0)cout<<”出现下溢错误！ ”<<end

4、l;if(i<1)|(i>n)cout<<”线性表里不存在该元素，不进行删除操作！”<<endl;for(k=i;k<=n;k+)vk-1=vk;n=n-1;9、栈（相当于一个井）的相关概念先进后出（后进先出）栈顶允许插入与删除栈底不允许插入与删除10 、队列（相对于排队买饭）的相关概念 先进先出 队尾允许插入对头允许删除11 、链式存储每个结点由两部分组成：数据域和指针域12 、单链表的插入函数实现在包含元素x 的结点前插入新元素bvoid insert(int x,int b)node *p,*q;p=new node;p->number=b

5、;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;13 、单链表的删除函数实现删除包换元素x 的结点void delete(int x)node *p,*q;if(head=NULL) cout<<”没有要删除的元素！”<<endl

6、;if(head->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<<”没有要删除的元素！”<<endl;p=q->next;q->next=p->next;delete p;14 、循环链表的插入函数实现在包含元素x 的结点前插入新元素bvoid insert(int x,int b)nod

7、e *p,*q;p=new code;p->number=b;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;while(q->next!=NULL)&&(q->next)->number)!=x)q=q->next;if(q->next=

8、head) cout<<”没有要删除的元素”<<endl;p=q->next;q->next=p->next;delete p;16 、单链表与循环链表的区别单链表的头指针指向线性表第一个元素的结点；而循环链表的头指针指向表头结点，表头结点的指针域指向链表的第一个结点。单链表的最后结点的指针域为空；而循环链表最后结点的指针域指向表头结点.17 、下三角矩阵的压缩存储（以行为主压缩）（以列为主压缩）18 、对称矩阵的压缩19 、索引存储的方式顺序 索引 顺序、顺序 索引 链接、链接 索引 顺序、链接 索引 链接20 、二叉树的性质在二叉树的第k 层上，最

9、多有2k1 (k 1)个结点深度为m 的二叉树最多有2m 1个结点（深度即为层数）在任意一棵二叉树中，度为0 的结点（即叶子结点）总是比度为2 的结点多一个具有 n 个结点的二叉树，其深度至少为log 2n 1，其中 log 2 n 表示取 log2 n 的整数部分21 、满二叉树是指每层的结点都有两个子结点，满的不行不行的了，完全二叉数是指最后一层必须是从左至右的顺序断了线的，其余层都是满的。22 、前序遍历、中序遍历、后续遍历（前中后对应的是根结点的访问顺序）前序遍历：先根结点，再左再右中序遍历：先左，再根结点，再右后续遍历：先左，再右，再根结点23 、若给出三种遍历中的任意两种遍历，要求

10、写出第三种遍历，思路如下：先正确画出对应的二叉树，根据已给条件进行验证，最后写出第三种遍历24 、三种遍历的程序实现前序遍历void qian_ma()node *p;p=BT;pre(p);cout<<endl;static qian(node *p)if(p!=NULL)cout<<p->number<<” ”;qian(p->lchild);qian(p->rchild);中序遍历void zhong_ma()node *p;p=BT;zhong(p);cout<<endl;static zhong(node *p)if

11、（ p!=NULL ）zhong(p->lchild);cout<<p->number<<”;zhong(p->rchild);后续遍历void hou_ma()node *p;p=BT;hou(p);cout<<endl;static hou(node *p)if （ p!=NULL ）hou(p->lchild);hou(p->rchild);cout<<p->number<<”;25 、有序树转二叉树最最简便的方法对于有序树中的每一个结点，保留与其第一个子结点（即最左边的子结点）的链接，断开与

12、其他子结点的链接，且将其他子结点依次链接在第一个子结点的右边。26 、private 后边的叫数据成员（私有变量）， public 后边的叫成员函数，其中函数名与类名完全相同，并且无返回值（ void 也不能加）的叫构造函数，这个知识点老师说占 4 分的分值，而且老师还说一打眼就可以看出答案来的，方法我都告诉小超了呢。第三章：查找与排序1、无序表只能用顺序查找，有序表可用对分查找，分块查找时，各子表的长度可以相等，也可以互相不等，但要求后一个子表中的每一个元素均大于前一个子表中的所有元素。2、查找效率比较：顺序查找< 分块查找 < 对分查找 < 哈希表查找3、有序表的插入函数

13、void insert （int *v,int m,int n, int x）int k;if(n=m) cout<<”出现上溢错误 !”<<endl;k=n-1;while(vk>x)vk+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(i<1)|(i>n)cout<<”线性表里不存在该元素，不进行删除操作！”<<endl;for

14、(k=i;k<=n;k+)vk-1=vk;n=n-1;5、有序表的对分查找函数int search （int x,int nint i,j,k;i=1;j=n;）while(i<=j)k=(i+j)/2;if(vk-1=x) cout<<vk-1;return(k-1);if(vk-1>x)j=k-1;else i=k-1;return(-1);6、冒泡排序的原理以及程序实现原理：相邻两个元素比较大小，要是大，往后移，要是小，不要动，这样每进行一次就可以把最大的那个移到末尾了程序实现：void maopao(int *s,int n)int i,j;int tem

15、p;for(i=1;i<n;i+)for(j=0;j<n-I;j+)if(sj>sj+1)temp=sj;sj=sj+1;sj+1=temp;7、快速排序的原理以及程序实现原理：我明白快速排序了，在考试的时候，老师已经明确说了将第一个元素作为关键字，所以这样的话 ，将第一个元素设为 p （k），并将 p（ k）的值赋给 T，然后设置两个指针 i 和 j 分别指向表的起始与最后的位置。反复作以下两步：将 j 逐渐减小，并逐次比较P（ j）与T，直到发现一个P（ j） <T为止，将P（ j）移到 P（ i）的位置上。将 i 逐渐增大，并逐次比较P（ i）与T，直到发现一个P

16、（ i）>T为止，将P（i）移到 P（ j）的位置上。上述两个操作交替进行，直到指针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<j)&&(pj>=

17、T)j=j-1;if(i<j)pi=pj;i=i+1;while(i<j)&&(pi<=t)i=i+1;if(i<j)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<n;j+)t=pj;k=j-1;while(k>=0)&&(pk>t)pk+1=pk;k=k-1;pk+1=t;9、希尔排序的原理以及程序实现

18、原理：每间隔一定数量的元素之间进行比较和互换，慢慢减小这个间隔，直到间隔为1 时，进行一次插入排序就搞定了。程序实现：void shel(int *p,int n)int k,j,i;int t;k=n/2;while(k>0)for(j=k;j<=n-1;j+)t=pj;i=j-k;while(i>=0)&&(pi>t) pi+k=pi;i=i-k; pi+k=t;k=k/2;10 、简单选择排序的原理以及程序实现原理：对于长度为 n 的序列，需要扫描 n-1 遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与剩余子表的第一个元素进行互

19、换。程序实现：void select(int *p,int n)int i,j,k;int d;for(i=0;i<n-1;i+)k=i;for(j=i+1;j<n;j+)if(pi<pk)k=j;if(k!=j)d=pi;pi=pk;pk=d;11 、堆排序的原理以及程序实现这个有点复杂，你只需要记住两句话就可以啦，一是堆一定是完全二叉树，二是堆中所有根结点一定是大于其对应的叶子结点的。12 、二叉排序树的概念及特性概念：左子树上所有结点的值均小于根结点的值；右子树上所有结点的值均不小于根结点的值。 特征：中序遍历二叉排序树即可得到有序数列。13 、给定序列构造二叉排序树第

20、 1 个你就放在根结点就可以啦，然后放第二个的时候你就看如果是大于根结点的话放在右子树，如果是小于根结点的话就放左子树，整体如此，局部也是一样，最后还要检查一下哦，按照一定的顺序检查，还是很好玩的呢。14 、二叉排序树的查找方法：给你一个数，怎么在二叉排序树中找到它呢？从上往下比较呗，真的很神奇呢，啦啦啦第四章：资源管理技术1、多道程序设计：在一台处理机上并发运行多个程序2、相对地址（逻辑地址）与绝对地址概念相对地址：编写程序时使用的地址绝对地址：即为物理地址，数据存储在计算机中的地址3、虚拟存储的意义：扩大逻辑内存第五章：数据库温馨提示：该部分因为考点较为明确，所以不按照知识点进行划分，而是

21、按照考题类型进行整理。本章考题占 20 分，分为两个题型，对表的操作、对表中数据的操作。一、对表的操作例：创建学生基本信息表（学号，姓名，年龄，所在系），学号为字符类型， 8 个字符长，学号为该表关键字；姓名为字符类型， 10 个字符长；年龄为整型，可以不输入值；所在系为字符型，12 个字符长，允许不输入值CREAME TABLE S(SNO CHAR(8) PRIMARY KEY,SNAME CHAR(10) NOT NULL,AGE INT,DEPART CHAR(12);例：学生信息表 S 没有记录学生性别，修改表结构，增加“性别”列 SEX，此列为字符型，长度为 2ALTER TABLE S ADD SEX CHAR(2)例：将学生表S 姓名 SNAME 列字符长度修改为20ALTER TABLE S MODIFY (SNAME CHAR(20)；例：删除 S 表DROP TABLE S二、对表中数据的操作有如下表Emplo