2023級(jí)算法與數(shù)據(jù)結(jié)構(gòu)試題A

1、山 西 財(cái) 經(jīng) 大 學(xué)20232023學(xué)年第 2學(xué)期期末算法與數(shù)據(jù)結(jié)構(gòu)課程試卷A卷題 號(hào)一二三四五總分分 數(shù)評(píng)卷人復(fù)核人 1、本卷考試形式為閉卷，考試時(shí)間為兩小時(shí)。2、考生不得將裝訂成冊(cè)的試卷拆散，不得將試卷或答題卡帶出考場。3、考生只允許在密封線以外答題，答在密封線以內(nèi)的將不予評(píng)分。4、考生答題時(shí)一律使用藍(lán)色、黑色鋼筆或圓珠筆制圖、制表等除外。5、考生禁止攜帶 、耳麥等通訊器材。否那么，視為作弊。一、單項(xiàng)選擇題共10小題，每題 1分，共計(jì)10 分二、判斷題共10小題，每題1 分，共計(jì)10分三、簡答題共4小題，每題5 分，共計(jì)20分四、應(yīng)用題共8小題，1-6小題必做，7、8任選一，1-2每題5

2、 分，3-8每題6分，共計(jì)40分五、算法設(shè)計(jì)題1、2小題任選一，3、4小題任選一，每題10分，共計(jì)20分此題得分單項(xiàng)選擇題共10小題，每題 1分，共計(jì)10此題得分答題要求：請(qǐng)將正確的選項(xiàng)填在題后的括號(hào)中1假設(shè)某線性表最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，那么以下的存儲(chǔ)方式中最節(jié)省時(shí)間的是( )。A單鏈表 B僅有頭指針的單循環(huán)鏈表C雙向鏈表 D僅有尾指針的單循環(huán)鏈表2.下面給出的算法段是要把一個(gè)p所指新結(jié)點(diǎn)，插入到非空雙向鏈表中，作為該雙鏈中q所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，能正確完成要求的算法段是 。Ap-llink=q-llink; B q-llink=p;p-rlink=q;p

3、-rlink=q;q-llink-rlink=p;q-llink-rlink=p;q-llink=p;p-llink=q-llink;Cp-rlink=q; D p-rlink=q;p-llink=q-llink; p-llink=q-llink; q-llink=p; q-rlink=p;q-llink-rlink=p; q-llink-rlink=p;3以下選項(xiàng)中， 是非線性數(shù)據(jù)結(jié)構(gòu)。A棧 B. 隊(duì)列 C. 完全二叉樹 D. 堆4判定一個(gè)循環(huán)隊(duì)列Q(最多元素為m0)為滿隊(duì)列的條件是( )。AQ.front !=Q.rearBQ.front=Q.rearCQ.front !=(Q.rear+

4、1)%m0DQ.front=(Q.rear+1)%m05串的長度是( )。A串中不同字母的個(gè)數(shù)B串中不同字符的個(gè)數(shù)C串中所含字符的個(gè)數(shù)，且大于0 D串中所含字符的個(gè)數(shù)6數(shù)組A中，每個(gè)元素的長度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A75的起始地址為 。ASA+192 BSA+195CSA+222 DSA+2257設(shè)森林F對(duì)應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p,p的右子樹結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是 Am-n Bm-n-1 Cn+1 D條件缺乏，無法確定8有向網(wǎng)G用鄰接矩陣A存儲(chǔ)，那么頂點(diǎn)i的入度等于A中(

5、)。A第i行非元素之和B第i列非的元素之和C第i行非且非0的元素個(gè)數(shù)D第i列非且非0的元素個(gè)數(shù)9對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須 。A以順序方式存儲(chǔ) B以鏈接方式存儲(chǔ)C以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列D以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列10以下排序算法中，在某趟結(jié)束后不一定能選出一個(gè)元素放到其最終的位置上的是()。此題得分A堆 B歸并C起泡 D此題得分判斷題共10小題，每題1 分，共計(jì)10分答題要求：正確的請(qǐng)?jiān)陬}后的括號(hào)內(nèi)打“，錯(cuò)誤的請(qǐng)打“x1順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。()2在鏈表中，邏輯上相鄰的兩個(gè)元素在物理上不一定相鄰。( )3棧和隊(duì)列的存儲(chǔ)方

