數(shù)據(jù)結(jié)構(gòu)題庫(kù)

1、數(shù)據(jù)結(jié)構(gòu)(課程代碼 02331)一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1、對(duì)順序存儲(chǔ)的線性表，設(shè)其長(zhǎng)度為n，在任何位置上插入或刪除操作都是等概率的。插入一個(gè)元素時(shí)平均要移動(dòng)表中的（A ）個(gè)元素。A、n/2 B、(n+1)/2 C、(n 1)/2 D、n2、 一個(gè)向量(一種順序表)第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是_B_。A、100 B、108 C、110 D、1203、一個(gè)棧的入棧序列a，b，c，d，e，則棧的不可能的輸出序列是_C_。

2、A、 edcba B、 decba C、 dceab D、 abcde 4、若已知一個(gè)棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為_C_。 A、 i B、 n-i C、 n-i+1 D、 n-i-15、判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m）為空的條件是_C_。A、rear - front= =m B、rear-front-1= =mC、front= = rear D、front= = rear+16、 判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m, m= =Maxsize-1）為滿隊(duì)列的條件是_A_。A、(rear- front)+ Maxsize)% Maxsi

3、ze = =mB、rear-front-1= =m C、front= =rear D、front= = rear+17、 循環(huán)隊(duì)列用數(shù)組A0，m-1存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是_A_。A、 (rear-front+m)%m B、 rear-front+1C、 rear-front-1 D、 rear-front8、設(shè)串的長(zhǎng)度為n，則它的子串個(gè)數(shù)為 D 。A、nB、n(n+1)C、n(n+1)/2 D、n(n+1)/2+19、S1=“ABCD”，S2=“CD”則S2在S3中的位置是（C ）A、1 B、2 C、3 D、410、設(shè)數(shù)組a76的基地址

4、為1024,每個(gè)元素占2個(gè)存儲(chǔ)單元,若以行序?yàn)橹餍蝽樞虼鎯?chǔ),則元素a24的存儲(chǔ)地址是_B_。A、1054 B、1056 C、1058 D、109811、 二維數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A47的起始地址為_B_。A、 SA+141 B、 SA+180 C、 SA+222 D、 SA+22512、二維數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的字節(jié)數(shù)是_C_。A、 80 B、 100 C、240 D、 2701

5、3、 二維數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，數(shù)組元素A74的起始地址為_C_。A、 SA+141 B、 SA+144 C、 SA+222 D、 SA+22514、假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15個(gè)，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)個(gè)數(shù)為 B 。A、15 B、16 C、17 D、4715、按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的不同形狀的二叉樹有_C_種。A、3 B、 4 C、 5 D、 616、深度為5的二叉樹至多有_C_個(gè)結(jié)點(diǎn)。A、16 B、32 C、31 D、1017、設(shè)高度為h的二叉樹上只有度為0

6、和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為_ A _。A、 2h B、 2h-1 C、 2h+1 D、 h+118、 對(duì)一個(gè)滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h，則_D_ 。A、 n=h+m B、 h+m=2n C、 m=h-1 D、 n=2 h-119、 如果某二叉樹的前根次序遍歷結(jié)果為stuwv，中序遍歷為uwtvs，那么該二叉樹的后序?yàn)開C_。 A、 uwvts B、 vwuts C、 wuvts D、 wutsv20、 某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是_D_。A、 bdgcefha B、

7、gdbecfha C、 bdgaechf D、 gdbehfca21、 已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是_D_。A、 acbed B、 decab C、 deabc D、 cedba22、由帶權(quán)為9,2,5,7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長(zhǎng)度為( D )。A、 23 B、 37 C、 46 D、 4423.在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹第i層上，最多具有( C )個(gè)結(jié)點(diǎn)。 A、2i B、 2i+1 C、 2i-1 D、 2n24、在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的倍數(shù)為_C_。A、 1/2 B、 1 C、 2 D、 4

8、 25、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的_B_倍。A、 1/2 B、 1 C、 2 D、 426、一個(gè)有n個(gè)頂點(diǎn)的無向圖的邊數(shù)最多為_C_。A、 n B、 n(n-1) C、 n(n-1)/2 D、 2n27、具有4個(gè)頂點(diǎn)的無向完全圖有_A_條邊。A、 6 B、 12 C、 16 D、 2028、具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有_A_條邊才能確保是一個(gè)連通圖。A、 5 B、 6 C、 7 D、 829、在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要_C_條邊。A、 n B、 n+1 C、 n-1 D、 n/230、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則

