2014年網(wǎng)研上機(jī)題目

1、Problem A.分?jǐn)?shù)加法題目描述 求2-a+2-b,其中a和b均為正整數(shù)，結(jié)果請用最簡分?jǐn)?shù)表示。輸入格式第一行為測試數(shù)據(jù)的組數(shù) T (1二T=4O0。請注意，任意兩組測試數(shù)據(jù)之 間是相互獨(dú)立的。每組測試數(shù)據(jù)一行，包含兩個整數(shù) a 和 b( 2=a,b=20)。輸出格式對于每組測試數(shù)據(jù)，在一行內(nèi)輸出結(jié)果，分子和分母用“/隔”開。輸入樣例22 43 2輸出樣例5/163/8Problem B最小堆題目描述給定一棵帶權(quán)二叉樹，請判斷它是不是一個最小堆。一棵二叉樹是一個最小堆，當(dāng)且僅當(dāng)對于樹上任意一個節(jié)點(diǎn)，它的權(quán)值都 小于或等于以它為根的子樹中的所有權(quán)值。輸入格式輸入數(shù)據(jù)第一行是一個整數(shù) T (1

2、=Tv=1O0，表示測試數(shù)據(jù)的組數(shù)。對于每組測試數(shù)據(jù)：第一行是一個整數(shù)N (1=Nv=1O0,表示樹的節(jié)點(diǎn)個數(shù)。接下來一行包含 N個正整數(shù)，第i個整數(shù)valuei(1二valuei=1000表示編號i 的點(diǎn)的權(quán)值。接下來N-1行，每行兩個整數(shù)u和v (1二u, v=N, u!=V，表示節(jié)點(diǎn)u是 節(jié)點(diǎn) v 的父節(jié)點(diǎn)。測試數(shù)據(jù)保證給定的一定是一棵二叉樹,并且節(jié)點(diǎn) 1 是樹的根結(jié)點(diǎn)。輸出格式對于每組測試數(shù)據(jù)，如果給定的樹是一個最小堆則輸出Yes否則輸出No。輸入樣例3110310 5 31 21 351 2 3 4 51 31 22 42 5輸出樣例YesNoYesProblem C進(jìn)程管理題目描述

3、在操作系統(tǒng)中，進(jìn)程管理是非常重要的工作，每個進(jìn)程都有唯一的進(jìn)程標(biāo)識（PID）。每個進(jìn)程都可以啟動子進(jìn)程，此時我們稱它為其子進(jìn)程的父進(jìn)程， 除了 PID為0的進(jìn)程之外，每個進(jìn)程有且只有一個父進(jìn)程，在這個任務(wù)中，你 需要實時維護(hù)操作系統(tǒng)運(yùn)行中的三個基本操作：1. FORK PID1 PID2標(biāo)識為PID1的進(jìn)程啟動了一個標(biāo)識為 PID2的子進(jìn)程。2. KILL PID結(jié)束標(biāo)識為PID的進(jìn)程。請注意，與此同時所有 PID的子進(jìn)程也 將同時結(jié)束。如果PID是不存在或已經(jīng)結(jié)束的進(jìn)程，則不做任何操作。3. QUERY PID查詢標(biāo)識為PID的進(jìn)程是否仍然存在。在初始狀態(tài)下，系統(tǒng)只開啟了 PID為0的進(jìn)程，

4、并且在任何情況下該進(jìn)程 不會結(jié)束。輸入格式輸入的第一行是一個整數(shù) T （T=50） ，表示輸入的數(shù)據(jù)組數(shù)。每組測試數(shù)據(jù)的第一行是一個整數(shù) N （1=Nv=1O0）,表示操作的數(shù)量。沒下來 N 行，每行按照上面的描述給出每個操作，輸入保證所有的進(jìn)程的PID都不相同，且一個進(jìn)程結(jié)束后不會被重新啟動，所有PID都是1,10 0之間的整數(shù)。輸出格式5FORK 0 1QUERY 1KILL 1QUERY 1QUERY 2輸出樣例YesNoNoYesProblem D.網(wǎng)絡(luò)傳輸題目描述網(wǎng)絡(luò)的高效互聯(lián)與智能傳輸是提升海量用戶服務(wù)請求映射效率的重要措 施。在這個任務(wù)中，你要用最少的傳輸時間，將特定的數(shù)據(jù)源發(fā)送

5、到指定的網(wǎng) 絡(luò)節(jié)點(diǎn)中。我么給定的網(wǎng)絡(luò)一共包含 N個節(jié)點(diǎn)（從1到N編號），其中節(jié)點(diǎn)1為數(shù)據(jù) 源。網(wǎng)絡(luò)中有M條無向邊（u,v,w），表示一條傳輸線連接節(jié)點(diǎn)u和節(jié)點(diǎn)V，且 數(shù)據(jù)通過這條傳輸線的平均時間為 w。由于傳送機(jī)制的限制，當(dāng)一個節(jié)點(diǎn)接收 到數(shù)據(jù)之后，它只能選擇與它互連的一個節(jié)點(diǎn)，并將數(shù)據(jù)轉(zhuǎn)發(fā)到該節(jié)點(diǎn)。節(jié)點(diǎn) 1 在初始化時只會發(fā)送一次數(shù)據(jù)，但在傳輸過程中它可以作為轉(zhuǎn)發(fā)節(jié)點(diǎn)。網(wǎng)絡(luò)中有k個目標(biāo)節(jié)點(diǎn)，你需要計算出該數(shù)據(jù)從節(jié)點(diǎn) 1傳送到所有K歌節(jié) 點(diǎn)所需要的最短時間。注意目標(biāo)節(jié)點(diǎn)可以按任意順序進(jìn)行傳送，數(shù)據(jù)也可以多 次經(jīng)過同一節(jié)點(diǎn)。輸入格式輸入數(shù)據(jù)第一行是一個整數(shù) T(T=5) ，表示測試數(shù)據(jù)的組數(shù)。對于每組測 試數(shù)據(jù)：第一行是三個正整數(shù) N,M,K (2=Nv=100Q 1二M二N(N-1)/2, K=10,分 別表示節(jié)點(diǎn)數(shù)，邊數(shù)和目標(biāo)節(jié)點(diǎn)數(shù)。接下來