2014年北邮计算机上机题目二

Problem A. 中位数

题目描述

给定一个长度为N的非降数列，求数列的中位数。

中位数：当有序数列的项数N为奇数时，处于中间位置的变量即为中位数；当N为偶数时，中位数则为处于中间位置的两个数的平均数。

输入格式

输入数据第一行是一个整数T（1<=T<=100），表示测试数据的组数。

对于每组测试数据：

第一行是一个正整数N（1<=N<=100），表示数列长度。

第二行有N个整数，整数之间用空格隔开，所有的整数都不超过100000，表示这个数列的元素。

输出格式

对于每组测试数据，输出数列的中位数，请不要输出小数点末尾多余的0。

输入样例

2

4

1 1 2 2

5

1 1 2 2 3

输出样例

1.5

2

　　说一点：%g用来输出实数，它根据数值的大小，自动选f格式或e格式（选择输出时占宽度较小的一种），且不输出无意义的0。即%g是根据结果自动选择科学记数法还是一般的小数记数法。

　　这题的精度用%g可以混过去的，不行的话其实自己写个函数处理下也是简单的。比如用sprintf(s,”%lf”,f)把实数变成字符串，再把后面没用的0去掉就行了。

#include<stdio.h>

int main() {
    int T,a[];
    scanf("%d",&T);
    while(T--) {
        int N;
        scanf("%d",&N);
        for(int i = ;i < N;i++) {
            scanf("%d",&a[i]);
        }
        if(N % ) {
            printf("%d\n",a[N / ]); 
        } else {
            printf("%g\n",(a[N / ] + a[N /  - ]) / );
        }
    }
}
           

Problem B. 内存分配

题目描述

在操作系统中，内存分配是非常重要的工作。

已知内存空间由N个内存块组成，这些内存块从1到N编号，进行内存分配时，操作系统将选择一块大小足够的内存全部分配给请求内存的进程。例如，当进程请求10MB的内存时，操作系统必须向该进程分配一个不小于10MB的内存块。内存块不能被重复分配。

操作系统有三种基本的分配方式，分别为：

首次适应：从1号到N号内存块依次查找，直到找到第一块足够大的且未分配出去的内存块，将其分配给进程。

最佳适应：找到当前未分配出去且大小足够的内存块中最小的内存块分配给进程。

最差适应：找到当前未分配出去且大小足够的内存块中最大的内存块分配给进程。

其中，最佳适应是应用最为广泛的分配方式。现在，操作系统要依次处理M个进程的内存请求，请按照最佳适应方式分配内存，并输出相应分配到的内存块的大小。如果没有大小足够的内存块可以满足当前请求，则输出“NULL”（不包含引号），并跳出该请求。

输入格式

输入数据的第一行是测试数据组数T（T<=50）

每组数据由4行构成：

第一行为一个整数N（1<=N<=100），表示有N个内存块。

第二行有N个整数，第i个整数表示第i块内存块的大小。

第三行为一个整数M（1<=M<=100），表示有M个请求。

第四行有M个整数，表示进程所请求的内存空间。

输出格式

每组数据输出一行，每行有M个数，表示操作系统采用最佳适应方式，依次分配给进程的内存块大小；如果没有可用的内存块，输出“NULL”（不包含引号）

请不要输出多余的行尾空格，否则会被判为格式错误。

输入样例

2

4

7 5 10 3

2

4 6

4

3 5 9 10

3

5 12 6

输出样例

5 7

5 NULL 9

　　水题。

#include<stdio.h>

int main() {
    int T,a[],b[];
    scanf("%d",&T);
    while(T--) {
        int N,M;
        scanf("%d",&N);
        for(int i = ;i < N;i++) {
            scanf("%d",&a[i]);
            b[i] = ;
        }
        scanf("%d",&M);
        int temp,dx,index,flag = ;
        while(M--) {
            dx = ;
            scanf("%d",&temp);
            for(int i = ;i < N;i++) {
                if(b[i] && a[i] >= temp && a[i] - temp < dx) {
                    dx = a[i] - temp; 
                    index = i;
                } 
            }
            if(dx != ) {
                b[index] = ;
                if(flag) {
                    printf(" %d",a[index]);
                } else {
                    flag = ;
                    printf("%d",a[index]);
                }
            } else {
                if(flag) {
                    printf(" NULL");
                } else {
                    flag = ;
                    printf("NULL");
                }
            }           
        }
        printf("\n");
    }
}
           

Problem C. 图像识别

题目描述

在图像识别中，我们经常需要分析特定图像中的一些特征，而其中很重要的一点就是识别出图像的多个区域。在这个问题中，我们将给定一幅N x M的图像，其中每个1 x 1的点都用一个[0,255]的值来表示他的RGB颜色。如果两个相邻的像素点颜色差不超过D，我们就认为这两个像素点属于同一个区域。对于一个像素点(x,y) ，以下这8个点（如果存在）是与它相邻的：（x-1, y-1），（x-1,y），（x-1,y+1），（x,y-1），（x,y+1），（x+1,y-1），（x+1,y），（x+1,y+1）。

你的任务是写一个程序，分辨出给定图像中一共被分为多少个区域。

输入格式

输入数据包含多组测试数据。

输入的第一行是一个整数T（T<=100），表示测试数据的组数。

