1、一、圖【1】各邊權(quán)值不同的無向連通圖的最小生成樹是唯一的【2】當(dāng)各邊上的權(quán)值( 均相等 )時,BFS算法可用來解決單源最短路徑問題解析：當(dāng)權(quán)值相同，則最短路徑問題轉(zhuǎn)化為求邊數(shù)最少的問題，BFS可以保證求得源點到匯點的最少邊數(shù)【3】無向圖：若V(G)中任意兩個不同的頂點vi和vj都連通(即有路徑)，則稱G為連通圖。無向圖G的極大連通子圖稱為G的最強連通分量有向圖：有向圖G中，若對于V(G)中任意兩個不同的頂點vi和vj，都存在從vi到vj以及從vj到vi的路徑，則稱G是強連通圖。有向圖的極大強連通子圖稱為G的強連通分量。【4】無向圖存儲：鄰接矩陣、鄰接表、多重鄰接表有向圖存儲：鄰接矩陣、鄰接表、

2、十字鏈表【5】若有向圖不存在回路,即使不用訪問標(biāo)志位同一結(jié)點也不會被訪問兩次()解析：錯誤。如果一個點的入度大于1的話，就有可能被多次訪問【6】有向圖是否有環(huán)的判定算法，主要有深度優(yōu)先和拓撲排序兩種方法。【7】一個AOV網(wǎng)應(yīng)該是一個有向無環(huán)圖 ，即不應(yīng)該帶有回路，因為若帶有回路，則回路上的所有活動都無法進行。既然AOV網(wǎng)是一個有向無環(huán)圖，則其必然存在拓撲序列。【8】關(guān)鍵路徑：1）頂點表示事件，弧表示活動 2）如果頂點A->B有弧，如果讓弧表示為L，則A為L的弧尾，B為L的弧頭，即有箭頭的那一端叫頭。【9】若無向圖G = （V.E）中含7個頂點，則保證圖G在任何情況下都是連通的，則需要的邊

3、數(shù)最少是（）解析：任何情況都連通的最少邊數(shù)表示邊分布最浪費的最少邊情況，取點數(shù)減一的完全圖6*5/2=15再加一條邊得結(jié)果16【10】AOE網(wǎng)的定義：在帶權(quán)有向圖中若以頂點表示事件，有向邊表示活動，邊上的權(quán)值表示該活動持續(xù)的時間，這樣的圖簡稱為AOE網(wǎng)。從定義上來看，很容易看出兩種網(wǎng)的不同，AOV網(wǎng)的活動以頂點表示，而AOE網(wǎng)的活動以有向邊來表示，AOV網(wǎng)的有向邊僅僅表示活動的先后次序。縱觀這兩種網(wǎng)圖，其實它們總體網(wǎng)絡(luò)結(jié)構(gòu)是一樣的，僅僅是活動所表示的方式不同，因此可以猜想從AOV網(wǎng)轉(zhuǎn)換成AOE網(wǎng)應(yīng)該是可行的。AOV網(wǎng)不能有環(huán)。AOE網(wǎng)一定是有向無環(huán)圖【11】關(guān)鍵活動延期完成，必將延期整個工程完

4、成時間。如果有多條關(guān)鍵路徑，此時延期的關(guān)鍵活動所在路徑成為關(guān)鍵路徑，其他原關(guān)鍵路徑變?yōu)榉顷P(guān)鍵路徑。關(guān)鍵活動提前完成，不一定使整個工程提前完成。因為關(guān)鍵路徑可能不唯一，一條路徑上的關(guān)鍵活動提前，只能使這條路徑變?yōu)榉顷P(guān)鍵路徑，其他關(guān)鍵路徑不受影響。【12】圖G的拓撲序列唯一，則其弧數(shù)必為n-1(其中n為G的頂點數(shù))解析：錯誤。有向圖的鄰接矩陣上三角全為1即可達到拓撲唯一，那么邊數(shù)為n(n-1)/2【13】無向圖的鄰接矩陣可用一維數(shù)組存儲。解析：正確。習(xí)慣上無向圖的鄰接矩陣一般用二維數(shù)組存儲，這樣使用方便。當(dāng)然，任意二維數(shù)組都是可以用一維數(shù)組存儲的，只是用起來不方便。【14】既使有向無環(huán)圖的拓撲序列

