江西師范大學計算機信息工程學院863數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計歷年考研真題匯編附答案6p

1、江西師范大學計算機信息工程學院863 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計歷年考研真題匯編附答案最新資料， WOR格D 式，可編輯修改！目錄第一部分 歷年考研真題匯編 32014年江西師范大學計算機信息工程學院 863 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計考研真題 32013年江西師范大學計算機信息工程學院 863 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計考研真題 10第二部分 兄弟院校真題匯編 182013年北京航空航天大學 991 數(shù)據(jù)結(jié)構(gòu)與 C語言程序設(shè)計考研真題 182012年北京航空航天大學 991 數(shù)據(jù)結(jié)構(gòu)與 C語言程序設(shè)計考研真題 292011年北京航空航天大學 991 數(shù)據(jù)結(jié)構(gòu)與 C語言程序設(shè)計考研真題 412010年北京航空航天大學

2、 993 數(shù)據(jù)結(jié)構(gòu)與 C語言程序設(shè)計考研真題 50第一部分 歷年考研真題匯編2014 年江西師范大學計算機信息工程學院 863 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計考研真題江西師范大學2014年全日制碩士研究生入學考試試題（B卷）專業(yè)：081200計算機科學與技術(shù)科目：863數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計注：考生答題時，請寫在考點下發(fā)的答題紙上，寫在本試題紙或其他答題紙上的一律無 效。（本試題共計6頁）一；單項選擇題（每小題2分，共20分）1.在一個長度為n的順序表中刪除第i個元素（lnext=NULL B. p-next=headC p=NULL D. p=head6. 無向圖 G= （V, E） 其中：V=a,b,c,

3、d,eJ, E= （a,b） （a,e） （a,c）, （b,c）, （c,f）,（f,d）, （e,d） ,對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是（）.A. b,e,c,d,fB. a,c,f,e,b,dC. a,e,d,f,c,bD. a,qb,c,f,d7. 對于哈希函數(shù)H（key）=key%13,被稱為同義詞的關(guān)鍵字是（）A. 35 和 41B. 25 和 51C. 23 和 39D. 15 和 448. 下列說法錯誤的是（）.A. 冒泡排序在數(shù)據(jù)有序的情況下具有最少的比較次數(shù)。B. 直接插入排序在數(shù)據(jù)有序的情況下具有最少的比較次數(shù)。C. 二路歸并排序需要借助O （/!）的存儲

4、空間.D. 基數(shù)排序適合于實型數(shù)據(jù)的排序.9. 如果在推序過程中，每次均將一個待排序的記錄按關(guān)鍵字大小加入到前面已經(jīng)有序的 子表中的適當位置，則該排序方法稱為（）A. 插入排序B.歸并排序C冒泡排序D.堆排序10. 設(shè)二叉排序樹中關(guān)鍵字由1至1000的整數(shù)構(gòu)成，現(xiàn)要檢索關(guān)鍵字為363的結(jié)點，下 述關(guān)鍵字序列哪一個不可能是二叉排序樹上搜索到的序列（）A 2,252,401,398,330,344,397,363B. 924,220,911,244,898,258,362,363C 952,202,911,240.912,245,363D. 2,399,387,219,266,382,381,27

5、8,363二、填空（每小題2分，共20分）1. 若一個算法中的語句頻度之和為T（n）=10n+2nlog2n,則算法的時間復雜度為2. 如果入棧序列是1, 3, 5,，97 , 99,且出棧序列的第一個元素為99,則出棧序列中第30個元索為3. 某二叉樹的先根遍歷序列為ABDC,中根遍歷序列為BDAC,則該二叉樹根結(jié)點的右孩子是.4. 若對序列（15, 2, 48, 60, 89, 25）采用二路歸并法升序排序，則進行一趙歸并后產(chǎn)生的序列為.5. 算術(shù)表達式a*（b+c）-d的對應的后綴表達式是6. 假設(shè)一個6階的下三角矩陣B按列優(yōu)先順序壓縮存儲在一維數(shù)組A中，其中A0存儲矩陣的第一個元素則A

6、14存儲的元素是7. 觸序循環(huán)隊列中（數(shù)組的大小為n）,隊頭指示front指向隊列的第1個元素，隊尾指示rearffi向隊列履后元素的后1個位置，則循環(huán)隊列中存放了 n-1個元素，即循環(huán)隊 列滿的條件為.&在含100個結(jié)點的完全二叉樹中，葉子結(jié)點的個數(shù)為9. 包含有刃個頂點的有向強連通圖茲多條邊.10. 如下圖所示的有向無環(huán)圖可以排出種不同的拓撲序列.三、程序填空與程序分析題（每小題6分，共24分）1. 閱讀下面的遞歸程序，寫出程序的運行結(jié)果。#include int fun(int n) int i； if (n=l) fun(n-l);for (i=l;ilchil(i=NULL& els

