數(shù)據(jù)結(jié)構(gòu)習(xí)題

1、《數(shù)據(jù)結(jié)構(gòu)》習(xí)題《數(shù)據(jù)結(jié)構(gòu)》習(xí)題一、單項選擇題一、單項選擇題1對矩陣進(jìn)行壓縮存儲是為了（）A節(jié)省存儲空間B提高運(yùn)算速度C便于運(yùn)算D方便存儲2鏈?zhǔn)綏Ｅc順序棧相比，一個比較明顯的優(yōu)點是（）A插入操作更加方便B通常不會出現(xiàn)棧滿的情況C不會出現(xiàn)?？盏那闆rD刪除操作更加方便3設(shè)輸入序列為1，2，3，4，5，則借助一個隊列可以得到的輸出序列是（）A3，4，1，2，5B1，2，3，4，5C2，3，4，1，5D5，4，3，2，14.一個棧的輸入序列是6

2、54321可能的輸出序列是（）A432156B362154C123546D5413265設(shè)輸入序列為A，B，C，D。借助一個棧可以得到的輸出序列是（）AA，C，D，BBC，A，D，BCD，C，A，BDD，A，B，C6將含100個結(jié)點的完全二叉樹從根開始，每層從左到右依次對結(jié)點編號，根結(jié)點的編號為1，則編號為71的結(jié)點的雙親結(jié)點的編號為（）A34B35C36D無法確定7已知完全二叉樹有80個結(jié)點，則該二叉樹有（）個度為1的結(jié)點。A0B1C

3、2D不確定8任何一個無向連通圖的最小生成樹（）A只有一棵B有一棵或多棵C一定有多棵D可能不存在9設(shè)圖G用鄰接表存儲，對該圖進(jìn)行深度優(yōu)先搜索遍歷，則算法的時間復(fù)雜度為（）AO(n)BO(ne)CO(n2)DO(n3)10用n個鍵值構(gòu)造一棵二叉排序樹，最低高度為（）An2BnC[㏒2n]D[㏒2n]111如果以鏈表作為棧的存儲結(jié)構(gòu)，則執(zhí)行出棧操作時（）A必須判斷棧是否滿B必須判斷棧是否空C判斷棧元素的類型D對棧不作任何判斷12設(shè)數(shù)組Data

4、[m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作的語句為（）Afront=front1Bfront=(front1)%mCrear=(rear1)%mDfront=(front1)%(m1)13線性表的長度是指（）A順序存儲方式下數(shù)組所占用的元素個數(shù)B鏈表存儲方式下的結(jié)點個數(shù)C表中的元素個數(shù)D所能存儲的最大的結(jié)點個數(shù)14設(shè)有一個無向圖G＝(V，E)和G’=(V’，E’)，如果G’是G的生成樹，則

5、下面不正確的說法是（）AG’為G的子圖BG’為G的連通分量CG’為G的極小連通子圖且V’=VDG’是G的一個無環(huán)子圖15在采用線性探測法處理沖突所構(gòu)成的閉散列表上進(jìn)行查找，可能要探測多個位置，在查找成功的情況下，所探測的這些位置上的鍵值（）A一定都是同義詞B一定都不是同義詞C都相同D不一定都是同義詞16在有序表A[20]中按二分查找方法查找A[13]依次比較的元素的下標(biāo)是（）A9，14，12，13B9，15，12，13C9，14，11，

6、12，13D10，15，12，1317棧和隊列都是（）A順序存儲的線性表B鏈?zhǔn)酱鎯Φ木€性表C限制的線性表D限制存儲點的非線性結(jié)構(gòu)18向順序棧中壓入新元素時，應(yīng)當(dāng)（）A先移動棧頂指針，再存入元素B先存入元素，再移動棧頂指針C先后次序無關(guān)緊要D同時進(jìn)行B[1..n(n1)2]中則對任一上三角元素aij(ij1≤i≤n1≤j≤n)在一維數(shù)組B中的下標(biāo)位置k是()Ai(i1)2jBj(j1)2iCi(j1)2iDj(i1)2i42對于靜態(tài)表順序

