數(shù)據(jù)結(jié)構(gòu)試題(含答案)

數(shù)據(jù)結(jié)構(gòu)試題(含答案)數(shù)據(jù)結(jié)構(gòu)試題(含答案)數(shù)據(jù)結(jié)構(gòu)試題(含答案)數(shù)據(jù)結(jié)構(gòu)試題(含答案)編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:數(shù)據(jù)結(jié)構(gòu)試題單選題在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為（C）A內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)B靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu)C線性結(jié)構(gòu)與非線性結(jié)構(gòu)D緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)。2、采用線性鏈表表示一個(gè)向量時(shí)，要求占用的存儲(chǔ)空間地址（D）A必須是連續(xù)的 B部分地址必須是連續(xù)的C一定是不連續(xù)的 D可連續(xù)可不連續(xù)3、采用順序搜索方法查找長度為n的順序表時(shí)，搜索成功的平均搜索長度為（D）。An Bn/2 C(n-1)/2 D(n+1)/24、在一個(gè)單鏈表中，若q結(jié)點(diǎn)是p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q與p之間插入結(jié)點(diǎn)s，則執(zhí)行（D）。As→link=p→link;p→link=s; Bp→link=s;s→link=q;Cp→link=s→link;s→link=p; Dq→link=s;s→link=p;5、如果想在4092個(gè)數(shù)據(jù)中只需要選擇其中最小的5個(gè)，采用（C）方法最好。A起泡排序 B堆排序 C錦標(biāo)賽排序 D快速排序6、設(shè)有兩個(gè)串t和p，求p在t中首次出現(xiàn)的位置的運(yùn)算叫做（B）。A求子串 B模式匹配 C串替換 D串連接7、在數(shù)組A中，每一個(gè)數(shù)組元素A[i][j]占用3個(gè)存儲(chǔ)字，行下標(biāo)i從1到8，列下標(biāo)j從1到10。所有數(shù)組元素相繼存放于一個(gè)連續(xù)的存儲(chǔ)空間中，則存放該數(shù)組至少需要的存儲(chǔ)字?jǐn)?shù)是（C）。A80 B100 C240 D2708、將一個(gè)遞歸算法改為對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用（A）。A棧 B隊(duì)列 C循環(huán)隊(duì)列 D優(yōu)先隊(duì)列9、一個(gè)隊(duì)列的進(jìn)隊(duì)列順序是1,2,3,4，則出隊(duì)列順序?yàn)椋–）。10、在循環(huán)隊(duì)列中用數(shù)組A[0..m-1]存放隊(duì)列元素，其隊(duì)頭和隊(duì)尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（D）。A(front-rear+1)%m B(rear-front+1)%mC(front-rear+m)%m D(rear-front+m)%m11、一個(gè)數(shù)組元素a[i]與（A）的表示等價(jià)。A*（a+i） Ba+i C*a+i D&a+i12、若需要利用形參直接訪問實(shí)參，則應(yīng)把形參變量說明為（B）參數(shù)。A指針 B 引用 C值 D變量13、下面程序段的時(shí)間復(fù)雜度為（C）for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;AO(m2) BO(n2) CO(m*n) DO(m+n)14、下面程序段的時(shí)間復(fù)雜度為（B）intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}AO(1) BO(n) CO(n2) DO(n!)15、線性表若是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址(D)。A必須是連續(xù)的B

部分地址必須是連續(xù)的C一定是不連續(xù)的D

連續(xù)或不連續(xù)都可以16、數(shù)據(jù)結(jié)構(gòu)的定義為(D，S)，其中D是(B)的集合。A算法B數(shù)據(jù)元素C數(shù)據(jù)操作D邏輯結(jié)構(gòu)17、算法分析的目的是(A)。A

找出數(shù)據(jù)結(jié)構(gòu)的合理性B

研究算法中輸入和輸出的關(guān)系C

分析算法的效率以求改進(jìn)D

分析算法的易懂性和文檔性18、在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行(B)。As->link=p;p->link=s; Bs->link=p->link;p->link=s;Cs->link=p->link;p=s; Dp->link=s;s->link=p;19、設(shè)單鏈表中結(jié)點(diǎn)結(jié)構(gòu)為(data,link).已知指針q所指結(jié)點(diǎn)是指針p所指結(jié)點(diǎn)的直接前驅(qū)，若在*q

與*p之間插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個(gè)操作（B）As->link=p->link;p->link=s; Bq->link=s;s->link=pCp->link=s->link; s->link=p; Dp->link=s;s->link=q;20、設(shè)單鏈表中結(jié)點(diǎn)結(jié)構(gòu)為(data,link).若想摘除結(jié)點(diǎn)*p的直接后繼，則應(yīng)執(zhí)行下列哪一個(gè)操作（A）Ap->link=p->link->link; Bp=p->link;p->link=p->link->link;Cp->link=p->link; Dp=p->link->link;21、設(shè)單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link）,且rear是指向非空的帶表頭結(jié)點(diǎn)的單循環(huán)鏈表的尾結(jié)點(diǎn)的指針。若想刪除鏈表第一個(gè)結(jié)點(diǎn)，則應(yīng)執(zhí)行下列哪一個(gè)操作（D）As=rear;rear=rear->link;deletes;Brear=rear->link;deleterear; Crear=rear->link->link;deleterear; Ds=rear->link->link;rear->link->link=s->link;deletes;22、設(shè)單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link）,且first為指向鏈表表頭的指針，current為鏈表當(dāng)前指針，在循環(huán)鏈表中檢測(cè)current是否達(dá)到鏈表表尾的語句是(D)。Acurrent->link=nullBfirst->link=currentCfirst=currentDcurrent->link=first23、一個(gè)棧的入棧序列為a，b，c，則出棧序列不可能的是(C)。A

