山西財(cái)經(jīng)大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)814數(shù)據(jù)結(jié)構(gòu)考研題庫(kù)

2017年山西財(cái)經(jīng)大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)814數(shù)據(jù)結(jié)構(gòu)考研題庫(kù)（一）說(shuō)明：①本資料為VIP包過(guò)學(xué)員內(nèi)部使用資料。涵蓋了歷年考研?？碱}型和重點(diǎn)題型。一、選擇題1?本地用戶(hù)通過(guò)鍵盤(pán)登錄系統(tǒng)時(shí)，首先獲得的鍵盤(pán)輸入信息的程序是（ X命令滁聞中斷處理程序系統(tǒng)調(diào)用服務(wù)程序用戶(hù)登錄程序【答案】B［解析】夕陪B設(shè)備在與計(jì)算機(jī)連接時(shí)有多種方式，中斷技術(shù)就是一種常用方式。其工作原理是：利用處理機(jī)中斷信號(hào)線，夕卜部設(shè)備在需要服務(wù)的時(shí)候?qū)⒃摼€設(shè)置為有效，計(jì)算機(jī)若同意接受中斷則會(huì)停止當(dāng)前進(jìn)程的運(yùn)行,轉(zhuǎn)而服務(wù)發(fā)出中斷的物理設(shè)備（注意與陷阱，即軟中斷有區(qū)別），那么對(duì)不同外部設(shè)備進(jìn)行服務(wù)的程序代碼是不同的，如何找到這些代碼呢涎就要借助中斷向量,中斷向量一般是由硬件根據(jù)中斷的類(lèi)型（不同外設(shè)不同）計(jì)算所得,或計(jì)算機(jī)系統(tǒng)在開(kāi)機(jī)配置時(shí)所配置的。處理機(jī)取得中斷向量，其實(shí)就是一^理地址,該地址下存放的是為此中斷服務(wù)的代碼的起始地址。所以，當(dāng)鍵盤(pán)按下的時(shí)候’鍵酣制器獲得該操作動(dòng)作’先將鍵盤(pán)掃描碼讀入鍵盤(pán)緩沖區(qū)，再向處理機(jī)發(fā)出鍵盤(pán)中斷，適當(dāng)?shù)臅r(shí)候（一條指令的末尾或一條原語(yǔ)結(jié)束）處理機(jī)會(huì)響應(yīng)中斷，調(diào)用指定服務(wù)程序?qū)㈡I盤(pán)緩沖區(qū)中的鍵盤(pán)掃描碼輸入到登錄進(jìn)程中去。如此，最先響應(yīng)鍵盤(pán)的必然是中斷處理程序。本題中，像命令解釋器（例如cmd窗口\系統(tǒng)調(diào)用服務(wù)和用戶(hù)登錄程序都在中斷處理程序后面。某計(jì)算機(jī)采用微程序控制器’共有32條指令，公共的取指令微程序包含2條微程序,各指令TOC\o"1-5"\h\z對(duì)應(yīng)的微程序平均由4條微指令組成，采用斷定法（下址字段法）確定下條徹指令的地址，則微指令中下址字段的位數(shù)至少是：（ ）5689【答案】C【解析】32*4+2=130,27=I28<13Ov2，=256,所以至少需要8位才能表示完130個(gè)地一個(gè)TCP連接總是以1KB的最大段發(fā)送TCP?.發(fā)送方有足夠多的數(shù)據(jù)要發(fā)送。當(dāng)擁塞窗口為16KB時(shí)發(fā)生了超時(shí)’如果接下來(lái)的4個(gè)RTT（往返時(shí)間）時(shí)間內(nèi)的TCP段的傳輸都是成功的,那么當(dāng)?shù)?個(gè)RTT時(shí)間內(nèi)發(fā)送的所有TCP段都得到肯定應(yīng)答時(shí)，擁塞窗口大小是（ 17KB8KB9KB16KB【答案】C【解析】回顧TCP流量控制和擁塞控制（慢啟動(dòng)）的知識(shí)點(diǎn)，從第一個(gè)MSS開(kāi)始，每次發(fā)送成功，擁塞窗口值翻倍’四次以后，應(yīng)該為16,但是由于擁塞閾值變?yōu)?6/2=8,故三次成功后為8,以后為畑性增長(zhǎng)，故為8+1=9,答案為C。TOC\o"1-5"\h\z4.若將關(guān)鍵字1，2.3.4,5,6,7依次插入到初始為空的平衡二叉樹(shù)T中，則T中平衡因子為。的分支結(jié)點(diǎn)的個(gè)數(shù)是（ ）0123【答案】D［解析】將圖中給定的關(guān)鍵字序列依次插入到平衡樹(shù)中，構(gòu)成的平衡樹(shù)如下圖所示，由圖可知平衡因子為0的分支結(jié)點(diǎn)為3個(gè)葉子結(jié)點(diǎn)，故答案為D。5.對(duì)一組數(shù)據(jù)（2,12,16,88,5,10）進(jìn)行排序，若前三趟排序結(jié)果如下：第一趟：2,12,16,5,10,88第二趟：2,12,5,10,16,88第Hffi：2,5,10,12,16.88則采用的排序方法可能是（ 1A起泡排序希爾排序歸并排序D基數(shù)排序【答案】A【解析】題目中所給的三趟排序過(guò)程’顯然是使用起泡排序方法，每趟AE序時(shí)從前往后依次匕做，使大值"沉底希爾排序的基本思想是：先對(duì)序列進(jìn)行"宏觀調(diào)整”，待序列中的記錄"基本有序“時(shí)再進(jìn)行直接插入排序。宏觀調(diào)整的方法是：通過(guò)某種規(guī)則將大的待掃E序序列分割為若干小的待排序序列，再依次對(duì)這些小的序列直接插入排序。宏觀調(diào)整可以多次，每次分割的序列數(shù)逐漸増多，而每個(gè)序列中所包含的元素?cái)?shù)逐漸減少。歸并掃E序的基本操作是將多個(gè)小的有序序列合并為一個(gè)大的有序序列，然后“逐趟歸并"，直至整個(gè)序列為有序?yàn)橹??；鶖?shù)排序是分配排序的一種，這類(lèi)AE序不是通過(guò)關(guān)鍵字比較，而是通過(guò)"分配"和“收集“過(guò)程來(lái)實(shí)現(xiàn)排序的。本題中?很容易看岀大值逐漸"沉底"，顯然使用的是起泡排序法。

