数据结构复习资料 ppt课件.ppt

《数据结构复习资料 ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、总复习考试类型选择题填空题简答题编程题绪论部分数据结构中逻辑结构与物理结构的区别时间复杂度for(i=0;i

2、域:数据域Data和指针域Link存储结构：链式存储结构特点：存储单元可以不连续。存取方式：顺序存取。链表结构（重点)datalinkNode存放数据元素值直接前驱或直接后继结点的地址（指针）链表结点插入和删除插入和删除不需要移动大量元素顺序存取单链表的插入在链表中插入一个元素的示意图如下：xsbapabp插入步骤（即核心语句）：Step1：s->next=p->next;Step2：p->next=s；p->nexts->next元素x结点应预先生成：S=(LinkList)malloc(m);S->data=x;S->next=p->next单链表的删除在链

3、表中删除某元素的示意图如下：cabp删除步骤（即核心语句）：q=p->next;//保存b的指针，靠它才能指向cp->next=q->next;//a、c两结点相连free(q)；//删除b结点，彻底释放p->next思考：省略free(q)语句行不行？(p->next)->next××1、填空题：1）在顺序表中插入和删除一个元素，需要平均移动个元素，具体移动的元素个数与有关。2）顺序表中逻辑上相邻的元素的物理位置紧邻。单链表中逻辑上相邻的元素的物理位置紧邻。3）在单链表中，除了首元结点外，任一结点内的存储位置由指示。4）在单链表中，设置头结点的作用是。栈和队列

4、栈和队列的特点栈的入栈出栈顺序设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，bA、D可以（B、C不行）。答：一、数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)循环队列的操作少使用一个元素空间判空条件：front==rear判满条件：(rear+1)%M==front入队列：rear=(rear+1)%M出队列：front=(fron

5、t+1)%MJ4J5J6012345rearfrontJ8J7练习一个队列的入队序列是1，2，3，4，则出队顺序是【1】A4,3,2,1B1,2,3,4C1,4,3,2D3,2,4,1判定一个队列QU（最多MaxSize个元素）为空的条件AQU>rear-QU->front=MaxSizeBQU->rear-QU->front-1=MaxSizeCQU->front==QU->rearD、QU->front==QU->rear+1Bcz判定一个队列QU（最多MaxSize个元素）为满的条件A、QU>rear-QU->front=MaxSizeB、QU->rear

6、-QU->front-1=MaxSizeC、QU->front==QU->rearD、QU->front==QU->rear+1A循环顺序队列中是否可以插入下一个元素，【2】A、与队头指针和队尾指针值有关B、与队头指针有关，与队尾指针值无关C、只与数组大小有关，与队头指针和队尾指针值无关D、与曾经进行过多少次插入操作有关(rear+1)%M=frontA判断一个循环队列QU（最多元素为MaxSize)为空的条件【1】A、QU->front==QU->rearB、QU->front!=QU->rearC、QU->front==(QU->rear+1)%MaxSiz

7、eD、QU->front!=(QU->rear+1)%MaxSize判断一个循环队列QU（最多元素为MaxSize)为空的条件【1】A、QU->front==QU->rearB、QU->front!=QU->rearC、QU->front==(QU->rear+1)%MaxSizeD、QU->front!=(QU->rear+1)%MaxSizeAC树和二叉树性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)。深度为k的二叉树至多有2k-1个结点(k≥1）性质3对任何一棵二叉树T，如果其终端结点数为n0，而其度为2的结点数为n2,则n0=n2+1。练习一棵

8、二叉树中，度为0的结点个