数据结构复习资料.doc

数据结构习题练习题一1. 何谓算法？简述算法的基本特性和表示方法。3. 简述算法与程序的联系与区别，并列举常见的算法设计方法。6. 常见的时间（或空间）复杂度量级有O(1)、O(n)、O(n2)、O(n3)、O(n)、O()和O(2n)等，试将它们按增长率由小到大排列。 练习题二1. 简述下列概念 数据、数据元素、数据类型、数据结构； 数据类型与数据结构的联系与区别； 数据类型的六个显著特征；4. 数组B1.10,-2.6,2.8以行为主序顺序存储；设基地址（第一个元素的地址）为100，每个元素的存储长度为3；试求元素B5,0,7的存储地址。16. 简述下列每对术语的区别： 空串和空格串 串变量和串常量 主串和子串 串名和串值18. 令s=“aabb”,t=“abcabaa”,u=“abcaabbabcabaacbacba”，试分别求其next函数值。练习题三1. 线性表可用顺序表和单链表作为存储结构。试问： 两种存储表示各有哪些主要优缺点？ 如果有n个表同时并存，且处理过程中各表的长度会动态发生变化，表的总数也可能自动改变；在此情况下应选用哪种存储表示？为什么？ 若表的总数基本稳定，且很少进行插入和删除，但要求以最快速度存取表中元素；这时应采用哪种存储表示？为什么？4. 设计一个算法，它通过一趟遍历在单链表中确定值最大的结点。5. 设计一个算法，它在非递减有序的单链表中删除值相同的多余结点。8. 设计一个计算不带表头结点的单链表的表长的算法。9. 已知线性表中元素是无序的，且以带表头结点的单链表作为存储结构。试设计删除表中所有的元素值大于min且小于max的元素的算法。12. 设有一个单循环链表，其表长大于1且表中既无表头结点又无表头指针。已知P为指向表中某结点的指针，试编写在该循环链表中删除指针P所指结点的前趋结点的算法。17. 设有一个栈，元素的进栈次序依次为A、B、C、D、E，试问能否得到下面的出栈序列？若能请写出操作序列，若不能请说明原因。 C，E，A，B，D C，B，A，D，E D，C，A，B，E A，C，B，E，D A，B，C，D，E E，A，B，C，D19. 已知表达式的中缀表示为(A+B)*D+E/(F+A*D)+C，试利用栈把它改写成为后缀表示，并写出转换过程中栈的变化。20. 何谓队列的上溢现象？解决方法有哪些？各种方法的工作原理是什么？23. 试写一个算法，它借助栈判断一个算术表达式中的圆括号是否配对。练习题四 1. 已知一棵树边的集合为 （i，m），（i，n），（e，i），（b，e），（b，d），（a，b），（g，j），（g，k），（c，g），（c，f），（h，l），（c，h），（a，c），请画出这棵树并回答如下问题： 哪个是根结点？ 哪些是叶子结点？ 哪个是结点g的双亲？ 哪些是结点g的祖先？ 哪些是结点g的孩子？ 哪些是结点e的子孙？ 哪些是结点e的兄弟？哪些是结点f的兄弟？ 结点b和结点n的层次号分别是多少？ 树的深度是多少？树的度是多少？ 以结点c为根的子树的深度是多少？2. 一棵度为2的树与一棵二叉树有何区别？5. 一棵深度为h的满k叉树是这样的一棵树，它的第h层上的结点全部是叶子结点，其余各层上的每个结点都有k棵非空子树。如果对深度为h的满k叉树按层次自上而下，同层次自左至右的顺序从1开始对所有结点编号，问： 各层的结点数目是多少？ 编号为n的结点的双亲结点若存在，其编号是多少？ 编号为n的结点的第i个孩子结点若存在，其编号是多少？ 编号为n的结点有右兄弟的条件是什么？其右兄弟编号是多少？6. 一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？7. 对于如图4-32所示的两棵二叉树，分别写出 前序遍历序列； 中序遍历序列； 后序遍历序列； 层次遍历序列。图4-32 两棵二叉树ABCD(a) EGFHIABC(b) DEFG 8. 找出满足下列条件的所有二叉树： 前序遍历序列和中序遍历序列相同； 后序遍历序列和中序遍历序列相同； 前序遍历序列和后序遍历序列相同； 前序遍历序列和层次遍历序列相同。9. 已知一棵二叉树的前序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK。请画出该二叉树，并写出它的后序序列和层次序序列。10. 已知一棵二叉树的后序序列为DCEGBFHKJIA，中序序列为DCBGEAHFIJK。请画出该二叉树，并写出它的前序序列和层次序序列。11. 已知一棵二叉树的层次序序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二叉树，并写出它的前序序列和后序序列。12. 把图4-33所示的两棵树，分别转换为相应的二叉树。图4-33 两棵一般的树ABCD(a) EGFHABC(b) DEFGHIJK 13. 把图4-34所示森林转换为相应的一棵二叉树。图4-34 由三棵树组成的森林ACBEDFGHIJK 14. 把图4-35所示二叉树转换为相应的树或森林，然后分别写出其先根序列和后根序列。 16. 给定一个权重集合为W=3，15，17，14，6，16，9，2，请画出相应的哈夫曼树，并计算其带权路径长度WPL。图4-35 两棵二叉树ABFE(a) CHGDIJABE(b) CFDG 17. 假设用于通信的电文仅由8个字母字符组成，各字母字符在电文中出现的频率分别为7、19、2、6、32、3、21、10。试为这8个字母字符设计哈夫曼编码。对这8个字母字符分别用0到7的三位二进制表示形式编码是另一种编码方案，试比较这两种编码方案的优缺点。20. 试编写一个算法，它交换以二叉链表作存储结构的二叉树中所有结点的左、右子树。24. 试以二叉链表作为存储结构，编写计算二叉树中叶子结点数目的非递归算法。28. 试以二叉链表作为存储结构，编写计算二叉树深度的算法。练习题五1. 对于图5-40给出的有向图和无向图，分别给出其邻接矩阵、邻接表和逆邻接表，并计算每个顶点的度（对有向图需先确定入度和出度）。(b) 无向图v2v1v3v4v5(a) 有向图图5-40 练习题1中的两个图v2v1v3v4v5v6 2. 对于图5-41给出的无向网，分别给出： 邻接多重表； 深度优先搜索遍历序列（分别从v1和v4开始）和深度优先生成树； 广度优先搜索遍历序列（分别从v1和v4开始）和广度优先生成树； 用Prim算法求得最小生成树的过程； 用Kruskal算法求得最小生成树的过程。3. 对于图5-42给出的有向网，分别给出： 邻接矩阵； 用Dijkstra算法求从v1出发到各顶点的最短路径。5. 给出图5-40(a)所示有向无环图的所有拓朴有序序列，并指出按拓朴排序算法求得的序列是哪一个。3116454213v2v1v3v42图5-41 练习题2中的无向网v7v8v5v622352518v2v1v3v410图5-42 练习题3中的有向网v548182v2v2v336图5-43 练习题4中的有向网 17. 用邻接矩阵表示图时，矩阵中元素的个数与顶点个数是否相关？与边的条数是否相关？18. 有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试分别举例说明之。19. 对于有n个顶点的无向图，若采用邻接矩阵表示如何判断以下问题： 图中有多少条边？ 任意两个顶点i和j之间是否有边相连？ 任意一个顶点的度是多少？练习题七4. 若对大小均为n的顺序表和有序表分别进行顺序检索，试分别讨论在等概率的前提下，下述三种情况时的平均检索长度是否相同： 检索不成功，即表中没有关键字值等于给定值k的记录； 检索成功，表中只有一个关键字值等于给定值k的记录； 检索成功，表中有若干个关键字值等于给定值k的记录，一次检索要求能全部找出所有关键字值等于给定值k的记录。5. 对长度为20的有序表进行二分法检索，试画出它的一棵判定树；并求出在等概率情况下检索成功和不成功时的平均检索长度。6. 试把二分法检索算法改写为非递归算法。9. 设结点序列为（60，30，90，50，120，70，40，80），试用二叉检索树的插入算法，画出按此结点序列建立的一棵二叉检索树T1；再用二叉检索树的删除算法，画出依次删除结点40、70、60之后的二叉检索树T2。10. 试编写一个判断给定二叉树是否为二叉排序树的算法；二叉树以二叉链表作为存储结构，且各结点的关键字值均不相等。11. 已知长度为12的表如下所示：（Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec） 按表中元素的顺序依次插入一棵初始为空的二叉检索树中，画出最终的二叉检索树，并求在等概率情况下检索成功时的平均检索长度。 若先对表中元素排序形成有序表，求在等概率情况下进行二分法检索时检索成功的平均检索长度。 构造一棵二叉平衡树，求在等概率情况下检索成功的平均检索长度。14. 具有n个结点的二叉检索树有多少种不同的形态？一个高度为h的二叉平衡树至少有多少个结点？具有n个结点的二叉平衡树的最大高度和最小高度各是多少？18. 给定关键字序列为（19，14，23，1，68，20，84，27，55，11，10，79），设哈希表长为13，哈希函数为h(k)=k%13。 试画出用线性探查法消解地址冲突时所构造的哈希表； 试画出用链地址法消解地址冲突时所构造的哈希表； 并求出以上两种哈希表的平均检索长度。19. 选取哈希函数为h(k)=(3*k)%11；用开放定址法消解地址冲突：d1=h(k)，di=(di-1+(7*k)%10+1)%11（i=2,，3，4，）。试在010的散列地址空间中对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求在等概率情况下检索成功与不成功时的平均检索长度。25. 试设计一个算法，它从二叉检索树中删除一个结点，并仍然保持二叉检索树的特性不变。练习题八2. 排序方法稳定性的含意是什么？试各举三种稳定的和不稳定的排序方法。3. 给定排序码序列为（17，8，21，35，32，15，25，12，23），试分别写出使用以下排序方法进行排序的过程，并说明关键字的比较次数。 直接插入排序 希尔排序（增量为，2，1） 折半插入排序 冒泡排序 快速排序 直接选择排序 堆排序 7. 在冒泡排序过程中，什么情况下排序码会朝着与最终位置相反的方向移动？试举例说明。9. 对于n个排序码进行快速排序时，所需的比较次数与排序码的初始序列有关。当n=7时，回答下列问题： 在最好情况下需要进行多少次比较？请说明理由； 给出在最好情况下的排序码初始序列的一个实例； 在最坏情况下需要进行多少次比较？请说明理由； 给出在最坏情况下的排序码初始序列的一个实例。15. 判断下列序列是否为堆。若不是堆则把它们调整为堆。 （100，85，98，77，80，60，82，40，20，10，66） （100，98，85，