【原】数据结构——链表PTA习题

文章目录

单选题

题号	题目	答案
1	结点的单链表中，实现下列哪个操作，其算法的时间复杂度是O(N)？	遍历链表和求链表的第i个结点
2	对于一个具有N个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为	O(N)
3	线性表若采用链式存储结构时，要求内存中可用存储单元的地址	连续或不连续都可以
4	某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？	仅有尾指针的单循环链表
5	若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间？	带头结点的双循环链表
6	线性表L在什么情况下适用于使用链式结构实现？	需不断对L进行删除插入
7	将线性表La和Lb头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小。应该使用哪种结构？	带尾指针的单循环链表
8	链表不具有的特点是：	方便随机访问任一元素
9	在单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行	s->next=p->next; p->next=s;
10	将两个结点数都为N且都从小到大有序的单向链表合并成一个从小到大有序的单向链表，那么可能的最少比较次数是：	N

函数题

6-1 链式表的按序号查找

本题要求实现一个函数，找到并返回链式表的第K个元素。

L是给定单链表，函数FindKth要返回链式表的第K个元素。如果该元素不存在，则返回ERROR。

输入样例：

1 3 4 5 2 -1
6
3 6 1 5 4 2

输出样例：

4 NA 1 2 5 3

代码

#include <stdio.h>
#include <stdlib.h>

#define ERROR -1
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode List;

List Read(); /* 细节在此不表 */

ElementType FindKth(List L, int K);

int main()
{
int N, K;
ElementType X;
List L = Read();
scanf("%d", &N);
while (N--) {
scanf("%d", &K);
X = FindKth(L, K);
if (X != ERROR)
printf("%d ", X);
else
printf("NA ");
}
return 0;
}

/* 你的代码将被嵌在这里 */
ElementType FindKth(List L, int K) {

// K是索引值+1   设置count计数时候也要从1 开始
int count = 1;
PtrToLNode p = L;

while (L != NULL && count < K)
{
p = p->Next;
count++;
}
if (p&&count == K)
return p->Data;
else
return ERROR;
}

6-3 建立学生信息链表 (20分)

本题要求实现一个将输入的学生成绩组织成单向链表的简单函数。

函数接口定义：

void input();

该函数利用scanf从输入中获取学生的信息，并将其组织成单向链表。链表节点结构定义如下：

struct stud_node {
    int              num;      /*学号*/
    char             name[20]; /*姓名*/
    int              score;    /*成绩*/
    struct stud_node *next;    /*指向下个结点的指针*/
};

单向链表的头尾指针保存在全局变量head和tail中。

输入为若干个学生的信息（学号、姓名、成绩），当输入学号为0时结束。

输入样例：

1 zhang 78
2 wang 80
3 li 75
4 zhao 85
0

输出样例：

1 zhang 78
2 wang 80
3 li 75
4 zhao 85

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct stud_node {
     int    num;
     char   name[20];
     int    score;
     struct stud_node *next;
};
struct stud_node *head, *tail;

void input();

int main()
{
    struct stud_node *p;

    head = tail = NULL;
    input();
    for ( p = head; p != NULL; p = p->next )
        printf("%d %s %d\n", p->num, p->name, p->score);

    return 0;
}

/* 你的代码将被嵌在这里 */
void input()
{
struct stud_node *pt;
pt = (struct stud_node *)malloc(sizeof(struct stud_node));
scanf("%d", &pt->num);
while (pt->num != 0)
{
scanf("%s %d", pt->name, &pt->score);
if (head == NULL)
{
head = pt;
head->next = NULL;
}
//tail为开辟节点
if (tail != NULL)
{
tail->next = pt;
}

// 把新加的节点赋予tail
tail = pt;
tail->next = NULL;
pt = (struct stud_node *)malloc(sizeof(struct stud_node));
scanf("%d", &pt->num);
}

}

6-4 学生成绩链表处理 (20分)

本题要求实现两个函数，一个将输入的学生成绩组织成单向链表；另一个将成绩低于某分数线的学生结点从链表中删除。

函数接口定义：

struct stud_node *createlist();
struct stud_node *deletelist( struct stud_node *head, int min_score );

函数createlist利用scanf从输入中获取学生的信息，将其组织成单向链表，并返回链表头指针。链表节点结构定义如下：

struct stud_node {
    int              num;      /*学号*/
    char             name[20]; /*姓名*/
    int              score;    /*成绩*/
    struct stud_node *next;    /*指向下个结点的指针*/
};

输入为若干个学生的信息（学号、姓名、成绩），当输入学号为0时结束。

函数deletelist从以head为头指针的链表中删除成绩低于min_score的学生，并返回结果链表的头指针。

输入样例：

1 zhang 78
2 wang 80
3 li 75
4 zhao 85
0
80

输出样例：

2 wang 80
4 zhao 85

代码

#include <stdio.h>
#include <stdlib.h>

struct stud_node {
     int    num;
     char   name[20];
     int    score;
     struct stud_node *next;
};

struct stud_node *createlist();
struct stud_node *deletelist( struct stud_node *head, int min_score );

int main()
{
    int min_score;
    struct stud_node *p, *head = NULL;

    head = createlist();
    scanf("%d", &min_score);
    head = deletelist(head, min_score);
    for ( p = head; p != NULL; p = p->next )
        printf("%d %s %d\n", p->num, p->name, p->score);

    return 0;
}

/* 你的代码将被嵌在这里 */
struct stud_node *createlist()
{
struct stud_node *pt;
pt = (struct stud_node *)malloc(sizeof(struct stud_node));
struct stud_node *head,*tail;
head = tail = NULL;
scanf("%d", &pt->num);
while (pt->num != 0)
{
scanf("%s %d", pt->name, &pt->score);
if (head == NULL)
head = pt;
else
tail->next = pt;

tail = pt;
pt = (struct stud_node *)malloc(sizeof(struct stud_node));
scanf("%d", &pt->num);
}
return head;
}
struct stud_node *deletelist(struct stud_node *head, int min_score)
{
struct stud_node*p1, *p2;
// // 头结点为空直接返回
// if (head==NULL)
// {
// return NULL;
// }
// 先检查头结点是否小于
while (head!=NULL&&head->score<min_score)
{
p1 = head;
head = head->next;
free(p1);
}
    // 如果刚才删除了头结点，头结点还为空直接返回
if (head==NULL)
{
return NULL;
}
p1 = head;
p2 = p1->next;
// 头结点没问题了  看头结点以后
// 后面要是没有直接跳过循环return   head就行
while (p2!=NULL)
{
if (p2->score<min_score)
{
p1->next = p2->next;
free(p2);
}
else
{
p1 = p2;
}
// 让p2等于下一个继续检验
p2 = p1->next;
}

return head;
}