山大網(wǎng)絡教育《數(shù)據(jù)結(jié)構(gòu)》(-C-卷)

數(shù)據(jù)結(jié)構(gòu)模擬卷 一、單項選擇題1數(shù)據(jù)結(jié)構(gòu)是（）。A一種數(shù)據(jù)類型B數(shù)據(jù)的存儲結(jié)構(gòu)C一組性質(zhì)相同的數(shù)據(jù)元素的集合D相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2算法分析的目的是（B）。A辨別數(shù)據(jù)結(jié)構(gòu)的合理性B評價算法的效率C研究算法中輸入與輸出的關(guān)系D鑒別算法的可讀性3在線性表的下列運算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運算是（D）。A插入B刪除C排序D定位4若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則可能出現(xiàn)的出棧序列為（B）。A3，2，6，1，4，5B3，4，2，1，6，5C1，2，5，3，4，6D5，6，4，2，3，15設(shè)串sl=Data Structures with Java,s2=it，則子串定位函數(shù)index(s1,s2)的值為（D）。A15B16C17D186二維數(shù)組A89按行優(yōu)先順序存儲，若數(shù)組元素A23的存儲地址為1087，A47的存儲地址為1153，則數(shù)組元素A67的存儲地址為（A）。A1207B1209C1211D12137在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（A）。A隊列B棧C線性表D有序表8在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系（B）。A不一定相同B都相同C都不相同D互為逆序9若采用孩子兄弟鏈表作為樹的存儲結(jié)構(gòu)，則樹的后序遍歷應采用二叉樹的（C）。A層次遍歷算法B前序遍歷算法C中序遍歷算法D后序遍歷算法10若用鄰接矩陣表示一個有向圖，則其中每一列包含的1的個數(shù)為（A）。A圖中每個頂點的入度B圖中每個頂點的出度C圖中弧的條數(shù)D圖中連通分量的數(shù)目11圖的鄰接矩陣表示法適用于表示（C）。A無向圖B有向圖C稠密圖D稀疏圖12在對n個關(guān)鍵字進行直接選擇排序的過程中，每一趟都要從無序區(qū)選出最小關(guān)鍵字元素，則在進行第i趟排序之前，無序區(qū)中關(guān)鍵字元素的個數(shù)為（D）。AiBi+1Cn-iDn-i+1二、填空題1棧是_操作受限_的線性表，其運算遵循_后進先出_的原則。2_棧_是限定僅在表尾進行插入或刪除操作的線性表。3. 一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是_3 1 2 _。4二叉樹由_(1)根節(jié)點_，_(2)左子樹_，_(3)右子樹_三個基本單元組成。5在二叉樹中，指針p所指結(jié)點為葉子結(jié)點的條件是_p-lchild=null & p-rchild=null _。6具有256個結(jié)點的完全二叉樹的深度為_9_。7已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹有_10_個葉子結(jié)點。8若不考慮基數(shù)排序，則在排序過程中，主要進行的兩種基本操作是關(guān)鍵字的_ 比較_和記錄的_移動_。9.分別采用堆排序，快速排序，冒泡排序和歸并排序，對初態(tài)為有序的表，則最省時間的是_冒泡_算法，最費時間的是_快速_算法。10不受待排序初始序列的影響，時間復雜度為O(N2)的排序算法是_簡單選擇排序_，在排序算法的最后一趟開始之前，所有元素都可能不在其最終位置上的排序算法是_直接插入排序_。 三、解答題1某廣義表的表頭和表尾均為（a,(b,c)），畫出該廣義表的圖形表示。2已知二叉樹的先序序列和中序序列分別為HDACBGFE和ADCBHFEG。（1）畫出該二叉樹；（2）畫出與（1）求得的二叉樹對應的森林。3已知帶權(quán)圖的鄰接表如下所示，其中邊表結(jié)點的結(jié)構(gòu)為：依此鄰接表從頂點C出發(fā)進行深度優(yōu)先遍歷。（1）畫出由此得到的深度優(yōu)先生成樹；（2）寫出遍歷過程中得到的從頂點C到其它各頂點的帶權(quán)路徑及其長度。參考答案：1. 2.(1)(2)3.(1)(2)頂點C到頂點A的帶權(quán)路徑為（C,D,B,A），其長度為8+20+11=39頂點C到頂點B的帶權(quán)路徑為（C,D,B），其長度為8+20=28頂點C到頂點D的帶權(quán)路徑為（C,D），其長度為8頂點C到頂點E的帶權(quán)路徑為（C,D,B,F,E），其長度為8+20+9+14=51頂點C到頂點F的帶權(quán)路徑為（C,D,B,F），其長度為8+20+9=37四、算法設(shè)計題1已知中序線索二叉樹T右子樹不空。設(shè)計算法，將S所指的結(jié)點作為T的右子樹中的一個葉子結(jié)點插入進去，并使之成為TT的右子樹的（中序序列）第一個結(jié)點（同時要修改相應的線索關(guān)系）。2寫出在中序線索二叉樹里；找指定結(jié)點在后序下的前驅(qū)結(jié)點的算法。參考答案：1.答案：題目分析若使新插入的葉子結(jié)點S成T右子樹中序序列的第一個結(jié)點，則應在T的右子樹中最左面的結(jié)點（設(shè)為p）處插入，使S成為結(jié)點p的左子女。則S的前驅(qū)是T，后繼是p.void ThrTreeInsert(BiThrTree T,S)/在中序線索二叉樹T的右子樹上插入結(jié)點S，使S成為T右子樹中序遍歷第一個結(jié)點p=T-rchild; /用p去指向T的右子樹中最左面的結(jié)點while(p-ltag=0) p=p-lchild;S-ltag=1;S-rtag=1; /S是葉子，其左右標記均為1S-lchild=T;S-rchild=p;/S的前驅(qū)是根結(jié)點T，后繼是結(jié)點pp-lchild=S;p-ltag=0; /將p的左子女指向S ，并修改左標志為0/結(jié)束 ThrTreeInsert2答案：題目分析在后序序列中，若結(jié)點p有右子女，則右子女是其前驅(qū)，若無右子女而有左子女，則左子女是其前驅(qū)。若結(jié)點p左右子女均無，設(shè)其中序左線索指向某祖先結(jié)點f（p是f右子樹中按中序遍歷的第一個結(jié)點），若f有左子女，則其左子女是結(jié)點p在后序下的前驅(qū)；若f無左子女，則順其前驅(qū)找雙親的雙親，一直繼續(xù)到雙親有左子女（這時左子女是p的前驅(qū)）。還有一種情況，若p是中序遍歷的第一個結(jié)點，結(jié)點p在中序和后序下均無前驅(qū)。BiThrTree InPostPre (BiThrTree t,p)/在中序線索二叉樹t中，求指定結(jié)點p在后序下的前驅(qū)結(jié)點qBiThrTree q; if (p-rtag=0) q=p-rchild; /若p有右子女，則右子女是其后序前驅(qū) else if (p-ltag=0) q=p-lchild; /若p無右子女而有左子女，左子女是其后序前驅(qū)。else if(p-lchild=null) q=null;/p是中序序列第一結(jié)點，無后序前驅(qū)else /順左線索向上找p的祖先，若存在，再找祖先的左子女 while(p-ltag=1 &