華南理工大學(xué)2019年《數(shù)據(jù)結(jié)構(gòu)》

PAGEPAGE1華南理工大學(xué)2019年《數(shù)據(jù)結(jié)構(gòu)》選擇題（從下列答案選項(xiàng)中選出一個(gè)正確答案，每小題2分)在計(jì)算機(jī)中存儲(chǔ)器內(nèi)表示時(shí)，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（ ）。A．邏輯結(jié)構(gòu) B．順序存儲(chǔ)結(jié)構(gòu) C．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D.以上都對(duì)線性表就是順序表，這種說(shuō)法（ ）。A．正確 B．錯(cuò)誤若已知一個(gè)棧的入棧序列是1,2,3,4,5，不可能得到的輸出序列是（ ）。A．2,3,4,1,5

B．5,4,1,3,2

C．2,3,1,4,5 D．1,5,4,3,2串的邏輯結(jié)構(gòu)與（ ）的邏輯結(jié)構(gòu)不同。棧隊(duì)列樹(shù)線性表如果一個(gè)串中的所有字符均在另一串中出現(xiàn)，則說(shuō)前者是后者的子串。（）正確錯(cuò)誤設(shè)有兩個(gè)串P和Q，求Q在P中首次出現(xiàn)的位置的操作稱為（）。A.連接 B.模式匹配 C.求子串 D.求串長(zhǎng)已知模式串t=“abcaabbcabcaabdab”，該模式串的next數(shù)組值為（ ）。-1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，0，10，1，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1-1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，7，1，-1，0，0，0，1，1，2，3，0，1，2，3，4，5，6，0，1設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占1個(gè)地址空間，則a85的地址為（ ）。13331840若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種說(shuō)法（ ）。正確錯(cuò)誤樹(shù)形結(jié)構(gòu)的特點(diǎn)是：一個(gè)結(jié)點(diǎn)可以有（）。A、多個(gè)直接前趨B、多個(gè)直接后繼C、多個(gè)前趨D、一個(gè)后繼在一棵高度為h的滿三叉樹(shù)中，結(jié)點(diǎn)總數(shù)為（）A、3h-1B、(3h-1)/2C、(3h-1)/3D、3h設(shè)森林T中有4棵樹(shù)，結(jié)點(diǎn)個(gè)數(shù)依次為n1,n2,n3,n4，當(dāng)把森林T轉(zhuǎn)換成一棵二叉樹(shù)后，二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上有（ ）個(gè)結(jié)點(diǎn)。A．n1-1 B．n1 C．n1+n2+n3 D．n2+n3+n4任何一個(gè)無(wú)向連通圖的最小生成樹(shù)（ ）。A．只有一顆 B．有一顆或多棵 C．一定有多棵 D．可能不存在一個(gè)無(wú)向連通圖的生成樹(shù)是含有該連通圖的全部頂點(diǎn)的（）。A、極小連通子圖B、極小子圖C、極大連通子圖D、極大子圖在一個(gè)有向圖的鄰接表或逆鄰接表中，如果某個(gè)頂點(diǎn)的鏈表為空，則該頂點(diǎn)的度一定為零，這種說(shuō)法(

)。正確錯(cuò)誤對(duì)于關(guān)鍵字序列（12，13，11，18，60，15，7，18，25，100），用篩選法建堆，必須從關(guān)鍵字值為（ ）的結(jié)點(diǎn)開(kāi)始。A．100 B．60 C．12 D．15下列排序算法中，時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(nlog2n）的是（）A、堆排序B、冒泡排序C、直接選擇排序D、快速排序下列排序算法中，（）排序在某趟結(jié)束后不一定選出一個(gè)元素放到其最終的位置上。A、選擇B、冒泡C、歸并D、堆在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最小不平衡子樹(shù)之根為A,并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應(yīng)作（）型調(diào)整使其平衡。A．LL B．LR C．RL D．RR 常采用下面幾種方式解決散列法中出現(xiàn)的沖突問(wèn)題（ ）。A．?dāng)?shù)字分析法、除余法、平方取中法B．?dāng)?shù)字分析法、除余法、線性探測(cè)法C．?dāng)?shù)字分析法、線性探測(cè)法、多重散列法D．線性探測(cè)法、多重散列法、鏈地址法填空題（每空2分）以下程序段的時(shí)間復(fù)雜度是_____________，其中n為正整數(shù)。voidfun(intn){ inti=1,k=100;while(i<n) { k=k+1; i+=2;} }對(duì)于長(zhǎng)度為n的順序表，插入或刪除元素的平均時(shí)間復(fù)雜度為_(kāi)________________。對(duì)于順序?；蝽樞蜿?duì)列，插入或刪除元素的時(shí)間復(fù)雜度為_(kāi)______________。一個(gè)n×n的對(duì)稱矩陣若采用壓縮存儲(chǔ)，需要存儲(chǔ)___________________________個(gè)元素。設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素a，b，c，d，e，f依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q。若這6個(gè)元素出隊(duì)列的順序?yàn)閎，d，c，f，e，a，則棧S的容量至少應(yīng)該是________________。判定一個(gè)環(huán)形隊(duì)列qu（最多元素為MaxSize）為空的條件是__________________________________________，判定環(huán)形隊(duì)列qu為滿隊(duì)列的條件是__________________________________________。已知二叉樹(shù)中葉子數(shù)為50，僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為30，則總結(jié)點(diǎn)數(shù)為_(kāi)_____________。取出廣義表A=((x,y,z),(a,b,c,d))中原子b的函數(shù)是___________________________________。無(wú)向圖中的極大連通子圖稱為該無(wú)向圖的___________。在有序表A[1..20]中，采用二分查找算法查找元素值等于A[12]的元素，所比較過(guò)的元素的下標(biāo)依次為_(kāi)______________________。一個(gè)深度為k的，具有最少結(jié)點(diǎn)的完全二叉樹(shù)按層次（同層次從左到右）用自然數(shù)依次對(duì)結(jié)點(diǎn)編號(hào)，則編號(hào)最小的葉子的序號(hào)是__________________；問(wèn)答題：在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？表示一個(gè)有1000個(gè)頂點(diǎn)、1000條邊的有向圖的鄰接矩陣有多少個(gè)矩陣元素?是否稀疏矩陣？（已知二叉樹(shù)的中序序列為DCEFBHGAKJLIM,后序序列為DFECHGBKLJMIA，畫(huà)出該二叉樹(shù)。已知如下一個(gè)無(wú)向圖，要求；畫(huà)出該無(wú)向圖的鄰接表；基于你給出的鄰接表，畫(huà)出以頂點(diǎn)A為出發(fā)點(diǎn)遍歷圖所得到的DFS序列。FDCBEGAFDCBEGA下圖是用鄰接表存儲(chǔ)的圖，畫(huà)出此圖，并畫(huà)出由頂點(diǎn)C出發(fā)按深度優(yōu)先遍歷該圖所得到的DFS生成樹(shù)。已知關(guān)鍵字的輸入序列如下：（46，88，45，39，70，58，101，10，66，34），畫(huà)出按關(guān)鍵字的輸入次序生成的一棵二叉排序樹(shù)，并求在等概率情況下查找成功的平均查找長(zhǎng)度。設(shè)有一組關(guān)鍵字序列：（29，18，25，47，58，12，51，10）要按照關(guān)鍵字值遞增的次序進(jìn)行排序。（1）若采用初始增量為4的希爾排序，寫(xiě)出第一趟排序的結(jié)果：（2）若采用以第一個(gè)元素為基準(zhǔn)元素的快速排序法，寫(xiě)出第一趟排序的結(jié)果：以下面的數(shù)據(jù)作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造一顆哈夫曼樹(shù)，并計(jì)算帶權(quán)路徑長(zhǎng)度WPL。{5，6，7，8，9，10，15，18，22}已知散列地址空間為０至14，散列函數(shù)H(K)=K%13，采用線性探查法處理沖突，將下列關(guān)鍵字序列依次存入散列表中，并求出在等概率情況下查找成功的平均查找長(zhǎng)度ASL。（240，29，345，189，100，20，21，35，3，208，78，99，45，350）算法填空：請(qǐng)仔細(xì)閱讀下面的堆排序算法：n個(gè)待排序的學(xué)生成績(jī)記錄存放在一維數(shù)組R[1..n]中，結(jié)點(diǎn)類型及相關(guān)定義如下：#definen200typedefstructstud{intnum;charname[20];floatscore;}rectype;rectypeR[n+1];要求按成績(jī)(score)由高到低排列學(xué)生記錄，將以下堆排序算法補(bǔ)充完整，使它們能正確工作。SIFT(R,i,m)//在數(shù)組R[i]..R[m]構(gòu)成的完全二叉樹(shù)中，已知R[i]的左、右子樹(shù)都是堆，rectypeR[];//現(xiàn)將R[i]為根的子樹(shù)也調(diào)整為堆inti,m;{intj;rectypetemp;temp=R[i];j=2*i;while(j<=m){if((j<m)&&())j++;if(________________________________________){R[i]=R[j];i=j;_____________________;}elsebreak;}//whileR[i]=temp;}//SIFTHEAPSORT(R)//對(duì)R[1]到R[n]進(jìn)行堆排序rectypeR[];{inti;rectypetemp;for(i=n/2;i>=1;i--)_______________