c,b,aBb,a,cCc,a,bDa,c,b24、棧的數(shù)組表示中，top為棧頂指針，棧空的條件是(A)。A

top=0Btop=maxSizeC

top=maxSizeDtop=-125、棧和隊(duì)列的共同特點(diǎn)是(C)。A

都是先進(jìn)后出B都是先進(jìn)先出C

只允許在端點(diǎn)處插入和刪除D沒有共同點(diǎn)26、假定一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針分別為f和r,則判斷隊(duì)空的條件為(D).Af+1==r Br+1==f Cf==0 Df==r27、當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長度為（B）An-2 Bn-1 Cn Dn+128、當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==n表示?？眨瑒t向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行（）語句修改top指針。Atop++; Btop--; Ctop=0; Dtop;29、設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為（data,link）,且top是指向棧頂?shù)闹羔?。若想摘除鏈?zhǔn)綏５臈ｍ斀Y(jié)點(diǎn)，并將被摘除結(jié)點(diǎn)的值保存到x中，則應(yīng)執(zhí)行下列（A）操作。Ax=top->data;top=top->link; Btop=top->link;x=top->data;Cx=top;top=top->link; Dx=top->data;30、設(shè)循環(huán)隊(duì)列的結(jié)構(gòu)是：constintMaxsize=100;typedefintDataType;typedefstruct{DataTypedata[Maxsize];Intfront,rear;}Queue;若有一個(gè)Queue類型的隊(duì)列Q，試問判斷隊(duì)列滿的條件應(yīng)是下列哪一個(gè)語句（D）A ==; B-==Maxsize; C+==Maxsize; D ==+1)%Maxsize;31、設(shè)有一個(gè)遞歸算法如下：intfact(intn){if(n<=0)return1;elsereturnn*fact(n-1);}下面正確的敘述是（B）A計(jì)算fact(n)需要執(zhí)行n次遞歸Bfact(7)=5040 C此遞歸算法最多只能計(jì)算到fact(8)D以上結(jié)論都不對(duì)32、設(shè)有一個(gè)遞歸算法如下intx(intn){if(n<=3)return1;elsereturnx(n-2)+x(n-4)+1;}試問計(jì)算x(x(8))時(shí)需要計(jì)算（D）次x函數(shù)。A8次 B 9 次C16 次 D18次33、設(shè)有廣義表D(a,b,D),其長度為（B），深度為（A）A∞ B3 C2 D534、廣義表A(a),則表尾為（C）Aa B(()) C 空表 D（a）35、下列廣義表是線性表的有（C）AE（a,(b,c)） BE(a,E) CE(a,b) DE(a,L())36、遞歸表、再入表、純表、線性表之間的關(guān)系為（C）A再入表>遞歸表>純表>線性表 B遞歸表>線性表>再入表>純表 C遞歸表>再入表>純表>線性表 D遞歸表>再入表>線性表>純表37、某二叉樹的前序和后序序列正好相反，則該二叉樹一定是（B）的二叉樹。A空或只有一個(gè)結(jié)點(diǎn)B高度等于其結(jié)點(diǎn)數(shù)C任一結(jié)點(diǎn)無左孩子D任一結(jié)點(diǎn)無右孩子38、對(duì)于任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)為n2.,則(A)An0=n2+1Bn2=n0+1Cn0=2n2+1Dn2=2n0+139、由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（B）A24B73C48D5340、已知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)需占m個(gè)存儲(chǔ)單元，若第一個(gè)結(jié)點(diǎn)的地址為da1,則第I個(gè)結(jié)點(diǎn)的地址為（A）。Ada1+(I-1)*mBda1+I*mCda1-I*mDda1+(I+1)*m41、34具有35個(gè)結(jié)點(diǎn)的完全二叉樹的深度為(A)A5B6C7D842、對(duì)線性表進(jìn)行折半搜索時(shí)，要求線性表必須（C）A以鏈接方式存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵碼有序排列 B以數(shù)組方式存儲(chǔ) C以數(shù)組方式存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵碼有序排列 D以鏈接方式存儲(chǔ)43、順序搜索算法適合于存儲(chǔ)結(jié)構(gòu)為（B）的線性表。A散列存儲(chǔ) B順序存儲(chǔ)或鏈接存儲(chǔ) C壓縮存儲(chǔ) D索引存儲(chǔ)44、采用折半搜索算法搜索長度為n的有序表時(shí)，元素的平均搜索長度為（C）AO（n2） B O（nlog2n） CO（log2n） DO（n）45、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，進(jìn)行拓?fù)渑判驎r(shí)，總的時(shí)間為(A)An Bn+1 Cn-1 Dn+e46、判斷一個(gè)有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ㄍ猓€可以利用（C）。A求關(guān)鍵路徑的方法 B求最短路徑的Dijkstra方法 C深度優(yōu)先遍歷算法 D廣度優(yōu)先遍歷算法47、在10階B-樹中根結(jié)點(diǎn)所包含的關(guān)鍵碼個(gè)數(shù)最多為（C），最少為(A)A1 B2 C9 D1048、對(duì)包含n個(gè)元素的散列表進(jìn)行搜索，平均搜索長度為（C）AO（log2n）BO（n） C不直接依賴于n D上述都不對(duì)填空題（）1、

數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)四種

2、

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)四種3、一種抽象數(shù)據(jù)類型包括（數(shù)據(jù)）和（操作）兩個(gè)部分。設(shè)有兩個(gè)串p和q，求p在q中首次出現(xiàn)的位置的運(yùn)算稱為（模式匹配）

