數(shù)據(jù)結(jié)構(gòu)各章作業(yè)題目

第一章作業(yè)一、選擇題被計(jì)算機(jī)加工的數(shù)據(jù)元素不是孤立的，它們相互之間一般存在某種關(guān)系，往常把數(shù)據(jù)元素之間的這類關(guān)系稱為()。A.規(guī)則B.結(jié)構(gòu)C.會合D.運(yùn)算2.在Data_Structure=(D,S)中，D是()的有限會合。A.數(shù)據(jù)元素B.算法C.數(shù)據(jù)操作D.數(shù)據(jù)對象計(jì)算機(jī)所辦理的數(shù)據(jù)一般擁有某種關(guān)系，這是指()之間存在的某種關(guān)系。A.數(shù)據(jù)與數(shù)據(jù)B.數(shù)據(jù)元素與數(shù)據(jù)元素C.元素內(nèi)數(shù)據(jù)項(xiàng)與數(shù)據(jù)項(xiàng)D.數(shù)據(jù)文件內(nèi)記錄與記錄次序儲存表示中數(shù)據(jù)元素之間的邏輯關(guān)系是由()表示的。A.指針B.邏輯次序C.儲存地點(diǎn)D.問題上下文鏈接儲存表示中數(shù)據(jù)元素之間的邏輯關(guān)系是由()表示的。A.指針B.邏輯次序C.儲存地點(diǎn)D.問題上下文從邏輯上可將數(shù)據(jù)結(jié)構(gòu)分為()。A.動向結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.內(nèi)部結(jié)構(gòu)和外面結(jié)構(gòu)D.線性結(jié)構(gòu)和非線性結(jié)構(gòu)以下選項(xiàng)屬于線性結(jié)構(gòu)的是()。A.廣義表B.二叉樹C.串D.稀少數(shù)組以下選項(xiàng)屬于非線性結(jié)構(gòu)的是()。A.廣義表B.行列C.優(yōu)先行列D.棧以部下于邏輯結(jié)構(gòu)的是()A.次序表B.散列表C.有序表D.單鏈表一個(gè)完好的算法應(yīng)當(dāng)擁有()等特征。A.可履行性、可改正性和可保護(hù)性B.可行性、確立性和有窮性1C.確立性、有窮性和靠譜性D.正確性、可讀性和有效性11.若一個(gè)問題既能夠用迭代方法也能夠用遞歸方法求解，則()的方法擁有更高的時(shí)空效率。A.迭代B.遞歸C.先遞歸后迭代D.先迭代后遞歸一個(gè)遞歸算法一定包含()A.遞歸部分B.停止條件和遞歸部分C.迭代部分D.停止條件和迭代部分算法的時(shí)間復(fù)雜度與()有關(guān)。A.問題規(guī)模B.源程序長度C.計(jì)算機(jī)硬件運(yùn)轉(zhuǎn)速度D.編譯后履行程序的質(zhì)量二、指出以下各算法的功能并求出其時(shí)間復(fù)雜度。(1)intPrime(intn){inti=2,x=(int)sqrt(n);數(shù)據(jù)項(xiàng)B.數(shù)據(jù)記錄C.數(shù)據(jù)元素D.數(shù)據(jù)字段次序表是線性表的()儲存表示。A.有序B.連續(xù)C.數(shù)組D.次序存取2.若長度為n的非空線性表采納次序儲存結(jié)構(gòu)，在表中的第i個(gè)地點(diǎn)插入一個(gè)數(shù)據(jù)元素，i的合法值應(yīng)當(dāng)是()A.1inB.1in1C.0in1D.0in3.若設(shè)一個(gè)次序表的長度為n，那么，在表中次序查找一個(gè)值為x的元素時(shí)，在等概率的狀況下，查找成功的數(shù)據(jù)均勻比較次數(shù)為()A.nB.n/2C.(n1)/2D.(n1)/24.在長度為n的次序表的表尾插入一個(gè)新的元素的時(shí)間復(fù)雜度為()A.O(n)B.O(1)C.O(n2)D.O(log2n)5.數(shù)據(jù)結(jié)構(gòu)反應(yīng)了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。單鏈表是一種()。A.次序儲存線性表B.非次序儲存非線性表C.次序儲存非線性表D.非次序儲存線性表26.單鏈表又稱為線性鏈表，在單鏈表上實(shí)行插入和刪除操作()A.不需挪動結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針B.不需挪動結(jié)點(diǎn)，只要改變結(jié)點(diǎn)指針C.只要挪動結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針D.既需挪動結(jié)點(diǎn)，又需改變結(jié)點(diǎn)指針7.已知L是帶頭結(jié)點(diǎn)的單鏈表，則刪除首元素結(jié)點(diǎn)的語句是()A.L=L->next;B.L->next=L->next->next;C.L=L->next->next;L->next=L;已知單鏈表A長度為m，單鏈表B長度為n，若將B鏈接在A的末端，在沒有鏈尾指針的狀況下，算法的時(shí)間復(fù)雜度應(yīng)為()。A.O(1)B.O(m)C.O(n)D.O(mn)9.給定有n個(gè)元素的一維數(shù)組，成立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是()A.O(1)B.O(n)C.O(n2)D.O(nlog2n)二、算法設(shè)計(jì)1.設(shè)計(jì)一個(gè)算法，從次序表L中(SqListL)刪除擁有給定值x(ElemTypex)的全部元素。設(shè)計(jì)一個(gè)算法，從有序次序表中刪除全部其值重復(fù)的元素，使表中全部元素的值均不同樣。設(shè)計(jì)一個(gè)算法，在非遞減有序的帶頭結(jié)點(diǎn)的單鏈表中刪除值同樣的剩余結(jié)點(diǎn)。3第三章作業(yè)一、選擇題1.用S表示進(jìn)棧操作，用X表示出棧操作，若元素的進(jìn)棧次序是1234，為了獲得1342的出棧次序，相應(yīng)的S和X的操作序列為()D.SXSSXSXX假定一個(gè)棧的輸入序列是1，2，3，4，則不行能獲得的輸出序列是()A.1,2,3,4B.4,1,2,3C.4,3,2,1D.1,3,4,23.已知一個(gè)棧的進(jìn)棧序列為1,2,3,,n，其輸出序列的第一個(gè)元素是i，則第j個(gè)出棧元素是()。A.jiB.niC.ji1D.不確立4.已知一個(gè)棧的進(jìn)棧序列為1,2,3,,n，其輸出序列是p1,p2,p3,,pn。若p1n，則pi的值是()A.iB.niC.ni1D.不確立5.已知一個(gè)棧的進(jìn)棧序列為1,2,3,,n，其輸出序列是p1,p2,p3,,pn。若p13，則p2的值是()A.必定是2B.必定是1C.可能是1D.可能是26.已知一個(gè)棧的進(jìn)棧序列為p1,p2,p3,,pn，其輸出序列是1,2,3,,n。若p31，則p1的值是()A.必定是2B.可能是2C.不行能是2D.必定是37.已知一個(gè)棧的進(jìn)棧序列為p1,p2,p3,,pn，其輸出序列是1,2,3,,n。若p33，則p1的值是()A.必定是2B.可能是2C.不行能是1D.必定是18.已知一個(gè)棧的進(jìn)棧序列為p1,p2,p3,,pn，其輸出序列是1,2,3,,n。若pn1，則p1的值是()4A.ni1B.niC.iD.不確立設(shè)棧S和行列Q的初始狀態(tài)均為空，元素1,2,3,4,5,6,7，挨次進(jìn)入S。假如每個(gè)元素出棧后立刻進(jìn)入行列Q，且7個(gè)元素的出隊(duì)次序?yàn)?,4,3,6,5,1,7，則棧S的容量起碼是()10.對中綴表達(dá)式32*(42*26*3)5求值，在求值過程中掃描到6時(shí)，操作數(shù)棧和操作符棧的內(nèi)容分別是()A.3,2,4,2,2和+,*,(,+,*B.3,2,4,4和+,*,(,+C.3,2,8和+,*,(D.3,2,8,6和+,*,(,-二、算法設(shè)計(jì)題詳見《數(shù)據(jù)結(jié)構(gòu)題集(C語言版)》第25頁。詳見《數(shù)據(jù)結(jié)構(gòu)題集(C語言版)》第25頁。5第四章作業(yè)串是一種特別的線性表，其特別性表此刻()A.能夠次序儲存B.數(shù)據(jù)元素是一個(gè)字符C.能夠鏈?zhǔn)絻Υ鍰.數(shù)據(jù)元素能夠是多個(gè)字符12.設(shè)有兩個(gè)串T和P，求P在T中初次出現(xiàn)的地點(diǎn)的運(yùn)算叫做()。A.求子串B.模式般配C.串替代D.串通接13.下邊對于串的表達(dá)中，哪一個(gè)是不正確的（）A．串是字符的有限序列B．空串是由空格構(gòu)成的串C．模式般配是串的一種重要運(yùn)算D．串既能夠采納次序儲存，也能夠采納鏈?zhǔn)絻Υ?4.串的長度是指（）A．串中所含不一樣字母的個(gè)數(shù)B．串中所含字符的個(gè)數(shù)C．串中所含不一樣字符的個(gè)數(shù)D．串中所含非空格字符的個(gè)數(shù)兩個(gè)串相等的充分必需條件是（）A．串中所含的字符同樣B．串中所含字符的個(gè)數(shù)同樣，且對應(yīng)地點(diǎn)上的字符也同樣C．串中所含的字符個(gè)數(shù)同樣D．串中對應(yīng)地點(diǎn)上的字符同樣6.已知p=”abcaabbabcabaacbacb”，求出next函數(shù)值。6第五章作業(yè)一、選擇題數(shù)組往常擁有的操作是()A.次序存取B.直接存取C.散列存取D.索引存取多維數(shù)組其實(shí)是由()實(shí)現(xiàn)的。A.一維數(shù)組B.多項(xiàng)式C.三元組表D.簡單變量18.在二維數(shù)組A[8][10]中，每一個(gè)數(shù)組元素A[i][j]占用3個(gè)儲存空間，全部數(shù)組元素接踵寄存于一個(gè)連續(xù)的儲存空間中，則寄存該數(shù)組起碼需要的儲存空間是()。A.80B.100C.240D.27019.一個(gè)二維數(shù)組A[10][20]按行寄存于一個(gè)連續(xù)的儲存空間中，A[0][0]的儲存地點(diǎn)是200，每個(gè)數(shù)組元素占1個(gè)儲存字，則A[6][2]的地點(diǎn)為()A.226B.322C.341D.34220.一個(gè)二維數(shù)組A[10][20]按列寄存于一個(gè)連續(xù)的儲存空間中，A[0][0]的儲存地點(diǎn)是200，每個(gè)數(shù)組元素占1個(gè)儲存字，則A[6][2]的地點(diǎn)為()A.226B.322C.341D.34221.在二維數(shù)組A[9][10]中，每個(gè)數(shù)組元素占用3個(gè)儲存單元，從首地點(diǎn)SA開始按行連續(xù)寄存，在這類狀況下，元素A[8][5]的開端地點(diǎn)為()A.SA+141B.SA+144C.SA+222D.SA+25522.將一個(gè)nn的對稱矩陣A的下三角部分按寄存在一個(gè)一維數(shù)組B中，A[0][0]寄存在B[0]中，那么第i行的對角元素A[i][i]在B中的寄存地點(diǎn)是()A.(i3)i/2B.(i1)i/2C.(2ni1)i/2D.(2ni1)i/223.將一個(gè)nn的對稱矩陣A的上三角部分按寄存在一個(gè)一維數(shù)組B中，A[0][0]寄存在B[0]中，那么第i行的對角元素A[i][i]在B中的寄存地點(diǎn)是()A.(i3)i/2B.(i1)i/2C.(2ni1)i/2D.(2ni1)i/224.設(shè)A是一個(gè)nn的對稱矩陣，將A的對角線及對角線上方的元素以列優(yōu)先(以列為主序)的方式存放在一維數(shù)組B[n(n1)/2]中，則矩陣中任一元素aij(0i,jn,ij)在B中的寄存地點(diǎn)是()7A.j(j1)/2iB.j(j1)/2i1C.i(i1)/2jD.i(i1)/2j125.設(shè)n階三對角矩陣A的三條對角線上的元素被按行壓縮儲存到一維數(shù)組B中，A[0][0]寄存于B[0]。若某矩陣元素在B中寄存的地點(diǎn)在k，那么該元素在原始矩陣中的行號i是()A.(k1)/3B.k/3C.(k1)/3D.(k1)/3二、簡答題26.設(shè)有一個(gè)3維數(shù)組A[10][20][15]，按行優(yōu)先寄存于一個(gè)連續(xù)的儲存空間中，每個(gè)數(shù)組元素占4個(gè)儲存字，首元素A[0][0][0]的儲存地點(diǎn)是1000，則A[7][8][9]寄存于什么地方。27.設(shè)有一個(gè)二維數(shù)組A[m][n]，假定A[0][0]寄存地點(diǎn)在644(10)，A[2][2]寄存在676(10)，每個(gè)元素占1個(gè)儲存單元，問A[3][3](10)寄存在什么地點(diǎn)腳注(10)表示用十進(jìn)制表示。28.對于一個(gè)nn矩陣A的任一元素a[i][j]，按行儲存和按列儲存時(shí)的地點(diǎn)之差是多少(假定兩種儲存的開始儲存地點(diǎn)LOC(0,0)以及元素所占儲存單元數(shù)d同樣)29.設(shè)有n階三對角矩陣A，將其3條對角線上的元素逐行儲存到數(shù)組B[0:3n3]中，使得B[k]A[i][j]，且B[0]A[0][0]，求用i，j表示k的下標(biāo)變換公式。用k表示i，j的下表變換公式。30.設(shè)有一個(gè)nn的對稱矩陣A，將其下三角部分按行壓縮寄存于一個(gè)一維數(shù)組B中，A[0][0]寄存于B[0]，試問：(1)一維數(shù)組B有多少個(gè)元素(2)A中的隨意一個(gè)元素A[i][j]應(yīng)存于一維數(shù)組B的什么下標(biāo)地點(diǎn)31.設(shè)有一個(gè)nn的對稱矩陣A，將其上三角部分按列壓縮寄存于一個(gè)一維數(shù)組B中，A[0][0]寄存于B[0]，試問：(1)一維數(shù)組B有多少個(gè)元素(2)A中的隨意一個(gè)元素A[i][j]應(yīng)存于一維數(shù)組B的什么下標(biāo)地點(diǎn)8第六章作業(yè)一、選擇題32.一顆有n個(gè)結(jié)點(diǎn)的樹的全部結(jié)點(diǎn)的度數(shù)之和為()。A.n-1B.nC.n1D.2n33.設(shè)一顆高度為h的滿二叉樹有n個(gè)結(jié)點(diǎn)，此中有m個(gè)葉結(jié)點(diǎn)，則()A.nhmB.hm2nC.mh1D.n2h134.一顆有124個(gè)葉結(jié)點(diǎn)的完好二叉樹最多有()個(gè)結(jié)點(diǎn)。A.247B.248C.249D.25035.一顆有129個(gè)葉結(jié)點(diǎn)的完好二叉樹最罕有()個(gè)結(jié)點(diǎn)。A.254B.255C.257D.25836.設(shè)完好二叉樹的第6層有24個(gè)葉結(jié)點(diǎn)，則此樹最多有()個(gè)結(jié)點(diǎn)。A.55B.79C.81D.12737.擁有1000個(gè)結(jié)點(diǎn)的完好二叉樹的次基層的葉結(jié)點(diǎn)個(gè)數(shù)為()。A.11B.12C.24D.3638.用次序儲存的方法將n個(gè)結(jié)點(diǎn)的完好二叉樹中全部結(jié)點(diǎn)按層逐一次序寄存在一維數(shù)組R[n]中，當(dāng)編號為0的根結(jié)點(diǎn)寄存于R[0]時(shí)，若結(jié)點(diǎn)R[i]有左孩子，則左孩子是()。A.R[2i1]B.R[2i]C.R[2i1]D.R[2i2]39.用次序儲存的方法將n個(gè)結(jié)點(diǎn)的完好二叉樹中全部結(jié)點(diǎn)按層逐一次序寄存在一維數(shù)組R[n]中，當(dāng)編號為0的根結(jié)點(diǎn)寄存于R[0]時(shí)，若結(jié)點(diǎn)R[i]有右孩子，則右孩子是()。A.R[2i1]B.R[2i]C.R[2i1]D.R[2i2]40.二叉樹的葉結(jié)點(diǎn)在前序、中序和后序遍歷過程中的相對次序()。A.發(fā)生改變B.不發(fā)生變化C.沒法確立D.以上均不對41.設(shè)n，m為一顆二叉樹上的兩個(gè)結(jié)點(diǎn)，在該二叉樹的中序遍歷序列中n在m前的條件是()。A.n在m右方B.n是m的先人C.n在m左方D.n是m的后代42.設(shè)一顆二叉樹的前序序列為abdec，中序序列為dbeac，則該二叉樹的后序遍歷次序是()。9A.abdecB.debacC.debcaD.abedc43.設(shè)一顆二叉樹的中序序列為badce，后序序列為bdeca，則該二叉樹的前序遍歷次序是()。A.adbecB.decabC.debacD.abcde對二叉樹的結(jié)點(diǎn)從1開始連續(xù)編號，要求每個(gè)結(jié)點(diǎn)的編號大于其左、右孩子的編號，同一結(jié)點(diǎn)的左、右孩子中，其左孩子編號小于其右孩子編號，則可采納()遍歷實(shí)現(xiàn)二叉樹的結(jié)點(diǎn)編號。A.先序B.中序C.后序D.層序次45.假如T是由有序樹T變換成的二叉樹，那么T中結(jié)點(diǎn)的先根遍歷次序?qū)?yīng)T中結(jié)點(diǎn)的()遍歷22次序。A.前序B.中序C.后序D.層序次46.假如T2是由有序樹T變換成的二叉樹，那么T中結(jié)點(diǎn)的后根遍歷次序?qū)?yīng)T2中結(jié)點(diǎn)的()遍歷次序。A.前序B.中序C.后序D.層序次47.用n個(gè)權(quán)值結(jié)構(gòu)出來的Huffman樹共有()個(gè)結(jié)點(diǎn)。A.2n1B.2nC.2n1D.n148.由權(quán)值為8,4,5,7的4個(gè)葉結(jié)點(diǎn)結(jié)構(gòu)一顆Huffman樹，該樹的帶權(quán)路徑長度為()。A.24B.36C.48D.72二、簡答題設(shè)二叉樹根結(jié)點(diǎn)所在層次為1，樹的深度d為距離根最遠(yuǎn)的葉結(jié)點(diǎn)所在的層次，試回答以下問題：(1)試精準(zhǔn)給出深度為d的完好二叉樹的不一樣二叉樹的棵數(shù)；(2)試精準(zhǔn)給出深度為d的滿二叉樹的不一樣二叉樹棵數(shù)。50.假如一棵樹有n1個(gè)度為1的結(jié)點(diǎn)，有n2個(gè)度為2的結(jié)點(diǎn)，，有nm個(gè)度為m的結(jié)點(diǎn)，試問有多少個(gè)度為0的結(jié)點(diǎn)已知一棵二叉樹的前序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ。(1)畫出這棵二叉樹；(2)給出這棵二叉樹后序遍歷序列；(3)畫出這棵二叉樹變換成對應(yīng)的樹(或叢林)。假定用于通訊的電文僅有8個(gè)字母A,B,C,D,E,F,G,H構(gòu)成，各字母在電文中出現(xiàn)的頻次分別為5,25,3,6,10,11,36,4。試為這8個(gè)字母設(shè)計(jì)不等長Huffman編碼，并給出該電文的總碼數(shù)。三、算法設(shè)計(jì)1053.設(shè)二叉樹的儲存結(jié)構(gòu)為二叉鏈表，編寫一個(gè)遞歸算法，統(tǒng)計(jì)二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)。54.設(shè)二叉樹的儲存結(jié)構(gòu)為二叉鏈表，編寫一個(gè)遞歸算法，統(tǒng)計(jì)二叉樹中度為2的結(jié)點(diǎn)個(gè)數(shù)。55.設(shè)樹T以孩子-兄弟鏈表作為其儲存表示，編寫一個(gè)算法統(tǒng)計(jì)樹T的葉結(jié)點(diǎn)個(gè)數(shù)。56.設(shè)樹T以孩子-兄弟鏈表作為其儲存表示，編寫一個(gè)算法計(jì)算樹T的高度。11第七章作業(yè)一、選擇題1.擁有n個(gè)極點(diǎn)且每一對不一樣極點(diǎn)間都有一條邊的無向圖被稱為()。A.完好無向圖B.無向連通圖C.無向強(qiáng)連通圖D.無向樹圖2.一個(gè)有n個(gè)極點(diǎn)的無向圖中邊數(shù)最多有()條。A.nB.n(n1)C.n(n1)/2D.2n3.對于擁有n(n1)個(gè)極點(diǎn)的強(qiáng)連通圖，其有向邊條數(shù)起碼是()A.n1B.nC.n1D.n24.設(shè)G是一個(gè)非連通無向圖，有15條邊，則該圖的極點(diǎn)數(shù)起碼有()個(gè)。A.5B.6C.7D.85.在一個(gè)擁有n個(gè)極點(diǎn)的有向圖中，若全部極點(diǎn)的岀度之和為s，則全部極點(diǎn)的入度之和為()。A.sC.s+1D.n一個(gè)有n個(gè)極點(diǎn)和n條邊的無向圖必定是()。A.重連通圖B.不連通圖C.無環(huán)的D.有環(huán)的無向圖的毗鄰矩陣是一個(gè)()。A.對稱矩陣B.零矩陣C.上三角矩陣D.對角矩陣8.有n個(gè)極點(diǎn)和e條邊的無向圖采納毗鄰矩陣儲存，零元素的個(gè)數(shù)為()。A.eB.2eC.n2eD.n22e帶權(quán)有向圖G用毗鄰矩陣A儲存，則極點(diǎn)i的入度等于A中()。A.第i行非∞的元素之和B.第i列非∞的元素之和C.第i行非∞且非0的元素個(gè)數(shù)D.第i列非∞且非0的元素個(gè)數(shù)10.設(shè)圖有n個(gè)極點(diǎn)和e條邊，采納毗鄰矩陣時(shí)，遍歷圖的極點(diǎn)所需時(shí)間為()。A.O(n)B.O(n2)C.O(e)D.O(ne)11.設(shè)圖有n個(gè)極點(diǎn)和e條邊，采納毗鄰表時(shí)，遍歷圖的極點(diǎn)所需時(shí)間為()。12A.O(ne)B.O(n2)C.O(e)D.O(ne)圖的深度優(yōu)先搜尋近似于樹的()序次遍歷。A.先根B.中根C.后根D.層圖的廣度優(yōu)先搜尋近似于樹的()序次遍歷。A.先根B.中根C.后根D.層14.采納毗鄰表儲存的圖的深度優(yōu)先搜尋算法近似于二叉樹的()。A.中序遍歷B.前序遍歷C.后序遍歷D.層次遍歷15.采納毗鄰表儲存的圖的廣度優(yōu)先搜尋算法近似于二叉樹的()。A.中序遍歷B.前序遍歷C.后序遍歷D.層次遍歷16.假如從無向圖的任一極點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜尋即可接見全部極點(diǎn)，則該圖必定是()。A.強(qiáng)連通圖B.連通圖C.有回路D.一棵樹17.假如一個(gè)連通網(wǎng)絡(luò)G中各邊權(quán)值互不同樣，權(quán)重最小的邊必定包含在G的()生成樹中。A.最小B.任何C.廣度優(yōu)先D.深度優(yōu)先任何一個(gè)連通圖的最小生成樹()。A.只有一棵B.有一棵或多棵C.必定有多棵D.可能不存在19.一個(gè)有n個(gè)極點(diǎn)和e條邊的連通圖的生成樹有()條邊。A.nB.e1設(shè)一個(gè)n個(gè)極點(diǎn)的帶權(quán)連通圖有nlog2n條邊，則應(yīng)當(dāng)選通()算法來求這個(gè)圖的最小生成樹，進(jìn)而使計(jì)算時(shí)間較少。D.BFS求最短路徑的Dijkstra算法的時(shí)間復(fù)雜度為()。A.O(n)B.O(ne)C.O(n2)D.O(ne)求最短路徑的Floyd算法的時(shí)間復(fù)雜度為()。A.O(n)B.O(ne)C.O(n2)D.O(n3)23.設(shè)有向圖擁有n個(gè)極點(diǎn)和e條邊，假如用毗鄰表作為它的儲存結(jié)構(gòu)，則拓?fù)渑判虻臅r(shí)間復(fù)雜度為()。13A.O(n)B.O(ne)C.O(n2)D.O(ne)設(shè)有向圖擁有n個(gè)極點(diǎn)和e條邊，假如用毗鄰矩陣作為它的儲存結(jié)構(gòu)，則拓?fù)渑判虻臅r(shí)間復(fù)雜度為()。A.O(nlog2e)B.O(ne)C.O(n2)D.O(ne)二、應(yīng)用題針對圖1所示的有向圖，畫出該圖的毗鄰矩陣、毗鄰表和逆毗鄰表。ADBEbeadgCFcf圖1圖226.對圖2所示的無向圖，從極點(diǎn)a開始進(jìn)行深度優(yōu)先遍歷，給出2個(gè)可獲得的極點(diǎn)接見序列；從頂點(diǎn)a開始進(jìn)行廣度優(yōu)先遍歷，給出2個(gè)可獲得的極點(diǎn)接見序列。27.已知一個(gè)帶權(quán)連通圖如圖3所示，分別使用Prim算法和Kruskal算法求其最小生成樹。B121520a3b12cAC105E81510651689D4Fd8e9f圖3圖428.已知一個(gè)帶權(quán)有向圖如圖4所示，用Dijkstra算法求從極點(diǎn)a到其他各極點(diǎn)的最短路徑及路徑長度。以下圖的AOE網(wǎng)，求達(dá)成此工程最少要多少天(設(shè)弧上的權(quán)值為天數(shù))；每項(xiàng)活動ai的最早開始時(shí)間e(ai)和最遲開始時(shí)間l(ai)；哪些是重點(diǎn)活動；14能否存在某些活動，當(dāng)其提升速度后能使整個(gè)工程縮散工期BF5344ADGJ315266EI342CH圖515第九章作業(yè)一、選擇題次序查找算法合用于()。A.線性表B.查找樹C.查找網(wǎng)D.連通圖次序查找法合用于線性表的()。A.散列儲存B.壓縮儲存C.索引儲存D.次序或鏈接儲存32.采納次序查找方式查找長度為n的次序表時(shí)，均勻查找長度為()A.nB.n/2C.(n1)/2D.(n1)/233.假如有5個(gè)重點(diǎn)嗎{a,b,c,d,e}放在次序表中，他們的查找概率分別為{,,,.015,}，可使均勻查找長度達(dá)到最小的寄存方式是()。A.d,a,b,c,eB.e,d,c,b,aC.a,b,c,d,eD.a,c,e,d,b對于長度為n的有序單鏈表，若查找每個(gè)元素的概率相等，則次序查找表中任一元素的查找成功的均勻查找長度為()A.n/4B.n/2C.(n1)/2D.(n1)/2對線性表進(jìn)行折半查找時(shí)，要求線性表一定()A.以次序方式儲存B.以鏈接方式儲存C.以次序方式儲存，且結(jié)點(diǎn)按重點(diǎn)嗎有序擺列D.以鏈接方式儲存，且結(jié)點(diǎn)按重點(diǎn)嗎有序擺列36.采納折半查找法查找長度為n的有序次序表時(shí)，均勻查找長度為()A.O(n)B.O(log2n)C.O(n2)D.O(nlogn)37.對于長度為18的有序次序表，若采納折半查找，則查找第15個(gè)元素的查找次數(shù)為()。A.3B.4C.5D.638.已知有序次序表(13,18,24,35,47,50,62,83,90,115,134)，若采納折半查找法查找值為18的元素時(shí)，查找成功的數(shù)據(jù)比較次數(shù)為()。A.1B.2C.3D.439.使用散列法時(shí)確立元素儲存地點(diǎn)的依照是()。16A.元素的序號B.元素個(gè)數(shù)C.重點(diǎn)嗎D.非碼屬性40.設(shè)一個(gè)散列表中有n個(gè)元素，用散列法進(jìn)行查找的均勻查找長度是()。A.O(1)B.O(n)C.O(log2n)D.O(n2)41.使用散列函數(shù)將元素的重點(diǎn)嗎映照為散列地點(diǎn)時(shí)，常會發(fā)生矛盾。此時(shí)的矛盾是指()。A.兩個(gè)元素?fù)碛型瑯拥男蛱朆.兩個(gè)元素的重點(diǎn)碼不一樣，而非重點(diǎn)碼同樣C.不一樣重點(diǎn)碼對應(yīng)到同樣的儲存地點(diǎn)D.裝載因子過大，數(shù)據(jù)元素過多計(jì)算出的地點(diǎn)散布最均勻的散列函數(shù)是()。A.數(shù)值剖析法B.除留余數(shù)法C.平方取中法D.折疊法43.將10個(gè)元素散列到大小為100000個(gè)元素的散列表中，()產(chǎn)生矛盾。A.必定會B.必定不會C.仍可能會D.以上都不對44.采納線性探測法解決矛盾時(shí)計(jì)算出的一系列“下一個(gè)空位”()。A.一定大于等于原散列地點(diǎn)B.一定小于等于原散列地點(diǎn)C.能夠大于或小于但不等于原散列地點(diǎn)D.對地點(diǎn)在哪處沒有限制45.包含有4個(gè)結(jié)點(diǎn)的元素值互不同樣的二叉查找樹有()棵。A.4B.6C.10D.1446.利用逐一數(shù)據(jù)插入的方法成立序列{35,45,25,55,50,10,15,30,40,20}對應(yīng)的二叉查找樹后，查找元素20需要進(jìn)行()次元素之間的比較。A.4B.5C.7D.1047.一顆高度為h的AVL樹，若其每個(gè)非葉子結(jié)點(diǎn)的均衡因子都是0，則該樹共有()個(gè)結(jié)點(diǎn)。A.2h11B.2h1C.2h11D.2h1高度為7的AVL樹最罕有()個(gè)結(jié)點(diǎn)。高度為7的AVL樹最多有()個(gè)結(jié)點(diǎn)。A.63B.64C.65D.127二、應(yīng)用題50.設(shè)有一個(gè)重點(diǎn)碼的輸入序列{55,31,11,37,46,73,63}，從空樹開始結(jié)構(gòu)AVL樹，畫出每加入一個(gè)17新結(jié)點(diǎn)時(shí)二叉樹的形態(tài)。若發(fā)生不均衡，指明需做的均衡旋轉(zhuǎn)的種類及均衡旋轉(zhuǎn)的結(jié)果。分別畫出在圖1所示的AVL樹中插入15、36后樹的變化。假如有均衡化旋轉(zhuǎn)，注明有關(guān)結(jié)點(diǎn)均衡因子的變化(注意，15和36是各自獨(dú)立插入到圖1所示的AVL樹中)。1393861224431202741471821263140圖152.已知含12個(gè)重點(diǎn)字的有序表及其相應(yīng)的權(quán)值以下表，試挨次優(yōu)查找樹的結(jié)構(gòu)算法，畫出由這12個(gè)重點(diǎn)字結(jié)構(gòu)所得的次優(yōu)查找樹，并計(jì)算它的PH值。重點(diǎn)字ABCDEFGHIJKL權(quán)值82349326711453.對于23題有序表及其相應(yīng)的權(quán)值，試挨次優(yōu)查找樹的結(jié)構(gòu)算法并加適合調(diào)整，畫出由這12個(gè)關(guān)鍵字結(jié)構(gòu)所得的次優(yōu)查找樹，并計(jì)算它的PH值。經(jīng)過適合調(diào)整后獲得的次優(yōu)查找樹能否更優(yōu)設(shè)哈希表HT[15]，哈希函數(shù)為H(key)key%13。用開放地點(diǎn)法解決矛盾，對以下重點(diǎn)碼序列12,23,45,57,20,03,78,31,15,36造表。采納線性探測法找尋下一個(gè)空位，畫出相應(yīng)的哈希表，并計(jì)算等概率下查找成功的均勻查找長度和查找不行功的均勻查找長度。設(shè)哈希表HT[15]，哈希函數(shù)為H(key)key%13。用開放地點(diǎn)法解決矛盾，對以下重點(diǎn)碼序列12,23,45,57,20,03,78,31,15,36造表。采納再哈希法找尋下一個(gè)空位，再哈希函數(shù)為RH(key)(7key)%101，找尋下一個(gè)空地點(diǎn)的公式為Hi(Hi1RH(key))%15，H0H(key)。畫出相應(yīng)的哈希表，并計(jì)算等概率下查找成功的均勻查找長度。18第十章作業(yè)一、選擇題排序算法的穩(wěn)固性是指()。經(jīng)過排序后，能使值同樣的數(shù)據(jù)保持原次序中的相對地點(diǎn)不變經(jīng)過排序后，能使值同樣的數(shù)據(jù)保持原次序中的絕對地點(diǎn)不變經(jīng)過排序后，數(shù)據(jù)序列的寄存數(shù)組的結(jié)構(gòu)保持不變經(jīng)過排序后，數(shù)據(jù)序列的寄存數(shù)組的結(jié)構(gòu)隨之變化57.若要求在最壞狀況下也能趕快地對序列進(jìn)行穩(wěn)固的排序，則應(yīng)選()。A.起泡排序B.迅速排序C.合并排序D.堆排序每次從未排序的序列中拿出一個(gè)元素與已排序的序列中的元素挨次進(jìn)行比較，而后把它插入到已排序序列中的適合地點(diǎn)，此種排序方法叫做()A.起泡排序B.直接插入排序C.簡單項(xiàng)選擇擇排序D.二路合并排序59.對5個(gè)不一樣數(shù)據(jù)元素做直接插入排序，其數(shù)據(jù)比較次數(shù)最多是()。直接插入排序在最好狀況下的時(shí)間復(fù)雜度是()A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)6