据 结 构 杨春花 2006-9-26
第 1 页 共 8 页 题数习
习题一
1.1 设有二元组表示的数据结构，画出它们对应的逻辑图形表示，并指出它们属于何种结构？ D＝（K，R）
K＝｛a,b,c,d,e,f,g,h｝
R＝｛ 1.2：已知某顾客电话号码表，请用两种方式写出数据元素的类型声明和顺序存储表示。并写出根据姓名查询电话号码的函数声明。 姓名 吴承志 李淑芳 刘 丽 张会友 电话号码 88010112 88010113 88010119 88010124 1.3 已知元素为整数的一维数组A，有10个元素。书写函数求数组中的最大值和最小值，要求用引用参数调用返回最大值和最小值。 1.4求下列程序段的时间复杂度 (1)i=1;k=0; for(i=1;i<=n;i++){ do { k+=10*i; for(j=I;j<=n;j++) i++; k++; }while(i<=n-1) } (2)k=0; 习题二 2.1采用如下的顺序表定义，书写算法实现在顺序表v中查找值等于e的元素的位置，若找到返回位置； 否则，返回-1。 2.2设线性表存放在整型数组V[1..N0]的前n个元素中，且递增有序。试写一算法，在线性表中插入一个值为x的新元素，并保持线性表的有序性。 2.3写一算法，从顺序表中删除自第i个元素开始的k个元素。 2.4写一算法，实现顺序表（a1,a2,…,an）的就地逆置。 2.5已知单链表L，求单链表的表长。 2.6有一不带头结点的单链表L，编写算法将L就地逆置。 2.7已知带头节点的单链表L中的结点按整数值递增排列，试写一算法，将值为x的结点插入L中，使L仍有序。 第 2 页 共 8 页 习题三 1． 设5个元素进栈的先后顺序为A、B、C、D、E，试问能否得到出栈顺序： （1）C、E、A、B、D （2）C、B、A、D、E （3）D、C、A、B、E （4）A、C、B、E、D （4）A、B、C、D、E （4）E、A、B、C、D 2． 两个栈共享向量空间v[m]，它们的栈底分别设在向量的两端，每个元素占一个分量，试写出两个栈公 用的栈操作算法：push(i,x)、pop(i)和top(i)，i=0和1 ,用以指示栈号。 3． 假设称正读和反读都相同的字符序列为“回文”，例如，“abcddcba”、 “qwerewq”是回文，“ashgash” 不是回文。是写一个算法判断读入的一个以‘@’为结束符的字符序列是否为回文。 4． 设计一个算法判别一个算术表达式的圆括号是否正确配对。 5． 已知一个多项式Fn(X)，可递归定义如下： 1 当n＝0时 Fn(X)＝ 2X 当n＝0时 2X Fn-1(X)-2(n-1)Fn-2(X) 当n＝0时 试写出计算Fn(X)值的递归函数的过程。 习题五 5.1 假设按行优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址时１００，每个整数占４个字节。问下列元素的存储地址是什么。 (1) a0000 (2)a1111 (3)a3125 5.2 数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（ (1) ），若该数组按行存放时，元素A[8][5]的起始地址是( (2) ），若该数组按列存放时，元素A[8][5]的起始地址是（ (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+117141 B.SA+180 C.SA+222 D.SA+225 5.3求下列广义表的操作结果 GetHead[((a),a)] GetTail[((a),a)] GetTail[GetHead[((a,b),(c,d))]] GetHead[GetHead[((a,b),(c,d))]] 习题六 6.1试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 6.2已知一棵度为m的树中有ni个（i=1,2,…,m）度为i的结点，问该树中有多少个叶子结点？ 6.3高度为h的完全二叉树至少有多少个结点？至多有多少个结点？ 6.4证明：一棵满k叉树上的叶子结点数n0和非叶子结点数n1之间满足如下关系： n0 =(k-1)n1 +1 6.5已知二叉树： 第 3 页 共 8 页 a b c e f d g h i 1画出各二叉树的顺序存储结构和二叉链表存储结构。 2写出各二叉树的前序、中序、后序、层次遍历序列。 3画出各二叉树的前序、中序、后序线索化树。 6.6已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中所有结点数。 6.7已知二叉树按照二叉链表方式存储，设计算法求二叉树的深度。 6.8有n个结点的完全二叉树以向量为存储结构，试写算法对其进行前序遍历。 6.9已知树： A C B D E F G H I J K 1画出对应的二叉树 2求树的先根遍历序列和后根遍历序列 6.10已知森林： 第 4 页 共 8 页 1 9 11 12 1 2 3 4 5 10 13 14 15 7 6 8 1将此森林转化为对应的二叉树 2求该森林的先序遍历序列和后序遍历序列 6.12将下面的二叉树转换为森林： A B C D E F I G H J K M 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个字母设计哈夫曼编码。若用三位二进制数（0～7）对这8个字母进行等长编码，则赫夫曼编码的平均码长是等长编码的百分之几？它使电文平均压缩多少？ 6.14给定权集W={2,3,4,7,8,9}，试构造关于W的一棵赫夫曼树，并求其WPL。 6.15假设一棵二叉树的先序序EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。 6.16设一棵二叉树的中序序列DCBGEAHFIJK，后序序列为DCEGBFHKJIA，请画出该二叉树。 习题七 7.1已知如图所示的有向图，请给出该图的： （1）每个顶点的入度、出度； （2）邻接矩阵； （3）邻接表； （4）逆邻接表； 1 2 6 第 5 页 共 8 页 3 5 4 （5）强连通分量。 7.2已知如图所示的无向图，请给出该图的： （1）邻接矩阵 （2）邻接表（要求邻接表中各顶点所邻接到的顶点序号由小到大排列） （3）写出从顶点1出发的深度优先遍历序列和广度优先遍历序列。 1 2 3 （4）画出其深度优先生成树和广度优先生成树。 （5）求其连通分量的个数。 7.4 给出下面有向图的两个拓扑序列： v2 v5 v1 v4 v3 v6 7.5 用prim算法构造下图的一棵最小生成树(给出构造过程) 9 b e 3 4 5 7 5 a d 6 f 5 2 3 c 4 5 5 g h 6 7.6用kruskal算法构造下图的一棵最小生成树 18 2 5 6 1 23 12 7 4 8 3 25 5 7 6 15 10 20 4 7.7 求下面AOE网的关键路径。 第 6 页 共 8 页 6 4 5 7 8 a3=3 2 a1=5 1 a2=6 3 a4=6 a8=3 5 4 a6=4 a7=4 7 a9=1 6 a11=5 a12=4 a14=2 9 a13=2 10 a5=3 a10=4 8 7.8 用Dijkstra算法求下图中从顶点V1到其余各顶点的最短路径。 10 15 v5 v2 2 10 v4 20 30 4 15 v6 10 v3 v1 20 习题9 9.1编写函数，利用二分查找算法在一有序表中插入元素x，并保持表的有序性。 9.2画出对长度为10的有序表a[1..10]进行查找的一棵判定树，并求其等概率时查找成功的平均查找长度ASL。 9.3有一2000块的表，要采用等分区间顺序查找的分块查找算法，问： (1)每块的理想长度为多少？ (2)平均查找长度ASL为多少？ (3)若每块为20，ASL为多少？ 9.4输入一正整数序列｛40,28,6,72,100,3,54,1,80,91,38｝： (1)建立一棵二叉排序树，并求出其等概率情况下查找成功的平均查找长度。 (2)依次插入结点30,10,101，删除结点72，画出每次执行后二叉排序树的状态。 9.5试从空树开始，画出按以下次序向2-3树，即3阶B-树中插入关键码的建树过程：20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后2-3树的状态。 9.6选取哈希函数H(key)=(3 key)%11，并开放地址法处理冲突，其求下一地址的函数为： d1＝H(key) di＝(di-1+(7key))%11(i=2,3…) 试在0～10的散列地址空间中，对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功与不成功时的平均查找长度。 9.7 试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。 9.8 已知长度为12的表（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。 （1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树并求其等 第 7 页 共 8 页 概率的情况下查找成功的平均查找长度。 （2）若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。 （3）按表中元素的顺序依次构造一棵平衡二叉排序树，并求其等概率的情况下查找成功的平均查找长度。 习题10 10.1 以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态： （1）直接插入排序；（3）起泡排序； （5）堆排序； （7）基数排序。 （2）简单选择排序； （4）快速排序； （6）归并排序； 第 8 页 共 8 页 因篇幅问题不能全部显示，请点此查看更多更全内容