國(guó)開大學(xué)2021年01月1252《數(shù)據(jù)結(jié)構(gòu)（本）》期末考試參考答案

數(shù)據(jù)結(jié)構(gòu)(本)試題2021年1月題號(hào)二三分?jǐn)?shù)45分)D.線性結(jié)構(gòu)和非線性結(jié)構(gòu)2.下面程序段的時(shí)間復(fù)雜度是(c[i][j]=c[i][j]+a[i][k3.在一個(gè)單鏈表中p指向結(jié)點(diǎn)a,q指向結(jié)點(diǎn)a的直接后繼結(jié)點(diǎn)b,要?jiǎng)h除結(jié)點(diǎn)b,可執(zhí)行(A.C.p->next=q->nextp->next=qB.D.p=q->nextp->next=q5.一個(gè)隊(duì)列的人隊(duì)序列是1,2,3,4。則隊(duì)列的輸出序列是()。B.p->next=top-nexttopnextD.p-nexttopnexttoptopnextA.求子串B.連接9.一個(gè)非空廣義表的表頭()。D.可以是子表或原子12.在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的()倍。13.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為()。14.有一個(gè)長(zhǎng)度為12的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為()。15.從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排A.插入排序C.選擇排序B.交換排序D.歸并排序17.數(shù)據(jù)結(jié)構(gòu)中，元素之間存在多對(duì)多的關(guān)系稱為圖狀結(jié)構(gòu)。()18.設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext,頭指針為head,p指向尾結(jié)點(diǎn)，為了使該單向鏈表改為單向循環(huán)鏈表，可用語(yǔ)句p->next=head。()19.設(shè)有一個(gè)單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext,頭指針為head,指針p指向表中某結(jié)點(diǎn)，若邏輯表達(dá)式p->next==head;的結(jié)果為真，則p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。()20.棧和隊(duì)列都是特殊的線性表，但它們對(duì)存取位置的限制不同。()21.棧是限定在表的兩端進(jìn)行插入和刪除操作的線性表，又稱為先進(jìn)先出表。()22.遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常用遞歸算法來(lái)實(shí)現(xiàn)對(duì)它的操作。()23.一個(gè)空格的串的長(zhǎng)度是0。()25.深度為k的完全二叉樹至少有2*-1個(gè)結(jié)點(diǎn)。()26.完全二叉樹中沒有度為1的結(jié)點(diǎn)。()if(q->front==q->rear)/*隊(duì)空*/printf(“%4d”,p->data/*出隊(duì)*//*釋放已出隊(duì)結(jié)點(diǎn)*//*隊(duì)空時(shí)，頭尾指針指向頭結(jié)點(diǎn)*/BB ; B.printf(“%c”,BT->right)C.printf(“%c”,BT->data)D.printf(“%d”,BT->data)33.一組記錄的關(guān)鍵字序列為(6,9,7,4,建立初始堆是如下哪個(gè)圖?()... (本小題3分)A.30,28,46,36,69,74B.28,30,3C.28,30,46,36,69,74D.3(2)用冒泡法對(duì)上述序列排序，經(jīng)過(guò)兩趟冒泡的結(jié)果序列為()。(本小題2分)35.設(shè)數(shù)據(jù)序列為：{53,30,37,12,45,24,96}(1)從空二叉樹開始逐個(gè)插入該數(shù)據(jù)序列來(lái)形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序列是()。(本小題3分)A.45,24,53,12,37,96,30B.37,24,12,30,(2)用鏈接地址法將該數(shù)據(jù)序列構(gòu)造哈希表，哈希函數(shù)為H(key)=keymod13,則散列地址為1的鏈中有()個(gè)記錄。(本小題2分)國(guó)家開放大學(xué)2020年秋季學(xué)期期末統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)(本)試題答案及評(píng)分標(biāo)準(zhǔn)(供參考)2021年1月