计算机软件技术基础知识点储备

第一章：概述1、程序=算法+数据结构2、算法的几个基本特征：能行性确定性有穷性拥有足够的情报3、算法的复杂度主要包括：时间复杂度和空间复杂度第二章：数据结构1、逻辑结构：数据集合中各数据元素之间所固有的逻辑关系（集合结构、线性结构、树形结构、图状结构），可以看作是从具体问题抽象出来的数据模型。2、物理（存储）结构：在对数据进行处理时，各数据元素在计算机中的存储关系，可分为以下四种：顺序存储结构（存储空间连续）、链式存储结构、索引结构、散列结构3、数据结构的运算是指对数据结构中的结点进行操作的集合，包括插入、删除、更新、检索、排序等。4、数据元素是数据的基本单位5、有时数据元素可由若干个数据项（数据的属性）组成，在这种情况下，数据项组成的数据元素称为记录，数据项是具有独立含义的最小标识单位，不可分割6、顺序存储结构：通常定义一维数组来表示线性表的顺序存储空间7、顺序表的插入异常处理：（m为线性表的空间大小，n为线性表的长度=m，插入的位置为i，i表示在第i个元素之前插入）⑴当存储空间已满（即n=m）时为上溢错误，不能进行插入，算法结束；⑵当in时，认为在最后一个元素之后（即第n+1个元素之前）插入；⑶当i1时，认为在第1个元素之前插入函数的代码实现：voidinsert（int*v,intm,intn,inti,intb）{intk;if(n==m)cout”出现上溢错误!”endl;if(in)i=n+1;if(i1)i=1;for(k=n;k=i;k--){v[k]=v[k-1];v[i-1]=b;n=n+1;}}8、顺序表的删除异常处理：⑴当线性表为空（即n=0）时为下溢错误，不能进行删除，算法结束；⑵当i1或in时，认为不存在该元素，不进行删除。函数的代码实现：voiddelete(int*v,intm,intn,inti){intk;if(n==0)cout”出现下溢错误！”endl;if((i1)||(in))cout”线性表里不存在该元素，不进行删除操作！”endl;for(k=i;k=n;k++)v[k-1]=v[k];n=n-1;}9、栈（相当于一个井）的相关概念⑴先进后出（后进先出）⑵栈顶允许插入与删除⑶栈底不允许插入与删除10、队列（相对于排队买饭）的相关概念⑴先进先出⑵队尾允许插入⑶对头允许删除11、链式存储每个结点由两部分组成：数据域和指针域12、单链表的插入函数实现在包含元素x的结点前插入新元素bvoidinsert(intx,intb){node*p,*q;p=newnode;p-number=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;}13、单链表的删除函数实现删除包换元素x的结点voiddelete(intx){node*p,*q;if(head==NULL)cout”没有要删除的元素！”endl;if((head-number)==x){p=head-next;deletehead;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;deletep;}14、循环链表的插入函数实现在包含元素x的结点前插入新元素bvoidinsert(intx,intb){node*p,*q;p=newcode;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的结点voiddelete(intx){node*p,*q;q=head;while((q-next!=NULL)&&(((q-next)-number)!=x))q=q-next;if(q-next==head)cout”没有要删除的元素”endl;p=q-next;q-next=p-next;deletep;}16、单链表与循环链表的区别⑴单链表的头指针指向线性表第一个元素的结点；而循环链表的头指针指向表头结点，表头结点的指针域指向链表的第一个结点。⑵单链表的最后结点的指针域为空；而循环链表最后结点的指针域指向表头结点.17、下三角矩阵的压缩存储（以行为主压缩）（以列为主压缩）18、对称矩阵的压缩19、索引存储的方式顺序—索引—顺序、顺序—索引—链接、链接—索引—顺序、链接—索引—链接20、二叉树的性质⑴在二叉树的第k层上，最多有2k－1(k≥1)个结点⑵深度为m的二叉树最多有2m－1个结点（深度即为层数）⑶在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个⑷具有n个结点的二叉树，其深度至少为[log2n]＋1，其中[log2n]表示取log2n的整数部分21、满二叉树是指每层的结点都有两个子结点，满的不行不行的了，完全二叉数是指最后一层必须是从左至右的顺序断了线的，其余层都是满的。22、前序遍历、中序遍历、后续遍历（前中后对应的是根结点的访问顺序）前序遍历：先根结点，再左再右中序遍历：先左，再根结点，再右后续遍历：先左，再右，再根结点23、若给出三种遍历中的任意两种遍历，要求写出第三种遍历，思路如下：先正确画出对应的二叉树，根据已给条件进行验证，最后写出第三种遍历24、三种遍历的程序实现⑴前序遍历voidqian_ma(){node*p;p=BT;pre(p);coutendl;}staticqian(node*p){if(p!=NULL){coutp-number””;qian(p-lchild);qian(p-rchild);}}⑵中序遍历voidzhong_ma(){node*p;p=BT;zhong(p);coutendl;}staticzhong(node*p){if（p!=NULL）{zhong(p-lchild);coutp-number””;zhong(p-rchild);}}⑶后续遍历voidhou_ma(){node*p;p=BT;hou(p);coutendl;}statichou(node*p){if（p!=NULL）{hou(p-lchild);hou(p-rchild);coutp-number””;}}25、有序树转二叉树最最简便的方法对于有序树中的每一个结点，保留与其第一个子结点（即最左边的子结点）的链接，断开与其他子结点的链接，且将其他子结点依次链接在第一个子结点的右边。26、private后边的叫数据成员（私有变量），public后边的叫成员函数，其中函数名与类名完全相同，并且无返回值（void也不能加）的叫构造函数，这个知识点老师说占4分的分值，而且老师还说一打眼就可以看出答案来的，方法我都告诉小超了呢。第三章：查找与排序1、无序表只能用顺序查找，有序表可用对分查找，分块查找时，各子表的长度可以相等，也可以互相不等，但要求后一个子表中的每一个元素均大于前一个子表中的所有元素。2、查找效率比较：顺序查找分块查找对分查找哈希表查找3、有序表的插入函数voidinsert（int*v,intm,intn,intx）{intk;if(n==m)cout”出现上溢错误!”endl;k=n-1;while(v[k]x){v[k+1]=v[k];k=k-1;}v[k+1]=x;n=n+1;}4、有序表的删除函数voiddelete(int*v,intm,intn,inti){intk;if(n==0)cout”出现下溢错误！”endl;if((i1)||(in))cout”线性表里不存在该元素，不进行删除操作！”endl;for(k=i;k=n;k++)v[k-1]=v[k];n=n-1;}5、有序表的对分查找函数intsearch（intx,intn）{inti,j,k;i=1;j=n;while(i=j){k=(i+j)/2;if(v[k-1]==x)coutv[k-1];return(k-1);if(v[k-1]x)j=k-1;elsei=k-1;}return(-1);}6、冒泡排序的原理以及程序实现原理：相邻两个元素比较大小，要是大，往后移，要是小，不要动，这样每进行一次就可以把最大的那个移到末尾了程序实现：voidmaopao(int*s,intn){inti,j;inttemp;for(i=1;in;i++)for(j=0;jn-I;j++)if(s[j]s[j+1]){temp=s[j];s[j]=s[j+1];s[j+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（i）T为止，将P（i）移到P（j）的位置上。上述两个操作交替进行，直到指针i与j指向同一个位置（即i=j）为止，此时将T移到P（i）（即P（j））的位置上。程序实现：voidquick（int*p,intn）{intm,i;int*s;i=split(p,n);quick(p,i);s=p+（i+1）；m=n-(i+1);quick(s,m);}staticintspilt(int*p,intn){inti,j,k,l;intT;i=0;j=n-1;T=p[0];while(i!=j){while((ij)&&(p[j]=T))j=j-1;if(ij){p[i]=p[j];i=i+1;while((ij)&&(p[i]=t))i=i+1;if(ij){p[j]=p[i];j=j-1;}}}p[i]=T;return(i);}8、简单插入排序的原理及程序实现原理：就是从第二个元素开始，往前插到它应该在的位置就好啦，还是蛮实用的嘛程序实现：voidinsert(int*p,intn){intj,k;intt;for(j=1;jn;j++){t=p[j];k=j-1;while((k=0)&&(p[k]t)){p[k+1]=p[k];k=k-1;}p[k+1]=t;}}9、希尔排序的原理以及程序实现原理：每间隔一定数量的元素之间进行比较和互换，慢慢减小这个间隔，直到间隔为1时，进行一次插入排序就搞定了。程序实现：voidshel(int*p,intn){intk,j,i;intt;k=n/2;while(k0){for(j=k;j=n-1;j++){t=p[j];i=j-k;while((i=0)&&(p[i]t)){p[i+k]=p[i];i=i-k;}p[i+k]=t;}k=k/2;}}10、简单选择排序的原理以及程序实现原理：对于长度为n的序列，需要扫描n-1遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与剩余子表的第一个元素进行互换。程序实现：voidselect(int*p,intn){inti,j,k;intd;for(i=0;in-1;i++){k=i;for(j=i+1;jn;j++)i