5、唯一，也不能唯一確定該圖。解析：正確。如果頂點有多個直接后繼，排序結(jié)果通常不唯一，所以拓撲排序的結(jié)果唯一的情況是，每個頂點有唯一的前驅(qū)后繼關(guān)系。【15】用相鄰矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小與圖中結(jié)點的個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。這種說法（ 正確 ）【16】設(shè)G是一個具有6個頂點,11條邊的圖，其每個頂點的度為3或4，則圖G是什么圖？（A）A、G是平面圖； B、G不連通； C、G為偶圖(也稱二部圖)； D、G不是哈密頓圖。【17】p個頂點p條邊的連通圖中至少有多少個生成樹？解析：3個。p個頂點p條邊的連通圖中至少有多少個生成樹，連通圖相當(dāng)于在樹上多加了一條邊，

6、所以其中必然會有一個回路，生成樹的數(shù)量應(yīng)該等于回路的邊數(shù)，如果不考慮重邊和自環(huán)的情況最小的回路必然是3。【18】完全偶圖(也稱完全二部圖) 既是歐拉圖又是哈密頓圖的充分必要條件是下列哪一個？m=n且m與n都是偶數(shù)；二、樹【1】不含任何結(jié)點的空樹（ 是一棵樹也是一棵二叉樹 ）。【2】如果T1是由有序樹T轉(zhuǎn)換而來的二叉樹,那么T中結(jié)點的前序就是T1中結(jié)點的前序,T中結(jié)點的后序就是T1中結(jié)點的中序【3】樹中的結(jié)點和圖中的頂點就是指數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素解析：對。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。在計算機中作為一個整體考慮和處理。在有些情況下，數(shù)據(jù)元素也稱為元素、記錄等，數(shù)據(jù)元素用于完整的描述一個對象，如圖中的

7、頂點。數(shù)據(jù)項是組成數(shù)據(jù)元素的、有獨立含義的、不可分割的最小單位。如學(xué)生基本信息中的學(xué)號、姓名、性別等都是數(shù)據(jù)項。【4】如果有N個節(jié)點用二叉樹結(jié)構(gòu)來存儲，那么二叉樹的最小深度是多少？解析：以2為底2N的對數(shù)，向下取整【5】二叉樹在線索化后，仍不能有效求解的問題是（）。解析：后序線索二叉樹中求后序后繼。后序線索二叉樹的遍歷仍需要借助棧，但其他二者卻不需要。【6】設(shè)F是一個森林,B是由F變換得到的二叉樹。若F中有n個非終端結(jié)點,則B中右指針域為空的結(jié)點有( n+1 )個【7】在線索化二叉樹中，節(jié)點t沒有左子樹的充要條件是（ t->ltag=1 ）【8】在中序線索二叉樹中,每一非空的線索均指向其

8、祖先結(jié)點()解析：中序遍歷的順序為：左、根、右，所以對于每一非空的線索，左子樹結(jié)點的后繼為根結(jié)點，右子樹結(jié)點的前驅(qū)為根結(jié)點，再遞歸的執(zhí)行上面的過程，可得非空線索均指向其祖先結(jié)點。【9】若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（ 11 ）解析：性質(zhì)4：在任意一棵二叉樹中，若終端結(jié)點的個數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1證明：因為二叉樹中所有結(jié)點的度數(shù)均不大于2，所以結(jié)點總數(shù)(記為n)="0度結(jié)點數(shù)(n0)" + "1度結(jié)點數(shù)(n1)" + "2度結(jié)點數(shù)(n2)"。由此，得到等式一。(等式一

9、) n=n0+n1+n2另一方面，0度結(jié)點沒有孩子，1度結(jié)點有一個孩子，2度結(jié)點有兩個孩子，故二叉樹中孩子結(jié)點總數(shù)是：n1+2n2。此外，只有根不是任何結(jié)點的孩子。故二叉樹中的結(jié)點總數(shù)又可表示為等式二。(等式二) n=n1+2n2+1由(等式一)和(等式二)計算得到：n0=n2+1。原命題得證！三、數(shù)組【1】關(guān)于 int a10; 問下面哪些不可以表示 a1 的地址？A、a+sizeof(int) B、&a0+1 C、(int*)&a+1 D、(int*)(char*)&a+sizeof(int)解析：A 不正確， 在32位機器上相當(dāng)于指針運算 a + 4【2】int

