1、数据结构课后习题答案合集第一章 绪论1. 数据结构课程研究的内容是什么？其中哪个方面和计算机无关？答：非数值计算，包括数据的 逻辑结构、存储结构，操作的实现2. 数据结构按逻辑结构可分为哪几类？（不要简单答线性和非线性）3为什么要进行算法分析？（分析算法的效率以求改进），算法分析主要研究哪几个方面？（ 时间效率和空间效率，即：空间复杂性和时间复杂性） 4分析下面各程序段的时间复杂度。2. s=0; for i=0; in; i+)for(j=0; jn; j+) s+=Bij;sum=s;1. for (i=0; in; i+)for (j=0; jm; j+)Aij=0;3. x=0;for
2、(i=1; in; i+) for (j=1; j=n-i; j+)x+;解：因为x+共执行了n-1+n-2+1= n(n-1)/2，所以执行时间为O（n2）4. i=1; while(i=n) i=i*3;答：O（log3n）5、数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。设有数据逻辑结构S=（D,R），试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？ 1. 【严蔚敏习题集P7 1.3】D=d1,d2,d3,d4 R=(d1,d2),(d2,d3),(d3,d4) 答： d1d2d3d4
3、 d1无直接前驱，是首结点 d4无直接后继是尾结点1. D=d1,d2,d9 R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) 答： 此图为树形结构 d1无直接前驱，是根结点 d2,d5,d7,d9无直接后继是叶子结点2. D=d1,d2,d9 R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)答： 此图为图形结构 d1，d2无直接前驱，是开始结点 d6,d7无直接后继是终端结点
4、 (2) (3)学习方法提示：同学们一定要把教材阅读，理解以后再做题，暂时不要做那些针对考试的“茴香豆的茴有几种写法的题”，以后要参加那些考试的时候再说。平时一定要以理解为核心，没有必要把一些细枝末节，甲乙丙丁的条款记住，甚至有些说法，这样说也有理，那样说也有理，没有必要钻牛角尖。比如上面习题中，数据结构分几类，有的教材上写“线性和非线性二类”，有的写“线性，树，图三类”，还有的写“线性，树，图，集合四类”，作者是从不同的角度去看待的。作为学习，这个问题所谓的“标准答案”是次要的。不要强记公式，公式应该是自己理解，自己能推导出来。比如评价顺序表的删除操作的复杂度，你应该记得思路，而不是公式（完
5、全忘记了也没关系）。我本人就不记得很多公式，但是要用的时候知道怎么自己推导出来，知道去哪里找到这个公式，那就行了，有些公式，在自己的工作中老用老用的，自然就记住了。人的大脑是有限的，要把这有限的“存储容量”用来记住你要用的东西。至于将来要参加程序员的考试的时候，需要“标准答案”和考试速度的时候才需要多看那些试题及所谓的“标准答案”。那些考试，总是把一个简单的说法用很复杂的方式转弯抹角地说出来，但在学习的过程中应该抓住实质与核心，而不是把精力放在牛角尖上。在你不熟悉教材内容的时候，你发现那些说法都是晦涩难懂的，而当你渐渐地熟悉问题的实质以后，大多数问题对你来说都是自然而然的，是你自己能解决的。欢
6、迎大家共同讨论学习的方法。以后同学们和我的心得将整理以后继续发出。杨华 谨识第二章 线性表一、填空1、 向一个长度为n的向量的第i个元素(1in+1)之前插入一个元素时，需向后移动 n-i+1 个元素。 向一个长度为n的向量中删除第i个元素(1in)时，需向前移动 n-i 个元素。.2、 顺序表中插入或删除一个元素，需要平均移动 表中一半元素，具体移动的元素个数与 表长和该元素在表中的位置 有关。 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构。.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 108 ；向一个有1
7、27个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 63.5 个元素；3、在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。现有一个具有五个元素的线性表L=23，17，47，05，31，若它以链接方式存储在下列100119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下所示：05U17X23V31Y47Z100120其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？（10分）答：X= 116 Y= 0 Z= 100 首址= 108 末址= 112 （小心） 二、简答题1. 试比
8、较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答： 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（用动态分配的方法，一般都情况下都接近1），存储空间利用率高。缺点：插入或删除元素时不方便。顺序表才适合随机存取；链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针;优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（lchild&!T-rchild) return 1; /叶子结点 else return Leaf_Count(T-lch
9、ild)+Leaf_Count(T-rchild);/左子树的叶子数加 上右子树的叶子数 /LeafCount_BiTree 3.编写按层次顺序（同一层自左至右）遍历二叉树的算法。或：按层次输出二叉树中所有结点；解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，以此产生了按层次输出的效果。void LayerOrder(Bitree T)/层序遍历二叉树 InitQueue(Q); /建立工
10、作队列 EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,p); visit(p); if(p-lchild) EnQueue(Q,p-lchild); if(p-rchild) EnQueue(Q,p-rchild); /LayerOrder 第七章 图1. 在一个图中，所有顶点的度数之和等于图的边数的 2 倍。2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 1 倍。3. 有8个结点的无向图最多有 28 条边。4. 有8个结点的有向完全图有 56 条边。5. 有8个结点的无向连通图最少有 7 条边。6. 有向图G用邻接表矩阵存储，其第
11、i行的所有元素之和等于顶点i的 出度 。7. 设有一稀疏图G，则G采用 邻接表 存储较省空间。 设有一稠密图G，则G采用 邻接矩阵 存储较省空间。（选填邻接表/邻接矩阵）8. 如果n个顶点的图是一个环，则它有 n 棵生成树。 （以任意一顶点为起点，得到n-1条边）9. 已知图的邻接矩阵如下，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是 0 1 3 4 2 5 6 ，按广度优先遍历的结点序列是 0 1 2 3 4 6 5 。10. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是 0 1 2 3 。11. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是 0 3 2 1 。12. 用邻接表表示图进行广度优先遍历时，通常是采用 队列 来辅助实现算法的。13. 拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。14. 请对下图的无向带权图，
