首页 > 编程语言 >山东大学计算机导论与程序设计基础限时测试三/作业三

山东大学计算机导论与程序设计基础限时测试三/作业三

时间：2024-08-21 11:24:49浏览次数：15  
标签：head ListNode struct int 导论 next 链表 限时 山东大学

A : 旋转数组

题目描述

给你一个数组 nums 。
nums 存在一个源数组originnums，其所有元素与 nums 相同，但按非递减顺序排列。
如果 nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则输出Yes ；否则，输出 No 。
源数组中可能存在 重复项 。

注意： 我们称数组 A 在轮转 x 个位置后得到长度相同的数组 B ，当它们满足 A[i] == B[(i+x) % A.length] ，其中 % 为取余运算。

输入格式

第一行一个数M，代表数据的组数。
之后M组数据，每组数据第一行数据N，代表nums中数据的个数，第二行N个数据为nums中数据。
10 < M < 50 ， 100 < N < 900 10<M<50，100<N<900 10<M<50，100<N<900

输出格式

共M行。
每行代表一组数据的输出，输出Yes或者No

完整答案代码

#include<stdio.h>
int f(int a[],int n){
	int i,j;
	int k=1;
	int x=1;
	int s=0;
	while(1){
		if(n==1){
			return 1;
		}
		for(i=0;i<n-1;i++){
			if(a[i]<=a[i+1]){
				x++;
			}else{
				x=1;
				break;
			}
			if(x==n){
				return 1;
			}
		}
		int l=0;
		int r=n-k-1;
		while(l<r){
			int t=a[r];
			a[r]=a[l];
			a[l]=t;
			r--;
			l++;
		}
		l=n-k;
		r=n-1;
		while(l<r){
			int t=a[l];
			a[l]=a[r];
			a[r]=t;
			r--;
			l++;
		}
		l=0;
		r=n-1;
		while(l<r){
			int t=a[l];
			a[l]=a[r];
			a[r]=t;
			r--;
			l++;
		} 
		if(s==n-1){
			return 0; 
		}
		s++;
	}
}
int main()
{
	int m;
	scanf("%d",&m);
	int i,j;
	int t;
	for(i=0;i<m;i++){
		int n;
		scanf("%d",&n);
		int a[n];
		for(j=0;j<n;j++){
			scanf("%d",&a[j]);
		}
		t=f(a,n);
		if(t==1){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}

	return 0;
 }

B : 链表的公共结点

题目描述

现在有一堆单向链表的结点互相连接，给定两个不在同一条链表上的头结点 a a a， b b b以及链表结点的连接情况，请求得这两个链表第一次相交位置所在的结点，返回该结点。

你需要做的是完成寻找链表公共节点的函数getIntersectionNode。

输入格式

该部分已由模板完成。

第一行三个数字n，m，k，n为第一个链表在公共节点之前的长度，m为第二个链表在公共节点之前的部分，k为两个链表公共部分的长度。

之后有三行数据，第一行n个数据，为第一个链表公共节点之前的部分，第二行m个数据，为第二个链表公共节点之前的部分，第三行k个数据，为链表公共部分。

函数的入参为两个链表，链表结构见代码模板

输出格式

第一个公共节点，该部分已由模板完成。

代码模板

## 题目描述

现在有一堆单向链表的结点互相连接，给定两个不在同一条链表上的头结点$a$，$b$以及链表结点的连接情况，请求得这两个链表第一次相交位置所在的结点，返回该结点。

你需要做的是完成寻找链表公共节点的函数`getIntersectionNode`。

## 输入格式

该部分已由模板完成。

> 第一行三个数字n，m，k，n为第一个链表在公共节点之前的长度，m为第二个链表在公共节点之前的部分，k为两个链表公共部分的长度。
>
> 之后有三行数据，第一行n个数据，为第一个链表公共节点之前的部分，第二行m个数据，为第二个链表公共节点之前的部分，第三行k个数据，为链表公共部分。

函数的入参为两个链表，链表结构见代码模板

## 输出格式

第一个公共节点，该部分已由模板完成。

## 代码模板

```c
#include "stdio.h"
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB);

// 根据数组创建一个链表
struct ListNode *createList(int *arr, int length) {
    struct ListNode *head = (struct ListNode *) malloc(sizeof(struct ListNode));
    struct ListNode *fakeHead = head;
    for (int i = 0; i < length; ++i) {
        struct ListNode *temp = (struct ListNode *) malloc(sizeof(struct ListNode));
        temp->val = arr[i];
        temp->next = NULL;
        head->next = temp;
        head = head->next;
    }
    return fakeHead->next;
}

// 合并两个链表
struct ListNode *concatList(struct ListNode *head1, struct ListNode *head2) {
    struct ListNode *pre = head1;
    if (head1 == NULL) {
        return head2;
    }
    while (head1->next != NULL) {
        head1 = head1->next;
    }
    head1->next = head2;
    return pre;
}

int main() {
    int n, m, k;
    // 链表A在公共节点前的部分的长度
    scanf("%d", &n);
    // 链表B在公共节点前的部分的长度
    scanf("%d", &m);
    // 公共节点部分长度
    scanf("%d", &k);
    int arrn[n];
    int arrm[m];
    int arrk[k];
    for (int i = 0; i < n; ++i) {
        scanf("%d", &arrn[i]);
    }
    for (int i = 0; i < m; ++i) {
        scanf("%d", &arrm[i]);
    }
    for (int i = 0; i < k; ++i) {
        scanf("%d", &arrk[i]);
    }
    // 创建三个链表   
    struct ListNode *headN = createList(arrn, n);
    struct ListNode *headM = createList(arrm, m);
    struct ListNode *headK = createList(arrk, k);
    // 将公共节点之前的部分和公共部分结合  
    struct ListNode *headA = concatList(headN, headK);
    struct ListNode *headB = concatList(headM, headK);
    // 获取链表的公共节点  
    struct ListNode *res = getIntersectionNode(headA, headB);
    while (res != NULL) {
        printf("%d ", res->val);
        res = res->next;
    }
    return 0;
}

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    // TODO: 填写获取公共节点的代码
}

完整答案代码

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

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB);

// 根据数组创建一个链表
struct ListNode *createList(int *arr, int length) {
    struct ListNode *head = (struct ListNode *) malloc(sizeof(struct ListNode));
    struct ListNode *fakeHead = head;
    for (int i = 0; i < length; ++i) {
        struct ListNode *temp = (struct ListNode *) malloc(sizeof(struct ListNode));
        temp->val = arr[i];
        temp->next = NULL;
        head->next = temp;
        head = head->next;
    }
    return fakeHead->next;
}

// 合并两个链表
struct ListNode *concatList(struct ListNode *head1, struct ListNode *head2) {
    struct ListNode *pre = head1;
    if (head1 == NULL) {
        return head2;
    }
    while (head1->next != NULL) {
        head1 = head1->next;
    }
    head1->next = head2;
    return pre;
}
// TODO: 填写获取公共节点的代码（自己要写的答案代码）
struct ListNode *getIntersectionNode(struct ListNode *headA,struct ListNode *headB){
	struct ListNode *p;
	p=headA;
	while(p){
		struct ListNode *t;
		t=headB;
		while(t){
			if(t==p){
				return t;
			}else{
				t=t->next;
			}
		}
		p=p->next;
	} 
}
int main() {
    int n, m, k;
    // 链表A在公共节点前的部分的长度
    scanf("%d", &n);
    // 链表B在公共节点前的部分的长度
    scanf("%d", &m);
    // 公共节点部分长度
    scanf("%d", &k);
    int arrn[n];
    int arrm[m];
    int arrk[k];
    for (int i = 0; i < n; ++i) {
        scanf("%d", &arrn[i]);
    }
    for (int i = 0; i < m; ++i) {
        scanf("%d", &arrm[i]);
    }
    for (int i = 0; i < k; ++i) {
        scanf("%d", &arrk[i]);
    }
    // 创建三个链表   
    struct ListNode *headN = createList(arrn, n);
    struct ListNode *headM = createList(arrm, m);
    struct ListNode *headK = createList(arrk, k);
    // 将公共节点之前的部分和公共部分结合  
    struct ListNode *headA = concatList(headN, headK);
    struct ListNode *headB = concatList(headM, headK);
    // 获取链表的公共节点  
    struct ListNode *res = getIntersectionNode(headA, headB);
    while (res != NULL) {
        printf("%d ", res->val);
        res = res->next;
    }
    return 0;
}

A : 判断2的幂

题目描述

给出一个非负整数 n n n，请你判断它是否为2的幂。如果一个整数是2的幂，这意味着它可以写成 2 k 2^k 2k 的形式，其中 k k k 是一个非负整数。例如，1（ 2 0 2^0 20）、2（ 2 1 2^1 21）、4（ 2 2 2^2 22）、8（ 2 3 2^3 23）等都是2的幂。

输入格式

单行输入，包含一个非负整数 n n n，满足 0 ≤ n < 2 31 0 \leq n < 2^{31} 0≤n<231。

输出格式

输出一行。如果 n n n 为2的幂，则输出 Yes，否则输出 No。

样例数据与解释

样例输入 1

16

样例输出 1

Yes

解释 1

16 可以表示为 2 4 2^4 24，因此它是2的幂。

样例输入 2

18

样例输出 2

No

解释 2

18 不能表示为 2 k 2^k 2k 的形式，因此它不是2的幂。

样例输入 3

0

样例输出 3

No

解释 3

0 不能表示为 2 k 2^k 2k 的形式，因此它不是2的幂。

数据规模与特性

  • 对于 100 % 100\% 100% 的数据， 0 ≤ n < 2 31 0 \leq n < 2^{31} 0≤n<231。

完整答案代码

#include<stdio.h>
int main(){
	unsigned int n;
	scanf("%d",&n);
	int m=1;
	unsigned i;
	for(i=1;i<=n;i=i*2){
		m=n%i;
	}
	if(m==0||n==1){
		printf("Yes");
	}else{
		printf("No");
	}
	return 0; 
}

B : 删除链表重复结点

题目描述

给出一个有序链表，请你删除链表中所有重复的结点。

本题中输入输出已由模板给出，请阅读并补全模板代码。

代码模板

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

// 结点类
struct ListNode {
    int val;
    struct ListNode *next;
};

// 需要实现的函数
void deleteDuplicates(struct ListNode *head);

int main() {
    int amount;
    struct ListNode *head, *temp;
  
    // 读入数据
    scanf("%d", &amount);
    for (int i = 0; i < amount; i++) {
        struct ListNode *input = (struct ListNode *) malloc(sizeof(struct ListNode));
        scanf("%d", &(input->val));

        if (i == 0) {
            head = input;
            temp = head;
        } else {
            temp->next = input;
            temp = temp->next;
        }

        if (i == amount - 1)
            temp->next = NULL;
    }
  
    // 执行函数
    deleteDuplicates(head);

    // 输出
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
}

// TODO: 在下方补全函数实现

完整答案代码

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

// 结点类
struct ListNode {
    int val;
    struct ListNode *next;
};

// 需要实现的函数（自己要写的答案部分）
void deleteDuplicates(struct ListNode *head){
	struct ListNode *p=head;
	while(p){
		if(p->next!=NULL && p->val==p->next->val){
			p->next=p->next->next;
		}else{
			p=p->next;
		}
	}
	
}
int main() {
    int amount;
    struct ListNode *head, *temp;
  
    // 读入数据
    scanf("%d", &amount);
    for (int i = 0; i < amount; i++) {
        struct ListNode *input = (struct ListNode *) malloc(sizeof(struct ListNode));
        scanf("%d", &(input->val));

        if (i == 0) {
            head = input;
            temp = head;
        } else {
            temp->next = input;
            temp = temp->next;
        }

        if (i == amount - 1)
            temp->next = NULL;
    }
  
    // 执行函数
    deleteDuplicates(head);

    // 输出
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
}

如能打赏，不胜感激[叩谢]。

标签：head,ListNode,struct,int,导论,next,链表,限时,山东大学
From： https://blog.csdn.net/Water_Star1/article/details/141350092

相关文章

  • 山东大学计算机导论与程序设计基础实验11-12
    A:实验11斐波那契序列题目描述使用递归法求斐波那契序列第n项的值。斐波那契序列的定义：f(n)......
  • 计算机导论与程序设计基础限时测试二和作业二
    A : 最大子数组和题目描述给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。输入格式共2行数。第一行为数组长度n。对于测试点1-12：0<n≤1000对于测试点13-14：10000<n≤20000对于......
  • 山东大学计算机导论与程序设计基础实验1-4
    A:实验1.1标准数学函数使用实验要求1.在你所创建的工程文件中，编程熟悉C程序的基本框架，以及C语言提供的标准数学函数，并按一定的格式输出程序的执行结果；Tips:我该怎么输出我的结果？在写完程序主题之后，使用printf()函数或cout来输出题目要求的结果。注意：不要在......
  • 计算机导论与程序设计基础实验5-9
    A:实验5字符串的输入输出题目描述利用循环结构连续调用scanf(”%[^\n]”,str)输入多个字符串，并使用printf()，将str输出。根据str的输出结果，观察是否在输入一个字符串后，后续的scanf(”%[^\n]”,str)中，会将缓冲区中残留的回车换行符读入到str中。提示：利用格式scanf(”%[......
  • 【数学建模导论】Task05 多模数据与智能模型
    前言在多模数据中，涉及以下领域数字图像处理与计算机视觉计算语言学与自然语言处理数字信号处理与智能感知多模态学习——融合不同的数据类型（如图像和文本）：是机器学习的一个重要分支。是处理复杂数据分析问题的关键❤️❤️❤️❤️❤️系列文章导航【数学建模导论】Ta......
  • 文心一言 VS 讯飞星火 VS chatgpt （320）-- 算法导论22.3 12题
    十二、证明：我们可以在无向图G上使用深度优先搜索来获得图G的连通分量，并且深度优先森林所包含的树的棵数与G的连通分量数量相同。更准确地说，请给出如何修改深度优先搜索来让其给每个结点赋予一个介于1和k之间的整数值v.cc，这里k是G的连通分量数，使得u.cc=v.cc当且仅当结点u和结......
  • 文心一言 VS 讯飞星火 VS chatgpt （319）-- 算法导论22.3 11题
    十一、请解释有向图的一个结点u怎样才能成为深度优先树中的唯一结点，即使结点u同时有入边和出边。如果要写代码，请用go语言。文心一言：在一个有向图中，如果结点u在深度优先搜索（DFS）的过程中成为深度优先树（DFS树）中的唯一结点，这通常意呀着在DFS遍历的某个特定时刻，从u出发能够探索......
  • 山东大学计算机组成原理实验13控制器实验（含原理图，实验结果实物图，结论分析）
    实验内容及说明  目前控制器设计大都采用微程序设计方法，又称存储逻辑控制器。微程序控制器电路结构如图13-1所示。它由控制存储器CROM、微程序μPC计数器和微指令寄存器μIR构成。  其中，微程序计数μPC向控制存储器提供8位微地址，在控存读信号μRD‘的作用下，读出一条......
  • 山东大学计算机网络实验Wireshark Lab:TLS v8.1（含问题答案）
    实验方法介绍  在本实验中，将研究传输层安全性(称为TLS)以及TLS提供的身份验证、数据完整性和机密性服务的各个方面。TLS是现已弃用的安全套接字层(SSL)的继承者。将通过分析在通过HTTPS检索网页期间捕获的Wireshark数据包跟踪来研究TLS。HTTPS是HTTP的安全版本，它在HTTP之......
  • 软件工程专业导论大作业-关于华为自主研发的新编程语言基本原理其应用场景分析
    摘 要在2024年6月21日的华为开发者大会上，华为宣布了其自主研发的全新编程语言——“仓颉”。这一语言的推出旨在为其“升腾”AI芯片和云原生应用开发提供强大支持，并且有助于构建全球技术生态系统。“仓颉”编程语言特别设计以应对华为“升腾”AI芯片的需求，并且专注于硬件和......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99