數(shù)據(jù)結(jié)構與算法模擬題1111

1、《數(shù)據(jù)結(jié)構與算法》模擬題一、填空題：（共一、填空題：（共1515分）分）（每空一分）（每空一分）1.按照排序時，存放數(shù)據(jù)的設備，排序可分為內(nèi)部內(nèi)部排序和外部外部排序。2.圖的常用的兩種存儲結(jié)構是鄰接矩陣鄰接矩陣和鄰接表接表。3.數(shù)據(jù)結(jié)構中的三種基本的結(jié)構形式是x線性結(jié)構線性結(jié)構和樹形結(jié)構樹形結(jié)構、圖形結(jié)構圖形結(jié)構。4.一個高度為6的二元樹，最多有63個結(jié)點。5.線性查找的時間復雜度為：O(n)，折半查找的時間復雜度為：O(nlogn)、

2、堆分類的時間復雜度為：O(nlogn)。6.在采用散列法進行查找時，為了減少沖突的機會，散列函數(shù)必須具有較好的隨機性，在我們介紹的幾種散列函數(shù)構造法中，隨機性最好的是隨機數(shù)法隨機數(shù)法法、最簡單的構造方法是除留余數(shù)法除留余數(shù)法。7.線性表的三種存儲結(jié)構是：數(shù)組、鏈表鏈表、靜態(tài)鏈表靜態(tài)鏈表。二、回答下列問題：（共二、回答下列問題：（共3030分）分）1.現(xiàn)有如右圖的樹，回答如下問題：A）根結(jié)點有：6B）葉結(jié)點有：5學號：姓名：第3頁（共5頁

3、）5.分析下列程序的運行時間：A)voidmystery(intn)intijkf(i=1ini)f(j=i1j=nj)f(k=1k=jk)somestatementrequiringO(1)time這個應該是時間復雜度吧這個應該是時間復雜度吧：O(n^3)B）voidpodd(intn)intIjxyf(I=1I=nI)if(odd(I))f(j=Ij=nj)x=x1f(j=1j=Ij)y=y1O（n^2）6.已知數(shù)學表達式是(3b)