學習通《數(shù)據(jù)結(jié)構(gòu)與算法》習題（含答案）

學習通《數(shù)據(jù)結(jié)構(gòu)與算法》習題（含答案）第1章第2章第3章第4章第5章第6章第7章問題：1.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）o答案：線性結(jié)構(gòu)和非線性結(jié)構(gòu)問題：2.在數(shù)據(jù)結(jié)構(gòu)中，從存儲結(jié)構(gòu)上可以將之分為（）。答案：順序存儲和非順序存儲問題：3.某算法的時間復雜度是0（d2）,說明該算法的（??）o答案：執(zhí)行時間與d2成正比問題：4.在下面的程序段中，x=x+l；的語句頻度為（）。for（i=l；i<=n；i++）for（j=l；j<=n；j++）x=x+l；答案：O（rT2）問題：5.以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)。答案：樹答案：元素間具有分支及層次關系的結(jié)構(gòu)問題：2.任意一棵二叉樹的葉子結(jié)點在其先序、中序、后序序列中的相對位置（）。答案：肯定不發(fā)生變化問題：3.判斷線索二叉樹中某結(jié)點P有左孩子的條件是（）。答案：p->LTag==O問題：4.設森林T中有4棵樹，其結(jié)點個數(shù)分別為nl,n2,n3,n4,那么當森林T轉(zhuǎn)換成一棵二叉樹后，那么根結(jié)點的右子樹上有（??）個結(jié)點。答案：n2+n3+n4問題：5.以數(shù)據(jù)集｛4,5,6,7,10,12,18｝為葉結(jié)點權值所構(gòu)造的哈夫曼樹，其帶權路徑長度為（）。答案：165問題：6.以下屬于前綴編碼的是（）。答案：｛0,1101,1110,1100,1111｝問題：7.一棵具有N個結(jié)點的二叉樹采用二叉鏈表進行存儲，其中空指針域有（？?）個。答案：N+1問題：8.一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點,4個度為3的結(jié)點，那么該樹中有（）個葉子結(jié)答案:12問題：9.滿二叉樹一定完全是二叉樹。答案：正確問題：10.二叉樹的遍歷結(jié)果不是唯一的。答案：正確第52章第53章第54章第55章第56章第57章第58章第59章第60章第61章第62章第63章第64章第65章第66章問題：1.一個具有n個頂點的無向圖最多有()邊。答案:n(n-l)/2??問題：2.對于一個具有n個頂點和e條邊的無向圖，假設采用鄰接表表示，那么占用的存儲空間為（？?）。答案：n+2e問題：3.如果含有n個頂點的圖形成一個環(huán)，那么它有（？?）棵生成樹。答案：n問題：4.任何一個無向連通網(wǎng)的最小生成樹（）。答案：有一棵或多棵問題：5.判斷一個有向圖是否存在回路，可以用（）。答案：深度優(yōu)先遍歷算法問題：6.關鍵路徑是事件結(jié)點網(wǎng)絡中（??）o答案：從源點到匯點的最長路徑問題：7.深度優(yōu)先遍歷類似于二叉樹的（）。答案：先序遍歷?？問題：8.廣度優(yōu)先遍歷類似于二叉樹的（）。答案：層次遍歷問題：9.迪杰斯特拉算法求最短路徑時，是按照路徑長度遞增的順序求解的。答案：正確問題：10.任何一個有向圖都一定存在拓撲序列。答案：錯誤第67章第68章第69章第70章第71章第72章第73章第74章第75章問題：1.具有12個關鍵字的有序表，折半查找的平均查找長度（）。答案：’37/12問題：2.如果要求用線性表既能較快地查找，又能適應動態(tài)變化的要求，那么可采用（？?）查找方法。答案：分塊查找問題：3.一如下10個記錄的表，其關鍵字序列為（2,15,19,25,30,34,44,55,58,80）,用折半查找法查找關鍵字為55的記錄，比擬次數(shù)是（）。答案：2次問題：4.如果按關鍵碼值遞增的順序依次將99個關鍵碼值插入到二叉排序樹中，那么對這樣的二叉排序樹檢索時,在等概率情況下查找成功時的平均查找長度ASL為（）。999999答案:50問題：5.對包含n個元素的散列表進行查找，平均查找長度為（）。答案：不直接依賴于n問題：6.衡量查找算法效率的主要標準是（）。答案：平均查找長度問題：7.Hash表的平均查找長度與處理沖突的方法無關。答案：錯誤問題：8.在二叉樹排序樹中插入一個新結(jié)點，總是插入到葉結(jié)點下面。答案：正確問題：9.哈希表是一種將關鍵字轉(zhuǎn)換為存儲地址的存儲方法。答案：正確問題：10.在二叉排序樹上刪除一個結(jié)點時，不必移動其它結(jié)點，只要將該結(jié)點的父結(jié)點的相應的指針域置空即可。答案：錯誤第76章第77章第78章第79章第80章第81章第82章第83章第84章第85章第86章問題：1.有一組數(shù)據(jù)(15,9,7,8,20,-1,7,4),用堆排序的篩選方法建立的初始小根堆為()。答案：-1,4,7,8,20,15,7,9問題：2.一組記錄的關鍵字為(46,79,56,38,40,84),那么利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為()。答案:(40,38,46,56,79,84)問題：3.對以下整數(shù)序列使用基數(shù)排序，一趟分配收集之后的結(jié)果是()O(179,208,93,306,55,859,984,9,271,33)答案：｛271,93,33,984,55,306,208,179,859,9｝問題:4.對序列｛15,9,7,8,20,-1,4｝進行排序，進行一趟后數(shù)據(jù)的排列變?yōu)?9,15,7,8,20,-1,4),那么采用的排序方法是()。答案：直接插入排序問題：5.評價排序算法好壞的標準主要是()。答案：執(zhí)行時間和所需的輔助空間問題：6.對n個不同的排序碼進行冒泡（遞增）排序，在以下（????）情況比擬的次數(shù)最多。。答案：從大到小排列好的問題：7.簡單項選擇擇排序和堆排序性能都受初始序列順序的影響。答案：錯誤問題：8.快速排序算法在每一趟排序中都能找到一個元素放在其最終位置上。答案：正確問題：9.堆排序所需的時間與待排序的記錄個數(shù)無關。答案：錯誤問題：10.采用希爾方法排序時，假設關鍵字的排列雜亂無序，那么效率最高。答案：正確第87章第88章第89章第90章第91章第92章第93章第94章第95章第96章第97章第98章第99章第100章第101章問題：文件壓縮產(chǎn)品最主要的功能是（）。答案：壓縮#解壓問題：哈夫曼樹最典型、最廣泛的應用是在編碼技術上。利用哈夫曼樹，構(gòu)造所得的哈弗曼編碼是一種最優(yōu)前綴編碼。答案：正確問題：在設計產(chǎn)品時，只需要辦好程序員的角色就可以To答案：錯誤第102章問題：6.順序存儲，存儲單元的地址（）。答案：一定連續(xù)問題：7.評價一個算法性能好壞的重要標準是（）。答案：算法的時間和空間復雜度問題：8.假設需要利用形式參數(shù)直接訪問修改實參值，那么應將形參說明為（）參數(shù)。答案：指針問題：9.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。答案：錯誤問題：10.數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標是算法的時間復雜度和空間復雜度。答案：正確第8章第9章第10章第11章第12章第13章第14章問題：1.下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點（）。答案：存儲密度大問題：2.假設某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，那么利用（）存儲方式最節(jié)省時間。答案：順序表?？問題：3.設某順序表中第一個元素的地址是se（下標從1開始），每個結(jié)點占m個單元，那么第i個結(jié)點的地址為（）。答案：se+（i-l）Xm問題：4.某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，那么采用。存儲方式最節(jié)省運算時間。答案：僅有尾指針的單循環(huán)鏈表問題：5.假設長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復雜度為（）。答案:0（n）??問題：6.在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是（）。答案：s->next=p->next；p->next=s；問題：7.對于一個頭指針為head的帶頭結(jié)點的單鏈表，判定該表為空表的條件是0。????????答案：head->next==NULL；問題：8.靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。答案：正確問題：9.順序表適宜于順序存取，而鏈表適宜于隨機存取。答案：錯誤問題：10.線性表的鏈式存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定相鄰。答案：正確第15章第16章第17章第18章第19章第20章第21章第22章第23章問題：1.棧和隊列都是（）。答案：限制存取點的線性結(jié)構(gòu)？？問題：2.設棧S和隊列Q的初始狀態(tài)為空，元素el,e2,e3,e4,e5和e6依次通過棧S,一個元素出棧后隨即進入隊列Q,假設6個元素出隊的序列是e2,e4,e3,e6,e5,el,那么棧S的容量至少應該是（）。答案：3問題：3.設計一個判別表達式中括號是否匹配出現(xiàn)的算法，采用（）的數(shù)據(jù)結(jié)構(gòu)最正確。答案：棧？？問題：4.表達式a*（b+c）-d的后綴表達式是（）。答案：abc+*d-??問題：5.遞歸過程或函數(shù)調(diào)用時,處理參數(shù)及返回地址需要用一種（）的數(shù)據(jù)結(jié)構(gòu)。答案.棧？—9問題：6.最大容量為n的循環(huán)隊列，隊尾指針為rear,隊頭指針為front,那么隊空的條件是（）。答案：rear==front????????問題：7.用帶頭結(jié)點的單鏈表表示隊長大于1的隊列時，其隊頭指針指向隊頭結(jié)點，其隊尾指針指向隊尾結(jié)點，那么在進行刪除操作時（）。答案：僅修改隊頭指針問題：8.對于一個具有n個結(jié)點的單鏈表，在的結(jié)點*p后插入一個新結(jié)點的時間復雜度和在給定值為x的結(jié)點后插入一個新結(jié)點的時間復雜度分別為（）。答案：0（1）,0（n）??問題：9.兩順序棧共享空間，也存在空間溢出問題。答案：正確問題：10.在對不帶頭結(jié)點的鏈隊列作出隊操作時，不會改變頭指針的值。答案：錯誤第24章第25章第26章第27章第28章第29章第30章問題：1.串是一種特殊的線性表，其特殊性表達在（）。答案：數(shù)據(jù)元素是字符問題：2.假設串S二'software',其前綴真子串的數(shù)目是（）。答案：7問題：3.設有兩個串p和q，其中q是p的子串，求q在P中首次出現(xiàn)的位置的算法稱為（）。答案：串的模式匹配?？問題：4.串S='aaab',其next函數(shù)值為（）。答案:0123問題：5.函數(shù)strcmp（1stcabuc1,1stbabuc'）的返回值是（）。答案：1問題：6.KMP算法的特點是在模式匹配時指示主串的指針不會回溯。答案：正確問題：7.模式串？?P='abaabcac'的next函數(shù)值序列為01122312。答案：正確問題：8.串的存儲結(jié)構(gòu)有順序串、堆串和塊鏈串三種。答案：正確問題：9.子串的定位運算稱為串的模式匹配。答案：正確問題：10.串'student'和'Student'相等。答案：錯誤第31章第32章第33章第34章第35章問題：1.假設以行序為主序存儲二維數(shù)組A二array[1...100,1...100],設每個數(shù)組元素占2個存儲單元，基地址為10,那么L0C[5,5>()o答案：818問題：2.假設對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組B［l...(n(n+l))/2］中，那么在B中確定aij(i〈j)的位置k的計算公式為()。答案：i(i-l)/2+j問題：3.設廣義表L二((a,b,c)),那么L的長度和深度分別為()。答案：1和2問題：4.在稀疏矩陣的三元組順序表中，每個三元組表示()。答案：矩陣中非零元素的行號、列號和數(shù)據(jù)值問題：5.多維數(shù)組可以看作是一種特殊的線性表。答案：正確問題：6.一個稀疏矩陣AM,n］采用三元組順序表形式表示，假設把三元組中有關行下標與列下標的值互換，并把m和n的值互換，那么就完成了A［m,n］的轉(zhuǎn)置運算。??答案：錯誤問題：7.廣義表