数据结构复习题市公开课获奖课件

1、数据结构第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、链表，给出鉴定该表为空表条件语句？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、假设以数组A60存储顺序循环队列元素，当front=47,rear=23时，则当前队列元素个数 为 4、已知链队列头尾结点分别是front和rear,则请给出 将值x入队操作语句序列。第5

3、页第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、假设一个二叉树

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，11 B、0，1，00，11C、0，10，110，111，D、1，01，000，001第9页第9页第7章 图 1、在n个结点无向图中 ，若边数不小于n-1，则该图必是连通( )2、任何无向图都存在生成树（）3、

5、无向图邻接矩阵可用一维数组存储（）4、有向图邻接矩阵是对称( )第10页第10页第8章 查找1、用单链表表示有序表均可使用折半查找办法来提升查找速度( )2、设散列表地址空间为010，散列函数为H(key)=key11，采用线性探查法处理冲突 ，并将键值序列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、对下列数