数据结构复习题省公共课一等奖全国赛课获奖课件.pptx

第1页第第1 1章章 绪论绪论1 1、数据元素之间关系在主要计算机中有几个、数据元素之间关系在主要计算机中有几个表示方法？各有什么特点表示方法？各有什么特点?2 2、数据两个算法、数据两个算法A1A1和和A2A2，其中，其中A1A1时间复杂度时间复杂度为为T1=O(2T1=O(2n n),A2),A2时间复杂度为时间复杂度为T2=O(n2),T2=O(n2),仅就仅就时间复杂度而言，请详细分析这两个算法时间复杂度而言，请详细分析这两个算法哪一个更加好哪一个更加好3 3、数据逻辑结构、数据存放结构及数据运算、数据逻辑结构、数据存放结构及数据运算之间存在着怎样关系？之间存在着怎样关系？4 4、试举一例，说明对相同逻辑结构，同一个、试举一例，说明对相同逻辑结构，同一个运算在不一样存放方式下实现，其运算效运算在不一样存放方式下实现，其运算效率不一样。率不一样。第2页5 5、在编制管理通讯录程序时，什么样数据结、在编制管理通讯录程序时，什么样数据结构适当？为何？构适当？为何？6 6、若有、若有100100个学生，每个学生有学号、姓名、个学生，每个学生有学号、姓名、平均成绩，采取什么样数据结构最方便？平均成绩，采取什么样数据结构最方便？第3页第第2 2章章 线性表线性表1 1、对于一个头指针为、对于一个头指针为headhead带头结点单链表，带头结点单链表，给出判定该表为空表条件语句？给出判定该表为空表条件语句？2 2、已知、已知L L为不带头结点单链表，若将新结点为不带头结点单链表，若将新结点为为q q新结点插入到新结点插入到P P结点之后，请给出执行结点之后，请给出执行语句。语句。第4页第第3章章 栈与与队列列1、递归过程或函数程或函数调用用时，处理参数及返回地址，理参数及返回地址，需要一个称需要一个称为_数据数据结构。构。2、设栈S和和队列列Q 初始状初始状态为空，元素空，元素e1、e2、e3、e4、e5和和e6依次依次经过栈S，一个元素出，一个元素出栈后即后即进队列列Q，若，若6个元素出个元素出队序列是序列是e2、e4、e3、e6、e5、e1，则栈S容量最少容量最少应该是是_。3、假、假设以数以数组A60存放次序循存放次序循环队列元素，当列元素，当front=47,rear=23时，则当前当前队列元素个数列元素个数 为 4、已知、已知链队列列头尾尾结点分点分别是是front和和rear,则请给出出 将将值x入入队操作操作语句序列。句序列。第5页第第4章章 串串 1、已知、已知S=“(xyz)+*”，t=“(x+z)*y”。试利用利用求子串和置求子串和置换等基本运算，将等基本运算，将S 转化化为t。2、两个字符串相等充分必要条件是、两个字符串相等充分必要条件是_第6页第第5章章 数数组和广和广义表表 1、数、数组不适合作不适合作为任何二叉任何二叉树存放存放结构（）构（）2、广、广义表中元素或者是一个不可分割原子，或者是表中元素或者是一个不可分割原子，或者是一个非空广一个非空广义表（）表（）3、画出稀疏矩、画出稀疏矩阵非零元素三元非零元素三元组次序表次序表、行、行单链表、列表、列单链表、十字表、十字链表等存放表等存放结构。构。第7页第第6章章 树1、一棵二叉、一棵二叉树中中结点度点度为0或或2，则二叉二叉树分支度分支度为2(n0-1),其中是其中是n0度度为0结点个数（）点个数（）2、一棵完全二叉、一棵完全二叉树上有上有1001个个结点，其中叶子点，其中叶子结点个数是点个数是_3、n个个结点点线索二叉索二叉树上含有上含有线索数索数为4、假、假设一个二叉一个二叉树两种遍两种遍历以下：以下：前序：前序：ABFGCHDEIJLK 中序：中序：FGBHCDILJKEA 画出画出这棵二叉棵二叉树以及它后序以及它后序线索索树。第8页5、请推推导结论：含有：含有n0个叶子个叶子结点哈夫曼点哈夫曼树分支分支总数数为2(n0-1)。6、已知某通信用、已知某通信用电文由文由A、B、C、D、E、F6个字个字符符组成，其出成，其出现频率分率分别为23、5、14、8、25、7，请给出它出它们哈夫曼哈夫曼编码及求解及求解过程。程。7、以下、以下编码中，哪一个不是前中，哪一个不是前缀码？（）？（）A、00，01，10，11 B、0，1，00，11C、0，10，110，111，D、1，01，000，001第9页第第7章章 图 1、在、在n个个结点无向点无向图中中，若，若边数大于数大于n-1，则该图必是必是连通通()2、任何无向、任何无向图都存在生成都存在生成树（）（）3、无向、无向图邻接矩接矩阵可用一可用一维数数组存放（）存放（）4、有向、有向图邻接矩接矩阵是是对称称()第10页第第8章章 查找找1、用、用单链表表示有序表均可使用折半表表示有序表均可使用折半查找方法来提升找方法来提升查找速度找速度()2、设散列表地址空散列表地址空间为010，散列函数，散列函数为H(key)=key11，采取，采取线性探性探查法法处理冲突理冲突，并将，并将键值序列序列15,36,50,27,19,48依次存放到散列表中。依次存放到散列表中。（1）请画出画出对应散列表；散列表；（2）并）并计算当算当查找找键值为48时，需要比，需要比较多少次？多少次？第11页第第9章章 排序排序 1、排序方法有、排序方法有许各种，各种，_法从未排序序法从未排序序列中依次取出元素，与已排序序列（初始列中依次取出元素，与已排序序列（初始时为空）空）中元素作比中元素作比较，将其放入到已排序序列正确位，将其放入到已排序序列正确位置上；置上；法从未排序序列中挑法从未排序序列中挑选元素，并将其元素，并将其依次放入已排序序列（初始依次放入已排序序列（初始时为空）一端。空）一端。交交换排序法是排序法是对序列中元素序列中元素进行一系列比行一系列比较，当被，当被比比较两元素逆序两元素逆序时，进行交行交换。_和和_是基于是基于这类方法两种排序方法。方法两种排序方法。_排序法是排序法是基于基于选择排序一个排序方法，是完全二叉排序一个排序方法，是完全二叉树结构构一个主要一个主要应用。用。第12页2、若待排序、若待排序统计关关键值集合是集合是30,4,48,25,95,13,90,27,18，请给出采取快速排出采取快速排序第序第1趟、第趟、第2趟排序趟排序结果。果。若若对这些关些关键值集合采取堆排序，集合采取堆排序，请问初始堆是什初始堆是什么么？3、对以下数据表以下数据表100,12,20,31,1,5,44,66,61,200,30,80,150,4,8,设增量序列增量序列为d=5,3,1，写出采取，写出采取Shell排序算法排序算法每一趟每一趟结果。果。第13页