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

数据结构期末考试复习提纲20136月题型1分×15=30分21222分×10=20分11213分×11=22分12214分×2=16分树1、排序15分×2=12二叉链表1、顺序表11章概论1。2。3、若结点的存储地址与结点内容有某种确定的关系，则相应的存储结构应为散列存储。4、一种逻辑结构只能对应一种存储结构吗？错5、数值型和非数值型数据、原子类型和结构类型、加工型和引用型运算含义？数据可分为数值型和非数值型数据类型可分为原子类型和结构类型运算可分为加工型和引用型6、数据结构可分为逻辑结构和非逻辑结构吗？错7、算法的正确性，一般不进行形式化的证明，而是用测试来验证。对8。9、线性结构可以顺序存储，也可以链式存储对 非线性结构只能链式存储吗错10、程序设计的实质是：数据的表示和数据处理，或者说，程序=数据结构＋算法。2章线性表：1、顺序表、链表优缺点？逻辑关系如何表示？顺序表是用数组实现的，链表是用指针或游标实现的。顺序表有三个优点：方法简单，各种高级语言中都有数组，容易实现。不用为表示结点间的逻辑关系而增加额外的存储开销。但它也有两个缺点：在顺序表中做插入删除操作时，对n较大的顺序表效率低。需要预先分配足够大的存储空间，估计过大将造成空间浪费造成溢出。链表的优缺点恰好与顺序表相反。（即指针域或游标域来表示逻辑关系。2、在顺序表中插入和删除结点时总要移动其它结点。错3、顺序表插入和删除时，移动元素的个数与该元素的位置有关。对4、顺序表中按值查找、按序号查找运算的复杂性分别为o(n)、o(1)。5、在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作存储密度。6、链表的结点地址一定不连续。错（可连续也可不连续）7、用尾指针表示单循环链表的好处是找头找尾都方便。8*p有且仅有一个后继结点的条件是p->next!=null&。9．例：将顺序表中所有负数移动到表的前端，要求移动次数小。为（。voidmoves(sqlist*L){inti,j;datatypex;i=1;j=L->n; //1开始while(i<j){while(L->data[i]<0&&i<j)i++;//从前向后找正数while(L->data[j]>=0&&i<j)j--;//从后向前找负数if(i<j){//交换x=L->data[i];L->data[i]=L->data[j];L->data[j]=x;i++;j--;}}}10．例：删除顺序表中所有的正数，要求移动次数小。解：搜索顺序表，对每一个正数，先不删除，而是累计当前正数个数数，将它一次性前移s位。算法复杂性为（。voiddels(sqlist*L){ints,i;s=0; //for(i=0;i<L->n;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、设进栈顺序为F，出栈顺序为4。4、若进栈序列为a,b,c，则通过入出栈操作能得到的a,b,c的不同排列个数为5。5、设入栈序列为A,B,C,D，则可能的出栈序列有哪些？（哪些不可能？）6、顺序栈在进行入栈运算时，可能发生栈的上溢，在进行出栈运算时，可能发生栈的下溢。7、顺序栈、链栈上进行进栈操作时，谁可不需判断栈满？链栈8、链栈一般不需要头结点，因为无头结点的链栈运算也很方便。对9pnode;p->data=x;p->next=top;top->p_4章多维数组和广义表1．数组的基本运算。读、写，没有插入删除运算2、多维数组之所以有行优先顺序和列优先顺序两种存储方式是因。数组的元素处行和列两个关系中3、数组各元素在内存中连续存放，故前后相邻的两元素物理地址相差为1或-1。对4、多维数组可以顺序储存，所以实际上是一种顺序表？错5CA[20][10]212000，则元素A[8][9]2000+89*2。6数组A[1..8][1..10]中每个元素占3个单元从首地址SA开始存放若该数组按列存放，则元素A[8][5]的地址是SA+39*3 。7A[1..n][1..n])A[i][j]对应位置B[k]，则k=i*(i-1)/2+j。8、稀疏矩阵常用的压缩存储方法有两种，即十字链表、三元组表。9、十字链表中的结点需存储非零元素的五个信息：行号、列号、值、行指针、列指针。10、稀疏矩阵的三元组表示中，三元组是指非零元素的行号、列号和值三项。5章树型结构1、某树所有结点的度数之和为100，则树中边数为100。2、树上每个结点都可有多个孩子、一个双亲吗？错（根无）3、3个结点可构成5个不同形态的二叉树。4、何谓完全二叉树？（会识别）P915、二叉树必须有结点的度为2吗错 可否所有点的度都小于2？对6、树的度是指树中结点的最大度数，所以二叉树的度为2。错7、某完全二叉树有7个叶子，则其结点总数（13或14,即2n-1或2n）8、若二叉树中没有度为1的结点，则为满二叉树？错9、满二叉树是一种特殊的完全二叉树吗？对10、深度为k的二叉树，结点数至多为2k-1，结点数至少为k。11、深度为k的二叉树，叶子数至多为2k-1，叶子数至少为1。12、高度为n、结点数也为n的二叉树，共有2n-1棵。(即等于满二叉树最底层叶子数)13、200个结点的二叉树，深度至多为200，深度至少为8。14、在深度为7的二叉树中，第5层上的结点数最少为_1_，最多为16(24)_。15、有无可能某二叉树的任何遍历次序都相同？有（一个节点或空树）16、某二叉树的先根遍历序列和后根遍历序列相同，则该二叉树的特征是一个节点或空树。17、二叉树、森林相互转换。P117如何画中序、先序、后序线索二叉链表（线索二叉树解：以中序线索二叉链表为例，下列二叉树的中序线索二叉链表如图所示。详细过程见课本。例：求二叉树高度。解：设二叉树结点类型为bitree，函数名为high，函数返回高度。inthigh(bitreet){intL,R;if(t==NULL)return0; //0，递归出口L=high(t->lchild);R=high(t->rchild)

求左子树高度求右子树高度return(L>R?L:R)+1; =+1}1的结点数。解：设二叉树结点类型为bitree，函数名为sum1，函数返回结点数。intsum1(bitreet){intL,R;if(t==NULL)return0;L=sum1(t->lchild);R=sum1(t->rchild)

//当前树为空，递归出口求左子树中相应结点数求右子树中相应结点数if((t->lchild==NULL&&t->rchild!=NULL)||(t->lchild!=NULL&&t->rchild==NULL))//当前结点度为也1returnL+R+1;//度1结点数=左子树中度1结点数+右子树中度1结点数+1elsereturnL+R;}22．例：求二叉树中度为2的结点数。解：设二叉树结点类型为bitree，函数名为sum2，函数返回结点数。intsum2(bitreet){intL,R;if(t==NULL)return0;L=sum2(t->lchild);R=sum2(t->rchild)

//当前树为空，递归出口求左子树中相应结点数求右子树中相应结点数if(t->lchild!=NULL&&t->rchild!=NULL)//当前结点度为也2returnL+R+1;//度2结点数=左子树中度2结点数+右子树中度2结点数+1elsereturnL+R;}第6章图1、n个顶点的有向图，最少0 条边；最多_n(n-1) 条边。2、n个顶点的无向图，最少0 条边，最多条边。3、某无向图有28条边，则其顶点数最少8 。4、某图所有顶点的度数之和为200，则边数条。5、n个顶点的强连通图若只有n条边，则该有向图的形状是环。6、n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。对7、有向图出度、入度关系？出度总和=入度总和8、含n个顶点的无向图，其邻接矩阵中非零元素的个数就是图中的边数。错（2倍）9、在n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素个数为2e_。10n个顶点和e_o(n)_（求入读看列数）11、有向图边数=邻接矩阵中1的个数；也=邻接表中的边表结点数。正确12、无向图边数=邻接矩阵中1的个数的一半；也=邻接表中的边表结点数的一半。正确7章排序1、内排序是指数据全部在内存中进行排序，稳定性是指数据中相同关键字的数据排序前后相对顺序不改变。2、可以将排序算法分为：插入排序、交换排序、选择排序、归并排序、分配排序。3、“就地排序”是指排序算法辅助空间的复杂度为O(1)。4．各种排序算法的结果总结。(好、坏、平均性能？稳定性？)5、不稳定的排序算法没有实际的应用价值吗？错6、谁的空间复杂性为O(logn)？快速排序27、时间复杂性为O(nlogn)且空间复杂性为O(1)的排序方法是堆排序。28、Shell排序稳定吗？（不稳定）其时间性能与增量序列的选取关系大不大？对各种排序方法步骤（会写每趟结果，归并、小根堆、直选、快速、希尔练习：(49,38,13,76,65,97,27,49)8章查找表1、查找表的逻辑结构是集合。2、哪些方法属于静态查找、动态查找？（会区分）二者根本区别？有没有修改数据结构,如果结构不变属于静态查找(施加在其上的操作不同)3、对长度为100的顺序表，在等概率情况下，查找成功时的平均查找长度为在找不成功时的平均查找长度50.5、100(或101)41055个元素的概率相同，均为3/40，则查找任一元素的平均查找长度为()。1*1/8+2*1/8+3*1/8+