棧、隊(duì)列邏輯上都是（線性存儲(chǔ)）結(jié)構(gòu)。線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是（一對(duì)一）的，圖中的數(shù)據(jù)元素之間的關(guān)系是（多對(duì)多）的，樹形結(jié)構(gòu)中數(shù)據(jù)元素間的關(guān)系是（一對(duì)多）的。棧中存取數(shù)據(jù)的原則（后進(jìn)先出），隊(duì)列中存取數(shù)據(jù)的原則（先進(jìn)先出）串是由（零個(gè)或多個(gè)）字符組成的序列。（長度為零的串）稱為空串，（由一個(gè)或多個(gè)空格組成的串）稱為空格串。設(shè)目標(biāo)串T=”abccdcdccbaa”,模式P=”cdcc”則第（6）次匹配成功。10、一維數(shù)組的邏輯結(jié)構(gòu)是（線性結(jié)構(gòu)），存儲(chǔ)結(jié)構(gòu)是（順序存儲(chǔ)表示）。對(duì)于二維數(shù)組，有（行優(yōu)先順序）和（列優(yōu)先順序）兩種不同的存儲(chǔ)方式，對(duì)于一個(gè)二維數(shù)組A[m][n],若采用按行優(yōu)先存放的方式，則任一數(shù)組元素A[i][j]相對(duì)于A[0][0]的地址為（n*i+j）。11、向一個(gè)順序棧插入一個(gè)元素時(shí)，首先使（棧頂指針）后移一個(gè)位置，然后把待插入元素（寫）到這個(gè)位置上。從一個(gè)順序棧刪除元素時(shí)，需要前移一位（棧頂指針）。12、在一個(gè)循環(huán)隊(duì)列Q中，判斷隊(duì)空的條件為（==）,判斷隊(duì)滿的條件為（+1)%MaxSize==）13、對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)之和為（n-1）。14、一棵高度為5的滿二叉樹中的結(jié)點(diǎn)數(shù)為（63）個(gè)，一棵高度為3滿四叉樹中的結(jié)點(diǎn)數(shù)為（85）個(gè)。15、若對(duì)一棵二叉樹從0開始進(jìn)行結(jié)點(diǎn)編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到a[0]中，其余類推，則a[i]元素的左子女結(jié)點(diǎn)為（2*i+1），右子女結(jié)點(diǎn)為（2*i+2），雙親結(jié)點(diǎn)（i>=1

）為（「(i-1)/2┐）.16、在一個(gè)最大堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的（最大值），在一個(gè)最小堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的（最小值）。17、已知具有n個(gè)元素的一維數(shù)組采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占k個(gè)存儲(chǔ)單元，第一個(gè)元素的地址為LOC(a1)，那么，LOC(ai)=LOC(a1)+(i-1)*k。

18、在霍夫曼編碼中，若編碼長度只允許小于等于4,則除掉已對(duì)兩個(gè)字符編碼為0和10外，還可以最多對(duì)（4）個(gè)字符編碼。

19、設(shè)高度為h的空二叉樹的高度為-1，只有一個(gè)結(jié)點(diǎn)的二叉樹的高度為0，若設(shè)二叉樹只有度為2上度為0的結(jié)點(diǎn)，則該二叉樹中所含結(jié)點(diǎn)至少有（2h+1）個(gè)。

20、由一棵二叉樹的前序序列和（中序序列）可唯一確定這棵二叉樹。

21、以折半搜索方法搜索一個(gè)線性表時(shí)，此線性表必須是（順序）存儲(chǔ)的（有序）表。