每组测试数据的第一行是三个整数N,M,D（1<=N,M<=100, 0<=D<=255），意义如上所述。

接下来N行，每行M个整数，表示给定图像的每个像素点颜色。

输出格式

对于每组测试数据输出一行，即图像中的区域数量。

输入样例

2

3 3 0

1 1 1

0 1 0

0 1 0

3 4 1

10 11 12 13

9 8 7 6

2 3 4 5

输出样例

3

1

　　很经典的问题，Flood Fill。

#include<stdio.h>
#include<stdlib.h>

int map[][];

void dfs(int i,int j,int m,int n,int d) {
    if(i >=  && i < m && j >=  && j < n && map[i][j] != ) {
        int temp = map[i][j];
        map[i][j] = ; 
        if(abs(map[i + ][j] - temp) <= d) {
            dfs(i + ,j,m,n,d);
        }
        if(abs(map[i - ][j] - temp) <= d) {
            dfs(i - ,j,m,n,d);
        }
        if(abs(map[i][j + ] - temp) <= d) {
            dfs(i,j + ,m,n,d);
        }
        if(abs(map[i][j - ] - temp) <= d) {
            dfs(i,j - ,m,n,d);
        }
        if(abs(map[i + ][j + ] - temp) <= d) {
            dfs(i + ,j + ,m,n,d);
        }
        if(abs(map[i - ][j - ] - temp) <= d) {
            dfs(i - ,j - ,m,n,d);
        }
        if(abs(map[i + ][j - ] - temp) <= d) {
            dfs(i + ,j - ,m,n,d);
        }
        if(abs(map[i - ][j + ] - temp) <= d) {
            dfs(i - ,j + ,m,n,d);
        }
    }
}


int main() {
    int T,N,M,D;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d%d",&N,&M,&D);
        for(int i = ;i < N;i++) {
            for(int j = ;j < M;j++) {
                scanf("%d",&map[i][j]);
            }
        }
        int num = ;
        for(int i = ;i < N;i++) {
            for(int j = ;j < M;j++) {
                if(map[i][j] != ) {
                    dfs(i,j,N,M,D);
                    num++;
                }
            }
        }
        printf("%d\n",num);     
    }
}
           

Problem D. 汇编

题目描述

汇编语言描述了机器最终所要执行的指令序列，其中，以8086CPU为中央处理器的汇编就是最经典的版本之一。这个题目需要你的程序处理一些简单的汇编指令，并返回执行之后各寄存器的结果。

在该CPU中，所有寄存器都是16位，可以存放两个字节（即0到65535之间）。为简单起见，我们只是用其中AX，BX，CX，DX四个通用寄存器。其中，每个寄存器又可分为两个独立使用的8位寄存器：

AX可分为AH和AL

BX可分为BH和BL

CX可分为CH和CL

DX可分为DH和DL

在存储数据时，低8位构成了L型寄存器（AL，BL，CL，DL），高8位构成了H型寄存器（AH，BH，CH，DH）。例如，当AX=（20000）10 =（0100 1110 0010 0000）2时，我们有

AX AH AL

0100 1110 0010 0000B 0100 1110B 0010 0000B

在汇编中，数值通常表示为2进制（以B结尾），16进制（以H结尾）或者10进制（没有后缀字符）。如上例出现的20000（10进制）可以表示为0100111000100000B，也可表示为04E20H。为了避免指令的歧义，16进制下的首位一定是0。

本题中所涉及的操作指令有以下两类：

MOV：数据转移

ADD：加法

指令的用法如下：

汇编指令 控制CPU完成的操作 用高级语言的语法描述

MOV AX，18 将18送入寄存器AX AX=18

MOV AH，11B 将11B送入寄存器AH AH=11B

MOV AX，BX 将寄存器BX中的数据送入AX AX=BX

ADD AX，08H 将寄存器AX中的数值加上08H AX=AX+08H

ADD AX，BX 将AX和BX中的数值相加， AX=AX+BX

结果存在AX中

注意在MOV和ADD操作中，指令的两个操作对象的位数应当是一致的，即不会出现如MOV AX，BL或ADD AL，100H这样错误的指令。

在初始状态下，四个通用寄存器中的数值均为0.给定一系列的汇编指令，请输出执行完所有指令后四个通用寄存器中的数值。

输入格式

输入的第一行是一个整数T（T<=50），表示输入的数据组数。

每组测试数据的第一行是一个整数N（1<=N<=100），表示指令的数量。

接下来N行，每行包括一个指令。指令中只会存在一个空格，出现在指令名和操作对象中间。数据保证不会出现错误的语句，每条语句结束之后该寄存器内的数值都不会超过它本身所能存储的最大值。

输出格式

对于每组测试数据，输出一行表示AX，BX，CX，DX最终的值（用十进制表示），数值中间用一个空格隔开。注意行末不要输出多余的空格。

样例输入

2

3

MOV AX，2

MOV BX，3

ADD AX，BX

5

MOV AX，2

MOV BX，030H

MOV CX，11B

ADD AX，CX

ADD DL，CL

样例输出

5 3 0 0

5 48 3 3

暂时没时间做了，以后做吧，毕竟渣渣又不是要AK，还有四门专业课等着我去背。。。