《数据结构》形成性考核册

（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