10、a23 = 0;printf("%x %x %xn", a0, a1, &a12);printf("%x %x %xn", a, a + 1, &a + 1);輸出：1da6e790 1da6e79c 1da6e7a4 1da6e790 1da6e79c 1da6e7a8【3】下面有關(guān)數(shù)據(jù)結(jié)構(gòu)的說法是正確的？A、數(shù)組和鏈表都可以隨機訪問 B、數(shù)組的插入和刪除可以 O(1)C、哈希表沒有辦法做范圍檢查 D、以上說法都不正確解析：B。在數(shù)組的開頭或結(jié)尾插入和刪除 是O(1),但正常情況下為O(n)所以說數(shù)組的插入和刪除復(fù)雜度可能是O(1)。【

11、4】一個非空廣義表的表尾()A、不能是子表 B、只能是子表 C、只能是原子 D、是原子或子表解析：B。（1）數(shù)據(jù)結(jié)構(gòu)對廣義表的表頭和表尾是這樣定義的： 如果廣義表LS=（a1,a2.an）非空，則 a1是LS的表頭，其余元素組成的表（a2,a3,.an）是稱為LS的表尾。根據(jù)定義，非空廣義表的表頭是一個元素，它可以是原子也可以是一個子表，表尾則必定是子表。例如:LS=(a,b),表頭為a,表尾是（b）而不是b.另外：LS=（a)的表頭為a，表尾為空表(). （2）非空廣義表，除表頭外，其余元素構(gòu)成的表稱為表尾，所以非空廣義表尾一定是個表【5】在Java中,下列說法錯誤的有（ BCD ）A、數(shù)組

12、是一種對象 B、數(shù)組屬于一種原生類 C、int number = 31,23,33,43,35,63; D、數(shù)組的大小可以任意改變【6】廣義表(a,b,c),d,e,f)的長度是4()解析：錯誤；長度：去掉一層括號剩下的是幾部分。 深度：去掉幾層括號可以到最后一部分。比如： 例如E(a,(a,b),(a,b),c)的長度和深度分別為1和4【7】對n個記錄的線性表進行快速排序為減少算法的遞歸深度,以下敘述正確的是()A、每次分區(qū)后,先處理較短的部分 B每次分區(qū)后,先處理較長的部分C、與算法每次分區(qū)后的處理順序無關(guān) D、以上三者都不對解析：A；在快速排序中，需要使用遞歸來分別處理左右子段，遞歸深度

13、可以理解為系統(tǒng)棧保存的深度,先處理短的分段再處理長的分段，可以減少時間復(fù)雜度；如果按長的遞歸優(yōu)先的話，那么短的遞歸會一直保存在棧中，直到長的處理完。短的優(yōu)先的話，長的遞歸調(diào)用沒有進行，他是作為一個整體保存在棧中的，所以遞歸棧中的保留的遞歸數(shù)據(jù)少一些。【8】若要刪除 book 表中的所有數(shù)據(jù)，如下哪些語法是錯誤的？A、drop table book; B、truncate table book; C、delete from book; D、delelet *from book;解析：A： drop table book 是刪除整個表，題目的潛在意思是刪除表中的數(shù)據(jù)而并非刪除整個表。因此A錯。B：

14、 truncate table book 是刪除表中的數(shù)據(jù)，刪除速度比delete更快，無法撤回（回退）。C： delete from book 刪除數(shù)據(jù)表中的數(shù)據(jù)，可以回退，可添加where 子句。D：語法錯誤。四、鏈表【1】當(dāng)靜態(tài)鏈表采用數(shù)組實現(xiàn)時，插入與刪除操作仍需移動元素，這種說法（）解析：錯誤。靜態(tài)鏈表采用數(shù)組實現(xiàn)鏈表的存儲，用空間換取時間，刪除與插入需要改的是游標(biāo)。【2】靜態(tài)鏈表中指針表示的是（ 數(shù)組下標(biāo) ）靜態(tài)鏈表中指針表示的是( 下一元素在數(shù)組中的位置 )【3】以下屬于邏輯結(jié)構(gòu)的是( C )A、順序表 B、哈希表 C、有序表 D、單鏈表解析：從大的方面來說，數(shù)據(jù)結(jié)構(gòu)是反映數(shù)據(jù)的

