链表的概念及结构练习题
A.选择题A.答案B、函数题1. 求单链表的表长2 求单链表元素序号3. 求单链表结点的阶乘和4. 逆序数据建立链表
A.选择题
1.链表的适用场合线性表在 ▁▁▁▁ 情况下适合采用链式存储结构。
A.线性表中数据元素的值需经常修改
B.线性表需经常插入或删除数据元素
C.线性表包含大量的数据元素
D.线性表的数据元素包含大量的数据项
2.链表 - 存储结构链表要求内存中可用存储单元的地址 ▁▁▁▁▁ 。
A.必须是连续的
B.部分地址必须是连续的
C.一定是不连续的
D.连续或不连续都可以
3.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是▁▁▁▁▁。
A. head == NULL
B. head→next == NULL
C. head→next == head
D. head != NULL
4.设有如下定义的链表，则值为7的表达式是▁▁▁▁▁。struct st{ int n; struct st *next;} a[3] = {5, &a[1], 7, &a[2], 9, NULL}, *p = &a;A. p->n
B. (p->n)++
C. ++p->n
D. p->next->n
5.在一个单链表head中，若要在指针p所指结点后插入一个q指针所指结点，则执行▁▁▁▁▁。
A. p->next=q->next; q->next=p;
B. q->next=p->next; p=q;
C. p->next=q->next; p->next=q;
D. q->next=p->next; p->next=q;
6.在一个单链表head中，若要删除指针p所指结点的后继结点，则执行（）。
A. p=p->next;free§;
B. p->next=p->next->next; free§;
C. q= p->next q->next=p->next; free(q);
D. q=p->next; p->next=q->next; free(q);
7.已创建如下的单向链表结构，指针变量s指向链表的第一个结点。以下程序段实现的功能是（ ）
p=s->next;s->next=s->next->next;free(p);A.首结点成为尾结点
B.删除首节点的后继节点
C.删除首结点
D.删除尾结点
A.答案
1.B
解释：链式存储适合频繁的删除，插入元素；顺序则更适合频繁的查询。数据元素的多少跟链式存储还是顺序存储关系不大
2.D
解释：链表中的结点是动态开辟出来的，跟连不连续没关系，可能会动态开辟连续的两块内存空间，但是大概率还是不连续的，因此连续或不连续都可以
3.B
解释：链表为空的条件：head头结点的next为空
4.D
解释：a是个结构体数组，存了三组数据；结构体指针p指向a首元素的地址。
对于A：p->n 即为a[0]->n = 5
对于B：(p->n)++ 即为 5++ 结果是 6
对于C： ->(成员选择(指针))优先级最高，跟B没差别
对于D：p->next为a中第二个结构体{7，&a[2]}，p->next->n即为7
5.D
解释：
如果先修改p->next 使其 = q ，那么接下来无法找到原来p->next指向的结点。
抛开这道题，插入结点也可以这样：
struct ListNode* next = p->next;p->next = q;q->next = next;6.D
解释：
7.B
解释：
B、函数题
1. 求单链表的表长
给链表的头节点指针head，求这个单链表的表长
(其中ListNode结构定义如下：)
typedef int DataType;typedef struct ListNode{ DataType data; struct ListNode *next;}ListNode;函数接口定义：
int Length ( ListNode* head );思路：
函数实现：
int Length ( ListNode* head ){ int len = 0; ListNode* cur = L; while(cur->next) { cur = cur->next; n++; } return n;}2 求单链表元素序号
给链表的头节点指针 head，和要查找的元素值x。如果x在单链表中存在，函数Locate返回其序号（序号从1开始）；否则，返回0。
(其中ListNode结构定义如下：)
typedef int DataType;typedef struct ListNode{ DataType data; struct ListNode *next;}ListNode;函数接口定义：
int Locate ( ListNode* head, DataType x);思路：
函数实现：
int Locate ( ListNode* head, DataType x){ int n = 1;//因为序号从1开始，不是从0 ListNode* cur = head->next;//head是哨兵位结点，数据域没有存有效数据 while(cur) { if(cur->data == x) return n; n++; cur = cur->next; } return 0;//找不到最后返回0}3. 求单链表结点的阶乘和
给链表的首元素指针head，求这个单链表结点的阶乘和
（这里默认所有结点的值非负，且题目保证结果在int范围内。）
(其中ListNode结构定义如下：)
typedef struct ListNode{ ElemType data; struct ListNode *next;}ListNode;函数接口定义：
int FactorialSum( ListNode* head );思路：
遍历一遍链表，把各结点的data的阶乘求和
函数实现：
//把求阶乘封装成一个函数，方便后面使用int factorial(int data){ if (data == 0) return 1; else { int ret = data; while (--data) { ret *= data; } return ret; }}int FactorialSum( ListNode* head );{ if(head == NULL) return 0; int ret = 0; ListNode* cur = head; while(cur) { ret += factorial(cur->data); cur = cur->next; } return ret;}4. 逆序数据建立链表
按输入数据的逆序建立一个链表；
函数createlist利用scanf从输入中获取一系列正整数，当读到−1时表示输入结束。按输入数据的逆序建立一个链表，并返回链表头指针。
(其中ListNode结构定义如下：)
typedef struct ListNode{ ElemType data; struct ListNode *next;}ListNode;函数接口定义：
ListNode* createlist();思路：
类似于栈Last InFirst Out ，可以考虑头插（在链表的头插入新结点，从而实现逆序）
函数实现：
//把求阶乘封装成一个函数，方便后面使用int factorial(int data){ if (data == 0) return 1; else { int ret = data; while (--data) { ret *= data; } return ret; }}int FactorialSum( ListNode* head );{ if(head == NULL) return 0; int ret = 0; ListNode* cur = head; while(cur) { ret += factorial(cur->data); cur = cur->next; } return ret;}