22、已知完全二叉樹的第8層有8個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)是（68）。若完全二叉樹的第7有10個(gè)葉子結(jié)點(diǎn)，則整個(gè)二叉樹的結(jié)點(diǎn)數(shù)最多是（235）23、對(duì)于折半搜索所對(duì)應(yīng)的判定樹，它既是一棵（二叉搜索樹），又是一棵（理想平衡樹）。24、假定對(duì)長度n=50的有序表進(jìn)行折半搜索，則對(duì)應(yīng)的判定樹高度為（５），判定樹中前５層的結(jié)點(diǎn)數(shù)為（３１），最后一層的結(jié)點(diǎn)數(shù)為（１９）。25、在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（２）倍。在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有（n(n-1)/2）條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有（n(n-1)）條邊。26、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的連通圖，其生成樹中的頂點(diǎn)數(shù)和邊數(shù)分別為（n）和（n-1）。27、設(shè)線性表中元素的類型是實(shí)型，其首地址為1024，則線性表中第6個(gè)元素的存儲(chǔ)位置是(1044)。28、在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選擇（插入排序），若初始數(shù)據(jù)基本反序，則最好選擇（選擇排序）。29、算法是對(duì)特定問題的求解步驟的一種描述，它是（指令）的有限序列，每一條（指令）表示一個(gè)或多個(gè)操作。30、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)肯e條邊的無向圖，進(jìn)行拓樸排序時(shí)，總的進(jìn)間為（n）31、構(gòu)造哈希函數(shù)有三種方法，分別為(平方取中)法、(除留余數(shù))法、(折迭移位)法。32、處理沖突的三種方法，分別為(線性探測(cè))、（隨機(jī)探測(cè)）、（鏈地址法）。33、對(duì)于含有n個(gè)頂點(diǎn)和e條邊的無向連通圖，利用普里姆算法產(chǎn)生的最小生成樹，其時(shí)間復(fù)雜度為（Ｏ（n2））、利用克魯斯卡爾算法產(chǎn)生的最小生成樹，其時(shí)間復(fù)雜度為（Ｏ（elog2e））34、快速排序在平均情況下的時(shí)間復(fù)雜度為（Ｏ（nlog2n）），在最壞情況下的時(shí)間復(fù)雜度為（Ｏ（n2））；快速排序在平均情況下的空間復(fù)雜度為（Ｏ（log2n）），在最壞情況下的空間復(fù)雜度為（Ｏ（n））。35、假定一組記錄的排序碼為（４６，７９，５６，３８，４０，８０），對(duì)其進(jìn)行歸并排序的過程中，第二趟排序后的結(jié)果是（［３８４６５６７９］［４０８０］）36、假定一組記錄的排序碼為（４６，７９，５６，３８，４０，８０），對(duì)其進(jìn)行快速排序的第一次劃分的結(jié)果是（［３８４０］４６［５６７９８０］）。37、一個(gè)結(jié)點(diǎn)的子樹的（個(gè)數(shù)）稱為該結(jié)點(diǎn)的度。度為（零）的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。度不為（零）的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。樹中各結(jié)點(diǎn)度的（最大值）稱為樹的度。38、設(shè)Ki=Kj(1<=i<=n,1<=j<=n,j<>i)且在排序前的序列中Ri領(lǐng)先于Rj(i<j),若排序后的序列中Ri仍領(lǐng)先于Rj，則這種排序方法是（穩(wěn)定的），反之是（不穩(wěn)定的）。40、在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行調(diào)整運(yùn)算的時(shí)間復(fù)雜度為（Ｏ（log2n）），整個(gè)排序過程的時(shí)間復(fù)雜度為（Ｏ（nlog2n））。41、在索引表中，每個(gè)索引項(xiàng)至少包含有（關(guān)鍵碼值）域和（子表地址）域這兩項(xiàng)。42、假定一個(gè)線性表為（”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”）,若按照字符串的第一個(gè)字母進(jìn)行劃分，使得同一個(gè)字母被劃分在一個(gè)子表中，則得到的a,b,c三個(gè)子表的長度分別為（３），（３），（２）。43、對(duì)于包含５０個(gè)關(guān)鍵碼的３階B-樹，其最小高度為（４），最大高度為（５）。44、從一棵B-樹刪除關(guān)鍵碼的過程，若最終引起樹根結(jié)點(diǎn)的合并，則新樹比原樹的高度（減１）45、假定要對(duì)長度n=100的線性表進(jìn)行散列存儲(chǔ)，并采用開散列法處理沖突，則對(duì)于長度m=20的散列表，每個(gè)散列地址的同義詞子表的長度平均為（５）。46、在散列存儲(chǔ)中，裝載因子α又稱為裝載系數(shù)，若用m表示散列表的長度，n表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則α等于（n/m）。47、在有向圖的鄰接矩陣中，第i行中“1”的個(gè)數(shù)是第i個(gè)頂點(diǎn)的（出度），第i列中“1”的個(gè)數(shù)是第i個(gè)頂點(diǎn)的（入度）。在無向圖的鄰接矩陣中，第i行（列）中“1”的個(gè)數(shù)是第i個(gè)頂點(diǎn)的（度），矩陣中“1”的個(gè)數(shù)的一半是圖中的（邊數(shù)）。48、在對(duì)m階B-樹中，每個(gè)非根結(jié)點(diǎn)的關(guān)鍵碼數(shù)最少為（「m/2┐-1）個(gè)，最多為（m-1）個(gè)，其子樹棵數(shù)最少為（「m/2┐），最多為（m）。判斷題數(shù)據(jù)元素是數(shù)據(jù)的最小單位（╳）。數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的(√).數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體（╳）。從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)（√）。線性表的邏輯順序與物理順序總是一致的（╳）。二維數(shù)組是其數(shù)組元素為線性表的線性表（╳）。每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運(yùn)算：插入、刪除、搜索（√）。非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接前驅(qū)元素。（╳）空串與由空格組成的串沒有區(qū)別。（╳）將T在S中首次出現(xiàn)的位置作為T在S中的位置的操作稱為串的模式匹配。（√）深度為h的非空二叉樹的第h層最多有2h-1個(gè)結(jié)點(diǎn)（╳）完全二叉樹就是滿二叉樹。（╳）已知一棵二叉樹的前序序列和中序序列可以唯一地構(gòu)造出該二叉樹。（√）帶權(quán)連通圖的最小生成樹的權(quán)值之和一定小于它的其它生成樹的權(quán)值之和。（√）15、線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也相鄰。（√）若有一個(gè)結(jié)點(diǎn)是二叉樹中某個(gè)子樹的中序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)，則它一定是該子樹的前序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)。（√）任一棵二叉搜索樹的平均搜索時(shí)間都小于用順序搜索法搜索同樣結(jié)點(diǎn)的順序表的平均搜索時(shí)間。（╳）18、最優(yōu)二叉搜索樹一定是平衡的二叉搜索樹。（√）19、AOE網(wǎng)是一種帶權(quán)的無環(huán)連通圖。（√）

