吉大研究生入学考试题！大家做做看看^_^
150分，3个小时，要求写出编程思想和具体代码！
第一题是写递归函数，很简单：
f(0)=0,
f(1)=1;
f(2n)=f(n);
f(2n+1)=f(n)+f(2n-1);
第二题是大体意思这样，要求写函数：
求一个整数的阶乘的低位区的连续零的个数；
比如11！=8977898900（具体数值不记得了，但是最后是两个0），要求返回2
要求写一个函数，要求以整数作为参数，返回它的阶乘的低位区的连续零的个数。
第三题与以前的一个题目很相似，要求写完整的程序，是关于螺旋矩阵的问题：
K=M*N,要求M,N（均是大于2小于100）在程序中输入，
输出从1到K的整数，输出M行，每行N列，按顺时针方向输出。
如M=4,N=6.
输出
1， 2， 3， 4， 5， 6
16，17，18，19，20， 7
15 ，24，23，22，21， 8
14，13，12，11，10， 9
第四题是识别字符串的题目，也要求完整的程序，
给定一个规则，也即文法，这个规则是由一些子规则通过“或”关系构成的，要求判断一个字符串（自己输入）是不是符合这个规则，就是判断是不是符合某一个子规则。
如果是，输出“Yes”,否则，输出“No”.
第五题是要求输出2~50之间整数的倒数的小数部分，（记不清楚了），无限循环的小数要求第一个循环完成的时候就要输出。
<这个题目直接放弃了>
第六题和第四题差不多，是判断一个表达式是不是符合文法，如果不是，输出“Error”,否则要计算出结果。
文法好象是这些：
E=E+T|E-T|E*T|T
T=F|^^^^^^(不记得了)
F=D|(E)
D=0|1|2|3|4|5|6|7|8|9
输出0~9之间数字，并且负数输出0吧好象，大于10输出其个位数字。
第七题是，给定了二叉树的矩阵形式：
-------------
|8|-1|-1|
------------
|5|2|4|
-----------
|6|5|1|
-----------
|7|-1|-1|
------------
|4|-1|-1|
第一列是结点的值，第二列是左子树所在的行，第三列是右子树所在的行，
-1表示没有子树。
（1）：要求以二维数组表示二叉树，并且写一段代码，将二叉树以动态数据结构表示，并指出你的声明中哪个是根结点，方法不限。
（2）：要求根据写出中序遍历刚才建立的二叉树的递归程序。
问题点数：20、回复次数：23Top
1 楼baryjim（吃饭－睡觉－打豆豆）回复于 2005-01-24 11:54:24 得分 0
第五题是要求输出2~50之间整数的倒数的小数部分，（记不清楚了），无限循环的小数要求第一个循环完成的时候就要输出。
我的方法很笨的，就是像小学除法那么做，我知道一个公式，可惜用不上。
1/9=0.1111
2/9=0.2222
17/99=0.171717....
不知道大家有没有高明的方法？Top
2 楼Macosx（结贴）回复于 2005-01-24 11:58:21 得分 1
越来越像JOJ的题目了 用状态机判断文法是否正确 写起来可老费时间了
题量够大但感觉不难Top
3 楼Macosx（结贴）回复于 2005-01-24 12:01:50 得分 1
第五题可不可以写一个类似手算除法的函数 然后再判断商Top
4 楼Disaster（载荷之舟）回复于 2005-01-24 19:39:20 得分 1
第5题我考试的时候作出来了，i是2--50以内的数，设变量c，如果10以内的数，令c=10，if c%i==0,输出"0.c/i".
否则，设数组t[],令s=c,do{ t[j++]=c/i，c=(c%i)*10 } while(s!=c&&c!=0),这样t数组中存储的就是第一次循环的小数，这个过程类似于手工除法Top
5 楼autoegg（哲学指引生活 && (动心忍性，增益其所不能)）回复于 2005-01-25 10:34:09 得分 1
楼主考的是吉大什么专业的研究生？Top
6 楼LuteXL（吟游诗人）回复于 2005-01-25 17:13:30 得分 2
刚刚把螺旋矩阵那个用C＋＋实现了一下，有点意思：）
编译环境：Dev-C++
/*********************************************
* File: SprialMatrix.CPP *
* Author: Lute(Lute_fan@hotmail.com) *
* Date: Jan, 25nd, 2005 *
* Desc: How to create a sprial matrix *
*********************************************/
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
class SprialMatrix
{
private:
int ai, aj;
int count; //fill number
int m, n; //Dimension of the array
int* a; //Pointer to the array
int elenum; //the number of elements in this array, it equal to m*n
public:
//Constructor & Destructor//////////////////////////////////////////
explicit SprialMatrix(int _m, int _n):
m(_m), n(_n), ai(0), aj(0), count(0), elenum(m*n)
{
a = new int[elenum];
if(!a)
{
cout<<"Error to allocate the memory!"<<endl;
return;
}
memset(a, 0, sizeof(int)*elenum);
}
~SprialMatrix()
{
delete [] a;
}
public:
//Using 1-Dimensional array to simulate 2-Dimensional array////////
bool ParameterInvalid(int x, int y)
{
if(x<0 || x>m-1 || y<0 || y>n-1)
{
cerr<<"Invalid Parameter!"<<endl;
return false;
}
return true;
}
int ReadElement(int x, int y)
{
if(!ParameterInvalid(x, y))
return -1;
return a[x*n+y];
}
void WriteElement(int x, int y, int elem)
{
if(!ParameterInvalid(x, y))
return;
a[x*n+y] = elem;
}
void PrintMatrix()
{
//cout.setf(ios::left, ios::adjustfield);
cout<<"Sprial Matrix "<<m<<'*'<<n<<":"<<endl;
for(int i=0; i<elenum; i++)
{
if(i%n == 0)
cout<<endl;
cout<<a[i]<<' ';
}
}
//Contoral functions: Left, Right, Down, Up////////////////////////////
void GoLeft(int steps)
{
for(int i=0; i<steps; i++)
WriteElement(ai, aj--, ++count);
}
void GoRight(int steps)
{
for(int i=0; i<steps; i++)
WriteElement(ai, aj++, ++count);
}
void GoUp(int steps)
{
for(int i=0; i<steps; i++)
WriteElement(ai--, aj, ++count);
ai++;
aj++;
}
void GoDown(int steps)
{
for(int i=0; i<steps; i++)
WriteElement(ai++, aj, ++count);
}
//Generate the Sprial matrix//////////////////////////////////
void GenSprialMatrix()
{
int stepv = n-1;
int steph = m-1;
while(count<elenum)
{
GoRight(stepv);
GoDown(steph);
GoLeft(stepv);
GoUp(steph);
stepv -= 2;
steph -= 2;
}
}
};//class SprialMatrix
int main()
{
SprialMatrix matrix(8, 7);
matrix.GenSprialMatrix();
matrix.PrintMatrix();
system("pause");
return 0;
}
输出：
Sprial Matrix 8*7:
1 2 3 4 5 6 7
26 27 28 29 30 31 8
25 44 45 46 47 32 9
24 43 54 55 48 33 10
23 42 53 56 49 34 11
22 41 52 51 50 35 12
21 40 39 38 37 36 13
20 19 18 17 16 15 14
Top
7 楼bacmoz（）回复于 2005-01-25 17:52:55 得分 1
第5题一个方法就是对循环节的长度进行循环
求a/b的循环节，判断99...9*a/b是否整数
采用数组保存99...9，判断余数，余数为0时商为循环节
csdn应该讨论过很多次了
忘了有没有好的方法Top
8 楼mathe（）回复于 2005-01-25 18:08:42 得分 2
1/n，可以先将n中所有因子2和5去掉，得到m，然后
计算1/m，这时，1/m的循环节肯定从小数点后第一位开始，
这时，判断方法就很简单
int buf[m];//循环长度不超过m
int index=0;
int carray=1;
do{
int x=carray*10;
buf[index++]=x/m;
carray=x%m;
}while(carray!=1);
这时，buf[0:index-1]里面给出了1/m的循环节。
然后再除以(n/m) 就可以了。
Top
9 楼MaxDD（激活）回复于 2005-01-26 16:27:19 得分 1
全是大题么？
看来挺难的啊。Top
10 楼baryjim（吃饭－睡觉－打豆豆）回复于 2005-01-26 18:40:09 得分 0
全是大题,难吗?我觉得还可以,如果觉得难的话,平时肯定没多动手吧^_^Top
11 楼ayalicer（小刀惋心）回复于 2005-02-01 11:36:17 得分 1
题目都不算难 就是不熟练的话 时间恐怕不够Top
12 楼stoneywang（喜欢飞）回复于 2005-02-01 19:49:31 得分 1
第5題如果以前沒見過的話,沒那麼容易做的吧,感覺考數學知識更多點
Top
13 楼AcerHeart（不辞长做岭南人）回复于 2005-02-01 21:11:40 得分 1
上面的螺旋阵的，如果m=10,n=8不正确，其他的没试过Top
14 楼languagec（各有所求）回复于 2005-02-02 09:28:34 得分 1
第二个只要求5的因子个数就行了.
while(n)
{
s=s+n/5;
n=n/5;
}
print(s)Top
15 楼languagec（各有所求）回复于 2005-02-02 09:30:20 得分 0
第五个,判断余数是否有重复,若重复就是循环Top
16 楼xiaolucky（小铭）回复于 2005-02-03 01:23:35 得分 0
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class SprialMatrix
{
static int z;
public SprialMatrix()
{
z = 0;
}
public static void main(String args[])
{
int a, b;
try{
System.err.print("Enter a number: ");
System.out.flush();
BufferedReader br = new BufferedReader(new InputStreamReader(System.
in));
a = Integer.parseInt(br.readLine());
System.err.print("Enter a number: ");
System.out.flush();
b = Integer.parseInt(br.readLine());
int[][] m = new SprialMatrix().fillArray(a, b);
for(int i = 0; i < a; i++){
for(int j = 0; j < b; j++){
if(i==0){
System.out.print(m[i][j] + " ");
}else{
System.out.print(m[i][j] + " ");
}
}
System.out.println("");
}
} catch(Exception e){
e.printStackTrace();
}
}
private int[][] fillArray(int a, int b)
{
int[][] matrix = new int[a][b];
int y = a;
int x = b;
int c = 3;
int d = 0;
int e = b - 1;
int f = a - 1;
int g = 0;
int h = 0;
int j = 1;
int k = b - 2;
int l = a - 2;
int u = 0;
int v = 1;
while(a * b != z){
c = (c + 5) % 0x04;
switch(c){
case 0:
for(int i = h++; i < x; i++){
z++;
matrix[d][i] = z;
}
d++;
x--;
break;
case 1:
for(int i = j++; i < y; i++){
z++;
matrix[i][e] = z;
}
e--;
y--;
break;
case 2:
for(int i = k--; i >= u; i--){
z++;
matrix[f][i] = z;
}
u++;
f--;
break;
case 3:
for(int i = l--; i >= v; i--){
z++;
matrix[i][g] = z;
}
v++;
g++;
break;
}
}
c++;
return matrix;
}
}
螺旋矩阵java实现Top
17 楼pcboyxhy（-273.15℃）回复于 2005-02-03 20:27:03 得分 1
1 2 5 7比较好做
可能是因为我们还学编译
阶乘连续0的个数其实就是统计5的幂
f(n)=x*5^y
y就是0的个数了
Top
18 楼jettylee（要学的还很多~~~）回复于 2005-02-03 22:28:25 得分 1
这是什么专业的研究生题阿。。。 居然靠的全是ICPC的题
吉大ACM还是不错的 难道要研究生也参与么？？
参加过ACM的对这种题都太简单了
Top
19 楼baryjim（吃饭－睡觉－打豆豆）回复于 2005-02-03 23:47:34 得分 0
计算机专业啊！！
这些题并没有涉及到算法，应该不是ACM的题吧！Top
20 楼xiaoyi20（）回复于 2005-02-04 11:28:26 得分 1
矩阵的我的想法是先把最外面的那个框框先填充出来，那很容易。剩下的数据就只是S型了。那很容易。估计15分钟就可以搞定了。Top
21 楼xiaoyi20（）回复于 2005-02-04 11:30:21 得分 1
第6题和第4题，汗，俺平时的练习题里就有。俺没考研。Top
22 楼huangry（凯撒）回复于 2005-02-04 13:00:01 得分 1
明明基本都是典型的ACM题目 出题目的老师烂呗肯定
现在有很多学校计算机系的学生基本上就是ACM专业的了 嘿嘿Top
23 楼pcboyxhy（-273.15℃）回复于 2005-02-05 08:30:55 得分 1
ACM题哪里有这么简单的
这个比初中的NOI还简单Top