9、該矩陣的大小是_D_。A、 n B、 (n-1)2 C、 n-1 D、 n231、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為_A_。A、 n B、 n+1 C、 n-1 D、 n+e32、判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用_D_。A、 求關(guān)鍵路徑的方法 B、 求最短路徑的Dijkstra方法C、 寬度優(yōu)先遍歷算法 D、 深度優(yōu)先遍歷算法33、關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中 A 。A、從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 B、從源點(diǎn)到匯點(diǎn)的最短路徑C、最長(zhǎng)的回路 D、最短的回路34、一個(gè)有n個(gè)頂點(diǎn)的無向連通圖，它所包含的連通分量個(gè)數(shù)為 B 。A、0B、1

10、C、nD、n+135對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度為k1,、出度為k2，則對(duì)應(yīng)鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為 B 。A、k1B、k2C、k1-k2D、k1+k236、對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度為k1,、出度為k2，則對(duì)應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為 A 。A、k1B、k2C、k1-k2D、k1+k237、具有n個(gè)頂點(diǎn)的有向圖最多有( B )條邊。 A、n B、 n(n-1) C、 n(n+1) D、 38、 n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有( A )條邊。 A、 n B、 n-1 C、 n+1 D、 n(n-1)39、 在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為s，則所有頂點(diǎn)

11、的入度之和為( A )。 A、s B、 s-1 C、 s+1 D、 n40、 在一個(gè)無向圖中，若兩個(gè)頂點(diǎn)之間的路徑長(zhǎng)度為k，則該路徑上的頂點(diǎn)數(shù)為( B )。 A、k B、 k+1 C、 k+2 D、 2k41、一個(gè)圖中包含k個(gè)連通分量，若按深度優(yōu)先(DFS)搜索方法訪問所有結(jié)點(diǎn)，則必須調(diào)用(A )次深度優(yōu)先遍歷算法。 A、k B、 1 C、 k-1 D、 k+142、設(shè)G1=(V1,E1)和G2=(V2,E2)為兩個(gè)圖， V1ÍV2,E1ÍE2,則稱（A ）A、G1是G2的子圖 B、G2是G1的子圖C、G1是G2的連通分量 D、G2是G1的連通分量43、采用順序查找方法查找

12、長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為_C_.A、 n B、 n/2 C、 (n+1)/2 D、 (n-1)/244、采用二分查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為_D_。A、O（n2） B、 O(nlog2n) C、 O(n) D、 O(log2n)45、有一個(gè)有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當(dāng)二分查找值82為的結(jié)點(diǎn)時(shí)，_C_次比較后查找成功。A、 1 B、 2 C、 4 D、 846、有一個(gè)長(zhǎng)度為12的有序表，按二分查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為_B_。A、 35/12 B

13、、 37/12 C、 39/12 D、 43/1247、對(duì)于18個(gè)元素的有序表采用二分(折半)查找，則查找A3的比較序列的下標(biāo)為( D )。 A、1、2、3 B、9、5、2、3 C、9、5、3 D、9、4、2、348、 一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為_B_。A、 79，46，56，38，40，80 B、 38，40,56，79，46，84，C、 84，79，56，46，40，38 D、 84，56，79，40，46，3849、 一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次

14、劃分結(jié)果為_C_。A、 38，40，46，56，79，84 B、 40，38，46，79，56，84C、 40，38，46，56，79，84 D、 40，38，46，84，56，7950、 一組記錄的排序碼為（25，48，16，35，79，82，23，40，36，72），其中含有5個(gè)長(zhǎng)度為2的有序表，按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為_A_。A、 16，25，35，48，23，40，79，82，36，72 B、 16，25，35，48，79，82，23，36，40，72C、 16，25，48，35，79，82，23，36，40，72D、 16，25，35，48，79，23，36，4

15、0，72，8251、 下述幾種排序方法中，要求內(nèi)存量最大的是_D_。A、 插入排序 B、 選擇排序 C、 快速排序 D、 歸并排序52、在對(duì)n個(gè)元素進(jìn)行簡(jiǎn)單選擇排序過程中，第i趟需從( A )個(gè)元素中選擇出最小值元素。A、n-i+1 B、 n-i C、i D、 i+153、n個(gè)記錄直接插入排序所需的記錄最小比較次數(shù)是 ( A ) A、 n-1 B、 2(n-1) C、 (n+2)(n-1)/2 D、 n54、一組記錄的關(guān)鍵字為（45，80，55，40，42，85），則利用堆排序的方法建立的初始堆為( B )。 A、（80，45，55，40，42，85） B、（85，80，55，40，42，45

