重要知识回顾.ppt

重要知识回顾进制转换二,十,八,十六进制之间的转换,以及它们的加减乘除 1.(2007)10=( )2=( )8=( )16 2.(123)10+(1010)2=( )16 ? 1. ********** 3727 7D7 ? 2. 85 栈的应用?判断出栈顺序,及出栈排列数?设栈 S的初始状态为空,元素 a, b, c, d, e 依次入栈,以下出栈序列不可能出现的有()。 A. a, b, c, e, d B. b, c, a, e, d C. a, e, c, b, d D. d, c, e, b, a ?C 二叉树?遍历:已知两种遍历,求余下的一种遍历?五种遍历之间的关系?计算:高度,、已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6 (数字为结点的编号,以下同),后根遍历是 3 2 5 6 4 1 ,则该二叉树的可能的中根遍历是( ) A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 1 3 5 4 6 D. 2 3 1 4 6 5 2、二叉树 T,已知其前序遍历序列为 1 2 4 3 5 7 6 ,中序遍历序列为 4 2 1 5 7 3 6 ,则其后序遍历序列为( )。 A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 1 ? 1. B 2. B 数学知识?排列:p(n,m) ?组合:c(n,m) ?加法原理和乘法原理?几个公式:海伦公式,一元二次方程的求根公式?递推和递归(包括数学方法和程序阅读) ?逻辑代数:﹁, ∧, ∨?集合(文氏图) ?最小公倍数和最大公约数 A = true , B = false , C = false , D = true ,以下逻辑运算表达式值为真的是( )。 A. (A ∧ B)∨(C ∧ D) B. ((A ∧ B)∨ C) ∧ D C. A ∧((B ∨ C) ∧ D) D. (A ∧(B∨ C)) ∨ D E. (A ∨ B)∧(C ∧ D) ,1个b和2个c构成的所有字符串中,包含子串“ abc ”的共有( )个。 A. 20 B. 8 C. 16 D. 12 E. 24 3. 设 A=B=D=true , C=false ,以下逻辑运算表达式值为真的有( )。 A. ( ? A∧ B)∨(C ∧ D) B. ? ((A ∨B∨ D) ∧ C) C.? A∧(B∨C∨ D) D. (A ∧B∧ C) ∨? D ? 1. D 2. E 字符串字符串 string 数据类型和字符 char 类型之间的关系。 var str : string; i : integer; begin str := 'Today-is-terrible!'; for i := 7 to 11 do if str[i] = '-' then str[i - 1] := 'x'; for i := 13 downto 1 do if str[i] = 't' then str[i + 1] := 'e'; writeln(str); end. 输出: ? Today-ix-terrible! 算法?特点:确定性,有效性,有穷性,输入( 0个或多个输入, 即一个算法可能没有输入),输出(必要的) ?评价算法的指标:正确性,可读性,健壮性,高效性(时间和空间,即快慢和需要计算机资源的多少) ?排序:插入排序,选择排序,冒泡排序,归并排序(二分法)的基本过程。?递推和递归,运用栈来分析递归程序。?枚举法:程序分析和问题求解中。?查找:普通查找和二分查找,了解查找过程和比较次数, 如同样是一个 1000 个元素,普通查找最多要比较多少次? 二分查找最多要比较多少次? ?数学方法?“创造”新算法 5 个数的序列排序,不论原先的顺序如何,最少都可以通过( )次比较,完成从小到大的排序。 B. 7 C. 8 D. 9 ,不是以“比较”作为主要操作的算法是( )。 B. 冒泡排序 C. 插入排序 D. 基数排序 ,不正确的是( )。 A. 一个正确的算法至少要有一个输入 B. 算法的改进,在很大程度上推动了计算机科学与技术的进步 C. 判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性