链表的概念及结构练习题

• 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;
}