【文章內(nèi)容簡(jiǎn)介】 輸入一個(gè)以句號(hào)結(jié)尾，長(zhǎng)度任意的字符序列，分別統(tǒng)計(jì)由字符’A’所構(gòu)成的平臺(tái)的最大長(zhǎng)度值，和由字符’B’所構(gòu)成的最大長(zhǎng)度值。如對(duì)于字符序列’ABCDANBBCBAJKBCAAABA’?！疉’平臺(tái)的最大長(zhǎng)度是3，’B’平臺(tái)的最大長(zhǎng)度是2 。數(shù)據(jù)結(jié)構(gòu)模擬試題四一、( 共30分，每題2分)單項(xiàng)選擇題1．循環(huán)隊(duì)列用數(shù)組A[0..m1]存放其元素值，已知其頭尾指針?lè)謩e為front和rear，則當(dāng)前元素個(gè)數(shù)為（）A．(rearfront+m) mod m B．rearfront+1 C．rearfront1 D．rearfront E．以上答案都不對(duì)2．?dāng)?shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（）A．存儲(chǔ)結(jié)構(gòu) B．物理結(jié)構(gòu) C．邏輯結(jié)構(gòu) D．物理結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu) E．以上答案都不對(duì)3．在具有n個(gè)結(jié)點(diǎn)的單鏈表中，實(shí)現(xiàn)（）的操作，其算法的時(shí)間復(fù)雜度都是O(n)。A．遍歷鏈表和求鏈表的第i個(gè)結(jié)點(diǎn) B．在地址為p的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn) C．刪除開(kāi)始結(jié)點(diǎn) D．刪除地址為p的結(jié)點(diǎn)的后繼結(jié)點(diǎn) E．以上答案都不對(duì)4．某二叉樹(shù)的前序遍歷序列為IJKLMNO，中序遍歷序列為JLKINMO，則后序遍歷序列為（）A．JLKMNOI B．LKNJOMI C．LKJNOMI D．LKNOJMI E．以上答案都不對(duì)5．設(shè)n階方陣是一個(gè)上三角矩陣，則需存儲(chǔ)的元素個(gè)數(shù)為（）A．n B．n*n C．n*n/2 D．n(n+1)/2 E．以上答案都不對(duì)6．串的“模式匹配”是指（）A．判兩個(gè)串是否相等 B．對(duì)兩個(gè)串進(jìn)行大小比較 C．找某字符在串中第一次出現(xiàn)位置 D．找某子串在主串中第一次出現(xiàn)的位置 E．以上答案都不對(duì)7．有n個(gè)結(jié)點(diǎn)的無(wú)向圖的邊數(shù)最多為（）A．n+1 B．n(n1)/2 C．n(n+1) D．2n(n+1) E．以上答案都不對(duì)8．多關(guān)鍵字文件是指（）A．有多個(gè)主關(guān)鍵字 B．有多個(gè)次關(guān)鍵字 C．有一個(gè)主關(guān)鍵字多個(gè)次關(guān)鍵字D．有多個(gè)主關(guān)鍵字和多個(gè)次關(guān)鍵字 E．以上答案都不對(duì)9．某順序存儲(chǔ)的表格中有90000個(gè)元素，已按關(guān)鍵字值額定升序排列，假定對(duì)每個(gè)元素進(jìn)行查找的概率是相同的，且每個(gè)元素的關(guān)鍵字的值皆不相同。用順序查找法查找時(shí)，平均比較次數(shù)約為（）A．25000 B．30000 C．45000 D．90000 E．以上答案都不對(duì)10．對(duì)于序列(49,38,65,97,76,13,27,50)按由小到大進(jìn)行排序，（）是初始步長(zhǎng)d=4的希爾排序法第一趟的結(jié)果。A. 49,76,65,13,27,50,97,38 B. 13,27,38,49,50,65,76,97C. 97,76,65,50,49,38,27,13 D. 49,13,27,50,76,38,65,97E. 以上答案都不對(duì)11．下列排序算法中，第一趟排序完畢后，其最大或最小元素一定在其最終位置的算法是（）A．歸并排序 B．直接插入排序 C．快速排序 D．冒泡排序 E．以上答案都不對(duì)12．關(guān)于樹(shù)和二叉樹(shù)的有序性，正確的結(jié)論是（）A. 樹(shù)和二叉樹(shù)都是有序的 B．樹(shù)和二叉樹(shù)都可能是有序的C．樹(shù)和二叉樹(shù)都是無(wú)序的 D．二叉樹(shù)是有序的，樹(shù)可能是有序的，也可能是無(wú)序的 E．以上答案都不對(duì)13．在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和與圖的邊數(shù)的比是（）A．1:2 B．1:1 C．2:1 D．4:1 E．以上答案都不對(duì)14．若一組紀(jì)錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)紀(jì)錄為基準(zhǔn)得到的一次劃分結(jié)果為（）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，79E．以上答案都不對(duì)15．從理論上講，將數(shù)據(jù)以（）結(jié)構(gòu)存放，則查找一個(gè)數(shù)據(jù)所用時(shí)間不依賴于數(shù)據(jù)個(gè)數(shù)n。A．二叉查找樹(shù) B．鏈表 C．二叉樹(shù) D．哈希表 E．以上答案都不對(duì)二、（共40分，每空2分）填空題1．二分查找算法的時(shí)間復(fù)雜度為（ ）2．在單鏈表中，申請(qǐng)到新結(jié)點(diǎn)p，將p指向的結(jié)點(diǎn)后插到s所指結(jié)點(diǎn)的操作，其一是pnext=snext，其二是（ ）。3．對(duì)一般樹(shù)和森林的后序遍歷序列的次序與對(duì)應(yīng)的二叉樹(shù)的（ ）遍歷次序相同。4．設(shè)二維數(shù)組A[10..20,5..10]按行優(yōu)先存儲(chǔ)，每個(gè)元素占4個(gè)單元，A[10,5]的地址為160，則A[15,10]的地址為（ ）。5．線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是（ ）的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是（ ）的。6．赫夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度（ ）的二叉樹(shù)。7．前序?yàn)閍bc且后序?yàn)閏ba的二叉樹(shù)共有（ ）棵。8．已知完全二叉樹(shù)的高度為8，第7層有10個(gè)葉子結(jié)點(diǎn)，則二叉樹(shù)的總結(jié)點(diǎn)數(shù)至少是（ ）。9．已知二叉樹(shù)有50個(gè)葉子結(jié)點(diǎn)，且僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為30，則總結(jié)點(diǎn)數(shù)為（ ）。10．具有m個(gè)葉子結(jié)點(diǎn)的赫夫曼樹(shù)共有（ ）個(gè)結(jié)點(diǎn)。11．從一棵二叉樹(shù)的前序序列和（ ）可唯一確定這棵二叉樹(shù)。設(shè)某二叉樹(shù)的后序遍歷為ABKCBPM，則可知該二叉樹(shù)的根為（ ）。12．設(shè)廣義表C=((x,(a,b)),((x,(a,b)),y)),則C的長(zhǎng)度為（ ），深度為（ ）。13．設(shè)有一稠密圖G，則G采用（ ）存儲(chǔ)較省空間。14．在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用（ ）；若初始數(shù)據(jù)基本反序，則選用（ ）。15．有n結(jié)點(diǎn)的二叉鏈表中，空指針域有（ ）個(gè)；利用這些空指針域，存放指向結(jié)點(diǎn)在中序次序下的前趨或后繼的指針，這種附加的指針?lè)Q為（ ）。三、（10分）已知一棵度為m的樹(shù)中有N1個(gè)度為1的結(jié)點(diǎn)，N2個(gè)度為2的結(jié)點(diǎn)，……Nm個(gè)度為m的結(jié)點(diǎn)，問(wèn)該樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)。請(qǐng)寫(xiě)出推導(dǎo)過(guò)程。四、（15分）給定字母a,b,c,d,, 。設(shè)計(jì)以該權(quán)值為基礎(chǔ)的赫夫曼樹(shù)，并給出赫夫曼編碼。五、（15分）設(shè)散列表的長(zhǎng)度為13，散列函數(shù)為H(K)=K%13，給定的關(guān)鍵字序列為：19，14，23，01，68，20，84，27，55，11，10，79。試畫(huà)出用線性探測(cè)再散列解決沖突時(shí)所構(gòu)成的散列表。并求等概率情況下這種方法查找成功和查找不成功時(shí)的平均查找長(zhǎng)度。六、（15分）已知奇偶交換排序如下所述：第一趟對(duì)序列中所有奇數(shù)項(xiàng)i掃描，將a[i]和a[i+1]進(jìn)行比較；第二趟對(duì)序列中所有偶數(shù)項(xiàng)i掃描，將a[i]和a[i+1]進(jìn)行比較。每次比較時(shí)若 a[i]a[i+1]，則將兩者交換。第三趟對(duì)所有奇數(shù)項(xiàng)，第四趟對(duì)所有偶數(shù)項(xiàng)……，如此重復(fù)，直至整個(gè)序列有序。1) 寫(xiě)出奇偶交換排序算法，設(shè)待排序的n個(gè)元素存放在數(shù)組a[1..n] 中。2) 說(shuō)明你的排序方法的結(jié)束條件3) 若待排序的初始序列已按關(guān)鍵字從小到大有序，則關(guān)鍵字的比較次數(shù)是多少？七、（10分）已知長(zhǎng)度為n的線性表A采用順序存儲(chǔ)結(jié)構(gòu)，并且元素按值大小非遞減排列，下面的算法刪除線性表中多余的值相同的元素。請(qǐng)?jiān)谒惴ㄖ锌瞻滋幪钊脒m當(dāng)內(nèi)容，使之能夠正常工作。void DEL(int A[n]) // 設(shè)A[1]~A[n]存放著n個(gè)元素{ int i=1。while (1) do if (A[i]!=A[i+1]) i++。 else //查找滿足條件的元素 { for (2) A[j1]=A[j]。//刪除第i+1個(gè)元素（滿足條件的元素） (3) //修改線性表的長(zhǎng)度 }}八、（15分）設(shè)計(jì)算法， 已知一棵以二叉鏈表存儲(chǔ)的二叉樹(shù)，root指向根結(jié)點(diǎn)，p指向二叉樹(shù)中任一結(jié)點(diǎn)，編寫(xiě)算法求從根結(jié)點(diǎn)到p所指結(jié)點(diǎn)之間的路徑（要求輸出該路徑上每個(gè)結(jié)點(diǎn)的數(shù)據(jù)）。數(shù)據(jù)結(jié)構(gòu)模擬試題五一、( 共34分，每題2分)單項(xiàng)選擇題在非空循環(huán)雙鏈表中q所指的結(jié)點(diǎn)前插入一個(gè)由p所指結(jié)點(diǎn)的過(guò)程依次為：pnext=q；pprior=qprior；qprior=p；（ ）；A．qnext=p B．qpriornext=p C．ppriornext=pD．pnextprior=p E．以上答案都不對(duì)已知有向圖G=(V,E)，其中V={v1,v2,v3,v4,v5,v6,v7}，E={v1,v2，v1,v3，v1,v4，v2,v5，v3,v5，v3,v6，v4,v6，v3,v7，v6,v7}，G的拓?fù)湫蛄惺牵? ）。A．v1,v3,v4,v6,v2,v5,v7 B．v1,v3,v2,v6,v4,v5,v7 C．v1,v3,v4,v5,v2,v6,v7 D．v1,v2,v5,v3,v4,v6,v7 E．以上答案都不對(duì)每個(gè)存儲(chǔ)結(jié)點(diǎn)只含有一個(gè)數(shù)據(jù)元素，存儲(chǔ)結(jié)點(diǎn)均勻地存放在連續(xù)的存儲(chǔ)空間，使用函數(shù)值對(duì)應(yīng)結(jié)點(diǎn)的存儲(chǔ)位置，該存儲(chǔ)方式是（ ）存儲(chǔ)方式A． 順序 B．鏈接 C．索引 D．散列 E．以上答案都不對(duì)對(duì)于單鏈表形式的隊(duì)列，隊(duì)空的條件是（ 　　?。〢．F＝R＝nil　　　　B．F＝R　　　　C．F≠nil且R＝nil　　　D．R－F＝1E．以上答案都不對(duì)采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于樹(shù)的（ ）。A． 中根遍歷 B．先根遍歷 C．后根遍歷 D．按層次遍歷E．以上答案都不對(duì)對(duì)于序列(49,38,65,97,76,13,27,50)按由小到大進(jìn)行排序，（ ）是初始步長(zhǎng)d=4的希爾排序法第一趟的結(jié)果。A． 49,76,65,13,27,50,97,38B． 13,27,38,49,50,65,76,97C． 97,76,65,50,49,38,27,13D． 49,13,27,50,76,38,65,97E．以上答案都不對(duì)在一個(gè)長(zhǎng)度為n的順序表的表尾插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（ ）。A．O（n） B．O（1） C．O（n2） D．O（log2n）E．以上答案都不對(duì)設(shè)n階方陣是一個(gè)上三角矩陣，則需存儲(chǔ)的元素個(gè)數(shù)為（ ）。A．n B．n*n C．n*n/2 D．n(n+1)/2 E．以上答案都不對(duì)樹(shù)中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（ ）。A．0 B．1