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

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

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

3、）5.分析下列程序的運(yùn)行時(shí)間：A)voidmystery(intn)intijkf(i=1ini)f(j=i1j=nj)f(k=1k=jk)somestatementrequiringO(1)time這個(gè)應(yīng)該是時(shí)間復(fù)雜度吧這個(gè)應(yīng)該是時(shí)間復(fù)雜度吧：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ù)學(xué)表達(dá)式是(3b)