数据结构简明教程学习与上机实验指导

本书是《数据结构简明教程（第2版）》配套教材，提供实验及习题解析。

第1章概论
1.1练习题1及参考答案
1.1.1练习题1
1.1.2练习题1参考答案
1.2上机实验题1及参考答案
1.2.1上机实验题1
1.2.2上机实验题1参考答案
第2章线性表
2.1练习题2及参考答案
2.1.1练习题2
2.1.2练习题2参考答案
2.2上机实验题2及参考答案
2.2.1上机实验题2
2.2.2上机实验题2参考答案
第3章栈和队列
3.1练习题3及参考答案
3.1.1练习题3
3.1.2练习题3参考答案
3.2上机实验题3及参考答案
3.2.1上机实验题3
3.2.2上机实验题3参考答案
第4章串
4.1练习题4及参考答案
4.1.1练习题4
4.1.2练习题4参考答案
4.2上机实验题4及参考答案
4.2.1上机实验题4
4.2.2上机实验题4参考答案
第5章数组和稀疏矩阵
5.1练习题5及参考答案
5.1.1练习题5
5.1.2练习题5参考答案
5.2上机实验题5及参考答案
5.2.1上机实验题5
5.2.2上机实验题5参考答案
第6章树和二叉树
6.1练习题6及参考答案
6.1.1练习题6
6.1.2练习题6参考答案
6.2上机实验题6及参考答案
6.2.1上机实验题6
6.2.2上机实验题6参考答案
第7章图
7.1练习题7及参考答案
7.1.1练习题7
7.1.2练习题7参考答案
7.2上机实验题7及参考答案
7.2.1上机实验题7
7.2.2上机实验题7参考答案
第8章查找
8.1练习题8及参考答案
8.1.1练习题8
8.1.2练习题8参考答案
8.2上机实验题8及参考答案
8.2.1上机实验题8
8.2.2上机实验题8参考答案
第9章排序
9.1练习题9及参考答案
9.1.1练习题9
9.1.2练习题9参考答案
9.2上机实验题9及参考答案
9.2.1上机实验题9
9.2.2上机实验题9参考答案

