2017年江西師范大學(xué)數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計考研真題

》》》》》》2023年整理歷年要考研試題資料《《《《《《》》》》》》2023年整理歷年要考研試題資料《《《《《《/》》》》》》2023年整理歷年要考研試題資料《《《《《《2017年江西師范大學(xué)數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計考研真題一、單項(xiàng)選擇題(每小題2分，共20分)1.順序存儲表示中數(shù)據(jù)元素之間的邏輯關(guān)系是由()表示的。A.指針B.邏輯順序C.存儲位置D.問題的上下文2.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復(fù)雜度為()。A.0(1)B.0(n)C.0(m)D.0(m+n)3.在單鏈表中，指針p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)“刪除x的后繼”的語句是()。A.p=p->next; B.p->next=p->next->next;C.p->next=p; D.p=p->next->next;4.若進(jìn)棧序列為1,2,3,4,5,6,且進(jìn)棧和出?？梢源┎暹M(jìn)行，則不可能出現(xiàn)的出棧序列是()。A.2,4,3,1,5,6 B.2,3,5,1,6,4C.4,3,2,1,5,6 D.3,2,4,1,6,55.對于一顆具有n個結(jié)點(diǎn)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)之和為()。A.n-1B.n+1C.nD.2n6.按照二叉樹的定義，具有3個結(jié)點(diǎn)的二叉樹有()不同的形態(tài)。A.6B.5C.4D.37.如果在排序過程中，每次均將一個待排序的記錄按關(guān)鍵宇大小加入到前面已經(jīng)有序的子表中的適當(dāng)位置，則該排序方法稱為()。A.插入排序B.歸并排序C.冒泡排序D.堆排序8.對于哈希函數(shù)H(key)=key%13,被稱為同義詞的關(guān)鍵字是()。A.35和41B.23和39C.15和44D.25和519.若結(jié)點(diǎn)的存儲地址與其關(guān)鍵字之間存在某種映射關(guān)系，則稱這種存儲結(jié)構(gòu)為()A.順序存儲結(jié)構(gòu)B.鏈?zhǔn)酱鎯Y(jié)構(gòu)C.索引存儲結(jié)構(gòu)D.散列存儲結(jié)構(gòu)10.有n個頂點(diǎn)的無向連通圖最少有()條邊。A.2nB.n+1C.nD.n-1二、填空題(每小題2分，共20分)1.數(shù)據(jù)的邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、（）2.順序循環(huán)隊(duì)列中(數(shù)組大小為6),隊(duì)首指示front和隊(duì)尾指示rear的值分別為3和0,當(dāng)從隊(duì)列中刪除1個元素，再插入2個元素后，front和rear的值分別為（）和（）3.表達(dá)式a*(b+c*b)-d的后綴表達(dá)式是（）。4.在一個單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行的語句是（）5.具有33個結(jié)點(diǎn)的完全二叉樹的高度為（）,有（）個葉結(jié)點(diǎn)。6.若從鍵盤輸入n個元素，則建立一個有序單向鏈表的時間復(fù)雜度為（）。7.如下圖所示的有向無環(huán)圖可以排出（）種不同的拓?fù)湫蛄?。DDFEACB8.表示一個有50個頂點(diǎn)，50條邊的有向圖的鄰接矩陣有（）個非零元素。9.要解決散列引起的哈希沖突問題，常用的3種方法是；開放定址法，（）10.在關(guān)鍵字序列(12,23,34,45,56,67,78,89,91)中二分查找關(guān)鍵字為45的結(jié)點(diǎn)時，所需進(jìn)行的比較次數(shù)為（）三、程序填空與程序分析題(每小題6分，共24分)1.設(shè)單鏈表的存儲定義如下：typedefintdatatype;typedefstructlinknode{datatypeinfo;structlinknode*next;}node;typedefnode*linklist;已知用有序鏈表存儲整數(shù)集合的元素。閱讀算法funl,并回答程序后的問題：intfunl(linklistha,linklisthb){/*linklist是帶有頭結(jié)點(diǎn)的單鏈表，ha和hb分別為指向存儲兩個有序整數(shù)集合的鏈表的頭指針*/linklistpa=ha->next,pb=hb->next;while(pa&&pb&&pa->info==pb->info){pa=pa->next;pb=pb->nēxt;}if(pa==NULL&&pb==NULL)return1;elsereturn0;(1)寫出執(zhí)行fun1(a,b)的返回值，其中a和b分別為指向存儲集合{2,4,5,7,9,12}和{2,4,5,7,9}的鏈表的頭指針；(2)簡述算法fun1的功能。2.閱讀如下程序代碼，并回答程序后的問題：#defineMAXSIZE100typedefintdatatype;typedefstruct{datatypea[MAXSIZE];intsize;}sequencelist;Voidfun2(sequencelist*L){datatypet;inti;for(i=0;i<L->size/2;i++){t=L->a[i];L->a[i]=L->a[L->size-1-i];L->a[L->size-1-i]=t;(1)若順序表L的數(shù)據(jù)值為{2,4,5,7,9,12},求執(zhí)行fun2(&L)以后，順序表L的數(shù)據(jù)值。(2)簡述算法fun2的功能。3.設(shè)二叉樹的存儲定義如下：typedefchardatatype;/*結(jié)點(diǎn)屬性值的類型*/typedefstructnode{/*二叉樹結(jié)點(diǎn)的類型*/datatypedata;structnode*lchild,*rchild;}bintnode;typedefbintnode*bintree;bintreeroot;函數(shù)change的功能是將一棵給定二叉樹中所有結(jié)點(diǎn)的左、右子女互換。請將程序空白處補(bǔ)充完整。voidchange(bintreet){bintreep;if(①){p=t->lchild;t->1child=t->rchild;t->rchild=p;②③4.設(shè)順序表的存儲定義同第三大題第2小題。函數(shù)binsearch1的功能是采用非遞歸二分查找算法，查找元素值為key在有序表L中的位置，并將查找結(jié)果作為函數(shù)值返回，若查找失敗則返回-1。請將程序空白處補(bǔ)充完整。intbinsearch1(sequencelistL,datatypekey){intlow=0,high=L.size-1,mid;while(①){mid=(low+high)/2;if(L.a[mid]==key)returnmid;if(L.a[mid]>key)high=mid-1;elselow=mid+1;四、解答題(每小題10分，共40分)1.已知二叉樹的前序序列和中序序列分別為HDACBGFE和ADCBHFEG。(1)畫出該二叉樹；(2)畫出與(1)求得的二叉樹對應(yīng)的森林。2.已知一個無向圖的頂點(diǎn)集為{A,B,C,D,E},其鄰接矩陣如下所示：3.設(shè)待排序的7個記錄的排序碼序列為{27,12,45,6,18,51,32},畫出使用二路歸并排序算法進(jìn)行排序的狀態(tài)變化過程。4.從空樹起，依次插入關(guān)鍵字40,8,90,15,62,95,12,23,56,構(gòu)造一棵二叉排序樹。(1)畫出該二叉排序樹(2)畫出刪去該樹中元素值為90的結(jié)點(diǎn)之后的二叉排序樹。五、算法與程序設(shè)計題(第1、2題每小題14分，第3小題18分，共46分)答題要求：①用自然語言說明所采用算法的思想；②用C語言(或其他程序設(shè)計語言)寫出對應(yīng)的算法程序，并加上必要的注釋。1、設(shè)單鏈表的存儲定義同第三大題第1小題。設(shè)計一個算法，判斷一個不帶頭結(jié)點(diǎn)的單鏈表中各個結(jié)點(diǎn)值是否有序。2、設(shè)二叉樹的存儲定義同第三大題第3小題。設(shè)計一個函數(shù)返回一棵給定二叉樹中葉子結(jié)點(diǎn)的個數(shù)。3、設(shè)中序穿線二叉樹在鏈接方式下的數(shù)據(jù)類型定義：ty