數(shù)據(jù)結構模擬試題5

1、數(shù)據(jù)結構模擬試題5 一、單選題（每小題2 分，共 10 小題， 20 分）1. 數(shù)據(jù)的四種基本存儲結構是指A. 順序存儲結構、索引存儲結構、直接存儲結構、倒排存儲結構B 順序存儲結構、索引存儲結構、鏈式存儲結構、散列存儲結構C 順序存儲結構、非順序存儲結構、指針存儲結構、樹型存儲結構D.順序存儲結構、鏈式存儲結構、樹型存儲結構、圖型存儲結構2. for （ i=0 ； im；i+ ）for （j=0 ； jt ； j+ ）for （ k=0；knext=p-next; p-next=s;B p-next=s; s-next=p-next;C p-next=s-next; s-next=p;D

2、s-next=p; p-next=s-next;5. 與線性表相比，串的插入和刪除操作的特點是A.通常以串整體作為操作對象B. 需要更多的輔助空間C. 算法的時間復雜度較高D. 涉及移動的元素更多6.隊列和棧的主要區(qū)別是A.邏輯結構不同B.C.所包含的運算個數(shù)不同D.存儲結構不同限定插入和刪除的位置不同7. 二叉樹中第 5 層上的結點個數(shù)最多為A.8B.15C.16D.328若用鄰接矩陣表示一個有向圖，則其中每一列包含的1的個數(shù)為A圖中每個頂點的入度B圖中每個頂點的出度C圖中弧的條數(shù)D圖中連通分量的數(shù)目9在下列各種文件中，不能進行順序查找的文件是A順序文件B索引文件C散列文件D多重表文件10在

3、對 n 個關鍵字進行直接選擇排序的過程中，每一趟都要從無序區(qū)選出最小關鍵字元素，則在進行第之前，無序區(qū)中關鍵字元素的個數(shù)為A iB i+1i 趟排序C n-iD n-i+1二、填空題（每小題2 分，共 10 小題， 20 分）11.數(shù)據(jù)的邏輯結構在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的（）。12 一個算法具有五個特性: （）、確定性、可行性、有零個或多個輸入、有一個或多個輸出。13順序存儲結構是通過（）表示元素之間的關系的; 鏈式存儲結構是通過指針表示元素之間的關系的。14.在鏈表的結點中，數(shù)據(jù)元素所占的存儲量和整個結點所占的存儲量之比稱作（）。15.假設一個6 階的下三角矩陣B 按列優(yōu)先順序壓縮存

4、儲在一維數(shù)組A 中，其中 A 0存儲矩陣的第一個元素11則 A 14存儲的元素是（）。16 假設 S 和 X 分別表示進棧和出棧操作，由輸入序列“ABC”得到輸出序列“ BCA”的操作序列為 SSXSXX，則由“ a*b+c/d ”得到“ ab*cd/+ ”的操作序列為（）。17.已知完全二叉樹 T 的第 5 層只有 7 個結點，則該樹共有（）個葉子結點。18.在有向圖中，以頂點 v 為終點的邊的數(shù)目稱為v 的（）。19索引順序查找適宜對（）的順序表進行查找。20.利用篩選法將關鍵字序列(37 ， 66， 48， 29， 31， 75) 建成的大根堆為 ()。三、應用題（每小題5 分，共 6

5、小題， 30 分）21鏈表與順序表的應用比較。22給出串的堆分配存儲結構的插入子串操作算法描述。串的堆分配存儲結構定義如下：typedef structchar *ch;/ 基址int length; /串長度 HString;23證明：在二叉樹的第i 層上至多有2 i-1 個結點 (i 1) 。24快速排序的一次劃分算法描述。（ 1）畫出在空表中依次插入關鍵字25， 20， 36， 15， 41， 52， 29， 72， 67 后的哈希表。（ 2）求在等概率情況下，查找成功的平均查找長度。26已知如圖所示，用普里姆（prim ）算法從頂點A 開始求最小生成樹。在算法執(zhí)行之初，頂點的集合邊的集

