数据结构 习题.doc
数 据 结 构 习 题习题一1.1 书写函数，实现求任一整数数组中的最小值。1.2书写实现如下功能的函数声明：已知一个含有n个元素的数组，从第i个元素开始移走k个元素。1.3用typedef定义学生成绩记录的类型，并书写函数求做高分的同学的姓名。1.4求下列程序段的时间复杂度(1)i=1;k=0;do k+=10*i;i+;while(i<=n-1)(2)k=0;for(i=1;i<=n;i+)for(j=i;j<=n;j+)k+;习题二2.1书写算法实现在顺序表v中查找值等于e的元素的位置，若找到返回位置；否则，返回-1。2.2* 已知递增有序的线性表采取顺序存储结构表示，试写一算法，在该表中插入一个值为x的新元素，并保持线性表的有序性。 2.3* 写一算法，从顺序表中删除自第i个元素开始的k个元素。 2.4* 写一算法，实现顺序表（a1,a2,an）的就地逆置。2.5已知单链表L，打印输出其所有元素。2.6已知单链表L，求单链表的表长。2.7已知递增有序的单链表，插入一个元素x，使之仍然保持有序。2.8* 有一不带头结点的单链表L，编写算法将L就地逆置。习题三3.1 设计一个算法判别一个算术表达式的圆括号是否正确配对。3.2* 假设称正读和反读都相同的字符序列为“回文”，例如，“abcddcba”、 “qwerewq”是回文，“ashgash”不是回文。是写一个算法判断读入的一个以为结束符的字符序列是否为回文。3.3 已知一个多项式Fn(X)，可递归定义如下：Fn(X)1 当n0时2X 当n1时2X Fn-1(X)-2(n-1)Fn-2(X) 当n>1时试写出计算Fn(X)值的递归函数。习题五5.1 数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（ (1) ），若该数组按行存放时，元素A85的起始地址是( (2) ），若该数组按列存放时，元素A85的起始地址是（ (3) ）。(1)A. 80 B.100 C.240 D.270(2)A.SA+141 B.SA+144 C.SA+222 D.SA+225(3)A.SA+117 B.SA+180 C.SA+222 D.SA+2255.2假设按行优先存储整数数组A9358时，第一个元素的字节地址时100，每个整数占4个字节。问下列元素的存储地址是什么。(1) a0000 (2)a1111 (3)a3125 5.3求下列广义表的操作结果GetHead(a),a) GetTail(a),a)GetTailGetHead(a,b),(c,d)GetHeadGetHead(a,b),(c,d)习题六6.1试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 6.2已知一棵度为m的树中有ni个（i=1,2,m）度为i的结点，问该树中有多少个叶子结点？6.3证明：一棵满k叉树上的叶子结点数n0和非叶子结点数n1之间满足如下关系： n0 =(k-1)n1 +1。6.4已知二叉树：1画出该二叉树的顺序存储结构和二叉链表存储结构。2写出该二叉树的前序、中序、后序、层次遍历序列。abcdgefhi6.5已知二叉树按照二叉链表方式存储，设计算法求二叉树的深度。6.6有n个结点的完全二叉树以向量为存储结构，试写算法对其进行先序遍历。6.7已知树：ABCDEGFHIJK1画出对应的二叉树2求树的先根遍历序列和后根遍历序列6.8已知森林：112134567891011121314151将此森林转化为对应的二叉树2求该森林的先序遍历序列和中序遍历序列6.9将下面的二叉树转换为森林：ABCDEGHJKFIM6.10假设一棵二叉树的先序序EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。6.11设一棵二叉树的中序序列DCBGEAHFIJK，后序序列为DCEGBFHKJIA，请画出该二叉树。6.12下列编码哪一组不是前缀码？(a)(00,01,10,11) (b)(0,1,00,11) (c)(0,10,110,111)6.13假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。若用三位二进制数（07）对这8个字母进行等长编码，则赫夫曼编码的平均码长是等长编码的百分之几？它使电文平均压缩多少？习题七2134567.1已知如图所示的有向图，请给出该图的：（1）每个顶点的入度、出度；（2）邻接矩阵；（3）邻接表。 213456787.2已知如图所示的无向图，请给出该图的：（1）写出从顶点1出发的深度优先遍历序列和广度优先遍历序列。（2）画出其深度优先生成树和广度优先生成树。（3）求其连通分量的个数。 7.3 用prim算法构造下图的一棵最小生成树(给出构造过程)abcdefgh439555553266747.4用kruskal算法构造下图的一棵最小生成树716523467182342520510812157.5 给出下面有向图的两个拓扑序列：v1v2v3v5v4v67.6 求下面AOE网的关键路径。12345769108a1=5a2=6a3=3a4=6a5=3a6=4a7=4a8=3a8=3a9=1a10=4a11=5a12=4a13=2a14=27.7 用Dijkstra算法求下图中从顶点V1到其余各顶点的最短路径。v4v5v6v2v3v1201510101030421520习题99.1画出对长度为10的有序表a1.10进行查找的一棵判定树，并求其等概率时查找成功的平均查找长度ASL。9.2有一2000块的表，要采用等分区间顺序查找的分块查找算法，问：(1)每块的理想长度为多少？(2)平均查找长度ASL为多少？(3)若每块为20，ASL为多少？9.3输入一正整数序列40,28,6,72,100,3,54,1,80,91,38：(1)建立一棵二叉排序树，并求出其等概率情况下查找成功的平均查找长度。(2)依次插入结点30,10,101，删除结点72，画出每次执行后二叉排序树的状态。9.4试从空树开始，画出按以下次序向2-3树，即3阶B-树中插入关键码的建树过程：20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后2-3树的状态。 9.5选取哈希函数H(key)=(3 key)%11，并开放地址法处理冲突，其求下一地址的函数为：d1H(key)di(di-1+(7key)%11 (i=2,3) 试在010的散列地址空间中，对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功与不成功时的平均查找长度。 9.6 试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。9.7 已知长度为12的表（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。（1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树并求其等概率的情况下查找成功的平均查找长度。（2）若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。（3）按表中元素的顺序依次构造一棵平衡二叉排序树，并求其等概率的情况下查找成功的平均查找长度。 习题1010.1 以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：（1）直接插入排序； （2）简单选择排序；（3）起泡排序； （4）快速排序；（5）堆排序； （6）归并排序；（7）基数排序。