15、一種形式，它具體分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，1，邏輯結(jié)構(gòu)：它是表現(xiàn)數(shù)據(jù)之間的一種關(guān)系的結(jié)構(gòu)，分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)；2，物理結(jié)構(gòu)：它是表現(xiàn)數(shù)據(jù)的是如何存儲的結(jié)構(gòu)，計算機內(nèi)部是如何安排該數(shù)據(jù)的存儲，通常分為順序結(jié)構(gòu)，鏈?zhǔn)浇Y(jié)構(gòu)，索引結(jié)構(gòu)，哈希結(jié)構(gòu)；該題中，順序表，哈希表，單鏈表均是存儲結(jié)構(gòu)；而有序表從字面意思是表達了數(shù)據(jù)之間是以升序或者降序的關(guān)系存在，感覺也是在考察語文功底，明顯有序表是邏輯上的關(guān)系。【4】在有n個結(jié)點的二叉鏈表中，值為非空的鏈域的個數(shù)為（ ）。解析：在有N個結(jié)點的二叉鏈表中必定有2N個鏈域。除根結(jié)點外，其余N-1個結(jié)點都有一個父結(jié)點。所以，一共有N-1個非空鏈域，其余2N-（N-1

16、）=N+1個為空鏈域。【5】一個長度為99的循環(huán)鏈表，指針A和指針B都指向了鏈表中的同一個節(jié)點，A以步長為1向前移動，B以步長為3向前移動，一共需要同時移動多少步A和B才能再次指向同一個節(jié)點_。解析：設(shè)A走x步 那么B就走3x步 兩個要碰到 所以有(3x-x)%99=0 x取99【6】隊列和棧都是運算受限的線性表,只允許在表的兩端進行運算()解析：錯誤。前半句是對的，后半句不對 棧只能在一端操作，隊列可以在兩端操作五、隊列【1】已知循環(huán)隊列存儲在一維數(shù)組A0.n-1中，且隊列非空時 front 和 rear 分別指向隊頭和隊尾元素。若初始時隊列為空，且要求第 1 個進入隊列的元素存儲在 A0處

17、，則初始時 front和 rear 的值分別是（ ）。解析：首先根據(jù)循環(huán)隊列的公式，插入元素，front不變，rear=(rear+1)%n。在本題中，即(rear+1)%n=0，可得rear=n-1。此時隊列中只有一個元素，則front與rear應(yīng)該指向同一個位置，即front也應(yīng)該為0。綜上，front=0， rear=n-1【2】以下開源軟件中經(jīng)常被用作隊列的是哪個？（BD）A、MongoDB B、Redis C、Memcached D、kafka【3】循環(huán)隊列的存儲空間為 Q(1:50)，初始狀態(tài)為 front=rear=50。經(jīng)過一系列正常的入隊與退隊操作后，front=rear=2

18、5，此后又插入一個元素，則循環(huán)隊列中的元素個數(shù)為（ ）。A、1，或50且產(chǎn)生上溢錯誤 B、51 C、26 D、2解析：循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置。入隊運算時，隊尾指針進1（即rear+1），然后在rear指針指向的位置插入新元素。當(dāng)front=rear=25時可知隊列空或者隊列滿，此后又插入了一個元素，如果之前隊列為空，插入操作之后隊列里只有一個元素，如果插入之前隊列已滿(50個元素)，執(zhí)行插入則會產(chǎn)生溢出錯誤。故本題答案為A選項。六、哈希【1】采用線性探測法處理散列時的沖突,當(dāng)從哈希表刪除一個記錄時,

19、不應(yīng)將這個記錄的所在位置置空,因為這會影響以后的查找解析：正確。如果初始地址在置空位置，查找失敗 如果初始位置不在置空位置，查找過程中遇到置空位置，探測失敗，查找失敗【2】HASH函數(shù)沖突處理方式（1）開放定值法 這個方法分為幾種其中一種是線性探索，就是這個值有沖突就向下一個尋址依次加1向后直到不沖突為止，但是這樣有的時候會造成效率偏低。所以還有的時候會使用二次探索法就是使用平方的方式等。（2）拉鏈法 這個方法就是使用鏈表處理沖突，只要有沖突就增加一個鏈表節(jié)點。（3）雙哈希法 就是這個hash函數(shù)有沖突，就換一個hash函數(shù)試試。（4）建立公共溢出區(qū) 這種方法就是將哈希表分為基本表和溢出表，凡

