數(shù)據(jù)結(jié)構(gòu)專項(xiàng)練習(xí)

數(shù)據(jù)結(jié)構(gòu)專項(xiàng)練習(xí)一、線性結(jié)構(gòu)1、 將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（）A、nB、2n-1C、2nD、n-12、線性鏈表中各鏈接點(diǎn)之間的地址（ ）A、必須連續(xù)B、部分地址必須連續(xù)C、不一定連續(xù)D、連續(xù)與否無(wú)所謂3、 在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個(gè)（）結(jié)構(gòu)。A、堆棧 B、隊(duì)列C、數(shù)組D、線性表4、循環(huán)鏈表表示隊(duì)列，正確的說(shuō)法是（ ）A、 可設(shè)一個(gè)頭指針使入隊(duì)、出隊(duì)都方便B、 可設(shè)一個(gè)尾指針使入隊(duì)、出隊(duì)都方便C、 必須設(shè)頭、尾指針才能使入隊(duì)、出隊(duì)都方便D、 無(wú)論如何，只能使入隊(duì)方便5、設(shè)棧的輸入序列為123 n,輸出序列為a1，a2，a3 a,若存在1v=kv=n使得1 2 3 na=n則當(dāng)k<=i<=n時(shí)，a為（）kiA、n-i+1B、n-（i-k） C、不確定6、 設(shè)棧的輸入序列是（1，2，3，4）則（）不可能是其出棧序列：A、1243B、2134 C、1432 D、4312E、32147、 設(shè)輸入元素為1、2、3、P和A，輸入次序?yàn)?23PA，如圖所示。元素經(jīng)過(guò)棧后到達(dá)輸出序列，當(dāng)所有元素均到達(dá)輸出序列后，有哪些序列可以作為高級(jí)語(yǔ)言的變量名？8、 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素a、b、c、d、e、f依次通過(guò)棧S,—個(gè)元素出棧后即進(jìn)入隊(duì)列Q。若這6個(gè)元素出隊(duì)列的順序是b、d、c、f、e、a,則棧S的容量至少應(yīng)該是 。9、 用數(shù)組Q（其下標(biāo)在0?n-1中，共有n個(gè)元素）表示一個(gè)環(huán)形隊(duì)列，f為當(dāng)前隊(duì)頭元素前一位置，r為隊(duì)尾元素的位置。假定隊(duì)列中元素個(gè)數(shù)總小于n，求隊(duì)列中元素個(gè)數(shù)的公式是 。10、 若串S=“software”，其子串的數(shù)目是（）A、8B、37C、36D、9二、樹(shù)和二叉樹(shù)11、若一個(gè)具有N個(gè)頂點(diǎn)，K條邊的無(wú)向圖是一個(gè)森林（N>K）,則該森林中必有（）棵樹(shù)A、K B、NC、N-KD、112、 設(shè)高為h的二叉樹(shù)只有度為0和2的結(jié)點(diǎn)，則此類二叉樹(shù)的結(jié)點(diǎn)至少為（），至多為（）A、2h B、 2h-1 C、 2h+1 D、 h+1E、 2h-1 F、 2h-1 G、 2h+1+1 H、 2h+113、對(duì)于前序和中序遍歷結(jié)果相同的二叉樹(shù)為（ ）；對(duì)于前序遍歷和后序遍歷結(jié)果相同的二叉樹(shù)為（）。A、一般二叉樹(shù) B、只有根結(jié)點(diǎn)的二叉樹(shù)C、根結(jié)點(diǎn)無(wú)左孩子的二叉樹(shù)D、根結(jié)點(diǎn)無(wú)右孩子的二叉樹(shù)E、所有結(jié)點(diǎn)只有左子樹(shù)的二叉樹(shù)F、 所有結(jié)點(diǎn)只有右子樹(shù)的二叉樹(shù)14、 已知一算術(shù)表達(dá)式的中綴形式A+B*C-D/E，后綴形式ABC*+DE/-，其前綴形式為（）A、-A+B*C/DE B、-A+B*CD/EC、-+*ABC/DED、-+A*BC/DE15、 將算術(shù)表達(dá)式（（a+b）+c*（d+e）+f）*（g+h）轉(zhuǎn)化為二叉樹(shù)。16、 對(duì)二叉排序樹(shù)進(jìn)行（）遍歷，可以得到該二叉樹(shù)所有結(jié)點(diǎn)構(gòu)成的排序序列。A、前序B、中序C、后序D、按層次三、圖17、G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有 個(gè)頂點(diǎn)。A、6B、7C、8D、9E、10 F、1118、設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n則該無(wú)向圖最多有 條邊。A、n-1B、n（n-1）/2C、n（n+1）/2 D、0 E、n219、一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為 ）A、n-1B、n C、n+1D、nlogn20、 設(shè)有如圖所示的AOE網(wǎng)（其中vi（i=1,2,?，6）表示事件，弧上表示活動(dòng)的天數(shù)）。1）找出所有的關(guān)鍵路徑 2）v3事件的最早開(kāi)始時(shí)間為 四、算法21、若在線性表中采用折半查找元素，該線性表應(yīng)該（ ）A、元素按值有序B、采用順序存儲(chǔ)結(jié)構(gòu)C、 元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)D、 元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)22、在關(guān)鍵字隨機(jī)分布的情況下，用二叉樹(shù)的方法進(jìn)行查找，其查找長(zhǎng)度與 量級(jí)相當(dāng)。A、順序查找 B、折半查找C、前兩者均不正確23、 利用逐點(diǎn)插入法建立序列（50、72、43、85、75、20、35、45、65、30）對(duì)應(yīng)的二叉排序樹(shù)以后，查找元素35要進(jìn)行（）元素間的比較。A、4次B、5次 C、7次 D、10次24、用序列（46、88、45、39、70、58、101、10、66、34）建立一個(gè)排序二叉樹(shù)，畫出該樹(shù)。答案與分析一、線性結(jié)構(gòu)1、 A當(dāng)一個(gè)表的最小元素大于另一個(gè)表的最大元素時(shí)，比較次數(shù)為n次。2、 D3、B緩沖區(qū)此時(shí)實(shí)際上是一個(gè)等待打印隊(duì)列4、 D因?yàn)槲仓羔槻⒉荒苁钩鲫?duì)方便，如果想使出隊(duì)方便，必須要用一個(gè)指針保存隊(duì)尾元素的前驅(qū)，只保留尾指針或頭指針并不能對(duì)入隊(duì)產(chǎn)生影響。尾指針相對(duì)于頭指針的優(yōu)勢(shì)在于可以簡(jiǎn)化一些操作，如：合并兩個(gè)鏈表。只是保存尾指針時(shí)，訪問(wèn)頭接點(diǎn)要多進(jìn)行一次操作。5、 C由于輸出序列a1，a2，a3??an，并沒(méi)有明確標(biāo)示出具體的序列值，只是一個(gè)1 2 3n變量序列，即可能是由輸入序列的任何可能出棧序列決定的。所以，當(dāng)1<=k<=n的ak為n時(shí)，不能確定kv=iv=n時(shí)的a.ki。6、 D7、AP321PA321P3A21P32A1 P321A 8、39、(r-f+n)modn10、C(空串一般不作為子串)二、樹(shù)和二叉樹(shù)11、C因?yàn)橐豢镁哂衝個(gè)頂點(diǎn)的樹(shù)有n-1條邊，因此設(shè)此森林中有m棵樹(shù)，每棵樹(shù)具有的頂點(diǎn)數(shù)為v.(1v=iv=m)則：iv+v+ +v=N①,(v—1)+(v一1)+ + (v—1)=K②1 2 m 1 2 m①—②得m=N-K12、B、F13、F、B14、D16、B三、圖17、D8個(gè)頂點(diǎn)的完全圖共有28條邊，再加一個(gè)孤立頂點(diǎn)使G成為非連通的。折半其他情況，由于點(diǎn)未充分利用必定多于9個(gè)。18、B19、A20(1)1-2-3-5-6及1-4-6(2)