笔试题练习（八）

xiaoxiao2026-08-28 33

1，不使用中间变量实现strlen

int strlen_p( const char * p){ if ( * p == ' /0 ' ) return 0 ; else return strlen_p( ++ p) + 1 ;}

2，统计32位整数二进制表示1的个数

bool isPowOf2( int n){ // 是否是2的幂 return (n & (n - 1 )) ? false : true ;} int countOnes( int n){ // 统计二进制表示中1的个数 int count = 0 ; while (n != 0 ){n = n & (n - 1 ); ++ count;} return count;} int countZeros( int n){ // 统计二进制表示中0的个数 n = ~ n; return countOnes(n);}

3，题目：有一个数组t[100]，存放了1～99之间的数字，用效率较高的代码把重复数字去掉。例如数组{1,2,2,2,3,5,6,6}变成{1,2,3,5,6}。

bool flag[ 100 ] = { false }; // flag[1]flag[99],flag[0]不用 int removeRedundant( int t[], int size){ int i,end = 0 ; for (i = 0 ;i < size; ++ i){ if (flag[t[i]] == false ){flag[t[i]] = true ;}} for (i = 1 ;i < size; ++ i){ if (flag[i] == true ){t[end ++ ] = i;}} return end;}

4，写一个程序, 要求功能：求出用1，2，5这三个数不同个数组合的和为100的组合个数。如：100个1是一个组合，5个1加19个5是一个组合。

因为x+2y+5z=100

所以x+2y=100-5z，且z<=20 x<=100 y<=50

所以(x+2y)<=100，且(x+5z)是偶数

对z作循环，求x的可能值如下（x的取值种数就代表了最终解的个数，对于某个z，x定了后y自动确定）：

z=0, x=100, 98, 96, ... 0

z=1, x=95, 93, ..., 1

z=2, x=90, 88, ..., 0

z=3, x=85, 83, ...,

z=4, x=80, 78, ..., 0

......

z=19, x=5, 3, 1

z=20, x=0

因此，组合总数为100以内的偶数+95以内的奇数+90以内的偶数+...+5以内的奇数+1，即为：

(51+48)+(46+43)+(41+38)+(36+33)+(31+28)+(26+23)+(21+18)+(16+13)+(11+8)+(6+3)+1

某个偶数m以内的偶数个数（包括0）可以表示为m/2+1=(m+2)/2

某个奇数m以内的奇数个数也可以表示为(m+2)/2

所以，求总的组合次数可以编程为：

intnumber = 0 ; for ( int m = 0 ;m <= 100 ;m += 5 ){number += (m + 2 ) / 2 ;}cout << number << endl;

这个程序，只需要循环21次, 两个变量，就可以得到答案，比最常见的那个穷举法要高效的多

5，通过一次遍历找到单链表中倒数第n个节点，链表可能相当大，可使用辅助空间，但是辅助空间的数目必须固定，不能和n有关。

struct Node{ int value; struct Node * next;};Node * findLastNth(Node * head, int n){ // 找到倒数第n个节点 assert(head != NULL && n > 0 );Node * p1, * p2;p1 = head;p2 = head; int i = 1 ; while (i < n && p2 -> next != NULL){ // 间隔n-1 p2 = p2 -> next; ++ i;} if (i < n){ // 没有倒数第n个 return NULL;} else if (p2 -> next == NULL){ // 恰好链表头就是 return p1;} while (p2 -> next != NULL){p1 = p1 -> next;p2 = p2 -> next;} return p1;}

6，有1,2,....一直到n的无序数组，求排序算法，并且要求时间复杂度为O(n)，空间复杂度O(1)，使用交换，而且一次只能交换两个数.

void sortOnorder( int array[], int len){ int temp; for ( int i = 0 ;i < len;){ if (array[i] != i + 1 ) // 下标和值不满足对应关系 {temp = array[array[i] - 1 ]; // 不相等的话就把array[i]交换到与索引相应的位置 array[array[i] - 1 ] = array[i];array[i] = temp;} else i ++ ; // 保存，以后此值不会再动了 }}

相关资源：全国计算机等级考试笔试题练习

转载请注明原文地址: https://www.6miu.com/read-5052013.html

Java

最新回复(0)