没有合适的资源?快使用搜索试试~ 我知道了~
首页严尉敏教授详解清华数据结构练习题及概念解析
严尉敏教授详解清华数据结构练习题及概念解析
需积分: 9 4 下载量 159 浏览量
更新于2024-07-31
收藏 1.29MB PDF 举报
在清华大学严尉敏教授的数据结构练习题祥解中,章节一"绪论"深入探讨了数据和信息的基本概念。首先,信息被定义为广义上的消息,是现实世界现象在人脑中的抽象,具有可识别、存储等一系列特性。数据则是信息的具体表现形式,是计算机处理的载体,如数字、字符,包括所有能输入计算机并被程序识别的信息。数据结构则涵盖了数据本身以及它们之间的关系,通常包括三个方面的讨论:逻辑结构、物理结构和操作。 逻辑结构关注数据成员及其关系,它是从问题的角度抽象出的数据模型,与计算机的存储方式无关。比如,线性结构和非线性结构是逻辑结构的重要分类,线性结构如数组和链表,数据元素之间按线性顺序排列,而非线性结构如树和图,数据元素之间存在更为复杂的关系。 物理结构即数据在计算机存储器中的实际布局,它是逻辑结构的计算机实现,会受到硬件限制和优化策略的影响。数据操作则是一系列针对数据结构定义的运算,如查找、插入、删除等,这些操作直接影响数据结构的性能和效率。 这部分内容强调了数据结构设计的核心,即如何根据实际问题的需求选择合适的数据结构,并理解其在存储和处理上的特性和优化。通过严尉敏教授的讲解,读者能够更好地理解和应用数据结构,提升编程技能。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/3118741/bg10.jpg)
《数据结构与算法分析》――例题选编(二) 第 2 章 数组
瞿有甜 整理编辑 完成日期:2006 年 10 月 共:153 页 第 14 页
i=0,1,…,last):
template<Type> void SeqList<Type> :: InsNo#i ( int i, Type& x ) {
if ( last == MaxSize-1|| i < 0 || i > last+1 ) //表满或参数 i 不合理, 中止操作返回
{ cerr << “ List is Full or Parameter is out range! ” << endl; exit(1); }
for ( int j = last; j >= i; j-- ) //空出位置以便插入, 若 i=last+1, 此循环不做
data[j+1] = data[j];
data[i] = x; //插入
last++; //表最后元素位置加 1
}
(4) 从顺序表中删除具有给定值 x 的所有元素。
template<Type> void SeqList<Type> :: DelValue ( Type& x ) {
int i = 0, j;
while ( i <= last ) //循环, 寻找具有值 x 的元素并删除它
if ( data[i] == x ) { //删除具有值 x 的元素, 后续元素前移
for ( j = i; j < last; j++ ) data[j] = data[j+1];
last--; //表最后元素位置减 1
}
else i++;
}
(5) 实现删除其值在给定值 s 与 t 之间(要求 s 小于 t)的所有元素的函数如下:
template<Type> void SeqList<Type> :: DelNo#sto#t ( Type& s, Type& t ) {
if ( last == -1 || s >= t )
{ cerr << “List is empty or parameters are illegal!” << endl; exit(1); }
int i = 0, j;
while ( i <= last ) //循环, 寻找具有值 x 的元素并删除它
if ( data[i] >= s && data[i] <= t ) { //删除满足条件的元素, 后续元素前移
for ( j = i; j < last; j++ ) data[j] = data[j+1];
last--; //表最后元素位置减 1
}
else i++;
}
(6) 实现从有序顺序表中删除其值在给定值 s 与 t 之间的所有元素的函数如下:
template<Type> void SeqList<Type> :: DelNo#sto#t1 ( Type& s, Type& t ) {
if ( last == -1 || s >= t )
{ cerr << “List is empty or parameters are illegal!” << endl; exit(1); }
for ( int i = 0; i <= last; i++ ) //循环, 寻找值 ≥s 的第一个元素
if ( data[i] >= s ) break; //退出循环时, i 指向该元素
if ( i <= last ) {
for ( int j = 1; i + j <= last; j++ ) //循环, 寻找值 > t 的第一个元素
if ( data[i+j] > t ) break; //退出循环时, i+j 指向该元素
for ( int k = i+j; k <= last; k++ ) //删除满足条件的元素, 后续元素前移
data[k-j] = data[k];
last-= j;
//表最后元素位置减 j
}
![](https://csdnimg.cn/release/download_crawler_static/3118741/bg11.jpg)
《数据结构与算法分析》――例题选编(二) 第 2 章 数组
瞿有甜 整理编辑 完成日期:2006 年 10 月 共:153 页 第 15 页
}
(7) 实现将两个有序顺序表合并成一个新的有序顺序表的函数如下:
template<Type> SeqList<Type>& SeqList<Type> :: Merge ( SeqList<Type>& A, SeqList<Type>& B )
{
//合并有序顺序表 A 与 B 成为一个新的有序顺序表并由函数返回
if ( A.Length() + B.Length() > MaxSize )
{ cerr << “The summary of The length of Lists is out MaxSize!” << endl; exit(1); }
Type value1 = A.Fist ( ), value2 = B.Fisrt ( );
int i = 0, j = 0, k = 0;
while ( i < A.length ( ) && j < B.length ( ) ) { //循环, 两两比较, 小者存入结果表
if ( value1 <= value2 )
{ data[k] = value1; value1 = A.Next ( ); i++; }
else { data[k] = value2; value2 = B.Next ( ); j++; }
k++;
}
while ( i < A.Length ( ) ) //当 A 表未检测完, 继续向结果表传送
{ data[k] = value1; value1 = A.Next ( ); i++; k++; }
while ( j < B.Length ( ) ) //当 B 表未检测完, 继续向结果表传送
{ data[k] = value2; value2 = B.Next ( ); j++; k++; }
last = k – 1;
return *this;
}
(8) 实现从表中删除所有其值重复的元素的函数如下:
template<Type> void SeqList<Type> :: DelDouble ( ) {
if ( last == -1 )
{ cerr << “List is empty!” << endl; exit(1); }
int i = 0, j, k; Type temp;
while ( i <= last ) { //循环检测
j = i + 1; temp = data[i];
while ( j <= last ) { //对于每一个 i, 重复检测一遍后续元素
if ( temp == data[j] ) { //如果相等, 后续元素前移
for ( k = j+1; k <= last; k++ ) data[k-1] = data[k];
last--; //表最后元素位置减 1
}
else j++;
}
i++; //检测完 data[i], 检测下一个
}
}
2-9 设有一个 n×n 的对称矩阵 A,如图(a)所示。为了节约存储,可以只存对角线及对角线
以上的元素,或者只存对角线或对角线以下的元素。前者称为上三角矩阵,后者称为下三
角矩阵。我们把它们按行存放于一个一维数组 B 中,如图(b)和图(c)所示。并称之为对称矩
阵 A 的压缩存储方式。试问:
(1) 存放对称矩阵 A 上三角部分或下三角部分的一维数组 B 有多少元素?
![](https://csdnimg.cn/release/download_crawler_static/3118741/bg12.jpg)
《数据结构与算法分析》――例题选编(二) 第 2 章 数组
瞿有甜 整理编辑 完成日期:2006 年 10 月 共:153 页 第 16 页
(2) 若在一维数组 B 中从 0 号位置开始存放,则如图(a)所示的对称矩阵中的任一元素
a
ij
在只存上三角部分的情形下(图(b))应存于一维数组的什么下标位置?给出计算公式。
(3) 若在一维数组 B 中从 0 号位置开始存放,则如图(a)所示的对称矩阵中的任一元素
a
ij
在只存下三角部分的情形下(图(c))应存于一维数组的什么下标位置?给出计算公式。
【解答】
(1) 数组 B 共有 n + ( n-1 ) +xxxxxx + 1= n * ( n+1 ) / 2 个元素。
(2) 只存上三角部分时,若 i ≤ j,则数组元素 A[i][j]前面有 i-1 行(1∼i-1,第 0 行第 0
列不算),第 1 行有 n 个元素,第 2 行有 n-1 个元素,xxxxxx,第 i-1 行有 n-i+2 个元素。在
第 i 行中,从对角线算起,第 j 号元素排在第 j-i+1 个元素位置(从 1 开始),因此,数组
元素 A[i][j]在数组 B 中的存放位置为
n + (n-1) + (n-2) + xxxxxx + (n-i+2) + j-i+1
= (2n-i+2) * (i-1) / 2 + j-i+1
= (2n-i) * (i-1) / 2 + j
若 i > j,数组元素 A[i][j]在数组 B 中没有存放,可以找它的对称元素 A[j][i]。在
数组 B 的第 (2n-
j) * (j-1) / 2 + i 位置中找到。
如果第 0 行第 0 列也计入,数组 B 从 0 号位置开始存放,则数组元素 A[i][j]在数组 B
中的存放位置可以改为
当 i ≤ j 时,= (2n-i+1) * i / 2 + j - i = ( 2n - i - 1 ) * i / 2 + j
当 i > j 时,= (2n - j - 1) * j / 2 + i
(3) 只存下三角部分时,若 i ≥ j,则数组元素 A[i][j]前面有 i-1 行(1∼i-1,第 0 行第 0
列不算),第 1 行有 1 个元素,第 2 行有 2 个元素,xxxxxx,第 i-1 行有 i-1 个元素。在第 i
行中,第 j 号元素排在第 j 个元素位置,因此,数组元素 A[i][j]在数组 B 中的存放位置为
1 + 2 + xxxxxx + (i
-1) + j = ( i-1)*i / 2 + j
若 i < j,数组元素 A[i][j]在数组 B 中没有存放,可以找它的对称元素 A[j][i]。在
数组 B 的第 (j-1)*j / 2 + i 位置中找到。
如果第 0 行第 0 列也计入,数组 B 从 0 号位置开始存放,则数组元素 A[i][j]在数组 B
中的存放位置可以改为
当 i ≥ j 时,= i*(i+1) / 2 + j
当 i < j 时,= j*(j+1) / 2 + i
2-10 设 A 和 B 均为下三角矩阵,每一个都有 n 行。因此在下三角区域中各有 n(n+1)/2 个
元素。另设有一个二维数组 C,它有 n 行 n+1 列。试设计一个方案,将两个矩阵 A 和 B 中
的下三角区域元素存放于同一个 C 中。要求将 A 的下三角区域中的元素存放于 C 的下三
角区域中,B 的下三角区域中的元素转置后存放于 C 的上三角区域中。并给出计算 A 的矩
阵元素 a
ij
和 B 的矩阵元素 b
ij
在 C 中的存放位置下标的公式。
![](https://csdnimg.cn/release/download_crawler_static/3118741/bg13.jpg)
《数据结构与算法分析》――例题选编(二) 第 2 章 数组
瞿有甜 整理编辑 完成日期:2006 年 10 月 共:153 页 第 17 页
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
−−−−−−−
−−
−−
−−
1111121110
1222222120
1121111110
1020100000
nnnnnnn
nn
nn
nn
baaaa
bbaaa
bbbaa
bbbba
C
L
LLLLL
L
L
⎩
⎨
⎧
<
≥
=
时当
时当
],][[
],][[
]][[
jiijC
jijiC
jiA
【解答】
计算公式
2-11 在实际应用中经常遇到的稀疏矩
阵是三对角矩阵,如右图所示。在该矩
阵中除主对角线及在主对角线上下最临
近的两条对角线上的元素外,所有其它
元素均为 0。现在要将三对角矩阵 A 中
三条对角线上的元素按行存放在一维数
组 B 中,且 a
11
存放于 B[0]。试给出计
算 A在三条对角线上的元素 a
ij
(1≤ i ≤ n,
i-1 ≤ j ≤ i+1)在一维数组 B 中的存放位置的计算公式。
【解答】
在 B 中的存放顺序为 [ a
11
, a
12
, a
21
, a
22
, a
23
, a
32
, a
33
, a
34
, …, a
n n-1
, a
nn
],总共有 3n-2 个非
零元素。元素 a
ij
在第 i 行,它前面有 3(i-1)-1 个非零元素,而在本行中第 j 列前面有 j-i+1
个,所以元素 a
ij
在 B 中位置为 2*i+j-3。
2-12 设带状矩阵是 n×n 阶的方阵,其中所有的非零元素都
在由主对角线及主对角线上下各 b 条对角线构成的带状区域
内,其它都为零元素。试问:
(1) 该带状矩阵中有多少个非零元素?
(2) 若用一个一维数组 B 按行顺序存放各行的非零元
素,且设 a
11
存放在 B[0]中,请给出一个公式,计算任一非
零元素 a
ij
在一维数组 B 中的存放位置。
【解答】
(1) 主对角线包含 n 个非零元素,其上下各有一条包含 n-1 个非零元素的次对角线,
再向外,由各有一条包含 n-2 个非零元素的次对角线,……,最外层上下各有一条包含 n-b
个非零元素的次对角线。则总共的非零元素个数有
n + 2(n-1) + 2(n-2) + … + 2(n-b) = n + 2( (n-1) + (n-2 ) + … + (n-b) )
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
−−−− 111110
1110
00
nnnn
aaa
aa
a
A
L
OLL
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
−−−− 111110
1110
00
nnnn
bbb
bb
b
B
L
OLL
⎩
⎨
⎧
<+
≥+
=
时当
时当
],1][[
],1][[
]][[
jijiC
jiijC
jiB
![](https://csdnimg.cn/release/download_crawler_static/3118741/bg14.jpg)
《数据结构与算法分析》――例题选编(二) 第 2 章 数组
瞿有甜 整理编辑 完成日期:2006 年 10 月 共:153 页 第 18 页
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
−
−
0020090
0000000
0008000
0300040
14000000
0130011012
(2)
在用一个一维数组 B 按行顺序存放各行的非零元素时,若设 b≤n/2,则可按各行
非零元素个数变化情况,分 3 种情况讨论。
① 当 1≤i≤b+1 时,矩阵第 1 行有 b+1 个元素,第 2 行有 b+2 个元素,第 3 行有 b+3
个元素,……,第 i 行存有 b+i 个元素,因此,数组元素 A[i][j]在 B[ ]中位置分析如下:
第 i 行(i≥1)前面有 i-1 行,元素个数为 (b+1)+(b+2)+…+(b+i-1) = (i-1)*b+i*(i-1)/2,
在第
i 行第 j 列(j≥1)前面有 j-1 个元素,则数组元素 A[i][j]在 B[ ]中位置为
② 当 b+1<i≤n-b+1 时,各行都有 2b+1 个元素。因为数组 A[ ][ ]前 b 行共有
b*b+(b+1)*b/2 = b*(3*b+1)/2 个元素,所以数组元素 A[i][j]在 B[ ]中位置为
③ 当 n-b+1<i≤n 时,各行元素个数逐步减少。当 i=n-b+1 时有 2b 个非零元素,当
i=n-b+2 时有 2b-1 个非零元素,当 i=n-b+3 时有 2b-2 个非零元素,…,当 i=n 时有 b+1
个非零元素。因为前面 n-b 行总共有 b*(3*b+1)/2+(n-2*b)*(2*b+1)个非零元素,所以在最
后各行数组元素
A[i][j]在 B[ ]中位置为
2
-13 稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。稀
疏矩阵有多少行,在行指针数组中就有多少个元素:第
i 个元素的
数组下标
i 代表矩阵的第 i 行,元素的内容即为稀疏矩阵第 i 行的第
一个非零元素在二元组表中的存放位置。二元组表中每个二元组只
记录非零元素的列号和元素值,且各二元组按行号递增的顺序排列。
试对右图所示的稀疏矩阵,分别建立它的三元组表和带行指针数组
的二元组表。
【解答】
2
-14 字符串的替换操作 replace (String &s, String &t, String &v)是指:若 t 是 s 的子串,则
用串
v 替换串 t 在串 s 中的所有出现;若 t 不是 s 的子串,则串 s 不变。例如,若串 s 为
“aabbabcbaabaaacbab”,串 t 为“bab”,串 v 为“abdc”,则执行 replace 操作后,串 s 中的结果
为
“aababdccbaabaaacabdc”。试利用字符串的基本运算实现这个替换操作。
2
b-b-1)n(2b1)bb(2nn
2
b))b(n1)((n
*2n +=−−+=
−+−
+=
()
1j
2
1)(i*i
b*1i −+
−
+−
bij1)b*(2*1)b(i
2
1)b*(3*b
+−++−−+
+
bij
2
2)bnib*(4*1)bn(i
1)b*(2*b)*2(n
2
1)b*(3*b
+−+
+−+−−+−
++−+
+
行指针数组
row
0
0
1 3
2 4
3 6
4 7
5 7
二元组表 data
col value
0 0 12
12 11
2 5 13
3 6 14
41
-4
55 3
63 8
71
-9
剩余152页未读,继续阅读
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/88017491f231415884e49a5a3bdd0285_sandyzjc008.jpg!1)
MrZhong.cn
- 粉丝: 4
- 资源: 41
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- Hadoop生态系统与MapReduce详解
- MDS系列三相整流桥模块技术规格与特性
- MFC编程:指针与句柄获取全面解析
- LM06:多模4G高速数据模块,支持GSM至TD-LTE
- 使用Gradle与Nexus构建私有仓库
- JAVA编程规范指南:命名规则与文件样式
- EMC VNX5500 存储系统日常维护指南
- 大数据驱动的互联网用户体验深度管理策略
- 改进型Booth算法:32位浮点阵列乘法器的高速设计与算法比较
- H3CNE网络认证重点知识整理
- Linux环境下MongoDB的详细安装教程
- 压缩文法的等价变换与多余规则删除
- BRMS入门指南:JBOSS安装与基础操作详解
- Win7环境下Android开发环境配置全攻略
- SHT10 C语言程序与LCD1602显示实例及精度校准
- 反垃圾邮件技术:现状与前景
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)