2023年河海大學(xué)計算機(jī)科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A(含答案)

2023試卷A〔有答案〕一、選擇題1、用有向無環(huán)圖描述表達(dá)式(A+B)*((A+B)／/A)，至少需要頂點(diǎn)的數(shù)目為〔 〕。A.5B.6C.8D.92、下述文件中適合于磁帶存儲的是〔 〕。挨次文件索引文件C.哈希文件D.多關(guān)鍵字文件計時，存儲單元的地址〔 〕。A.肯定連續(xù)B.肯定不連續(xù)C.不肯定D.局部連續(xù)，局部不連續(xù)4、向一個棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時，應(yīng)執(zhí)行〔 〕。A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s5、用不帶頭結(jié)點(diǎn)的單鏈表存儲隊列，其隊頭指針指向隊頭結(jié)點(diǎn)，隊尾指針指向隊尾結(jié)點(diǎn)，〔 〕。A.僅修改隊頭指針B.僅修改隊尾指針C.隊頭、隊尾指針都可能要修改D.隊頭、隊尾指針都要修改6、循環(huán)隊列放在一維數(shù)A中，end1指向隊頭元素，end2指向隊尾元素的后一個位置。假設(shè)隊列兩端均可進(jìn)展入隊和出隊操作，隊列中最多能容納M－1個元素。初始時為空，以下推斷隊空和隊滿的條件中，正確的選項(xiàng)是〔 〕。隊空：end1＝＝end2；隊滿：end1＝＝〔end2＋1〕modM隊空：end1＝＝end2；隊滿：end2＝＝〔end1＋1〕mod〔M－1〕隊空：end2＝＝〔end1＋1〕modM；隊滿：end1＝＝〔end2＋1〕modM；隊滿：end2＝＝〔end1＋1〕mod〔M－1〕7、排序過程中，對尚未確定最終位置的全部元素進(jìn)展一遍處理稱為一趟排序。以下排序方法中，每一趟排序完畢時都至少能夠確定一個元素最終位置的方法是〔〕。Ⅰ．簡潔選擇排序Ⅱ．希爾排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路歸并排序A．僅Ⅰ、Ⅲ、ⅣB．僅Ⅰ、Ⅱ、ⅢC．僅Ⅱ、Ⅲ、ⅣD．僅Ⅲ、Ⅳ、Ⅴ81025個結(jié)點(diǎn)的二叉樹的高h(yuǎn)為〔〕。A.11B.10C.11 至1025之間D.10 至1024之間9、下述二叉樹中，哪一種滿足性質(zhì)：從任一結(jié)點(diǎn)動身到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序〔〕。A.二叉排序樹B. 哈夫曼樹C.AVL 樹D. 堆10、數(shù)據(jù)序列〔8，9，10，4，5，6，20，1，2〕只能是以下排序算法中的〔〕的兩趟排序后的結(jié)果。A.選擇排序B.起泡排序C.插入排序D. 堆排序二、填空題11、以下程序的功能是實(shí)現(xiàn)帶附加頭結(jié)點(diǎn)的單鏈表數(shù)據(jù)結(jié)點(diǎn)逆序連接，請?zhí)羁胀晟浦?2、假設(shè)用n表示圖中頂點(diǎn)數(shù)目，則有 條邊的無向圖成為完全圖。別是后序線索二叉樹求給定結(jié)node的前驅(qū)結(jié)點(diǎn)與后繼結(jié)點(diǎn)的算法，請在算法空格處填上正確的語句。設(shè)線索二叉樹的結(jié)點(diǎn)數(shù)據(jù)構(gòu)造為〔lflag，left，data，right，rflag〕，其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驅(qū)；rflag=0，rightrflag=1，right指向其后繼。14、設(shè)T是一棵結(jié)點(diǎn)值為整數(shù)的二叉排序樹，A是一個任意給定的整數(shù)。在下面的算法中，free_tree〔T〕在對二叉排序樹丁進(jìn)展后序遍歷時釋放二又排序樹T的全部結(jié)點(diǎn)；delete_subtree〔T，A〕，首先在二叉排序樹T中查找A的結(jié)點(diǎn)，依據(jù)查找狀況分別進(jìn)展如下處理：〔1〕假設(shè)找不到值為A的結(jié)點(diǎn)，則返回根結(jié)點(diǎn)的地址〔2〕假設(shè)找到A的結(jié)點(diǎn)，則刪除以此結(jié)點(diǎn)為根的子樹，并釋放此子樹中的全部結(jié)點(diǎn)，假設(shè)值為A的結(jié)點(diǎn)是查找樹的根結(jié)點(diǎn)，刪除后變成空的二叉樹，則null；否則返回根結(jié)點(diǎn)的地址。15、有序表為〔12，18，24，35，47，50，62，83，90，115，134〕當(dāng)用二分法查找90時，需 次查找成功，查找47時 成功，查找100時，需 次才能確定不成功。16、一循環(huán)隊列的存儲空間為[m..n]，其中n>m，隊頭和隊尾指針分別為front和rear，則此循環(huán)隊列判滿的條件是 。17、閱讀以下程序說明和程序，填充程序中的 。【程序說明】本程序完成將二叉樹中左、右孩子交換的操作。交換的結(jié)果如下所示〔編者略〕。本程序承受非遞歸的方法，設(shè)立一個堆棧stack存放還沒有轉(zhuǎn)換過的結(jié)點(diǎn)，它的棧頂指針tp。交換左、右子樹的算法為：把根結(jié)點(diǎn)放入堆棧。當(dāng)堆棧不空時，取出棧頂元素，交換它的左、右子樹，并把它的左、右子樹分別入棧。重復(fù)〔2〕直到堆棧為空時為止。經(jīng)過PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，輸出序列是，而棧頂指針值是。設(shè)棧為挨次棧4個字節(jié)。三、推斷題19、直接訪問文件也能挨次訪問，只是一般效率不高?！?〕20、倒排文件是對次關(guān)鍵字建立索引。〔 〕21、在鏈隊列中，即使不設(shè)置尾指針也能進(jìn)展入隊操作。〔 〕22、數(shù)組不適合作為任何二叉樹的存儲構(gòu)造?！?〕23、一棵樹中的葉子數(shù)肯定等于與其對應(yīng)的二叉樹的葉子數(shù)。〔 〕24、樹形構(gòu)造中元素之間存在一對多的關(guān)系?！?〕25、抽象數(shù)據(jù)類型與計算機(jī)內(nèi)部表示和實(shí)現(xiàn)無關(guān)?！?〕26、數(shù)據(jù)元素是數(shù)據(jù)的最小單位?！?〕27、B-樹中全部結(jié)點(diǎn)的平衡因子都為零?！?〕28、有向圖中頂點(diǎn)V度等于其鄰接矩陣中第V行中的1的個數(shù)?！?〕四、簡答題29、對于具有n個葉結(jié)點(diǎn)且全部非葉結(jié)點(diǎn)都有左、右孩子的二叉樹。i試問這種二叉樹的結(jié)點(diǎn)總數(shù)是多少?i1〕。