16、） C、（85，80，55，45，42，40） D、（85，55，80，42，45，40）55、一組記錄的關(guān)鍵字為（45，80，55，40，42，85），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到一次劃分結(jié)果是( C )。 A、（40，42，45，55，80，85） B、（42，40，45，80，55，85） C、（42，40，45，55，80，85） D、（42，40，45，85，55，80）56將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為（ A ）。A）98B）99C）50D）4857一組記錄的排序

17、碼為(48,24,18,53,16,26,40)，采用冒泡排序法進(jìn)行排序，則第一趟排序需要進(jìn)行記錄交換的次數(shù)是（ C ）。A）3B）4C）5D）658采用分塊查找時(shí)，如某線性表中共有256個(gè)元素，查找每個(gè)元素的概率相同，假設(shè)采用順序查找來確定元素所在的塊，則每塊包含（ C ）個(gè)結(jié)點(diǎn)時(shí)，平均查找長(zhǎng)度最小。A）256B）15C）16D）1859對(duì)于有向圖的鄰接矩陣，該圖共有（ B ）條弧。A）5B）4C）3D）260由帶權(quán)9、1、3、5、6的五個(gè)葉子結(jié)點(diǎn)生成的哈夫曼樹的帶權(quán)路徑長(zhǎng)度為（ C ）。A）50B）60C）52D）65二、填空題(本大題共10小題，每小題2分，共20分)請(qǐng)?jiān)诿啃☆}的空格中填

18、上正確答案。錯(cuò)填、不填均無分。1、下面程序段的時(shí)間復(fù)雜度是_ O(m*n) _。for (i=0;i<n;i+)for (j=0;j<m;j+)aij=0;2、下面程序段的時(shí)間復(fù)雜度是_ O()_。i=s=0while(s<n) i+; /* i=i+1 */ s+=i;/* s=s+i */3、下面程序段的時(shí)間復(fù)雜度是_ O(n2)_。s=0;for (i=0;i<n;i+)for (j=0;j<n;j+)s+=bij;sum=s;4、下面程序段的時(shí)間復(fù)雜度是_ O(log3n) _。i=1;while (i<=n)i=i*3;5、在順序表中，若第一個(gè)元素

19、所在的地址為L(zhǎng)oc(a1)，每個(gè)元素在內(nèi)存中占有L個(gè)存儲(chǔ)單元，則元素ai在內(nèi)存中的地址Loc(ai)=_ Loc(a1)+(i-1)*L _。6、向一個(gè)長(zhǎng)度為n的順序表的第i個(gè)元素（1in+1）之前插入一個(gè)元素時(shí)，需向后移動(dòng)_ n-i+1_個(gè)元素。7、向一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（1in）時(shí)，需向前移動(dòng)_ n-i _個(gè)元素。8、串s=abcdef,s1=cde，s1在s中的位置為_3 _。9、 已知二維數(shù)組Amn采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC(A00)，則Aij的地址是_ LOC (A00)+(n*i+j)*k _。10、 二維數(shù)組A1

20、020采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元并且A00的存儲(chǔ)地址是200，則A612的地址是_326_。11、 二維數(shù)組A1020510采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且A105的存儲(chǔ)地址是1000，則A189的地址是_1208_。12、現(xiàn)有一個(gè)n階的對(duì)稱矩陣ann，現(xiàn)將其壓縮存儲(chǔ)在一個(gè)一維數(shù)組sm中，則m=_ n(n+1)/2_，若以行序?yàn)橹餍蜻M(jìn)行存儲(chǔ)，則元素aij(i>=j)在s中的下標(biāo)k=_ i(i-1)/2+j-1_。13、在一個(gè)m*n的矩陣中，若a00是第一個(gè)元素，則aij是第_ i*n+j _個(gè)元素。14、在二叉樹中，某一結(jié)點(diǎn)x的編號(hào)為i，x若有雙親，其

