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

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

2、54321可能的輸出序列是（）A432156B362154C123546D5413265設(shè)輸入序列為A，B，C，D。借助一個(gè)?？梢缘玫降妮敵鲂蛄惺牵ǎ〢A，C，D，BBC，A，D，BCD，C，A，BDD，A，B，C6將含100個(gè)結(jié)點(diǎn)的完全二叉樹從根開始，每層從左到右依次對結(jié)點(diǎn)編號，根結(jié)點(diǎn)的編號為1，則編號為71的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為（）A34B35C36D無法確定7已知完全二叉樹有80個(gè)結(jié)點(diǎn)，則該二叉樹有（）個(gè)度為1的結(jié)點(diǎn)。A0B1C

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

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

5、下面不正確的說法是（）AG’為G的子圖BG’為G的連通分量CG’為G的極小連通子圖且V’=VDG’是G的一個(gè)無環(huán)子圖15在采用線性探測法處理沖突所構(gòu)成的閉散列表上進(jìn)行查找，可能要探測多個(gè)位置，在查找成功的情況下，所探測的這些位置上的鍵值（）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棧和隊(duì)列都是（）A順序存儲(chǔ)的線性表B鏈?zhǔn)酱鎯?chǔ)的線性表C限制的線性表D限制存儲(chǔ)點(diǎn)的非線性結(jié)構(gòu)18向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（）A先移動(dòng)棧頂指針，再存入元素B先存入元素，再移動(dòng)棧頂指針C先后次序無關(guān)緊要D同時(shí)進(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個(gè)元素往后查找該數(shù)據(jù)元素B從第1個(gè)元素往后查找該數(shù)據(jù)元素C從第n個(gè)元素開始往前查找該數(shù)據(jù)元素D與查找順序無關(guān)43常采用下面幾種方式解決散列法中出現(xiàn)的沖突問題（）A數(shù)字分析法、除余法、平方取中法B數(shù)字分析法、除余法、線性探測法C數(shù)字分析法、線性探測法、多重散列法D線性探測法、多重散列法、鏈地址法44若待排序列已基本有序，要使它們完全有序，從關(guān)鍵碼比較次數(shù)和移動(dòng)次數(shù)考慮，應(yīng)當(dāng)使用的排

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

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

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

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

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