20、對(duì)于同一組待輸入的關(guān)鍵碼集合，雖然各關(guān)鍵碼的輸入次序不同，但得到的二叉搜索樹都是相同的（╳）。21、二叉排序樹可以是一棵空樹（√）22、線性表中所有結(jié)點(diǎn)的類型必須相同。（√）23、n個(gè)結(jié)點(diǎn)的有向圖，若它有n(n－1)條邊，則它一定是強(qiáng)連通的。（√）24、任何無環(huán)的有向圖，其結(jié)點(diǎn)都可以排在一個(gè)拓?fù)湫蛄欣铩＃ā蹋?5、隊(duì)列邏輯上是一個(gè)下端口和上端能增加又能減少的線性表（╳）26、二叉樹是樹的一種特殊情況（√）27、用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)（√）。28、鄰接表只能用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無向圖的存儲(chǔ)都適用。（╳）29、連通分量是無向圖中的極小連通子圖。（╳）30、在ＡＯＥ網(wǎng)絡(luò)中一定只有一條關(guān)鍵路徑。（╳）31、關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間。（√）32、平衡二叉樹的左右子樹深度之差的絕對(duì)值不超過1。（√）33、快速排序是對(duì)起泡排序的一種改進(jìn)。(√)34、直接選擇排序穩(wěn)定。（╳）35、堆排序占用的輔助空間很大。（╳）36、在散列法中采取開散列法來解決沖突時(shí)，其裝載因子的取值一定在（０，１）之間。（╳）37、B-樹是一種動(dòng)態(tài)索引結(jié)構(gòu)，它既適用于隨機(jī)搜索，也適用于順序搜索。（╳）38、在散列法中，一個(gè)可用散列函數(shù)必須保證絕對(duì)不產(chǎn)生沖突。（╳）39、任何一個(gè)關(guān)鍵活動(dòng)延遲，那么整個(gè)工程將會(huì)延遲。（√）40、任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成。（╳）四、運(yùn)算應(yīng)用題1、在一個(gè)有n個(gè)元素的順序表的第i個(gè)元素（1in）之前插入一個(gè)新元素時(shí)，需要向后移動(dòng)多少個(gè)元素答案：需要向后移動(dòng)n-i+1個(gè)元素當(dāng)一個(gè)棧的進(jìn)棧序列為1234567時(shí)，可能的出棧序列有多少種6457321是否是合理的出棧序列答案：可能的出棧序列有種，6457321不是合理的出棧序列。簡單（直接）選擇排序是一種穩(wěn)定的排序方法嗎試舉例說明答案：是不穩(wěn)定的排序方法。下面就是不穩(wěn)定的例子。只要能舉出反例即可。{275275*512061}i=1{061275*512275}i=2{061275*512275}i=3{061275*275512}4、設(shè)有序順序表為{10,20,30,40,50,60,70}，采用折半搜索時(shí)，搜索成功的平均搜索長度是多少答案：ASLsucc=(1*1+2*2+3*4)/7=17/75、在結(jié)點(diǎn)個(gè)數(shù)為n(n>1)的各棵樹中，高度最小的樹的高度是多少它有多少個(gè)葉結(jié)點(diǎn)多少個(gè)分支結(jié)點(diǎn)高度最大的樹的高度是多少它有多少個(gè)葉結(jié)點(diǎn)多少個(gè)分支結(jié)點(diǎn)答案：結(jié)點(diǎn)個(gè)數(shù)為n時(shí)，高度最小的樹的高度為1，有2層；它有n-1個(gè)葉結(jié)點(diǎn)，1個(gè)分支結(jié)點(diǎn)；高度最大的樹的高度為n-1,有n層；它有1個(gè)葉結(jié)點(diǎn)，n-1個(gè)分支結(jié)點(diǎn)。6、一棵高度為h的滿k叉樹有如下性質(zhì):第h層上的結(jié)點(diǎn)都是葉結(jié)點(diǎn),其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹,如果按層次自頂向下,同一層自左向右,順序從1開始對(duì)全部結(jié)點(diǎn)進(jìn)行編號(hào),試問：(1)各層的結(jié)點(diǎn)個(gè)數(shù)是多少 (2)編號(hào)為i的結(jié)點(diǎn)的父結(jié)點(diǎn)(若存在)的編號(hào)是多少 (3)編號(hào)為i的結(jié)點(diǎn)的第m個(gè)孩子結(jié)點(diǎn)(若存在)的編號(hào)是多少 (4)編號(hào)為i的結(jié)點(diǎn)有右兄弟的條件是什么其右兄弟結(jié)點(diǎn)的編號(hào)是多少 (5)若結(jié)點(diǎn)個(gè)數(shù)為n,則高度h是n的什么函數(shù)關(guān)系答案：（1）各層的結(jié)點(diǎn)個(gè)數(shù)是ki(i=0,1,2,....,h)（2）編號(hào)為i的結(jié)點(diǎn)的父結(jié)點(diǎn)(若存在)的編號(hào)是└(i+k-2)/k」（3）編號(hào)為i的結(jié)點(diǎn)的第m個(gè)孩子結(jié)點(diǎn)(若存在)的編號(hào)是(i-1)*k+m+1（4）當(dāng)(i-1)%k<>0時(shí)有右兄弟，右兄弟的編號(hào)為i+1（5）若結(jié)點(diǎn)個(gè)數(shù)為n，則高度h和n的關(guān)系為：h=logk(n*(k-1)+1)-1(n=0時(shí)h=-1)7、寫出下列中綴表達(dá)式的后綴形式： (1)A*-B+C (2)(A+B)*D+E/(F+A*D)+C (3)A&&B||!(E>F) {注：按C++的優(yōu)先級(jí)) (4)!(A&&!((B<C)||(C>D)))||(C<E)答案：各中綴表達(dá)式的后綴形式如下：（1）AB-*C+ (2)AB+D*EFAD*+/+C+(3)AB&&EF>!|| (4)ABC<CD>||!&&!CE<||8、畫出下列廣義表的圖形表示和它們的存儲(chǔ)表示： (1)D(A(c),B(e),C(a,L(b,c,d))) (2)J1(J2(J1,a,J3(J1)),J3(J1))答案：廣義表（1）的圖形表示為： 廣義表（2）的圖形表示為： DABDABCDLceabcdJ1J3J2a廣義表（1）的存儲(chǔ)表示為：0A1C^0A1C^0B1e^AB0D222^0C1a2^0L1b1C1d^CLD廣義表（2）的存儲(chǔ)表示為：0J10J122^0J221a2^0J32^J3J2J19、題目：11、將下面的森林變換成二叉樹（7分）。AACDBFEKJGHIAACDBFEKJGHI答案：10、將算術(shù)表達(dá)式((a+b)+c*(d+e)+f)*(g+h)轉(zhuǎn)化為二叉樹。（7分）答案：*+++f*+++f+*+cbahgde11325476答案：其中的一個(gè)拓?fù)湫蛄袨椋篤1，V2，V3，V4，V5，V6，V712、將給定的圖簡化為最小的生成樹，要求從頂點(diǎn)1出發(fā)。（7分）1313254768515310122796答案: 11325476515362713、某子系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其出現(xiàn)的概率分別為，，，，，，，試設(shè)計(jì)赫夫曼編碼。答案：為方便起見，設(shè)各種字符的權(quán)值w={5,29,7,8,14,23,3,11}。因?yàn)閚=8，所以要構(gòu)造的赫夫曼樹共有m=2n-1=2*8-1=15個(gè)結(jié)點(diǎn)。生成的赫夫曼樹為下圖所示。2323115329147800000001111111赫夫曼編碼為：概率為的字符編碼為：00概率為的字符編碼為：010概率為的字符編碼為：0110概率為的字符編碼為：0111概率為的字符編碼為：10概率為的字符編碼為：110概率為的字符編碼為：1110概率為的字符編碼為：111114、已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ,中序遍歷的結(jié)果是EBCDAFHIGJ,試畫出這棵二叉樹，并給出這棵二叉樹的后序遍歷序列。AABFGECDHJI、答案：根據(jù)前序序列和中序序列能得到唯一的二叉樹，所得二叉樹如圖：這棵二叉樹的后序遍歷序列為：EDCBIHJGFA15、在結(jié)點(diǎn)個(gè)數(shù)為n(n>1)的各棵樹中，高度最小的樹的高度是多少它有多少個(gè)葉結(jié)點(diǎn)多少個(gè)分支結(jié)點(diǎn)高度最大的樹的高度是多少它有多少個(gè)葉結(jié)點(diǎn)多少個(gè)分支結(jié)點(diǎn)答案：結(jié)點(diǎn)個(gè)數(shù)為n時(shí)，高度最小的樹的高度為1，有2層；它有n-1個(gè)葉結(jié)點(diǎn)，1個(gè)分支結(jié)點(diǎn)；高度最大的樹的高度為n-1,有n層；它有1個(gè)葉結(jié)點(diǎn)，n-1個(gè)分支結(jié)點(diǎn)。16、對(duì)于一個(gè)高度為h的AVL樹，其最少結(jié)點(diǎn)數(shù)是多少反之，對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的AVL樹,其最大高度是多少最小高度是多少答案：設(shè)高度為h(空樹的高度為-1)的AVL樹的最少結(jié)點(diǎn)為Nh，則Nh=Fh+3-1。Fh是斐波那契數(shù)。又設(shè)AVL樹有n個(gè)結(jié)點(diǎn)，則其最大高度不超過3/2*log2(n+1),最小高度為「log2(n+1)┐-1。17、7-7設(shè)有序順序表中的元素依次為017,094,154,170,275,503,509,512,553,612,677,765,897,908。試畫出對(duì)其進(jìn)行折半搜索時(shí)的判定樹,并計(jì)算搜索成功的平均搜索長度和搜索不成功的平均搜索長度。509509154677017275170503094553897512612765908答案：折半搜索時(shí)的判定樹為：ASLSUCC=1/14（1+2*2+3*4+4*7）=45/14ASLUNSUCC=1/15（3*1+4*14）=59/1518、試對(duì)下圖所示的AOE網(wǎng)絡(luò)(1)這個(gè)工程最早可能在什么時(shí)間結(jié)束。(2)求每個(gè)事件的最早開始時(shí)間Ve[i]和最遲開始時(shí)間Vl[i]。(3)求每個(gè)活動(dòng)的最早開始時(shí)間e()和最遲開始時(shí)間l()。(4)確定哪些活動(dòng)是關(guān)鍵活動(dòng)。畫出由所有關(guān)鍵活動(dòng)構(gòu)成的圖，指出哪些活動(dòng)加速可使整個(gè)工程提前完成。答案：按拓樸有序的順序計(jì)算各個(gè)頂點(diǎn)的最早可能開始時(shí)間Ve和最遲允許開始時(shí)間Vl，然后再計(jì)算各個(gè)活動(dòng)的最早可能開始時(shí)間e和最遲允許開始時(shí)間l,根據(jù)l-e是否等于0來確定關(guān)鍵活動(dòng)，從而確定關(guān)鍵路徑。①③②④⑤⑥Ve01915293843Vl01915373843<1,2><1,3><3,2><2,4><2,5><3,5><4,6><5,6>e00151919152938L170152719273738l-e1700801280此工程最早完成時(shí)間為43，關(guān)鍵路徑為<1,3><3,2><2,5><5,6>19、已知有五個(gè)待排序的記錄，其關(guān)鍵字分別為：256，301，751，129，937,863，742，694，076，438請(qǐng)用快速排序的方法將它們從小到大排列。答案：第一次排序：（076，129），256，（751，937，863，742，694，301，439）第二次排序：076，129，256，（438，301，694，742），751，（863，937）第三次排序：076，129，256，301，438，（694，742），751，（863，937）第四次排序：076，129，256，301，438，694，742，751，（863，937）第五次排序：076，129，256，301，438，694，742，751，863，93720、設(shè)有150個(gè)記錄要存儲(chǔ)到散列表中,并利用線性探查法解決沖突,要求找到所需記錄的平均比較次數(shù)不超過2次。試問散列表需要設(shè)計(jì)多大(設(shè)是散列表的裝載因子，則有ASLsucc=(1+1/(1-))/2)。答案：已知要存儲(chǔ)的記錄數(shù)為n=150,查找成功的平均查找長度為ASLsucc≤2，則有：ASLsucc=1/2（1+1/（1-））≤2解得≤2/3，又有：=n/m=150/m兩式聯(lián)立得：150/m≤2/3,解得：m≥225.所以散列表需要設(shè)計(jì)225個(gè)單位。五、算法分析題1、給出下列遞歸過程的執(zhí)行結(jié)果 voidunknown(intw){if(w){ unknown(w-1); for(inti=1;i<=w;i++)cout<<w<<''; cout<<endl; }}調(diào)用語句為unknown(4)。答案：(1) 1 22333 44442、給出遞歸過程的執(zhí)行結(jié)果 voidunknown(intn){ cout<<n%10; if(int(n/10))unknown(int(n/10)); } 調(diào)用語句為unknown(582)。答案： 2853、給出遞歸過程的執(zhí)行結(jié)果 intunknown(intm){ intvalue; if(!m)value=3; elsevalue=unknown(m-1)+5; returnvalue; }執(zhí)行語句為cout<<unknown(3)。答案： 184、設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每個(gè)元素占一個(gè)空間，問A[3][3]（10）存放在什么位置腳注（10）表示用10進(jìn)制表示。答案：設(shè)數(shù)組元素A[i][j]存放在起始地址為Loc(i,j)的存儲(chǔ)單元中。因?yàn)椋篖oc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676所以：n=(676-2-644)/2=15所以：Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=6925、設(shè)單鏈表結(jié)構(gòu)為structListNode{intdata; ListNode*link; };下面的程序是以單鏈表為存儲(chǔ)結(jié)構(gòu),實(shí)現(xiàn)二路歸并排序的算法,要求鏈表不另外占用存儲(chǔ)空間,排序過程中不移動(dòng)結(jié)點(diǎn)中的元素,只改各鏈結(jié)點(diǎn)中的指針,排序后r仍指示結(jié)果鏈表的第一個(gè)結(jié)點(diǎn)。在初始狀態(tài)下,所有待排序記錄鏈接在一個(gè)以r為頭指針的單鏈表中。例如,在算法實(shí)現(xiàn)時(shí)，利用了一個(gè)隊(duì)列做為輔助存儲(chǔ),存儲(chǔ)各有序鏈表構(gòu)成的歸并段的鏈頭指針。初始時(shí),各初始?xì)w并段為只有一個(gè)結(jié)點(diǎn)的有序鏈表。隊(duì)列的數(shù)據(jù)類型為Queue,其可直接使用的相關(guān)操作有置空隊(duì)列操作：makeEmpty();將指針x加入到隊(duì)列的隊(duì)尾操作：EnQueue(ListNode*x);退出隊(duì)頭元素,其值由函數(shù)返回的操作：ListNode*DlQueue();判隊(duì)列空否的函數(shù),空則返回1,不空則返回0：intIsEmpty()。解決方法提示：程序首先對(duì)待排序的單鏈表進(jìn)行一次掃描,將它劃分為若干有序的子鏈表,其表頭指針存放在一個(gè)指針隊(duì)列中。當(dāng)隊(duì)列不空時(shí),從隊(duì)列中退出兩個(gè)有序子鏈表,對(duì)它們進(jìn)行二路歸并,結(jié)果鏈表的表頭指針存放到隊(duì)列中。如果隊(duì)列中退出一個(gè)有序子鏈表后變成空隊(duì)列,則算法結(jié)束。這個(gè)有序子鏈表即為所求。在算法實(shí)現(xiàn)時(shí)有6處語句缺失，請(qǐng)閱讀程序后補(bǔ)上。(1)兩路歸并算法 voidmerge(ListNode*ha,ListNode*hb,,ListNode*&hc){ ListNode*pa,*pb,*pc; if(ha→data<=hb→data){hc=ha;pa=ha→link;pb=hb;} else{hc=hb;pb=hb→link;pa=ha;} pc=hc; while(pa&&pb)if(pa→data<=pb→data) { pc→link=pa;pc=pa;pa=pa→link; } else{pc→link=pb;pc=pb;pb=pb→link; } if(pa)pc→link=pa;elsepc→link=pb;};(2)歸并排序主程序 voidmergesort(ListNode*r){ ListNode*s,t;QueueQ; if(!r)return; s=r;(r) ; while(s){ t=s→link; while(t!=0&&s→data<=t→data){s=t;t=t→link;} if(t){s→link=0;s=t;(s);} } while(!()){ r=(); if(())break; s=();merge(r,s,t);(t);}}6、請(qǐng)讀下列程序，該程序是在單鏈表中刪除一個(gè)結(jié)點(diǎn)的算法，為空出的地方填上正確的語句。（7分）voiddemo2(LinkListhead,ListNode*p){（2）程序功能是計(jì)算∑ni=1i!，該算法的時(shí)間復(fù)雜度為O（n）.10、判斷一個(gè)帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表L是否對(duì)稱相等的算法如下所示，請(qǐng)?jiān)谒惴ǖ奶幪钊胝_的語句。intsymmetry(DblListDL){intsym=1;DblNodep=DL->rLink,q=DL->lLink;While(p!=q&&p->lLink==q)&&sym==1)if(p->data==q->data){p=p->rLink;q=q->lLink;}elsesym=0;returnsym;}11、閱讀下面程序，指出其算法的功能#include“”intBaseTrans(intN,intB){inti,result=0;Stack<int>S;while(N!=0){i=N%B;N=N/B;(i);}while(!()){i=();();result=result*10+i;}returnresult;}答案：該算法是將一個(gè)非負(fù)的十進(jìn)制整數(shù)N轉(zhuǎn)換為另一個(gè)基數(shù)為B的B進(jìn)制數(shù)。12、閱讀下面程序，指出其算法的功能template<classType>voidBinaryTree<Type>::binsearchTree(BinTreeNode<Type>*t,int&bs){if(t!=Null){if((t->letfchild==Null||t->data>t->leftchild->data)&&(t->rightchild==Null||t->data<t->rightchild->data)){bs=1;binsearchTree(t->leftchild,bs);if(bs)binsearchTree(t->rightchild,bs);}elsebs=0;}}答案：該算法是判別給定的以二叉鏈表存儲(chǔ)的二叉樹是否是二叉搜索樹。采用遞歸算法，對(duì)樹中的所有結(jié)點(diǎn)檢查是否左子樹上結(jié)點(diǎn)的關(guān)鍵碼都小于它的關(guān)鍵碼，右子樹上結(jié)點(diǎn)的關(guān)鍵碼都大于它的關(guān)鍵碼。如滿足上述條件，則是二叉搜索樹。六、綜合算法題1、試設(shè)計(jì)一個(gè)實(shí)現(xiàn)下述要求的查找運(yùn)算函數(shù)Locate。設(shè)有一個(gè)帶表頭結(jié)點(diǎn)的雙向鏈表L，每個(gè)結(jié)點(diǎn)有4個(gè)數(shù)據(jù)成員：指向前驅(qū)結(jié)點(diǎn)的指針llink、指向后繼結(jié)點(diǎn)的指針rlink，存放字符數(shù)據(jù)的成員data和訪問頻度freq。所有結(jié)點(diǎn)的freq初始時(shí)都為0。每當(dāng)在鏈表上進(jìn)行一次Locate(L,x)操作時(shí)，令元素值為x的結(jié)點(diǎn)的訪問頻度freq加1，并將該結(jié)點(diǎn)前移，鏈接到與它的訪問頻度相等的結(jié)點(diǎn)后面，使得鏈表中所有結(jié)點(diǎn)保持按訪問頻度遞減的順序排列，以使頻繁訪問的結(jié)點(diǎn)總是靠近表頭。答案：(1)定義鏈表結(jié)構(gòu) structDoubleListNode{ chardata; intfreq; DoubleListNode*llink,*rlink;}; 初始時(shí)，所有結(jié)點(diǎn)的freq域的值都為0。(2)定義函數(shù)DoubleListNode*locate(DoubleListNode*f;char&x){ DoubleListNode*p,*q; p=f→rlink; /*跳過表頭結(jié)點(diǎn)*/ while(p!=NULL&&p→data!=x)p=p→rlink; /*搜索*/ if(p){ p→freq++;q=p→llink; p→rlink→llink=q;q→rlink=p→rlink; /*從鏈中摘下p*/ while(q!=f&&q→freq<p→freq)q=q→llink; p→llink=q; p→rlink=q→rlink;q→rlink→llink=p; q→rlink=p;/*在q后面插入p*/} returnp; }2、已知A[n]為整數(shù)數(shù)組，試寫出實(shí)現(xiàn)下列運(yùn)算的遞歸算法： (1)求數(shù)組A中的最大整數(shù)。 (2)求n個(gè)整數(shù)的和。 (3)求n個(gè)整數(shù)的平均值答案：#include<>classRecurveArray{private:int*Elements;intArraySize;intCurrentSize;public:RecurveArray(intMaxSize=10):ArraySize(MaxSize),Elements(newint[MaxSize]){}~RecurveArray(){delete[]Elements;}voidInputArray();intMaxkey(intn);intsum(intn);floatAverage(intn);};voidRecurveArray::InputArray(){cout<<”InputthenumberofArray:\n”;for(inti=0;i<ArraySize;i++)cin>>Elements[i];}intRecurveArray::Maxkey(intn){if(n==1)returnElements[0];inttemp=Maxkey(n-1);if(Elements[n-1]>temp)returnElements[n-1];elsereturntemp;}intRecurveArray::Sum(intn){if(n==1)returnElements[0];elsereturnElements[n-1]+Sum(n-1);}floatRecurveArray::Average(intn){if(n==1)return(float)Elements[0];elsereturn((float)Elements[n-1]+(n-1)*Average(n-1))/n;}intmain(intargc,char*argv[]){intsize=1;cout<<”theElements:”;while(size<1)cin>>size;RecurveArrayra(size);();Cout<<”\nThemaxis:”<<<<end1;Cout<<”\nTheSumis:”<<ra.Sum<<end1;Cout<<”\nTheaveis:”<<<<end1;Return0;}3、試編寫一個(gè)函數(shù)計(jì)算n!*2n的值，結(jié)果存放于數(shù)組A[arraySize]的第n個(gè)數(shù)組元素中，0narraySize。若設(shè)計(jì)算機(jī)中允許的整數(shù)的最大值為maxInt，則當(dāng)n>arraySize或者對(duì)于某一個(gè)k(0kn)，使得k!*2k>maxInt時(shí)，應(yīng)按出錯(cuò)處理?？捎腥缦氯N不同的出錯(cuò)處理方式： (1)用cerr<<及exit(1)語句來終止執(zhí)行并報(bào)告錯(cuò)誤； (2)用返回整數(shù)函數(shù)值0,1來實(shí)現(xiàn)算法，以區(qū)別是正常返回還是錯(cuò)誤返回； (3)在函數(shù)的參數(shù)表設(shè)置一個(gè)引用型的整型變量來區(qū)別是正常返回還是某種錯(cuò)誤返回。 用你認(rèn)為是最好的方式實(shí)現(xiàn)它。答案：#include“”#definearraySize100#defineMaxInt0x7fffffffintcalc(intt[],intn){inti,edge=MaxInt/n/2;t[0]=1;if(n!=0){for(i=1;i<n;i++