2-〔li-1〕=1。其中：li個葉結(jié)點(diǎn)所在的層號〔設(shè)根結(jié)點(diǎn)所在層號為30、假定對有序表：〔3，4，5，7，24，30，42，54，63，72，8795〕進(jìn)展折半查找，試答復(fù)以下問題：查找過程的判定樹。假設(shè)查54，需依次與哪些元素比較?假設(shè)查90，需依次與哪些元素比較?查找概率相等，求查找成功時的平均查找長度。A＝〔a

，a，…，a 〕，0≤a＜0 1 n0 1 n1 n〔0≤i≤n〕，假設(shè)存在a

＝a ＝…＝a ＝xm＞n/2〔0≤p≤n1≤k≤m〕，則xAp1 p2 pm kA＝〔0，5，5，3，5，7，55〕，則5為A＝〔0，5，5，3，5，1，5，7〕則A中沒有主元素。假設(shè)An個元素保存在一個一維數(shù)組中，請設(shè)計一個盡可能高效的算法，找出A的主元素。假設(shè)存在主元素，則輸出該元素；否則輸出－1。要求：出算法的根本設(shè)計思想。依據(jù)設(shè)計思想，承受CCJava語言描述算法，關(guān)鍵之處給出注釋。說明你所設(shè)計算法的時間簡單度和空間簡單度。五、算法設(shè)計題32、設(shè)二叉樹用二指針構(gòu)造存儲〔可以是動態(tài)存儲構(gòu)造〕，元素值為整數(shù)，且元素值無重復(fù)，請編寫子程序，求出以元素值等于某個給定的整數(shù)的結(jié)點(diǎn)為根的子樹中的各個葉結(jié)點(diǎn)。33、按圖的寬度優(yōu)先搜尋法寫一算法判別以鄰接矩陣存儲的有向圖中是否存在由頂點(diǎn)Vij到頂點(diǎn)V的路徑(i≠j)j34、試編寫在帶頭結(jié)點(diǎn)的單鏈表中刪除〔一個〕最小值結(jié)點(diǎn)的〔高效〕算法delete〔Linklist&L〕。35、設(shè)鍵盤輸入n個英語單詞，輸入格式為n，w1，w2，…，wn，其中n表示隨后輸入英語單詞個數(shù)，試編一程序，建立一個單向鏈表，實(shí)現(xiàn)：假設(shè)單詞重復(fù)消滅，則只在鏈表上保存一個。除滿足〔1〕的要求外。鏈表結(jié)點(diǎn)還應(yīng)有一個計數(shù)域，記錄該單詞重復(fù)消滅的次數(shù)，然后輸出消滅次數(shù)最多的前k〔k<=n〕個單詞。參考答案一、選擇題1、【答案】A2、【答案】A3、【答案】A4、【答案】D5、【答案】C6、【答案】A7、【答案】A8、【答案】C9、【答案】D10、【答案】C二、填空題11、【答案】p!=NULL//鏈表未到尾就始終進(jìn)展q//將當(dāng)前結(jié)點(diǎn)作為頭結(jié)點(diǎn)后的第一元素結(jié)點(diǎn)插入12、【答案】n(n-1)/213、【答案】node->rflag==0；*x=bt；*x=node->right；prior〔t，x〕14、【答案】free〔T〕；q&&q->data!=A；q=q->rchild；p->lchild=null；p->rchild=null15、【答案】2；4；3【解析】二分法查找元素次數(shù)列表查100115就停頓了。16、【答案】〔rear+1〕%〔n-m+1〕==frontstack[tp]=t；p=stack[tp--]；p；++tp【解析】此題主要使用堆棧完成了二叉樹左右子樹交換的操作。首先根結(jié)點(diǎn)進(jìn)棧，然后推斷棧是否為空，假設(shè)不為空，則取棧頂元素，交換取出結(jié)點(diǎn)的左右指針。并將左右指針分別進(jìn)棧，重復(fù)這一操作。完成二叉樹左右孩子的交換。18、【答案】23；100CH三、推斷題19、【答案】×20、【答案】√21、【答案】√22、【答案】×23、【答案】×24、【答案】√25、【答案】√26、【答案】×27、【答案】√28、【答案】×四、簡答題29、答：〔1〕依據(jù)二叉樹中度2的結(jié)點(diǎn)個數(shù)等于葉結(jié)1的性質(zhì)n個葉結(jié)點(diǎn)且非葉子結(jié)點(diǎn)均有左子樹的二叉樹的結(jié)2n-1?！?〕證明：當(dāng)i=1時，2-〔1-1〕=20=1，公式成立。設(shè)i=n-1時公式成立，證明當(dāng)i=n時公式仍成立。設(shè)某葉結(jié)點(diǎn)的層號t，當(dāng)將該結(jié)點(diǎn)變?yōu)閮?nèi)部結(jié)點(diǎn)，從而再增加兩個葉結(jié)點(diǎn)時這兩個葉結(jié)點(diǎn)的層號都是t+1，對于公式的變化，是削減了一個原來的葉結(jié)點(diǎn)，增加了兩個葉結(jié)點(diǎn)，反映到公式中，由于2-〔t-1〕=2-〔t+1-1〕+2-〔t+1-1〕，所以結(jié)果不變，這就證明當(dāng)i=n時公式仍成立。證畢。30、答：〔1〕判定樹如下圖：假設(shè)查5430、63、42、54比較，查找成功。假設(shè)查9030、63、87、95比較，查找失敗。〔4〕31、答：〔1〕算法的策略是從前向后掃描數(shù)組元素，標(biāo)記出一個可能成為主元素的元素Num。然后重計數(shù)，確Num是否是主元素。算法可分為以下兩步：①選取候選的主元素：依次掃描所給數(shù)組Num保存c中，Num的消滅次數(shù)1Num，則計1，否則計1；當(dāng)計