【笔试题精选】_5

在一个二维数组中，每一行都按照从左到右的顺序排序，每一列都按照从上到下的顺序排序。请实现一个函数用于判断数组中是否包含指定的数。函数原型： bool find_in_matrix(int matrix[N][M], int value);说明： 查找成功时返回true, 返回失败时返回false.template<typename T, int N, int M>bool find_in_matrix(T matrix[N][M], T value) // O(N + M){ if( (matrix[0][0] <= value) && (value <= matrix[N-1][M-1]) ) { int r = 0; int c = M - 1; while( (r < N) && (c >= 0) ) { if( value == matrix[r][c] ) { return true; } else if( value < matrix[r][c] ) { c–; } else { r++; } } } return false;}写一个函数，打印二叉树中某层的所有节点二叉树节点定义:struct Node{ int v; Node* left; Node* right;};函数原型： void print_node_at_level(Node* node, int level);说明： 将 level 层的节点所保存的值打印在同一行void print_node_at_level(Node* node, int level){ if( node != NULL ) { if( level == 0 ) { cout<<node->v<<" “; } else { print_node_at_level(node->left, level-1); print_node_at_level(node->right, level-1); } }}void print_node_at_level_ex(Node* node, int level){ if( node != NULL ) { list<Node*> nl; list<int> ll; nl.push_back(node); ll.push_back(0); while( nl.size() > 0 ) { Node* n = nl.front(); int cl = ll.front(); nl.pop_front(); ll.pop_front(); if( cl == level ) { cout<<n->v<<” “; } else if( cl < level ) { if( n->left != NULL ) { nl.push_back(n->left); ll.push_back(cl+1); } if( n->right != NULL ) { nl.push_back(n->right); ll.push_back(cl+1); } } } }}编写一个函数用于删除二叉树中的度数为 1 的所有节点要求：节点删除后其唯一的子节点代替它的位置struct Node{ int v; Node* left; Node* right;};void print_div(int p){ for(int i=0; i<p; i++) { cout<<”-"; }}void print_tree(Node* node, int p){ if( node != NULL ) { print_div(p); cout<<node->v<<endl; if( (node->left != NULL) || (node->right != NULL) ) { print_tree(node->left, p+1); print_tree(node->right, p+1); } } else { print_div(p); cout<<endl; }}void print_tree(Node* node){ print_tree(node, 0);}void delete_one_degree_node(Node*& node){ if( node != NULL ) { if( (node->left != NULL) && (node->right != NULL) ) { delete_one_degree_node(node->left); delete_one_degree_node(node->right); } else if( (node->left != NULL) && (node->right == NULL) ) { node = node->left; delete_one_degree_node(node); } else if( (node->left == NULL) && (node->right != NULL) ) { node = node->right; delete_one_degree_node(node); } }}输入一个数组，数组里面可能有正数也有负数。数组中一个或连续的多个元素组成一个子数组。求所有子数组的和的最大值。要求：时间复杂度为 O(n)template<typename T>bool max_sub_array_sum(T array[], int len, T& max_sum){ int ret = (len > 0) && (array != NULL); if( ret ) { T sum = array[0]; T cur = array[0]; for(int i=1; i<len; i++) { cur = cur + array[i]; if( cur < array[i] ) { cur = array[i]; } if( cur > sum ) { sum = cur; } } max_sum = sum; } return ret;}在一个整型数组中只可能有 0，1，2 三种数字重复出现，编写一个函数对这样的数组进行排序。void swap(int& a, int& b){ int c = a; a = b; b = c;}void three_element_sort(int array[], int len){ int* ts = new int[len]; int p = 0; if( ts != NULL ) { for(int i=0; i<3; i++) { for(int j=0; j<len; j++) { if( array[j] == i ) { ts[p++] = i; } } } for(int i=0; i<len; i++) { array[i] = ts[i]; } delete[]ts; }}void three_element_sort_ex(int array[], int len){ int p0 = 0; int p2 = len - 1; while( array[p0] == 0 ) p0++; while( array[p2] == 2 ) p2–; for(int i=p0; i<=p2;) { if( array[i] == 0 ) { swap(array[i], array[p0++]); while( array[p0] == 0 ) p0++; if( i < p0 ) i = p0; } else if( array[i] == 2 ) { swap(array[i], array[p2–]); while( array[p2] == 2 ) p2–; } else { i++; } }}求 1 + 2 + 3 + … + n 的和要求：不能使用 if, while, for, switch, ?: 等条件语句，不能使用 ==, ！=, <=, >, <= 等比较运算符，也不能调用外部库函数。只能使用加减法操作操作符，不能使用乘除法操作符class Sum{private: static int N; static int S; Sum();public: static int Calculate(int n);};int Sum::N = 0;int Sum::S = 0;Sum::Sum(){ S = S + N; N = N - 1;}int Sum::Calculate(int n){ int ret = 0; Sum* p = NULL; N = n; S = 0; p = new Sum[N]; ret = S; delete[]p; return ret;}int main(){ cout<<Sum::Calculate(10)<<endl; cout<<Sum::Calculate(100)<<endl; return 0;}typedef int(Func)(int);int end_func(int n);int recusive_func(int n);Func* Array[] = { end_func, // 0 recusive_func // 1};int end_func(int n){ return n;}int recusive_func(int n){ return n + Array!!(n-1);}int sum(int n){ return recusive_func(n);}int main(){ cout<<sum(10)<<endl; cout<<sum(100)<<endl; return 0;}template<int N>class Sum{public: static const int Value = N + Sum<N-1>::Value;};template<>class Sum<0>{public: static const int Value = 0;};int main(){ cout<<Sum<10>::Value<<endl; cout<<Sum<100>::Value<<endl; return 0;}