2023年數(shù)據(jù)結(jié)構(gòu)考試題

規(guī)定：所有的題目的解答均寫在答題紙上（每張答題紙上要寫清楚姓名、班號(hào)和學(xué)號(hào)），需寫清楚題目的序號(hào)。每張答題紙都要寫上姓名和序號(hào)。一、單項(xiàng)選擇題（每小題2分，共20分）1.在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，并且還要存儲(chǔ)。A.數(shù)據(jù)的解決方法 B.數(shù)據(jù)元素的類型C.數(shù)據(jù)元素之間的關(guān)系 D.數(shù)據(jù)的存儲(chǔ)方法2.下述函數(shù)中相應(yīng)的漸進(jìn)時(shí)間復(fù)雜度（n為問題規(guī)模）最小是。A.T1(n)=nlog2n+5000n B.T2(n)=n2-8000nC.T3(n)=n-6000n D.T4(n)=7000log2n3.設(shè)線性表有n個(gè)元素，以下操作中，在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高。A.輸出第i（1≤i≤n）個(gè)元素值B.互換第1個(gè)元素與第2個(gè)元素的值C.順序輸出這n個(gè)元素的值D.輸出與給定值x相等的元素在線性表中的序號(hào)4.設(shè)n個(gè)元素進(jìn)棧序列是p1，p2，p3，…，pn，其輸出序列是1，2，3，…，n，若p3=3，則p1的值。A.也許是2 B.一定是2C.不也許是1 D.一定是15.以下各種存儲(chǔ)結(jié)構(gòu)中，最適合用作鏈隊(duì)的鏈表是。A.帶隊(duì)首指針和隊(duì)尾指針的循環(huán)單鏈表 B.帶隊(duì)首指針和隊(duì)尾指針的非循環(huán)單鏈表C.只帶隊(duì)首指針的非循環(huán)單鏈表 D.只帶隊(duì)首指針的循環(huán)單鏈表6.對于鏈串s（長度為n，每個(gè)結(jié)點(diǎn)存儲(chǔ)一個(gè)字符），查找元素值為ch的算法的時(shí)間復(fù)雜度為。A.O(1) B.O(n)C.O(n2) D.以上都不對7.設(shè)二維數(shù)組A[6][10]，每個(gè)數(shù)組元素占用4個(gè)存儲(chǔ)單元，若按行優(yōu)先順序存放的數(shù)組元素a[3][5]的存儲(chǔ)地址為1000，則a[0][0]的存儲(chǔ)地址是。A.872 B.860C.868 D.8648.一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為。A.11 B.10C.11～1025 D.12～10249.一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則先序遍歷序列為。A.ACBED B.DECABC.DEABC D.CEDBA10.對圖1所示的無向圖，從頂點(diǎn)1開始進(jìn)行深度優(yōu)先遍歷；可得到頂點(diǎn)訪問序列。A.1243576 B.1243567C.1245637 D.1234576圖1一個(gè)無向圖二、填空題（每題2分，共10分）1.順序隊(duì)和鏈隊(duì)的區(qū)別僅在于的不同。2.在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)。3.對有18個(gè)元素的有序表R[1..18]進(jìn)行二分查找，則查找R[3]的比較序列的下標(biāo)為。4.對具有n元素的關(guān)鍵字序列進(jìn)行直接選擇排序時(shí)，所需進(jìn)行的關(guān)鍵字之間的比較次數(shù)為。5.已知關(guān)鍵字序列為{2,7,4,3,1,9,10,5,6,8}，采用堆排序法對該序列作升序排序時(shí)，構(gòu)造的初始堆（大根堆）是。（不用畫出堆，只需寫出初始堆的序列）三、問答題（共40分）1.一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉結(jié)點(diǎn)的個(gè)數(shù)是多少？（需寫出推導(dǎo)過程，8分）2.給出如下各種情況下求任意一個(gè)頂點(diǎn)的度的過程（只需文字描述）：（8分）（1）含n個(gè)頂點(diǎn)的無向圖采用鄰接矩陣存儲(chǔ)；（2）含n個(gè)頂點(diǎn)的無向圖采用鄰接表存儲(chǔ)；（3）含n個(gè)頂點(diǎn)的有向圖采用鄰接矩陣存儲(chǔ)；（4）含n個(gè)頂點(diǎn)的有向圖采用鄰接表存儲(chǔ)。3.將整數(shù)序列{4,5,7,2,1,3,6}中的數(shù)依次插入到一棵空的平衡二叉樹中，試構(gòu)造相應(yīng)的平衡二叉樹。（規(guī)定畫出每個(gè)元素插入過程，若需調(diào)整，還需給出調(diào)整后的結(jié)果，并指出是什么類型的調(diào)整，12分）4.當(dāng)實(shí)現(xiàn)插入直接排序過程中，假設(shè)R[0..i-1]為有序區(qū)，R[i..n-1]為無序區(qū)，現(xiàn)要將R[i]插入到有序區(qū)中，可以用二分查找來擬定R[i]在有序區(qū)中的也許插入位置，這樣做能否改善直接插入排序算法的時(shí)間復(fù)雜度?為什么?（8分）5.簡述外排序的兩個(gè)階段。（4分）四、算法設(shè)計(jì)題（每小題10分，共30分）1.設(shè)計(jì)一個(gè)算法delminnode(LinkList*&L)，在帶頭結(jié)點(diǎn)的單鏈表L中刪除所有結(jié)點(diǎn)值最小的結(jié)點(diǎn)（也許有多個(gè)結(jié)點(diǎn)值最小的結(jié)點(diǎn)）。2.假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，設(shè)計(jì)一個(gè)算法copy(BTNode*b,BTNode*&t)，由二叉樹b復(fù)制成另一棵二叉樹t。3.假設(shè)一個(gè)無向圖是非連通的，采用鄰接表作為存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)算法，輸出圖中各連通分量的節(jié)點(diǎn)序列。參考答案一、單項(xiàng)選擇題（每小題2分，共20分）1.C 2.D 3.A 4.A 5.B6.B 7.B 8.C 9.D 10.A二、填空題（每題2分，共10分）1.存儲(chǔ)方法或存儲(chǔ)結(jié)構(gòu)。2.2(n-1)。3.9、4、2、34.n(n-1)/2。5.10,8,9,6,7,2,4,5,3,1。（序列不全對不給分）三、問答題（共40分）1.答：二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)只能是1或0。設(shè)n1=1，n=n0+n1+n2=n0+n2+1=1001，由性質(zhì)1可知n0=n2+1，由兩式可求n0=500.5，不成立；設(shè)n1=0，n=n0+n1+n2=n0+n2=1001，由性質(zhì)1可知n0=n2+1，由兩式可求n0=501。本題答案為：501。評分標(biāo)準(zhǔn)：只給出結(jié)果給3分，推導(dǎo)過程占5分。2.答：對于鄰接矩陣表達(dá)的無向圖，頂點(diǎn)i的度等于第i行中元素等于1的個(gè)；對于鄰接矩陣表達(dá)的有向圖，頂點(diǎn)i的出度等于第i行中元素等于1的個(gè)數(shù)；入度等于第i列中元素等于1的個(gè)數(shù)；度數(shù)等于它們之和。對于鄰接矩陣表達(dá)的無向圖，頂點(diǎn)i的出度等于g->adjlist[i]為頭結(jié)點(diǎn)的單鏈表中結(jié)點(diǎn)的個(gè)數(shù)；入度需要遍歷各頂點(diǎn)的邊表，若g->adjlist[k]為頭結(jié)點(diǎn)的單鏈表中存在頂點(diǎn)編號(hào)為i的結(jié)點(diǎn)，則頂點(diǎn)i的入度增1；度數(shù)等于它們之和。評分標(biāo)準(zhǔn)：有向圖、無向圖兩種存儲(chǔ)方式各占4分。3.建立平衡二叉樹過程如圖2所示(圖中加陰影的結(jié)點(diǎn)表達(dá)要調(diào)整的結(jié)點(diǎn))。圖2構(gòu)造平衡二叉樹過程評分標(biāo)準(zhǔn)：每次調(diào)整占1分。4.答：不能。由于在這里，二分查找只減少了關(guān)鍵字間的比較次數(shù)，而記錄的移動(dòng)次數(shù)不變，時(shí)間的復(fù)雜度仍為O(n2)。評分標(biāo)準(zhǔn)：答對“不能”占3分，說明理由占5分。5.答：生成初始?xì)w并段（或順串），采用多路平衡歸并方法進(jìn)行歸并。四、算法設(shè)計(jì)題（共30分）1.解：用p從頭至尾掃描單鏈表，pre指向*p結(jié)點(diǎn)的前驅(qū)，用minp保存值最小的結(jié)點(diǎn)指針，minpre指向*minp結(jié)點(diǎn)的前驅(qū)。一面掃描，一面比較，將最小值的結(jié)點(diǎn)放到*minp中。算法如下：voiddelminnode(LinkList*&L){ LinkList*pre=L,*p=pre->next,*minp=p,*minpre=pre; ElemTypemindata=p->data; while(p!=NULL&&p->data<mindata) { mindata=p->data; p=p->next; } p=pre->next; while(p!=NULL) { if(p->data==mindata) { pre->next=p->next; free(p); } pre=pre->next; p=pre->next; }}評分標(biāo)準(zhǔn)：根據(jù)算法的對的性評分，不考慮算法的時(shí)間復(fù)雜度。2．解：遞歸算法如下：voidcopy(BTNode*b,BTNode*&t){ BTNode*l,*r; if(b==NULL)t=NULL; else { t=(BTNode*)malloc(sizeof(BTNode)); copy(b->lchild,l); copy(b->rchild,r); t->lchild=l; t->rchild=r; }}評分標(biāo)準(zhǔn)：根據(jù)算法的對的性評分，不考慮算法的時(shí)間復(fù)雜度。3.解：采用深度優(yōu)先搜索遍