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

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