2012-2019年三峽大學(xué)836數(shù)據(jù)結(jié)構(gòu)真題合輯

第2第2頁三峽大學(xué)2012年研究生入學(xué)考試試題（A卷）科目代碼：型匕科目名稱：數(shù)據(jù)結(jié)構(gòu)（考生必須將答案寫在答題紙上，總分150分，考試時(shí)間180分鐘）一、選擇題（每小題2分，共40分）1、線性表采用鏈?zhǔn)酱鎯r(shí)，結(jié)點(diǎn)的存儲地址（）。必須是不連續(xù)的B.連續(xù)與否均可C.必須是連續(xù)的D.和頭結(jié)點(diǎn)的存儲地址相連續(xù)2、已知指針q所指結(jié)點(diǎn)是指針p所指結(jié)點(diǎn)的直接前驅(qū)，若在*q與*p之間插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行（）操作。A.s—>next二p—>next;p—>next二sB.q—>next二s;s—>next二pC.p—>next二s->next;s—>next二pD.p—>next二s;s—>next二q3、設(shè)有一個(gè)順序棧S,元素按S1,S2,S3,S4,S5,S6順序進(jìn)棧，若6個(gè)元素的出棧順序?yàn)镾2,S3,S4,S6,S5,S1,則順序棧的容量至少應(yīng)為（）。A.2B.3C.4D.54、如下陳述中正確的是（）。A.串是一種特殊的線性表B.串的長度必須大于零C.串中兀素只能是字母D.空串就是空白串5、設(shè)有一個(gè)二維數(shù)A[m][n]，假設(shè)A[0][0]存放位置在544,A[5][5]存放位置在624，每個(gè)元素占一個(gè)空間，A[2][2]在（）位置。A.592B.586C.576D.6086、設(shè)有5個(gè)字符出現(xiàn)的頻度分別為1,2,3,5,4,則對應(yīng)的哈夫曼樹的帶權(quán)路徑TOC\o"1-5"\h\z長度為（）。A.34B.33C.35D.157、含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中非零元素的個(gè)數(shù)為（）。A.eB.2eC.n2—eD.n2—2e第頁三峽大學(xué)2017年碩士研究生入學(xué)考試試題（A卷）科目代碼：936科目名稱：數(shù)據(jù)結(jié)構(gòu)考試時(shí)間為3小時(shí)，卷面總分為150分答案必須寫在答題紙上一單選題（每小題5分，共60分）1數(shù)據(jù)在計(jì)算機(jī)存儲器內(nèi)表示時(shí)，物理地址與邏輯地址沒有關(guān)聯(lián)的，為—。A.存儲結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.鏈?zhǔn)酱鎯Y(jié)構(gòu)D.順序存儲結(jié)構(gòu)在一個(gè)長度為n的順序表中刪除第i個(gè)元素（1<=i<=n）時(shí)，需向前移動個(gè)A.n-iB.n-i+lC.n-i-1D.i在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則須執(zhí)行—s—>next二p—>next;p—>next二sq—>next二s;s—>next二pp—>next二s->next;s—>next二pp—>next二s;s—>next二q線性表的順序存儲結(jié)構(gòu)是一種的存儲結(jié)構(gòu)。A.隨機(jī)存取B.順序存取C.索引存取D.散列存取在等概率情況下，順序表的插入操作要移動結(jié)點(diǎn)。A.全部B.—半C.三分之一D.四分之一TOC\o"1-5"\h\z向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行。hs->next二s;s->next二hs;hs=s;s->next二hs->next;hs->next二s;s->next二hs;hs=hs->next;在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為。A.front二front->nextB.rear二rear—>nextC.rear二front->nextD.front二rear—>next若m行n列二維數(shù)組A,其元素記為A[i][j],i=0,l,-?m-l,j=0,l,-?n-l,按列優(yōu)先順序存儲，則A[i][j]地址為。A.LOC(A[O][O])+[j*m+i]B.LOC(A[O][O])+[j*n+i]C.LOC(A[O][O])+[(j-1)*n+i-1]D.LOC(A[O][O])+[(j-l)*m+i-l]對于長度為9的順序存儲的有序表，若采用折半查找，在等概率情況下的平均查找長度為—的9分之一。TOC\o"1-5"\h\zA.20B.18C.25D.22對于順序存儲的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，則查找元素26的比較次數(shù)為_。A.2B.3C.4D.5在索引查找中，若用于保存數(shù)據(jù)元素的主表的長度為144,它被均分為12子表，每個(gè)子表的長度均為12,則索引查找的平均查找長度為。A.13B.24C.144D.79若一個(gè)元素序列基本有序，則選用_方法較快。A.直接插入排序B.簡單選擇排序C.堆排序D.快速排序二填空題（每小題5分，共30分）從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較個(gè)元素結(jié)點(diǎn)。在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持該表有序的時(shí)間復(fù)雜度是。若對n階對稱矩陣A,其元素計(jì)為A[i][j],i,j=0,2,???n-l,以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑兀òㄖ鲗蔷€上所有元素）依次存放于一維數(shù)組B中，B的元素為B[i],i=O,l,…，n（n+l）/2-l,則下三角中的A[i][j]）元素對應(yīng)B中位置元素。在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，所含的邊數(shù)為。從具有n個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)元素時(shí)，在最壞情況下的時(shí)間復(fù)雜度為。在對n個(gè)元素進(jìn)行冒泡排序的過程中，至少需要趟完成。三應(yīng)用題（每題10分，共60分）1?計(jì)算下面程序段的時(shí)間復(fù)雜度：i=1;while（i<=n）i=i*3;對于線性表的兩種存儲結(jié)構(gòu)（順序表和鏈表），若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲結(jié)構(gòu)？試說明理由。什么是隊(duì)列的上溢現(xiàn)象？一般有幾種解決方法，試簡述之。4分別畫出具有3個(gè)結(jié)點(diǎn)的樹和3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。5在一棵度為M樹