7、e temp=(*t)-lchild;(*t)-!child=(*t)-rchild; (*t)-rchild=temp; fun( &(*t)-lchild ); fun( &(*t)-rchild);(*t)-rchild=NULL) returnJ說明算法fun()的功能；(2)畫出算法執(zhí)行于上圖所示的二叉樹t后所得的二叉樹。3. 帶頭結(jié)點的單鏈表存儲結(jié)構(gòu)定義如下：typedcf int datatype;typedef struct node datatype data;struct node *next;linknode;typedcf linknode 叫inkiist；函數(shù)max

8、()的功能是在帶頭結(jié)點的單鏈表head中找最大值所在的位置作為函數(shù)的返 回結(jié)果，請將程序補充完整。linklist max(linklist head)(linklist pmax,p;/pmax用于記錄最大數(shù)結(jié)點所在的位置pmax=head-next;while (p) if ( p-data pmax-data)(2)； ；return pmax;J.函數(shù)void insertsort(int a,int n)采用直接插入法對長度為n的整型數(shù)組進行升序排序, 誨在橫線上填上適當?shù)恼Z句。void insertsort(int a|,int n)int ij,x;for (i=l;i=0 &

9、aj|x)(5);四. 解答題（每小題10分，共40分）1. 己知一棵二叉樹如下圖所示.試求:（1）寫出該二叉樹前序、中序和后序遍歷的結(jié)果;（2）試對該二叉樹進行中序線索化2. 設(shè)散列函數(shù)H （key） =key mod 6,給定鍵值序列為 11、23、15、34、16、13、24、37、29、56,采用拉鏈法解決沖突，試畫出相應的開散列表，并計算在等概率情況下査 找成功時的平均査找長度.3. 對數(shù)據(jù)12、3、4. 56、7. 9、5、13、21、38應用堆推序算法，畫出建立小根堆（最 小堆）的過程4下圖是一個無向網(wǎng)絡(luò)及其鄰接表表示.其中結(jié)點用自然數(shù)表示.鄰接表中的邊結(jié)點存 儲有邊上的權(quán)值.請

10、解答如下問題：（1）寫出從結(jié)點0出發(fā)深度優(yōu)先遍歷序列；（2）畫出從0結(jié)點出發(fā)用Prim方法建立最小生成樹的過程圖示.五、算法與程序設(shè)計題(第1、2題每小題14分，第3小題18分，共46分)答題娶求：根據(jù)設(shè)計思想和實現(xiàn)步驟.采用C語言寫岀對應的算法程序，關(guān)鍵之處 請給出注釋.1設(shè)計算法linldist delodddinklist head). IM除帶頭結(jié)點的單鏈表h“d中所有值為岱數(shù) 值的結(jié)點，函數(shù)返回牲表頭結(jié)點地址.2. 設(shè)計算法int binSearch(int a|,int kftjnt right,int x),采用二分査找算法在按升序排列 的整塑數(shù)組段alefL.right|中合找

11、值為x的數(shù)據(jù)位置，若賁找成功，則返回該數(shù)所在的位K.否則返回3. 定義二叉排序樹存儲結(jié)構(gòu)，并設(shè)計算法程序，根據(jù)鍵盤輸入數(shù)據(jù)序列建立一棵二叉排 序樹.2013 年江西師范大學計算機信息工程學院 863 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計考研真題江西師范大學2013年全日制碩士研究生入學考試試題（A卷）專業(yè)： 081200計算機科學與技術(shù) 科目： 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計注：考生答題時，請寫在考點下發(fā)的答題紙上，寫在本試題紙或其他答題紙上的一律 無效。（本試題共計7頁）一、單項選擇題（每小題2分，共20分）1-若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組（K, R）, 是K上（）A. 操作的有限集合C類型的有限集合2. 以下算法的時間

12、復雜度為（）其中K是數(shù)據(jù)元素的有限集合.則RB. 映象的有限集合D.關(guān)系的有限集合void fun(int n) inti=l;while (i=n) i=i*2;return ;A. nJ+1A. O（n）B O（lopn）C. O（nlog2n）D. O（n2）2.在長度為n的順序表中刪除第i個元素（linext=p-next; p-next=s;B. p-ncxt=s; s-ncxt=p-next;C. p-next=s-next; s-next=p;D. s-next=p; p-next=s-ncxt;4. 操作系統(tǒng)為實現(xiàn)函數(shù)嵌套調(diào)用的管理，通常需要設(shè)立一個存儲區(qū)，記錄函數(shù)調(diào)用轉(zhuǎn)移的斷

