最终的所有19数据结构习题解答

1、数据结构习题解答第1题：见教材前3页数据：客观十五采用计算机进行识别、存储和加工所进行的描述，统称为数据。数据元素：数据的基本单位。数据结构：讨论计算机系统中数据的组织形式及其相互关系。包括逻辑结构、存储结构以及操作。第3题：数据逻辑结构：描述数据元素之间的逻辑关系。是数据元素之间的逻辑关系的集合。逻辑结构主要分为：线性结构，非线性结构（树结构、图结构）第4题：数据的存储结构：数据元素在计算机系统存储器里的存储方法。存储方法包括：顺序存储方法、链接存储方法、索引存储方法、散列存储方法。第9题：分析：这是一个顺序存储的线性表。数组A的最大空间为MAXNUM个，线性表有elenum个元素。如果el

2、enum1MAXNUM就不能在A中增加元素在顺序存储的线性表中增加元素时，要从表尾开始逐个向后挪动元素，以腾出空间根据题意，新元素应放置在挪动元素过程中遇到的第一个比新元素小的元素后面。10. A(x) = 1+5x+7x3-9x7+5x16 B(x) = 4x+7x4+4x7-3x15+x1614477415-31610115377-9165A(x)+B(x) = 1+9x+7x3 +7x4-5x7 -3x15 +6x16011937477-515-316611. 编号为1,2,3,4的四辆车不可能的出栈顺序有： 3 1 2 4 2 1 3 4 2 3 1栈0（top0）入栈：栈顶1；满：t

3、op0+1=top1出栈：栈顶1；空：top0=-1；栈1 （top1）入栈：栈顶1；满：top1-1=top0出栈：栈顶1；空：top1=MAX栈底栈顶栈顶栈底sm栈1栈0s012.typedef struct elemtype sMAX; int top0; int top1;Dstack_type;13.入队时，判断队列是否已满 if(rear = front & tag = 1)入队后，如果队列已满就将tag置为1出队时，判断队列是否已空 if ( front = rear & tag = 0 )#define MAXNUM 10typedef struct Queue elemtyp

4、e QMAXNUM int rear, front, tag;Queue_type;14. 求稀疏矩阵A的三元组A67=1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 0 0 -4 0 0 0 0 0 0 0 0 0 0 -1 15 0 0 0 7 0 0 0T83=6 7 71 11 6 23 2 -34 2 -45 6 -15 7 156 4 715. 下三角矩阵A压缩存储于一维数组Sa中，A44 =3 0 0 0 2 -1 0 0 5 4 1 0 1 0 1 3 （1） Sa的元素个数为：10（2）a43在Sa中的下标为：816. 已知 A=“” ; B

5、=“MULE”; C=“OLE”; D=“MY”（1） A + B = “MULE”；（2） D + C + A = “MYOLE”;18. 三个结点的树（无序）：注意：无序树和有序树的区别19. 三个结点的二叉树：20. 先序：- + a b c d / e f中序：a + b c d e / f后序：a b c d - + e f / - - /+ab e - f cd21.（1） （2） （3）. . . . .22. ABCDEFGHABCDEFGH补充题： 二叉树的先序序列为：ABDECFGHI，中序序列为：DBEAFHGIC，画出此二叉树。ACBDEFGHI23.n个顶点的无向图，

6、用邻接矩阵表示（1）图的边=邻接矩阵中1的个数总和/2（2）若aij=1，则顶点i和j之间有边； 若aij=0，则顶点i和j之间没有边。（3）顶点i的度=该顶点所在行或列1的个数和。补充：已知一个图的邻接矩阵或邻接表，如何判断此图是有向图还是无向图？邻接矩阵为对称阵则为无向图，反之为有向图；邻接表中若任意顶点i开始的单链表中存在邻接顶点j，同时顶点j开始的单链表中存在邻接顶点i，则为无向图。24.（1）0 1 1 0 0 0 0 11 0 0 1 1 0 1 01 0 0 0 0 1 0 00 1 0 0 0 0 1 00 1 0 0 0 0 1 00 0 1 0 0 0 0 10 1 0 1

7、 1 0 0 01 0 0 0 0 1 0 0FHKGIJML(2) GFHKMILJ (3) GFILJHMKdataFGHMdataGFIdataHFKdataIGLdataJGLLJdataKHMLMdatadataIGJKF26.k=43（1）low:0 high:7 mid:3（2）low:4 high:7 mid:5k=5（1）low:0 high:7 mid:3（2）low:0 high:2 mid:1（3）low:0 high:0 mid:027. 首先计算哈希值： Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, D

8、ec 5 3 6 0 6 5 5 0 9 7 7 2（1） 线性探测法：AprAugDecFebJanMarMayJunJulSepOctNovASL = (1+2+1+1+1+1+2+4+5+2+5+6) / 12 = 31/12151413121110987654321016（2）链地址法：ASL = 18 / 12Apr01Dec2Feb3Jan5Oct789Sep46Mar10MayJunJulAugNov28. 快速排序： (513, 87, 512, 61, 908, 170, 897, 275, 653, 462) (462, 87, 512, 61, 275, 170) 513

9、 (897, 653, 908) (170, 87, 275, 61) 462 (512) 513 (653) 897 (908) (61, 87) 170 (275) 462 512 513 653 897 908 61 87 170 275 462 512 513 653 897 908冒泡排序：513, 87, 512, 61, 908, 170, 897, 275, 653, 46287, 512, 61, 513, 170, 897, 275, 653, 462, 90887, 61, 512, 170, 513, 275, 653, 462, 897, 90861, 87, 170, 512, 275, 513, 462, 653, 897, 90861, 87, 170, 275, 512, 462, 513, 653, 897, 90861, 87, 170, 275, 462, 512, 513, 653, 897, 90861, 87, 170, 275, 462, 512, 513, 653, 897, 908归并排序：(1) 87,513,6