數(shù)據(jù)結(jié)構(gòu)試題及答案修2(編輯修改稿)
2025-07-20 22:44 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 NULL){ cerr空表endl。exit(1)。}LNode* p=HL。HL=HLnext。ElemType temp=pdata。delete p。return temp。 } 試卷十三一、選擇題(30分)1．下列程序段的時(shí)間復(fù)雜度為（ ）。for(i=0； im； i++) for(j=0； jt； j++) c[i][j]=0；for(i=0； im； i++) for(j=0； jt； j++) for(k=0； kn； k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]； (A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n)2．設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要移動(dòng)（ ）個(gè)元素。 (A) ni (B) n+l i (C) n1i (D) i3．設(shè)F是由TT2和T3三棵樹(shù)組成的森林，與F對(duì)應(yīng)的二叉樹(shù)為B，TT2和T3的結(jié)點(diǎn)數(shù)分別為NN2和N3，則二叉樹(shù)B的根結(jié)點(diǎn)的左子樹(shù)的結(jié)點(diǎn)數(shù)為（ ）。 (A) N11 (B) N21 (C) N2+N3 (D) N1+N34．利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為（ ）。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)5．設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為（ ）。 (A) pright=s； sleft=p； prightleft=s； sright=pright； (B) sleft=p；sright=pright；pright=s； prightleft=s； (C) pright=s； prightleft=s； sleft=p； sright=pright； (D) sleft=p；sright=pright；prightleft=s； pright=s；7．設(shè)輸入序列…、n經(jīng)過(guò)棧作用后，輸出序列中的第一個(gè)元素是n，則輸出序列中的第i個(gè)輸出元素是（ ）。 (A) ni (B) n1i (C) n+l i (D) 不能確定8．設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)= key % p，則p最好選擇（ ）。 (A) 小于等于m的最大奇數(shù) (B) 小于等于m的最大素?cái)?shù) (C) 小于等于m的最大偶數(shù) (D) 小于等于m的最大合數(shù)9．設(shè)在一棵度數(shù)為3的樹(shù)中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè)，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有（ ）個(gè)。 (A) 4 (B) 5 (C) 6 (D) 7，則該完全無(wú)向圖中有（ ）條邊。 (A) n(n1)/2 (B) n(n1) (C) n(n+1)/2 (D) (n1)/2={1，2，2，3，3，4，1，4}，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵? ）。 (A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3二、填空題(30分)1．設(shè)指針p指向單鏈表中結(jié)點(diǎn)A，指針s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的前面插入結(jié)點(diǎn)X時(shí)的操作序列為：1）snext=___________；2) pnext=s；3) t=pdata；4) pdata=___________；5) sdata=t；2．設(shè)某棵完全二叉樹(shù)中有100個(gè)結(jié)點(diǎn)，則該二叉樹(shù)中有______________個(gè)葉子結(jié)點(diǎn)。3．設(shè)某順序循環(huán)隊(duì)列中有m個(gè)元素，且規(guī)定隊(duì)頭指針F指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針R指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中最多存儲(chǔ)_______隊(duì)列元素。6． 設(shè)一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹(shù)的平均查找長(zhǎng)度是_______________________________。7． 設(shè)一棵二叉樹(shù)的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹(shù)的前序序列為_(kāi)___________________。8． 設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為13210，根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹(shù)，則這棵哈夫曼樹(shù)的高度為_(kāi)_______________。 10． 設(shè)無(wú)向圖G（如右圖所示），則其最小生成樹(shù)上所有邊的權(quán)值之和為_(kāi)________________。三、判斷題(20分)1． 有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不一定相等。( )2． 對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。( )3． 子串“ABC”在主串“AABCABCD”中的位置為2。( )4．
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1