2022年重慶工商大學(xué)計算機(jī)科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A(有答案)

2022年重慶工商大學(xué)計算機(jī)科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A（有答案）一、選擇題1、用有向無環(huán)圖描述表達(dá)式(A+B)*((A+B)／/A)，至少需要頂點(diǎn)的數(shù)目為（）。A.5B.6C.8D.92、設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序?yàn)橹鞔鎯?，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（）。A.13B.33C.18D.403、算法的計算量的大小稱為計算的（）。A.效率B.復(fù)雜性C.現(xiàn)實(shí)性D.難度4、向一個棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時，應(yīng)執(zhí)行（）。A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s5、最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭：front，則隊(duì)空的條件是（）。A.（rear+1）MODn=frontB.rear=frontC.rear+1=frontD.（rear-1）MODn=front6、若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)（）。A．只有eB．有e、bC．有e、cD．無法確定7、排序過程中，對尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束時都至少能夠確定一個元素最終位置的方法是（）。Ⅰ．簡單選擇排序Ⅱ．希爾排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路歸并排序A．僅Ⅰ、Ⅲ、ⅣB．僅Ⅰ、Ⅱ、ⅢC．僅Ⅱ、Ⅲ、ⅣD．僅Ⅲ、Ⅳ、Ⅴ8、一個具有1025個結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（）。A.11B.10C.11至1025之間D.10至1024之間9、一棵非空的二叉樹的前序序列和后序序列正好相反，則該二叉樹一定滿足（）。A.其中任意一個結(jié)點(diǎn)均無左孩子B.其中任意一個結(jié)點(diǎn)均無右孩子C.其中只有一個葉結(jié)點(diǎn)D.其中度為2的結(jié)點(diǎn)最多為一個10、對序列{15，9，7，8，20，-1，4}用希爾排序方法排序，經(jīng)一趟后序列變?yōu)閧15，-1，4，8，20，9，7}則該次采用的增量是（）。A.1B.4C.3D.2二、填空題11、N個頂點(diǎn)的連通圖用鄰接矩陣表示時，該矩陣至少有______個非零元素。12、若用n表示圖中頂點(diǎn)數(shù)目，則有______條邊的無向圖成為完全圖。13、如下的算法分別是后序線索二叉樹求給定結(jié)點(diǎn)node的前驅(qū)結(jié)點(diǎn)與后繼結(jié)點(diǎn)的算法，請?jiān)谒惴崭裉幪钌险_的語句。設(shè)線索二叉樹的結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)為（lflag，left，data，right，rflag），其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驅(qū)；rflag=0，right指向其右孩子，rflag=1，right指向其后繼。14、關(guān)鍵碼序列（Q，H，C，Y，Q，A，M，S，R，D，F(xiàn)，X），要按照關(guān)鍵碼值遞增的次序進(jìn)行排序，若采用初始步長為4的希爾排序法，則一趟掃描的結(jié)果是______；若采用以第一個元素為分界元素的快速排序法，則掃描一趟的結(jié)果是______。15、設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為（data，next），next為指針域，已知指針px指向單鏈表中data為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn)，若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行以下語句：______16、每一棵樹都能唯一地轉(zhuǎn)換為它所對應(yīng)的二叉樹。若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列是______。設(shè)上述二叉樹是由某棵樹轉(zhuǎn)換而成，則該樹的前序序列是______。17、一棵有n個結(jié)點(diǎn)的滿二叉樹有______個度為1的結(jié)點(diǎn)、有______個分支（非終端）結(jié)點(diǎn)和______個葉子，該滿二叉樹的深度為______。18、設(shè)有一個10階對稱矩陣A采用壓縮存儲方式（以行為主序存儲：a11=1），則a85的地址為______。三、判斷題19、直接訪問文件也能順序訪問，只是一般效率不高。（）20、倒排文件是對次關(guān)鍵字建立索引。（）21、數(shù)組不適合作為任何二叉樹的存儲結(jié)構(gòu)。（）22、隊(duì)列和棧都是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)行運(yùn)算。（）23、用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點(diǎn)。（）24、深度為k的二叉樹中結(jié)點(diǎn)總數(shù)小于等于2k-1。（）25、為了很方便地插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。（）26、數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。（）27、當(dāng)改變網(wǎng)上某一關(guān)鍵路徑上任一關(guān)鍵活動后，必將產(chǎn)生不同的關(guān)鍵路徑。（）28、對兩棵具有相同關(guān)鍵字集合的而形狀不同的二叉排序樹，按中序遍歷它們得到的序列的順序卻是一致的。（）四、簡答題29、用一個數(shù)組S（設(shè)大小為MAX）作為兩個堆棧的共享空間。請說明共享方法，棧滿／棧空的判斷條件，并用C語言或PASCAL語言設(shè)計公用的入棧操作push（i，x），其中i為0或1，用于表示棧號，x為入棧值。30、設(shè)有n個元素采用起泡排序法進(jìn)行排序，通常需要進(jìn)行多少趟排序?對于第J趟起泡通常需要進(jìn)行多少次關(guān)鍵字比較?在程序設(shè)計中如何設(shè)置判斷條件，有可能使起泡趟數(shù)可以減少并且能完成排序。31、設(shè)將n（n＞1）個整數(shù)存放到一維數(shù)組R中。試設(shè)計一個在時間和空間兩方面都盡可能高效的算法，將R中存有的序列循左移P（0＜P＜n）個位置，即將R中的數(shù)據(jù)由（X0，X1，…，Xn－1）變換為（xp，xp＋1，…，xn－1，x0，x1，…，xp－1）。要求：（1） 給出算法的基本設(shè)計思想。（2） 根據(jù)設(shè)計思想，采用C或C＋＋或JAVA語言描述算法，關(guān)鍵之處給出注釋。說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。五、算法設(shè)計題32、已知字符串s1中存放一段英文，寫出算法format（s1，s2，s3，n），將其按給定的長度n格式化成兩端對齊的字符串s2，其多余的字符送s3。33、設(shè)從鍵盤輸入一整數(shù)的序列：a1，a2，a3，…，an，試編寫算法實(shí)現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當(dāng)ai≠-1時，將ai入棧；當(dāng)ai=-l時，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況（入棧滿等）給出相應(yīng)的信息。34、編寫程序，統(tǒng)計在輸入字符串中各個不同字符出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為A～Z這26個字母和0～9這10個數(shù)字）。35、寫出算法，求出中序線索二叉樹中給定值為x的結(jié)點(diǎn)之后繼結(jié)點(diǎn)，返回該后繼結(jié)點(diǎn)的指針。線索樹中結(jié)點(diǎn)結(jié)構(gòu)為：（ltag，lc，data，rc，rtag）。其中，data存放結(jié)點(diǎn)的值；lc、rc為指向左、右孩子或該結(jié)點(diǎn)前驅(qū)、后繼的指針，ltag、rtag為標(biāo)志域，若值為0，則lc、rc為指向左、右孩子的指針；若值為1，則lc、rc為指向其前驅(qū)、后繼結(jié)點(diǎn)的指針。

