華科2010級數(shù)據(jù)結構期末考試試題-a卷[1]

1、1得分《數(shù)據(jù)結構數(shù)據(jù)結構》考試題（閉卷）考試題（閉卷）A卷（電信系本科（電信系本科2010級2012年1月11日）日）姓名姓名班級班級學號學號題號一二三總分題分403030100得分一、回答下列問題一、回答下列問題(每題每題5分，共分，共4040分)1采用哪種方法可構建表示表達式的二叉樹，畫出表示表達式采用哪種方法可構建表示表達式的二叉樹，畫出表示表達式AB(CD)EF的二叉樹，并給出后序遍歷結果。的二叉樹，并給出后序遍歷結果。采用表達

2、式求值方法采用表達式求值方法AEFBCD后序遍歷結果后序遍歷結果ABCDEF2.待排序列有待排序列有256個關鍵字，采用錦標賽排序排出最小三個關鍵字的比較次數(shù)個關鍵字，采用錦標賽排序排出最小三個關鍵字的比較次數(shù)是多少？需多少個輔助空間。錦標賽排序空間復雜度是多少？是多少？需多少個輔助空間。錦標賽排序空間復雜度是多少？比較次數(shù)比較次數(shù)25588輔助空間輔助空間2551空間復雜度空間復雜度o(n)3對對n個記錄的線性表進行快速排序，為減少算

3、法的遞歸深度（空間）個記錄的線性表進行快速排序，為減少算法的遞歸深度（空間），以下敘，以下敘述正確的是（述正確的是（）A每次分割后，先處理較短的部分每次分割后，先處理較短的部分B每次分割后，先處理較長的部分每次分割后，先處理較長的部分C與算法每次分割后的處理順序無關與算法每次分割后的處理順序無關D以上三者都不對以上三者都不對4在在KMP算法中，已知模式串為算法中，已知模式串為ACBACBBAD寫出模式串的寫出模式串的next[j]函數(shù)函

4、數(shù)值，若主串為值，若主串為ADACBACACBACBBADABD給出匹配成功的比較次數(shù)。給出匹配成功的比較次數(shù)。next[j]函數(shù)值函數(shù)值011123412比較次數(shù)比較次數(shù)216393voidreverse（linklistqnext=p；p=q；(2)__________________(3)_____________________2設有設有5個互不相同的元素個互不相同的元素a、b、c、d、e，能否通過，能否通過7次比較就將其排好次

5、比較就將其排好序？如果能，請列出其比較過程；如果不能，則說明原因。序？如果能，請列出其比較過程；如果不能，則說明原因。（9分）分）3在排序算法的某一存儲結構中，有在排序算法的某一存儲結構中，有n個關鍵字存在一維向量個關鍵字存在一維向量K中，中，0號單元未號單元未用，試給出以下函數(shù)的功能及返回值用，試給出以下函數(shù)的功能及返回值0，1，1，2的含義（的含義（8分）分）intStL(sqlistkintn)if(n==0)return(0)i