《计算机软件技术基础知识点储备》由会员分享，可在线阅读，更多相关《计算机软件技术基础知识点储备（16页珍藏版）》请在金锄头文库上搜索。
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;if(n=m) cout”出现上溢错误!”n) i=n+1;if(i=i;k-)vk=vk-1;vi-1=b;n=n+1;8、顺序表的删除异常处
3、理： 当线性表为空（即n=0）时为下溢错误，不能进行删除，算法结束； 当in时，认为不存在该元素，不进行删除。函数的代码实现：void delete(int *v, int m,int n, int i)int k;if(n=0) cout”出现下溢错误！”endl;if(in) cout”线性表里不存在该元素，不进行删除操作！”endl;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)
4、!=x)q=q-next;p-next=q-next;q-next=p;13、单链表的删除函数实现删除包换元素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的结点前插
5、入新元素bvoid insert(int x,int b)node *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=head) cout”没有要删除的元素”next;q-next=p-next;d
6、elete p;16、单链表与循环链表的区别单链表的头指针指向线性表第一个元素的结点；而循环链表的头指针指向表头结点，表头结点的指针域指向链表的第一个结点。单链表的最后结点的指针域为空；而循环链表最后结点的指针域指向表头结点.17、下三角矩阵的压缩存储（以行为主压缩）（以列为主压缩）18、对称矩阵的压缩19、索引存储的方式顺序索引顺序、顺序索引链接、链接索引顺序、链接索引链接20、二叉树的性质在二叉树的第k层上，最多有2k1(k1)个结点深度为m的二叉树最多有2m1个结点（深度即为层数）在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个具有n个结点的二叉树，其深度至少为lo
7、g2n1，其中log2n表示取log2n的整数部分 21、满二叉树是指每层的结点都有两个子结点，满的不行不行的了，完全二叉数是指最后一层必须是从左至右的顺序断了线的，其余层都是满的。22、前序遍历、中序遍历、后续遍历（前中后对应的是根结点的访问顺序）前序遍历：先根结点，再左再右中序遍历：先左，再根结点，再右后续遍历：先左，再右，再根结点23、若给出三种遍历中的任意两种遍历，要求写出第三种遍历，思路如下：先正确画出对应的二叉树，根据已给条件进行验证，最后写出第三种遍历24、三种遍历的程序实现前序遍历void qian_ma()node *p;p=BT;pre(p);coutendl;static
8、 qian(node *p)if(p!=NULL)coutnumberlchild);qian(p-rchild);中序遍历void zhong_ma()node *p;p=BT;zhong(p);coutlchild);coutnumberrchild);后续遍历void hou_ma()node *p;p=BT;hou(p);coutlchild); hou(p-rchild);coutnumber” ”;25、有序树转二叉树最最简便的方法对于有序树中的每一个结点，保留与其第一个子结点（即最左边的子结点）的链接，断开与其他子结点的链接，且将其他子结点依次链接在第一个子结点的右边。26、pr
9、ivate后边的叫数据成员（私有变量），public后边的叫成员函数，其中函数名与类名完全相同，并且无返回值（void也不能加）的叫构造函数，这个知识点老师说占4分的分值，而且老师还说一打眼就可以看出答案来的，方法我都告诉小超了呢。第三章：查找与排序1、无序表只能用顺序查找，有序表可用对分查找，分块查找时，各子表的长度可以相等，也可以互相不等，但要求后一个子表中的每一个元素均大于前一个子表中的所有元素。2、查找效率比较：顺序查找分块查找对分查找哈希表查找3、有序表的插入函数void insert（int *v,int m,int n, int x）int k;if(n=m) cout”出现上溢
10、错误!”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(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;while(i=j)k=(i+j)/2;if(vk-1=x) coutx) j=k-1;else i=k-1;return(-1);6
11、、冒泡排序的原理以及程序实现原理：相邻两个元素比较大小，要是大，往后移，要是小，不要动，这样每进行一次就可以把最大的那个移到末尾了程序实现：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;7、快速排序的原理以及程序实现原理：我明白快速排序了，在考试的时候，老师已经明确说了将第一个元素作为关键字，所以这样的话 ，将第一个元素设为p（k），并将p（k）的值赋给T，然后设置两个指针i和j分别指向表的起始与最后的位置。反复作以下两步：将j逐渐减小，并逐次比较P（j）与T，直到发现一个P（j）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)
