# DS-PTA-Coding **Repository Path**: weber-ds/ds-pta-coding ## Basic Information - **Project Name**: DS-PTA-Coding - **Description**: 数据结构PTA期末复习题 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2021-12-10 - **Last Updated**: 2021-12-23 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README ## 写在前面 欢迎来到大饭桶的数据结构PTA题集笔记! 当前笔记收录题目：22/22 当前笔记题解实现语言： | 编程语言 | 实现比例 | | --- | --- | | C语言 | 100% | ## 目录 * [函数题-求二叉树高度](#求二叉树高度) * [函数题-二叉树的遍历](#二叉树的遍历) * [函数题-先序输出叶结点](#先序输出叶结点) * [函数题-统计二叉树结点个数](#统计二叉树结点个数) * [函数题-统计二叉树叶子结点个数](#统计二叉树叶子结点个数) * [函数题-直接插入排序](#直接插入排序) * [函数题-冒泡排序](#冒泡排序) * [函数题-简单选择排序](#简单选择排序) * [函数题-折半插入排序](#折半插入排序) * [编程题-顺序表的建立及遍历](#顺序表的建立及遍历) * [编程题-顺序表区间元素删除](#顺序表区间元素删除) * [编程题-数组循环左移](#数组循环左移) * [编程题-简单密码（凯撒密码）](#简单密码（凯撒密码）) * [编程题-递增有序顺序表的插入](#递增有序顺序表的插入) * [编程题-两个有序链表序列的合并](#两个有序链表序列的合并) * [编程题-两个有序链表序列的交集](#两个有序链表序列的交集) * [编程题-单链表的创建及遍历](#单链表的创建及遍历) * [编程题-求链式线性表的倒数第K项](#求链式线性表的倒数第K项) * [编程题-链表倒数n个结点的乘积](#链表倒数n个结点的乘积) * [编程题-在有序链表中插入数据](#在有序链表中插入数据) * [编程题-二分查找](#二分查找) * [编程题-二分查找-2](#二分查找-2) ## 函数题 ### 求二叉树高度 ##### 函数接口定义： ```c int GetHeight( BinTree BT ); ``` 其中 `BinTree` 结构定义如下: ```c typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; }; ``` 要求函数返回给定二叉树BT的高度值 ##### 裁判测试程序样例 ```c #include #include typedef char ElementType; typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; }; BinTree CreatBinTree(); /* 实现细节忽略 */ int GetHeight( BinTree BT ); int main() { BinTree BT = CreatBinTree(); printf("%d\n", GetHeight(BT)); return 0; } /* 你的代码将被嵌在这里 */ ``` ##### 输出样例（对于图中给出的树）: ![图 1-1](https://gitee.com/weber-ds/ds-pta-coding/raw/master/images/1-1.png "图1-1") ``` 4 ``` ##### 参考答案(实现语言：C语言) ```c //声明函数并定义 int GetHeight( BinTree BT ) { //声明用于储存左右子树高度的变量 int leftH,rightH; //如果当前传入的节点为空，说明其父节点为叶子节点。该情况为递归基，返回0。 if(BT==NULL) { return 0; } //分别求出左右子树的高度 leftH = GetHeight(BT->Left); rightH = GetHeight(BT->Right); //三元表达式：在左右子树的中选择高度较高的一个，将其高度+1（即加上当前节点的高度），作为返回值 return leftH>rightH?leftH+1:rightH+1; } ``` ### 二叉树的遍历 本题要求给定二叉树的4种遍历。 ##### 函数接口定义： ```c void InorderTraversal( BinTree BT ); void PreorderTraversal( BinTree BT ); void PostorderTraversal( BinTree BT ); void LevelorderTraversal( BinTree BT ); ``` 其中`BinTree`结构定义如下： ```c typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; }; ``` 要求4个函数分别按照访问顺序打印出结点的内容，格式为一个空格跟着一个字符。 ##### 裁判测试程序样例： ```c #include #include typedef char ElementType; typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; }; BinTree CreatBinTree(); /* 实现细节忽略 */ void InorderTraversal( BinTree BT ); void PreorderTraversal( BinTree BT ); void PostorderTraversal( BinTree BT ); void LevelorderTraversal( BinTree BT ); int main() { BinTree BT = CreatBinTree(); printf("Inorder:"); InorderTraversal(BT); printf("\n"); printf("Preorder:"); PreorderTraversal(BT); printf("\n"); printf("Postorder:"); PostorderTraversal(BT); printf("\n"); printf("Levelorder:"); LevelorderTraversal(BT); printf("\n"); return 0; } /* 你的代码将被嵌在这里 */ ``` ##### 输出样例（对于图中给出的树）： ![图 2-1](https://gitee.com/weber-ds/ds-pta-coding/raw/master/images/2-1.png "图2-1") ``` Inorder: D B E F A G H C I Preorder: A B D F E C G H I Postorder: D E F B H G I C A Levelorder: A B C D F G I E H ``` ##### 参考答案(实现语言：C语言) ```c //Inorder为中序遍历 void InorderTraversal( BinTree BT ) { //递归基：当前节点为空，不作回应 if(BT==NULL) { return; } //中序遍历：左 右 根 //先访问当前节点的左子节点 InorderTraversal( BT->Left ); //访问当前节点 printf(" %c",BT->Data); //访问当前节点的右子节点 InorderTraversal( BT->Right ); return; } //Preorder为前序遍历 void PreorderTraversal( BinTree BT ) { //递归基：当前节点为空，不作回应 if(BT==NULL) { return; } //前序遍历：根 左 右 //先访问当前节点 printf(" %c",BT->Data); //访问当前节点的左子节点 PreorderTraversal( BT->Left ); //访问当前节点的右子节点 PreorderTraversal( BT->Right ); return; } //Postorder为后序遍历 void PostorderTraversal( BinTree BT ) { //递归基：当前节点为空，不作回应 if(BT==NULL) { return; } //后序遍历： 左 右 根 //先访问当前节点的左子节点 PostorderTraversal( BT->Left ); //再访问当前节点的右子节点 PostorderTraversal( BT->Right ); //访问当前节点 printf(" %c",BT->Data); return; } //层序遍历 void LevelorderTraversal( BinTree BT ) { //层序遍历需要一个循环队列辅助，其操作为节点出队，访问该出队节点，将该节点的左右子节点入队，直至队列为空 BinTree queue[100]; BinTree node; int front,rear,maxQ; front=0; rear=0; maxQ=100; //根节点入队 node = BT; if(node==NULL) { return; } queue[rear]=node; rear += 1; while(front!=rear) { //节点出队 node = queue[front]; front = (front+1)%maxQ; printf(" %c",node->Data); //左右子节点若不为空，入队 if(node->Left!=NULL) { queue[rear] = node->Left; rear = (rear+1)%maxQ; } if(node->Right!=NULL) { queue[rear] = node->Right; rear = (rear+1)%maxQ; } } return; } ``` ### 先序输出叶结点 本题要求按照先序遍历的顺序输出给定二叉树的叶结点。 ##### 函数接口定义： ```c void PreorderPrintLeaves( BinTree BT ); ``` 其中`BinTree`结构定义如下: ```c typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; }; ``` 函数`PreorderPrintLeaves`应按照先序遍历的顺序输出给定二叉树BT的叶结点，格式为一个空格跟着一个字符。 ##### 裁判测试程序样例： ```c #include #include typedef char ElementType; typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; }; BinTree CreatBinTree(); /* 实现细节忽略 */ void PreorderPrintLeaves( BinTree BT ); int main() { BinTree BT = CreatBinTree(); printf("Leaf nodes are:"); PreorderPrintLeaves(BT); printf("\n"); return 0; } /* 你的代码将被嵌在这里 */ ``` ##### 输出样例（对于图中给出的树）： ![图 3-1](https://gitee.com/weber-ds/ds-pta-coding/raw/master/images/3-1.png "图3-1") ``` Leaf nodes are: D E H I ``` ##### 参考答案(实现语言：C语言) ```c //声明函数定义 void PreorderPrintLeaves( BinTree BT ) { //如果当前节点为空，不作处理 if(BT==NULL) { return; } //如果当前节点的左右子节点均为空，说明当前节点为叶子节点，可以输出 if(BT->Left==NULL&&BT->Right==NULL) { printf(" %c",BT->Data); return; } //先序遍历为根 左 右 //访问左子节点 PreorderPrintLeaves( BT->Left ); //访问右子节点 PreorderPrintLeaves( BT->Right ); } ``` ### 统计二叉树结点个数 本题要求实现一个函数，可统计二叉树的结点个数。 ##### 函数接口定义： ```c int NodeCount ( BiTree T); ``` T是二叉树树根指针，函数NodeCount返回二叉树中结点个数，若树为空，返回0。 ##### 裁判测试程序样例： ```c #include #include typedef char ElemType; typedef struct BiTNode { ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree Create();/* 细节在此不表 */ int NodeCount ( BiTree T); int main() { BiTree T = Create(); printf("%d\n", NodeCount(T)); return 0; } /* 你的代码将被嵌在这里 */ ``` ##### 输出样例（对于图中给出的树）： ![图 4-1](https://gitee.com/weber-ds/ds-pta-coding/raw/master/images/4-1.png "图4-1") ``` 6 ``` ##### 参考答案(实现语言:C语言) ```c //声明函数定义 int NodeCount ( BiTree T) { //递归基:如果当前节点为空，返回0 if(T==NULL) { return 0; } //返回当前节点+左子树节点数量+右子树节点数量 return 1 + NodeCount(T->lchild)+NodeCount(T->rchild); } ``` ### 统计二叉树叶子结点个数 本题要求实现一个函数，可统计二叉树的叶子结点个数。 ##### 函数接口定义： ```c int LeafCount ( BiTree T); ``` T是二叉树树根指针，函数LeafCount返回二叉树中叶子结点个数，若树为空，则返回0。 ##### 裁判测试程序样例： ```c #include #include typedef char ElemType; typedef struct BiTNode { ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree Create();/* 细节在此不表 */ int LeafCount ( BiTree T); int main() { BiTree T = Create(); printf("%d\n", LeafCount(T)); return 0; } /* 你的代码将被嵌在这里 */ ``` ##### 输出样例（对于图中给出的树）： ![图 5-1](https://gitee.com/weber-ds/ds-pta-coding/raw/master/images/5-1.png "图5-1") ``` 3 ``` ##### 参考答案(实现语言：C语言) ```c //声明函数定义 int LeafCount ( BiTree T) { //递归基:如果当前节点为空，返回0 if(T==NULL) { return 0; } //递归基:如果当前节点的左右子树都为空，视为叶子节点，记录该节点 if(T->lchild==NULL&&T->rchild==NULL) { return 1; } //返回当前节点的左子树叶子节点数量+右子树叶子节点数量 return LeafCount(T->lchild)+LeafCount(T->rchild); } ``` ### 直接插入排序 本题要求实现直接插入排序函数，待排序列的长度1<=n<=1000。 ##### 函数接口定义： ```c void InsertSort(SqList L); ``` 其中L是待排序表，使排序后的数据从小到大排列。 ###类型定义： ```c typedef int KeyType; typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList; ``` ##### 裁判测试程序样例： ```c #include #include typedef int KeyType; typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList; void CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ void InsertSort(SqList L); int main() { SqList L; int i; CreatSqList(&L); InsertSort(L); for(i=1;i<=L.Length;i++) { printf("%d ",L.elem[i]); } return 0; } /*你的代码将被嵌在这里 */ ``` ##### 输入样例： 第一行整数表示参与排序的关键字个数。第二行是关键字值 例如： ```c 10 5 2 4 1 8 9 10 12 3 6 ``` ##### 输出样例： ```c 1 2 3 4 5 6 8 9 10 12 ``` ##### 参考答案1(实现语言：C语言) ```c //声明函数定义 void InsertSort(SqList L) { //初始化循环控制变量i和j int i,j; //外层循环控制需要插入的值 for(i=2;i<=L.Length;i++) { //判断当前值是否需要插入 if((L.elem)[i]<(L.elem)[i-1]) { //0号元素为哨兵 //内层循环执行插入 (L.elem)[0]=(L.elem)[i]; for(j=i-1;j>=1&&(L.elem)[j]>(L.elem)[0];j--) { (L.elem)[j+1]=(L.elem)[j]; } //取出哨兵中的值 (L.elem)[j+1]=(L.elem)[0]; } } } ``` ### 冒泡排序 本题要求实现冒泡排序函数，待排序列的长度1<=n<=1000。 ##### 函数接口定义： ```c void bubble_sort(SqList L); ``` 其中L是待排序表，使排序后的数据从小到大排列。 ###类型定义： ```c typedef int KeyType; typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList; ``` ##### 裁判测试程序样例： ```c #include #include typedef int KeyType; typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList; void CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ void bubble_sort(SqList L); int main() { SqList L; int i; CreatSqList(&L); bubble_sort( L); for(i=1;i<=L.Length;i++) { printf("%d ",L.elem[i]); } return 0; } /*你的代码将被嵌在这里 */ ``` ##### 输入样例： 第一行整数表示参与排序的关键字个数。第二行是关键字值 例如： ``` 10 5 2 4 1 8 9 10 12 3 6 ``` ##### 输出样例： 输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。 ``` 1 2 3 4 5 6 8 9 10 12 ``` ##### 参考答案1(实现语言：C语言) ```c void bubble_sort(SqList L) { //初始化循环控制变量i和j int i,j; //外层循环控制第几趟 for(i=1;i<=L.Length;i++) //内层循环进行冒泡 for(j=1;jL.elem[j+1]) { L.elem[0] = L.elem[j]; L.elem[j] = L.elem[j+1]; L.elem[j+1] = L.elem[0]; } } } ``` ##### 参考答案2-短版(实现语言：C语言) ```c void bubble_sort(SqList L) { int i,j,n; for(i=0,n=L.Length;i=!i;n--) for(j=1;jL.elem[j+1])?(L.elem[j] ^= L.elem[j+1] ^= L.elem[j] ^= L.elem[j+1],0):i; } ``` ### 简单选择排序 本题要求实现简单选择排序函数，待排序列的长度1<=n<=1000。 ##### 函数接口定义： ```c void SelectSort(SqList L); ``` 其中L是待排序表，使排序后的数据从小到大排列。 ###类型定义： ```c typedef int KeyType; typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList; ``` ##### 裁判测试程序样例： ```c #include #include typedef int KeyType; typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList; void CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ void SelectSort(SqList L); int main() { SqList L; int i; CreatSqList(&L); SelectSort(L); for(i=1;i<=L.Length;i++) { printf("%d ",L.elem[i]); } return 0; } /*你的代码将被嵌在这里 */ ``` ##### 输入样例： 第一行整数表示参与排序的关键字个数。第二行是关键字值 例如： ``` 10 5 2 4 1 8 9 10 12 3 6 ``` ##### 输出样例： 输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。 ``` 1 2 3 4 5 6 8 9 10 12 ``` ##### 参考答案1（实现语言：C语言） ```c //声明函数定义 void SelectSort(SqList L) { //初始化循环控制变量i,j以及最小值缓冲区 int i,j,min; //外层循环控制波次 for(i=1;i<=L.Length;i++) { //内层循环寻找未处理数列中的最小值 min = i; for(j=i;j<=L.Length;j++) { if(L.elem[min]>L.elem[j]) { min = j; } } //交换位置 L.elem[0] = L.elem[min]; L.elem[min] = L.elem[i]; L.elem[i] = L.elem[0]; } } ``` ##### 参考答案2-短版（实现语言：C语言） ```c void SelectSort(SqList L) { int i,j,min; for(i=1;i<=L.Length;i++) { for(min=j=i;j<=L.Length;j++) min = (L.elem[min]>L.elem[j])?j:min; if(i!=min) L.elem[i] ^= L.elem[min] ^= L.elem[i] ^= L.elem[min]; } } ``` ### 折半插入排序 实现折半插入排序。 ##### 函数接口定义： ```c void BInsertSort(SqList &L); ``` ##### 裁判测试程序样例： ```c #include #define MAXSIZE 1000 using namespace std; typedef struct { int key; char *otherinfo; }ElemType; typedef struct { ElemType *r; int length; }SqList; void BInsertSort(SqList &L); void Create_Sq(SqList &L);//实现细节隐藏 void show(SqList L) { int i; for(i=1;i<=L.length;i++) if(i==1) cout<=low+1;j--) { (L.r)[j] = (L.r)[j-1]; } (L.r)[low] = tmp; } } } ``` ## 编程题 ### 顺序表的建立及遍历 读入n值及n个整数，建立顺序表并遍历输出。 ##### 输入格式: 读入n及n个整数 ##### 输出格式: 输出n个整数，以空格分隔（最后一个数的后面没有空格）。 ##### 输入样例: 在这里给出一组输入。例如： ``` 4 -3 10 20 78 ``` ##### 输出样例: 在这里给出相应的输出。例如： ``` -3 10 20 78 ``` ##### 参考答案(实现语言：C语言) ```c #include #include int main() { int *a,cache,len,i; scanf("%d",&len); if(len==0)return 0; a = (int*)malloc(sizeof(int)*len); for(i=0;i #include int main() { int *a,cache,len,i,x,y; scanf("%d",&len); if(len==0)return 0; a = (int*)malloc(sizeof(int)*len); for(i=0;i=x&&a[i]<=y) { i++; continue; } a[cache++] = a[i++]; } for(i=0;printf("%d",a[i++]),i #include void swap(int *a,int start,int end) { while(start #include int main() { char *result; char c; int len,i; len = 1; result = (char*)malloc(sizeof(char)); while((c=getchar())!=EOF&&c!='\n') { if(c<'A'||c>'Z') { result[len-1] = c; }else { result[len-1] = (c-'A'+21)%26+'A'; } result = (char*)realloc(result,sizeof(char)*(++len)); } if(len==1) { printf("NULL"); return 0; } for(i=0;printf("%c",result[i++]),i #include int main() { int *a,cache,len,i,target; scanf("%d",&len); if(len==0)return 0; a = (int*)malloc(sizeof(int)*(len+1)); for(i=0;i=0;i--) { if(i==0||a[i-1] #include typedef struct Element { int value; struct Element* next; }Element; typedef struct ArrayList { Element* head; Element* rear; Element* point; int length; }ArrayList; void initElement(Element** e,int v) { (*e) = (Element*)malloc(sizeof(Element)); (*e)->next = NULL; (*e)->value = v; return; } void initArrayList(ArrayList** L) { (*L) = (ArrayList*)malloc(sizeof(ArrayList)); (*L)->head = NULL; (*L)->rear = NULL; (*L)->point = NULL; return; } void resetPoint(ArrayList** L) { (*L)->point = (*L)->head; return; } void nextPoint(ArrayList** L) { (*L)->point = (*L)->point->next; return; } void headInsert(ArrayList** L,int v) { Element* e = NULL; initElement(&e,v); if((*L)->head==NULL) { (*L)->head = e; (*L)->point = e; (*L)->rear = e; return; } e->next = (*L)->head; (*L)->head = e; return; } void rearInsert(ArrayList** L,int v) { Element* e = NULL; initElement(&e,v); if((*L)->head==NULL) { (*L)->head = e; (*L)->point = e; (*L)->rear = e; return; } (*L)->rear->next = e; (*L)->rear = e; return; } int delHead(ArrayList** L) { int v; Element* e; v = (*L)->head->value; e = (*L)->head; (*L)->head = e->next; free(e); return v; } int dropHead(ArrayList** L) { int v; Element* e; v = (*L)->head->value; e = (*L)->head; (*L)->head = e->next; return v; } ArrayList* appendSortedList(ArrayList** L1,ArrayList** L2) { int v1,v2; Element* p,*l,*e; p = (*L1)->head; l = NULL; if(p==NULL) { free((*L1)); return (*L2); } if((*L2)->head==NULL) { free((*L2)); return (*L1); } while((*L2)->head!=NULL&&p!=NULL) { v1 = p->value; v2 = (*L2)->head->value; if(v1>v2) { if(l==NULL) { l = (*L2)->head; dropHead(L2); l->next = p; (*L1)->head = l; }else { e = (*L2)->head; dropHead(L2); e->next = p; l->next = e; l = e; } continue; } l = p; p = p->next; } if((*L2)->head!=NULL) { l->next = (*L2)->head; (*L1)->rear = (*L2)->rear; } free((*L2)); return (*L1); } int main() { ArrayList* L1; ArrayList* L2; Element* p; int cache; initArrayList(&L1); initArrayList(&L2); cache = 0; while(cache!=-1) { scanf("%d",&cache); if(cache!=-1) rearInsert(&L1,cache); } cache = 0; while(cache!=-1) { scanf("%d",&cache); if(cache!=-1) rearInsert(&L2,cache); } L1 = appendSortedList(&L1,&L2); p = L1->head; if(p==NULL) { printf("NULL"); return 0; } while(p!=NULL) { printf("%d",p->value); if(p->next!=NULL) { printf(" "); } p = p->next; } return 0; } ``` ### 两个有序链表序列的交集 已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。 ##### 输入格式: 输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用-1表示序列的结尾（-1不属于这个序列）。数字用空格间隔。 ##### 输出格式: 在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出`NULL`。 ##### 输入样例: ``` 1 2 5 -1 2 4 5 8 10 -1 ``` ##### 输出样例: ``` 2 5 ``` ##### 参考答案（实现语言：C语言） ```c #include #include typedef struct Element { int value; struct Element* next; }Element; typedef struct ArrayList { Element* head; Element* rear; Element* point; int length; }ArrayList; void initElement(Element** e,int v) { (*e) = (Element*)malloc(sizeof(Element)); (*e)->next = NULL; (*e)->value = v; return; } void initArrayList(ArrayList** L) { (*L) = (ArrayList*)malloc(sizeof(ArrayList)); (*L)->head = NULL; (*L)->rear = NULL; (*L)->point = NULL; return; } void headInsert(ArrayList** L,int v) { Element* e = NULL; initElement(&e,v); if((*L)->head==NULL) { (*L)->head = e; (*L)->point = e; (*L)->rear = e; return; } e->next = (*L)->head; (*L)->head = e; return; } void rearInsert(ArrayList** L,int v) { Element* e = NULL; initElement(&e,v); if((*L)->head==NULL) { (*L)->head = e; (*L)->point = e; (*L)->rear = e; return; } (*L)->rear->next = e; (*L)->rear = e; return; } void intersectionSortedList(ArrayList** L1,ArrayList** L2,ArrayList** L3) { Element *p1,*p2; p1 = (*L1)->head; p2 = (*L2)->head; while(p1!=NULL&&p2!=NULL) { if(p1->value == p2->value) { rearInsert(L3,p1->value); p1 = p1->next; p2 = p2->next; }else if(p1->value < p2->value) { p1 = p1->next; }else { p2 = p2->next; } } } int main() { ArrayList* L1; ArrayList* L2; ArrayList* L3; Element* p; int cache; initArrayList(&L1); initArrayList(&L2); initArrayList(&L3); cache = 0; while(cache!=-1) { scanf("%d",&cache); if(cache!=-1) rearInsert(&L1,cache); } cache = 0; while(cache!=-1) { scanf("%d",&cache); if(cache!=-1) rearInsert(&L2,cache); } intersectionSortedList(&L1,&L2,&L3); p = L3->head; if(p==NULL) { printf("NULL"); return 0; } while(p!=NULL) { printf("%d",p->value); if(p->next!=NULL) { printf(" "); } p = p->next; } return 0; } ``` ### 单链表的创建及遍历 读入n值及n个整数，建立单链表并遍历输出。 ##### 输入格式: 读入n及n个整数。 ##### 输出格式: 输出n个整数，以空格分隔（最后一个数的后面没有空格）。 ##### 输入样例: 在这里给出一组输入。例如： ``` 2 10 5 ``` ##### 输出样例: 在这里给出相应的输出。例如： ``` 10 5 ``` ##### 参考答案（实现语言：C语言） ```c #include #include typedef struct Element { int value; struct Element* next; }Element; typedef struct ArrayList { Element* head; Element* rear; Element* point; int length; }ArrayList; void initElement(Element** e,int v) { (*e) = (Element*)malloc(sizeof(Element)); (*e)->next = NULL; (*e)->value = v; return; } void initArrayList(ArrayList** L) { (*L) = (ArrayList*)malloc(sizeof(ArrayList)); (*L)->head = NULL; (*L)->rear = NULL; (*L)->point = NULL; return; } void rearInsert(ArrayList** L,int v) { Element* e = NULL; initElement(&e,v); if((*L)->head==NULL) { (*L)->head = e; (*L)->point = e; (*L)->rear = e; return; } (*L)->rear->next = e; (*L)->rear = e; return; } int main() { ArrayList* L1; Element* p; int cache,len,i; initArrayList(&L1); scanf("%d",&len); cache = 0; for(i=0;ihead; while(p!=NULL) { printf("%d",p->value); if(p->next!=NULL) { printf(" "); } p = p->next; } return 0; } ``` ### 求链式线性表的倒数第K项 给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第K个位置上的数字。 ##### 输入格式: 输入首先给出一个正整数K，随后是若干非负整数，最后以一个负整数表示结尾（该负数不算在序列内，不要处理）。 ##### 输出格式: 输出倒数第K个位置上的数据。如果这个位置不存在，输出错误信息`NULL` ##### 输入样例: ``` 4 1 2 3 4 5 6 7 8 9 0 -1 ``` ##### 输出样例: ``` 7 ``` ##### 参考答案（实现语言：c语言） ```c #include #include typedef struct Element { int value; struct Element* next; }Element; typedef struct ArrayList { Element* head; Element* rear; Element* point; int length; }ArrayList; void initElement(Element** e,int v) { (*e) = (Element*)malloc(sizeof(Element)); (*e)->next = NULL; (*e)->value = v; return; } void initArrayList(ArrayList** L) { (*L) = (ArrayList*)malloc(sizeof(ArrayList)); (*L)->head = NULL; (*L)->rear = NULL; (*L)->point = NULL; return; } void rearInsert(ArrayList** L,int v) { Element* e = NULL; initElement(&e,v); if((*L)->head==NULL) { (*L)->head = e; (*L)->point = e; (*L)->rear = e; return; } (*L)->rear->next = e; (*L)->rear = e; (*L)->length +=1; return; } int main() { ArrayList* L1; Element* p; int cache,k,i; initArrayList(&L1); scanf("%d",&k); scanf("%d",&cache); while(cache>=0) { rearInsert(&L1,cache); scanf("%d",&cache); } p = L1->head; if(k-1>L1->length) { printf("NULL"); return 0; } i = L1->length-k; while(p!=NULL&&i>=0) { p = p->next; i--; } printf("%d",p->value); return 0; } ``` ### 链表倒数n个结点的乘积 本题要求计算单链表倒数n个结点的乘积。例如，给出单链表1 2 3 4 5，则倒数2个结点的乘积为20。 ##### 输入格式: 输入有2行，第一个行为2个非负整数m和n。其中m为链表结点个数，n为链表倒数结点的数量。题目保证计算结果在int范围内。 第二行为链表的m个数，以空格分隔。 ##### 输出格式: 在一行中输出倒数n个结点的乘积。 ##### 输入样例: ``` 5 2 1 2 3 4 5 ``` ##### 输出样例: ``` 20 ``` ##### 样例解释： 20 = 4 * 5 ##### 参考答案（实现语言：c语言） ```c #include #include typedef struct Element { int value; struct Element* next; }Element; typedef struct ArrayList { Element* head; Element* rear; Element* point; int length; }ArrayList; void initElement(Element** e,int v) { (*e) = (Element*)malloc(sizeof(Element)); (*e)->next = NULL; (*e)->value = v; return; } void initArrayList(ArrayList** L) { (*L) = (ArrayList*)malloc(sizeof(ArrayList)); (*L)->head = NULL; (*L)->rear = NULL; (*L)->point = NULL; return; } void rearInsert(ArrayList** L,int v) { (*L)->length += 1; Element* e = NULL; initElement(&e,v); if((*L)->head==NULL) { (*L)->head = e; (*L)->point = e; (*L)->rear = e; return; } (*L)->rear->next = e; (*L)->rear = e; return; } int main() { ArrayList* L1; Element* p; int cache,len,i,k,rs; initArrayList(&L1); scanf("%d",&len); scanf("%d",&k); cache = 0; for(i=0;ihead; i = L1->length - k - 1; if(k==0) { printf("0"); return 0; } rs = 1; while(p!=NULL) { if(i<0) { rs *= p->value; } i--; p = p->next; } printf("%d",rs); return 0; } ``` ### 在有序链表中插入数据 给定一批严格递增排列的整型数据，给定一个x，若x不存在，则插入x，要求插入后保持有序。存在则无需任何操作。 ##### 输入格式: 输入有两行： 第一个数是n值，表示链表中有n个数据。后面有n个数，分别代表n个数据。 第二行是要插入的数。 ##### 输出格式: 输出插入后的链表数据，以空格分开。行末不能有多余的空格。 ##### 输入样例1: 在这里给出一组输入。例如： ``` 5 1 3 6 9 11 4 ``` ##### 输出样例1: 在这里给出相应的输出。例如： ``` 1 3 4 6 9 11 ``` ##### 输入样例2: 在这里给出一组输入。例如： ``` 5 1 3 6 9 11 3 ``` ##### 输出样例2: 在这里给出相应的输出。例如： ``` 1 3 6 9 11 ``` ##### 参考答案（实现语言：c语言） ```c #include #include typedef struct Element { int value; struct Element* next; }Element; typedef struct ArrayList { Element* head; Element* rear; Element* point; int length; }ArrayList; void initElement(Element** e,int v) { (*e) = (Element*)malloc(sizeof(Element)); (*e)->next = NULL; (*e)->value = v; return; } void initArrayList(ArrayList** L) { (*L) = (ArrayList*)malloc(sizeof(ArrayList)); (*L)->head = NULL; (*L)->rear = NULL; (*L)->point = NULL; return; } void rearInsert(ArrayList** L,int v) { (*L)->length += 1; Element* e = NULL; initElement(&e,v); if((*L)->head==NULL) { (*L)->head = e; (*L)->point = e; (*L)->rear = e; return; } (*L)->rear->next = e; (*L)->rear = e; return; } int main() { ArrayList* L1; Element *p, *e,*q; int cache,len,i,t; initArrayList(&L1); scanf("%d",&len); cache = 0; for(i=0;ihead; q = NULL; if(p==NULL) { rearInsert(&L1,t); } while(p!=NULL){ if(L1->head->value > t) { initElement(&e,t); e->next = L1->head; L1->head = e; break; } if(p->value > t && q != NULL && q->value < t) { initElement(&e,t); e->next = p; q->next = e; break; } if(p->value == t) { break; } if(p->next == NULL && p->value < t) { rearInsert(&L1,t); break; } q = p; p = p->next; } //输出最终内容 p = L1->head; while(p!=NULL) { printf("%d",p->value); if(p->next!=NULL) { printf(" "); } p = p->next; } return 0; } ``` ### 二分查找 输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用**二分查找算法**查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。 ##### 输入格式: 输入共三行： 第一行是n值； 第二行是n个整数； 第三行是x值。 ##### 输出格式: 输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。 ##### 输入样例: ``` 4 1 2 3 4 1 ``` ##### 输出样例: ``` 0 2 ``` ##### 参考答案（实现语言：c语言） ```c #include #include //二分查找函数 int splitSearch(int *a,int s,int e,int t,int *c) { int mid = (s+e)/2; if(s>e) { return -1; } *c += 1; if(a[mid]==t) { return mid; } if(a[mid] #include //二分查找函数 int splitSearch(int *a,int s,int e,int t) { int mid = (s+e)/2; if(s>e) { return -1; } if(a[mid]==t) { return mid; } if(a[mid]