數(shù)據(jù)結(jié)構(gòu)考試試題

第8頁共8頁（密封線內(nèi)不要答題）………密………………（密封線內(nèi)不要答題）………密………………封………………線……………專業(yè)______________________班級姓名______________學號f考試科目數(shù)據(jù)結(jié)構(gòu)考試時間2015.1.9考試方式閉卷成績題號一二三四五核總分得分評卷人（滿分100分,考試時間120分鐘）一、填空題（每空1分，共25分）1、數(shù)據(jù)的存儲結(jié)構(gòu)主要有和兩種基本方法，不論哪種存儲結(jié)構(gòu)都要存儲兩方面的內(nèi)容：和。2、算法分析的目的是：，算法分析的兩個主要方面是、。3、一個具有n個結(jié)點的單鏈表，在p所指結(jié)點后插入一個新結(jié)點的時間復雜度為；在給定值為x的結(jié)點后插入一個新結(jié)點的時間復雜度為。4、非空的循環(huán)單鏈表由頭指針head指示，則其尾結(jié)點（由指針p所指）滿足。5、棧和隊列的主要區(qū)別在于：。6、在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，棧頂元素是棧底元素是。7、表達式a*（b+c）/d-e的后綴表達式是。8、在有n個葉子的哈夫曼樹中，葉子結(jié)點總數(shù)為，分支結(jié)點總數(shù)為。9、深度為k的二叉樹至少有個結(jié)點，至多有個結(jié)點。10、在一個有向圖中，所有頂點的度數(shù)之和等于所有弧數(shù)的倍。11、已知一個無向圖的鄰接矩陣表示，計算第j個頂點的入度的方法是。12、在一個有向圖中，若存在弧<vi，vj>、<vj，vk>、<vi，vk>，則在其拓撲序列中的，頂點vi，vj，vk的相對次序為。13、如果要將序列(50，16，23，68，94，70，73)建成堆，只需把16與交換。14、在索引表中，每個索引項至少包含有和等信息。15、設有40000個記錄，通過分塊劃分為若干子表并建立索引，那么為了提高查找效率，每一個子表的大小應設計為。二、選擇題（每題2分，共22分）1、使用雙鏈表存儲線性表，其優(yōu)點是可以()A、節(jié)約存儲空間B、提高檢索速度C、更方便數(shù)據(jù)的插入和刪除D、很快回收存儲空間2、對于n個元素組成的線性表，建立一個有序單鏈表的時間復雜度是()A、O(1)B、O(n)C、O(n2)D、O(nlog2n)（密封線內(nèi)不要答題）………（密封線內(nèi)不要答題）………密………………封………………線……………專業(yè)______________________班級姓名______________學號fA、s->next=p->next；p->next=s；B、q->next=s；s->next=p；C、p->next=s->next；s->next=p；D、p->next=s；s->next=q；4、設線性表有n個元素，以下操作中，()在順序表上實現(xiàn)比在鏈表上實現(xiàn)的效率更高。A、輸出第i(1≤i≤n)個元素值B、交換第1個和第2個元素的值C、順序輸出所有n個元素D、查找與給定值x相等的元素在線性表中的序號5、下面的說法中，不正確的是()A、數(shù)組是一種定長的線性結(jié)構(gòu)B、數(shù)組是一種隨機存取結(jié)構(gòu)C、數(shù)組的基本操作有存取、修改、檢索等，沒有插入與刪除操作D、除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索等6、設主串S=“ababaababcb”，模式T=“ababc”，則該模式的next[3]值為()A、-1B、0C、1D、27、含n個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過

()A、1B、n/2C、n-1D、n8、討論樹、森林和二叉樹的關系，目的是為了()A、借助二叉樹上的運算方法去實現(xiàn)對樹的一些運算B、將樹、森林按二叉樹的存儲方式進行存儲并利用二叉樹的算法解決樹的有關問題C、將樹、森林轉(zhuǎn)換成二叉樹D、體現(xiàn)一種技巧，沒有什么實際意義9、按{12，24，36，90，52，30}的順序構(gòu)成的平衡二叉樹，其根結(jié)點是()A、24B、36C、52D、3010、長度為20的有序表采用折半查找，共有()個元素的查找長度為3。A、1B、2C、3D、411、下列排序方法中，時間性能與待排序記錄的初始狀態(tài)無關的是()A、插入排序和快速排序B、歸并排序和快速排序C、選擇排序和歸并排序D、插入排序和歸并排序 三、判斷題（每題1分，共10分）1、邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關。（）2、線性表的鏈接存儲結(jié)構(gòu)是一種隨機存取結(jié)構(gòu)。（）3、循環(huán)隊列的引入是為了克服假溢出。（）4、具有100個結(jié)點的完全二叉樹的葉子結(jié)點樹為50。（）5、二叉樹是度為2的樹。（）6、在線索二叉樹中，任一結(jié)點均有指向其前驅(qū)和后繼的線索。（）7、圖的深度優(yōu)先遍歷類似于樹的前序遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是棧。（）8、在AOE網(wǎng)中一定只有一條關鍵路徑。（）9、二叉排序樹中，最小值結(jié)點的左指針一定為空。（）10、二叉排序樹的的查找和折半查找的時間性能相同。（）（密封線內(nèi)不要答題）………密………………（密封線內(nèi)不要答題）………密………………封………………線……………專業(yè)______________________班級姓名______________學號f1、對于一個n行m列的上三角矩陣A，如果以行優(yōu)先的方式用一維數(shù)組B從0號位置開始存儲，，求元素aij(1≤i≤n，1≤j≤m)在數(shù)組B中的存儲位置。(3分)2、對下圖所示的一個無向帶權圖：(13分)(1)請給出該圖的鄰接矩陣存儲結(jié)構(gòu)表示。(2)請選用一種方法求出該圖的最小生成樹。(3)將(2)求出的樹轉(zhuǎn)換成二叉樹。1abedf1abedfc65526632題圖3、給定關鍵碼集合{26，25，20，34，28，24，45，64，42}，設定裝填因子為0.6。(5分)(1)請給出除留余數(shù)法的散列函數(shù)。(2)采用線性探測法處理沖突，試構(gòu)造閉散列表，并計算查找成功的平均查找長度。4、已知數(shù)據(jù)序列為（24，10，18，40，12，62，48），對該數(shù)據(jù)序列排序，寫出插入排序，