2022年杭州師范大學(xué)計算機科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A(有答案)

2022年杭州師范大學(xué)計算機科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A（有答案）一、選擇題1、將線性表的數(shù)據(jù)元素進行擴充，允許帶結(jié)構(gòu)的線性表是（）。A.串B.樹C.廣義表D.棧2、從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在已排序序列的合適位置，該排序方法稱為（）排序法。A.插入B.選擇C.希爾D.二路歸并3、連續(xù)存儲設(shè)計時，存儲單元的地址（）。A.一定連續(xù)B.一定不連續(xù)C.不一定連續(xù)D.部分連續(xù)，部分不連續(xù)4、下面關(guān)于串的敘述中，不正確的是（）。A.串是字符的有限序列B.空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運算D.串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?、動態(tài)存儲管理系統(tǒng)中，通?？捎校ǎ┓N不同的分配策略。A.1B.2C.3D.46、排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束時都至少能夠確定一個元素最終位置的方法是（）。Ⅰ．簡單選擇排序Ⅱ．希爾排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路歸并排序A．僅Ⅰ、Ⅲ、ⅣB．僅Ⅰ、Ⅱ、ⅢC．僅Ⅱ、Ⅲ、ⅣD．僅Ⅲ、Ⅳ、Ⅴ7、已知關(guān)鍵字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關(guān)鍵字3，調(diào)整后的小根堆是（）。A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，198、已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，則后序遍歷結(jié)果為（）。A.CBEFDAB.FEDCBAC.CBEDFAD.不定9、在下述結(jié)論中，正確的有（）。①只有一個結(jié)點的二叉樹的度為0。②二叉樹的度為2。③二叉樹的左右子樹可任意交換。④深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。A.①②③B.⑦③④C.②④D.①④10、下面關(guān)于B和B+樹的敘述中，不正確的是（）A.B樹和B+樹都是平衡的多叉樹B.B樹和B+樹都可用于文件的索引結(jié)構(gòu)C.B樹和B+樹都能有效地支持順序檢索D.B樹和B+樹都能有效地支持隨機檢索二、填空題11、分別采用堆排序，快速排序，起泡排序和歸并排序，對初態(tài)為有序的表，則最省時間的是______算法，最費時間的是______算法。12、起始地址為480，大小為8的塊，其伙伴塊的起始地址是______；若塊大小為32，則其伙伴塊的起始地址為______。13、文件由______組成；記錄由______組成。14、設(shè)T是一棵結(jié)點值為整數(shù)的二叉排序樹，A是一個任意給定的整數(shù)。在下面的算法中，free_tree（T）在對二叉排序樹丁進行后序遍歷時釋放二又排序樹T的所有結(jié)點；delete_subtree（T，A），首先在二叉排序樹T中查找值為A的結(jié)點，根據(jù)查找情況分別進行如下處理：（1）若找不到值為A的結(jié)點，則返回根結(jié)點的地址（2）若找到值為A的結(jié)點，則刪除以此結(jié)點為根的子樹，并釋放此子樹中的所有結(jié)點，若值為A的結(jié)點是查找樹的根結(jié)點，刪除后變成空的二叉樹，則返null；否則返回根結(jié)點的地址。15、數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是______。16、當(dāng)兩個棧共享一存儲區(qū)時，棧利用一維數(shù)組stack（1，n）表示，兩棧頂指針為top[1]與top[2]，則當(dāng)棧1空時，top[1]為______，棧2空時，top[2]為______，棧滿時為______。17、設(shè)廣義表L=（（），（）），則head（L）是______；tail（L）是______；L的長度是______；深度是______。18、設(shè)有一個空棧，棧頂指針為1000H（十六進制），現(xiàn)有輸入序列為l，2，3，4，5，經(jīng)過PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，輸出序列是______，而棧頂指針值是______。設(shè)棧為順序棧，每個元素占4個字節(jié)。三、判斷題19、對磁帶機而言，ISAM是一種方便的文件組織方法（）20、倒排文件是對次關(guān)鍵字建立索引。（）21、KMP算法的特點是在模式匹配時指示主串的指針不會變小。（）22、稀疏矩陣壓縮存儲后，必會失去隨機存取功能。（）23、一般來說，若深度為k的n個結(jié)點的二叉樹只有最小路徑長度，那么從根結(jié)點到第k-1層具有的最多結(jié)點數(shù)為2k-1-1，余下的n-2k-1+1個結(jié)點在第k層的任一位置上。（）24、一棵樹中的葉子數(shù)一定等于與其對應(yīng)的二叉樹的葉子數(shù)。（）25、在任何情況下，歸并排序都比簡單插入排序快。（）26、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）27、有向圖中頂點V度等于其鄰接矩陣中第V行中的1的個數(shù)。（）28、對大小均為n的有序表和無序表分別進行順序查找，在等概率查找的情況下，對于查找成功，它們的平均查找長度是相同的，而對于查找失敗，它們的平均查找長度是不同的。（）四、簡答題29、設(shè)有n個元素采用起泡排序法進行排序，通常需要進行多少趟排序?對于第J趟起泡通常需要進行多少次關(guān)鍵字比較?在程序設(shè)計中如何設(shè)置判斷條件，有可能使起泡趟數(shù)可以減少并且能完成排序。30、s是字符數(shù)組，s[0]中存放的是該字符串的有效長度，假設(shè)s[1..7]中字符串的內(nèi)容為"abcabaa"，說明下列程序的功能及執(zhí)行結(jié)果。31、設(shè)二叉樹BT的存儲結(jié)構(gòu)如表：其中BT為樹根結(jié)點的指針，其值為6，Lchild、Rchild分別為結(jié)點的左、右孩子指針域data為結(jié)點的數(shù)據(jù)域。試完成下列各題：（1）畫出二叉樹BT邏輯結(jié)構(gòu)。（2）寫出按前序、中序、后序遍歷該二叉樹所得到的結(jié)點序列。（3）畫出二叉樹的后序線索樹。五、算法設(shè)計題32、按圖的寬度優(yōu)先搜索法寫一算法判別以鄰接矩陣存儲的有向圖中是否存在由頂點Vi到頂點Vj的路徑(i≠j)33、結(jié)點類型和存儲結(jié)構(gòu)如下：試設(shè)計一個排序算法，要求不移動結(jié)點的存儲位置，只在結(jié)點的count字段記錄結(jié)點在排序中的序號，并將排序結(jié)果按升序輸出。34、編寫程序，統(tǒng)計在輸入字符串中各個不同字符出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為A～Z這26個字母和0～9這10個數(shù)字）。35、試為二叉樹寫出一個建立三叉鏈表的算法，并在此三叉鏈表中刪去每一個元素值為x的結(jié)點，以及以它為根的子樹，且釋放相應(yīng)存儲空間。二叉樹的三叉鏈表的描述為：

參考答案一、選擇題1、【答案】C2、【答案】A3、【答案】A4、【答案】B5、【答案】C6、【答案】A7、【答案】A8、【答案】A9、【答案】D10、【答案】C二、填空題11、【答案】起泡；快速12、【答案】480+8=488；480-32=44813、【答案】記錄；數(shù)據(jù)項14、【答案】free（T）；q&&q->data!=A；q=q->rchild；p->lchild=null；p->rchild=null15、【答案】算法的時間復(fù)雜度和空間復(fù)雜度16、【答案】0；n+1；top[1]+1=top[2]17、【答案】（）；（（））；2；218、【答案】23；100CH三、判斷題19、【答案】×20、【答案】√21、【答案】√22、【答案】√23、【答案】√24、【答案】×25、【答案】×26、【答案】×27、【答案】×28、【答案】√四、簡答題29、答：n個元素采用起泡排序法進行排序，通常需要進行n-1趟排序。第j趟起泡排序要進行n-j次比較。在一趟排序中，若沒有記錄交換，則表示排序完成。因而，可通過設(shè)標(biāo)記來控制排序結(jié)束，下面語句段說明了標(biāo)記flag的使用。30、答：本程序的功能是求字符串的nextva