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