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

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

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

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

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

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