對(duì)于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹(shù)中一條查找路徑的序列是(A.95,22,91,24,94,7192,20,91,34,88,3521,89,77,29,36,3812,25,71,68.33,34【答案】A【解析】各選項(xiàng)對(duì)應(yīng)的査找過(guò)程如下圖所示，從中看到選項(xiàng)B、C、D對(duì)應(yīng)的查找樹(shù)都是二叉排序樹(shù)，只有選項(xiàng)A對(duì)應(yīng)的查找樹(shù)不是一棵二叉排序樹(shù),因?yàn)樵谝?1為根的左子樹(shù)中出現(xiàn)了比91大的結(jié)點(diǎn)94。(0選項(xiàng)C的夜找過(guò)程(鈔選項(xiàng)A的査找過(guò)程(b)(0選項(xiàng)C的夜找過(guò)程(鈔選項(xiàng)A的査找過(guò)程(b)選項(xiàng)B的在找過(guò)番1(山選項(xiàng)D的査找過(guò)程設(shè)有一個(gè)n行n列的對(duì)稱(chēng)矩陣A,將其下三角部分按行存放在一個(gè)一維數(shù)組B中，A[0][0)存放于中，那么第i行的對(duì)角元素，'網(wǎng)il存放于B中( )處。(i+3)*i/2B.(i+i)*i/2C.(2n-i+l)*i/2D.(2n-i-l)*i/2【答案】A【解析】A[i川]中列標(biāo)不大于行標(biāo)，又AI0H0]存放在B[0J中,所以存放的位置為i*(i+l)/2+i+1-l=i*(i+3)/2o已知廣義表LS=((a,b.c),(d,e,f)).用head和tail數(shù)取出LS中原子e的運(yùn)算是( \A.head(tail(LS))B.tail(head(LS))C.head(tail<head(tail<LS)))D.head(tail(tail(head<LS))))【答案】C[解析】head操作就是得到廣義表中第—的原子。函1操作就是得到除第一個(gè)原子^卜剩下元素構(gòu)成的表。tail(LS)得到((d.e,f)),head(tail(LS))得到(d,e.f),tail(head(tail(LS)))得到(e,f),head(tail(head(tail(1^)))得到6。若某文件系統(tǒng)索引結(jié)點(diǎn)(inode)中有直接地址項(xiàng)和間接地址項(xiàng)，則下列選項(xiàng)中，與單個(gè)文件長(zhǎng)度無(wú)關(guān)的因素是( )索引結(jié)點(diǎn)的總數(shù)間接地址索引的級(jí)數(shù)地址項(xiàng)的個(gè)數(shù)文件塊大小【答案】A【解析】根據(jù)文件長(zhǎng)度與索引結(jié)構(gòu)的關(guān)系可知，只有選項(xiàng)A是與單個(gè)文件長(zhǎng)度無(wú)關(guān)的。某設(shè)備中斷請(qǐng)求的相應(yīng)和處理時(shí)間為100m,每400ns發(fā)出一次中斷請(qǐng)求，中斷相應(yīng)所容許的最長(zhǎng)延退時(shí)間為50ns,貝U在該設(shè)備持續(xù)工作過(guò)程中CPU用于該設(shè)備的I/O時(shí)間占整個(gè)CPU時(shí)間百分比至少是( )12.5%25%37.5%5O%【答案】B【解析】每400m響應(yīng)一次中斷并且用100m進(jìn)行處理，所以該設(shè)備的I/O時(shí)間占用CPU時(shí)間百分比為100/400=25%,中斷響應(yīng)容許的延遲時(shí)間對(duì)此沒(méi)有影響，屬于干擾條件。?若一個(gè)有向圖具有拓?fù)渑判蛐蛄?，那么它的鄰接矩陣必定? IA.對(duì)稱(chēng)矩陣B稀疏矩陣C.三角矩陣D.一般矩陣【答案】C【解析】在圖論中，由f有向無(wú)環(huán)圖的頂點(diǎn)組成的序列，當(dāng)且僅當(dāng)滿(mǎn)足下列條件時(shí)，稱(chēng)為改圖的f拓?fù)渑判颍孩倜總€(gè)頂點(diǎn)岀現(xiàn)且岀現(xiàn)一次；②若頂點(diǎn)在序列中排在頂點(diǎn)B的前面，貝帷圖中不存在從頂點(diǎn)B到頂點(diǎn)A的路徑。由拓?fù)渑判虻男再|(zhì)知，有向圖的鄰接矩陣必定為三角矩陣。.連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址( I—定連續(xù)—定不連續(xù)不一德續(xù)D部分連續(xù)，部分不連續(xù)【答案】A［解析】連續(xù)存儲(chǔ)是指數(shù)據(jù)的物理存儲(chǔ)相連，即存儲(chǔ)單元的地址是連續(xù)的。二、填空題 .設(shè)T是一棵結(jié)點(diǎn)值為整數(shù)的二叉排序樹(shù),A是一個(gè)任意給定的整數(shù)。在下面的算法中,free_tree(T)在對(duì)二叉排序樹(shù)丁進(jìn)行后序遍歷時(shí)釋放二又排序樹(shù)T的所有結(jié)點(diǎn)；Delete_sUbtree(T,A),首先在二叉排序樹(shù)T中查找值為A的結(jié)點(diǎn)，根據(jù)查找情況分別進(jìn)行如下處理：(1)若找不到值為A的結(jié)點(diǎn)?則返回根結(jié)點(diǎn)的地址(2)若找到值為A的結(jié)點(diǎn).則刪除以此結(jié)點(diǎn)為根的子樹(shù)’并釋放此子樹(shù)中的所有結(jié)點(diǎn)?若值為A的結(jié)點(diǎn)是查找樹(shù)的根結(jié)點(diǎn)’刪除后變成空的二叉樹(shù)’則返NULL：否則返回根結(jié)點(diǎn)的地址。typedefstructnode(intdata,structnode*lchild,*rchild}node;voidfree_tree(node*T)(if(T?=null){free_cree(T->lchild)；free_tree(T->rchild): (1);}}node*delete_subCree(node*T,intA)(node*p?null,*q-T;TOC\o"1-5"\h\zwhilef(2) >(p=q;if(A<q->data)q°q->lchild;else(3) ;}if(qJ?null)(free_tree(q);if(p==null)T=null;elseif(A<p->data> 14) :else(5) ;>return(T);［答案】free(T)；q&&q->data!=A；q=q->rchild；p->lchild=nu11:p->rchild=nu11.設(shè)m、n均為自然數(shù)，m可表示為一些不超過(guò)n的自然數(shù)之和，f(m,n)為這種表示方式的數(shù)目。例f(5,3)=5,有5種表示方式：3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+1。①以下是該函數(shù)的程序段，請(qǐng)將未完成的部分填入，使之完整。intf(in,n)intm.n；{if(m==l)return(1)；if(n=l〉{return(2)：}if(m<n){returnf(m.m)：}if(m=n){return14-(3):}returnf(m<n-1)+f(m-n.(4))；}行穌f(6,4)= 0【答案】①1;1;f(m,n-1):n@9.TE有。個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)有 個(gè)度為1的結(jié)點(diǎn)、有 個(gè)分支(非終端)結(jié)點(diǎn)和 個(gè)葉子，該滿(mǎn)二叉樹(shù)的深度為 【答案】0：n-l)/2或Ln/2」：(n+l)/2；Liog;nJ+1［解析】滿(mǎn)二叉樹(shù)沒(méi)有度為1的結(jié)點(diǎn)，度為0的結(jié)點(diǎn)等于度為2的結(jié)點(diǎn)個(gè)數(shù)+1。 .閱讀下列程序說(shuō)明和程序，填充程序中的 【程序說(shuō)明】本程序完成將二叉樹(shù)中左、右孩子交換的操作。交換的結(jié)果如下所示(編科略)本程序采用非遞歸的方法，設(shè)立一個(gè)堆?；騇k存放還沒(méi)有轉(zhuǎn)換過(guò)的結(jié)點(diǎn)，它的棧頂指針為 交換左、右子樹(shù)的算法為：(1)把礙秘入堆棧。(2)當(dāng)堆棧不空時(shí)，取岀棧頂元素，交換它的左、右子樹(shù)，并把它的左、右子樹(shù)分別入棧。(3)重復(fù)(2)直到堆棧為空時(shí)為止。typedefstructnode*tree;structnode{inrdata;tr-c：chi1d,rchi1d；>exchange(t)treet;{treer,p；treestack(500J;inttp=0;(1)while{tp>?0){(2)lf((3)){r*p->lchild；p->Lehild*p->rchlid;p->rchiLd*r:stackt t4i-p->lchild；stack［**tp|-p->rchiId;}))【答案】Stack［tp］?stspestMCkftp--］：P：++tp 【解析】本題主要使用堆棧完成了二叉樹(shù)左右子樹(shù)交換的操仁首先根結(jié)點(diǎn)進(jìn)棧，然后判斷棧足否為空，如果不為空，則取棧頂元素，交換取出節(jié)點(diǎn)的左右指針。并將左右指針?lè)謩e進(jìn)桟，重復(fù)這一操作。完成二叉樹(shù)左右孩子的交換。.串是一種特殊的線性表,其特殊性表現(xiàn)在 :串的兩種最基本的存儲(chǔ)方式 ； 兩個(gè)串相等的充分必要條件 0［答案】其數(shù)據(jù)元素都是字符；II賄存儲(chǔ)；鏈?zhǔn)酱鎯?chǔ)；串的長(zhǎng)度相等且兩串中對(duì)應(yīng)位置的字符也相等.深度為H的完全二叉樹(shù)至少有 個(gè)結(jié)點(diǎn):至多有 個(gè)結(jié)點(diǎn);H和結(jié)點(diǎn)總數(shù)N之間的關(guān)系 【答案】2助；2h-1：H=Llog2Nj+1.在單鏈表L中，指針P所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件 【答案】P->next!=NULL［解析］指針?biāo)腹?jié)點(diǎn)的指針域所指向的元素非空，說(shuō)明該指針?biāo)腹?jié)點(diǎn)有后繼結(jié)點(diǎn)。.在一個(gè)具有n個(gè)單元的順序棧中,假定以地址高端(即下標(biāo)為n的單元)作為棧底，以top作為棧頂指針’則當(dāng)向棧中壓入一個(gè)元素時(shí),top的變化是top= 【答案】【解析】由于棧底在地址高端，棧中壓入一個(gè)元素時(shí),棧頂向地址底端移動(dòng)一個(gè)單位，所以top-1r.建立索引文件的目的是 。［答案］提高查找速度.以下程序的功能是實(shí)現(xiàn)帶附加頭結(jié)點(diǎn)的單鏈表數(shù)據(jù)結(jié)點(diǎn)逆序連接，請(qǐng)?zhí)羁胀晟浦oidreverse(pointerh)/*h為附加頭結(jié)點(diǎn)指針?/{pointerp,q；p?h->next;h->next-NULL;while(_Q1_)(q=p；p：=p->next;q->next?h->next;h->next=(2) })［答案】(1)PLNULL〃鏈表未到尾就一行(2)q〃將當(dāng)前結(jié)點(diǎn)作為頭結(jié)點(diǎn)后的第一元素結(jié)點(diǎn)插入三、算法設(shè)計(jì)題.假設(shè)KI,…，Kn是n個(gè)關(guān)鍵詞’試解答：(1)試用二叉查找樹(shù)的插入算法建立一棵二叉查找樹(shù)，即當(dāng)關(guān)鍵詞的插入次序?yàn)镵I.K2，…，Kn時(shí)，用算法建立一棵以IlinkTlink鏈接表示的二叉查找樹(shù)。(2)設(shè)計(jì)一個(gè)算法，打印出該二叉查找樹(shù)的嵌套括號(hào)表示結(jié)構(gòu)。例如，K1=B.K2=A,K3=D.K4=C.K5=E,貝IJ用二叉查找樹(shù)的插入算法建立如圖所示的二叉查找樹(shù)。圖該二叉查找樹(shù)的嵌套括號(hào)表示結(jié)構(gòu)為：B(A.D(C,E))o【答案】(1)算法如下：BSTreeBST_Search(BSTreebst,f,ElementK,mt*tag)〃在二義排兩bst上査找值為K的結(jié)點(diǎn)，返冋其雙親結(jié)點(diǎn)指針f{if(!bst)(*tag=0;return(f);)elseif(bst->key=?K){*tag?l;return(bst);}elseif(bst->key>K){f?bst；returnBST_Search(bst->llink,ftag);)

else{f*bst;returnBST__Search(bst->rlink,f,K,tag);})//BST_Search BSTreeCreat_BST(ElemTypeR(],intn)〃以存儲(chǔ)在數(shù)組R中的n個(gè)關(guān)健字，建立?棵初始為空的二叉排序樹(shù){int*flag?0;BSTreet; for(i-1ji<n?i+*)(f-null; f=BST_Search(t,f,K(i],flag);if(*tag—1)tag=O;//不再插入相同值結(jié)點(diǎn)else(3?(BSNode*)ma1loc(sizeof(BiNode));//申請(qǐng)結(jié)點(diǎn)空間s->key-K(i)；s->llink-null;s->rlink*null;if(f**null)t=?a //根禁點(diǎn)elseif(a->key<f->data)f->llinkup;//左子女elsef->rchild=s; 〃右子女}//else}//for;returnt; }//結(jié)束算法(2)算法如下：voidPrintfBSTreet)//以嵌套括號(hào)表示結(jié)構(gòu)打印.叉排序樹(shù){if(tl-null)(printf(t->data); //打印根結(jié)點(diǎn)值if(t->lchildIIt->rchild);//左"女和右子女中至少有一個(gè)不空(printf //輸出左括號(hào)Print(t->lchild); //輸岀左f?樹(shù)的嵌套括號(hào)表示if(t->rchild)printf(-,”)；//若右子輝不空，輸出逗號(hào)Print(t->rchild); //輸出右子樹(shù)的嵌套括號(hào)表示printf(??)"); //輸出右括號(hào)}//if}//if)//Print.寫(xiě)出一個(gè)遞歸算法來(lái)實(shí)現(xiàn)字符串逆序存儲(chǔ)。【答案】算法如下：voidInvertstore(charA[])//字符串逆序存儲(chǔ)的遞歸算法{charch;staticinti=0; //需要使用靜態(tài)變量scantif(chl=?.1) //規(guī)定’.'是字符串輸入結(jié)束標(biāo)志(InvertStore(A);A(i++]-ch;//字符串逆序存儲(chǔ)}A[i]=?XO1; //卞符串結(jié)尾標(biāo)記}〃結(jié)束算法Invertstore.已知兩個(gè)鏈表A和B分別表示兩個(gè)集合，其元素遞增排列。編一函數(shù)，求A與B的交集’并存放于A鏈表中?！敬鸢浮克惴ㄈ缦拢簆a?la->next;pb=lb->next;//i殳工作指針pa和pb;pc=la； 〃結(jié)果表中當(dāng)前合并結(jié)點(diǎn)的前驅(qū)的指針while(pa&&pb)if(pa?>data=>?pb->data)//交集外人結(jié)槩應(yīng)中{pc->next=pa:pc=pa;pa=pa->next；u=pb;pb=pb->next;free(u);elseif(pa->data<pb->data)(u=pa;pa=pa->next;free(u);)//釋放結(jié)點(diǎn)空間else(u=pb;pb=pb->next;free(u);)while(pa){u=pa;pa=pa->next;free(u);}//釋放結(jié)點(diǎn)空間while(pb)(u=pb；pb=pb->next;free(u);}//釋放結(jié)點(diǎn)空間pc->next=null;// 表尾標(biāo)i己free(lb);〃注：本算法中也町對(duì)B表不作釋放空間的您理26.設(shè)記錄R[i|的關(guān)鍵字為RliJ.KEY(I細(xì))，樹(shù)結(jié)點(diǎn)T[i|(l<i<K-l)指向敗者記錄，T[()|為全勝記錄下標(biāo)。寫(xiě)一算法產(chǎn)生對(duì)應(yīng)上述Rin(l<?>的敗者樹(shù)，要求除R|l??燈和Tr|()..k-ll以外，只用O(I輔助空間?！敬鸢浮克惴ㄈ缦拢簐oidAdiustfintT[),ints)(〃選搟最小災(zāi)健了記錄后，沿從葉結(jié)點(diǎn)到槌結(jié)點(diǎn)T[0]的路徑理整畋松首t"(s+k)/2; //T(t]feR[s]的雙親站點(diǎn)while(t>0)(if(R(s].key>R(T[t)].key)s<—>T[tJ;〃s指示新的勝?zèng)At-t/2;}//whileT(0)?a;}//AdjustvoidCreateLoserTree(intT(J)(//R(0]到為完全義樹(shù)T的葉結(jié)點(diǎn)，本薛法逮立敗者樹(shù)R|kl.key?MINKEY； //MINKEY是與題中要求的關(guān)鍵字類(lèi)型相同的機(jī)器呆小數(shù)for(i-0;i<k?i++)T[il-k; //i殳1RT中“敗者”的初値//依次從R(k-lbR(k-2h-,R(0]出發(fā)調(diào)整畋者for(i=k-l;k>?0;i--)Adjust(Tri);}//CreateLoserTree27.設(shè)有一頭指針為L(zhǎng)的帶有表頭結(jié)點(diǎn)的非循環(huán)雙向鏈表，其每個(gè)結(jié)點(diǎn)中除有pred(前驅(qū)指針).data(數(shù)據(jù))和next(后繼指針)域外，還有一個(gè)訪問(wèn)頻度域freq。在鏈表被啟用前，其值均初始化為零。每當(dāng)在鏈表中進(jìn)行一次Locate(L,x)運(yùn)算時(shí)，令元素值為x的結(jié)點(diǎn)中freq域的值増1,并使此鏈表中結(jié)點(diǎn)保持按訪問(wèn)頻度非增(遞減)的順序排列’同時(shí)最近訪問(wèn)的結(jié)點(diǎn)排在頻度相同的結(jié)點(diǎn)的最后，以便使頻繁訪問(wèn)的結(jié)點(diǎn)總是靠近表頭。試編寫(xiě)符合上述要求的Locate(L.x)運(yùn)算的算法該運(yùn)算為函數(shù)過(guò)程，返回找到結(jié)點(diǎn)的地址，類(lèi)型為指針型?！敬鸢浮克惴ㄈ缦拢篋LinkListlocate(DLinkedListL,ElemTypex)//L是帶頭結(jié)點(diǎn)的按訪問(wèn)頻度遞減的雙向鏈表//本算法先査找數(shù)據(jù)x,査找成功時(shí)結(jié)點(diǎn)的訪問(wèn)頻度域增1,最后將該結(jié)點(diǎn)按頻度遞減插入縫表中(DLinkedListp=L->next,q; //p為L(zhǎng)表的匸作指針，q為p的前知用干査找插人位輪while(p&&p->data!=x)p=p->next;//查找值為x的結(jié)點(diǎn)if(!p)(printf(-不存在所査結(jié)點(diǎn)\n");exit(O);}else{p->freq++;//令元素值為x的結(jié)點(diǎn)的freq域加1p->next->pred=p->pred;//將P結(jié)點(diǎn)從鏈表上摘Ep->pred->next=p->next;q=p->pred;//以I、?査找P結(jié)點(diǎn)的插入位置.while(q!=L&&q->freq<p->freq)q=q->pred;p->next=q->next;q->next->pred=p;//將p結(jié)點(diǎn)插入p->pred=q;q->next=p;return(p);〃返回值為x的結(jié)點(diǎn)的指針}//算法結(jié)束.請(qǐng)運(yùn)用快速排序思想’設(shè)計(jì)遞歸算法實(shí)現(xiàn)求n(n>l)個(gè)不同元素集合中的第「(1塵n)小元素?！敬鸢浮克惴ㄈ缦拢篿ntpartition(RecTypeA[],intlrn){inti=l,j?n；x=A|i].key；i-1；while(i<i)(while(i<j&&A[j].key>?x)j■-;if(i<j)A[i+*]-A(j];while(i<j&&A[i].key<?x)i+*;if(i<j)A[j—)returni;voidFind_j(RecTypeA[],intn,intj);{i=partition(A,1,n);while(iI?j)if(i<j)i?quicksart(A,i+1rn); //在后半?部分繼續(xù)進(jìn)行劇分elsei?quicksart(Rr1,i-1); 〃在前半部分繼續(xù).進(jìn)濘劃分.按圖的寬度優(yōu)先搜索法寫(xiě)一算法判別以鄰接矩陣存儲(chǔ)的有向圖中是否存在由頂點(diǎn)V,到頂點(diǎn)V,的路徑冋)【答案】算法如下：intvisitedfn]:〃設(shè)有向圖有n個(gè)頂點(diǎn)intPathiToj(AdjMatrixg,vertypeVi,vertypeVj)〃判斷以鄰接矩陣方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)Vi到頂點(diǎn)Vj的路徑(for(i=0;i<n;i++)visited[i]-0;i?GraphLocateVertex(g,Vi);j=GraphLocateVertex(gzVj);Queuelnit(Q); 〃Q是隊(duì)列，容量足夠大,元素是頂點(diǎn)編號(hào)(0..n-1)visited(i； ;Queuein(Q,i);//Vi人隊(duì)while(IQueueEmpty(Q))(v=QueueOut(Q);for(w=0;i<n;w++){if(g[vj(wj—1&&w=nj){printf("Vi到頂點(diǎn)Vj存在路徑\n");return(l);}if(g[V)【w]==1&&1visited[w])(visitedfw]?1;Queuein(Q,w)；}}//forprinH(”Vi到頂點(diǎn)Vj不存在路徑")；return(O);

.借助于快速排序的算法思想,在一組無(wú)序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組r[l..h]中。若查找成功，則輸岀該記錄在r數(shù)組中的位置及其值，否則顯示“notflnd”信息。請(qǐng)編寫(xiě)出算法并簡(jiǎn)要說(shuō)明算法思想?！敬鸢浮克惴ㄈ缦拢篿ntindex(RecTypeR(],intl,hrdatatypekey)tintwhile(i<j)｛while(i<=j&&R(j).key>key)j一；if(R(j).key-=key)returnj;while(i<-=j&&R(i].key<key)七if(R(i].key==key)returni;if(i<j)R[iJ<—>R[j);//本句的有無(wú)不影響査找結(jié)果printf("notfind");return)//index四、應(yīng)用題.在改進(jìn)了的(無(wú)回溯)字符串模式匹配中，要先求next數(shù)組的值。下面是求nextval值的算法。TYPESAR=ARRAY【I??m]OFINTEGER;PTYhARRAY[1??m]OFCHAR;PROCEDUREnext2(P:PTY;VARNEXTVAL:SAR)；｛在模式P中求nextv』數(shù)組的值｝BEGINJ:=l;NEXTVAL(1):=0;K:=0REPEATIF(K-0)OR(P()THEN[J:=J+1;K:?K+1;IFP(J]=P(K]THENNEXTVAL[J]:=NEXTVAL[K]89891011UNTILJ=mEND;算法中第4行有叩]=P[K]，第六行中也有P|J|=P|K|兩處比較語(yǔ)句相同。請(qǐng)分析說(shuō)明此兩處比較語(yǔ)句的含義是什么粉析此算法在最壞情況下的時(shí)間復(fù)雜度是多少？【答案】第4行的P【J]=P|KJ語(yǔ)句是測(cè)試模式串的第J個(gè)字符是否等于第K個(gè)字符，如是，則指針J和K均増加1,繼續(xù)匕做。第6行的PlJ]=P〔K]語(yǔ)句的意義是，當(dāng)?shù)贘個(gè)字符在模式匹配中失配時(shí)，若第K個(gè)字符和第J個(gè)字符不等，則下個(gè)與主串匹配的字符是第K個(gè)字符：否則，若第K個(gè)字符和第J個(gè)字符相等，則下個(gè)與主串匹配的字符是第K個(gè)字符失配時(shí)的下一個(gè)(即NEXTVALIK]\該算法在最壞情況下的時(shí)間復(fù)雜度O掃)。.請(qǐng)寫(xiě)出應(yīng)填入下列敘述中( )內(nèi)的正確答案。排序有各種方法，如插入排序、快速flE序、堆排序等。設(shè)_數(shù)組中原有麴g如下：15,13.20,18,12,60。下面是一組用不同排序方法進(jìn)行TS排序后的結(jié)果。()排序的結(jié)果為：12,13,15,18,20,60()排序的結(jié)果為：13,15,18,12,20,60()排序的結(jié)果為：13,15,20,18,12,60()排序的結(jié)果為：12,13,20,18,15,60【答案】①快湖序②起泡排序③匐妾插入排序④堆排序.夕卜排序中為何采用k一路(k>2>合并而不用2-路合并?這種技術(shù)用于內(nèi)排序有意義嗎?為什么？【答案】夕卜排序用k-路歸并(E)是因?yàn)閗越小，歸并趟數(shù)越多，讀寫(xiě)外存次數(shù)越多，時(shí)間效率越低’故一般應(yīng)大于最少的2-路歸并。若將k-路歸并的敗者樹(shù)思想單純用于內(nèi)排序，因其由勝者樹(shù)改進(jìn)而來(lái)，且輔助空間大，完全可由堆排序取代，故將其用于內(nèi)排序效率并不高。.閱讀下面的算法’說(shuō)明算法實(shí)現(xiàn)的功能。node*link(node*headl, *head2)(node*p, *q; p=headl;while(p->next!-headl)p*p->next;q=head2;while(q->next!shead2)q?q->next;p->next=head2; q->next=headl;return(headl);}［答案］本算法功能是將兩個(gè)無(wú)頭結(jié)點(diǎn)的循環(huán)鏈表合并為f循環(huán)鏈表。Headl最后f結(jié)點(diǎn)的鏈域指向head2.heM2最后一個(gè)結(jié)點(diǎn)的鏈域指向headl,headl為結(jié)果循環(huán)鏈表的指針。.如果兩個(gè)串含有相等的字符，能否說(shuō)它們相等？［答案］僅從兩串含有相等的字符，不能判定兩串是否相等，兩串相等的充分必要條件是兩串長(zhǎng)度相等且對(duì)應(yīng)位置上的字符相同(即兩串串值相等1.畫(huà)出對(duì)算術(shù)表達(dá)式A-B*C/『E"求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過(guò)程?！敬鸢浮吭O(shè)操作數(shù)棧是opnd，運(yùn)算符棧是optr,對(duì)算術(shù)表達(dá)式入#"。王仃求值，過(guò)程如表所小0表操作數(shù)棧和運(yùn)算符找的變化過(guò)程歩驟opnd^k棧輸入字符主妾操作初始tAR*OD￡tF#PUSH9PTR.■#')1A9AB-C/DEtF9PUSHiOPND.A)2Af-我，C，D-￡TF#PUSHtOPTR.'?)3ABt-￡*C/D-E:FtPUSHIOPND.fl)4AB?C/D-￡TF#PUSHtOPTR.'?')5ABCQtD-ElFfPUSH{OPND.C)6AT(T=8*09-i/D-ETF#PUSHIOPND、POP2PNDEPOP(OPND)，PUSHiOPTR,'fj7ATD#■/Q-E1〃PUSH(OPND.D)8A7XT=TfD)nr=A-n?-9-二￡頃x^POP(OPND):y-POPfOPND)PUSH(OPND.y!xY.x=POP(OPND).'=POP(OPND):PUSH(OPND.y-x)PUSHiOPTR.?)9TEf-￡fF*PUSHlOPND.E)10TE?-tJ-F*PUSHfOPTR.'1')11TEF#-f序PUSH(OPND,F)12TETS(S=￡!F)R(R=TF?-?Ix=POP(OPND.\=POPggPOP(OPTR)PUSHIOPND.y1x)x=POP(OPND)"POP(OPND)?OP9PTR)PUSH2PND，yF2017年山西財(cái)經(jīng)大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)814數(shù)據(jù)結(jié)構(gòu)考研題庫(kù)（二）說(shuō)明：①本資料為VIP包過(guò)學(xué)員內(nèi)部使用資料。涵蓋了歷年考研?？碱}型和重點(diǎn)題型。一、選擇題1?有兩個(gè)并發(fā)執(zhí)行的進(jìn)程P1和P2,共享初值為1的變量x。P1對(duì)x加LP2對(duì)x減1。加1和減1操作的指令序列分別如下所示?！?操作〃減1操作loadRl.x 伽X到寄存器R1中l(wèi)oadR2?xinc R1dec R2storex,Rl //將R1的內(nèi)容存入xstorex.R2兩個(gè)操作完成后’2的值（ XA.可能為-1或3B.只能為1C.可能為0、1或2D.可能為-1、0、1或2【答案】c［解析】這是在數(shù)據(jù)庫(kù)中常有的操作。為保證數(shù)據(jù)的正確，避免產(chǎn)生錯(cuò)誤，系統(tǒng)必須保證數(shù)據(jù)的同步。而保證數(shù)據(jù)的同步一般采取加鎖的方法，讓進(jìn)程P1和P2互斥訪問(wèn)共享變量X。當(dāng)然用信號(hào)量和P、V操作也是可以保證互斥操作，達(dá)到數(shù)據(jù)同步的。本例中，由于沒(méi)有采取保證數(shù)據(jù)同步的相應(yīng)措施’則最后結(jié)果就會(huì)出現(xiàn)差錯(cuò)。例如’當(dāng)正常情況下,進(jìn)程P1和P2先后對(duì)x操作’可以看到x值的變化為初始1一2一1的過(guò)程,若P2,P1先后操作，則x值的變化為初始1一0-1,這是正確的。若考慮一種并發(fā)的情況,進(jìn)程P1和P2先后執(zhí)行了取數(shù)load的操作，它們得到的x值均為1,運(yùn)算后，P1和P2的x值分別為2和0,此時(shí)要看哪個(gè)進(jìn)程后執(zhí)行存數(shù)store的操作了，哪個(gè)進(jìn)程后操作，結(jié)果就是SB個(gè)逬程的x值’所以可能的結(jié)果為?；?加上前面正確的x值1,則可能的結(jié)果就有3種了。TOC\o"1-5"\h\z\o"CurrentDocument"2.將有關(guān)二叉樹(shù)的概念推廣到三叉樹(shù)，則一棵有244個(gè)結(jié)點(diǎn)的完全三叉樹(shù)的高度為（ 1A.4567【答案】C［解析】若二叉樹(shù)中最多只有最下面兩層的結(jié)點(diǎn)的度數(shù)可以小于2,并且最下面一層的葉結(jié)點(diǎn)都依次排列在該層最左邊的位置上’則這樣的二叉樹(shù)稱(chēng)為完全二叉樹(shù)。具有n個(gè)（n>o）結(jié)點(diǎn)的完全二叉樹(shù)的高度為「奧血+1）1或卩。g2n」+l：由完全二叉樹(shù)類(lèi)推到完全三叉樹(shù)可知,n個(gè)結(jié)點(diǎn)的完全三叉樹(shù)的高度為1理3（肝1）〕或卩吶屮13.系統(tǒng)為某進(jìn)程分配了4個(gè)頁(yè)框,該進(jìn)程已訪問(wèn)的頁(yè)號(hào)序列為2,0,2,9,3.4.2.8,2,3,8.4,5若進(jìn)程要訪問(wèn)的下一頁(yè)的頁(yè)號(hào)為7,依據(jù)LRU算法,應(yīng)淘汰頁(yè)的頁(yè)號(hào)是（ 1A.2B.3C.4D.8【答案】B［解析】LRU置換算法是選擇最近最久未使用的頁(yè)面予以淘汰。進(jìn)程有4個(gè)頁(yè)框，題中訪問(wèn)過(guò)程中頁(yè)框的變化如下：朝：2029342823845頁(yè)框：22000293344230222934482389934282384342823845淘汰：0 92訪問(wèn)頁(yè)號(hào)為7的頁(yè)時(shí),內(nèi)存中存在的頁(yè)的頁(yè)號(hào)是：3、8、4和5,根據(jù)LRU定義應(yīng)淘汰的是3。4.以太網(wǎng)的MAC協(xié)議提供的是（ X無(wú)連接不可靠服務(wù)無(wú)連接可靠服務(wù)C有連接不可靠服務(wù)D有連接可靠服務(wù)【答案】A?！窘馕觥靠疾橐蕴W(wǎng)MAC協(xié)議，考慮到局域網(wǎng)信道質(zhì)量好，以太網(wǎng)采取了兩項(xiàng)重要的措施以使通信更簡(jiǎn)潔：①采用無(wú)連接的工作方式；②不對(duì)發(fā)送的數(shù)據(jù)幀進(jìn)行編號(hào)，也不要求對(duì)方發(fā)回確認(rèn)。因此，以太網(wǎng)提供的服務(wù)是不可靠的服務(wù)?即盡最大努力交付，差錯(cuò)的糾正由高層完成。5.排序過(guò)程中，對(duì)尚未確定最終位置的所有元素進(jìn)行一遍處理稱(chēng)為一趟排序。下列排序方法中,每一趟排序結(jié)束時(shí)都至少能夠確定一個(gè)元素最終位置的方法是（ IL簡(jiǎn)單選擇排序II希爾排序III.快速排序IV.1?非V.二路歸并排序僅I、III、IV僅I、II、III僅II、III、IVD?僅III、IV、V【答案】A。【解析】其中簡(jiǎn)單選擇排序、堆排序?qū)儆谶x擇類(lèi)排序,每一趟排序結(jié)束時(shí)將確定最大（或最?。╆P(guān)鍵字所在的位置?？焖倥判蛎恳惶伺判蚪Y(jié)束時(shí)將確定基準(zhǔn)關(guān)鍵字所在的位置。希爾排序、

二路歸并排序每一趟排序結(jié)束時(shí)不一定能確定一個(gè)元素的最終位置。6.對(duì)線性表進(jìn)行折半查找時(shí)’要求線性表必須（ 1A以I質(zhì)序方式存儲(chǔ)B以|質(zhì)序方式存儲(chǔ)，且數(shù)據(jù)元素有序C以鏈接方式存儲(chǔ)D似鏈接方式存儲(chǔ)，且數(shù)據(jù)元素有序【答案】B［解析］二分查找又稱(chēng)折半查找，優(yōu)點(diǎn)是比較次叫，查找速度快，平均性能好：其缺點(diǎn)是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。折半查找方法適用于對(duì)以順序方式存儲(chǔ)的有序表的查找，查找效率較高。7.若數(shù)據(jù)元素序列11.12,13,7,8.9,23.4,5是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是（ 1A起泡排序B?插入排序選擇排序二路歸并排序【答案】B【解析】經(jīng)過(guò)兩趟排序后’A項(xiàng)起泡排序的結(jié)果是兩個(gè)最小或最大的元素放到了序列的最終位置；B項(xiàng)插入排序的結(jié)果是前三個(gè)數(shù)有序即可；C項(xiàng)選擇排序結(jié)果是兩個(gè)最小的元素在最前面按順序扌非好；D項(xiàng)二路歸并排序的結(jié)果是長(zhǎng)度為4的子序列有序，即前4個(gè)數(shù)排好序，接下來(lái)的4個(gè)數(shù)扣防序。顯然題目中的元素序列只能是插入排序第二趟排序后的結(jié)果，因此,B項(xiàng)正確。TOC\o"1-5"\h\z8.已知串S=，aaab，其N(xiāo)ext數(shù)組值為（ 1A.0123112312311211【答案】A【解析】KMP算法的next數(shù)組建立的原則0當(dāng)j=1時(shí)next[j]=Maxik11<k<j且即??8/='Pl?+lP；；next[j]=1 其它情況9.下面關(guān)于哈希（Hash,雜湊）查找的說(shuō)法正確的是（ X哈希函數(shù)構(gòu)造的越復(fù)雜越好,因?yàn)檫@樣隨機(jī)性好,沖突小除留余數(shù)法是所有哈希函數(shù)中最好的不存在特別好與壞的哈希函數(shù)，要視情況而定若需在哈希表中刪去一個(gè)元素,不管用何種方法解決沖突都只要簡(jiǎn)單地將該元素刪去即可【答案】C【解析】若數(shù)據(jù)結(jié)構(gòu)中存在關(guān)鍵字和K值相等的記錄，則必定在f(K)的存儲(chǔ)位置上，由此，不需要進(jìn)行比較便可直接取得所查記錄。在此，稱(chēng)這個(gè)對(duì)應(yīng)關(guān)系f為哈希(Hash)函數(shù)，哈希函數(shù)的選擇體情況而定。10.設(shè)被排序的結(jié)點(diǎn)序列共有'個(gè)結(jié)點(diǎn)?在該序列中的結(jié)點(diǎn)已十分接近排序的情況下，用直接插入法、歸并法和一般的快速排序法對(duì)其排序?這些算法的時(shí)間復(fù)雜性應(yīng)為( 1A.O(N).O(N),O(N)B.O(N).O(N*log2N).O(N*log2N)C.O(N),O<N*log2N),O(N2)D.O(N2),O(N*log2N),O(N2)【答案】C【解析】因?yàn)樵撔蛄兄械慕Y(jié)點(diǎn)已經(jīng)十分接近排序的情況’對(duì)于直接插入法，大部分結(jié)點(diǎn)只需要直接插入后面即可，因此時(shí)間復(fù)雜度為O(N),對(duì)于采用歸并法’它是一種穩(wěn)定的排序方法，它的時(shí)間復(fù)雜度為O(N】。史N).對(duì)于一般的快速排序法，序列越接近有序,所需要的比較次數(shù)越多，此時(shí)的時(shí)間復(fù)雜度為O<N2)O11.某機(jī)器有一個(gè)標(biāo)志寄存器，其中有進(jìn)位/借位標(biāo)志CF、零標(biāo)志ZF、符號(hào)標(biāo)志SF和溢岀標(biāo)志OF,條件轉(zhuǎn)移指令bgt(無(wú)符號(hào)整數(shù)比較大于時(shí)轉(zhuǎn)移)的轉(zhuǎn)移條件是(XCF+OF=0SF+ZF=OCF+ZF=OCF+SF=O【答案】c［解析］判斷無(wú)符號(hào)整數(shù)A>B成立，滿(mǎn)足的條件是結(jié)果不等于0,即零標(biāo)志ZF=O,且不發(fā)生進(jìn)位，即進(jìn)位/借位標(biāo)志CF=O。所以正確選項(xiàng)為C。其余選項(xiàng)中用到了符號(hào)標(biāo)志SF和溢出標(biāo)志OF,顯然可以排除掉。12.哈希文件使用哈希函數(shù)將記錄的關(guān)鍵字值計(jì)算轉(zhuǎn)化為記錄的存放地址?因?yàn)楣：瘮?shù)是一對(duì)一的關(guān)系則選擇好的( )方法是哈希文件的關(guān)鍵。哈希函數(shù)除余法中的質(zhì)數(shù)沖突處理哈希函數(shù)和沖突處理【答案】D［解析】哈希表是根據(jù)文件中關(guān)鍵字的特點(diǎn)設(shè)計(jì)一種哈希函數(shù)和處理沖突的方法將記錄散列到存儲(chǔ)設(shè)備上。二、填空題 .一棵深度為k的平衡二叉樹(shù)，其每個(gè)非終端結(jié)點(diǎn)的平衡因子均為0,則該樹(shù)共有 個(gè)結(jié)點(diǎn)。【答案】2—1［解析】每個(gè)非終端結(jié)點(diǎn)都是0表示該平衡二叉樹(shù)沒(méi)有高度落差。也就是說(shuō)它是一棵滿(mǎn)二叉樹(shù)。故結(jié)點(diǎn)個(gè)數(shù)為渣-1。.在二叉樹(shù)中,指針p所指結(jié)點(diǎn)為葉結(jié)點(diǎn)的條件是 。［答案】p->lchild=null&&p->rchlid==null ［解析］葉子節(jié)點(diǎn)的左右孩子都不存在。.若不考慮基數(shù)排序?則在排序過(guò)程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的 和記錄的 【答案】比較：移動(dòng).在順序存儲(chǔ)的二叉樹(shù)中,編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是 o【答案】Lk>g2S」=l_lOg2【」。［解析】用II賄存儲(chǔ)結(jié)構(gòu)存儲(chǔ)二叉樹(shù)時(shí)，歟完全二叉樹(shù)的形式存儲(chǔ),非完全二叉樹(shù)存儲(chǔ)時(shí),要加“虛結(jié)點(diǎn)”。設(shè)編號(hào)為i和j的結(jié)點(diǎn)在順序存儲(chǔ)中的下標(biāo)為、和?，則結(jié)點(diǎn)I和j在同一層上的條件是llogiS-=llog；lo.在一棵m階B-樹(shù)中，若在某結(jié)點(diǎn)中插入一個(gè)新關(guān)鍵字而引起該結(jié)點(diǎn)分裂?則此結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是 :若在某結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵字而導(dǎo)致結(jié)點(diǎn)合并’則該結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是—o【答案】m-1：「m/21-1【解析】m階B-樹(shù)除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)最多是m-l.最少「m/21-l.從用戶(hù)的觀點(diǎn)看，文件的邏輯結(jié)構(gòu)通?？梢詤^(qū)分為兩類(lèi)：一類(lèi)是如NdBASE中數(shù)據(jù)庫(kù)文件SU樣的文件組織結(jié)構(gòu)，稱(chēng)為 文件:另一種是諸如用各種文字處理軟件編輯成的文本文件，稱(chēng)為 文件。從文件在存儲(chǔ)器上的存放方式來(lái)看，文件的物理結(jié)構(gòu)往往可區(qū)分為三類(lèi)，即 ， 和 B+樹(shù)適用于組織 的索引結(jié)構(gòu)，m階B+樹(shù)每個(gè)結(jié)點(diǎn)至多有 個(gè)兒子，除根結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)至少有 個(gè)兒子，根結(jié)點(diǎn)至少有 個(gè)兒子，有k個(gè)兒子的結(jié)點(diǎn)必有 個(gè)關(guān)鍵碼。【答案】數(shù)據(jù)庫(kù)：文本：順序組織：隨機(jī)組織：鏈組織；隨機(jī)組織：m：Fm/21：2：k.設(shè)正文串長(zhǎng)度為n,模式串長(zhǎng)度為m,則串匹配的KMP算法的時(shí)間復(fù)雜度為 【答案】O(m+n) .執(zhí)行順序查找時(shí)，存儲(chǔ)方式可以 ,折半查找時(shí)’要求線性表 ,分塊查找時(shí)要求線性表 ，而哈希表的查找，要求線性表的存儲(chǔ)方式是 。【答案】JI賄存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)：順序存儲(chǔ)且有序：塊內(nèi)順序存儲(chǔ)，塊間有序：散列存儲(chǔ).在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用 o[答案】方便運(yùn)算.一個(gè)有2001個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度是 ?！敬鸢浮?1【解析】完全二叉樹(shù)的高度H=UogNH三、算法設(shè)計(jì)題.編寫(xiě)算法打印出由指針Hm指向總表頭的以十字鏈表形式存儲(chǔ)的稀疏矩陣中每一行的非零元的個(gè)數(shù)。注意：行、列及總表頭結(jié)點(diǎn)的形式為：row col valdown righi它們已用val域鏈接成循環(huán)鏈表。非零元的結(jié)點(diǎn)形式也同上，每一行(列)的非零元由right(down)域把它們鏈接成循環(huán)鏈表，該行(列)的表頭結(jié)點(diǎn)即為該行(列)循環(huán)鏈表的表頭。【答案】算法如下：intMatrixNum(OlinkHm)//輸出由Hm指向的十字鏈表中每-行的非零元素個(gè)數(shù){Olinkrch=Hm->uval.next,p；intA[];i=l; 〃數(shù)組A記各行非等元個(gè)數(shù)，i記行號(hào)while(rch!-Hni) //循環(huán)完備行列表頭{p=rch->right;num=0;〃p是稀疏矩陣行內(nèi)I.作指針，num記該行非零個(gè)數(shù)while(p!=rch) 〃完成行內(nèi)非零元的査找{printf([%d]=%d",p->rowrp->col,p->uval.e);num++;p=p->right;printf("\nM);//指針后移}A(i++]-num; //存該行非零元個(gè)數(shù)rch=rch->uval.next;//移到下一行列表頭)num*0;for(j=l;j<i；j++) //輸出各行非零元個(gè)數(shù)(num+=A[j];printf(行非零元個(gè)數(shù)為%d\n",j,A[j]);}return(num)；//稀疏矩陣非零元個(gè)數(shù))算法結(jié)束.已知一棵二叉樹(shù)的前序遍歷序列和中序遍歷序列分別存于兩個(gè)一維數(shù)組中,試編寫(xiě)算法建立該二叉樹(shù)的二叉鏈表?！敬鸢浮克惴ㄈ缦拢簐oidPrelnCreat(BiTreeroot,ElemTypepre[Jrin(J,int11,hl,12,h2)〃根據(jù)二叉樹(shù)前序序列pre和中序序列in建立二叉樹(shù)。11.hi和12、h2是兩個(gè)序列首、尾元素下標(biāo)■'(:' ,, II*!?■?->'：.??;〃申請(qǐng)結(jié)點(diǎn)??'-是根m⑵亠= …3rn[i]"pre(E)break;//^中序序列中，根結(jié)點(diǎn)將樹(shù)分成左右子樹(shù)root.->1ch1id=ni;l1:〃無(wú)左子樹(shù)elsePrelnCreat(root~>lchild,pre,in,11+1,11*(i-12),12.i-1):〃遞歸建/r子樹(shù):1<==h?):m-re：.；：d=rr;l1;〃無(wú)右子樹(shù)elsePrelnCreat(root->rchild,pre,in,11+(i-12)+1.hl,i+1,h2) //遞歸建\>/"]子樹(shù)}〃結(jié)束mcreat?設(shè)二叉排序樹(shù)的各元素值均不相同?采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，試分別設(shè)計(jì)遞歸和非遞歸算法按遞減序打印所有左子樹(shù)為空，右子樹(shù)非空的結(jié)點(diǎn)的數(shù)據(jù)域的值?！敬鸢浮?1)遞歸算法如下：voidDecPrint(BSTreet)//遞減序輸出二叉排序樹(shù)t中所有左子樹(shù)為空右子樹(shù)非空的結(jié)點(diǎn)數(shù)據(jù)域的債(if(t){DecPrint(t->rchild);if(!t->lchild&&t->rchild)printf(t->data:4)DecPrint(t->lchild);}//if}//DecPrint(2)非遞歸算法如下：voidDecPrint(BSTreet)//遞減序輸出二叉排序樹(shù)t中所有左子樹(shù)為空、右子樹(shù)非空的結(jié)點(diǎn)的數(shù)據(jù)域的值(BSTreeS[];//S是二叉排序樹(shù)結(jié)點(diǎn)指針的棧，容量足夠大inttop=0;while(t||top>0)(while(t)(S(++top)=t;t=t->rchild;}//沿右分支向下if(top>0)(t=S(top一];if(1t->lchild&&t->rchiId)printf(t->data：4);t?t->lchild;//去左分支}//if}//while}//算法結(jié)束.已知兩個(gè)線性表A,B均以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu)?且表中元素按值遞增有序排列。設(shè)計(jì)算法求出A與B的交集C,要求C另開(kāi)辟存儲(chǔ)空間。，并同樣以元素值的遞增有序的單鏈表形式存儲(chǔ)。【答案】算法如下：LinkedListUnion(LinkedListA,B)//線性表A和B以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)。本算法求A和B的交篥C,C另辟空間(pa=A->next;pb=B->next；//pa.pb是兩鏈表的匸作指針pc?C=(LinkedList)maloc(sizeof(LNode));pc->data=MaxElemType//監(jiān)視哨while(pa&&pb)if(pa->data<pb->data)pa=pa->next; //pa指針后移elseif(pa->data>pb->data)pb=pb->next；//pb指針后移else 〃處理交集元素if(pc->data=s=pa->data)(pa=pa->next;pb=pb->next；}//刪除咬気元素else{p=(LinkedList)maLoc(sizeof<LNode));p->data=pa->data;pc->next=p；pc=p；pa=pa->next;pb=pb->nextj}〃交集元素井人結(jié)果表pc->next-null;//置結(jié)果鏈表尾returnC;}27.串以靜態(tài)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，結(jié)構(gòu)如下所述，試實(shí)現(xiàn)串操作。quil算法。CONSTmaxlen-niW確認(rèn)的最大R度TYPEStrtp=*RECORDch:ARRAY(1..maxlen]OFchar;curlen:0..maxlenEND；【答案】算法如下：intequal(strtpsrstrtpt)//本算法判斷字符申s和字符串t是否相等，如相等返回1,否則返回。{if(s.curlen!=t.curlen)return(0);for(i-0;i<3.curlen;i++) 〃在類(lèi)C中，一維數(shù)組下標(biāo)從零開(kāi)始if(s.ch[i]!=t.ch[i])return(0);return(1); //兩串相等}//算法結(jié)朿28.已知字符串S1中存放一段英文’寫(xiě)出算法hmai(sl.s2,s3.n),將其按給定的長(zhǎng)度n格式化成兩端對(duì)齊的字符串S2.其多余的字符送S3?！敬鸢浮克惴ㄈ缦拢簐oidformat(char*sl,*s2,*s3)//將字符串s】拆分成字符串g和字符串s3,要求字符串s2長(zhǎng)度為n且兩端對(duì)齊{char*p=sl,*q=s2;intin。；whilst*pl?'\0?&&*p?=?')p++;//濾掉sl左端空格if(*p?=,\0,)(printf(-$符串sl為空串或空格串\n");exit(0)?}while(*p!?*\0,&&i<n){*q=*p;q++;p++； 宇符軍sl向字符串s2中復(fù)制if(*p"，\0)(printf(Mt:符串sl沒(méi)有個(gè)有效字符\n-,n);exit(0);}if(*(—q)-=(?)〃若最后一個(gè)字符為空格，則需向后找到第一個(gè)非空格『符{P—； 〃P指針也后退while(*p=。&&*p!=?\0?)p++；//往后査找一個(gè)非空格字符作為串s2的尾字符if(*p—*\0)(printf("sl串沒(méi)有*d個(gè)兩端對(duì)齊的字符串exit(0);)*q-*P； 〃字符串s2最后一個(gè)非空字符、iq)i\0,； //Ws2T符串結(jié)斐標(biāo)記}*q=s3;pi; 〃將sl串其余部分送字符串S3while(*pl=,\0,)(*q=*p；q++；p++;}/置串S3結(jié)束標(biāo)記29.給定(已生成)一個(gè)帶表頭結(jié)點(diǎn)的單鏈表,設(shè)head為頭指針,結(jié)點(diǎn)的結(jié)構(gòu)為(data,next).data為整型元素?next為指針’試寫(xiě)出算法：按遞増次序輸出單鏈表中各結(jié)點(diǎn)的數(shù)據(jù)元素?并釋放結(jié)點(diǎn)所占的存儲(chǔ)空間(要求：不允許使用數(shù)組作輔助空間X【答案】算法如下：voidMiniDelete(LinkedListhead)//head是帶頭結(jié)點(diǎn)的單鏈表的頭指針//本算法按遞增順序輸出單鏈表各結(jié)點(diǎn)的值，并釋放結(jié)點(diǎn)所占的存儲(chǔ)空間{while(head->next!=null)//循環(huán)到僅剩頭結(jié)點(diǎn)(pre=head;r=pre; //pre為元素最小值結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針p=?pre->next; 〃p為工作指針while(pisnull)(if(p->data<pre->next->data)pre^r; //記住當(dāng)前最小值結(jié)點(diǎn)的前驅(qū)r=p;p=p->next;}printf(pre->next->data); //輸出元素最小値結(jié)點(diǎn)的數(shù)據(jù)u=pre->next;pre->next=u->next;free(u);//刪除元素值最小的結(jié)點(diǎn)，耗放結(jié)點(diǎn)空間}//while(head->next1=null)free(head);} //軽放頭結(jié)點(diǎn)30.已知L為沒(méi)有頭結(jié)點(diǎn)的的單鏈表中第一個(gè)結(jié)點(diǎn)的指針，每個(gè)結(jié)點(diǎn)數(shù)據(jù)域存放一個(gè)字符，該字符可能是英文字母字符、數(shù)字字符或其他字符，編寫(xiě)算法構(gòu)造三個(gè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類(lèi)字符(要求用最少的時(shí)間和最少的空間X【答案】算法如下：voidOneToThree(LinkedListL,la,Idrlo)L是不帶頭結(jié)點(diǎn)的單鏈表第?個(gè)結(jié)點(diǎn)的指針，鏈表中的數(shù)據(jù)域存放宇符//本算法啊鏈表L分解成含有英攵字母字符.數(shù)字字符和其他字符的帶頭結(jié)點(diǎn)的個(gè)循環(huán)犠彳

(la=(LinkedList)malloc(sizeof(LNode)); //建立三個(gè)犠表的頭結(jié)點(diǎn).Ld=(LinkedList)malloc(sizeof(LNode));lo?(LinkedList)malloc(sizeof(LNode));la->next=la;ld->next=ld;lo->next=lo; //置三個(gè)循壞鏈?友為空表while(Ll-null) //分解原鏈表{r-L;L=L->next;//L指向待處理結(jié)疙的后繼if &飛&r->^ata<=*z,\\r->daxa>='A'&&r->data<=1z'(r->next=la~>next;la->next=r:} 〃處理字母字符elsexf(r->cfata>?0'r->data<-9'){r->next=?ld->next;ld->next=r;} //處理數(shù)字字符else(r->next=lo->next;lo->next3sr;} //處理K他符號(hào)}//結(jié)束while(LI^null)}〃算法結(jié)束四、應(yīng)用題

31.(1)對(duì)于有向無(wú)環(huán)圖’敘述求拓?fù)溆行蛐蛄械牟襟E;(2)對(duì)于圖1,寫(xiě)出它的四個(gè)不同的拓?fù)溆行蛐蛄??！敬鸢浮?1)對(duì)有向圖，求拓?fù)湫蛄胁襟E為：1)在有向圖中選一個(gè)沒(méi)有前驅(qū)(即入度為0)的頂點(diǎn)并輸出。在圖中刪除該頂點(diǎn)及所有以它為尾的弧。重復(fù)1)和2),直至全部頂點(diǎn)輸出，這時(shí)拓?fù)渑判蛲瓿桑悍駝t，圖中存在環(huán)，拓?fù)渑判蚴　?2.調(diào)用下列C函數(shù)f(n).回答下列問(wèn)題：(1)試指出f(n)值的大小，并寫(xiě)出，f(n)值的推導(dǎo)過(guò)程；(2)假定n=5,試指出，f(5)值的大洲口執(zhí)行，f(5)時(shí)的輸出結(jié)果。C函數(shù)：intf(inin)(inti.j.k,silm=O：for(i=l：i<n+l：i++){for(j=n：j>i-l：j~)for(k=l：k<j+l：k++)sum++： printf("sum=%d\n”，sum)：return(sum)：I【答案】(1)第一層FOR循環(huán)判斷n+1次，往下執(zhí)行n次，第二層FOR執(zhí)行次數(shù)為(n+(n-1)+(n-2)+...+1),第三層循環(huán)體受第一層循環(huán)和第二層循環(huán)的控制，其執(zhí)行次數(shù)如表所小。表執(zhí)行次數(shù)i=1 2 3 … ni=fin n n ??? nTOC\o"1-5"\h\zj=n—I n-1 n-1 n—\j=3 333J=2 2 2J=1 1執(zhí)行次數(shù)為f(n)=(1+2+...+,n)+(2+3+...+,n)+...+n=n*n(n+1)/2-n(n2-l)/6。(2)在n=5對(duì)，f(5)=55,執(zhí)行過(guò)程中，輸岀結(jié)果為：sum=l5sum=29sum=41sum=50sum=5533.三維數(shù)組.巡..10.-2..6?2..81的每個(gè)元素的長(zhǎng)度為4個(gè)字節(jié)，試問(wèn)該數(shù)組要占多少個(gè)字節(jié)的存儲(chǔ)空間?如果數(shù)組元素以行優(yōu)先的順序存儲(chǔ)，設(shè)第一個(gè)元素的首地址是100,試求元素A[5,0.郴存儲(chǔ)首地址?！敬鸢浮繑?shù)組占的存儲(chǔ)字節(jié)數(shù)=10*9*7*4=2520；A[5,0,7]的存儲(chǔ)地址=100+14*9*7+2*7+5)*4=118434.假設(shè)利用邊界標(biāo)識(shí)法，并以首次擬合策略分配，己知在某個(gè)時(shí)刻可利用空間表的狀態(tài)如圖所示(注：存儲(chǔ)塊頭部s認(rèn)域的值和申請(qǐng)分配的存儲(chǔ)量均包括頭部和尾部的存儲(chǔ)空間)請(qǐng)畫(huà)出： 213 462 (1)當(dāng)系統(tǒng)回收f(shuō)起始地址為559,大小為45的空閑塊之后的鏈表狀態(tài)；(2)系統(tǒng)繼而在接受存儲(chǔ)塊大小為100的請(qǐng)求后，又回收始地址為515,大小為44的空閑塊之后的鏈表狀態(tài)。[答案】(1)系統(tǒng)回收f(shuō)起始地址為559,大小為45的空閑塊后，因右側(cè)起始地址604為空閑塊，應(yīng)與之合并。合并后，成為起始地址為559,大小為167的空閑塊。鏈表狀態(tài)如圖1所示：/s(2)系統(tǒng)在接受存儲(chǔ)塊大小為100的請(qǐng)求后，將大小為117的空閑塊分出100給予用戶(hù)。在回收一個(gè)起始地址為515,大小為44的空閑塊之后，因左側(cè)起始地址為462、大小為53和右側(cè)起始地址為559、大小為167均為空閑塊，應(yīng)與之合并。合并后，起始地址為462、大小為264的空閑塊。鏈表狀態(tài)如圖2所示：35.分析ISAM文件(IndexedSequentialAccessMethord)和VSAM文件(VirtualstorageAccessMethord)的應(yīng)用場(chǎng)合、優(yōu)缺點(diǎn)等?！敬鸢浮縄SAM是一種專(zhuān)為磁盤(pán)存取設(shè)計(jì)的文件組織形式,采用靜態(tài)索引結(jié)構(gòu),對(duì)磁盤(pán)上的數(shù)據(jù)文件建立盤(pán)組、柱面、磁道三級(jí)索引OISAM文件中記錄按關(guān)鍵字順序存放，插入記錄時(shí)需移動(dòng)記錄并將同一磁道上最后的f記錄移至溢出區(qū)，同時(shí)修改磁道索引項(xiàng)’刪除記錄只需在存儲(chǔ)位置作標(biāo)記,不需移動(dòng)記錄和修改指針。經(jīng)過(guò)多次插入和刪除記錄后’文件結(jié)構(gòu)變得不合理,需周期整理ISAM文件。VSAM文件采用B+動(dòng)態(tài)索引結(jié)構(gòu)’文件只有控制區(qū)間和控制區(qū)域等邏輯存儲(chǔ)單位,與外存儲(chǔ)器中柱面、磁道等具體存儲(chǔ)單位沒(méi)有必然聯(lián)系。VSAM文件結(jié)構(gòu)包括索引集、順序集和數(shù)據(jù)集三部分，記錄存于數(shù)據(jù)集中’順序集和索引集構(gòu)成B+樹(shù),作為文件的索引部分可實(shí)現(xiàn)順鏈查搠口從根結(jié)點(diǎn)開(kāi)始的隨機(jī)査找。優(yōu)缺點(diǎn)：與ISAM文件相比，VSAM文件有如下優(yōu)點(diǎn)：動(dòng)態(tài)分配和釋放存儲(chǔ)空間，不需對(duì)文件進(jìn)行重組：能保持較高的查找效率，且查找先后插入記錄所需時(shí)間相同。因此，基于B+的VSAM文件通常作為大型索引III贍文件的標(biāo)準(zhǔn)組織。36.已知一個(gè)整數(shù)序列人=(%q……J)'其中0《q<〃(0GG).若存在*="=……%=X且m>n/2^<.pt51”5)，則稱(chēng)x為A的主元素。例如A=(0.5,535,7.5.5).則稱(chēng)5為主元素：又如A=(0.5,5,3.5.L5.7)則A中沒(méi)有主元素。假設(shè)A中的n個(gè)元素保存在一個(gè)一維數(shù)組中’請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素：否則輸出-1。要求：(1)給出算法的基本設(shè)計(jì)思想。根據(jù)設(shè)計(jì)思想，采用C或C++或刼a語(yǔ)言描述算法，關(guān)鍵之處給出注釋。說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。【答案】(1)算法的策略是從前向后掃描數(shù)組元素，標(biāo)記出一個(gè)可能成為主元素的元素Num。然后重新計(jì)數(shù)，確認(rèn)Num是否是主元素。算法可分為以下兩步：選取候選的主元素：依次掃描所給數(shù)組中的每個(gè)整數(shù)，將第一個(gè)遇到的整數(shù)Num保存到c中，記錄Num的出現(xiàn)次數(shù)為1;若遇到的下f整數(shù)仍等于Num,則計(jì)數(shù)加1否則計(jì)數(shù)減1;當(dāng)計(jì)數(shù)減到0時(shí)，將遇到的下一個(gè)整數(shù)保存到c中，計(jì)數(shù)重新記為1,開(kāi)始新一輪計(jì)數(shù)，即從當(dāng)前位置開(kāi)始重復(fù)上述過(guò)程，直到掃描完全部數(shù)組元素。判斷c中元素是否是真正的主元素，再次掃描該數(shù)組,統(tǒng)計(jì)c中元素出現(xiàn)的次數(shù),若大于n/2.則為主元素：否則，序列中不存在主元素。(2)算法實(shí)現(xiàn)如下：intMajority(intA[],inln){imi.c.count=I;//c用來(lái)保存候選主元素，Count用來(lái)計(jì)數(shù)c=A[0]; 〃設(shè)置A[0]為候選主元素for(i=l:i<n;i++)(〃查找候選主元素if(A[i]==c)count++: 〃為A中的候選主元素計(jì)數(shù)eles{if(count>0) 〃處理不是候選主元素的情況count—;〃更換候選主元素eise{〃更換候選主元素c=A[i];count=l：}I}if(count>0)foru=count=0;i<n:i++){ 〃統(tǒng)計(jì)候選主元素的實(shí)際出現(xiàn)次數(shù)if(A[i]==e)COUHI++；)if(count>iV2) 〃確認(rèn)候選主元素returnc;elsereturn-1： //不主元素(3)時(shí)間復(fù)雜度為0(n),空間復(fù)雜度為0(112017年山西財(cái)經(jīng)大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)814數(shù)據(jù)結(jié)構(gòu)考研題庫(kù)（三）說(shuō)明：①本資料為VIP包過(guò)學(xué)員內(nèi)部使用資料。涵蓋了歷年考研常考題型和重點(diǎn)題型。一、選擇題TOC\o"1-5"\h\z1-在子網(wǎng)192.16840/30中，能接收目的地址為的IP分組的最大主機(jī)數(shù)是（ \0124【答案】C【解析】每個(gè)子網(wǎng)中忽略子網(wǎng)內(nèi)全為0和全為1的地址剩下的就是有效主機(jī)地址，本題中由于子網(wǎng)的比特?cái)?shù)是30,因此用于主機(jī)的只有2位，即00,01.10,11,有效主機(jī)地址是2個(gè)，這里192.16843顯然是其廣播地址，因此答案是C。TOC\o"1-5"\h\z\o"CurrentDocument"2.數(shù)據(jù)鏈路層采用后退N幀（GBN）協(xié)議’發(fā)送方已經(jīng)發(fā)送了編號(hào)為0-7的傾。當(dāng)計(jì)時(shí)器超時(shí)，若發(fā)送方只收到0、2、3號(hào)幀的確認(rèn)，則發(fā)送方需要重發(fā)的幀數(shù)是（ XA.2345【答案】C【解析】后退N幀協(xié)議，即GO-BACK-N策略的基本原理是，當(dāng)接收方檢測(cè)出失序的信息幀后，要求發(fā)送方重發(fā)最后f正確接收的信息幀之后的所有未被確認(rèn)的幀；或者當(dāng)發(fā)送方發(fā)送了N個(gè)幀后，若發(fā)現(xiàn)該N幀的前一個(gè)幀在計(jì)時(shí)器超時(shí)后仍未返回其確認(rèn)信息，則該幀被判為出錯(cuò)或丟失，此時(shí)發(fā)送方就不得不重新發(fā)送岀錯(cuò)幀及其后的N幀。本題收到3號(hào)幀的確認(rèn)，說(shuō)明0,1.2,3號(hào)幀已經(jīng)收到，丟失的是4,5,6,7號(hào)幀,共4幀。因此答案為C項(xiàng)。3.在文件的索引節(jié)點(diǎn)中存放直接索引指針10個(gè),一級(jí)二級(jí)索引指針各1個(gè)磁盤(pán)塊大小為IKBO每個(gè)索引指針占4個(gè)字節(jié)。若某個(gè)文件的索引節(jié)點(diǎn)已在內(nèi)存中’到把該文件的偏移量（按字節(jié)編址）為1234和307400處所在的磁盤(pán)塊讀入內(nèi)存。需訪問(wèn)的磁盤(pán)塊個(gè)數(shù)分別是（ 123342334LL22A.B.CD.【答案】B【解析】文件的索引結(jié)點(diǎn)的直接索引指針有10個(gè)，因此直接索弓I的偏移量范圍是0-2559.-級(jí)索引的偏移量范圍是2560?65791，二級(jí)索弓|訪問(wèn)的偏移量范圍是65792?45183907偏移量1234可以通過(guò)直接索引得到在磁盤(pán)塊的地址，因此需要一次訪問(wèn)，307400需要通過(guò)二級(jí)索引查找其在磁盤(pán)的位置，需要分別訪問(wèn)存放二級(jí)索引的兩個(gè)索引塊以及對(duì)應(yīng)的數(shù)據(jù)塊。

4.在下圖所示的采用“存儲(chǔ)一轉(zhuǎn)發(fā)”方式的分組交換網(wǎng)絡(luò)中,所有鏈路的數(shù)據(jù)傳輸速率為100Mbps分組大小為1000B,其中分組頭大小20B,若主機(jī)H1向主機(jī)H2發(fā)送一個(gè)大小為980000B的文件，則在不考慮分組拆裝時(shí)間和傳播延遲的情況下，從H1發(fā)送開(kāi)始到H2接收完為止，需要的時(shí)間至少是( 1H2A.80ms80.08ms80.16msD.80.24ms【答案】c【解析】由題設(shè)可知，分組攜帶的數(shù)據(jù)長(zhǎng)度為980B,文件長(zhǎng)度為980000B,需拆分為1000個(gè)分組，加上頭部后，每個(gè)分組大小為［000B,總共需要傳送的數(shù)據(jù)量大小為1MB。由于所有鏈路的數(shù)據(jù)傳輸速度相同，因此文件傳輸經(jīng)過(guò)最短路徑時(shí)所需時(shí)間最少，最短路徑經(jīng)過(guò)分組交換機(jī)。當(dāng)t=1Mx8/100Mbps=80ms時(shí)，HI發(fā)送完最后f比特；到達(dá)目的地，最后f分組,需經(jīng)過(guò)兩個(gè)分組交換機(jī)的轉(zhuǎn)發(fā)，每次轉(zhuǎn)發(fā)的時(shí)間為V.=IKx8/IOOMbps=0.08ms.所以，在不考慮分組拆裝時(shí)間和傳播延時(shí)的情況下’當(dāng)t=8Oms+2to=8O.16ms時(shí)，H2接受完文件,即所需的時(shí)間至少為80.16msTOC\o"1-5"\h\z\o"CurrentDocument"5.已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18,將其再調(diào)整為大根堆，調(diào)整過(guò)程中元素之間進(jìn)行的比較次數(shù)是( X1245【答案】B［解析】對(duì)堆插入或刪除一個(gè)元素，有可能不滿(mǎn)足堆的性質(zhì)，堆被破壞，需要調(diào)整為新堆。(1)為原堆’為插入18后，比較10與18,交換后,(4)比較25與18,不交換，即為調(diào)整后的新的大根堆。因此調(diào)整過(guò)程中元素之間進(jìn)行的比較次數(shù)為2。13251013122510181325101312251018采用開(kāi)址定址法解決沖突的哈希查找中，發(fā)生集聚的原因主要是（ X螭元素過(guò)多負(fù)載因子過(guò)大哈希函數(shù)選擇不當(dāng)D解決沖突的算法選擇不好【答案】D［解析］開(kāi)放定址法就是從發(fā)生沖突的那個(gè)單元開(kāi)始，按照一定的次序，從散列表中查找出一個(gè)空閑的存儲(chǔ)單元，把發(fā)生沖突的待插入元素存入到該單元中的一類(lèi)處理沖突的方法。主機(jī)甲與乙之間已建立一個(gè)TCP連接’雙方持續(xù)有數(shù)據(jù)傳輸’且無(wú)差錯(cuò)與丟失。若甲收到1個(gè)來(lái)自乙的TCP段，該段的序號(hào)為1913、確認(rèn)序號(hào)為2046、有效載荷為100字節(jié)，則甲立即發(fā)送給乙的TCP段的序號(hào)和確認(rèn)分別是（ ）A.2046、20122046、20132047、20122047、2012【答案］B【解析】若甲收到1個(gè)來(lái)自乙的TCP段，該段的序號(hào)seq=1913、確認(rèn)序號(hào)ack=2046、有效載荷為100字節(jié)，則甲立即發(fā)送給乙的TCP段的序號(hào)seql=a^=2046和確認(rèn)序號(hào)亦1=seq+100=2013,答案為B。8.在有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)中，頂點(diǎn)V在鏈表中出現(xiàn)的次數(shù)是（ 1A.頂點(diǎn)V的度B.頂點(diǎn)V的出度C.頂點(diǎn)V的入度D.依附于頂點(diǎn)V的邊數(shù)【答案】B【解析】在有向圖中’第j個(gè)鏈表中的結(jié)點(diǎn)個(gè)數(shù)只是頂點(diǎn)Vi的出度,為求入度,必須遍歷整個(gè)鄰接表。因此頂點(diǎn)V在鏈表中出現(xiàn)的次數(shù)是頂點(diǎn)V的出度。9.用戶(hù)在刪除某文件的過(guò)程中，操作系統(tǒng)不可能執(zhí)行是（ ）刪除此文件所在的目錄刪除與此文件關(guān)聯(lián)的目錄項(xiàng)C刪除與此文件對(duì)應(yīng)的控制塊釋放與此文件關(guān)聯(lián)的內(nèi)存級(jí)沖區(qū)【答案】A［解析】刪除文件不需要?jiǎng)h除文件所在的目錄，而文件的關(guān)聯(lián)目錄項(xiàng)和文件控制塊需要隨著文件一同刪除，同時(shí)釋放文件的關(guān)聯(lián)緩沖區(qū)。10.下列關(guān)于無(wú)向連通圖特性的敘述中?正確的是（所有的頂點(diǎn)的度之和為偶數(shù)邊數(shù)大于頂點(diǎn)個(gè)數(shù)減［至少有一個(gè)頂點(diǎn)的度為1只有I只有III和III和III【答案】A【解析】在圖中，頂點(diǎn)的度TD（K）之和與邊的數(shù)目滿(mǎn)足關(guān)系式：去如化）業(yè)（n為圖的總結(jié)點(diǎn)數(shù)，e為總邊數(shù)'因此，I項(xiàng)正確。對(duì)于II、III項(xiàng)中的特性不是一般無(wú)向連通圖的特性，可以輕松地舉出反例至少有一個(gè)頂點(diǎn)的度為1”的反例如下圖（1）所示，“邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1"的反例如下圖（2）所示。⑴(2)

圖11-n個(gè)頂點(diǎn)的無(wú)向圖的鄰接表最多有（ ）個(gè)表結(jié)點(diǎn)。A.ITB.n（n-l）C.n（n+l）D.n（n-l）/2【答案】B［解析】當(dāng)n個(gè)頂點(diǎn)構(gòu)成的無(wú)向圖是無(wú)向完全圖時(shí)，則每一個(gè)結(jié)點(diǎn)都會(huì)和其余的n-1個(gè)結(jié)點(diǎn) 連接，從而會(huì)產(chǎn)生n（n-l）個(gè)表結(jié)點(diǎn)。下面關(guān)于B和B+樹(shù)的敘述中，不正確的是（ ）B樹(shù)和B+樹(shù)都是平衡的多叉樹(shù)B樹(shù)和B+樹(shù)都可用于文件的索引結(jié)構(gòu)B樹(shù)和B+樹(shù)都能有效地支持解檢索B樹(shù)和B+樹(shù)都能有效地支持隨機(jī)檢索【答案】C[解析】B樹(shù)是一種平衡的多分樹(shù)，通常我們說(shuō)m階的B樹(shù)，它必須滿(mǎn)足如下條件：①每個(gè)結(jié)點(diǎn)至多有m個(gè)子結(jié)點(diǎn)；②除根結(jié)點(diǎn)和葉結(jié)點(diǎn)夕卜其它每個(gè)結(jié)點(diǎn)至少有個(gè)子結(jié)點(diǎn)；③若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩個(gè)子結(jié)點(diǎn)：④所有的葉結(jié)點(diǎn)在同一層：⑤有k個(gè)子結(jié)點(diǎn)的非根結(jié)點(diǎn)恰好包含k-1個(gè)關(guān)鍵碼。B+樹(shù)是B樹(shù)的一