6、合 TE= （ A ， B ） 。試按照最小生成樹的生成過程，分步給出加入頂點和邊以后的集合UU=A ，B ，和 TE 的值。四、算法閱讀與分析題（每小題10 分，共2 小題， 20分）27閱讀算法，在空白處填入語句或注釋。void InvertAdjList(AdjList gin,gout）/ 根據(jù)有向圖的鄰接表結構生成其按入度建立的逆鄰接表結構for (i=1;i=n;i+) /（1）gini.vertex=gouti.vertex; gin.firstarc=（ 2）for (i=1;iadjvex;s=(ArcNode *)malloc(sizeof(ArcNode);/s-adjv

7、ex=i; s-next=ginj.firstarc; ginj.firstarc=s;p=p-next; /（ 5）申請結點空間。/for/ InvertAdjList28閱讀算法，指出功能和 int Depth_T (BiTree T ) / if ( !T ) depthval = 0; else depthval的作用。返回二叉樹的深度depthLeft = Depth( T-lchild );depthRight= Depth( T-rchild );depthval= 1 + (depthLeft depthRight ? depthLeft : depthRight); / el

8、se return depthval; / Depth_T五、算法設計題（本題10 分）29設計算法purge_Sq 實現(xiàn)刪除順序表SqList中重復元素，指出其算法的時間復雜度。數(shù)據(jù)結構模擬試題 5 答案 一、單選題1、B2、C3、A4、A5、A6、D7、C8、A9、C10、D二、填空題11. 存儲結構 12有窮性 13物理上相鄰14. 存儲密度 15. b55 16 SXSSXXSSXSSXXX 17. 11 18.入度19分塊有序 20. ( 75，60， 48，37， 31，29)三、應用題21參考答案（ 1）用順序的方式存儲線性表，內(nèi)存的存儲密度高，在結點等長時， 可以隨機地存取結點

9、；在順序表中插入或刪除一個數(shù)據(jù)元素，平均約需移動表中一半元素，效率比較低。（ 2） 順序表要求占用連續(xù)的存儲空間，存儲分配只能預先進行。 如果插入操作超出了預先分配的存儲區(qū)間, 需要臨時擴大是非常困難的。（ 3）采用鏈表存儲結構時則可以克服上述不足, 它適合于頻繁插入和刪除并且存儲空間大小不能預先確定的線性表。22參考答案（ 1）算法描述。構造一個新的串，為被插入串S 重新分配存儲空間。將 S 串中插入位置之前的子串復制到新分配的存儲空間中。將插入的 T 串復制到新分配的存儲空間中。將 S 串中插入位置之后的子串復制到新分配的存儲空間中。23參考答案利用歸納法。i=1時，只有一個根結點。顯然2

10、 i-1 =20=1 是對的。設對所有的 j(1j Rs.key ，則高端指針向左移動一個位置；否則，將它和樞軸元素交換，并從低端指針起和樞軸比較。4 若 Rlow.key =high 。25參考答案（ 1）哈希表01234567891011 12521541296720723625（ 2）平均查找長度查找成功的平均查找長度=(5*1+3*2+1*4)/9=1.626參考答案（ 1）集合 U 中頂點加入順序A ，B，G，I，E ，D，C，H，F(xiàn)（ 2）集合 TE 中邊加入順序（A，B），（A，G ），（G，I ），（I，E ），（E，D ），（D，C ），（C，H ），（I， F ）四、算法閱讀與分析題27參考答案（ 1）初始化逆鄰接表頂點向量（ 2） null;（ 3） gouti.firstarc;（ 4） p（ 5）指向下一個鄰接點。28參考答案功能：后序遍歷求二叉樹深度。depthval的作用：二叉樹的深度為其左右子樹深度的最大值加1。五、算法設計題29參考答案void purge_Sq( SqList &L ) /刪除順序表L 中的重復元素k