华师网络教育_本科_数据结构_期末复习资料

《华师网络教育_本科_数据结构_期末复习资料》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、华师网络教育_本科_数据结构_期末复习资料数据结构　期末考试　复习提纲2013年6月题型1．单选题：2分×15=30分　概述1、线性表2、栈队串2、数组广义表1、树3、图2、排序2、查找22．判断题：2分×10=20分　概述1、线性表1、栈队串1、数组广义表1、树2、图2、排序1、查找13．填空题：2分×11=22分　概述1、线性表1、栈队串1、数组广义表2、树2、图2、排序1、查找14．应用题：8分×2=16分　树1、排序15．程序题：6分×2=12分　二叉链表1、顺序表1第1章概论1、四种基本

2、存储结构是：顺序、链式、索引、散列；其中最基本的是：顺序、链式。2、若结点的存储地址可以反映数据间的逻辑关系，则相应的存储结构应为顺序存储。3、若结点的存储地址与结点内容有某种确定的关系，则相应的存储结构应为散列存储。4、一种逻辑结构只能对应一种存储结构吗？错5、数值型和非数值型数据、原子类型和结构类型、加工型和引用型运算含义？数据可分为数值型和非数值型数据类型可分为原子类型和结构类型运算可分为加工型和引用型6、数据结构可分为逻辑结构和非逻辑结构吗？错7、算法的正确性，一般不进行形式化的证明，而是

3、用测试来验证。对8、运算定义在逻辑结构上，算法定义在存储结构上；运算指出"做什么"，算法指出怎么做。9、线性结构可以顺序存储，也可以链式存储。对非线性结构只能链式存储吗？错10、程序设计的实质是：数据的表示和数据处理，或者说，程序=数据结构＋算法。第2章线性表：1、顺序表、链表优缺点？逻辑关系如何表示？顺序表是用数组实现的，链表是用指针或游标实现的。顺序表有三个优点：(1)方法简单，各种高级语言中都有数组，容易实现。(2)不用为表示结点间的逻辑关系而增加额外的存储开销。(3)顺序表具有按元素序号随

4、机访问的特点。但它也有两个缺点：(1)在顺序表中做插入删除操作时，对n较大的顺序表效率低。(2)需要预先分配足够大的存储空间，估计过大将造成空间浪费；预先分配过小，又会造成溢出。链表的优缺点恰好与顺序表相反。顺序表中节点间的逻辑关系由其物理位置反映，链表用额外的空间（即指针域或游标域）来表示逻辑关系。2、在顺序表中插入和删除结点时总要移动其它结点。错3、顺序表插入和删除时，移动元素的个数与该元素的位置有关。对4、顺序表中按值查找、按序号查找运算的复杂性分别为o(n)、o(1)。5、在链表的结点中，

5、数据元素所占的存储量和整个结点所占的存储量之比称作存储密度。6、链表的结点地址一定不连续。错（可连续也可不连续）7、用尾指针表示单循环链表的好处是找头找尾都方便。8、单链表中结点*p有且仅有一个后继结点的条件是p->next!=null&p->next->next==null。9．例：将顺序表中所有负数移动到表的前端，要求移动次数小。解：双向扫描：从前向后找一个正数，再从后向前找一个负数，然后交换两者位置。复杂性为O（n）。voidmoves(sqlist*L){inti,j;datatypex;

6、i=1;j=L->n;//设数组下标从1开始while(idata[i]<0&&idata[j]>=0&&idata[i];L->data[i]=L->data[j];L->data[j]=x;i++;j--;}}}10．例：删除顺序表中所有的正数，要求移动次数小。解：搜索顺序表，对每一个正数，先不删除，而是累计当前正数个数s，于是，对每个非正数，将它一次性

7、前移s位。算法复杂性为O（n）。voiddels(sqlist*L){ints,i;s=0;//正数计数器for(i=0;in;i++){if(L->data[i]>0)s++;//累计当前正数elseif(s>0)L->data[i-s]=l->data[i];//非整数向前移动s位}L->n=L->n-s;//调整表长}第３章栈、队列和串1、栈和队列的共同特点是运算受限的线性表。2、栈操作的原则是后进先出或先进后出。3、设进栈顺序为A，B，C，D，E和F，出栈顺序为C，E，D，F，B，

8、A，则栈的容量至少为4。4、若进栈序列为a,b,c，则通过入出栈操作能得到的a,b,c的不同排列个数为5。5、设入栈序列为A,B,C,D，则可能的出栈序列有哪些？（哪些不可能？）6、顺序栈在进行入栈运算时，可能发生栈的上溢，在进行出栈运算时，可能发生栈的下溢。7、顺序栈、链栈上进行进栈操作时，谁可不需判断栈满？链栈8、链栈一般不需要头结点，因为无头结点的链栈运算也很方便。对9、设链栈结点结构为(data,next)，top为栈顶指针，当执行入栈操作时需执行下列语句：p=newnod