110 關務特考四等 資訊處理 程式設計概要 考古題詳解
第 一 題25 分
今有一雜湊函式 ，且該函式以線性探測（Linear Probing）處理碰撞。若依序輸入下列資料：，請問該筆資料中最大搜尋次數為何？
登入後即可作答並保存紀錄。
核心觀念
本題考查雜湊表的線性探測法。雜湊函式為 ，因此雜湊表有 個位置，編號為 至 。
資料發生碰撞時，從雜湊位置起依序往下一格探測；到位置 後，循環回位置 。搜尋某筆資料時，探測次數從該資料的雜湊位置開始計算，包含找到資料的那一次。
解題方法
依輸入順序計算各資料的雜湊位置；若該位置已被占用，就依線性探測規則找下一個空位。
| 資料 | 雜湊位置 | 實際存放位置 | 插入時探測次數 |
|---|---|---|---|
第 二 題25 分
請問下列程式碼之輸出結果為何？
#include <stdio.h> #include <stdlib.h>
int function(int num);
int main(){ int var1=1; int sum=0;
for(var1=1;var1<=9;var1++){
sum+=function(var1);
if(var1==3)
printf("output1:%d\n",function(var1));
}
printf("output2:%d",sum);
return 0;
}
int function(int input){ if(input==9) return 1;
return 2*function(input+1);
}
登入後即可作答並保存紀錄。
核心觀念
本題考查 遞迴函式的呼叫與回傳值，以及 for 迴圈中函式呼叫和累加的執行順序。
function(input) 在 input == 9 時回傳 1；其餘情況回傳 2 * function(input + 1)。每往回一層遞迴，回傳值就乘以 。
解題方法
從終止條件往回推：
因此，當 var1 依序為 到 時，function(var1) 的回傳值依序為：
第 三 題25 分
請參考下列程式碼，若輸入字串 helloworld，輸出之結果為何？
#include<stdio.h>
#define MAX 100
char* My_Function(char str1[]){ static int i=0; static char Array1[MAX];
if(*str1){
My_Function(str1+1);
Array1[i++] = *str1;
}
return Array1;
}
int main(){ char array2[MAX],*p1;
printf("Input any string:");
scanf("%s",array2);
p1 = My_Function(array2);
printf("The output is:%s\n\n",p1);
return 0;
}
登入後即可作答並保存紀錄。
核心觀念
本題考查遞迴呼叫的執行順序，以及區域靜態變數（static）的生命週期與保留狀態。
My_Function 每次呼叫都檢查目前字元是否為字串結尾。只要尚未到結尾，就先遞迴處理下一個字元；等遞迴呼叫返回後，才把目前字元存入 Array1。因此，字元是從字串尾端往前寫入，輸出順序會與輸入相反。
Array1 是靜態字元陣列，會自動以 '\0' 初始化；函式沒有改寫這個結尾字元，因此可以作為 C 字串輸出。
解題方法
輸入字串為 helloworld，其字元索引如下：
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 字元 | h | e | l | l | o | w | o | r | l | d |
呼叫時，str1 會依序指向每個字元，直到 '\0'。此時最深層呼叫直接返回；返回過程中，各層才依序執行 Array1[i++] = *str1：
第 四 題25 分
請仔細觀察下列程式碼，請問 function 之功能為何？
#include <stdio.h> #include <stdlib.h>
void function(int* p, int input1, int input2){ int* p1; int* p2 = p;
for(p1 = p + input1 - 1;p1 > p - 1;p1--){
*(p1 + input2) = *p1;
}
for(p1 = p + input1;p2 < p + input2;p1++){
*p2++ = *p1;
}
}
int main(){ int array[5] = {103,45,99,38,76}; int* p1 = array; int var1 = 0; int var2 = 5; int var3 = 2;
for(p1 = array;p1 < array + var2;){
printf("%d,",*p1++);
}
function(array,var2,var3);
printf("\n");
for(p1 = array;p1 < array + var2;){
printf("%d,",*p1++);
}
return 0;
}
登入後即可作答並保存紀錄。
核心觀念
本題考查 C 語言的指標運算、陣列元素搬移，以及迴圈執行順序。function(p, input1, input2) 將陣列前 input1 個元素向右移 input2 格，再把前 input2 個位置改成原本最後 input2 個元素，因此效果是將前 input1 個元素循環左移 input2 格。
解題方法
本題呼叫時：
p指向array[0]input1 = 5input2 = 2
原始陣列為：
| 索引 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 元素 | 103 | 45 | 99 | 38 | 76 |
第一個迴圈由後往前搬移：
for(p1 = p + input1 - 1; p1 > p - 1; p1--){
*(p1 + input2) = *p1;
}
p1 依序指向 array[4] 到 array[0]，每次將元素寫到往右 2 格的位置：
| 搬移 | 結果 |
|---|---|
array[4] → array[6] | 76 |
array[3] → array[5] | 38 |
array[2] → array[4] | 99 |
array[1] → array[3] | 45 |
array[0] → array[2] | 103 |
由後往前搬，才能避免尚未搬移的原始元素被覆寫。搬移後陣列前幾格為：