中南大學(xué)2020級計算機學(xué)院軟件工程專業(yè)數(shù)據(jù)結(jié)構(gòu)試卷(八)

中南大學(xué)2020級計算機學(xué)院軟件工程專業(yè)數(shù)據(jù)結(jié)構(gòu)試卷（八）一、選擇題(30分)1.字符串的長度是指（）。(A)串中不同樣字符的個數(shù)(B)串中不同樣字母的個數(shù)(C)串中所含字符的個數(shù)(D)串中不同樣數(shù)字的個數(shù)2.建立一個長度為n的有序單鏈表的時間復(fù)雜度為（）(A)O(n)(B)O(1)2(D)O(log2n)(C)O(n)3.兩個字符串相等的充要條件是（）。(A)兩個字符串的長度相等(B)兩個字符串中對應(yīng)地址上的字符相等(C)同時具備(A)和(B)兩個條件(D)以上答案都不對4.設(shè)某散列表的長度為100，散列函數(shù)H(k)=k%P，則P平時情況下最好選擇（）。(A)99(B)97(C)91(D)935.在二叉排序樹中插入一個要點字值的平均時間復(fù)雜度為（）。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n2)6.設(shè)一個序次有序表A[1:14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的序次為()。(A)A[1]，A[2]，A[3]，A[4](B)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4]7.設(shè)一棵完好二叉樹中有65個結(jié)點，則該完好二叉樹的深度為（）。(A)8(B)7(C)6(D)58.設(shè)一棵三叉樹中有2個度數(shù)為1的結(jié)點，2個度數(shù)為2的結(jié)點，2個度數(shù)為3的結(jié)點，則該三叉鏈權(quán)中有（）個度數(shù)為0的結(jié)點。(A)5(B)6(C)7(D)89.設(shè)無向圖G中的邊的會集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從極點a出發(fā)進行深度優(yōu)先遍歷可以獲取的一種極點序列為（）。(A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc10.隊列是一種（）的線性表。(A)先進先出(B)先進后出(C)只能插入(D)只能刪除二、判斷題(20分)1.若是兩個要點字的值不等但哈希函數(shù)值相等，則稱這兩個要點字為同義詞。（）2.設(shè)初始記錄要點字基本有序，則快速排序算法的時間復(fù)雜度為O(nlog2n)。（）分塊查找的基本思想是第一在索引表中進行查找，以便確定給定的要點字可能存在的塊號，爾后再在相應(yīng)的塊內(nèi)進行序次查找。（）4.二維數(shù)組和多維數(shù)組均不是特其他線性結(jié)構(gòu)。（）5.向二叉排序樹中插入一個結(jié)點需要比較的次數(shù)可能大于該二叉樹的高度。（）6.若是某個有向圖的毗鄰表中第i條單鏈表為空，則第i個極點的出度為零。（）7.非空的雙向循環(huán)鏈表中任何結(jié)點的前驅(qū)指針均不為空。（）8.不論線性表采用序次儲藏結(jié)構(gòu)還是鏈?zhǔn)絻Σ亟Y(jié)構(gòu)，刪除值為X的結(jié)點的時間復(fù)雜度均為O(n)。（）9.圖的深度優(yōu)先遍歷算法中需要設(shè)置一個標(biāo)志數(shù)組，以便區(qū)分圖中的每個極點可否被接見過。（）10.稀罕矩陣的壓縮儲藏可以用一個三元組表來表示稀罕矩陣中的非0元素。（）三、填空題(30分)1．設(shè)一組初始記錄要點字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為。下面程序段的功能是實現(xiàn)在二叉排序樹中插入一個新結(jié)點，請在下劃線處填上正確的內(nèi)容。typedefstructnode{intdata;structnode*lchild;structnode*rchild;}bitree;voidbstinsert(bitree*&t,intk){if(t==0){;t->data=k;t->lchild=t->rchild=0;}elseif(t->data>k)bstinsert(t->lchild,k);else;}3.設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后邊插入結(jié)點X需要執(zhí)行的語句序列：s->next=p->next;;。4.設(shè)指針變量head指向雙向鏈表中的頭結(jié)點，指針變量p指向雙向鏈表中的第一個結(jié)點，則指針變量p和指針變量head之間的關(guān)系是p=和head=（設(shè)結(jié)點中的兩個指針域分別為llink和rlink）。5.設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為。6.完好二叉樹中第5層上最稀有個結(jié)點，最多有個結(jié)點。7.設(shè)有向圖中不存在有向邊<Vi,Vj>，則其對應(yīng)的鄰接矩陣A中的數(shù)組元素A[i][j]的值等于。8．設(shè)一組初始記錄要點字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為。9.設(shè)連通圖G中有n個極點e條邊，則對應(yīng)的最小生成樹上有條邊。10.設(shè)有一組初始記錄要點字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與相互交換即可。四、算法設(shè)計題(20分)設(shè)計一個在鏈?zhǔn)絻Σ亟Y(jié)構(gòu)上統(tǒng)計二叉樹中結(jié)點個數(shù)的算法。設(shè)計一個算法將無向圖的毗鄰矩陣轉(zhuǎn)為對應(yīng)毗鄰表的算法。一、選擇題1．C2．C3．C4．B5．B6．C7．B8．C9．A10．A二、判斷題1．對2．錯3．對4．錯5．錯6．對7．對8．對9．對10．對三、填空題(49，13，27，50，76，38，65，97)2.t=(bitree*)malloc(sizeof(bitree))，bstinsert(t->rchild,k)p->next=shead->rlink，p->llinkCABD1，160(13，27，38，50，76，49，65，97)n-150四、算法設(shè)計題設(shè)計一個在鏈?zhǔn)絻Σ亟Y(jié)構(gòu)上統(tǒng)計二叉樹中結(jié)點個數(shù)的算法。voidcountnode(bitree*bt,int&count){if(bt!=0){count++;countnode(bt->lchild,count);countnode(bt->rchild,count);}}設(shè)計一個算法將無向圖的毗鄰矩陣轉(zhuǎn)為對應(yīng)毗鄰表的算法。typedefstruct{intvertex[m];intedge[m][m];}gadjmatrix;typedefstructnode1{intinfo;intadjvertex;structnode1*nextarc;}glinklistnode;typedefstructnode2{intvertexinfo;glinklistnode*firstarc;}glinkheadnode;voidadjmatrixtoadjlist(gadjmatrixg1[],glinkheadnodeg2[]){inti,j;glinklistnode*p;for(i=0;i<=n-1;i++)g2[i].firstarc=0;for(i=0;i<=n-1;i++)for(j=0;j<=n-1;j++)if(g1.edge[i][j]==1){p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=