13、點，該存儲區(qū)的邏輯結(jié)構(gòu)是（）A.棧B隊列C樹D.圖5. 對于一棵具有n個結(jié)點，度為4的樹來說，（）A樹的高度至多是n3B.樹的高度至多是17C. 第i層至多有4 （i-l）個節(jié)點D-至少在某一層上正好有4個節(jié)點6. 下列二叉樹中，不平衡的二叉樹泉（） n個頂點的強連通圖中至少含有(A. n-1條有向邊C. n (n-1) /2條有向邊已知一個有向圖如下所示，則從頂點aB. n條有向訥D. n (n-1)條有向邊出發(fā)進行深度優(yōu)先遍歷，不可能得到的DFS序列為()A. a d b e f cC. a d c b f cB a d c e f b D. a d e fb c用某種排序方法對關(guān)鍵字序列

14、(25, 84, 21, 47, 15, 27, 68, 35, 20)進行排 序時，序列的變化情況如下：20,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,6884貝J所采用的排序方法是()A. 選擇排序B.希爾排序 C.歸并排序D快速排序0.在最好和最壞情況下的時間復雜度均為O(nlog2n)fi穩(wěn)定的排序方法是()A快速排序B.堆排序C.歸并排序D.基數(shù)排序二、填空題(每小題2分，共2()分)(.數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的。沢己知在結(jié)點個數(shù)大于1的單循環(huán)鏈表中，指針P指向表

15、中某個結(jié)點，則下列程序 段執(zhí)行結(jié)束時，指針q指向結(jié)點的結(jié)點。while(q-next?=p) q=q-next;3. 假設(shè)S和X分別表示進棧和出棧操作，由輸入序列“ABC”得到輸出序列“BCA”的操作序列為SSXSXX,則由“a*b+c”得到“ab*c+，啲操作序列為。4. 如圖所示的有向無環(huán)圖可以排出種不同的拓撲序列。5-假設(shè)一個6階的下三角矩陣B按列優(yōu)先順序壓縮存儲在一維數(shù)組A中，其中A|0| 存儲矩陣的第一個元素bIP則A|14J存儲的元素是.6. 在含100個結(jié)點的完全二叉樹中，葉子結(jié)點的個數(shù)為。7. 在無向圖中，若從頂點a到頂點h存在,則稱a與b之間是連通的。&對Prim算法和Kru

16、skal算法，算法適合求邊稀疏的網(wǎng)的最小生成樹。9. 在排序之前，若關(guān)鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，用較為適當。10. 在有序表(12, 24, 36, 4X, 60. 72, 84)中二分査找關(guān)鍵字72時所需進行的關(guān)鍵字比較次數(shù)為.三、程序填空與程序分析題(每小題6分，共24分)1. 函數(shù)getprimeO的功能是將2到100之間的所有素數(shù)存入數(shù)組a,并返回所存入的 素數(shù)個數(shù)，main()函數(shù)中調(diào)用該因數(shù)輸出所有素數(shù)。請將程序補充完整。#includc #include int getprime(int a(J) int i=O,n,j,k;for (n=2;n10

17、0;n+) k=fint)sqrt(n);for (j=2;jk)a(2)|=n;return i;int main() int(3); 函數(shù)調(diào)用for (i=0;ivk;i+)printf(n%5dM,a|il);2字符串采用帶頭結(jié)點的單鏈表存儲，其結(jié)構(gòu)定義如下：tj pedef char datatype;typedef struct nodedatatype data;struct node * next; listnode;t pedef listnode* linklist;| 兩數(shù)index (t,s)的功能是求子串$在主串t中的第一次出現(xiàn)的起始位置，如果s 不在t中，則返回NUL

