考研真題：廣東暨南大學(xué)2021年數(shù)據(jù)結(jié)構(gòu)考試真題

考研真題：暨南大學(xué)2021年[數(shù)據(jù)結(jié)構(gòu)]考試真題一、單項(xiàng)選擇題1.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？（）A.二叉樹B.棧C.線性表D.隊(duì)列2.當(dāng)要對(duì)線性表進(jìn)行折半查找時(shí)，線性表必須滿足以下條件（）。A.以順序方式存儲(chǔ)B.以鏈表方式存儲(chǔ)C.以順序方式存儲(chǔ)且按關(guān)鍵字有序排列D.以鏈表方式存儲(chǔ)且按關(guān)鍵字有序排列3.為了提高哈希表的查找效率，以下方法說法不正確的是（）。A.設(shè)計(jì)好的哈希函數(shù)B.增加哈希函數(shù)的個(gè)數(shù)C.增大存儲(chǔ)空間D.采用更好的地址沖突解決方法4.用單向鏈表來實(shí)現(xiàn)容量為n的堆棧時(shí)，鏈表頭指針指向堆棧頂部元素，鏈表尾指針指向堆棧底部元素，則以下說法錯(cuò)誤的是（）A.入棧操作的復(fù)雜度為O(1)B.出棧操作的復(fù)雜度為O(1)C.插入一個(gè)新的堆棧底部元素復(fù)雜度為O(1)D.刪除底部元素的復(fù)雜度為O(1)5.設(shè)一個(gè)順序有序的一維數(shù)組A[1:14]中有14個(gè)元素，采用二分查找算法查找到A[4]中的元素過程中需要比較的元素的順序是（）A.A[1],A[2],A[3],A[4]B.A[7],A[3],A[5],A[4]C.A[1],A[14],A[7],A[4]D.A[7],A[5],A[3],A[4]6.稀疏矩陣一般采用的壓縮存儲(chǔ)方法有兩種，即（）A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.十字鏈表和散列7.設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)先訪問a后訪問b的條件是（）A.a在B的左邊B.a在b的右邊C.a是b的祖先D.a是b的子孫8.某二叉樹的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹結(jié)點(diǎn)數(shù)為（）A.5B.4C.3D.29.判斷一個(gè)有向圖中是否存在環(huán)（回路），可采用以下方法（）A.廣度優(yōu)先遍歷B.求關(guān)鍵路徑C.求最短路徑D.拓?fù)渑判?0.用哈希表存儲(chǔ)7個(gè)整數(shù)18,25,63,50,42,32,9,如果哈希函數(shù)為H(x)=xmod9，則與18發(fā)生地址沖突的整數(shù)有（）個(gè)A.1B.2C.3D.4二、填空題1.數(shù)據(jù)結(jié)構(gòu)的三要素是指（）（）（）。2.在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)（），具體移動(dòng)的元素個(gè)數(shù)與（）有關(guān)。3.設(shè)棧S與隊(duì)列Q的初始狀態(tài)皆為空，元素a1,a2,a3,a4,a5和a6依次通過一個(gè)棧，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)列的順序是a3,a5,a4,a6,a2,a1,則棧S至少應(yīng)該容納（）個(gè)元素。4.有一個(gè)10階對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式（以行序?yàn)橹?，且A[0][0]=1）,則A[8][5]的地址是（）5.含有100個(gè)結(jié)點(diǎn)的樹有（）條邊。6.已知二叉樹的前序序列為ABDEGCFHIJ，中序序列為DBGEAHFIJC，請(qǐng)寫出后序列（）。7.在一個(gè)無向圖的鄰接表中，若表結(jié)點(diǎn)數(shù)目為m，則圖中邊的條數(shù)為（）。三．判斷題通過使用線性鏈表來實(shí)現(xiàn)堆棧，可以使得每次入棧/出棧操作的時(shí)間復(fù)雜度為O(1)。（）深度優(yōu)先搜索的核心數(shù)據(jù)結(jié)構(gòu)是隊(duì)列。（）將包含n個(gè)元素的升序線性鏈表改成降序線性鏈表所需要的時(shí)間復(fù)雜度為O(n)。（）選擇排序算法是穩(wěn)定的。（）一棵高度為h的完全二叉樹的結(jié)點(diǎn)數(shù)量比同樣高度的一棵滿二叉樹的結(jié)點(diǎn)要多。（）平衡二叉樹（AVL）的優(yōu)點(diǎn)是能夠保證在最壞情況下的查找時(shí)間復(fù)雜度為O(logN)。（）無向圖的鄰接矩陣是對(duì)稱的，因此只需要存儲(chǔ)矩陣的下三角陣以節(jié)省存儲(chǔ)空間。（）一棵高度為h的完全二叉樹可能的最大結(jié)點(diǎn)個(gè)數(shù)為2h個(gè)。（）在快速排序、冒泡排序、希爾排序、堆排序中，空間復(fù)雜度最高的是快速排序。（）將一棵樹轉(zhuǎn)化成一棵二叉樹，則該二叉樹的右子樹不一定為空。（）四、簡(jiǎn)答題1.描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。（6分）2.簡(jiǎn)述線性表、隊(duì)列和堆棧這三種數(shù)據(jù)類型的相同點(diǎn)和差異處。（6分）3.在程序設(shè)計(jì)中，可采用下列三種方法實(shí)現(xiàn)輸出和輸入:（1）通過scanf和printf語句;(2)通過函數(shù)的參數(shù)顯式傳遞;(3)通過全局變量隱式傳遞。試討論這三種方法的優(yōu)缺點(diǎn)。（6分）4.試著描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語言中數(shù)據(jù)類型概念的區(qū)別。（6分）5.試寫出一種算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Length(L)。（8分）6.請(qǐng)用順序存儲(chǔ)的方式，用C語言寫出實(shí)現(xiàn)把串S1復(fù)制到串S2的串復(fù)制函數(shù)strcpy（S1，S2）。（8分）五、算法填空1.假設(shè)有一棵二叉查找樹，其每個(gè)結(jié)點(diǎn)包含鍵值key、左孩子指針left和右孩子指針right，指針p指向該二叉樹的根結(jié)點(diǎn)。現(xiàn)要查找鍵值為x的結(jié)點(diǎn)，如果該二叉樹中存在鍵值為x的結(jié)點(diǎn)，則返回指向該結(jié)點(diǎn)的指針；如果不存在，則返回空指針NULL。請(qǐng)?zhí)顚懴旅鍯代碼中空白的部分，使其成為完整的算法以完成對(duì)二叉樹的查找。SearchBinaryTree(p,x){if(p==NULL||（1）)returnp;if(2)return(3)_______;elsereturn(4);}請(qǐng)將以上空白處的答案填寫在下面對(duì)應(yīng)位置：2．給定一個(gè)單向鏈表L，鏈表中的結(jié)點(diǎn)按照鍵值大小升序排列。以下的代碼可以將L中所有鍵值相同的結(jié)點(diǎn)從L中刪除，請(qǐng)將代碼中空白處填寫完整。Structnode{intkey;node*next;}intDeleteDuplicate(node*L){node*p,*q;if(L==NULL||L->next==NULL)return-1;p=L;q=p->next;while(p->next!=NULL){if(p->key!=q->key){（1）;（2）;}else{while(（3）){node*tmp=q->next;deleteq;（4）;if(q==NULL)break;}if(q!=NULL){（5）;p=p->next;q=p->next;}else（6）;}}}請(qǐng)將以上代碼的空白處答案填寫在下方相應(yīng)位置：(1)(2)(3)(4)(5)(6)

六．編寫算法1.假設(shè)稱正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’和‘a(chǎn)babab’則不是回文。試寫一個(gè)算法判別讀入的一個(gè)以‘@’為結(jié)束符的字符序列是否是“回文”。（10分）2.已知由一個(gè)線性鏈表表示的線性表中含有三類字