2007解放軍理工大學(xué)指揮自動化學(xué)院考研專業(yè)課-數(shù)據(jù)結(jié)構(gòu)與自動控制

2007解放軍理工大學(xué)指揮自動化學(xué)院考研專業(yè)課——數(shù)據(jù)結(jié)構(gòu)與自動控制.txt我的優(yōu)點(diǎn)是：我很帥；但是我的缺點(diǎn)是：我?guī)浀牟幻黠@。什么是幸福？幸福就是貓吃魚，狗吃肉，奧特曼打小怪獸！令堂可是令尊表姐？我是胖人，不是粗人。本文由胥秀峰貢獻(xiàn)pdf文檔可能在WAP端瀏覽體驗不佳。建議您優(yōu)先選擇TXT，或下載源文件到本機(jī)查看。機(jī)密★啟用前中國人民解放軍理工大學(xué)2007年全國碩士研究生入學(xué)統(tǒng)一考試試卷考試科目代碼：806考試科目名稱：數(shù)據(jù)結(jié)構(gòu)與自動控制原理說明：所有答案必須按序號書寫在考場提供的答題紙上，可不抄寫原題，做在試卷和草稿紙上的一律無效。數(shù)據(jù)結(jié)構(gòu)部分一、填空題（本題共10空，每空2分，滿分20分）1．已知一棵樹中含有父子關(guān)系的邊是：(L,N)，(G,K)，(G,L)，(G,M)，(B,E)，(B,F)，(D,G)，(D,H)，(D,I)，(D,J)，(A,B)，(A,C)，(A,D)。（1）請畫出這棵樹的樹形。（2）該樹的高度是。2．含3個結(jié)點(diǎn)的二叉樹的樹形共有（1）種，其樹形分別為（2）。其中，有（3）個是完全二叉樹。3．已知二叉樹的擴(kuò)充先序序列是“ABC空空DE空FG空空空空空”。那么，它的中序序列是（1），后序序列是（2）。第1頁（共10頁）4．如果排序期間，序列的變化情況依次是：①25，84，21，47，15，27，68，35，20（原始排列）②20，15，21，25，47，27，68，35，84③15，20，21，25，35，27，47，68，84④15，20，21，25，27，35，47，68，84那么，所用的排序方法是排序。5．對于下面的加權(quán)圖：A6B12C4958G20D12151610F13E（1）寫出用Kruskal算法求最小生成樹時，依次得到的樹邊（寫出邊的兩個頂點(diǎn)和長度，形如AB6）。（2）畫出所求出的最小生成樹。二、單項選擇題（本題共10空，每空2分，滿分20分）1．設(shè)進(jìn)棧序列是1，2，3，…，n，出棧序列為p1，p2，p3，…，pn。（1）若p1=n，則pi（1＜i≤n）為。A）iB）n-iC）n-i+1D）不確定第2頁（共10頁）（2）若pn=n，則pi（1≤i＜n）為。A）iB）n-iC）n-i+1D）不確定（3）若p1=3，則p2為。A）可能是2B）不可能是2C）可能是1D）必是1（4）若p3=1，則p1為。A）必是2B）可能是3C）必定是3D）不可能是3（5）若pn=1，則pi（1≤i＜n）為。A）有多種可能B）n-iC）iD）n-i+12．對有序數(shù)組a[12]進(jìn)行二分查找時，查找長度最大的元素下標(biāo)為。A）1，4，7，9，11B）0，3，6，9，11C）1，3，6，9，11D）0，4，8，9，103．在雙向鏈表中，刪除p所指結(jié)點(diǎn)（不考慮回收結(jié)點(diǎn)）不正確的操作是。A）p->Llink->Rlink=p->Rlink,p->Rlink->Llink=p->Llink;B）p->Llink=p->Rlink,p->Rlink=p->Llink;C）p=p->Llink,p->Rlink=p->Rlink->Rlink,p->Rlink->Llink=p;D）p=p->Rlink,p->Llink=p->Llink->Llink,p->Llink->Rlink=p;第3頁（共10頁）4．若k元正則樹中共有m個非葉結(jié)點(diǎn)，則葉子數(shù)。A）≥(k-1)mB）≤kmC）=(k-1)m-1D）=(k-1)m+15．用Dijkstra算法求下圖中，頂點(diǎn)A到其余各頂點(diǎn)的最短路徑時，將按照的次序，依次求出A到它們的最短路徑。A）BEDFCB）BEDCFC）BCEDFD）EDFCBA3B65E8F712C15104D6．以下序列不是堆。A）100，85，98，77，80，60，82，40，20，10，66B）100，98，85，82，80，77，66，60，40，20，10C）10，20，40，60，66，77，80，82，85，98，100D）100，85，40，77，80，60，66，98，82，10，20三、程序填空題（本題共10空，每空2分，滿分20分）注：編號相同的空內(nèi)應(yīng)填寫相同內(nèi)容。第4頁（共10頁）1．函數(shù)merge用于將兩個順序存儲的遞增有序表合并成一個遞增有序表。設(shè)數(shù)組a[M]，b[N]，c[M+N]分別用來存儲原表和結(jié)果表，其中，M和N是整體量（常數(shù)）。voidmerge(inta[],intb[],intc[]){int（1）;while(（2）)if(a[i]a[i+1]){x=a[i];a[i]=a[i+1];a[i+1]=x;（6）;}if(（8）)return;flag=0;for(i=--（9）;i>=f;i--)if(a[i]>a[i+1]){x=a[i];a[i]=a[i+1];a[i+1]=x;（6）;}（10）++;}}四、閱讀程序，回答下面的問題（滿分15分）#include#definen8voidmain(){inti,j,k,x,a[n],b[n];printf("請輸入%d個數(shù)據(jù):\n",n);for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n;i++)b[i]=-1;k=1;第6頁（共10頁）while(k<n){i=k-1;while(i<n-1){j=i+k;if(a[i]<=a[j])b[i]=b[j],b[j]=i;//語句1elsex=a[i],a[i]=a[j],a[j]=x,b[j]=i;i=j+k;}k*=2;}j=b[n-1];i=b[j];while(i!=-1){if(a[i]>a[j])j=i;//語句2i=b[i];}printf("%d\n",a[j]);}（1）當(dāng)輸入數(shù)據(jù)為（6果。第7頁（共10頁）5843127）時，寫出程序輸出的結(jié)（2）寫出該程序的功能，即程序在找（輸出）什么樣的數(shù)值。（3）如果將n的值改為任意的正整數(shù)（不限于形如2k的數(shù)），如何對程序進(jìn)行修改，從而保證程序能完成上述功能？提示：只要加一條語句即可，請指出在哪條語句上面（或下面）加語句。（4）對任意的正整數(shù)n，程序為完成上述功能，至多進(jìn)行多少次元素之間的比較，即“語句1”和“語句2”共執(zhí)行多少次。（5）請指出程序使用什么樣的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組b[n]所實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。提示：可從下面給出的選項，選擇其中你認(rèn)為最準(zhǔn)確的一個。A．比賽樹模式B．判定樹模式C．最優(yōu)檢索樹模式D．普通鏈表模式（6）請指出該程序中所用到的算法是不是最優(yōu)的，即是否存在完成上述功能的算法，所進(jìn)行的元素比較次數(shù)少于該程序。簡述為什么。第8頁（共10頁）自動控制原理部分一、（15分）RC網(wǎng)絡(luò)如圖1所示，其中u1為網(wǎng)絡(luò)輸入量，u2為網(wǎng)絡(luò)輸出量。（1）畫出網(wǎng)絡(luò)結(jié)構(gòu)圖；（2）求傳遞函數(shù)U2(s)/U1(s)。C2U1R1C1R2U2圖1二、（15分）設(shè)復(fù)合控制系統(tǒng)如圖2所示，圖中Gn(s)為順饋傳遞函數(shù)，Gc(s)=kts為測速電機(jī)及分壓器的傳遞函數(shù)，1(s)為前向通路中環(huán)節(jié)的傳遞G函數(shù)，N(s)為可測量的干擾。若G1(s)=1/s2，試確定Gn(s)，Gc(s)和k，使系統(tǒng)輸出量完全不受干擾n(t)的影響，且單位階躍響應(yīng)的超調(diào)量等于25%，峰值時間為2s。圖2GnR(S)E(S)C(S)N(S)kG1Gc最大的元素下標(biāo)為。A）1，4，7，9，11B）0，3，6，9，11C）1，3，6，9，11D）0，4，8，9，103．在雙向鏈表中，刪除p所指結(jié)點(diǎn)（不考慮回收結(jié)點(diǎn)）不正確的操作是。A）p->Llink->Rlink=p->Rlink,p->Rlink->Llink=p->Llink;B）p->Llink=p->Rlink,p->Rlink=p->Llink;C）p=p->Llink,p->Rlink=p->Rlink->Rlink,p->Rlink->Llink=p;D）p=p->Rlink,p->Llink=p->Llink->Llink,p->Llink->Rlink=p;第3頁（共10頁）4．若k元正則樹中共有m個非葉結(jié)點(diǎn)，則葉子數(shù)。A）≥(k-1)mB）≤kmC）=(k-1)m-1D）=(k-1)m+15．用Dijkstra算法求下圖中，頂點(diǎn)A到其余各頂點(diǎn)的最短路徑時，將按照的次序，依次求出A到它們的最短路徑。A）BEDFCB）BEDCFC）BCEDFD）EDFCBA3B65E8F712C15104D6．以下序列不是堆。A）100，85，98，77，80，60，82，40，20，10，66B）100，98，85，82，80，77，66，60，40，20，10C）10，20，40，60，66，77，80，82，85，98，100D）100，85，40，77，80，60，66，98，82，10，20三、程序填空題（本題共10空，每空2分，滿分20分）注：編號相同的空內(nèi)應(yīng)填寫相同內(nèi)容。第4頁（共10頁）1．函數(shù)merge用于將兩個順序存儲的遞增有序表合并成一個遞增有序表。設(shè)數(shù)組a[M]，b[N]，c[M+N]分別用來存儲原表和結(jié)果表，其中，M和N是整體量（常數(shù)）。voidmerge(inta[],intb[],intc[]){int（1）;while(（2）)if(a[i]a[i+1]){x=a[i];a[i]=a[i+1];a[i+1]=x;（6）;}if(（8）)return;flag=0;for(i=--（9）;i>=f;i--)if(a[i]>a[i+1]){x=a[i];a[i]=a[i+1];a[i+1]=x;（6）;}（10）++;}}四、閱讀程序，回答下面的問題（滿分15分）#include#definen8voidmain(){inti,j,k,x,a[n],b[n];printf("請輸入%d個數(shù)據(jù):\n",n);for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n;i++)b[i]=-1;k=1;第6頁（共10頁）while(k<n){i=k-1;while(i<n-1){j=i+k;if(a[i]<=a[j])b[i]=b[j],b[j]=i;//語句1elsex=a[i],a[i]=a[j],a[j]=x,b[j]=i;i=j+k;}k*=2;}j=b[n-1];i=b[j];while(i!=-1){if(a[i]>a[j])j=i;//語句2i=b[i];}printf("%d\n",a[j]);}（1）當(dāng)輸入數(shù)據(jù)為（6果。第7頁（共10頁）5843127）時，寫出程序輸出的結(jié)（2）寫出該程序的功能，即程序在找（輸出）什么樣的數(shù)值。（3）如果將n的值改為任意的正整數(shù)（不限于形如2k的數(shù)），如何對程序進(jìn)行修改，從而保證程序能完成上述功能？提示：只要加一條語句即可，請指出在哪條語句上面（或下面）加語句。（4）對任意的正整數(shù)n，程序為完成上述功能，至多進(jìn)行多少次元素之間的比較，即“語句1”和“語句2”共執(zhí)行多少次。（5）請指出程序使用什么樣的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組b[n]所實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。提示：可從下面給出的選項，選擇其中你認(rèn)為最準(zhǔn)確的一個。A．比賽樹模式B．判定樹模式C．最優(yōu)檢索樹模式D．普通鏈表模式（6）請指出該程序中所用到的算法是不是最優(yōu)的，即是否存在完成上述功能的算法，所進(jìn)行的元素比較次數(shù)少于該程序。簡述為什么。第8頁（共10頁）自動控制原理部分一、（15分）RC網(wǎng)絡(luò)如圖1所示，其中u1為網(wǎng)絡(luò)輸入量，u2為網(wǎng)絡(luò)輸出量。（1）畫出網(wǎng)絡(luò)結(jié)構(gòu)圖；（2）求傳遞函數(shù)U2(s)/U1(s)。C2U1R1C1R2U2圖1二、（15分）設(shè)復(fù)合控制系統(tǒng)如圖2所示，圖中Gn(s)為