华东师范大学系统分析与集成专业考研
2004、2005年真题解析
04年的真题解析
第一部分    C语言程序设计（共70分）
一  回答下列问题：
分析： 这题主要考察指针，指针在C语言中的重要性不必再强调，可以说如果没有把指针理解透，那就几乎可以说不懂C语言，指针是C语言的精髓和核心。同时C语言的题目难题和大题都出在这一块。要答好这一块首先得对指针足够熟悉，同时在答题的时候一定要细心，具体复习方法见第六部分的专业课复习方法。
第一题的参考答案：
d[36]表示定义有36个元素的数组d；
*p：表示定义一个指针P
**p：表示定义一个指向指针的指针；
*r[6]：表示定义一个具有6个元素的指针数组
j，k 表示两个表示整形的变量
r[]数组表示d数组的每列，但p是从r[1]开始的
所以
（1）r[2][3] 表示 d[2][3]  （2）p[2]表示d[1][1]  （3）q[2][3]表示d[3][3]
（4）r+3表示d[3]的地址，而*（r+3）表示是d[3][0]的地址，把一个整形的数字赋给一地址显然不对
（5）同样的道理，也是数据类型不对。
总结：对于这类题目，一定要细心，其实仔细考虑下来并不难，但是切忌一上来慌里慌张的在还没有理解透的情况下就进行答题。
二 写出输出内容
分析：这两道题目是考察分析程序的能力，编程的人都知道，读别人程序是最痛苦的事情，特别是这种没有注释的程序，那我们应当怎样对待这种题目呢？首先肯定是需要通读一遍程序，在大体上弄懂这个程序是想做什么，然后在不看程序的情况下，自己思考一下这个程序应当怎么写，有了个大体思路就可以，不必详细写出来。然后再仔细阅读程序，分析与自己的思路相同点和不同点，特别注意不相同的地方，那些地方很有可能就是陷阱。最后再读一遍程序，把整个程序的执行流程做到心里有数，这时候结果就基本出来了。
这两道题的参考答案就没必要给了，把程序敲进电脑里运行下，什么结果都出来了。
三：写函数定义
分析：这两题是考基本工夫了，是虎是猫这个时候就能见分晓了。对于这种题目我们应当怎么解答呢？
首先需要冷静，别看着题目一大串心里就没底，其实题目给的越长对我们越有利，因为题
目给点越多，那么对问题就说的越清楚，我们进行“需求分析”的时候就更有把握，这样就更能写出合适的程序来。
其次：把输入和输出罗列出来，比如第一题就是把一个YMD格式的转换成YK型的，那么输入就是YMD格式的日期，输出就是YK型的日期，再比如第二题就是把两个大数加起来，输入就是两个数，输出就是和。
接着：我们把从输入到输出需要的条件写出来，这个是问题的关键。比如第一题就是考虑某一个日期在某一年中是第几个数字，把这个确定下来了问题就解决了，要确定是第几个日期那么就需要各种判定条件，如当年是否是闰年？是第几个月，某个月是30天还是31天，这些需要用到些日常生活中的常识。第二个题目关键是如何存储这两个大的数字，其实这个问题可以理解为在硬件条件下做一个加法器。也就是数字逻辑里面的内容。
总结：这两到题目并不难，但具体写的时候需要一定的时间，再三强调在考试的时候不能有烦躁的心态。
这两倒题目都有些不同的方法来实现，具体代码就由自己完成。
第二部分 数据结构
简答题考的是些比较基础的知识，只要所谓理解一下基本都没问题，这块是必须要拿分的。
1：（1）环行队列是队列中的一种形式，其关键就是把队列中的第一位和最后一位连接起来，要求R-H=-2表示这个队列中有两个数据。这有很多种画法，只要符合题意就可以了。
（2）空的链式队列，
^
head
2:假设P前面的接点是R，后面的接点是Q
语句：  r=p.prior;
      ;
      r.next=q;
      q.next=r;
      free(p);
