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

1、数据结构数据结构学位考试学位考试复习提纲复习提纲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、顺序表11、四种基本逻辑结构是：_？2、算法区别于程序的主要地方是_。3、算法评价一般考虑四个方面：_、_、_、_；其中在数据

2、结构里主要考虑_。4、时间和空间性能往往是一对矛盾吗？5、空间耗费包括代码部分吗？6、程序段时间复杂性的简单判断？7、算法的时间复杂性越高，则从计算机速度提高得到的收益就越大吗？第二部分 复习提纲(不分题型)1、顺序表和链表哪个可以按序号随机存取？按值能否随机存取？2顺序表和链表中的逻辑关系分别用什么表示？3链表中结点物理地址一定不连续吗？4、寻找单链表中当前结点的后继和前趋的时间复杂度分别是_。5、单链表中插入、删除结点的执行步骤？6、何谓存储密度？顺序表、链表分别如何？L a1 a2 an7、例：将顺序表中所有负数移动到表的前端，要求移动次数小。解：双向扫描：从前向后找一个正数，再从后向前

3、找一个负数，然后交换两者位置。复杂性为O（n）。void moves(sqlist*L)int i,j;datatype x;i=1;j=L-n;/设数组下标从1开始 while(idatai0&idataj=0&ij)j;/从后向前找负数 if(idatai;L-datai=L-dataj;L-dataj=x;i+;j;+-+-+-+-+-8、例：删除顺序表中所有的正数，要求移动次数小。解：搜索顺序表，对每一个正数，先不删除，而是累计当前正数个数s，于是，对每个非正数，将它一次性前移s位。算法复杂性为O（n）。void dels(sqlist*L)int s,i;s=0;/正数计数器 for

4、(i=0;in;i+)if(L-datai0 s+;/累计当前正数 else if(s0)L-datai-s=l-datai;/向前移动s位 L-n=L-n-s;/调整表长+-+-+-+-+-1、什么问题需要用栈或队列来描述？2、怎样克服假溢出？3、已知进栈序列，怎样判断哪些出栈序列可能或不可能？4、C语言中，串的存储方式是_。5、空串、空白串、串相等、模式匹配含义？6、strcmp()、strlen()、strcat()、strcpy()函数功能？1、数组的基本运算是读、写。没有插入删除等运算2、为什么说数组是随机存储结构？3、对称矩阵、稀疏矩阵，谁压缩存储后还可以随机存取？4、十字链表中的

5、结点需存储非零元素的哪五个信息？5、广义表的分类，图形表示与识别？6、广义表不仅是线性表的推广，也是树的推广。7、用head()和tail()函数在广义表A=(a,(x,y,z),b)中取出原子b。(c)C=(a,b)(d)D=(C,x)(e)E=(y,D)CbDxCabEaGz DxyFCabDxCab(f)F=(C,D)(g)G=(z,G)ABA(a)A=()(b)B=(A)1、3个结点可构成_个不同形态的二叉树。2、二叉树的先根遍历序列和后根遍历序列相同，则该二叉树的特征是_。3、能否有二叉树，其任何遍历次序都相同？4、某完全二叉树有5个叶子，则其结点总数为_。(10或9，一般2n或2n

6、-1)5、某完全二叉树的第5层只有6个结点，则其叶子结点数是_。6、树的先根遍历需要借助_来实现、层次遍历需要借助_来实现。(栈,队列)7、线索二叉树上，求结点的(遍历)前趋和后继时可利用线索得到，是否就不必进行遍历了？8、线索二叉树中，线索的含义？9、哈夫曼树的特点？10、如何画中序、先序、后序线索二叉链表（线索二叉树）？解：以中序线索二叉链表为例，下列二叉树的中序线索二叉链表如图所示。详细过程见课本。ABCDEFCBDEA00000F1111111NULLNULL中序：中序：D B E F A CABCDEFNULLNULL中序线索二叉树中序线索二叉树 中序线索二叉链表中序线索二叉链表11

7、如何由先序中序、后序中序还原出二叉树？解：对前序序列，序列的第一个点就是整个二叉树的根；对后序序列，序列的最后一个点就是整个二叉树的根；对中序序列，以根为界，序列的前一部分为根的左子树，后一部分为根的右子树；并且，前一部分是左子树的中序序列，后一部分是右子树的中序序列。若给定了前序和中序序列，反复利用上面的和，即由前序序列找到根，由中序序列得到左、右子树；再对每个子树由前序序列找到子树的根，由中序序列得到子树的左、右子树，等等类推，每次得到一个点(子树的根)，从而逐渐还原和构造出该二叉树。中序遍历序列：左子树根右子树前序遍历序列：左子树根右子树 根根pspeisiei例例 由先根和中根序列构造

8、二叉树由先根和中根序列构造二叉树G先根序列先根序列中根序列中根序列A BHFD ECKGH BDFA EKC后根后根+中根中根呢？呢？12、例：判断二叉树是否所有结点都为正数。解：设二叉树根指针类型为bitree，函数名为detect，函数返回判断结果int detect(bitree t)if(t=NULL)return 1;/空树返回真，递归出口 if(t-datalchild)&detect(t-rchild);/由左右子树共同决定真或假13、例：判断是否二叉树t否满足小根堆的特点。解：设二叉树结点类型为bitree，函数名为detect，函数返回判断结果。int detect(bitr

9、ee t)if(t=NULL)return 1;/空树返回真 if(t-lchild!=NULL&t-lchild-datadata)|(t-rchild!=NULL&t-rchild-datadata)return 0;return detect(t-lchild)&detect(t-rchild);1 n个顶点及e条边的无向图，邻接表中的边结点数为_，邻接矩阵中1的个数为_。若是有向图呢？2、n个顶点的无向图、有向图，边数范围分别是多少？3、图的DFS遍历类似树的_遍历，是其推广。4、在邻接矩阵和邻接表上进行BFS或DFS遍历时，时间复杂性分别为多少？5、某图有3个连通分量，则要访问所有顶

10、点时，必须调用_次DFS遍历算法。6、若有向图的邻接矩阵中，主对角线以下的元素均为零，则该图可拓扑排序吗？7、拓扑排序可用以分析工程能否顺利进行。8、何谓关键路径？0 1 0 1 00 1 0 1 01 0 1 0 11 0 1 0 10 1 0 1 10 1 0 1 11 0 1 0 01 0 1 0 00 1 1 0 00 1 1 0 0V11V22V33V44m24131各种排序算法的复杂度如何？(好、坏、平均?)(1)、哪些最好和最坏时间复杂度都为O(nlog2n)？(2)、趟数最少和最多情况如何？(3)、哪些空间复杂性为O(n)？2、初始序列基本有序时，哪些排序方法好？3、n个数据直接插入排序，可能的最少比较次数是_。4、希尔排序的增量序列中，最后一个增量为_。5、堆的定义？6、基数排序的排序趟数？练习：练习：(49,38,13,76,65,97,27,49)7各种排序方法步骤如何？（会写每趟结果，冒泡、选择、快速排序等）1、顺序查找法既可用于顺序表，也可用于链表吗？2、二分查找对数据的要求？3、分块查找如何分块较好？效率如何？4、二叉排序树按_遍历结果递增有序。5、散列表中要解决的两个主要问题是：_、_。6、解决散列引起的冲突问题，常采用的方法有哪些？7、何谓堆积现象？开散列表会出现吗？8、数据量越多，散列表的查找效率就越低吗？ii+1i+2i+k i+k+1#