数据结构习题.doc

《数据结构习题.doc》由会员分享，可在线阅读，更多相关《数据结构习题.doc（14页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第 1 页数据结构习题集第一章 序论思考题：1.1 简述下列术 语：数据、数据元素、数据对象、数据结构、存储结构、数据类型、抽象数据类型作业题：1.2 设有数据结构（D，R） ，其中D=d1, d2, d3, d4 R=r1, r2r1= , , , , , r2= (d1, d2), (d1, d3), (d1, d4), (d2, d4), (d2, d3) 试绘出其逻辑结构示意图。1.3 设 n 是正整数。试写出下列程序段中用记号“”标注的语句的频度：(1) i=1; k=0;while(i=(y+1)*(y+1) y+;(6) x=91; y=100;while ( y0 ) if(x

2、100) x-=10; y-; else x+ ; (7) for( i=0; in; i+)for( j=i; jn; j+)for( k=j; kn; k+) x+=2;1.4 试写一算法，自大至小依次输出顺序读入的三个整数 X,Y和 Z的值。1.5 已知 k阶斐波那契序列的定义为：f0=0, f1=0, fk-2=0, fk-1=1；fn= fn-1+ fn-2+ fn-k, n=k,k+1,试编写求 k阶斐波那契序列的第 m项值的函数算法，k 和 m均以值调用的形式在函数参数表中出现。第二章 线性表思考题：2.1 描述以下三个概念的区别：头指针、头结点、首元结点。2.2 描述以下几个概

3、念：顺序存储结构、链式存储结构、顺序表、有序表。作业题：2.3已知顺序表 La中数据元素按非递减有序排列。试写一个算法，将元素 x插到 La的合适位置上，保持该表的有序性。2.4已知单链表 La中数据元素按非递减有序排列。按两种不同情况，分别写出算法，将元素 x插到 La的合适位置上，保持该表的有序性：（1）La 带头结点；（2）La 不带头结点。2.5试写一个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表（a 1,a2, ., an-1,an）逆置为(a n,an-1, ., a2,a1)2.6试写一个算法，对带头结点的单链表实现就地逆置。第 3 页2.7已知线性表 L采用顺序存储结

4、构存放。对两种不同情况分别写出算法，删除 L中值相同的多余元素，使得 L中没有重复元素：(1)L 中数据元素无序排列；(2)L中数据元素非递减有序排列。2.8将 2.7题中 L的存储结构改为单链表，写出相应的实现算法。2.9 设有两个非递减有序的单链表 A和 B。请写出算法，将 A和 B“就地”归并成一个按元素值非递增有序的单链表 C。2.10 设有一个长度大于 1的单向循环链表，表中既无头结点，也无头指针，s为指向表中某个结点的指针,如图 2-1所示。试编写一个算法，删除链表中指针s所指结点的直接前驱。s待删结点图 2-12.11 已知线性表用带头结点的单链表表示，表中结点由三类字符组成：字

5、母、数字和其他字符。试编写算法，将该线性链表分割成三个循环单链表，每个循环单链表中均只含有一类字符。2.12 已知线性表用顺序存储结构表示，表中数据元素为 n个正整数。试写一算法，分离该表中的奇数和偶数，使得所有奇数集中放在左侧，偶数集中放在右侧。要求：(1)不借助辅助数组;(2)时间复杂度为 O(n)。2.13 设以带头结点的双向循环链表表示的线性表 L=(a1,a2,a3,.,an)。试写一时间复杂度为 O(n)的算法，将 L改造为 L=(a1,a3,.,an,.,a4,a2)。第三章 栈和队列思考题：3.1 简述栈和线性表的差别。3.2 如果进栈序列为 A、B、C、D，写出所有可能的出栈

6、序列。第 4 页3.3 简述栈和队列的相同点和差异。3.4 已知栈 S中存放了 8个数据元素，自栈底至栈顶依次为(1,2,3,4,5,6,7,8)。（1）写出在执行了函数调用 algo1(S)后，S 中的元素序列。（2）在（1）的基础上，又执行了函数调用 algo2(S,5)，写出此时 S中的元素序列。void algo1(Stack while(!StackEmpty(S) n+; Pop(S, an); for(i=1; i=n; i+) Push(S, ai);void algo2(Stack int d;InitStack(T);while(!EmptyStack(S)Pop(S,d)

7、;if(d!=e) Push(T,d);while(!StackEmpty(T)Pop(T,d);Push(S,d);3.5已知队列 Q中自队头至队尾依次存放着(1,2,3,4,5,6,7,8)。写出在执行了函数调用 algo3(Q)后，Q 中的元素序列。void algo3(Queue int d;InitStack(S);第 5 页while(!QueueEmpty(Q)DeQueue(Q,d); Push(S,d);while(!StackEmpty(S)Pop(S,d); EnQueue(Q,d);作业题：3.6 试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形如“序列 1

8、&序列 2”模式的字符序列。其中，序列 1和序列 2中都不包含字符&,且序列 2是序列 1的逆序。例如， “a+b&b+a”是属于该模式的字符序列，而“13&31”则不是。3.7 假设一个算术表达式中可以包含三种符号：圆括号“(”和“)” 、方括号“”和“” 、花括号“”和“” ，且这三种括号可按任意次序嵌套使用。编写判别给定表达式中所含的括号是否正确配对的算法（已知表达式已存入数据元素为字符的顺序表中） 。3.8 设表达式由单字母变量、双目运算符和圆括号组成（如:“(a*(b+c)-d)/e） ”。试写一个算法，将一个书写正确的表达式转换为逆波兰式。3.9 试用类 C写一个算法，对逆波兰式求

9、值。3.10 假设以带头结点的单循环链表表示队列，只设一个尾指针指向队尾元素，不设头指针。试编写相应的队列初始化、入队和出队的算法。3.11 假设将循环队列定义为：以 rear和 length分别指示队尾元素和队列长度。试给出此循环队列的队满条件，并写出相应的入队和出队算法（在出队算法中要传递回队头元素的值） 。3.12 试写一个算法：判别读入的一个以为结束符的字符序列是否是“回文” （所谓“回文”是指正读和反读都相同的字符序列，如“xxyzyxx”是回文，而“abcab”则不是回文） 。第 6 页第五章 多维数组5.1 已知多维数组 A2233按行优先方式存储。试按存储位置的先后次序，列出所

10、有数组元素 Aijkl序列（为了简化表达，可以只列出形如“i,j,k,l”的序列，如元素 A0021可表示为“0,0,2,1” ） 。5.2 假设有一个二维数组 A0.50.7，每个元素占 6个字节，首元素 A00的地址为 1000，求：(1)A的体积；(2)最后一个元素 A57的地址；(3)按行主序方式存储时，A24的地址；(4)按列主序方式存储时，A24的地址；5.3 设有上三角矩阵 Ann， nnaCaa.3322111将其上三角的元素逐行存于数组 B0.m-1中（m 充分大） ，使得 Bk=aij且kf 1(i)+f2(j)+c。试推导出函数 f1、f 2和常数 c（要求 f1和 f2

11、中不含常数项）。5.4 设有一个准对角矩阵 mma aa2,12,14321 .按以下方式存于一维数组 B4m中：第 7 页0 1 2 3 4 5 6 k 4m-2 4m-1a11 a12 a21 a22 a33 a34 a43 . aij . a2m-1,2m a2m,2m写出由一对下标(i,j)求 k的转换公式。5.5 已知稀疏矩阵 A45如下： 70463251(1)用三元组表作为存储结构，绘出相应的三元组表示意图；(2)用十字链表作为存储结构，绘出相应的十字链表示意图。5.6 设稀疏矩阵 A和 B均以三元组顺序表作为存储结构。试写出计算矩阵相加CAB 的算法，其中，C 是另设的、存放结

12、果的三元组表（提示：可用类似于两个有序顺序表归并的处理方法） 。5.7 试编写一个算法，实现以三元组的形式打印用十字链表表示的稀疏矩阵中所有非零元素及其下标。5.8 试编写一个算法，实现以矩形阵列的形式打印用十字链表表示的稀疏矩阵。第六章 树和二叉树6.1 试分别绘出具有 3个结点的树和 3个结点的二叉树的所有不同形态。6.2 设结点 X是二叉树上一个度为 1的结点，X 有几个子树？6.3 描述满足下列条件的二叉树形态：(1) 先序遍历序列与中序遍历序列相同；(2) 后序遍历序列与中序遍历序列相同；(3) 先序遍历序列与后序遍历序列相同；6.4 一个深度为 H的满 k叉树有如下性质：第 H层上

13、所有结点都是叶子结点，其余各层上每个结点都有 k棵非空子树。如果从 1开始按自上而下、自左向右的次序对全部结点编号，问：(1) 各层的结点数目是多少？第 8 页(2) 编号为 i的结点的父结点(若存在)的编号是多少？(3) 编号为 i的结点的第 j个孩子(若存在)的编号是多少？(4) 编号为 i的结点有右兄弟的条件是什么？其右兄弟的编号是多少？6.5 已知一棵度为 k的树中有 n1个度为 1的结点，n2 个度为 2的结点，.，nk 个度为 k的结点，问该树中有多少个叶子结点？6.6 已知在一棵含有 n个结点的树中，只有度为 k的分支结点和度为 0的叶子结点。试求该树含有的叶子结点的数目。6.7

14、 设 n和 m为二叉树中两个结点，用 “1”、 “0”、和“” （分别表示肯定，否定和不一定）填写下表：已知 问 先序遍历时n在 m之前？ 中序遍历时n在 m之前？ 后序遍历时n在 m之前？n在 m左方n在 m右方n是 m祖先n是 m子孙（注：如果离 n 和 m 的最近的共同祖先 X 存在，且 n 位于 X 的左子树中，m 位于 X 的右子树中，则称“n 在 m 的左方”或“m 在 n 的右方” 。 ）6.8已知一棵树如图 6-1所示，画出与该树对应的二叉树，并写出该树的先根遍历序列和后根遍历序列。AB C DE F G HKI J图 6-1第 9 页6.9 将如图 6-2所示的森林转化为对应

15、的二叉树。K图 6-2AC D EBF GHJI LM NO6.10 画出和下列二叉树（如图 6-3所示）相应的森林。图 6-3AB CCABCABAD EB CFG HJ K LI6.11已知某二叉树的中序序列为 DCBGEAHFIJK，后序序列为DCEGBFHKJIA。请画出该二叉树。6.12 已知树 T 的先根遍历访问序列为 GFKDAIEBCHJ，后根遍历访问序列为第 10 页图 7-1V5V4V2V3V1V6DIAEKFCJHBG。请画出树 T。6.13 已知森林 F 的先根遍历访问序列为 ABCDEFGHIJKL，中根遍历访问序列为 CBEFDGAJIKLH。请画出这个森林 F。6

16、.14 假设某个电文由(a,b,c,d,e,f,g,h)8 个字母组成，每个字母在电文中出现的次数分别为(7,19,2,6,32,3,21,10)，试解答下列问题：(1) 画出出 huffman树；(2) 写出每个字母的 huffman编码；(3) 在对该电文进行最优二进制编码处理后，电文的二进制位数。6.15 写出复制一棵二叉树的算法。6.16 试编写算法，实现将二叉树所有结点的左右子树互换。6.17 写出按层次遍历二叉树的算法。6.18 写出判断给定二叉树是否为完全二叉树的算法。6.19 写出判断两棵给定二叉树是否相似的算法。(注：两棵二叉树 B1 和 B2 相似是指：B1 和 B2 皆空，或者皆不空且 B1 的左、右子树和 B2 的左、右子树分别相似。)6.20 利用栈的基本操作，写出二叉树先序遍历的非递归算法。6.21 写出统计树中叶子结点个数的算法，树用孩子兄弟链表表示。6.22 写出计算树的深度的算法，树用孩子兄弟链表表示。6.23 写出计算二叉树第 K层结点数的算法。6.24 写出计算二叉树深度的算法。第七章 图7.1 已知有向图如图 7-1所示，请给出该图的(1)邻接矩阵示意图