7、查找算法，若在表頭設(shè)置崗哨，則正確的查找方式為（）A從第0個元素往后查找該數(shù)據(jù)元素B從第1個元素往后查找該數(shù)據(jù)元素C從第n個元素開始往前查找該數(shù)據(jù)元素D與查找順序無關(guān)43常采用下面幾種方式解決散列法中出現(xiàn)的沖突問題（）A數(shù)字分析法、除余法、平方取中法B數(shù)字分析法、除余法、線性探測法C數(shù)字分析法、線性探測法、多重散列法D線性探測法、多重散列法、鏈地址法44若待排序列已基本有序，要使它們完全有序，從關(guān)鍵碼比較次數(shù)和移動次數(shù)考慮，應(yīng)當(dāng)使用的排

8、序方法是（）A歸并排序B直接插入排序C直接選擇排序D快速排序45.中序遍歷與后序遍歷結(jié)果相同的二叉樹為（）A根節(jié)點無左孩子的二叉樹B根節(jié)點無右孩子的二叉樹C所有結(jié)點只有左子樹的二叉樹D所有結(jié)點只有右子樹的二叉樹46.下列關(guān)于廣義表的敘述中錯誤的是（）A廣義表是線性表的推廣B廣義表至少有一個元素是子表C廣義表可以是自身的子表D廣義表可以是空表47.用快速排序算法對線性表排序若選擇表中第一個元素作為分界元素則表中按（）分布時排序效率最高.A

9、已經(jīng)有序B部分有序C完全有序D逆序48若用數(shù)組S[1..n]作為兩個棧S1和S2的共同存儲結(jié)構(gòu)，對任何一個棧，只有當(dāng)S全滿時才不能作入棧操作。為這兩個棧分配空間的最佳方案是（）AS1的棧底位置為0，S2的棧底位置為n1BS1的棧底位置為0，S2的棧底位置為n2CS1的棧底位置為1，S2的棧底位置為nDS1的棧底位置為1，S2的棧底位置為n249在有n個結(jié)點的二叉鏈表中，值為非空的鏈域的個數(shù)為（）An1B2n1Cn1D2n150帶權(quán)有向圖

10、G用鄰接矩陣A存儲，則頂點i的人度等于A中（）A第i行非∞的元素之和B第i列非∞的元素之和C第i行非∞且非0的元素個數(shù)D第i列非∞且非0的元素個數(shù)51在有n個結(jié)點且為完全二叉樹的二叉排序樹中查找一個鍵值，其平均比較次數(shù)的數(shù)量級為（）A0(n)B0(log2n)C0(nlog2n)D0(n2)52若線性表最常用的操作是存取第i個元素及其前趨的值，則采用（）存儲方式節(jié)省時間。A單鏈表B雙鏈表C單循環(huán)鏈表D順序表53對二叉樹從1開始進(jìn)行連續(xù)編

11、號，要求每個結(jié)點的編號大于其左右孩子的編號，同一個結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，則可采用（）遍歷實現(xiàn)編號。A先序B中序C后序D從根開始的層次遍歷54下列排序算法中，（）算法可能會出現(xiàn)下面情況：初始數(shù)據(jù)有序時，花費(fèi)的時間反而最多。A堆排序B冒泡排序C快速排序DSHELL排序55一棵左右子樹均不空的二叉樹在先序線索化后，其空指針域數(shù)為（）A0B1C2D不確定56在一個長度為n的順序存儲的線性表中，刪除第i個元素（1≤i

12、≤n）時，需要從前向后依次前移（）個元素。AniBni1Cni1Di57假定一個順序隊列的隊首和隊尾指針分別為1和r，則判斷隊空的條件為（）Af1==rBr＋1==fCf==0Df==r58哈夫曼樹的帶權(quán)路徑長度WPL等于（）A除根以外的所有結(jié)點的權(quán)植之和B所有結(jié)點權(quán)值之和C各葉子結(jié)點的帶權(quán)路徑長度之和D根結(jié)點的值59一個對象序列的排序碼為46，79，56，38，40，84，采用快速排序以位于最左位置的對象為基準(zhǔn)而得到的第一次劃分結(jié)果為