华师大数据结构复习题课件

数据结构学位考试复习提纲2013年10月考试时间90分钟

第一部分题型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数据结构学位考试复习提纲考试时间90分钟第一部分1、四种基本逻辑结构是：____？2、算法区别于程序的主要地方是____。3、算法评价一般考虑四个方面：____、____、____、____；其中在数据结构里主要考虑____。4、时间和空间性能往往是一对矛盾吗？5、空间耗费包括代码部分吗？6、程序段时间复杂性的简单判断？

7、算法的时间复杂性越高，则从计算机速度提高得到的收益就越大吗？第二部分复习提纲(不分题型)1、四种基本逻辑结构是：____？第二部分复习提纲(不分题1、顺序表和链表哪个可以按序号随机存取？按值能否随机存取？2．顺序表和链表中的逻辑关系分别用什么表示？3．链表中结点物理地址一定不连续吗？4、寻找单链表中当前结点的后继和前趋的时间复杂度分别是____。5、单链表中插入、删除结点的执行步骤？6、何谓存储密度？顺序表、链表分别如何？L…

a1

a2an1、顺序表和链表哪个可以按序号随机存取？按值能否随机存取？L7、例：将顺序表中所有负数移动到表的前端，要求移动次数小。解：双向扫描：从前向后找一个正数，再从后向前找一个负数，然后交换两者位置。复杂性为O（n）。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−−;}}}+--+--++-+--+-7、例：将顺序表中所有负数移动到表的前端，要求移动次数小。+8、例：删除顺序表中所有的正数，要求移动次数小。解：搜索顺序表，对每一个正数，先不删除，而是累计当前正数个数s，于是，对每个非正数，将它一次性前移s位。算法复杂性为O（n）。voiddels(sqlist*L){ints,i;s=0; //正数计数器

for(i=0;i<L->n;i++)if(L->data[i]>0s++; //累计当前正数

elseif(s>0)L->data[i-s]=l->data[i];//向前移动s位

L->n=L->n-s; //调整表长}+--+--++-+--+-8、例：删除顺序表中所有的正数，要求移动次数小。+--1、什么问题需要用栈或队列来描述？2、怎样克服假溢出？3、已知进栈序列，怎样判断哪些出栈序列可能或不可能？4、C语言中，串的存储方式是_____。5、空串、空白串、串相等、模式匹配含义？6、strcmp()、strlen()、strcat()、strcpy()函数功能？1、什么问题需要用栈或队列来描述？1、数组的基本运算是读、写。没有插入删除等运算2、为什么说数组是随机存储结构？3、对称矩阵、稀疏矩阵，谁压缩存储后还可以随机存取？4、十字链表中的结点需存储非零元素的哪五个信息？5、广义表的分类，图形表示与识别？6、广义表不仅是线性表的推广，也是树的推广。7、用head()和tail()函数在广义表A=(a,(x,y,z),b)中取出原子b。1、数组的基本运算是读、写。没有插入删除等运算1、3个结点可构成____个不同形态的二叉树。2、二叉树的先根遍历序列和后根遍历序列相同，则该二叉树的特征是____。3、能否有二叉树，其任何遍历次序都相同？4、某完全二叉树有5个叶子，则其结点总数为____。(10或9，一般2n或2n-1)5、某完全二叉树的第5层只有6个结点，则其叶子结点数是____。6、树的先根遍历需要借助__来实现、层次遍历需要借助__来实现。(栈,队列)7、线索二叉树上，求结点的(遍历)前趋和后继时可利用线索得到，是否就不必进行遍历了？8、线索二叉树中，线索的含义？9、哈夫曼树的特点？1、3个结点可构成____个不同形态的二叉树。10、如何画中序、先序、后序线索二叉链表（线索二叉树）？解：以中序线索二叉链表为例，下列二叉树的中序线索二叉链表如图所示。详细过程见课本。ABCDEFCBDEA00000F1111111NULLNULL中序：DBEFACABCDEFNULLNULL中序线索二叉树中序线索二叉链表10、如何画中序、先序、后序线索二叉链表（线索二叉树）？AB11．如何由先序＋中序、后序＋中序还原出二叉树？解：①对前序序列，序列的第一个点就是整个二叉树的根；②对后序序列，序列的最后一个点就是整个二叉树的根；③对中序序列，以根为界，序列的前一部分为根的左子树，后一部分为根的右子树；并且，前一部分是左子树的中序序列，后一部分是右子树的中序序列。若给定了前序和中序序列，反复利用上面的①和③，即由前序序列找到根，由中序序列得到左、右子树；再对每个子树由前序序列找到子树的根，由中序序列得到子树的左、右子树，等等类推，每次得到一个点(子树的根)，从而逐渐还原和构造出该二叉树。11．如何由先序＋中序、后序＋中序还原出二叉树？例由先根和中根序列构造二叉树G先根序列中根序列ABHFDECKGHBDFAEKCHFDKGBCEA后根+中根呢？例由先根和中根序列构造二叉树G先根序列中根序列ABHFD12、例：判断二叉树是否所有结点都为正数。解：设二叉树根指针类型为bitree，函数名为detect，函数返回判断结果intdetect(bitreet){if(t==NULL)return1; //空树返回真，递归出口if(t->data<=0)return0; //根不为正数，返回假returndetect(t->lchild)&&detect(t->rchild); //由左右子树共同决定真或假}12、例：判断二叉树是否所有结点都为正数。13、例：判断是否二叉树t否满足小根堆的特点。解：设二叉树结点类型为bitree，函数名为detect，函数返回判断结果。intdetect(bitreet){if(t==NULL)return1; //空树返回真

if((t->lchild!=NULL&&t->lchild->data<t->data)||(t->rchild!=NULL&&t->rchild->data<t->data))return0;returndetect(t->lchild)&&detect(t-rchild);}13、例：判断是否二叉树t否满足小根堆的特点。1．n个顶点及e条边的无向图，邻接表中的边结点数为____，邻接矩阵中1的个数为___。若是有向图呢？2、n个顶点的无向图、有向图，边数范围分别是多少？3、图的DFS遍历类似树的____遍历，是其推广。4、在邻接矩阵和邻接表上进行BFS或DFS遍历时，时间复杂性分别为多少？5、某图有3个连通分量，则要访问所有顶点时，必须调用__次DFS遍历算法。6、若有向图的邻接矩阵中，主对角线以下的元素均为零，则该图可拓扑排序吗？7、拓扑排序可用以分析工程能否顺利进行。8、何谓关键路径？0101010101010111010001100V11V22V33V44……m24∧1∧3∧1．n个顶点及e条边的无向图，邻接表中的边结点数为____1．各种排序算法的复杂度如何？(好、坏、平均?)(1)、哪些最好和最坏时间复杂度都为O(nlog2n)？(2)、趟数最少和最多情况如何？(3)、哪些空间复杂性为O(n)？2、初始序列基本有序时，哪些排序方法好？3、n个数据直接插入排序，可能的最少比较次数是____。4、希尔排序的增量序列中，最后一个增量为____。5、堆的定义？6、基数排序的排序趟数？练习：(49,38,13,76,65,97,27,49)7．各种排序方法步骤如何？（会写每趟结果，冒泡、选择、快速排序等）1．各种排序算法的复杂度如何？(好、坏、平均?)练习：(491、顺序查找法既可用于顺序表，也可用于链表吗？2、二分查找对