文章目录 单选题函数题6-1 链式表的按序号查找输入样例：输出样例：代码 6-3 建立学生信息链表 (20分)输入样例：输出样例：代码 6-4 学生成绩链表处理 (20分)输入样例：输出样例：代码
单选题 题号题目答案1结点的单链表中，实现下列哪个操作，其算法的时间复杂度是O(N)？遍历链表和求链表的第i个结点2对于一个具有N个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为 O(N)3线性表若采用链式存储结构时，要求内存中可用存储单元的地址 连续或不连续都可以4某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？ 仅有尾指针的单循环链表5kdyt表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间？ 带头结点的双循环链表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 -1typedef 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);elseprintf("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;elsereturn 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 782 wang 803 li 754 zhao 850 输出样例： 1 zhang 782 wang 803 li 754 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 %dn", 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;}// 把新加的节点赋予tailtail = 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 782 wang 803 li 754 zhao 85080 输出样例： 2 wang 804 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 %dn", 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;elsetail->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;}