（3）、将单链表逆置（不带表头结点）。
第 13 页 共 49 页
（4）、删除一个有序的单链表中其值重复的元素，使链表中所有元素的值均不同的
算法。
（5）、查找单链表中第i个元素的值的算法，如果给定的i值不合法或链表为空等
异常情况返回空值NULL；
第 14 页 共 49 页
《数据结构》作业2
一、 填空题
得 分： 教师签名： 第三章 稀疏矩阵和广义表
1、 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的__________________。
2、 在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的____________、______________________和___________________三项。
3、 广义表A=(a,(b,(,d)),(e))的长度为________________，深度为________________。 4、 广义表((a,(b,( ),c),((d),e)))的表头为______________，表尾为____________。 5、 一个广义表中的元素分为________元素和________元素两类。
6、 一个稀疏矩阵如下图所示，则对应的三元组线性表表示为_______________。 0 0 2 0 3 0 0 0 0 0 -1 5
0 0 0 0
7、 在稀疏矩阵所对应的三元组线性表中，每个三元组元素按________为主序、________为辅序的次序排列。
8、 在稀疏矩阵的带行指针向量的链接存储中，每个结点包含________个域，而在相应的十字链接存储中，每个结点包含________个域。
第 15 页 共 49 页
9、 广义表的深度等于______________嵌套的最大层数。
10、 若采用三元组来存储一个稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法是________（正确/错误？）的。
二、 选择题
1、在稀疏矩阵的十字链接存储中，每个结点的down指针指向的结点都具有相同的（ ）。
A.行号 B.列号 C.地址 D.元素值
2、在稀疏矩阵的十字链接存储中，每个结点的right指针指向的结点都具有相同的
（ ）。
A. 地址 B. 元素值 C. 行号 D. 列号
3、设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，其转置矩阵的普通转置算法的时间复杂度为（ ）。
A. O(m) B. O(n) C. O(n+t) D.O(n*t)
4、设一个广义表中结点的个数为n，则广义表深度算法的时间复杂度为（ ）。
A. O(1) B. O(n) C. O(n) D. O(log2n)
5、在广义表的存储结构中，若某结点的tag域等于1，则其next域存放的是（ ）。
A. NULL B.值域
C.下一个元素的地址 D.子表的表头指针
第 16 页 共 49 页
2