參考答案一、選擇題1、【答案】A2、【答案】B3、【答案】B4、【答案】D5、【答案】B6、【答案】A7、【答案】A8、【答案】C9、【答案】C10、【答案】B二、填空題11、【答案】2(N-1)12、【答案】n(n-1)/213、【答案】node->rflag==0；*x=bt；*x=node->right；prior（t，x）14、【答案】（Q，A，C，S，Q，D，F(xiàn)，X，R，H，M,Y）；（F，H，C，D，a，A，M，Q，R，S，Y，X）15、【答案】py->next=px->next；px->next=py16、【答案】FEGHDCB；BEF【解析】樹的前序序列對應(yīng)二叉樹的前序序列，該二叉樹轉(zhuǎn)換成森林時含三棵樹，其第一棵樹的前序是BEF。17、【答案】【解析】滿二叉樹沒有度為1的結(jié)點(diǎn)，度為0的結(jié)點(diǎn)等于度為2的結(jié)點(diǎn)個數(shù)+1。18、【答案】33三、判斷題19、【答案】×20、【答案】√21、【答案】×22、【答案】×23、【答案】×24、【答案】√25、【答案】√26、【答案】×27、【答案】×28、【答案】√四、簡答題29、答：兩棧共享一向量空間（一維數(shù)組），棧底設(shè)在數(shù)組的兩端，兩棧頂相鄰時為棧滿。設(shè)共享數(shù)組為S[MAX]，則一個棧頂指針為一l，另一個棧頂指針為MAX時，棧為空。用C語言寫的入棧操作push（i，x）如下：30、答：n個元素采用起泡排序法進(jìn)行排序，通常需要進(jìn)行n-1趟排序。第j趟起泡排序要進(jìn)行n-j次比較。在一趟排序中，若沒有記錄交換，則表示排序完成。因而，可通過設(shè)標(biāo)記來控制排序結(jié)束，下面語句段說明了標(biāo)記flag的使用。31、答：（1）算法的基本設(shè)計思想：先將n個數(shù)據(jù)由x0，x1，…，xp，…，xn－1原地逆置，得到xn－1，…，xp，xp－1，…，x0然后再將數(shù)組R中的前n－P個數(shù)和后P