數據結構試題及答案免費-免費閱讀

　　

【正文】 一個線性表為B=（12，23，45，57，20，03，78，31，15，36），設散列表為HT[0..12]，散列函數為H（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。 在以HL為表頭指針的帶表頭附加結點的單鏈表和循環單鏈表中，判斷鏈表為空的條件分別為________________和____________________。 填空題（每空1分，共32分） 數據的邏輯結構被分為__________、 ___________ 、________和________四種。A 棧頂 B 棧底 C 任意位置 D 指定位置 D q →link=s。 單選題（每小題2分，共8分） 在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x與元素的平均比較次數，假定查找每個元素的概率都相等）為 ( )。 p=pnext。 算法填空（每空2分，共8 分）true BSTleft BSTright 六、 六、六、 六、605078903412. 12.10. 10.9. 9.8. 8.7. 7.6. 6. 以下數據結構中哪一個是非線性結構？( ) A. 隊列 　　 B. 棧 C. 線性表 　　 D. 二叉樹4. 4. 2. 2. HL){if (HL==NULL){ cerr空表endl。Int Binsch(ElemType A[ ],int n,KeyType K){int low=0。 39。 couti39。 if (ix) return 1。11. 11. 二叉樹是指度為2的____________________樹。 廣義表A= (a,(a,b),((a,b),c)),則它的深度為____________，它的長度為____________。若按行順序存放二維數組W，其起始地址為100，則二維數組元素W[6，3]的起始地址為＿________＿。A．值 B．函數 C．指針 D．引用8. 8. pnext=HL。 在帶有頭結點的單鏈表HL中，要向表頭插入一個由指針p指向的結點，則執行( )。 while (i=1) if (temp=r[i1])break。 設計在二叉排序樹上查找結點X的算法。}2. 2.ha=hanext。void mergelklist(lklist *ha,lklist *hb,lklist *amp。數據結構試卷（14）參考答案else {qnext=p。 void lklistcreate(_____________ *amp。}}14. 14.ch)。12. 12. 設二叉排序樹的高度為h，則在該樹中查找關鍵字key最多需要比較_________次。3. 3. (A) 129 (B) 219 (C) 189 (D) 2299. 設有n個關鍵字具有相同的Hash函數值，則用線性探測法把這n個關鍵字映射到HASH表中需要做（ ）次線性探測。一、選擇題(24分)1．下列程序段的時間復雜度為（ ）。i=i+1。} }2． 2． 8 設計判斷單鏈表中元素是否是遞增的算法。 設計計算二叉樹中所有結點值之和的算法。5． 5． 設某順序循環隊列中有m個元素，且規定隊頭指針F指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當前位置，則該循環隊列中最多存儲_______隊列元素。 (A) n(n1)/2 (B) n(n1) (C) n(n+1)/2 (D) (n1)/2，則順序查找的平均比較次數為（ ）。 (A) ni (B) n+l i (C) n1i (D) i3．設F是由TT2和T3三棵樹組成的森林，與F對應的二叉樹為B，TT2和T3的結點數分別為NN2和N3，則二叉樹B的根結點的左子樹的結點數為（ ）。 g[i].firstarc=p。i++) g2[i].firstarc=0。}glinklistnode。 countnode(btrchild,count)。 (13，27，38，50，76，49，65，97)9. 9.三、填空題1. 1. 設有向圖中不存在有向邊Vi,Vj，則其對應的鄰接矩陣A中的數組元素A[i][j]的值等于____________。5． 5．else__________________________。struct node *lchild。（ ） 非空的雙向循環鏈表中任何結點的前驅指針均不為空。（ ）7. 7. 隊列是一種（ ）的線性表。void level(bitree *bt,int x){ if (bt!=0){lev++。i++,j++) t[j]=s[i]。 sdata=qdata。 q!=0。amp。數據結構試卷（十一） if (ij) {r[j]=r[i]。 struct record x=r[s]。（ ）6．對連通圖進行深度優先遍歷可以訪問到該圖中的所有頂點。 (C) topnext=top。 (A) 先序遍歷 (B) 中序遍歷 (C) 后序遍歷 (D) 層次遍歷5．設按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結點的左孩子結點的編號為（ ）。 (A) 2n (B) n (C) n/2 (D) n(n1)2．設無向圖G中有n個頂點，則該無向圖的最小生成樹上有（ ）條邊。 (A) 1 (B) 2 (C) 3 (D) 4，則刪除棧頂元素的操作序列為（ ）。（ ）3．設某堆中有n個結點，則在該堆中插入一個新結點的時間復雜度為O(log2n)。（ ） 設指針變量p指向雙向鏈表中的結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為_________=p；sright=pright；__________=s； prightleft=s；（設結點中的兩個指針域分別為left和right）。 設完全有向圖中有n個頂點，則該完全有向圖中共有________條有向條；設完全無向圖中有n個頂點，則該完全無向圖中共有________條無向邊。 設關鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個元素開始進行篩選。 解決散列表沖突的兩種方法是________________和__________________。 設一棵三叉樹中有50個度數為0的結點，21個度數為2的結點，則該二叉樹中度數為3的結點數有______個。 高度為h的完全二叉樹中最少有________個結點，最多有________個結點。 設有一組初始關鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結束后的結果的是__________________________________。 設有一組初始關鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結束后的結果的是__________________________________。 設一棵二叉樹的前序序列為ABC，則有______________種不同的二叉樹可以得到這種序列。}。 if (ij) {r[i]=r[j]。2. 2. 設計在順序存儲結構上實現求子串算法。 int min,t。p=pnext) if(minpdata){min=pdata。 else if (start+count1length) printf(Too characters to be copied)。typedef struct node{int key。一、選擇題(30分)1. 1. (A) 串中不同字符的個數 (B) 串中不同字母的個數 (C) 串中所含字符的個數 (D) 串中不同數字的個數2. 2.（ ）4. 4. 二維數組和多維數組均不是特殊的線性結構。tdata=k。4． 4． 完全二叉樹中第5層上最少有__________個結點，最多有_________個結點。數據結構試卷（12）參考答案 pnext=s4. 4.void countnode(bitree *bt,int amp。typedef struct node1{int info。 glinklistnode *p。j++)if ([i][j]==1){p=(glinklistnode *)malloc(sizeof(glinklistnode))。}}數據結構試卷（13） (A) ni (B) n1i (C) n+l i (D) 不能確定8．設散列表中有m個存儲單元，散列函數H(key)= key % p，則p最好選擇（ ）。 (A) 4 (B) 5 (C) 6 (D) 7二、填空題(30分)1． 1． 設一組初始記錄關鍵字序列為(20，12，42，31，18，14，28)，則根據這些記錄關鍵字構造的二叉排序樹的平均查找長度是_______________________________。8． 8． 設無向圖G（如右圖所示），則其最小生成樹上所有邊的權值之和為_________________。五、算法設計題(20分)1． 1．3． 3．s){ if(bt!=0) {s=s+btdata。amp。j=j1。 q=p,p=pnext)if(qdatapdata) return(0)。 (A) 10 (B) 19 (C) 28 (D) 556．設一棵m叉樹中有N1個度數為1的結點，N2個度數為2的結點，……，Nm個度數為m的結點，則該樹中共有（ ）個葉子結點。9. 9. 設散列表的長度為8，散列函數H(k)=k % 7，用線性探測法解決沖突，則根據一組初始關鍵字序列(8，15，16，22，30，32)構造出的散列表的平均查找長度是________。13. 13.}bitree。 btdata=ch。typedef struct node {int data。(pdata))。 else {snext=ha。hb=hbnext。 return(0)。}數據結構（十五）一、 C. pnext=HL。 對線性表，在下列哪種情況下應當采用鏈表表示？( ) 4. 4. AOV網是一種（ ）。A．行號 B．列號 C．元素值 D．非零元素個數9. 9. 數據結構是指數據及其相互之間的______________。 寫出它的三元組線性表；（2） （2）2. 2.3. 3.若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進行排序，試給出得到的拓樸排序的序列。 int Prime(int n){ int i=1。 edgenode* p=GL[k]。五、 五、 //在右子表上繼續查找}return 1。數據結構15參考答案一、 一、 填空題（每空1分，共26分）1. 1. 聯系 圖（或圖結構）2. 2. 尾 首3. 3. top==04. 4. O（1） O（n）5. 5. 128 44 1086. 6. 3 3 7. 7. 655151321452515637 圖7有序 n18. 8. 有序序列 后綴表達式（或逆波蘭式）9. 9. 2n n1 n+110. 10. 開放定址法 鏈接法12. 12. 運算題（每題6分，共24分）1. 1. （1） ((1,5,1),(3,2,1),(4,5,2),(5,1,5),(6,3,7)) (3分)（2） 三元組線性表的順序存儲表示如圖7示。五、 五、delete p。 A．688 B．678 C．692 D．6965. 5. 通常從四個方面評價算法的質量：_________、_________、_________和_________。 一