2015年天勤考研机试模拟赛解题报告

2015年天勤考研机试模拟赛解题报告

A: 判断三角形

这题可以用map建立单词与数字之间的映射，也可以用if...else来写。唯一可能成为坑的是前几个单词可能是zero。

代码：http://wendang.chazidian.com/10616118/

#include <cstdio>

#include <cstring>

intstrToNum(char str[]) {

if(strcmp(str, "zero") == 0) return 0;

if(strcmp(str, "one") == 0) return 1;

if(strcmp(str, "two") == 0) return 2;

if(strcmp(str, "three") == 0) return 3;

if(strcmp(str, "four") == 0) return 4;

if(strcmp(str, "five") == 0) return 5;

if(strcmp(str, "six") == 0) return 6;

if(strcmp(str, "seven") == 0) return 7;

if(strcmp(str, "eight") == 0) return 8;

if(strcmp(str, "nine") == 0) return 9;

}

int main() {

int n, len[3] = {0};

char c, str[10];

for(inti = 0; i< 3; i++) {

scanf("%d", &n);

for(int j = 0; j < n; j++) {

scanf("%s", str);

len[i] = len[i] * 10 + strToNum(str);

}

}

if(len[0] + len[1] >len[2] &&

len[0] + len[2] >len[1] &&

len[1] + len[2] >len[0]) {

printf("YES\n");

} else printf("NO\n");

return 0;

}

B: 删除结点

此题为15年408数据结构大题第一题（算法设计题），仿照PAT出题风格而出，所有的坑都是仿照PAT的题目而设计。坑点有：

（1） 虽然结点的Address地址不会是-1，但是第一个结点的地址可能是-1，由此可能导致部

分代码输出超限或者运行超时或者运行错误。（这是PAT中题目的坑点之一）

（2） 可能有不在单链表上的结点，也就是无效结点。这可能导致答案错误。（这也是PAT中

题目的坑点之一）

代码：http://wendang.chazidian.com/10616121/

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

constintmaxn = 100005;

constint TABLE = 1000010;

struct Node { //定义静态链表（第一步）

int address, data, next;

int order; //结点在链表上的序号，无效结点记为maxn

}node[maxn];

boolisExist[TABLE] = {false};

boolcmp(Node a, Node b) {

returna.order<b.order;

}

int main() {

memset(isExist, false, sizeof(isExist));

for(inti = 0; i<maxn; i++) { //初始化（第二步）

node[i].order = maxn;

}

int n, begin, address;

scanf("%d%d", &n, &begin);

for(inti = 0; i< n; i++) {

scanf("%d", &address);

scanf("%d%d", &node[address].data, &node[address].next);

node[address].address = address;

}

int count = 0, p = begin;

while(p != -1) { //枚举链表，计数有效结点个数（第三步）

if(!isExist[abs(node[p].data)]){

isExist[abs(node[p].data)] = true;

node[p].order = count++;

}

p = node[p].next;

}

if(count == 0) { //特判，新链表中没有结点时输出0 -1

printf("0 -1\n");

} else {

sort(node, node + maxn, cmp); //筛选有效结点，并按结点顺序排序（第四步） //输出结果（第五步）

printf("%d %05d\n", count, node[0].address); //防止-1被%05d化，因此提前判断 for(inti = 0; i< count; i++) {

if (i != count - 1) {

printf("%05d %d %05d\n", node[i].address, node[i].data, node[i+1].address); } else {

printf("%05d %d -1\n", node[i].address, node[i].data);

}

}

}

return 0;

}

C: 收集数码晶体

此题为15年408数据结构大题第二题。本题其实是求这样一个问题：求从起点S到终点T的长度为L的路径条数，而这恰好就是邻接矩阵的L次幂。注意在求幂时也要时刻模上1000000007，否则可能爆long long使结果变成负数。

本题用DFS/BFS会超时，复杂度爆棚了。

