"2012计算机考研真题及答案1，阶乘算法时间复杂度和中缀转后缀表达式算法"

2012计算机考研真题及答案 1. 求整数 n(n≥0)阶乘的算法如下，其时间复杂度是O(n)。此算法使用了递归的方式，当n小于等于1时，返回1，否则返回n乘以n-1的阶乘。 2. 已知操作符包括‘ ’、‘-’、‘*’、‘/’、‘(’和‘)’。将中缀表达式a b-a*((c d)/e-f) g转换为等价的后缀表达式ab acd e/f-*-g时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数。 平衡二叉树的高度为6，根据平衡二叉树的性质，可以推断出最少有5层节点。在最坏情况下，平衡二叉树的高度和节点数的关系为2^h-1=n，其中h为高度，n为节点数。根据这个关系，可以推算出最少有31个节点。 慕课考研是一家提供考研辅导服务的机构，针对不同专业的考研科目提供系统的教学课程和资料。他们提供了2012年全国硕士研究生入学统一考试的计算机科学与技术学科联考的计算机学科专业基础综合试题。 在该综合试题中，有40个单项选择题，每题2分，总共80分。其中第一题是关于计算整数的阶乘算法的时间复杂度，根据给出的代码可知，其时间复杂度为O(n)，即线性复杂度，与输入规模n成正比。这是因为算法使用了递归的方式，每次都将n减1，并乘以原来的结果，直到n小于等于1。所以总共需要执行n次乘法运算。因此，该算法的时间复杂度为O(n)。 第二题是关于中缀表达式转后缀表达式的问题。中缀表达式是常见的数学表示方法，而后缀表达式则是一种更加方便计算机处理的表达式格式。转换过程中，需要用栈来存放暂时还不能确定运算次序的操作符。从左到右扫描中缀表达式，当遇到数字时，直接输出；当遇到操作符时，与栈顶的操作符进行比较，如果优先级更低或相等，则将栈顶操作符弹出并输出，再将当前操作符入栈；如果优先级更高，则将当前操作符直接入栈。最后，将栈中剩余的操作符全部弹出并输出。该题的要求是要求同时保存在栈中的操作符的最大个数，根据转换过程可知，最大个数为2，即在乘法和除法的优先级相等时，同时保存在栈中。 综合总结，2012年计算机考研真题及答案包括两道题，分别涉及计算整数的阶乘的算法时间复杂度和中缀表达式转后缀表达式的问题。通过分析两道题，我们可以学到计算复杂度和栈的使用技巧。