2024年甘肅開(kāi)放大學(xué)《數(shù)據(jù)結(jié)構(gòu)》形成性考核參考試題庫(kù)（含答案）

2024年甘肅開(kāi)放大學(xué)《數(shù)據(jù)結(jié)構(gòu)》形成性考核參考試題庫(kù)(含答案)A、都是0B、地址域D、空閑域D、線性表charsex;}person[5];需要給結(jié)構(gòu)體數(shù)組中第2個(gè)變量的no成員賦值為5,正確D、person[1].no=5.19.已知一棵度為3的樹(shù)有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)。則該樹(shù)中有()個(gè)葉子結(jié)點(diǎn)。C、12棧頂，棧1的底在V[0],棧2的底在V[m-1],則棧滿的條件是()。21.用順序存儲(chǔ)的方法將完全二叉樹(shù)中所有結(jié)點(diǎn)逐層存放在數(shù)組R[],根結(jié)點(diǎn)存A、R[2*i+l]23.循環(huán)單鏈表的主要優(yōu)點(diǎn)是()。D、從表中的任意結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表24.一棵樹(shù)的廣義表表示為a(b(c),de(g(h)),f,k)),則該樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)為25.設(shè)有13個(gè)值，用它們組成一棵赫夫曼樹(shù)，則該赫夫曼樹(shù)共有()個(gè)結(jié)點(diǎn)。D、任意多個(gè)B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)32.n個(gè)頂點(diǎn)的生成樹(shù)有()條邊。37.一棵樹(shù)的廣義表表示為a(b(c),d(e(g(h)),f,k)),則該樹(shù)的度為()。B、138.對(duì)下面的有向圖進(jìn)行深度優(yōu)先遍歷得到的遍歷序列是()。A、bcfdeg39.已知單鏈表的每個(gè)結(jié)點(diǎn)包括一個(gè)指針域next,它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)?，F(xiàn)要將指針指向的新結(jié)點(diǎn)插入到指針p指向的結(jié)點(diǎn)之后，下面的操作序列中正確的A、q=p->next;p->next=q->nA、p->next=p->next->n48.n個(gè)頂點(diǎn)的無(wú)向圖的接表最多有()個(gè)結(jié)點(diǎn)。49.一棵深度為6的滿二又樹(shù)一共有個(gè)()結(jié)點(diǎn)。B、2和452.一個(gè)容量為15的循環(huán)隊(duì)列中，隊(duì)尾指針是rear,隊(duì)頭是front,初始時(shí)均為0,54.若已知一個(gè)棧的進(jìn)棧序列是1,2,3,...,n,其輸出序列為p1,p2,p3,,pn,若p1A、一定是2D、一定是1②邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1③至少有一個(gè)頂點(diǎn)度為162.一棵深度為h的滿k又樹(shù)有如下性質(zhì)：第h層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上的每個(gè)結(jié)點(diǎn)都有k棵非空子樹(shù)。如果按層次順序(同層自左至右)從1開(kāi)始對(duì)A、i63.該二叉樹(shù)對(duì)應(yīng)的森林有()棵樹(shù)。64.一個(gè)遞歸算法必須包括()。A、遞歸部分68.一棵完全二又樹(shù)按層次遍歷的序列為ABCDEFGHI則在前序遍歷中結(jié)點(diǎn)E的直接前驅(qū)為結(jié)點(diǎn)()。69.一棵樹(shù)的廣義表表示為a(b(c),d(e(g(h)),f,k)),則該樹(shù)中e結(jié)點(diǎn)的孩子結(jié)點(diǎn)個(gè)數(shù)為()。70.最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear,隊(duì)頭指針是front,初始時(shí)均為0,B、根結(jié)點(diǎn)但不是分支結(jié)點(diǎn)D、分支結(jié)點(diǎn)但不是根結(jié)點(diǎn)72.已知輸入序列為abcd,經(jīng)過(guò)隊(duì)列后能得到的輸出序列有()。73.已知單鏈表的每個(gè)結(jié)點(diǎn)包括一個(gè)指針域next,它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。帶頭結(jié)點(diǎn)的單鏈表L為空的條件是()C、線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)D、順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)78.對(duì)圖從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先遍歷，則()是不可能得到的遍歷序列。79.對(duì)于任何一棵二又樹(shù)，如果其終端結(jié)點(diǎn)數(shù)為no,度為2的結(jié)點(diǎn)數(shù)為n2,則no=80.用鄰接表存儲(chǔ)圖所用的空間大小()。A、與圖的頂點(diǎn)數(shù)和邊數(shù)都有關(guān)B、只與圖的邊數(shù)有關(guān)85.表示一個(gè)有100個(gè)頂點(diǎn)，1000條邊的非帶權(quán)有向圖的鄰接矩陣有()個(gè)大于零矩陣元素86.已知一個(gè)有向圖的邊集為{<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>},則由該圖產(chǎn)生的一種可能的拓?fù)湫蛄袨?)。87.已知鏈表的每個(gè)結(jié)點(diǎn)包括一個(gè)指針域next,它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。非空的循環(huán)單鏈表head的尾結(jié)針p滿足()。A、都是n94.表示一個(gè)有100個(gè)頂點(diǎn)，1000條邊的無(wú)向圖的鄰接矩陣有()個(gè)非零矩陣元素。95.已知單鏈表的每個(gè)結(jié)點(diǎn)包括一個(gè)指針域next,它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。假定己建立以下動(dòng)態(tài)鏈表結(jié)構(gòu)，且指針pl和p2已指向如圖所示的結(jié)點(diǎn)：則以下可以將p2所指結(jié)點(diǎn)從鏈表中刪除并釋放該結(jié)點(diǎn)的語(yǔ)句組是()。PePeA、pl->next=p2->next;free96.一顆非空二叉樹(shù)其前序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定A、所有結(jié)點(diǎn)均無(wú)左孩了結(jié)點(diǎn)B、所有結(jié)點(diǎn)均無(wú)右孩子結(jié)點(diǎn)C、只有一個(gè)葉結(jié)點(diǎn)D、是任意一棵二又樹(shù)97.一棵完全二又樹(shù)按層次遍歷的序列為ABCDEFGHI,后序遍歷中結(jié)點(diǎn)B的直接后繼是結(jié)點(diǎn)()。98.分析以下程序段，其時(shí)間復(fù)雜度為T(mén)()=()99.在一棵具有35個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，該樹(shù)的深度為()。100.無(wú)向圖G=(V.E),其中：VA、,b,e,c,d,f101.設(shè)一棵二叉樹(shù)中有3個(gè)葉子結(jié)點(diǎn)，有8個(gè)度為1的結(jié)點(diǎn)，則該二叉樹(shù)中總的結(jié)點(diǎn)數(shù)是()7A、s->next=a->next->next;a->next->neD、a=a->next:s->next104.一棵樹(shù)的廣義表表示為a(b(c),d(e(g(h)),f,k)),則該樹(shù)的高度為()105.由3個(gè)結(jié)點(diǎn)所構(gòu)成的二又樹(shù)有()種形態(tài)。106.已知鏈表的每個(gè)結(jié)點(diǎn)包括一個(gè)指針域next它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。在頭指針為head且表長(zhǎng)大于1的單循環(huán)鏈表中，指針p指向表中某個(gè)結(jié)點(diǎn)，若p->next->next=head,則()。A、p指向頭結(jié)點(diǎn)B、p指向尾結(jié)點(diǎn)C、米p的直接后繼是頭結(jié)點(diǎn)D、米p的直接后繼是尾結(jié)點(diǎn)107.棧和隊(duì)列的共同點(diǎn)是()。A、都是先進(jìn)先出B、都是先進(jìn)后出C、只允許在端點(diǎn)處插入和刪除元素D、沒(méi)有共同點(diǎn)108.由權(quán)值分別是8,7,2,5的葉子結(jié)點(diǎn)生成一棵赫夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為109.在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的()倍。A、1/2111.一個(gè)圖中包含k個(gè)連通分量，若按深度優(yōu)先遍歷方法訪問(wèn)多有頂點(diǎn)，則必須調(diào)用()次深度優(yōu)先遍歷算法。A、帶尾指針的非循環(huán)鏈表B、帶尾指針的循環(huán)鏈表C、帶頭指針的非循環(huán)鏈表D、帶頭指針的循環(huán)鏈表A、一個(gè)圖的鄰接矩陣表示是唯一的，鄰接表表示也唯一B、一個(gè)圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一C、一個(gè)圖的鄰接矩陣表示不唯一的，鄰接表D、一個(gè)圖的鄰接矩陣表示不唯一的，鄰接表表示也不唯一119.在一棵二叉樹(shù)的二叉鏈表中，空指針域等于所有非空指針域相加()。120.設(shè)深度為k的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則這棵樹(shù)所含的結(jié)點(diǎn)數(shù)122.設(shè)有一個(gè)順序棧S,元素1,2,3,4,5,6依次進(jìn)棧，如果6個(gè)元素的出棧順序?yàn)?,3,4,6,5,1,1則順序站的容量至少可以存儲(chǔ)()個(gè)元素。124.后綴表達(dá)式“45*32+-”的值為()。B、可以改變133.計(jì)算機(jī)算法指的是解決問(wèn)題的有限運(yùn)算序列，它必具備輸入、輸出和()等五A、可行性、可移植性和可擴(kuò)充性B、可行性、確定性和有窮性134.隊(duì)列的“先進(jìn)先出”特性是指()。A、最早插入隊(duì)列中的元素總是最后被刪除B、當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先D、每次從隊(duì)列中刪除的總是最早插入的元素135.一個(gè)向量第一個(gè)元素的地址是100,每個(gè)元素的長(zhǎng)度為2,則第5個(gè)元素的地136.5、森林F中有三棵樹(shù)，每棵樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)分別為n1,n2和n3,森林F轉(zhuǎn)換二叉樹(shù)后，根結(jié)點(diǎn)的右子樹(shù)上結(jié)點(diǎn)個(gè)數(shù)為()。A、存在這樣的二叉樹(shù)，對(duì)它采用任何次序遍歷其結(jié)點(diǎn)訪問(wèn)序列均相同B、普通二叉樹(shù)只能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)D、二叉樹(shù)只有一棵子樹(shù)的情況下也要明確指出該子樹(shù)是左子樹(shù)還是右子樹(shù)138.數(shù)組Q[n]用來(lái)表示一個(gè)循環(huán)隊(duì)列，為當(dāng)前隊(duì)列頭元素的前一位置，r為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于n,計(jì)算隊(duì)列中元素的公式為()。判斷題2.任何一個(gè)遞歸過(guò)程都可以轉(zhuǎn)換成非遞歸過(guò)程3.任何無(wú)向圖都存在生成樹(shù)。4.二叉樹(shù)的前序和后序遍歷序列能惟一確定這棵二叉樹(shù)。5.三叉鏈表存儲(chǔ)二叉樹(shù)，指針域除了指向左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)，還要指向兄6.隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型鄰B、錯(cuò)誤B、錯(cuò)誤22.二叉樹(shù)的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子樹(shù)結(jié)點(diǎn)的前面。23.任何A0V網(wǎng)拓?fù)渑判虻慕Y(jié)果都是唯一的。A、正確24.順序表的插入和刪除一個(gè)數(shù)據(jù)元素，每次操作平均只有近一半的元素需要移25.在帶頭節(jié)點(diǎn)的單循環(huán)鏈表中，任意節(jié)點(diǎn)中的指針域都不為空26.用棧這種數(shù)據(jù)結(jié)構(gòu)可以實(shí)現(xiàn)隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，反之亦然。32.由