21、雙親編號(hào)應(yīng)為_ _；x若有左孩子，其左孩子編號(hào)應(yīng)為_2*i _；x若有右孩子，其右孩子應(yīng)為_2*i+1_。15、8層完全二叉樹至少有 128 個(gè)結(jié)點(diǎn)，擁有100個(gè)結(jié)點(diǎn)的完全二叉樹的最大層數(shù)為 7 。16、n個(gè)頂點(diǎn)的連通圖至少_ n-1 _條邊。17、在無向圖G的鄰接矩陣A中，若Aij等于1，則Aji 等于_1_。18、一個(gè)無向圖有n個(gè)頂點(diǎn)和e條邊，則所有頂點(diǎn)的度的和即(表示頂點(diǎn)i的度)= 2e 。19、在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá) 2(n-1) 。20、 對(duì)于長(zhǎng)度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為_ O（n）_；若采用折半法查找，則時(shí)間復(fù)雜度為_ O(log2n)_。

22、21、已知有序表為（12，18，24，35，47，50，62，83，90，115，134），當(dāng)用折半查找90時(shí)，需進(jìn)行 2 次查找可確定成功；查找47時(shí)，需進(jìn)行 4 次查找成功；查找100時(shí)，需進(jìn)行 3 次查找才能確定不成功。22、平衡二叉排序樹上任一結(jié)點(diǎn)的平衡因子只可能是 0 、 1 或 -1 。23、用起泡法對(duì)n個(gè)關(guān)鍵碼排序，在最好情況下，只需做 n-1 次比較；在最壞的情況下要做 n(n-1)/2 次比較。24、設(shè)字符串S1= “ABCDEF”，S2= “PQRS”，則運(yùn)算S=CONCAT（SUB（S1，2，LEN（S2），SUB（S1，LEN（S2），2）后的串值為_“BCDEDE”_

23、。25、在一棵二叉排序樹上按_中序_遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。26、在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的_2_倍。27、在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有_ n(n-1)/2_條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有_ n(n-1)_條邊。28、假定一個(gè)有向圖的頂點(diǎn)集為a,b,c,d,e,f，邊集為<a,c>, <a,e>, <c,f>, <d,c>, <e,b>, <e,d>，則出度為0的頂點(diǎn)個(gè)數(shù)為_2_，入度為1的頂點(diǎn)個(gè)數(shù)為_4_。29、在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通所有頂點(diǎn)則至少需要

24、_ n-1_條邊。30、若一個(gè)圖的頂點(diǎn)集為a,b,c,d,e,f，邊集為(a,b),(a,c),(b,c),(d,e)，則該圖含有_3_個(gè)連通分量。31、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的連通圖，其生成樹中的頂點(diǎn)數(shù)和邊數(shù)分別為_ n _和_ n-1_。32、假定一個(gè)順序表的長(zhǎng)度為40，并假定查找每個(gè)元素的概率都相同，則在查找成功情況下的平均查找長(zhǎng)度_20.5_，在查找不成功情況下的平均查找長(zhǎng)度_41_。33、在索引查找中，假定查找表（即主表）的長(zhǎng)度為96，被等分為8個(gè)子表，則進(jìn)行索引查找的平均查找長(zhǎng)度為_11_。34、假定對(duì)長(zhǎng)度n=50的有序表進(jìn)行折半查找，則對(duì)應(yīng)的判定樹高度為_6_，最后一層的結(jié)

25、點(diǎn)數(shù)為_19 _。35、假定在索引查找中，查找表長(zhǎng)度為n，每個(gè)子表的長(zhǎng)度相等，設(shè)為s，則進(jìn)行成功查找的平均查找長(zhǎng)度為_(n/s+s)/2+1_。46、假定一組記錄為(46,79,56,38,40,84)，則利用堆排序方法建立的初始小根堆為_(38,40,56,79,46,84)_。37、假定一組記錄為(46,79,56,38,40,84)，在冒泡排序的過程中進(jìn)行第一趟排序后的結(jié)果為_(46,56,38,40,79,84)_。38、假定一組記錄為(46,79,56,64,38,40,84,43)，在冒泡排序的過程中進(jìn)行第一趟排序時(shí)，元素79將最終下沉到其后第_4_個(gè)元素的位置。39、假定一組記錄