3:公式
aij=a00+[i*(i-1)/2+(j+1)]*addr;
addr 表示每个元素占用的地址
4：
选择排序，每次选一个最小的。它最小的比较次数是N（N-1）/2
92  35  67  76  84  51
35  92  67  76  84  51
35  51  92  67  76  84
35  51  67  92  76  84
35  51  67  76  92  84
35  51  67  76  84  92
基数排序
首先按个位数上的数字进行排序
Head[0]
2021国企社会招聘正式工Tail[0]
Head[1]
51
Tail[1]
Head[2]
92
Tail[2]
Head[3]
Tail[3]
Head[4]
84
Tail[4]
Head[5]
35
初中教师资格证需要考什么Tail[5]
Head[6]
76
Tail[6]
Head[7]
67
Tail[7]
Head[8]
Tail[8]
Head[9]
Tail[9]
再按十位数上的数字进行排序
Head[0]
Tail[0]
Head[1]
公务员行政能力测试题库Tail[1]
Head[2]
Tail[2]
Head[3]
35
Tail[3]
Head[4]
Tail[4]
Head[5]
51
Tail[5]
Head[6]
67
Tail[6]
Head[7]
76
Tail[7]
Head[8]
84
Tail[8]
Head[9]
92
Tail[9]
收集后得到的链表是
P    35    51      67      76      84      92
5：这题比较简单，第一问只要把握二叉树与森林间的转换就可以，可以把森林的第三个孩子作为第二个孩子的右子接点，依次类推下去。
（2）后序遍历可以根据二叉树简单得出
（3）画穿线树参考课本P139。
6：这里关键的要求是递推。对于FLOYD公式是需要把它牢老记住，这题目考的比较死板，没什么灵活，对课本上介绍的算法比较熟悉的话很轻松拿分。
二、写函数
这两道题目需要足够重视。因为这两道题目占了36分之多。而且这种大题目每个人都完全实现它不太现实，所以这个应当根据自己的情况，如果不能完整的写出这个程序，那么把一些小的功能写成函数，然后在写一个函数去调用这些小函数，可能会有一两个小函数不对，但对的函数肯定能拿分，而且这样写也比较有条理性。
二 05年的真题解析
第一部分  C语言程序设计
一：填空题
分析：我参加的是05年的考试，当初我在复习C语言的时候，对文件那一章复习的比较马虎，因为以前的考试都没有涉及到文件方面的内容。但这题目一上来当时脑子就嗡了。其实现在看来题目很简单，但是你不熟悉的东西再简单也是答不出来的。所以我们在复习的时候一定要全面，不要迷信任何权威或者非权威的人士的预测，说某某方面的知识点肯定不会考，那万一真的考了谁来负责任？还不是你自己？当然复习是需要有所侧重，但是不能存在知识盲点。
具体答案就不用再说了。因为这么简单的题目看着书都搞不定，那我劝你放弃考研算了。免得耽搁了工作的时间。
二和三：阅读程序
分析：这种题目连续考到，可见ECNU的计算机老师对这种题目的青睐，也可见这类能力的重要性，那就是分析程序的能力。
具体结果也是一样，敲到电脑里把程序运行一遍知道结果了。
四：编写程序
分析：
第一题比较简单，按选择法进行升序的话就是每次要选一个最小的放在最前或者每次选一个最大放在最后。当然需要注意到必须是递归函数。
具体代码就不提供了。
第二部分  数据结构
1填空
（1）查不成功，那必须是查到了最后一个数据。所以平均查长度应当是N+1；
（2）由于是循环队列，所以元素个数为1
（3）做这个运算只要小心些就可以，应当是从里往外进行计算。最后结果为D
（4）如果以行存，则地址为i*8+j+1
    如果以列存，则地址为j*5+i+1
当两者相等时，则i=4 ,j=17  还有第一个元素的地址是相同的，所以一共有两个元素地址相同。
（5）接点最少的情况就是满二叉树，具体为1+2+4+8+16+32+50=113个。
最多的情况就是无穷多个。
（6）这题需要对推的概念以及堆怎么存储的了解清楚。
（7）5阶B数每个接点最多有4个孩子，所以高度最少7
1+4+16+64+256+1024+635=2000
5阶B数每个接点最少有2个孩子，所以高度最多为11
1+2+4+8+16+32+64+128+256+512+977=2000
（8）对于有向图，边数为矩阵的非零元素的个数，
    若是无向图，则为非零元素的个数的一半。
2 简答题
大专应届毕业生招聘（1）这题是考基本的概念，只要对书本比较熟悉拿分是没问题，所以还是强调要仔细看书。
（2）这题也比较简单
A
B
C
D
E
A
0
1
0
0
1
B
0
0
1
1
0
C
1
1
0
0
0
近十年考研时间D考研各学校报录比
0
0
0
0
0
E
0
1
0
0
0
（3）：这结论不一定对，比如函数为取9的模，对应的数列为27 36 20 38 45 47
散列之后为
27
20
36
38
45
47
0  1  2    3  4  5  6  7  8  新开辟地址
如图，同义词36 45没有在连续的区域中
（4）这里是考合并排序
（5）这里实质是考构造图的最短路径，比较简单。
3  算法设计题
这两题第一题相比比较简单，第一题关键是把每个“桶”的记录个数统计出来，完成了这个统计后就可以简单的把数据输出就可以了。算法有很多种实现方法，所以在分析时间复杂性和空间复杂性的时候各个程序也可能不相同。其优缺点只能临场发挥了，这里考的稍微
灵活了些，这就真正的考到了分析问题的能力，考察学生对新的问题如何进行分析。
第二题稍微比较复杂些，不仅仅要对什么是平衡查树了如手掌，而且需要用程序来判断，并且要求时间复杂性最小。这题目是道拉开分数的题目。