代码：http://wendang.chazidian.com/10616125/

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

constintmaxn = 60;

const long long MOD = 1000000007;

longlong G[maxn][maxn], ans[maxn][maxn], temp[maxn][maxn];

voidMatrixPow(int n, int L) {

for(int times = 0; times < L; times++) {

for(inti = 0; i< n; i++) {

for(int j = 0; j < n; j++) {

temp[i][j] = 0;

for(int k = 0; k < n; k++) {

temp[i][j] = (temp[i][j] + (ans[i][k] * G[k][j] % MOD + MOD)) % MOD;

}

}

}

for(inti = 0; i< n; i++) {

for(int j = 0; j < n; j++) {

ans[i][j] = temp[i][j];

}

}

}

}

voidinit() {

memset(G, 0, sizeof(G));

memset(ans, 0, sizeof(ans));

for(inti = 0; i<maxn; i++) {

ans[i][i] = 1;

}

}

int main() {

init();

int n, m, L, u, v;

scanf("%d%d%d", &n, &m, &L);

for(inti = 0; i< m; i++) {

scanf("%d%d", &u, &v);

G[u][v] = 1;

}

MatrixPow(n, L);

int k;

scanf("%d", &k);

for(inti = 0; i< k; i++) {

scanf("%d%d", &u, &v);

printf("%lld\n", (ans[u][v] % MOD + MOD) % MOD);

}

return 0;

}

D: 还原二叉树

不同在于后面的步骤。

但是层序不行，层序的左右子树结点在层序序列中可能是分散的。因此必须想办法把左子树所有结点跟右子树所有结点都找出来。

于是可以开两个vector，一个存左子树所有结点的层序，一个存右子树所有结点的层序。然后遍历当前层序序列的所有结点，根据中序序列判断其属于左子树还是右子树，如果是左子树就push_back到左子树的vector，否则就push_back到右子树的vector。

这样就可以继续递归了，递归参数中用vector表示层序，而中序可以仍然用数组下标。 代码：http://wendang.chazidian.com/10616131/

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

constintmaxn = 50;

struct node {

int data;

node* lchild;

node* rchild;

};

int in[maxn]; //中序

//当前二叉树的层序序列为layer，中序序列区间为[inL, inR]

//create函数返回构建出的二叉树的根结点地址

node* create(vector<int> layer, intinL, intinR) {

if(layer.size() == 0) {

return NULL;

}

node* root = new node; //新建一个新的结点，用来存放当前二叉树的根结点

root->data = layer[0]; //新结点的数据域为根结点的值

int k;

for(k = inL; k <= inR; k++) {

if(in[k] == layer[0]) {

break;

}

}

vector<int>layerLeft;

vector<int>layerRight;

for(inti = 1; i<layer.size(); i++) {

boolisLeft = false;

for(int j = inL; j < k; j++) {

if(layer[i] == in[j]) {

isLeft = true;

break;

}

}

if(isLeft) {

layerLeft.push_back(layer[i]);

} else {

layerRight.push_back(layer[i]);

}

}

root->lchild = create(layerLeft, inL, k - 1); root->rchild = create(layerRight, k + 1, inR); return root; //返回根结点地址 }

intnum;

voidpreOrder(node* root,int n) { if(root == NULL) {

return;

}

printf("%d", root->data);

num++;

if(num< n) printf(" ");

elseprintf("\n");

preOrder(root->lchild, n);

preOrder(root->rchild, n);

}

voidpostOrder(node* root,int n) { if(root == NULL) {

return;

}

postOrder(root->lchild, n);

postOrder(root->rchild, n);

printf("%d", root->data);

num++;

if(num< n) printf(" ");

elseprintf("\n");

}

int main() {

vector<int> layer;

int n, temp;

scanf("%d", &n);

for(inti = 0; i< n; i++) {

scanf("%d", &temp);

layer.push_back(temp);