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

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