发布时间 : 星期六 文章数据结构复习题习题全六章含答案更新完毕开始阅读
C、q->next = p->next; p->next = q; D、p->next = q->next ; q->next = p;
6．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行 。
A、p = q->next ; p->next = q->next; B、p = q->next ; q->next = p; C、p = q->next ; q->next = p->next; D、q->next = q->next->next; q->next = q; 二、填空题
1．在线性表的单链接存储结构中，每个结点包含有两个域，一个叫 域，另一个叫 域。
2．在下面数组a中链接存储着一个线性表，表头指针为a[0].next，则该线性表为
。
3．对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。
4．对于一个长度为n的单链接存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。
5．在线性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为 ，后继元素的下标为 。
6．在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为 ，若假定p为一个数组a中的下标，则其后继结点的下标
为 。
7．在循环单链表中，最后一个结点的指针指向 结点。 8．在双向链表中每个结点包含有两个指针域，一个指向其 结点，另一个指向其 结点。
9．在循环双向链表中表头结点的左指针域指向 结点，最后一个结点的右指针域指向 结点。
10．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为 和 。 三、应用题
1．在下面的每个程序段中，假定线性表La的类型为List，元素类型ElemType为int，并假定每个程序段是连续执行的，试写出每个程序段执行后所得到的线性表La。
(1) InitList(La);
int a[]={48,26,57,34,62,79};
for(i=0; i<6; i++) InsertFront(La,a[i]);
TraverseList(La); (2) InitList(La);
for(i=0; i<6; i++) Insert(La,a[i]);
TraverseList(La);
(3) ClearList(La);
for(i=0; i<6; i++) InsertRear(La,a[i]); Delete(La, a[5]);
Sort(La);
Insert(La,a[5]/2);
TraverseList(La);
2．写出下面函数被调用执行后，得到的以HL为表头指针的单链表中的数据元素序列。
void AA(LNode * & HL) {
InitList(HL); InsertRear(HL,30); InsertRear(HL,50);
int a[5] = {15,8,9,26,12};
for ( int i=0; i<5; i++ ) InsertFront(HL,a[i]);
}
3．对于List类型的线性表，编写出下列每个算法。
(1) 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若线性表为空则显示出错信息并退出运行。 (2) 从线性表中删除第i个元素并由函数返回。 (3) 向线性表中第i个元素位置插入一个元素。 (4) 从线性表中删除具有给定值x的所有元素。
4．对于结点类型为LNode的单链表，编写出下列每个算法。
(1) 删除单链表中的第i个结点。
(2) 在有序单链表中插入一个元素x的结点。
(3) 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息并停止运行。
(4) 统计出单链表中结点的值等于给定值x的结点数。
第三章 稀疏矩阵和广义表
一、单选题
1. 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的________。
A、 行号 B、 列号 C、 元素值 D、 地址
2. 设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为_______。
A、 O(1) B、 O(n) C、 O(n2) D、 O(log2n) 二、填空题
1. 在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的________、________和________三项。
2. 在稀疏矩阵所对应的三元组线性表中，每个三元组元素按________为主序、________为辅序的次序排列。
3. 在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为________参数。 4. 在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应________对应三元组线性表的长度。
5．在稀疏矩阵的带行指针向量的链接存储中，每个结点包含有________个域，在相应的十字链接存储中，每个结点包含有________个域。
6．在稀疏矩阵的十字链接存储中，每个结点的down指针域指向________相