数据结构练习

1、第一章 作业1. 解释下列术语 数据、数据元素、数据对象、数据类型、抽象数据类型、原子数据类型、结构数据类型、逻辑结构、存储结构、数据结构、顺序存储结构、链式存储结构、算法2设有数据逻辑结构为Data-structure=(D,R), 其中Dd1,d2,d3,d4,d5,d6, R=r, r=<d1, d2>, <d1, d3>, <d1, d4>, <d3, d5>, <d4, d5>, <d4, d6>, 试画出其逻辑结构图。3如图所示为某种数据类型的逻辑结构图，试用二元组方式表示此数据的逻辑结构：ABCGDFE4.

2、数据类型和抽象数据类型是如何定义的，二者有何相同和不同之处？抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？5. 按照阶由低到高的顺序排列下列时间复杂度：6. 试编写算法，对连续输入的n个整数，找出其中最大值和最小值（规定输入数在整数允许范围内）。7有若干学生（设有3个学生）的成绩（设每个学生有4门课程），编程找出其中有不及格课程的学生，输出他们的全部课程的成绩。第二章作业：1. 已知线性表LA的数据元素（n个，n为偶数），现要求将LA拆开成两个新的线性表LB，LC。要求LB中的数据元素为LA中的奇数位序的数据元素（a1, a3, , an-1），LC中的数据元素为LA中的偶数

3、位序的数据元素（a2, a4, , an）。2. 已知线性表LA的数据元素（n个），现要求将LA的数据元素复制到另一个线性表LB中。3. 设有一个线性表采用顺序存储结构，表中的数据元素值为正整数（n个）。设在O(n) 时间内，将线性表分成两为两部分，其中左半部分每个元素都小于原表的第一个元素，而右半部分则相反。4.设线性表LA（a1, a2, , am），LB（b1, b2, , bn）。试编写一个算法，将LA、LB合并为线性表LC，使要求LA、LB和LC均以单链表为存储结构，且LC表利用LA和LB中结点空间，这里m和n的值没有保存在头结点中，并分析算法时间复杂度。5. 约瑟夫问题：设编号为1

4、，2，n的n（n>0）个人按顺时针方向围坐一圈，每人持有一正整数密码。开始时任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列（采用循环单链表结构）。6. 试比较顺序存储结构和链表存储结构的优缺点第三章作业：3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Pu

5、sh(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何 (这里Push(i)表示i进栈，Pop( )表示出栈)? (2) 能否得到出栈序列1423和1432? 并说明为什么不能得到或者如何得到。 (3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。3.2 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?3.3 回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不

6、是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 3.4 设计算法判断一个算术表达式的圆括号是否正确配对。 (提示： 对表达式进行扫描，凡遇到'('就进栈，遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。3.5 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。3.6 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队

7、头元素。第四章作业1. 假设以顺序存储结构存放字符串，试编写算法，实现下列基本操作（用C语言编写）：（1）CreatString(&S)。输入并建立顺序存储的字符串S；（2）SubString(&T, S, pos, len)。求S串从pos开始长度为len的子串放入T串；（3）StrInsert(&S, i, T)。在串S的第i个字符前插入T；（4）StrDelele(&T, S, i, len)。从串S中删除第i个字符起长度为len的子串送到T中。2. 设a=“ ”，b=“old friend”, c=“good”, d=“new”, 试完成下列运算：（1）

8、StrLength(a), StrLength(b); （2）SubString(sub, b, 4, 3);（3）Replace(b, old, d);（4）ConCat(S, c, ConCat(T, a, b).第六章 练习1 已知一棵树的逻辑结构用以下二元组表示：D_structure=(D,S);D=A,B,C,D,E,F,G,H,I,J,K,L,M,NS=<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>,<G,J>,<G,K>,<C,G>,<C,F

9、>,<H,L>,<C,H>,<A,C>画出树的逻辑结构图，并回答以下问题：（1） 哪个是根结点（2） 哪些是叶子结点？（3） 哪个是结点G的双亲？哪个是结点G的祖先？哪些是结点G的孩子？（4） 哪些是结点F的兄弟？（5） 树的深度是多少？结点N在第几层？2、设树T的度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，问T有多少叶子结点？3、画出只含有三个结点的二叉树的所有不同形态，并分别写出其先序边历、中序遍历、后序遍历的序列。已知二叉树的先序遍历序列为DBACFEG，中序遍历序列为ABCDEFG。画出二叉树，并写出后序遍历序列。4、已知二叉

10、树的中序遍历序列为DCBGEAHFIJK，后序遍历序列为DCEGBFHKJIA。画出二叉树，并写出先序遍历序列。5、分别对图A和图B进行中序线索化和后序线索化，为每个空指针建立相应的前驱或后继线索。ACBDEFGACBDEFG（A） (B)6、画出和下列二叉树对应的森林7、将下列森林转换为相应二叉树8、画出树的二叉树链表表示的逻辑结构图9、设有7个带权结点A,B,C,D,E,F,G。其权值分别为3、7、8、2、5、8、4。试以这些结点作为叶子结点，构造最优二叉树。要求左子树根结点的权值小于右子树根结点。10、设用于通信的电文仅由六个字符A,B,C,D,E,F组合而成，字符在电文中出现的概率分别

11、为0.32, 0.12, 0.16 , 0.03 ,0.21, 0.16，试为这6个字母设计赫夫曼编码。11、编写递归算法，在链式存储的二叉树中求位于先序序列中的K个位置的结点的值。12、编写递归算法，计算二叉树中叶子结点的数目13、编写递归算法，将二叉树中所有结点的左右子树互换。14、编写递归算法，求二叉树的深度。第七章 图1 设有一有向图为G=(V，E)。其中，V=v0, v1, v2, v3，E=<v1, v0>, <v2, v1>, <v3, v2>, <v3, v1>, <v0, v3>。请画出该有向图。2对n个顶点的无向图

12、G，采用邻接矩阵表示，如何判别下列有关问题(1) 图中有多少条边?(2) 任意两个顶点i和j是否有边相连?(3) 任意一个顶点的度是多少?3 对于下面的带权有向图，写出其相邻矩阵表示，并画出其邻接表表示。4 对于图7.27，从顶点v0出发分别画出其深度优先生成树和广度优先生成树。5 对于图7.28所示的网络，请分别用Prim算法和Kruskal算法构造该网络的最小生成树。第九章 查找1 试编写利用折半查找确定记录所在块的分块查找算法。并讨论在块中进行顺序查找时使用“监视哨”的优缺点，以及必要时如何在分块查找的算法中实现设置“监视哨”的技巧。2在地址空间为016的散列区中，对以下关键字序列构造两个哈希表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）（1）用线性探测开放定址法处理冲突；（2）用链地址法处理。设哈希函数为，其中i为关键字中第一个字母在字母表中的序号。3. 哈希函数H(k)=(3k)MOD11。用开放定址法处理冲突，di=i(7k)MOD10+1) (i=1,2,3,)。试在012的散列地址空间中对关键字序列（22，41，53，46，30，13，01，67，18，90）造哈希表。第10章 内部排序1给出初始排序码序