18、L,請將程序補充完整。hnldist index(iinklist tjinklist s)* linklist p.qmpre;int succ=0;I pre=t;I p=t-next;I while ( p & !succ )| r=p;/*r指示主串t當前比較的位置勺I q=s-next; /*q指示子串s當前比較的位置*7 II while ( succ & q & r)if (r-data=q-data) (5)q=q-next;else succ=0;pre=p;p=p-next;if (succ) (6)eke return NULL;希爾排序(shell)過程可表示如下，請將

19、其補充完整。nclude )id shdlsort(int a()9 int length)int i,jdx;d=length/2;while( (7) for(i=d;i=0 & xaj| ) (8)；(9);5d=d/2;int main() inta|10J;for(i=0;i10;i+) scanf(”d”,a+i);shellsortfaJO);for(i=0;idata); if(t-rchild)s.data +s.top=t-rchild;if(t-lchild)t=t-lchild;else t=s.datas.top;四、解答題(每小題10分，共40分)1. 已知一棵二叉

20、樹的前序與中序序列分別為ABDCEGHFI和DBAGHECFIo(1) 畫出此二叉樹；(2) 寫岀該二叉樹的后序遍歷結(jié)果。2. 序列12, 18, 33, 29, 35, 92, 88, 36是否構(gòu)成大根堆(最大堆)，如不夠成, 請畫出對其進行堆排序時建立大根堆的過程示意圖。3. 假設(shè)通信電文使用的字符集為abcde,字符的哈夫曼編碼依次為：0110, 1(),110, 111, 00, 0111 和 010o(1) 請根據(jù)哈夫曼編碼畫出此哈夫曼樹，并在葉子結(jié)點中標注相應字符；(2) 若這些字符在電文中出現(xiàn)的頻度分別為：3, 35, 13, 15, 20, 5和9,求該哈 夫曼樹的帶權(quán)路徑長度

21、。4. 已知某帶權(quán)連通圖如下圖所示，用普里姆(prim)算法從頂點A開始求最小生成 樹。試按照最小生成樹算法分步聚給出構(gòu)造過程。五、算法與程序設(shè)計題(第1、2題每小題14分，第3小題18分，共46分)答題要求： 描述算法的基本設(shè)計思想； 給出每個算法所需的數(shù)據(jù)結(jié)構(gòu)定義： 根據(jù)設(shè)計思想和實現(xiàn)步驟，采用用C語言寫出對應的算法程序，關(guān)鍵之處請給出 簡要注釋。1. 已知集合采用帶頭結(jié)點的單鏈表存儲，請設(shè)計算法函數(shù)，求兩個單鏈表表示的集 合的交集，并將結(jié)果用一個新的單鏈表保存并返回。2. 二叉樹采用二叉鏈表存儲結(jié)構(gòu)，采用遞歸程序?qū)崿F(xiàn)以下函數(shù)：(1) 求二叉樹的高度函數(shù)int high(bintree t

22、);(2) 求二叉樹的葉子結(jié)點個數(shù)函數(shù)int lcaf(bintree t);(3) 返回二叉樹的后序遍歷的第一個結(jié)點地址函數(shù)bintree succlast(bintrce t);3. 給定-個有向圖，試編寫程序?qū)崿F(xiàn)：(1) 創(chuàng)建該圖的鄰接衷(出邊表)表示；(2) 輸出該圖中出度最大的結(jié)點值。第二部分 兄弟院校真題匯編2013 年北京航空航天大學 991 數(shù)據(jù)結(jié)構(gòu)與 C 語言程序設(shè)計考研真題北京航空航天大學2013年碩士研究生入學考試試題 科目代碼：991數(shù)據(jù)結(jié)構(gòu)與C語言程序設(shè)計(共頁)考生注意：所有答題務必書寫在考場提供的答題紙上，寫在本試題單上的答題一律無效(本題單不參與閱卷)。一、單項

23、選擇題(本題共20分，每小題各2分)1. 對于長度為n的線性表，建立其對應的單鏈表的時間復雜度為。A. 0(1)；B. O(log2n)： C. O(n)；D. O(n2)o2. 一般情況下，在一個雙向鏈表中插入一個新的鏈結(jié)點，。A. 需要修改4個指針域內(nèi)的指針； B.需要修改3個指針域內(nèi)的指針；C.需要修改2個指針域內(nèi)的指針；D.只需要修改1個指針域內(nèi)的指針。3. 假設(shè)用單個字母表示中綴表達式中的一個運算數(shù)(或稱運算對彖)，并利用堆棧產(chǎn)生中綴表達式對應的后綴表達式。對于中綴表達式A+B*(C/D-E),當從左至右掃描到 運算數(shù)E時，堆棧中的運算符依次是o (注：不包含表達式的分界符)A. +

24、/-；B. +(/-；C. +*-；D. +(-4. 若某二叉排序樹的前序遍歷序列為50,20,40,30,80,60,70,則后序遍歷序列為。A. 30,40,20,50,70,60,80；B. 30,40,20,70,60,80,50；C. 70,60,80,50,30,40,20；D. 70,60,80,30,40,20,50。5. 分別以6, 3, & 12, 5, 7對應葉結(jié)點的權(quán)值構(gòu)造的哈夫曼(Huffman)樹的深度為。A. 6；B. 5；C. 4：D. 3o6. 卜列關(guān)于國的敘述中，錯誤的是oA. 根據(jù)圖的定義，圖中至少有一個頂點；B根據(jù)圖的定義，圖中至少有一個頂點和一條邊(弧

25、)；C具有n個頂點的無向圖最多有nx(n-l)/2條邊：D. 具有n個頂點的有向圖最多有nx(n-l)條邊(弧)。7. 若在有向圖G的拓撲序列中，頂點w在頂點Vj之前，則下列4種情形中不可能 出現(xiàn)的是oA. G 中有弧Vj,Vj；B. G中沒有弧Vi,vj；C. G中有一條從頂點*到頂點Vj的路徑；D. G中有一條從頂點勺到頂點*的路徑。8下列關(guān)于査找操作的敘述中，錯誤的是。A. 在順序表中査找元素可以采用順序査找法，也可以釆用折半査找法；B. 在鏈表中査找結(jié)點只能采用順序査找法，不能采用折半査找法；C. 一般情況下，順序査找法不如折半査找法的時間效率高；D. 折半査找的過程可以用一棵稱之為“

26、判定樹”的二叉樹來描述。9. 在一棵m階B樹中，除根結(jié)點之外的任何分支結(jié)點包含關(guān)鍵字的個數(shù)至少 是0A. m/2-1；B. m/2；C.m/21-1；D.m/2。10若對序列(49,38,65,97,76,13,27,49，)進行快速排序，則第一趟排序結(jié)束(即確 定了第1個分界元素的最終位置)時，序列的狀態(tài)是。A(13,27,49, 38,49, 76, 97, 65)；B. (13,38, 27,49 49, 76, 97, 65)；C. (13,38,49, 27,49, 97, 76, 65)；D. (13, 38,49, 27, 49, 76, 97, 65)。二、填空題(本題共20分

27、，每小題各2分)1. 非空線性表在采用存儲結(jié)構(gòu)的情況下，刪除表的一個數(shù)據(jù)元素平均需要移動表中近一半元素的位買。2. 將一個長度為n的單鏈表鏈接到一個長度為m的單鏈表后面，該算法的時間復雜度用大O符號表示為。3. 若完全二叉樹的葉結(jié)點的數(shù)目為k,且最下面一層的結(jié)點數(shù)大于1,則該完全二叉樹的深度為o4. 若深度為8的完全二叉樹的第7層有10個葉結(jié)點，則該二叉樹的結(jié)點總數(shù)為O5. 在具有n個頂點的有向圖中，每個頂點的度最大可以達到。6. 若對有向圖進行拓撲排序，則能夠得到拓撲序列的條件是o7. 已知長度為10的順序表中數(shù)據(jù)元素按值從小到大排列。若在該表中進行折半査找,則平均査找長度（ASL）是。8.

28、 若在一棵m階B樹的某個結(jié)點中插入一個新的關(guān)鍵字值而引起結(jié)點產(chǎn)生分裂，則該結(jié)點中原有的關(guān)鍵字值的數(shù)目是O9. 有一種排序方法可能會出現(xiàn)這種情況：最后一趟排序開始之前，序列中所有的元素都不在其最終應該在的位置上，這種排序方法是。10. 若按照泡排序法的思想將序列（2, 12, 16, 5, 10）中元素按值從小到大進行排序，整個排序過程屮所進行的元索之間的比較次數(shù)為O三、綜合題（本題共20分，每小題各5分）1. 一般情況下，當一個算法中需要建立多個堆棧時可以選用下列三種處理方案之一。問：這三種方案之間相比較各有什么優(yōu)點和缺點？（1）多個堆棧共享一個連續(xù)的存儲空間；（2）分別建立多個采用順序存儲結(jié)

29、構(gòu)的堆棧；（3）分別建立多個釆用鏈式存儲結(jié)構(gòu)的堆棧。2. 已知二叉樹采用二叉鏈表存儲結(jié)構(gòu)，根結(jié)點指針為T,鏈結(jié)點類型定義為：typedef struct nodechar data;/* 數(shù)據(jù)域/struct node *lchild, *rchild;/指向左、右子樹的指針域/*BTREE；下面的算法的功能是輸出二叉樹中所有葉結(jié)點的數(shù)據(jù)信息。 請在算法的空白處（方框內(nèi)）填入合適內(nèi)容，使算法完整。 void FUNC（BTREE T），if（T!=NULL）iM I）printf（“c”, Tdata）;FUNCdb；FUNCdb；3. 對給定AOE網(wǎng)（如題三3圖所示），請完成（1）分別求出各

30、活動環(huán)=1,2,，14）的最早開始時間與最晚開始時間：（請以表格 形式給出結(jié)果）（2）求出所有關(guān)鍵路徑。（請以圖形方式畫出各關(guān)鍵路徑）題三J圖4已知要將給定的關(guān)鍵字值序列（42, 51,16, 26, 50, 25, 37, 68, 64, 33, 18）進行散列存 儲，并且要求裝填因子（也稱負載因子）a0.61,（1）請利用除留余數(shù)法構(gòu)造出合適的散列函數(shù)；（2）請畫岀利用該散列函數(shù)依次將序列中各關(guān)鍵字值插入到散列表以后表的狀態(tài)。 設(shè)散列表初始為空，并且采用線性探測再散歹法處理散列沖突。四、算法設(shè)計題（本題15分）假設(shè)長度為n的順序表Al.n中每個數(shù)據(jù)元素為一整數(shù)，請寫出按照下列思想將表 中數(shù)

31、據(jù)元素按值從小到大進行排序的算法：第1趟排序?qū)⒆钚≈翟胤旁贏l中，最大 值元素放在An中；第2趟排序?qū)⒋涡≈翟胤旁贏2中，次大值元素放在An-1 中；，依此下去，直至排序結(jié)束。五、填空題(本題共20分，每小題各2分)1. 已知某等比數(shù)列的第一項邊為1,公比為3,下列程序的功能是輸出該數(shù)列中小 于1000的最大項an及其對應的no請在程序的空白處(方框內(nèi))填入合適內(nèi)容，使程序完整。main() int n=l, a=l, q=3;while(l)a=a*q;n+；if(a=1000)Iprintf(“n=%d,a=%dn, nT, |b；2. 下列遞歸函數(shù)FUNC2的功能是判斷整型數(shù)組an是

32、否為遞增數(shù)組，即判斷數(shù)組 的元素是否按值從小到大排列。若是一個遞增數(shù)組，則函數(shù)返回true,否則，函數(shù)返回 false o請在函數(shù)的空白處(方框內(nèi))填入合適內(nèi)容，使函數(shù)完整。bool FUNC2(int a , int n) if(n=l)return true;if(n=2)return |return| & (an-1 =an2);3. 下列程序的功能是主函數(shù)調(diào)用FUNC3函數(shù)求方陣a中兩條對角線上亓素之和。 請在程序的空白處(方框內(nèi))填入合適內(nèi)容，使程序完整。#define N 10void FUNC3(int aNN, int *p, int *q) int i；*P=0;*q=0；f

33、br(i=O； iN; i+)p=*p4-(*|b；q=*q-h(*|I)；main() intaNN, i,j,x, y;for(i=0; iN; j卄)fbr(j=O;jvN;j+)scanff%!”, *(a+i)+j);FUNC3(a, &x, &y);/ x,y中分別存放主對角線與副對角線上的元素之和/printf(%d, %dn”, x, y);4. 下列程序的功能是先通過鍵盤輸入一正整數(shù)，然后調(diào)用一遞歸函數(shù)FUNC4,該 函數(shù)將正整數(shù)轉(zhuǎn)換為對應的數(shù)字字符組成的字符串顯示在屏幕上。例如：若輸入的正整 數(shù)為583,則屏幕上顯示的是字符串583。請在程序的空白處(方框內(nèi))填入合適內(nèi)容，

34、使程序完整。# include void FUNC4( int n ) int i;i=n/10;iftl bFUNC4(i);putchardb；main() int n;printf(“請輸入一正整數(shù)n： ”)；scanff%d, &n);printf(“轉(zhuǎn)換后的字符串是：”)；FUNC4(n); ,5. 下列程序的功能是將小寫字母轉(zhuǎn)換成對應的大寫字母后的第2個字母，例如：將 a轉(zhuǎn)換成C,將b轉(zhuǎn)換成D,其中，y轉(zhuǎn)換成A, z轉(zhuǎn)換成B。請在程序的空白處(方框內(nèi))填入合適內(nèi)容，使程序完整。#include main() char ch;while(ch=getchar( )!=*n)if(ch

35、=ta, & chv=，z)ZZJ；if(chZ & chv=Z+2)6. 下列函數(shù)FUNC6的功能是刪除字符串s屮的所有空白字符，包括Tab字符、回 車符以及換行符。請在函數(shù)的空白處(方框內(nèi))填入合適內(nèi)容，使函數(shù)完整。#include #include #include FUNC6(char *s) int i, t;charc80;fbr(i=O,t=O; si; i+)if(! isspaced I)clh=sni；ct=cO strcpy(s, c);7. 下列程序的功能是判斷輸入的字符串是否是“回文”。(注：按順序讀與按逆序讀 都一樣的字符串被稱為“回文”，例如：abcdcba)。請

36、在程序的空白處(方框內(nèi))填入合適內(nèi)容，使程序完整。#include #include main() char ch81 , *p=ch, *q;gets(p);q=P4l 1;whiledMi*P=*q) p+； q;elsebreak;if(pvq)printf(“該字符串不是回文！ n”)；elseprintf(“該字符串是回文！ n”)；8. 下列程序的功能是：對于字符類型變量ch=108,保留中間兩位，而將高、低3 位清零。請在程序的空白處(方框內(nèi))填入合適內(nèi)容，使程序完整。main() char ch;ch=108;ch= I; printf(%d, ch);9. 設(shè)file為存放了

37、整型數(shù)據(jù)的二進制文件。下列程序的功能是從該文件中讀入第3 個數(shù)據(jù)輸出到屏幕上。請在程序的空白處(方框內(nèi))填入合適內(nèi)容，使程序完整。#include main() FILE fjp;int number;巾=fdpen(file, “rb);fseek(fp, L SEEK_SET);.freadd L 2, 1, fp);printf(“d”, number);fclose(fp);10. 下列程序的功能是將一個磁盤中的二進制文件復制到另一個磁盤中。兩個文件 的文件名隨命令行一起輸入，輸入時原有文件的文件名在前，新復制文件的文件名在后。請在程序的空白處(方框內(nèi))填入合適內(nèi)容，使程序完整。#in

38、clude main(int argc, char *argv) FILE * old, * new;if(argc!=3)printf(uYou forgot to enter a filename!n); exit(0);if(old=fbpen(|b=NULL) printf(4tCannot open infile!n);exit(0);if(new=fbpen(r b=NULL) printf(“Cannot open outfile!n”)；exit(0);while(!feof(old)fputc(fgetc(old), new);fclose(old); fclose(new)

39、;六、簡答題（本題共20分，每小題各5分）1. 在C語言中，函數(shù)調(diào)用時數(shù)據(jù)的傳遞通常有哪幾種方式？2. 在C語言中，指針可以做哪些運算？3. 共用體（union）具有哪些基本特征？4. 使用文件的基本操作步驟是怎樣的？七、程序設(shè)計題（本題15分）請編寫一程序，該程序的功能是找出并且刪除一維整型數(shù)組a100中的最小值元素。 要求：數(shù)組各元素通過鍵盤輸入獲得初值；所有對數(shù)組元素的引用必須通過指針完成。八、程序設(shè)計題（本題20分）請僅編寫出一 C語言函數(shù)char *maxword（char *s, char *t）該函數(shù)的功能是求出字符 串s與字符串t的最長公共單詞（這里，假設(shè)兩個字符串均由英文字母

40、和空格字符組成）; 若找到這樣的公共單詞，函數(shù)返回該單詞，否則，函數(shù)返回NULL。例如：若 s=“This is C programming text”，t=“This is a text for C programming”，則函 數(shù)返回 “programming”。要求：函數(shù)中不得設(shè)置保存單詞的存儲空間；給出函數(shù)之前請用文字簡要敘述函數(shù)的基本思想。2012 年北京航空航天大學 991 數(shù)據(jù)結(jié)構(gòu)與 C 語言程序設(shè)計考研真題北京航空航天大學2012年碩士研究生入學考試試題 科冃代碼：991 數(shù)據(jù)結(jié)構(gòu)與C語言程序設(shè)計(共H頁)考生注意：所有答題務必書寫在考場提供的答題紙上，寫在本試題單上 的答題

41、一律無效(本題單不參與閱卷)。.一、填空題(本題共20分，每小題各2分)1. 從總體上說，“數(shù)據(jù)結(jié)構(gòu)”課程主要研究三個方面的內(nèi)容。2. 若對某線性表最常用的操作是在表中插入元素或者刪除表中元素，則對于順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)這兩種存儲結(jié)構(gòu)而言，線性表應該采用。3. 在長度為n的非空隊列中進行插入或者刪除操作的時間復雜度用大O符號表示為。4. 若一棵度為4的樹中度為1、2、3和4的結(jié)點個數(shù)分別為4、2、1和1,則該樹中葉結(jié)點的個數(shù)為o5. 若某二叉樹的中序遍歷序列為B,A,F,DGC,E,按層次遍歷序列為A,B,C,D,E,F,G,則該二叉樹的后序遍歷序列為。6. 將一棵結(jié)點總數(shù)為n、且具有m

42、個葉結(jié)點的樹轉(zhuǎn)換為一棵二叉樹以后，該二叉樹中右子樹為空的結(jié)點有個。7. 對于圖 G=(V,E)與 G=(V,E),若有 VuV, E cE,則稱 G是 G 的。8. 在順序表(6,15,30,37,65,68,70,72,89,99)中采用折半查找法査找元素37,與表中進行過比較的元素依次是。9. 若已知n個關(guān)鍵字值具有相同的散列函數(shù)值，并且采用線性探測再散列法處理沖突，那么，將這n個關(guān)鍵字值全部散列到初始為空的地址空間中，發(fā)生散列沖突的次數(shù) 是o10. 若長度為n的序列K=(k|,k2,kn)當且僅當滿足kiWk2i并且kk2i+i(l WiWLn/2j) 時，則稱該序列為一個小頂堆積(He

43、ap)。根據(jù)該定義，序列(26,5,77,1,61,11,59,48,15,19) 對應的小頂堆積是o二、簡答題(本題共20分，每小題各5分)1. 如果一個具有100個頂點、200條邊的有向圖采用鄰接矩陣存儲，該鄰接矩陣是 否是稀疏矩陣？為什么？(這里我們假設(shè)：當矩陣中非零元素的數(shù)目小于整個矩陣總元 素的數(shù)目的5%時認為該矩陣為稀疏矩陣)2. 一般情況卜，建立散列表時難以避免出現(xiàn)散列沖突，常用處理散列沖突的方法之 一是開放定址法，該方法的基本思想是什么？3. 若對序列(2,12,16,88,5,10)按值從小到大進行排序，前三趟排序的結(jié)果分別為：第一趟排序的結(jié)果：(2,12,16,5,10,8

44、8)第二趟排序的結(jié)果：(2,12,5,10,16,88)第三趟排序的結(jié)果：(2,5,10,12,16,88)請問：該結(jié)果是采用了選擇排序法還是采用了(起)泡排序法得到的？為什么？4. 快速排序法的排序過程是遞歸的。若待排序序列的長度為n,則快速排序的最小 遞歸深度與最大遞歸深度分別是多少？ 三、綜合題(本題共20分，每小題各5分)1. 若非空雙向循環(huán)鏈表中鏈結(jié)點結(jié)構(gòu)為llink data rlink ,則依次執(zhí)行下列4 條語句的目的是在該鏈表中由q指的結(jié)點后面插入一個由p指的結(jié)點，其中1條語句有 錯誤，請找出該語句，并寫出正確的語句。p-llink=q; p-rlink=q-rlink; q_

45、rlink=p; q_rlink_llink=p;/*第1條語句*/嚴第2條語句/*第3條語句/車第4條語句*/2. 已知某完全二叉樹的第7層有10個葉結(jié)點，請求出該完全二叉樹的結(jié)點總數(shù)的 最大值。(要求寫出結(jié)論的求解過程)3證明：具有n個頂點的無向圖最多有nx(n-l)/2條邊。4. 請分別寫出對數(shù)據(jù)元素序列(8030,50,10,90,20)按值從大到小進行選擇排序時每一趟的排序結(jié)果。四. 算法設(shè)計題(木題15分)已知某具有n個頂點的有向圖采用鄰接表方法存儲，其中，用以存儲有向邊信息的 邊結(jié)點類型為typedef struct edge int adjvex;struct edge *ne

