》》》》》》2023年整理歷年要考研試題資料《《《《《《》》》》》》2023年整理歷年要考研試題資料《《《《《《/》》》》》》2023年整理歷年要考研試題資料《《《《《《2016年江西師范大學(xué)數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)考研真題一、單項(xiàng)選擇題（每小題2分，共20分）1.對于邏輯結(jié)構(gòu)B,如果它只有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，而其他的每一個(gè)結(jié)點(diǎn)有且僅-有一個(gè)前驅(qū)和一個(gè)后繼，則稱為（）A.網(wǎng)狀結(jié)構(gòu)B.線性結(jié)構(gòu) C.圖形結(jié)構(gòu)D.樹型結(jié)構(gòu)2.線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元的地址（）A.必須是連續(xù)的 B.部分地址必須是連續(xù)的C.一定是不連續(xù)的 D,連續(xù)不連續(xù)都可以3.隊(duì)列是一種特殊的線性表，具有（）的性質(zhì)。A.先進(jìn)先出B.先進(jìn)后出 C.后進(jìn)后出 D.順序進(jìn)出4.設(shè)非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)由p所指向，則該尾結(jié)點(diǎn)滿足（）A.p->next==NULLB.p==NULLC.p->next==headD.p==head5.一棵具有5層的滿二叉樹所包含的結(jié)點(diǎn)個(gè)數(shù)為（）A.15B.31-C.63D.326.將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹，按照從上到T、、同…-層次上按從左到右的順序?qū)λ薪Y(jié)點(diǎn)從1開始編號，則編號為49的結(jié)點(diǎn)，其左孩子編號為（）A.98B.99C.50D.487.若無向圖G是具有6個(gè)頂點(diǎn)的連通圖，則至少具有（）條邊。A.5B.6C.7D.88.適用于二分法檢索的表的存儲方式及元素排列要求為（）A.鏈?zhǔn)椒绞酱鎯?，元素?zé)o序 B.鏈?zhǔn)椒绞酱鎯?，元素有序C.順序方式存儲，元素?zé)o序D.順序方式存儲，元素有序9.在關(guān)鍵字序列｛1,3,9,12,32,找關(guān)鍵字為81,45,62,75,78,81,93,99｝中，二分査的結(jié)點(diǎn)81時(shí)，通過（）次比較后査找成功。A.1B.2C.4D.810.下面幾種排序方法中，空間復(fù)雜度最高的是（）A.快速排序B.選擇排序C.歸并排序D.插入排序二、填空題（每小題2分，共20分）1.數(shù)據(jù)的存儲結(jié)構(gòu)主要有4種?：順序存儲、鏈?zhǔn)酱鎯?、（）和（?.一個(gè)算法的復(fù)雜度可分為（）復(fù)雜度和（）雜度。3.設(shè)棧S的初始狀態(tài)為空，元素T、2、3、4、5依次全部進(jìn)棧，然后所有元素依次出棧，則出棧序列為（）.4.表達(dá)式A*（B+C）/（D-E+F）的后綴表達(dá)式是（）。5.在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，應(yīng)執(zhí)行語句（）6.對于一個(gè)循環(huán)單鏈表，若首指針為head,指針p指向表中的某個(gè)結(jié)點(diǎn)，則p所指結(jié)點(diǎn)是該表中最后一個(gè)結(jié)點(diǎn)的特征是（）7.一棵非空二叉樹的第i(>1)層上最多有（）個(gè)結(jié)點(diǎn)。8.在無向圖G的鄰接矩陣A中，若A[i][j]^于1,則等于（）.。9.設(shè)圖G是一個(gè)具有n個(gè)頂點(diǎn)的無向連通圖，則G的生成樹的邊數(shù)為（）10.要解決散列引起的沖突問題，常用的3種方法是開放定址法、（）和（）三、程序填空與程序分析題(每小題6分，共24分)1.閱讀下列程序，寫出程序運(yùn)行的輸出結(jié)果。#include<stdio.h>voidmain()(inti,j;i=l；while(i<4)(for(j-1;j<2*i+l;j++)printf(H%c"/'#1);printf("\n"); *i++；))2.設(shè)單鏈表的存儲結(jié)構(gòu)定義如下：typedefintdatatype;typedefstructlink_node{datatypeinfo; 'structlink_node*next;)node;typedefnode*linklist;閱讀以下程序，并回答程序后的問題：node*fun(node*headzdatatypex){node*pm=head,q=head->next;while(q&&q->info!=x)(pre=q;q=q->next;}if(q){pre->next=q->next;free(q);}returnhead;(1)請描述函數(shù)fun()的功能;(2)定義變量如下：linklisthead;設(shè)head鏈表如圖1所示。請畫出執(zhí)行函數(shù)調(diào)用語句head=fun(head,2)之后的head鏈表。3.設(shè)二叉樹的存儲結(jié)構(gòu)定義如下：typedefstructnode(/*二叉樹結(jié)點(diǎn)定義*/datatypedata;structnode*lchildz*rchild;)bintnode;typedefbintnode*bintree;函數(shù)isequal的功能是判斷給定的兩棵二叉樹tl和t2是否等價(jià)，并返回0或丄的結(jié)果。請將程序空白處補(bǔ)充完整。intisequal(bintreetlzbintreet2)(intb=0;if(tl==NULL&&t2==NULL)(1) ;elseif(tl!t2!=NULL)if(tl->data== (2) )if(isequal(tl->lchildzt2->lchild)b= (3) ;returnb;}4.設(shè)順序表的結(jié)構(gòu)定義如下:#defineMAXSIZE100typedefintdatatype;typedefstruct(datatypea[MAXSIZE];.intsize;}seqlist;函數(shù)split的功能是將給定順序表LI中的數(shù)據(jù)進(jìn)行分類，奇數(shù)存放到存