天津大學(xué)23春“計(jì)算機(jī)科學(xué)與技術(shù)”《數(shù)據(jù)結(jié)構(gòu)》考試高頻考點(diǎn)參考題庫(kù)含答案

長(zhǎng)風(fēng)破浪會(huì)有時(shí)，直掛云帆濟(jì)滄海。天津大學(xué)23春“計(jì)算機(jī)科學(xué)與技術(shù)”《數(shù)據(jù)結(jié)構(gòu)》考試高頻考點(diǎn)參考題庫(kù)帶答案（圖片大小可自由調(diào)整）第I卷一.綜合考核(共15題)1.設(shè)有一個(gè)10階的下三角矩陣A(包括對(duì)角線)，按照從上到下、從左到右的順序存儲(chǔ)到連續(xù)的55個(gè)存儲(chǔ)單元中，每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲(chǔ)空間，則A[5][4]地址與A[0][0]的地址之差為()。A.55B.28C.19D.102.對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為()。A.O(n2)B.O(n)C.O(1og2n)D.O(1)3.二叉樹(shù)的第k層的結(jié)點(diǎn)數(shù)最多為()。A.B.C.2K-1D.2K+14.設(shè)串s1=‘ABCDEFG’，s2=‘PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號(hào)i的字符開(kāi)始的j個(gè)字符組成的子串，len(s)返回串s的長(zhǎng)度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是()。A.BCPQRSTB.BCDEFGC.BCDEFEFD.BCDEF5.設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過(guò)()。A.log2n-1B.log2n+1C.log2nD.log2(n+1)6.快速排序方法在()情況下最不利于發(fā)揮其長(zhǎng)處。A.要排序的數(shù)據(jù)量太大B.要排序的數(shù)據(jù)已基本有序C.要排序的數(shù)據(jù)中含有多個(gè)相同值D.要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)7.對(duì)一個(gè)滿二叉樹(shù)，m個(gè)樹(shù)葉，n個(gè)結(jié)點(diǎn)，深度為h，則()。A.n=h+mB.n=2的h次方-1C.m=h-1D.h+m=2n8.設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是()。A.P，A，C，S，Q，D，F(xiàn)，X，R，H，M，YB.H，C，Q，P，A，M，S，R，D，F(xiàn)，X，YC.F，H，C，D，P，A，M，Q，R，S，Y，XD.A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X9.設(shè)順序表的長(zhǎng)度為n，則順序查找的平均比較次數(shù)為()。A.n/2B.nC.(n-1)/2D.(n+1)/210.設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D，R)，其中D={1，2，3，4}，R={r}，r={，，，}，則數(shù)據(jù)結(jié)構(gòu)A是()。A.集合B.線性結(jié)構(gòu)C.樹(shù)型結(jié)構(gòu)D.圖型結(jié)構(gòu)11.下列四種排序中()的空間復(fù)雜度最大。A.插入排序B.歸并排序C.堆排序D.冒泡排序12.設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為()。A.s->left=p;s->right=p->right;p->right=s;p->right->left=sB.s->left=p;s->right=p->right;p->right->left=s;p->right=sC.p->right=s;s->left=p;p->right->left=s;s->right=p->rightD.p->right=s;p->right->left=s;s->left=p;s->right=p->right13.如果只想得到1024個(gè)元素組成的序列中第5個(gè)最小元素之前的部分排序的序列，用()方法最快。A.起泡排序B.簡(jiǎn)單選擇排序C.快速排序D.堆排序14.在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行()。A.p=p->next;p->next=p->next->nextB.p=p->next->nextC.p->next=p->next->nextD.p->next=p->next15.在一非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊()。A.只有左子樹(shù)上的部分結(jié)點(diǎn)B.只有左子樹(shù)上的所有結(jié)點(diǎn)C.只有右子樹(shù)上的部分結(jié)點(diǎn)D.只有右子樹(shù)上的所有結(jié)點(diǎn)第II卷一.綜合考核(共15題)1.判定一個(gè)順序棧ST(最多元素為m0)為棧滿的條件是()。A.top!=m0B.top!=0C.top==m0-1D.top==02.從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行()。(不帶空的頭結(jié)點(diǎn))A.x=HS->data;HS=HS->nextB.x=HS->dataC.x=HS;HS=HS->nextD.HS=HS->next;x=HS->data3.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的()倍。A.4B.2C.1/2D.14.若有18個(gè)元素的有序表存放在一維數(shù)組A[19]中，第一個(gè)元素放A[1]中，現(xiàn)進(jìn)行二分查找，則查找A[3]的比較序列的下標(biāo)依次為()。A.9，5，3B.9，5，2，3C.9，4，2，3D.1，2，35.有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有()條邊。A.56B.28C.14D.1126.二叉排序樹(shù)中左子樹(shù)上所有結(jié)點(diǎn)的值均()根結(jié)點(diǎn)的值。A.>B.=C.D.!=7.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址()。A.部分地址必須是連續(xù)的B.連續(xù)或不連續(xù)都可以C.必須是連續(xù)的D.一定是不連續(xù)的8.判定一個(gè)順序棧ST(最多元素為m0)為空的條件是()。A.top==m0-1B.top==0C.top!=m0D.top!=09.一組記錄的關(guān)鍵碼為(46，79，56，38，40，84)，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為()。A.40，38，46，84，56，79B.40，38，46，79，56，84C.40，38，46，56，79，84D.38，40，46，56，79，8410.樹(shù)最適合用來(lái)表示()。A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C.元素之間無(wú)聯(lián)系的數(shù)據(jù)D.元素之間具有分支層次關(guān)系的數(shù)據(jù)11.把一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài)是()。A.有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子B.有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子C.有多種D.唯一的12.設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)，則該無(wú)向圖的最小生成樹(shù)上有()條邊。A.n-1B.nC.2n-1D.2n13.按照二叉樹(shù)的定義，具有3個(gè)不同數(shù)據(jù)結(jié)點(diǎn)的不同的二叉樹(shù)有()種。A.6B.5C.32D.3014.任何一個(gè)無(wú)向連通圖的最小生成樹(shù)()。A.有一棵或多棵B.可能不存在C.只有一棵D.一定有多棵15.在以下的敘述中，正確的是()。A.線性表的順序存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況B.線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)C.線性表的鏈表存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況D.線性表的鏈表存儲(chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)第III卷一.綜合考核(共15題)1.采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為()。A.n/2B.nC.(n-1)/2D.(n+1)/22.設(shè)某散列表的長(zhǎng)度為100，散列函數(shù)H(k)=k%P，則P通常情況下最好選擇()。A.99B.97C.93D.913.假定在一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為()個(gè)。A.47B.17C.16D.154.具有五層結(jié)點(diǎn)的二叉平衡樹(shù)至少有()個(gè)結(jié)點(diǎn)。A.17B.15C.12D.105.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)()。A.頭、尾指針都要修改B.頭、尾指針可能都要修改C.僅修改尾指針D.僅修改頭指針6.深度為5的二叉樹(shù)至多有()個(gè)結(jié)點(diǎn)。A.32B.31C.16D.107.隊(duì)列是一種()的線性表。A.只能插入B.只能刪除C.先進(jìn)后出D.先進(jìn)先出8.用某種排序方法對(duì)線性表(25，84，21，47，15，27，68，35，20)進(jìn)行排序時(shí)，元素序列的變化情況如下：⑴25，84，21，47，15，27，68，35，20;⑵20，15，21，25，47，27，68，35，84;⑶15，20，21，25，35，27，47，68，84;⑷15，20，21，25，27，35，47，68，84。則所采用的排序方法是()。A.選擇排序B.快速排序C.歸并排序D.希爾排序9.設(shè)F是由T1、T2和T3三棵樹(shù)組成的森林，與F對(duì)應(yīng)的二叉樹(shù)為B，T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，則二叉樹(shù)B的根結(jié)點(diǎn)的左子樹(shù)的結(jié)點(diǎn)數(shù)為()。A.N2+N3B.N2-1C.N1+N3D.N1-110.設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)=key%p，則p最好選擇()。A.小于等于m的最大素?cái)?shù)B.小于等于m的最大奇數(shù)C.小于等于m的最大合數(shù)D.小于等于m的最大偶數(shù)11.有一個(gè)長(zhǎng)度為12的有序表，按二分查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為()。A.43/12B.39/12C.37/12D.35/1212.設(shè)一棵二叉樹(shù)的深度為k，則該二叉樹(shù)中最多有()個(gè)結(jié)點(diǎn)。A.2k-1B.C.D.13.以下敘述中正確的是()。A.空串就是空白串B.串的長(zhǎng)度必須大于零C.串是一種特殊的線性表D.串中無(wú)素只能是字母14.某二叉樹(shù)的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是()。A.gdbehfcaB.gdbecfhaC.bdgcefhaD.bdgaechf15.設(shè)一個(gè)順序有序表A[1:14]中有14個(gè)元素，則采用二分法查找元素A[4]的過(guò)程中比較元素的順序?yàn)?)。A.A[7]，A[5]，A[3]，A[4]B.A[7]，A[3]，A[5]，A[4]C.A[1]，A[2]，A[3]，A[4]D.A[1]，A[14]，A[7]，A[4]第I卷參考答案一.綜合考核1.參考答案：C2.參考答案：C3.參考答案：B4.參考答案：C5.參考答案：B6.參考答案：B7.參考答案：B8.參考答案：B9.參考答案：D10.參考答案：D11.參考答案：B12.參考答案：B13.參考答案：D14.參考答案：B15.參考答案：D第II卷參考答案一.綜合考核1.參考答案：C2.參考答案：A3.參考答案：B4.參考答案：C5.參考答案：B6.參考