6、式，可以采用順序方式，也可以采用鏈?zhǔn)椒绞健? )4數(shù)組可以看成是線性結(jié)構(gòu)的一種推廣，因此可以對(duì)它進(jìn)行插入、刪除。 5一棵樹中的葉子數(shù)一定等于與其對(duì)應(yīng)的二叉樹的葉子數(shù)。()6刪除二叉排序樹中的一個(gè)結(jié)點(diǎn)，再重新插入進(jìn)去，一定能得到原來的二叉排序樹。 ( )7采用散列法存儲(chǔ)，負(fù)載因子越大，發(fā)生碰撞的可能性也越大。 ( )8假設(shè)一棵樹中某結(jié)點(diǎn)的度為1，那么該結(jié)點(diǎn)僅有一棵子樹。 ()9如果一個(gè)串中的所有字符均在另一串中出現(xiàn)，那么說前者是后者的子串。( )10對(duì)任意一個(gè)圖，從它的某個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索遍歷可訪問到該圖的每個(gè)頂點(diǎn)。( )此題得分三、簡答題共4小題，每題5 分，共計(jì)20此題

7、得分答題要求：第2、3題請(qǐng)寫出中間過程，只寫結(jié)果不得分1.請(qǐng)簡述棧和隊(duì)列的相同和不同之處。2.完全二叉樹的第8層有10個(gè)結(jié)點(diǎn)，那么整個(gè)二叉樹的結(jié)點(diǎn)數(shù)最多為？3.什么是二叉排序樹？如何在二叉排序樹上實(shí)施查找操作？4.直接插入排序和快速排序兩種算法的穩(wěn)定性如何?請(qǐng)寫出原因。此題得分應(yīng)用題1-6小題必做，7、8任選一，1-2每題5 分，3-8每題6分，共計(jì)40此題得分答題要求：請(qǐng)盡量寫出中間過程1.設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角局部按行序存放在一維數(shù)組B1，n(n-1)/2中，對(duì)上三角局部的任一元素ai,j(ij)，求它在一組數(shù)組B中的下標(biāo)位置k的值？bacfdebacfdehg(

8、1)請(qǐng)畫出它的順序存儲(chǔ)表示(2)寫出它的中序遍歷序列(3)畫出它的后序線索二叉樹。3.某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdcefgh，中序遍歷的結(jié)點(diǎn)訪問順序是cbdagfeh，請(qǐng)畫出該二叉樹。4.以數(shù)據(jù)集3,5,9,14,16,25,33為結(jié)點(diǎn)權(quán)值(1)請(qǐng)構(gòu)造的哈夫曼樹。(2)并求出它的帶權(quán)路徑長度。5.哈希表長為11，請(qǐng)給出對(duì)序列7，18，40，35，9，33，28，37，90進(jìn)行散列，按照哈希函數(shù)H(key)key MOD 11，及線性線性探測再散列處理沖突，請(qǐng)給出處理的過程及結(jié)果。6序列30，8，25，15，78，97，65，43，72，采用堆排序法對(duì)該序列作升序排序。建立的初始堆應(yīng)是

9、大頂堆還是小頂堆？建初始堆時(shí)應(yīng)從哪一個(gè)位置開始篩選？請(qǐng)畫出建成的初始堆。7求出下面AOE網(wǎng)中的關(guān)鍵路徑。要求標(biāo)明每個(gè)頂點(diǎn)的最早和最遲發(fā)生時(shí)間，并畫出關(guān)鍵路徑。10104997a1bcdegf6513268求出以下圖的一棵最小生成樹，要求給出過程和所依據(jù)的是哪一種算法。88106596142538763437512此題得分五、算法設(shè)計(jì)題此題得分任選一，每題10分，共計(jì)20分答題要求：在寫出算法之前先簡要寫出算法思想；在算法中盡可能寫一些注釋信息。不按要求只寫算法不得分。單鏈表存儲(chǔ)結(jié)構(gòu)如下：typedef struct Lnode Elemtype data; Struct Lnode *next;Lnode,*Linklist;試編寫在帶頭結(jié)點(diǎn)的單鏈表中刪除最小值結(jié)點(diǎn)的算法。void deleteLinklist &L請(qǐng)編寫對(duì)不帶頭結(jié)點(diǎn)的單鏈表進(jìn)行就地逆置的算法，要求算法用L返回逆置后的鏈表的頭指針。二叉鏈表存儲(chǔ)表示定義如下：typedef struct BiTNo