《计算机软件技术基础知识点储备》由会员分享，可在线阅读，更多相关《计算机软件技术基础知识点储备（17页珍藏版）》请在金锄头文库上搜索。
1、计算机软件技术基础知识点储备第一章：概述1 、程序 = 算法 + 数据结构2 、算法的几个基本特征：能行性确定性有穷性拥有足够的情报3 、算法的复杂度主要包括：时间复杂度和空间复杂度第二章：数据结构1 、逻辑结构：数据集合中各数据元素之间所固有的逻辑关系（集合结构、线性结构、树形结构、图状结构），可以看作是从具体问题抽象出来的数据模型。2 、物理（存储）结构：在对数据进行处理时，各数据元素在计算机中的存储关系，可分为以下四种：顺序存储结构（存储空间连续）、链式存储结构、索引结构、散列结构3 、数据结构的运算是指对数据结构中的结点进行操作的集合，包括插入、删除、更新、检索、排序等。4 、数据元素
2、是数据的基本单位5 、有时数据元素可由若干个数据项（数据的属性）组成，在这种情况下，数据项组成的数据元素称为记录，数据项是具有独立含义的最小标识单位，不可分割6 、顺序存储结构：通常定义一维数组来表示线性表的顺序存储空间7 、顺序表的插入异常处理：（ m 为线性表的空间大小， n 为线性表的长度 n时，认为在最后一个元素之后（即第n+1 个元素之前）插入；当 i1时，认为在第 1 个元素之前插入函数的代码实现：voidinsert（ int*v,intm,intn,int i, int b）int k;if(n=m)cout”出现上溢错误 !”n)i=n+1;if(i=i;k-)vk=vk-1
3、;vi-1=b;n=n+1;8 、顺序表的删除异常处理： 当线性表为空（即 n=0 ）时为下溢错误，不能进行删除，算法结束；当 in时，认为不存在该元素，不进行删除。函数的代码实现：void delete(int *v, int m,int n, int i)intk;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-n
4、ext!=NULL)&(q-next)-number)!=x)q=q-next;p-next=q-next;q-next=p;13 、单链表的删除函数实现删除包换元素x 的结点voiddelete(int x)node *p,*q;”没有要删除的元素！”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 、循环链表的插入函数实现在
5、包含元素x 的结点前插入新元素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 的结点voiddelete(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-nex
6、t=p-next;delete p;16 、单链表与循环链表的区别单链表的头指针指向线性表第一个元素的结点；而循环链表的头指针指向表头结点，表头结点的指针域指向链表的第一个结点。单链表的最后结点的指针域为空；而循环链表最后结点的指针域指向表头结点.17 、下三角矩阵的压缩存储（以行为（以列为主18 、对称矩阵的压缩19 、索引存储的方式顺序 索引 顺序、顺序 索引 链接、链接 索引 顺序、链接 索引 链接20 、二叉树的性质在二叉树的第k 层上，最多有2 k 1(k 1)个结点深度为m 的二叉树最多有2 m 1个结点（深度即为层数）在任意一棵二叉树中，度为0 的结点（即叶子结点）总是比度为2
7、的结点多一个具有n 个结点的二叉树，其深度至少为log2 n1 ，其中 log2 n表示取log2 n的整数部分21 、满二叉树是指每层的结点都有两个子结点，满的不行不行的了，完全二叉数是指最后一层必须是从左至右的顺序断了线的，其余层都是满的。22 、前序遍历、中序遍历、后续遍历（前中后对应的是根结点的访问顺序）前序遍历：先根结点，再左再右中序遍历：先左，再根结点，再右后续遍历：先左，再右，再根结点23 、若给出三种遍历中的任意两种遍历，要求写出第三种遍历，思路如下：先正确画出对应的二叉树，根据已给条件进行验证，最后写出第三种遍历24 、三种遍历的程序实现前序遍历voidqian_ma()no
8、de*p;p=BT;pre(p);coutendl;staticqian(node *p)if(p!=NULL)coutnumberlchild);qian(p-rchild);中序遍历voidzhong_ma()node*p;p=BT;zhong(p);coutlchild);coutnumberrchild);后续遍历voidhou_ma()node*p;p=BT;hou(p);coutlchild);hou(p-rchild);coutnumber”;25 、有序树转二叉树最最简便的方法对于有序树中的每一个结点，保留与其第一个子结点（即最左边的子结点）的链接，断开与其他子结点的链接，且将
9、其他子结点依次链接在第一个子结点的右边。26 、private 后边的叫数据成员（私有变量）， public 后边的叫成员函数，其中函数名与类名完全相同，并且无返回值（ void 也不能加）的叫构造函数，这个知识点老师说占 4 分的分值，而且老师还说一打眼就可以看出答案来的，方法我都告诉小超了呢。第三章：查找与排序1 、无序表只能用顺序查找，有序表可用对分查找，分块查找时，各子表的长度可以相等，也可以互相不等， 但要求后一个子表中的每一个元素均大于前一个子表中的所有元素。2 、查找效率比较：顺序查找 分块查找 对分查找 哈希表查找3 、有序表的插入函数voidinsert（ int*v,intm,intn, int x）int k;if(n=m)cout”出现上溢错误!”x)vk+1=vk;k=k-1;vk+1=x;n=n+1;4 、有序表的删除函数
