文档介绍：计算机软件技术基础知识点储
备
第一章：归纳
1、程序=算法+数据构造
2、算法的几个基本特点：能行性确立性有穷性拥有足够的情报
3、算法的复杂度主要包含：时间复杂度和空间复&(((q->next)->number)!=x))
q=q->next;
if(q->next==NULL)
cout<<
”没有要删除的元素！
”<<endl;
p=q->next;
q->next=p->next;
deletep;
}
、循环链表的插入函数实现
在包含元素x的结点前插入新元素b
voidinsert(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;
}
、循环链表的删除函数实现
删除包含元素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;
}
、单链表与循环链表的差别
⑴单链表的头指针指向线性表第一个元素的结点；而循环链表的头指针指向表头结点，表头结点的指针域指向链表的第一个结点。
⑵单链表的最后结点的指针域为空；而循环链表最后结点的指针域指向表头结点.
、下三角矩阵的压缩储藏
（以行为
（以列为主
、对称矩阵的压缩
、索引储藏的方式
序次—索引—序次、序次—索引—链接、链接—索引—序次、链接—索引—链接
、二叉树的性质
⑴在二叉树的第k层上，最多有2k－1(k≥1)个结点
⑵深度为
m的二叉树最多有
2m－1
个结点（深度即为层数）
⑶在任意一棵二叉树中，度为
0的结点（即叶子结点）总是比度为
2的结点多一个
⑷拥有
n个结点的二叉树，其深度最少为
[log
2n]
＋1，此中[log
2n]
表示取
log
2n
的整
数部分
、满二叉树是指每层的结点都有两个子结点，满的不能够不能够的了，完整二叉数是指最后一层一定是从左至右的序次断了线的，其余层都是满的。
、前序遍历、中序遍历、后续遍历（前中后对应的是根结点的接见序次）前序遍历：先根结点，再左再右
中序遍历：先左，再根结点，再右后续遍历：先左，再右，再根结点
、若给出三种遍历中的任意两种遍历，要求写出第三种遍历，思路以下：先正确画出对应的二叉树，依据已给条件进行考据，最后写出第三种遍历
、三种遍历的程序实现
⑴前序遍历
voidqian_ma( )
{
node*p;
p=BT;
pre(p);
cout<<endl;
}
staticqian(node*p)
{
if(p!=NULL)
{
cout<<p->number<<””;
qian(p->lchild);
qian(p->rchild);
}
}
⑵中序遍历
voidzhong_ma( )
{
node*p;
p=BT;
zhong(p);
cout<<endl;
}
staticzhong(node*p)
{
if（p!=NULL）
{
zhong(p->lchild);
cout<<p->number<<””;
zhong(p->rchild);
}
}