数据结构所有练习和作业

1、 第一章练习第一章练习1. 1.数据结构就是研究（数据结构就是研究（ D D ）。）。A A数据的逻辑结构数据的逻辑结构 B B数据的存储结构数据的存储结构C C数据的逻辑结构和存储结构数据的逻辑结构和存储结构D D数据的逻辑结构、存储结构及其数据在运算数据的逻辑结构、存储结构及其数据在运算上的实现上的实现2. 2.一个算法的好坏取决于该算法的（一个算法的好坏取决于该算法的（ 空间复杂空间复杂度）和（度）和（ 时间复杂度时间复杂度 ）。）。 3. 3.下面程序的时间复杂度为（下面程序的时间复杂度为（ C C ）。）。For(i=0;im;i+)For(i=0;im;i+) For(j=0;jn

2、;j+) For(j=0;jn;j+)Aij=iAij=i* *j; j;A.O(mA.O(m2 2) )B. O(nB. O(n2 2) )C. O(nC. O(n* *m)m) D.O(n+m) D.O(n+m)4. 4.下面程序的时间复杂度为（下面程序的时间复杂度为（ O(log3(n) O(log3(n) ）。）。i=1;i=1;while(i=n)while(i=n)i=ii=i* *3; 3;假设代码执行次数是k，则i=3k-1因为i=n，i=3k-1=n,k=log3n+1,所以O(logn)3第二章第二章 练习练习 1.1.线性表线性表L=L=（a a1 1，a a2 2 ，a

3、an n，）下列说法正确的是（，）下列说法正确的是（ D D ）。）。 A A每个元素都有一个直接前驱和一个直接后继每个元素都有一个直接前驱和一个直接后继 B B线性表中至少要有一个元素线性表中至少要有一个元素 C C表中所有元素的排列顺序必须是由小到大或由大到小表中所有元素的排列顺序必须是由小到大或由大到小 D D除第一个和最后一个元素外，其余每个元素都有且仅有一个除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继直接前驱和一个直接后继 2.2.线性表采用链式存储时，其地址（线性表采用链式存储时，其地址（ D D ）。）。 A A必须连续必须连续B B部分地址必须连续

4、部分地址必须连续 C C必须连续必须连续D D连续与否均可连续与否均可 3 3下面关于线性表叙述错误的是（下面关于线性表叙述错误的是（ B B ）。）。 A A线性表采用顺序存储，必须占用一段地址连续的单元线性表采用顺序存储，必须占用一段地址连续的单元 B B线性表采用顺序存储，便于进行插入和删除操作线性表采用顺序存储，便于进行插入和删除操作 C C线性表采用链式存储，不必占用一段地址连续的单元线性表采用链式存储，不必占用一段地址连续的单元 D D线性表采用链式存储，便于进行插入和删除操作线性表采用链式存储，便于进行插入和删除操作 4 4若某线性表中最常用的操作是在最后一个元素之后插入一个若某

5、线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（元素和删除最后一个元素，则采用（ D D ）存储方式最节省运算）存储方式最节省运算时间。时间。 A A单链表单链表 B B双链表双链表 C C带头结点的双循环链表带头结点的双循环链表 D D容量足够大的顺序表容量足够大的顺序表 第二章作业第二章作业2.222.22 试写一算法试写一算法, ,对单链表实现就地逆置对单链表实现就地逆置, ,即利用原表的存储空间将线性表即利用原表的存储空间将线性表（a1,a2,a1,a2,an,an）逆置为（）逆置为（an,an-1,an,an-1,a1,a1）提示：提示：将原链表中的头

6、结点和第一个元素结将原链表中的头结点和第一个元素结点断开（令其指针域为空），先构成一个点断开（令其指针域为空），先构成一个空表，然后将原链表中各结点从第一个结空表，然后将原链表中各结点从第一个结点起依次插入这个新表的头部。点起依次插入这个新表的头部。2.112.11设顺序表设顺序表VaVa中的数据元素递增有序（非中的数据元素递增有序（非递减有序）。试写一算法，递减有序）。试写一算法，将将x x插入到顺序表的适当位置上，以保持该表插入到顺序表的适当位置上，以保持该表的有序性。的有序性。补充作业：补充作业：写出按写出按正位序正位序建立一个单链表的算法。建立一个单链表的算法。for (i = 1;

7、i data); / 输入元素值p-next = NULL; if (head-next = NULL) /如果链表只有头结点 head-next = p; q = p;else /如果头结点next不为空 q-next = p; q = p;第三章练习1.假定一个顺序循环队列存储于长度为假定一个顺序循环队列存储于长度为n的一维数组中，的一维数组中，其队头和队尾指针分别用其队头和队尾指针分别用front和和rear表示，则判断队满的表示，则判断队满的条件是（条件是（ D）*A（rear+1）%n=frontBfront+1=rearCrear=（front-1）%nDrear=（front+1

8、）%n2.假定一个顺序循环队列的队头和队尾指针分别用假定一个顺序循环队列的队头和队尾指针分别用front和和rear表示，则判队空的条件是（表示，则判队空的条件是（D）。）。Afront+1= =rearBfront= =rear+1Cfront= =0Dfront= =rear练习3.三个元素按照三个元素按照A,B,C的顺序入栈，下列哪一个是不合的顺序入栈，下列哪一个是不合法的出栈序列？（法的出栈序列？（B ） A. ABC B. CAB C. ACB D. BAC 4.堆栈的逻辑特点是（堆栈的逻辑特点是（ 先进后出先进后出 ），队列的逻辑特点），队列的逻辑特点是（先进先出是（先进先出 ）。

9、二者的共同点是只允许在它们的）。二者的共同点是只允许在它们的（ 端点端点 ）处插入和删除数据元素。）处插入和删除数据元素。5. 设输入元素的顺序为设输入元素的顺序为1,2,3,4,5，要在栈的输出端得到，要在栈的输出端得到43521，则应进行栈的基本运算表示应为：，则应进行栈的基本运算表示应为：Push（S,1）,Push(S,2),Push(S,3),Push(S,4),Pop(S,4),(Pop(S,3),Push(S,5),Pop(S,5)，Pop(S,2)，Pop(S,1)。练习6. 队列的插入操作是在队列的（队尾队列的插入操作是在队列的（队尾 ）进行，）进行，删除操作是在队列的（删除

10、操作是在队列的（ 队头队头 ）进行。）进行。7堆栈的逻辑特点是（堆栈的逻辑特点是（ 先进后出先进后出 ），队列），队列的逻辑特点是（先进先出的逻辑特点是（先进先出 ）。）。第三章作业3.1 设将整数设将整数1、2、3、4依次进栈，但只要出栈时栈依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答非空，则可将出栈操作按任何次序夹入其中，请回答下面问题：下面问题： （1）若入栈次序为）若入栈次序为push(1)，pop()，push(2），），push(3)，pop()，pop( )，push(4)，pop( )，则出栈，则出栈的数字序列为什么？的数字序列为什么？ （2）请分析）

11、请分析1、2、3、4的的24种排列中，哪些序列种排列中，哪些序列可以通过相应的入出栈得到。可以通过相应的入出栈得到。 4、3、1、2可能吗？可能吗？3.12 写出以下程序段的输出结果（队列中的元素写出以下程序段的输出结果（队列中的元素 类型类型QElemType 为为char）。）。Void main( ) Queue Q; InitQueue(Q); Char x=e, y=c; EnQueue(Q, h); EnQueue(Q, r); EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q, a); Wh

12、ile ( !QueueEmpty(Q) ) DeQueue(Q, y); Printf(y); Printf(x);第四章 习 题1.空串是（零个字符的串），其长度等于（ 0 ）。2.空格串是（一个或多个空格组成的串），其长度等于（ 串中空格字符的个数 ）。3.空串与空格串的区别在于：（ “” ）。4.两个字符串相等的充分必要条件是（字符串长度相同且对应位置字符相同）。长度相等，并且各个对应位置上的字符都相等。5.写出模式串p=“abaabcac”的next函数值序列为（01122312）。第五章 作 业5.1 假设有二维数组A 68，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的

13、起始存储位置（基地址）为1000，计算：（1）数组A的体积（即存储量）；（2）数组A的最后一个元素a57的第一个字节的地址；（3）按行存储时，元素a14的第一个字节的地址；（4）按列存储时，元素a47的第一个字节的地址。第五章 作 业5.10 求下列广义表操作的结果：（1）GetHead( (p, h, w) );（4） GetTail( (a ,b) ,(c ,d) );（5） GetHead ( GetTail ( (a,b),(c,d) ) )。5.12 画出下列广义表的存储结构图，并求它的长度。（1）( ( ( ) ) , a , ( ( b , c ) , ( ) , d ) , (

14、 ( ( e ) ) ) )（2）( ( ( ( a ) , b ) ) , ( ( ( ) , d ) , ( e , f ) ) ) 性质性质 1 ： 在二叉树的第在二叉树的第 i 层上至多有层上至多有2i-1 个结点。个结点。 (i1)二叉树中第二叉树中第5层上的结点个数最多为层上的结点个数最多为_C_A.8 B.15C.16 D.32第六章练习第六章练习 性质性质 2 ： 深度为深度为 k 的二叉树上至多含的二叉树上至多含 2k-1 个结点（个结点（k1）。）。深度为深度为5的二叉树至多有（的二叉树至多有（ C ）结点。）结点。A64 B32 C31 D63 性质性质 3 ： 对任何一

15、棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。1、一棵二叉树有、一棵二叉树有67个结点个结点,这些结点的度要么是这些结点的度要么是0，要么是要么是2。这棵二叉树中度数为。这棵二叉树中度数为2的结点有的结点有 33 个。个。1.将一棵有将一棵有100个结点的完全二叉树从上到下，从个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为左到右依次对结点进行编号，根结点的编号为1，则编号为则编号为49的结点的左孩子的编号为的结点的左孩子的编号为_A_。*左孩子2n，右孩子2n+1A.98 B.99 C.50 D.48练练 习习1. 假

16、设一棵二叉树的层序序列是假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是和中序序列是DBGEHJACIF,请画出该树。请画出该树。练练 习习1、一个哈夫曼、一个哈夫曼(Huffman)树有树有19个结点，则其个结点，则其叶结点的个数是叶结点的个数是 10 。哈弗曼树。哈弗曼树2n-1个节个节点，则有点，则有n个叶子节点。个叶子节点。2、一棵深度为、一棵深度为6的满二叉树有的满二叉树有 31 个分支结个分支结点和点和 32 个叶子。个叶子。2n- 1个节点，个节点，2n-1个个叶子叶子3、设二叉树结点的先序序列为、设二叉树结点的先序序列为ABDECFGH，中序序列为中序序列为DEBAF

17、CHG,则二叉树的后序序列则二叉树的后序序列是是EDBHFGCA 。 作 业1、已知一棵二叉树的中序序列和后序序列分已知一棵二叉树的中序序列和后序序列分别为：别为： DBGEACHF和和DGEBHFCA，则该二，则该二叉树的前序序列是什么？试画出这棵二叉树。叉树的前序序列是什么？试画出这棵二叉树。2.给定权值集合给定权值集合15,03,14,02,06,09,16,17，构造，构造相应的哈夫曼树，并计算它的带权路径长度。相应的哈夫曼树，并计算它的带权路径长度。 第七章第七章 练练 习习无向完全图具有（无向完全图具有（ 1/2n(n-1) ）条边。）条边。有向完全图具有有向完全图具有 （ n(n

18、-1) ）条边。）条边。图的遍历方式有（深度优先搜索图的遍历方式有（深度优先搜索 ）和（）和（ 广广度优先搜索度优先搜索 ）两种。）两种。 0 1 04.从邻接矩阵从邻接矩阵A= 1 0 1 可以看出，该图共有（可以看出，该图共有（ ） 0 1 0顶点。如果是无向图，则共有（）条边。顶点。如果是无向图，则共有（）条边。 练练 习习1.写出有向图写出有向图2的顶点的顶点V和弧和弧E的邻接矩阵，邻接表和的邻接矩阵，邻接表和逆邻接表逆邻接表。 练练 习习1.从顶点从顶点a出发写出深度优先搜索顺序和广度优先搜出发写出深度优先搜索顺序和广度优先搜索顺序。索顺序。abcdegf 练练 习习1.对于图所示的无向带权图，根据普里姆算法思想，对于图所示的无向带权图，根据普里姆算法思想，画出构造该无向带权图最小生成树的过程。画出构造该无向带权图最小生