北京航空航天大學計算機復試上機真題
2023北京航空航天大學計算機復試上機真題
在線評測：https://app2098.acapp.acwing.com.cn/
階乘和
題目描述
求Sn=1!+2!+3!+4!+5!+…+n!之值，其中n是一個數字。
輸入格式
輸入一個n（n<=20）
輸出格式
輸出Sn，Sn可能超出int范圍
輸入樣例
5
輸出樣例
153
最簡真分數
題目描述
給出n個正整數，任取兩個數分別作為分子和分母組成最簡真分數，編程求共有幾個這樣的組合。
輸入格式
多組測試數據，每組包含n（n<=600）和n個數，整數大于1且小于等于1000。
輸出格式
每行輸出最簡真分數組合的個數。
輸入樣例
7
3 5 7 9 11 13 15
輸出樣例
17
八皇后
題目描述
會下國際象棋的人都很清楚：皇后可以在橫、豎、斜線上不限步數地吃掉其他棋子。如何將8個皇后放在棋盤上（有8 * 8個方格），使它們誰也不能被吃掉！這就是著名的八皇后問題。 對于某個滿足要求的8皇后的擺放方法，定義一個皇后串a與之對應，即a=b1b2…b8，其中bi為相應擺法中第i行皇后所處的列數。已經知道8皇后問題一共有92組解（即92個不同的皇后串）。 給出一個數b，要求輸出第b個串。串的比較是這樣的：皇后串x置于皇后串y之前，當且僅當將x視為整數時比y小。
輸入格式
每組測試數據占1行，包括一個正整數b(1 <= b <= 92)
輸出格式
輸出有n行，每行輸出對應一個輸入。輸出應是一個正整數，是對應于b的皇后串。
輸入樣例
1
輸出樣例
15863724
素數
題目描述
輸入一個整數n(2<=n<=10000)，要求輸出所有從1到這個整數之間(不包括1和這個整數)個位為1的素數，如果沒有則輸出-1。
輸入格式
輸入包含多組測試數據。
每組數據占一行，包含一個整數 n。
輸出格式
每組數據輸出占一行，由小到大輸出所有滿足條件的素數，素數之間單個空格隔開。如果沒有則輸出 ?1?1。
輸入樣例
100
輸出樣例
11 31 41 61 71
旋轉矩陣
題目描述
任意輸入兩個9階以下矩陣，要求判斷第二個是否是第一個的旋轉矩陣，如果是，輸出旋轉角度（0、90、180、270），如果不是，輸出-1。
輸入格式
第一行包含整數 n，表示矩陣階數。
接下來 n 行，每行包含 n 個空格隔開的整數，表示第一個矩陣。
再接下來 n 行，每行包含 n 個空格隔開的整數，表示第二個矩陣。
輸出格式
判斷第二個是否是第一個的旋轉矩陣，如果是，輸出旋轉角度（0、90、180、270），如果不是，輸出-1。
如果旋轉角度的結果有多個，則輸出最小的那個。
輸入樣例
3
1 2 3
4 5 6
7 8 9
7 4 1
8 5 2
9 6 3輸出樣例
90字符串匹配
題目描述
給定一個包含 n 個字符串的字符串數組 s1,s2,…,sn 和一個短字符串 p，找出字符串數組中所有能夠和短字符串匹配的字符串。
匹配時不區分大小寫，短字符串中可能包含若干個用中括號表示的模式匹配。
例如，對于 aa[123]bb，字符串 aa1bb、aa2bb、aa3bb 均可與其匹配（每次匹配只能與中括號中的任意單個字符進行匹配）。
輸入格式
第一行包含整數 n，表示字符串數組中的字符串個數。
接下來 n 行，第 i 行包含一個字符串表示 si。
最后一行，包含一個字符串表示 p。
輸出格式
輸出可以匹配的字符串的下標和該字符串。
數據范圍
1≤n≤1000,
si 的長度不超過 10,
p 的長度不超過 50,
所有字符串中只包含大小寫字母、數字、[]。
輸入樣例
4
Aab
a2B
ab
ABB
a[a2b]b輸出樣例
1 Aab
2 a2B
4 ABB迭代求立方根
題目描述
立方根的逼近迭代方程是 y(n+1) = y(n)2/3 + x/(3y(n)*y(n)),其中y0=x.求給定的x經過n次迭代后立方根的值。
輸入格式
輸入有多組數據。
每組一行，輸入x n。
輸出格式
迭代n次后的立方根，double精度,保留小數點后面六位。
輸入樣例
4654684 1
65461 23輸出樣例
3103122.666667
40.302088等差序列
題目描述
給定閉區間[a,b] ,要求輸出 連續的素數的等差序列,三個以上才算是序列，例如 [100,200] 會輸出 151 157 163
再例如輸入[1,100] 會有兩個等差序列，3 5 7 和47 53 59。輸出樣式行末的空格保留。
輸入格式
輸入兩個正整數a和b，其中a和b小于等于10000。
輸出格式
參考輸出樣例
輸入樣例
141 400輸出樣例
151 157 163
167 173 179
199 211 223
251 257 263 269
367 373 379year
2019
三叉樹
題目描述
一個關于三叉樹的題目，小于100的值代表樹葉，大于100的值為分支點，建樹的過程是水平方向建樹，
輸入格式：
先輸入n，代表有n組數據，接下來n行，輸入4個數，第一個數代表根節點，接下來分別代表三個子節點，-1代表子節點不存在，輸入的順序按照層次遍歷的次序。接下來，要求尋找葉子節點的最短路徑，最短路徑是指不經過重復的邊。輸入方式，首先輸入一個值m，代表m行，接下來m行輸入m個葉子節點和對應的優先級，要求按優先級輸出從上次到達的位置到該節點的最短路徑，每條路徑的最后一個節點要求輸出目標葉子節點，最后要求回到根節點。
輸入格式
見題目描述
輸出格式
見輸出樣例
輸入樣例
10
100 101 108 107
101 1 102 2
108 103 104 105
107 17 109 18
102 3 4 5
103 7 8 9
104 10 106 11
105 15 16 -1
109 19 20 21
106 12 13 14
5
8 1
14 3
16 2
5 0
19 4輸出樣例
100 101 102 5
102 101 100 108 103 8
103 108 105 16
105 108 104 106 14
106 104 108 100 107 109 19
109 107 100year
2019
連續合數段
題目描述
給定區間 [a,b]，輸出這個區間里最長的連續合數段。
輸入格式
一行，兩個整數 a,bb。
輸出格式
一行，輸出最長的連續合數段。
如果答案不唯一，則輸出首項最小的那一段。
數據范圍
1≤a≤b≤10000
輸入樣例
1 10輸出樣例
8 9 10year
2019
空閑塊
題目描述
在操作系統中，空閑存儲空間通常以空閑塊鏈表方式組織，每個塊包含塊起始位置、塊長度及一個指向下一塊的指針。空閑塊按照存儲位置升序組織，最后一塊指向第一塊（構成循環鏈表）。當有空間申請請求時，按照如下原則在空閑塊循環鏈表中尋找并分配空閑塊：
1）從當前位置開始遍歷空閑塊鏈表（初始是從地址最小的第一個空閑塊開始），尋找滿足條件的最小塊（即：大于等于請求空間的最小空閑塊，如果有多個大小相同的最小空閑塊，則選擇遍歷遇到的第一個空閑塊）（最佳適應原則）；
2）如果選擇的空閑塊恰好與請求的大小相符合，則將它從鏈表中移除并返回給用戶；這時當前位置變為移除的空閑塊指向的下一空閑塊；
3）如果選擇的空閑塊大于所申請的空間大小，則將大小合適的空閑塊返回給用戶，剩下的部分留在空閑塊鏈表中；這時當前位置仍然為該空閑塊；
4）如果找不到足夠大的空閑塊，則申請失敗；這時當前位置不變。
例如：下圖示例給出了空閑塊鏈表的初始狀態，每個結點表示一個空閑塊，結點中上面的數字指空閑塊的起始位置，下面的數字指空閑塊的長度，位置和長度都用正整數表示，大小不超過int表示范圍。當前位置為最小地址為1024的空閑塊。
若有4個申請空間請求，申請的空間大小依次為：1024、2560、10240和512。則從當前位置開始遍歷上圖的鏈表，按照上述原則尋找到滿足條件的最小塊為地址是16384的空閑塊，其長度正好為1024，所以將其從鏈表中刪除，這時鏈表狀態如下圖所示，當前位置變成地址為32768的空閑塊。
從當前位置開始為第二個空間請求（大小為2560）遍歷鏈表，按照上述原則尋找到滿足條件的最小塊為地址是80896的空閑塊，其長度為3072，大于請求的空間大小，于是申請空間后該空閑塊剩余的長度為512，當前位置為地址是80896的空閑塊，鏈表狀態如下圖所示：
從當前位置開始為第三個空間請求（大小為10240）遍歷鏈表，遍歷一圈后發現找不到足夠大的空閑塊，則忽略該請求，當前位置不變。下面繼續為第四個空間請求（大小為512）遍歷鏈表，按照上述原則尋找到滿足條件的最小塊為當前位置的空閑塊，其長度等于請求的空間大小，于是將該空閑塊刪除后，鏈表狀態變為下圖所示：
編寫程序，模擬上述空閑空間申請。
輸入格式
第一行包含正整數 N，表示空閑塊個數。
接下來 N 行，每行包含兩個正整數，按照起始位置由小到大的順序依次描述每個空閑塊的起始位置和長度。
最后一行包含若干正整數，按照申請的先后順序依次描述每個申請的空間大小，最后以一個 -1 表示結束。
輸出格式
按照上述原則模擬完空閑空間申請后，輸出當前空閑空間鏈表狀態，即從當前位置開始，遍歷鏈表，分行輸出剩余空閑塊的起始位置和長度，位置和長度之間以一個空格分隔。
若申請完后，鏈表中沒有空閑塊，則什么都不輸出。
數據范圍
1≤N≤100
申請請求的個數范圍 [1,100]，
每個空閑塊的起始位置和長度以及每個申請的空間大小的取值范圍 [1,109]。
輸入樣例
12
1024 2048
8192 512
16384 1024
32768 8192
65536 8192
77824 1024
80896 3072
86016 1024
91136 5120
99328 512
104448 1024
112640 3072
1024 2560 10240 512 1024 6400 512 -1輸出樣例
104448 1024
112640 3072
1024 2048
8192 512
32768 1792
65536 8192
77824 1024
91136 5120year
2021
題目描述
假設某機場所有登機口（Gate）呈樹形排列（樹的度為3），安檢處為樹的根，如下圖所示。圖中的分叉結點（編號大于等于100）表示分叉路口，登機口用小于100的編號表示（其一定是一個葉結點）。通過對機場所有出發航班的日志分析，得知每個登機口每天的平均發送旅客流量。作為提升機場服務水平的一個措施，在不改變所有航班相對關系的情況下（即：出發時間不變，原在同一登機口的航班不變），僅改變登機口（例如：將3號登機口改到5號登機口的位置），使得整體旅客到登機口的時間有所減少（即：從安檢口到登機口所經過的分叉路口最少）。
編寫程序模擬上述登機口的調整，登機口調整規則如下：
- 首先按照由大到小的順序對輸入的登機口流量進行排序，流量相同的按照登機口編號由小到大排序；
- 從上述登機口樹的樹根開始，按照從上到下（安檢口在最上方）、從左到右的順序，依次放置上面排序后的登機口。
例如上圖的樹中，若只考慮登機口，則從上到下有三層，第一層從左到右的順序為：5、6、14、13，第二層從左到右的順序為：7、8、9、10、1、2、18、17、16、15，第三層從左到右的順序為：11、12、3、4、20、19。
若按規則1排序后流量由大至小的前五個登機口為3、12、16、20、15，則將流量最大的3號登機口調整到最上層且最左邊的位置（即：5號登機口的位置），12號調整到6號，16號調整到14號，20號調整到13號，15號調整到第二層最左邊的位置（即7號登機口的位置）。
輸入格式
首先輸入一個整數表示樹結點關系的條目數。
接著在下一行開始，按層次從根開始依次輸入樹結點之間的關系。其中分叉結點編號從數字 100 開始（樹根結點編號為 100，其它分叉結點編號沒有規律但不會重復），登機口為編號小于 100 的數字（編號沒有規律但不會重復，其一定是一個葉結點）。
樹中結點間關系用下面方式描述：
R S1 S2 S3其中 R 為分叉結點，從左至右 S1,S2,S3 分別為樹叉 R 的子結點，其可為樹叉或登機口，由于樹的度為 3，S1,S2,S3 中至多可以 2 個為空，該項為空時用 -1 表示。
如：
100 101 102 103表明編號 100 的樹根有三個子叉，編號分別為 101、102 和 103。
又如：
104 7 8 -1 表明樹叉 104 上有 2 個編號分別為 7 和 8 的登機口。
假設分叉結點數不超過 100 個。
分叉結點輸入的順序不確定，但可以確定：輸入某個分叉結點信息時，其父結點的信息已經輸入。
在輸入完樹結點關系后，接下來輸入登機口的流量信息，每個登機口流量信息分占一行，分別包括登機口編號（ 1～99之間的整數）和流量（大于 0 的整數），兩整數間以一個空格分隔。
輸出格式
按照上述調整規則中排序后的順序（即按旅客流量由大到小，流量相同的按照登機口編號由小到大）依次分行輸出每個登機口的調整結果：先輸出調整前的登機口編號，再輸出要調整到的登機口編號。編號間均以一個空格分隔。
數據范圍
分叉結點數量 [1,100]，
分叉結點編號不超過 300。
登機口數量 [1,99]，
流量數據范圍 [1,10000]
輸入樣例
12
100 101 102 103
103 14 108 13
101 5 104 6
104 7 8 -1
102 105 106 107
106 1 110 2
108 16 15 -1
107 18 111 17
110 3 4 -1
105 9 109 10
111 20 19 -1
109 11 12 -1
17 865
5 668
20 3000
13 1020
11 980
8 2202
15 1897
6 1001
14 922
7 2178
19 2189
1 1267
12 3281
2 980
18 1020
10 980
3 1876
9 1197
16 980
4 576輸出樣例
12 5
20 6
8 14
19 13
7 7
15 8
3 9
1 10
9 1
13 2
18 18
6 17
2 16
10 15
11 11
16 12
14 3
17 4
5 20
4 19year
2021
手機基站
題目描述
一共6個手機基站，具有記錄手機連接基站的能力，6個手機基站分別記為ABCDEF，他們具有自己的覆蓋范圍且任何兩個基站的覆蓋范圍不相交，基站保存的手機登陸日志包括手機號（11位，用字符串保存）、基站編號、登陸時間（6位數字，用字符串保存）、登出時間（6位，用學符串保存）
讀入某一天多個基站的手機登陸日志信息和一個要查找的人員手機號，查找與該人員同時空的手機號
輸入:一個N和N條登陸日志信息，最后還有一個要查找人員的手機號
輸出:輸出與要查找人員時間和地點有重疊的人員信息(即日志信息)，依次輸出手機號、基站編號、登陸時間和登出時間; 按照登陸時間進行排序,如果登陸時間相同按照手機號進行排序(如果一個人員的登出時間和另一個人員的登陸時間相同也算時間重疊)
輸入格式
見題目
輸出格式
見題目
輸入樣例
7
11111 A 080000 225959
22222 B 080000 225959
33333 A 100000 110000
44444 B 101000 110000
55555 A 120000 131000
66666 A 225959 235959
77777 A 100000 120000
11111輸出樣例
33333 A 100000 110000
77777 A 100000 120000
55555 A 120000 131000year
2023
老鼠回家路
題目描述
老鼠找食物，但是回家的時候找到最短路
輸入是x-y，x是1234其中的一個，代表四個方向，y是向這個方向走的距離
比如:
格式 數字 - 數字
1-2表示，向上走兩步
2-3向下走3步
3-1向左走1步
4-2向右走2步
0-0表示找到了
然后返回的時候，找到最短路徑
然后要求給他找回頭路，把重復的路給去掉
題目首先規定四個方向:1、2、3、4分別代表上下左右
輸入序列形式為1-3 3-4 1-4…，前一個數字代表方向，后一個數字代表前進距離，以0-0為結束，結束則代表老鼠找到了食物。
老鼠在碰到死路時會原路返回到分叉路口，探索下一個方向。
需要求解老鼠原路返回的最佳路徑，以2-3 4-2…等作為輸出。最佳路徑的描述是“不走回頭路”，即沒有折返過程即可
輸入格式
見題目
輸出格式
見題目
輸入樣例
1-1 3-1 1-1 2-1 4-2 1-2 4-1 1-1 2-1 3-1 1-1 0-0輸出樣例
2-3 3-1 2-1year
2023
字符串距離
題目描述
在信息論漢明碼中，存在一個定義;字符串之間的距離，指兩個等長字符串進行比較時，存在不同字母的位置的個數，例如01010和01011的距離是1(最后一位不一樣)，ROSES和roses的距離是5(每一位的大小寫都不一樣)
輸入格式
一個整數n(2<=n<=16),后接n行相同長度的字符串，字符串兩兩互不相同
輸出格式
輸出每對字符串兩兩比較的結果，輸出格式如下:
較小的字符串+空格+較大的字符串+空格+兩者的距離+換行符
優先輸出距離最小的字符串組合，如果有的組合距離相同，則優先輸出較小的字符串更小的組合，如果較小的字符串相同，則優先輸出較大的字符串更小的組合，如果比較結果多于6對，則只輸出前6對
PS:字符串的大小指的是字符串的ASC碼的字典序大小
輸入樣例
7
01010
11011
10101
10011
Roses
roses
cotes輸出樣例
10011 11011 1
Roses roses 1
01010 11011 2
10011 10101 2
Roses cotes 2
cotes roses 2year
2022
模擬編譯系統
題目描述
該程序會模擬一個解釋運行的編譯系統，每次從標準輸入中讀入一行指令，都要進行對應的操作，該程序中存在四種語句，語句最長200個字符，每個語句占且僅占一行，每行最多一個語句
四種語句分別如下:
1輸入語句，格式為"read+空格+<交量序列>+換行符"，變量序列是以空分隔的變量名稱的組合，變量的名字只可能為單個的小寫字母，變量不需要前聲明，緊接著下一行，輸入若干十進制整數，每個整數和上一行的變量對應賦值
2.賦值語句，格式為"變量+等于符號+表達式+換行符"，表達式中包含十進制整數，變量，±*/()這六種計算符號，整個語句不包含空白符
3.輸出語句，格式為"print+空格+<變量序列>+換行符"，緊接著下一行，輸出若干個變量的值，值以浮點數形式輸出，保留兩位小數，值之間以空格分隔，最后一個值后面不跟空格跟換行符
4.結束語句，格式為"exit+換行符"，該語句后直接結束程序運行
測試樣例中，所有語句均不包含語法錯誤，所有變量在使用前均會賦值(不需要考慮輸入錯誤的情況)
輸入格式
見題目
輸出格式
見題目
輸入樣例
read a
10
b=20
c=(a+b)/4
print a b c
exit輸出樣例
10.00 20.00 7.50year
2022