　　第5章数组和稀疏矩阵
　　5.1练习题5及参考答案
　　5.1.1练习题5
　　1. 单项选择题
　　（1） 有一个三维数组A［-2..2］［-4..5］［2..6］，其元素个数是（）。
　　A. 60B. 250C. 144D. 396
　　（2） 设二维数组A［1..5］［1..8］，若按行优先的顺序存放数组的元素，则A［4］［6］元素的前面有（）个元素。
　　A. 6B. 28C. 29D. 40
　　（3） 设二维数组A［1..5］［1..8］，若按列优先的顺序存放数组的元素，则A［4］［6］元素的前面有（）个元素。
　　A. 6B. 28C. 29D. 40
　　（4） 一个n阶对称矩阵A采用压缩存储方式，将其下三角部分按行优先存储到一维数组B中，则B中元素个数是（）。
　　A. nB. n2
　　C. n（n+1）/2D. n（n+1）/2+1
　　（5） 一个n阶对称矩阵A［1..n，1..n］采用压缩存储方式，将其下三角部分按行优先存储到一维数组B［1..m］中，则A［i］［j］（i≥j）元素在B中的位置k是（）。
　　A. j（j-1）/2+iB. j（j-1）/2+i-1
　　C. i（i-1）/2+jD. i（i-1）/2+j-1
　　（6） 一个对称矩阵A［1..10,1..10］采用压缩存储方式，将其下三角部分按行优先存储到一维数组B［0..m］中，则A［8］［5］元素在B中的位置k是（）。
　　A. 32B. 37C. 45D. 60
　　（7） 一个对称矩阵A［1..10,1..10］采用压缩存储方式，将其下三角部分按行优先存储到一维数组B［0..m］中，则A［5］［8］元素值在B中的位置k是（）。
　　A. 18B. 32C. 45D. 60
　　（8） 一个对称矩阵A［1..10，1..10］采用压缩存储方式，将其上三角部分按行优先存储到一维数组B［1..m］中，则A［8］［5］元素值在B中的位置k是（）。
　　A. 10B. 37C. 45D. 60
　　（9） 一个n阶上三角矩阵A按列优先顺序压缩存放在一维数组B，则B中元素个数是（）。
　　A. nB. n2C. n（n+1）/2D. n（n+1）/2+1
　　（10） 一个10阶下三角矩阵A［0..9，0..9］按行优先压缩存放在一维数组B［0..m］中，则A［3］［2］在B中的位置k是（）。
　　A. 1B. 8C. 10D. 21
　　（11） 对特殊矩阵采用压缩存储的目的主要是为了（）。
　　A. 表达变得简单B. 对矩阵元素的存取变得简单
　　C. 去掉矩阵中的多余元素D. 减少不必要的存储空间
　　（12） 稀疏矩阵是指（）的矩阵。
　　A. 非零元素较多且分布无规律B. 非零元素较少且分布无规律
　　C. 总元素个数较少D. 不适合用二维数组表示
　　（13） 稀疏矩阵一般的压缩存储方法有两种，即（）。
　　A. 二维数组和三维数组B. 三元组和散列
　　C. 三元组和十字链表D. 散列和十字链表
　　（14） 一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去（）特性。
　　A. 顺序存储B. 随机存取C. 输入输出D. 以上都不对
　　（15） 一个m行n列的稀疏矩阵采用十字链表表示时，其中总的头结点的个数为（）。
　　A. m+1B. n+1
　　C. m+n+1D. MAX{m，n}+1
　　2. 填空题
　　（1） 三维数组A［c1..d1，c2..d2，c3..d3］（c1≤d1，c2≤d2，c3≤d3）共含有（）个元素。
　　（2） 已知二维数组A［m］［n］采用行序为主序存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC（A［0］［0］），则A［i］［j］的地址是（）。
　　（3） 二维数组A［10］［20］采用列序为主序存储，每个元素占一个存储单元，并且A［0］［0］的存储地址是200，则A［6］［12］的地址是（）。
　　（4） 二维数组A［10..20］［5..10］采用行序为主方式存储，每个元素占4个存储单元，并且A［10］［5］的存储地址是1000，则A［18］［9］的地址是（）。
　　（5） 有一个10阶对称矩阵A，采用压缩存储方式（以行序为主存储下三角部分，且A［0］［0］存放在B［1］中），则A［8］［5］在B中的地址是（）。
　　（6） 设n阶下三角矩阵A［1..n］［1..n］已压缩到一维数组B［1..n（n+1）/2］中，若按行序为主存储，则A［i］［j］对应的B中的存储位置是（）。
　　（7） 稀疏矩阵的三元组表示中，每个结点对应于稀疏矩阵的一个非零元素，它包含三个数据项，分别表示该元素的（）。
　　3. 简答题
　　（1） 简述数组的主要基本运算。
　　（2） 为什么说数组是线性表的推广或扩展，而不说数组就是一种线性表呢？
　　（3） 为什么数组一般不采用链式结构存储？
　　（4） 如果一维数组A中元素个数n很大，存在大量重复的元素，且所有元素值相同的元素紧挨在一起，请设计一种压缩存储方式使得存储空间更节省。
　　4. 算法设计题
　　（1） 假定数组A［0..n-1］的n个元素中有多个零元素，设计一个算法将A中所有的非零元素全部移到A的前端。
　　（2） 有一个含有n个整数元素的数组a［0..n-1］，设计一个算法通过比较求a［i..j］中的第一个最小元素的下标。
　　（3） 设计一个算法，求一个n×n的二维整型数组A的下三角和主对角部分的所有元素之和。
　　（4） 设计一个算法，给定一个n×n的二维整型数组A，按位置输出其中左上右下和左下右上两条对角线的元素。
　　5.1.2练习题5参考答案
　　1. 单项选择题
　　（1） B（2） C（3） B（4） C（5） C
　　（6） A（7） B（8） B（9） D（10） B
　　（11） D（12） B（13） C（14） B（15） D
　　2. 填空题
　　（1） （d1-c1+1）×（d2-c2+1）×（d3-c3+1）
　　（2） LOC（A［0］［0］）+（n×i+j）×k
　　（3） 326
　　（4） 1208
　　（5） 42
　　（6） i（i-1）/2+j
　　（7） 行下标、列下标和元素值
　　3. 简答题
　　（1） 答： 数组的主要基本运算如下。
　　① 取值运算： 给定一组下标，读取其对应的数组元素。
　　② 赋值运算： 给定一组下标，存储或修改与其相对应的数组元素。
　　（2） 答： 从逻辑结构的角度看，一维数组是一种线性表； 二维数组可以看成数组元素为一维数组的一维数组，所以二维数组是线性结构，可以看成是线性表，但就二维数组的形状而言，它又是非线性结构，因此将二维数组看成是线性表的推广更准确。三维及以上维的数组也是如此。
　　（3） 答： 因为数组使用链式结构存储时需要额外占用更多的存储空间，而且不具有随机存取特性，使得相关操作更复杂。
　　（4） 答： 设数组的元素类型为ElemType，采用一种结构体数组B来实现压缩存储，该结构体数组的元素类型如下。
　　……

　　F O R E W O R D
　　前言
　　本书是《数据结构简明教程》(第2版，李春葆等编著，清华大学出版社，以下简称为《教程》)的配套学习与上机实验指导书。全书共分为9章，章次安排与《教程》相对应。
　　书中练习题共401道(含单项选择题170道，填空题112道，简答题62道，算法设计题57道)，上机实验题共118道(含基础实验题37道，应用实验题81道)。
　　所有练习题均给出了参考答案，算法设计题包含算法设计思路和完整的C/C++语言描述代码。所有上机实验题均上机调试通过。考虑向下的兼容性，所有程序调试执行采用低版本的Visual C++ 6.0作为编程环境，稍加修改，可以在Dev C++或者其他更高版本的编程环境中执行。全部上机实验题的源程序代码可以从清华大学出版社网站http://www.tup.edu.cn免费下载。
　　书中同时列出了全部练习题和上机实验题，因此自成一体，可以脱离《教程》单独使用。
　　由于水平所限，尽管编者不遗余力，书中仍可能存在疏漏和不足之处，敬请教师和同学们批评指正。
　　编者2018年12月