《數(shù)據(jù)結(jié)構(gòu)》蘭大2020年9月考試在線考核試題及答案

1、數(shù)據(jù)結(jié)構(gòu)蘭大2020年9月考試在線考核試題及答案若用單鏈表示列隊(duì)，那么應(yīng)選用()。A、帶尾指針的循環(huán)鏈表B、帶尾指針的非循環(huán)列隊(duì)C、帶頭指針的非循環(huán)鏈表D、帶頭指針的循環(huán)鏈表單鏈表的結(jié)點(diǎn)包含()和()。A、結(jié)點(diǎn)域，符號(hào)域B、數(shù)據(jù)域，符號(hào)域C、結(jié)點(diǎn)域，指針域D、數(shù)據(jù)域，指針域序例278、109、930經(jīng)過(guò)一趟基數(shù)排序后結(jié)果為()。A、930、278、109B、109、930、278C、109、278、930D、278、109、930函數(shù)substr(“DATASTRUCTURE”，5，9)的返回為()。A、“STRUCTURE”B、“DATA”C、“ASTRUCTUR”D、“DATASTRUCT

2、URE”設(shè)某完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中有()條邊。A、n(n-1)/2B、n(n-1)C、n²D、n²-1堆排是一種()排序。A、插入B、選擇C、交換D、歸并圖的廣度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的()。A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷對(duì)n個(gè)不同的排序碼進(jìn)行冒泡排序，在下列哪種情況下比較的次數(shù)最多()。A、從小到大排列好的B、從大到小排列好的C、元素?zé)o序D、元素基本有序如果只想得到1000個(gè)元素組成的序列中第5個(gè)最小元素之前的部分排序的序列，用()方法最快。A、起泡排序B、快速排列C、Shell排序D、堆排序E、單單選擇排序二叉樹(shù)的第K層的結(jié)點(diǎn)數(shù)最多

3、為()。A、2k-1B、2K+1C、2(k-1)+1D、2(k-1)棧是后進(jìn)先出的線性表。()A、正確B、錯(cuò)誤森林的先序遍歷與其對(duì)應(yīng)的二叉樹(shù)的中序遍歷對(duì)應(yīng)。()A、正確B、錯(cuò)誤對(duì)于哈希函數(shù)，沖突只能盡可能的少，不可能完全避免。()A、正確B、錯(cuò)誤線性表若采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中的可用存儲(chǔ)單元的地址必須連續(xù)。()A、正確B、錯(cuò)誤棧是限定在表尾進(jìn)行插入或刪除操作的線性表。()A、正確B、錯(cuò)誤設(shè)有一棵算術(shù)表達(dá)式樹(shù)，用什么方法可以對(duì)該樹(shù)所表示的表達(dá)式求值?寫(xiě)出二叉樹(shù)進(jìn)行前序和中續(xù)遍歷的過(guò)程。如何知道循環(huán)隊(duì)列是空還是滿?圖的遍歷(名詞解釋)稀疏矩陣(名詞解釋) 參考答案：A參考答案：D參考答案：A

4、參考答案：A參考答案：A參考答案：B參考答案：B參考答案：B參考答案：D參考答案：D參考答案：A參考答案：A參考答案：A參考答案：A參考答案：B參考答案：方法有二。一是對(duì)該算術(shù)表達(dá)式(二叉樹(shù))進(jìn)行后序遍歷，得到表達(dá)式的后序遍歷序列，再按后綴表達(dá)式求值；二是遞歸求出左子樹(shù)表達(dá)式的值，再遞歸求出右子樹(shù)表達(dá)式的值，最后按根結(jié)點(diǎn)運(yùn)算符(、-、*、/等)進(jìn)行最后求值。參考答案：前序遍歷：(1)訪問(wèn)根結(jié)點(diǎn)(2)前序遍歷左子樹(shù)(3)前序遍歷右子樹(shù)中序遍歷：(1)中序遍歷左子樹(shù)(2)訪問(wèn)根結(jié)點(diǎn)(3)中序遍歷右子樹(shù)參考答案：采用循環(huán)隊(duì)列是解決假溢出的途徑。另外，解決隊(duì)滿隊(duì)空的辦法有三：(1)設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空；(2)浪費(fèi)一個(gè)元素的空間，用于區(qū)別隊(duì)滿還是隊(duì)空；(3)使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)(即隊(duì)列長(zhǎng)度)。我們常采用方法(2)，即隊(duì)頭指針、隊(duì)尾指針中有一個(gè)指向?qū)嵲?，而另一個(gè)指向空閑元素。判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是：f=rear；隊(duì)滿標(biāo)志是：f=(r+1)%N參考答案：是從圖中某一頂點(diǎn)出發(fā)