数据结构复习题公开课一等奖优质课大赛微课获奖课件.pptVIP

数据结构第1页第1页

第1章绪论1、数据元素之间关系在主要计算机中有几个表示方法？各有什么特点?2、数据两个算法A1和A2，其中A1时间复杂度为T1=O(2n),A2时间复杂度为T2=O(n2),仅就时间复杂度而言，请详细分析这两个算法哪一个更加好3、数据逻辑结构、数据存放结构及数据运算之间存在着怎样关系？4.试举一例，说明对相同逻辑结构，同一个运算在不同存放方式下实现，其运算效率不同。第2页第2页

5、在编制管理通讯录程序时，什么样数据结构适当？为何？6.若有100个学生，每个学生有学号、姓名、平均成绩，采用什么样数据结构最以便？第3页第3页

第2章线性表1、对于一个头指针为head带头结点单链表，给出鉴定该表为空表条件语句？2.已知L为不带头结点单链表，若将新结点为q新结点插入到P结点之后，请给出执行语句。第4页第4页

第3章栈与队列1、递归过程或函数调用时，处理参数及返回地址，需要一个称为_______数据结构。2、设栈S和队列Q初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队序列是e2、e4、e3、e6.e5、e1，则栈S容量至少应当是______。3、假设以数组A[60]存储顺序循环队列元素，当front=47,rear=23时，则当前队列元素个数为——————4、已知链队列头尾结点分别是front和rear,则请给出将值x入队操作语句序列。第5页第5页

第4章串1、已知S=“(xyz)+*”，t=“(x+z)*y”。试利用求子串和置换等基本运算，将S转化为t。2.两个字符串相等充足必要条件是_____第6页第6页

第5章数组和广义表1、数组不适合作为任何二叉树存储结构（）2、广义表中元素或者是一个不可分割原子，或者是一个非空广义表（）3.画出稀疏矩阵非零元素三元组顺序表、行单链表、列单链表、十字链表等存储结构。第7页第7页

第6章树1、一棵二叉树中结点度为0或2，则二叉树分支度为2(n0-1),其中是n0度为0结点个数（）2、一棵完全二叉树上有1001个结点，其中叶子结点个数是________3、n个结点线索二叉树上含有线索数为—————4.假设一个二叉树两种遍历下列：前序：ABFGCHDEIJLK中序：FGBHCDILJKEA画出这棵二叉树以及它后序线索树。第8页第8页

5、请推导结论：含有n0个叶子结点哈夫曼树分支总数为2(n0-1)。6、已知某通信用电文由A、B、C、D.E、F6个字符构成，其出现频率分别为23、5、14、8、25、7，请给出它们哈夫曼编码及求解过程。7、下列编码中，哪一个不是前缀码？（）A、00，01，10，11B、0，1，00，11C、0，10，110，111，D.1，01，000，001第9页第9页

第7章图1、在n个结点无向图中，若边数不小于n-1，则该图必是连通()2、任何无向图都存在生成树（）3、无向图邻接矩阵可用一维数组存储（）4.有向图邻接矩阵是对称()第10页第10页

第8章查找1、用单链表表示有序表均可使用折半查找办法来提升查找速度()2.设散列表地址空间为0…10，散列函数为H(key)=key％11，采用线性探查法处理冲突，并将键值序列{15,36,50,27,19,48}依次存储到散列表中。（1）请画出相应散列表；（2）并计算当查找键值为48时，需要比较多少次？第11页第11页

第9章排序1.排序办法有许各种，______法从未排序序列中依次取出元素，与已排序序列（初始时为空）中元素作比较，将其放入到已排序序列正确位置上；———法从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）一端。互换排序法是对序列中元素进行一系列比较，当被比较两元素逆序时，进行互换。______和_____是基于这类办法两种排序办法。______排序法是基于选择排序一个排序办法，是完全二叉树结构一个主要应用。第12页第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页第13页