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

1、數(shù)據(jù)結(jié)構(gòu)蘭大2020年9月考試在線考核試題及答案若用單鏈表示列隊，那么應(yīng)選用()。A、帶尾指針的循環(huán)鏈表B、帶尾指針的非循環(huán)列隊C、帶頭指針的非循環(huán)鏈表D、帶頭指針的循環(huán)鏈表單鏈表的結(jié)點包含()和()。A、結(jié)點域，符號域B、數(shù)據(jù)域，符號域C、結(jié)點域，指針域D、數(shù)據(jù)域，指針域序例278、109、930經(jīng)過一趟基數(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è)某完全無向圖中有n個頂點，則該完全無向圖中有()條邊。A、n(n-1)/2B、n(n-1)C、n²D、n²-1堆排是一種()排序。A、插入B、選擇C、交換D、歸并圖的廣度優(yōu)先遍歷算法類似于二叉樹的()。A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷對n個不同的排序碼進(jìn)行冒泡排序，在下列哪種情況下比較的次數(shù)最多()。A、從小到大排列好的B、從大到小排列好的C、元素?zé)o序D、元素基本有序如果只想得到1000個元素組成的序列中第5個最小元素之前的部分排序的序列，用()方法最快。A、起泡排序B、快速排列C、Shell排序D、堆排序E、單單選擇排序二叉樹的第K層的結(jié)點數(shù)最多

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

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