46、xt;/*某有向邊的終止頂點在頂點結(jié)點中的位置*/ /*指向下一個邊結(jié)點/)ELink;用以存儲頂點信息的頂點結(jié)點類型為typedef struct ver int indegree; vertype vertex; ELink *link;/*某頂點的入度/*某頂點的數(shù)拯信息*/*指向以該頂點為出發(fā)點的第一個邊結(jié)點*/VLink;并且n個頂點結(jié)點構(gòu)成一個數(shù)組結(jié)構(gòu)G0.n-1o請寫一個算法，該算法判斷給定的頂點 序列V0.n-l=V|,V2,V3,.,Vn是否是該有向圖的一個拓撲序列，若是該有向圖的一個拓 撲序列，算法返回1,否則，算法返回0。五、單項選擇題(本題共20分，每小題各2分)1.

47、在C語言中，標識符只能由字母、數(shù)字和下劃線三種字符組成，并且第個字符。A必須是字母B.必須是下劃線C.必須是字母或考下劃線D.可以是字母、數(shù)字和下劃線之一2. 若整型變量x的初值為6,則計算農(nóng)達式x+=x-=x*x之后，x的值是。A. 50B. 60C. -50D. -603. 下列4個程序段中，不是無限循環(huán)的是oA. for(b=0,a=l; a+b; a=k+) k=a;B. for(; a+=k);C. while(l) a+; D. for(k=IO; k-) total+=k;4. 說明double(*ptr)N;” 中的標識符ptr是。A. N個指向double類型變量的指針B.

48、指向N個double類型變量的函數(shù)指針C. 一個指向由N個double類型元素組成的一維數(shù)組的指針D. 具有N個指針元素的維指針數(shù)組，其每一個元素都只能指向double類 型變量5. 下列4個敘述中，正確的是：，A. char *r=china;等價于 char *r; *r=“china”；B. char * pt尸 “china;等價于 char *ptr; ptr=china;C. char string 10= china”;等價于 char $tring10; string戶“china”;D. char sb4=“abc,temp4=abc”;等價于 char str4=temp4J=abc*;6在 C 程序中,語句char *func(int x,int y);” 表示A. 對函數(shù)ftmc的定義B.對函數(shù)fimc的調(diào)用C.對函數(shù)fimc返回值類型的說明D.對函數(shù)ftinc的原型說明7. 對于下列程序，若從鍵盤上輸入：abcdef回車，則輸出結(jié)果是。#include #include main() char *p,*q;p=(char *)malloc(sizeof(char)*20);q=p；1scanf(t%s%s,p,q);printf(%s%sn,p,q);A. defdefB. abedefC. abc dD