26、為(46,79,56,38,40,80)，對(duì)其進(jìn)行快速排序的第一次劃分后的結(jié)果為_40 38 46 56 79 80_。40、假定一組記錄為(46,79,56,38,40,80,46,75,28,46)，對(duì)其進(jìn)行歸并排序的過程中，第二趟歸并后的子表個(gè)數(shù)為_3_。三、應(yīng)用題(本大題共4小題，每小題7分，共28分)1、分別畫出具有3個(gè)結(jié)點(diǎn)的樹和三個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。解：具有3個(gè)結(jié)點(diǎn)的樹有兩種不同形態(tài)。具有3個(gè)結(jié)點(diǎn)的二叉樹有以下五種不同形態(tài)。2、如下圖所示的二叉樹，試分別寫出它的順序表示和鏈接表示（二叉鏈表）。解：（1）順序表示。（2）該二叉樹的二叉鏈表表示。3、假定用于通信的電文由8個(gè)字

27、符A、B、C、D、E、F、G、H組成，各字母在電文中出現(xiàn)的概率為5、25、4、7、9、12、30、8，試以這8個(gè)字母構(gòu)造哈夫曼樹。解： 根據(jù)題意，設(shè)這8個(gè)字母對(duì)應(yīng)的權(quán)值分別為（5，25，4，7，9，12，30，8），并且n=8。步驟如下：4、假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請(qǐng)寫出該二叉樹的后序遍歷序列。解：后序序列：ACDBGJKIHFE5、已知一個(gè)無向圖的鄰接表下圖所示，要求：（1）畫出該無向圖；（2）根據(jù)鄰接表，分別寫出用DFS(深度優(yōu)先搜索)和BFS（廣度優(yōu)先搜索）算法從頂點(diǎn)V0開始遍歷該圖后所得到的遍歷序列。解：（1）該無向圖如下圖所

28、示。（2）根據(jù)該無向圖的鄰接表表示，從頂點(diǎn)V0開始的深度優(yōu)先遍歷序列為：V0、V2、V3、V1、V4、V6、V5。廣度優(yōu)先遍歷序列為V0、V2、V5、V6、V1、V3、V4。6、如下圖所示的一個(gè)網(wǎng)，按照Prim方法，從頂點(diǎn)V1 出發(fā)，求該網(wǎng)的最小生成樹的產(chǎn)生過程。 解：步驟如下：7、記錄的關(guān)鍵字序列為：63，90，70，55，67，42，98，83，10，45，58，則畫出構(gòu)造一棵二叉排序樹的過程。解：構(gòu)造二叉排序樹的過程如下圖所示。8、已知一組記錄為(46,74,53,14,26,38,86,65,27,34)，給出采用冒泡排序法進(jìn)行排序時(shí)每一趟的排序結(jié)果。解：排序過程如下：(0) 46 7

29、4 53 14 26 38 86 65 27 34(1) 46 53 14 26 38 74 65 27 34 86(2) 46 14 26 38 53 65 27 34 74 86(3) 14 26 38 46 53 27 34 65 74 86(4) 14 26 38 46 27 34 53 65 74 86(5) 14 26 38 27 34 46 53 65 74 86(6) 14 26 27 34 38 46 53 65 74 86(7) 14 26 27 34 38 46 53 65 74 869、已知一組記錄為(46,74,53,14,26,38,86,65,27,34)，給出采

30、用直接插入排序法進(jìn)行排序時(shí)每一趟的排序結(jié)果。解：排序過程如下所示：(0) 46 74 53 14 26 38 86 65 27 34(1) 46 74 53 14 26 38 86 65 27 34(2) 46 53 74 14 26 38 86 65 27 34(3) 14 46 53 74 26 38 86 65 27 34(4) 14 26 46 53 74 38 86 65 27 34(5) 14 26 38 46 53 74 86 65 27 34(6) 14 26 38 46 53 74 86 65 27 34(7) 14 26 38 46 53 65 74 86 27 34(8)

31、 14 26 27 38 46 53 65 74 86 34(9) 14 26 27 34 38 46 53 65 74 8610、關(guān)鍵字序列為 （47，7，29，11，16，92，22，8，3，50，37，89，94，21），哈希函數(shù)為：Hash(key)=key mod 11，用拉鏈表處理沖突。解：建表如下：11、已知如下圖所示的有向圖，請(qǐng)給出該圖的(1) 每個(gè)頂點(diǎn)的出/入度；(2) 鄰接矩陣；(3) 鄰接表；解：(1) 每個(gè)頂點(diǎn)的出/入度是：(2) 鄰接矩陣：(3) 鄰接表：12、已知圖的鄰接矩陣如下圖所示。試分別畫出自頂點(diǎn)A出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。解：（1）深