20、是有沖突的就直接放到溢出區(qū)。【3】若裝填因子a為1,則向哈希表中散列元素時一定會產(chǎn)生沖突解析：錯誤。裝填因子為1，表明裝入的元素個數(shù)與表長相等裝填因子 a = 裝入的元素個數(shù)/哈希表的長度若采用鏈地址法處理，則向哈希表中散列元素時不一定會產(chǎn)生沖突；【4】設(shè)有n個關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關(guān)鍵字映射到Hash表中需要做幾次線性探測？解析：第一個關(guān)鍵字直接插入，第二個關(guān)鍵字要做1次探測，所以類推n個關(guān)鍵詞要做0+1+2+.+(n-1) = n*(n-1) / 2 【5】采用哈希表組織100萬條記錄，以支持字段A快速查找，則（ C ）A、理論上可以在常數(shù)時間內(nèi)找到特定記錄

21、 B、所有記錄必須存在內(nèi)存中C、拉鏈?zhǔn)焦Ｗ顗牟檎視r間復(fù)雜度是O（n） D、哈希函數(shù)的選擇跟A無關(guān)解析：A，記錄共有100萬條，一般的哈希表長度不可能做這么長，因此要解決散列沖突問題，因此一般不能在常數(shù)時間內(nèi)找到記錄B，哈希查找可以在外存中查找，可以用哈希表映射到文件，分級查找C，最壞情況是所有記錄的散列值都沖突，這樣就退化為線性查找，時間復(fù)雜度為O（n）D，哈希函數(shù)的選擇跟A關(guān)系密切，跟A的字段類型有關(guān)，哈希函數(shù)設(shè)計的好壞也影響著查找的速度【6】現(xiàn)有一完全的P2P共享協(xié)議，每次兩個節(jié)點通訊后都能獲取對方已經(jīng)獲取的全部信息，現(xiàn)在使得系統(tǒng)中每個節(jié)點都知道所有節(jié)點的文件信息，共17個節(jié)點，假設(shè)只能

22、通過多次兩個對等節(jié)點之間通訊的方式，則最少需要（ 30 ）次通訊【7】常用構(gòu)造散列函數(shù)的方法有：直接定址法，數(shù)字分析法，折疊法，平方取中法，乘余取整法減去法，基數(shù)轉(zhuǎn)換法，除留余數(shù)法，隨機乘數(shù)法，字符串?dāng)?shù)值哈希法，旋轉(zhuǎn)法，偽隨機數(shù)法【8】設(shè)哈希表長為14，哈希函數(shù)是H(key)=key%11,表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84共四個，現(xiàn)要將關(guān)鍵字為49的結(jié)點加到表中，用二次探測再散列法解決沖突，則放入的位置是( 9 )【9】有一組關(guān)鍵字為77,28,38,41,45,1,9,31,99,51,23,47,68,61.1,請構(gòu)造一個hash函數(shù)，形式為H（key）=key mod p，裝

23、填因子a=0.8，用鏈地址法解決沖突；2計算等概率情況下查找成功的平均查找長度；3計算等概率情況下查找失敗的平均查找長度（空指針的比較不計入）。解析：裝填因子 a 的定義知道，a=n/m 其中n 為關(guān)鍵字個數(shù)，m為表長m = n / a = 14 / 0.8 = 17.5(取18) 取17比較好，一般都是取素數(shù)77%18=5 41%18=5 23%18=5 1/328%18=10 138%18=2 145%18=9 9%18=9 99%18=9 1/31%18=1 131%18=13 147%18=11 168%18=14 161%18=7 151%18=15 1查找成功的平均查找長度：20/

24、14 查找失敗的平均查找長度：14/18查找成功時，分母為哈希表元素個數(shù)，查找不成功時，分母為哈希表長度。七、字符串【1】n 個字符構(gòu)成的字符串，假設(shè)每個字符都不一樣，問有多少個子串？解析：長度為 1 的字符串 n 個長度為 2 的 n-1 個長度為 3 的 n-2 個.長度為 n 的 1 個然后 n+(n-1)+(n-2)+.+1 =n(n+1)/2，再加一個空串串a(chǎn)babaaababaa的next數(shù)組為()解析：i 0 1 2 3 4 5 6 7 8 9 10 11 s a b a b a a a b a b a a nexti -1 0 0 1 2 3 1 1 2 3 4 5答案為先計算前綴nexti的值： （字符串匹配是 從頭開始的 和 從尾開始的字符串進行匹配是否重復(fù) ）nexti的值主要是看si之前的字符串中重復(fù)的子串長度。next0 = -1，定值。 next1是看s1之前的字符串“a”中重復(fù)的子串長度為0，故next1 = 0。next2是看s2之前的字符串“ab”中重復(fù)的子串長度為0，故next2 = 0。next3是看s3之前的字符串&qu