导航：复试上机历年真题，题目未搜集全
十四：2003 十三：2004
十二：2005 十一：2006
十：2007 九：2008
八：2009 七：2012
六：2013 五：2014
四：2015 三：2017
二：2018 一：2019
六、2013
1、素数
题目：
打印 n 以内（包括 n）的所有素数，从小到大，中间用空格隔开。
代码：
#include<stdio.h>
bool isprime(int x)//判断x是否为素数
{
for(int i=2;i<=x/2;i++)
if(x%i==0)
return false;
return true;
}
int main()
{
int N;
scanf("%d", &N);
for(int i=2;i<=N;i++)
{
if(isprime(i)==true)
printf("%d ", i);
}
return 0;
}
2、波兰式
题目：
表达式 a+b*(c-d)+m/c 求出波兰式先序遍历
对于 a+b*(c-d)+m/c 其用二叉树表示为
- 用+*+a..b..-c..d../m..c..先序创建该二叉树
- 其中序遍历结果即为a+b*c-d+m/c
代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
//波兰式：a+b*(c-d)+m/c
//输入 +*+a..b..-c..d../m..c..创建一颗二叉树
//二叉树的中序遍历为 a+b*c-d+m/c
//二叉树的先序遍历为
typedef struct BTNode{
char data;
struct BTNode *lchild, *rchild;
}BTNode, *BTree;
void creatBT(BTree *bt)//创建二叉树
{
char ch;
scanf("%c", &ch);
if(ch=='.')
*bt = NULL;
else
{
BTNode *q;
q = new BTNode;
q->data = ch;
q->lchild = NULL; q->rchild = NULL;
*bt = q;
creatBT(&((*bt)->lchild));
creatBT(&((*bt)->rchild));
}
}
void inTravel(BTree bt)//中序遍历二叉树
{
if(bt!=NULL)
{
inTravel(bt->lchild);
printf("%c", bt->data);
inTravel(bt->rchild);
}
}
void preTravel(BTree bt)//先序遍历二叉树
{
if(bt!=NULL)
{
printf("%c", bt->data);
preTravel(bt->lchild);
preTravel(bt->rchild);
}
}
void printTree(BTree bt, int layer)//层级打印二叉树
{
if(bt!=NULL)
{
printTree(bt->rchild, layer+1);
for(int i=0;i<layer;i++)
printf(" ");
printf("%c
", bt->data);
printTree(bt->lchild, layer+1);
}
}
int main()
{
BTree bt;
creatBT(&bt);
printf("波兰式");
inTravel(bt);
printf("的先序遍历为：");
preTravel(bt);
printf("二叉树层级遍历为：
");
printTree(bt, 0);
return 0;
}
3、公共字符串
题目：
字符串：x[]=mcdabhaad，y[]=mavbmmcbn，求出：z[]=mab，即是把相同的部分给提取出来放到另外一个数组中输出
动态规划求最长公共子序列LCS：
对于两个字符串如A[]='sadsto', B[]='admin'。
令dp[i][j]为字符串A第i位与字符串B第j位之间的最大长公共子序列长度，如dp[4][5]表示'sads'与'admin'的最长公共子序列，显然这是dp[4][5]=2，子串为ad；
对于A[i]与B[j]可以分为两种情况：
- A[i]==B[j],这时最长公共子序列长度加1，dp[i][j]=dp[i-1][j-1]+1,如dp[3][2]表示'sad'与'ad'的公共子序列长度，则dp[3][2]=dp[2][1]+1，
- A[i]!=B[j],字符串A的第i位于字符串B的第j位之前的最长公共子序列长度无法延长，因此dp[i][j]为dp[i-1][j]与dp[i][j-1]中较大的一个，即dp[i][j]=max(dp[i][j-1], dp[i-1][j])。dp[3][3]表示"sad"与"adm"的最长公共子序列的长度，对于A[3]与B[3]，发现'd'!='m'，则继承'sa'与'adm'或者'sad'与'ad'中的最长公共子序列的长度较大者，即dp[3][3]=2;
因此其状态转移方程为：
- dp[i][j]=dp[i-1][j-1]+1， （A[i]==B[j]）
- dp[i][j]=max(dp[i][j-1], dp[i-1][j])， （A[i]!=B[j]）
代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn=100;
int dp[maxn][maxn];
int main()
{
char str[maxn];
int num=0;
char str1[maxn], str2[maxn];
gets(str1+1);
gets(str2+1);
int len1, len2;
len1 = strlen(str1+1);
len2 = strlen(str2+1);
//边界值初始化
for(int i=0;i<len1;i++)
dp[i][0] = 0;
for(int j=0;j<len2;j++)
dp[0][j] = 0;
//状态方程
for(int i=1;i<len1;i++)
for(int j=1;j<len2;j++)
{
if(str1[i]==str2[j])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
printf("最大公共部分长度为：%d
", dp[len1-1][len2-1]);
//打印dp数组
// for(int i=0;i<len1;i++)
// {
// for(int j=0;j<len2;j++)
// printf("%3d", dp[i][j]);
// printf("
");
// }
//查找公共部分，并放在str数组中
num = dp[len1-1][len2-1];
for(int i=len1-1;i>=0;i--)
{
for(int j=len2-1;j>=0;j--)
if(str1[i]==str2[j]&&dp[i][j]==num)
{
num--;
str[num] = str1[i];
}
}
printf("公共部分为：%s",str);
}
4、大数相加
题目：
如12345678+11111111=23456789；
对于输入的数为'123456789'， 显然最高位为1， 先定义一个大数，大数中有，数组长度len=9，以及数组d[]={9,8,7,6,5,4,3,2,1,},为了方便两个大数相加的时候进位，需要将低位放在前面。
代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int maxn=100;
typedef struct bign
//定义一个大数
{
int d[maxn];
int len;
bign(){
len = 0;
fill(d, d+maxn, 0);//先初始化为0
}
}bign;
bign generate(char str[])
//生成一个大数，str=123,大数为321，方便进位，需要将高位与低位反转
{
bign res;
int len;
len = strlen(str);
reverse(str, str+len);
res.len = len;
for(int i=0;i<len;i++)
res.d[i] = str[i]-'0';
return res;
}
bool compare(bign a, bign b)
//a>b返回1，a<b返回-1，a=b返回0
{
if(a.len>b.len)
return 1;
else if(a.len<b.len)
return -1;
else if(a.len==b.len)
{
for(int i=a.len-1;i>=0;i--)
if(a.d[i]>b.d[i])
return 1;
else if(a.d[i]<b.d[i])
return -1;
}
return 0;
}
bign add(bign a, bign b)
//大数相加
{
bign c;
int carry, temp;
carry = 0;//为进位值
temp = 0;
if(compare(a, b)==-1)
//保证A>B
swap(a, b);
for(int i=0;i<a.len||i<b.len;i++)//逐个位相加
{
temp = a.d[i]+b.d[i]+carry;
carry = (a.d[i]+b.d[i])/10;
c.d[c.len++] = temp%10;
}
if(carry>0)//最后一位进位
c.d[c.len++] = carry;
return c;
}
void printfBign(bign c)
{
if(c.len==0)//如果c为0
printf("0");
else
{
for(int i=c.len-1;i>=0;i--)//从后往前，从高位向低位打印
printf("%d", c.d[i]);
}
printf("
");
}
int main()
{
char A[maxn], B[maxn];
bign a, b, c;
gets(A);
gets(B);
a = generate(A);
b = generate(B);
c = add(a, b);
printfBign(c);
return 0;
}