32、度優(yōu)先搜索如下所示：(2)廣度優(yōu)先搜索如下所示：13、已知一組記錄為(46,74,53,14,26,38,86,65,27,34)，給出采用歸并排序法進(jìn)行排序時(shí)每一趟的排序結(jié)果。解：排序過程如下所示：(0) 46 74 53 14 26 38 86 65 27 34(1) 46 74 14 53 26 38 65 86 27 34(2) 14 46 53 74 26 38 65 86 27 34(3) 14 26 38 46 53 65 74 86 27 34(4) 14 26 27 34 38 46 53 65 74 8614、假定一個(gè)待哈希存儲(chǔ)的線性表為(32,75,29,63,48,94

33、,25,36,18,70,49,80)，哈希地址空間為HT12，若采用除留余數(shù)法構(gòu)造哈希函數(shù)和拉鏈法處理沖突，試畫出最后得到的哈希表，并求出平均查找長(zhǎng)度。解：H(K)=K % 11，哈希表如下圖所示，平均查找長(zhǎng)度17/12。15、對(duì)于一個(gè)無向圖如下所示，假定采用鄰接矩陣表示，試分別寫出從頂點(diǎn)0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。解：（1）深度優(yōu)先搜索序列：0,1,2,8,3,4,5,6,7,9（2）廣度優(yōu)先搜索序列：0,1,4,2,7,3,8,6,5,916、已知如下圖所示的一個(gè)網(wǎng)，按照Kruskal方法，求該網(wǎng)的最小生成樹的產(chǎn)生過程。解：過程如下圖所示。四

