申論題 - 阿摩線上測驗

申論題資訊

試卷：109年 - 109 身心特考_三等_資訊處理：資料結構#86485
科目：公職◆資料結構
年份：109年
排序：0

申論題內容

一、假設 A[1:n]是一個矩陣，存有n個不同的整數，且已依序從小到大排列。給定一個整數s，設計一個線性時間（linear time）的演算法，找出在A[1:n]中是否存在兩個相異之 A[i]和 A[ j ]，使得A[i]+A[ j ]=s。若存在，則印出任一組符合條件之i和 j ；若不存在，則印出 0。（須詳述或證明所設計程式之正確性及其計算複雜度，否則不計分）（25 分）