2020年考研計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)模擬試題及答案三

2020年考研計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)模擬試題及答案(三)一、選擇題(30分)1.字符串的長(zhǎng)度是指()。(A)串中不同字符的個(gè)數(shù)(B)串中不同字母的個(gè)數(shù)(C)串中所含字符的個(gè)數(shù)(D)串中不同數(shù)字的個(gè)數(shù)2.建立一個(gè)長(zhǎng)度為n的有序單鏈表的時(shí)間復(fù)雜度為()(A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)3.兩個(gè)字符串相等的充要條件是()。(A)兩個(gè)字符串的長(zhǎng)度相等(B)兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等(C)同時(shí)具備(A)和(B)兩個(gè)條件(D)以上答案都不對(duì)4.設(shè)某散列表的長(zhǎng)度為100，散列函數(shù)H(k)=k%P,則P通常情況下選擇()。(A)99(B)97(C)91(D)935.在二叉排序樹(shù)中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為()。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n2)6.設(shè)一個(gè)順序有序表A[1：14]中有14個(gè)元素，則采用二分法查找元素A[4]的過(guò)程中比較元素的順序?yàn)?)。(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è)一棵完全二叉樹(shù)中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹(shù)的深度為()。（A）8（B）7（C）6（D）58.設(shè)一棵三叉樹(shù)中有2個(gè)度數(shù)為1的結(jié)點(diǎn)，2個(gè)度數(shù)為2的結(jié)點(diǎn)，2個(gè)度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有（）個(gè)度數(shù)為0的結(jié)點(diǎn)。（A）5（B）6（C）7（D）89.設(shè)無(wú)向圖6中的邊的集合E=｛（a，b），（a，e），（a，c），（b，e），（e，d），（d，f），（f，c）｝，則從頂點(diǎn)a出發(fā)實(shí)行深度優(yōu)先遍歷能夠得到的一種頂點(diǎn)序列為（）。（A）aedfcb（B）acfebd（C）aebcfd（D）aedfbc10.隊(duì)列是一種（）的線性表。（A）先進(jìn)先出（B）先進(jìn)后出（C）只能插入（D）只能刪除斷題（20分）1.如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個(gè)關(guān)鍵字為同義詞。（）2.設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時(shí)間復(fù)雜度為O（nlog2n）。（）3.分塊查找的基本思想是首先在索引表中實(shí)行查找，以便確定給定的關(guān)鍵字可能存有的塊號(hào)，然后再在相對(duì)應(yīng)的塊內(nèi)實(shí)行順序查找。（）4.二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。（）5.向二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹(shù)的高度。（）6.如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。（）7.非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。（）8.不論線性表采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，刪除值為X的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。()9.圖的深度優(yōu)先遍歷算法中需要設(shè)置一個(gè)標(biāo)志數(shù)組，以便區(qū)分圖中的每個(gè)頂點(diǎn)是否被訪問(wèn)過(guò)。()10.稀疏矩陣的壓縮存儲(chǔ)能夠用一個(gè)三元組表來(lái)表示稀疏矩陣中的非0元素。()三、填空題(30分)1.設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27,50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為 O2.下面程序段的功能是實(shí)現(xiàn)在二叉排序樹(shù)中插入一個(gè)新結(jié)點(diǎn)，請(qǐng)?jiān)谙聞澗€處填上準(zhǔn)確的內(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è)指針變量口指向單鏈表中結(jié)點(diǎn)A，指針變量$指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X需要執(zhí)行的語(yǔ)句序列：s->next=p->next;;。4.設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量p指向雙向鏈表中的第一個(gè)結(jié)點(diǎn)，則指針變量p和指針變量head之間的關(guān)系是p=和head=（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink）。5.設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為。6.完全二叉樹(shù)中第5層上最少有個(gè)結(jié)點(diǎn)，最多有 個(gè)結(jié)點(diǎn)。7.設(shè)有向圖中不存有有向邊，則其對(duì)應(yīng)的鄰接矩陣A中的數(shù)組元素A[i][j]的值等于。8.設(shè)一組初始記錄關(guān)鍵字序列為（49，38，65，97，76，13，27,50），則第4趟直接選擇排序結(jié)束后的結(jié)果為 O9.設(shè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則對(duì)應(yīng)的最小生成樹(shù)上有條邊。10.設(shè)有一組初始記錄關(guān)鍵字序列為（50，16，23，68，94，70，73），則將它們調(diào)整成初始堆只需把16與相互交換即可。法設(shè)計(jì)題（20分）1.設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。2.設(shè)計(jì)一個(gè)算法將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。答案一、選擇題C2.C3.C4.B5.B6.C7.B8.C9.A10.A二、判斷題1.對(duì)2.錯(cuò)3.對(duì)4.錯(cuò)5.錯(cuò)6.對(duì)7.對(duì)8.對(duì)9.對(duì)10.對(duì)三、填空題1.(49，13，27，50，76，38，65，97)2.t=(bitree*)malloc(sizeof(bitree))，bstinsert(t->rchild,k)3.p->next=s4.head->rlink，p->llink5.CABD6.1，167.08.(13，27，38，50，76，49，65，97)9.n-110.50四、算法設(shè)計(jì)題1.1.設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。voidcountnode(bitree*bt,int&count){if(bt!=0){count++;countnode(bt->lchild,count);countnode(bt->rchild,count);}}2.2.設(shè)計(jì)一個(gè)算法將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(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;iadjvertex=j