34、、算法設(shè)計(jì)題(本大題共2小題，每小題11分，共22分)1、編寫一個(gè)單鏈表類的成員函數(shù)，實(shí)現(xiàn)刪除不帶頭結(jié)點(diǎn)的單鏈表中數(shù)據(jù)域值等于x的第一個(gè)結(jié)點(diǎn)的操作。若刪除成功，則返回被刪除結(jié)點(diǎn)的位置；否則，返回-1。算法設(shè)計(jì)如下： public int remove(Object x) Node p = head;/ 初始化,p指向首結(jié)點(diǎn)Node q=null; /q用來記錄p的前驅(qū)結(jié)點(diǎn) int j = 0; /j為計(jì)數(shù)器/ 從單鏈表中的首結(jié)點(diǎn)元素開始查找，直到p.getData()指向元素x或到達(dá)單鏈表的表尾while (p != null && !p.getData().equals(x)

35、 q=p; p = p.getNext();/ 指向下一個(gè)元素 +j;/ 計(jì)數(shù)器的值增1 if (p!=null&&q=null) /刪除的是單鏈表中的首結(jié)點(diǎn) head=p.getNext(); else if (p != null) / 刪除的是單鏈表中的非首結(jié)點(diǎn) q.setNext(p.getNext(); else return -1;/值為x的結(jié)點(diǎn)在單鏈表中不存在 return j; 2、編寫一個(gè)單鏈表類的成員函數(shù)，實(shí)現(xiàn)刪除帶頭結(jié)點(diǎn)的單鏈表中數(shù)據(jù)域值等于x的所有結(jié)點(diǎn)的操作。要求函數(shù)返回被刪除結(jié)點(diǎn)的個(gè)數(shù)。算法設(shè)計(jì)如下：public int removeAll(Object

36、 x) Node p = head.getNext();/ 初始化,p指向首結(jié)點(diǎn),j為計(jì)數(shù)器Node q = head; / 用來記錄p的前驅(qū)結(jié)點(diǎn)int j = 0;/ 用來記錄被刪除結(jié)點(diǎn)的個(gè)數(shù)while (p != null) / 從單鏈表中的首結(jié)點(diǎn)開始對(duì)整個(gè)鏈表遍歷一次if (p.getData().equals(x) q.setNext(p.getNext();+j;/ 計(jì)數(shù)器的值增1 elseq = p;p = p.getNext();/ 指向下一個(gè)元素return j;/ 返回被刪除結(jié)點(diǎn)的個(gè)數(shù)3、試設(shè)計(jì)算法，用插入排序方法對(duì)單鏈表進(jìn)行排序。算法設(shè)計(jì)如下： public static

37、void insertSort(LinkList L) Node p, q, r, u; p = L.getHead().getNext(); L.getHead().setNext(null); /置空表，然后將原鏈表結(jié)點(diǎn)逐個(gè)插入到有序表中 while (p != null) /當(dāng)鏈表尚未到尾，p為工作指針 r = L.getHead(); q = L.getHead().getNext(); while (q != null && (Integer.parseInt(String) q.getData() <= (Integer.parseInt(String) p.

38、getData() /查P結(jié)點(diǎn)在鏈表中的插入位置，這時(shí)q是工作指針 r = q; q = q.getNext(); u = p.getNext(); p.setNext(r.getNext(); r.setNext(p); p = u; /將P結(jié)點(diǎn)鏈入鏈表中，r是q的前驅(qū)，u是下一個(gè)待插入結(jié)點(diǎn)的指針 4、試設(shè)計(jì)算法，用選擇排序方法對(duì)單鏈表進(jìn)行排序。算法設(shè)計(jì)如下：/單鏈表選擇排序算法 public static void selectSort(LinkList L) /p為當(dāng)前最小,r為此過程中最小,q為當(dāng)前掃描接點(diǎn) Node p, r, q; Node newNode = new Node()

39、; newNode.setNext(L.getHead(); L.setHead(newNode); /制造一個(gè)最前面的節(jié)點(diǎn)newNode，解決第一個(gè)節(jié)點(diǎn)的沒有前續(xù)節(jié)點(diǎn)需要單獨(dú)語句的問題。 p = L.getHead(); while (p.getNext().getNext() != null) r = p.getNext(); q = p.getNext().getNext(); while (q.getNext() != null) if (Integer.parseInt(String) q.getNext().getData() <= (Integer.parseInt(Str

40、ing) r.getNext().getData() r = q; q = q.getNext(); if (r != p) /交換p與r Node swap = r.getNext(); r.setNext(r.getNext().getNext(); /r的next指向其后繼的后繼 swap.setNext(p.getNext(); p.setNext(swap); /p的后繼為swap p = p.getNext(); /while p.setNext(null); 5、試設(shè)計(jì)算法，使用非遞歸方法實(shí)現(xiàn)快速排序。算法設(shè)計(jì)如下： public static void Nonrecursive

41、QuickSort(int ary) if (ary.length < 2) return; /數(shù)組棧：記錄著高位和低位的值 int stack = new int2ary.length; /棧頂部位置 int top = 0; /低位，高位，循環(huán)變量，基準(zhǔn)點(diǎn) /將數(shù)組的高位和低位位置入棧 stack1top = ary.length - 1; stack0top = 0; top+; /要是棧頂不空，那么繼續(xù) while (top != 0) /將高位和低位出棧 /低位：排序開始的位置 top-; int low = stack0top; /高位：排序結(jié)束的位置 int high =

42、stack1top; /將高位作為基準(zhǔn)位置 /基準(zhǔn)位置 int pivot = high; int i = low; for (int j = low; j < high; j+) if (aryj <= arypivot) int temp = aryj; aryj = aryi; aryi = temp; i+; /如果i不是基準(zhǔn)位，那么基準(zhǔn)位選的就不是最大值 /而i的前面放的都是比基準(zhǔn)位小的值，那么基準(zhǔn)位 /的值應(yīng)該放到i所在的位置上 if (i != pivot) int temp = aryi; aryi = arypivot; arypivot = temp; if (

43、i - low > 1) /此時(shí)不排i的原因是i位置上的元素已經(jīng)確定了，i前面的都是比i小的，i后面的都是比i大的 stack1top = i - 1; stack0top = low; top+; /當(dāng)high-i小于等于1的時(shí)候，就不往棧中放了，這就是外層while循環(huán)能結(jié)束的原因 /如果從i到高位之間的元素個(gè)數(shù)多于一個(gè)，那么需要再次排序 if (high - i > 1) /此時(shí)不排i的原因是i位置上的元素已經(jīng)確定了，i前面的都是比i小的，i后面的都是比i大的 stack1top = high; stack0top = i + 1; top+; 6、試設(shè)計(jì)算法，判斷完全二叉樹

44、是否為大頂堆。算法設(shè)計(jì)如下：boolean checkmax(BiTreeNode t) /判斷完全二叉樹是否為大頂堆 BiTreeNode p = t; if (p.getLchild() = null && p.getRchild() = null) return true; else if (p.getLchild() != null && p.getRchild() != null) if (RecordNode) p.getLchild().getData().getKey().compareTo(RecordNode) p.getData().getKey() <= 0 && (RecordNode) p.getRchild().getData().getKey().compareTo(RecordNode) p.