模擬題數(shù)據(jù)結(jié)構(gòu)與算法

XXXX-XXXX年第X學(xué)期期末趣XXXX-XXXX年第X學(xué)期期末趣X 裝 訂 線 系(院)：專業(yè)：姓名：學(xué)號(hào)：數(shù)學(xué)與計(jì)算機(jī)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)軟件專業(yè)XXXX級(jí)本斗課程考核試卷考試時(shí)間：120分鐘考試方式：閉卷（提示：答案必須依試題順序做在答題冊(cè)上，并標(biāo)明大、小題號(hào)，否則不予計(jì)分）一、選擇題（每小題2分，共30分）1、順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（ ）表示的。線性結(jié)構(gòu) B.非線性結(jié)構(gòu) C.存儲(chǔ)位置 D.指針2、算法指的是（ ）。對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。計(jì)算機(jī)程序 C.解決問(wèn)題的計(jì)算方法 D.數(shù)據(jù)處理3、線性表是具有n個(gè)（ ）的有限序列。表元素 B.字符C.數(shù)據(jù)元素 D.數(shù)據(jù)項(xiàng) E.信息項(xiàng)4、線性表采用鏈接存儲(chǔ)時(shí)，其地址（ ）。A.必須是連續(xù)的 B.部分地址必須是連續(xù)的一定是不連續(xù)的 D.連續(xù)與否均可以5、一個(gè)隊(duì)列的入隊(duì)順序是1，2，3，4，則隊(duì)列的輸出順序是（ ）。A.4321B.1234C.1432D.32416、 假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素，其頭尾指針?lè)謩e為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（）。A．（rear-front+m）%m B．rear-front+1C．（front-rear+m）%m D．（rear-front）%mTOC\o"1-5"\h\z7、串的長(zhǎng)度是指（ ）A?串中所含不同字母的個(gè)數(shù)B.串中所含字符的個(gè)數(shù)C.串中所含不同字符的個(gè)數(shù) D.串中所含非空格字符的個(gè)數(shù)8、設(shè)有兩個(gè)串p和q,其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（ ）。A.求子串 B.聯(lián)接 C.匹配 D.求串長(zhǎng)9、 具有10個(gè)葉結(jié)點(diǎn)的二叉樹(shù)中有（）個(gè)度為2的結(jié)點(diǎn)。A．8 B．9 C．10 D．ll10、 設(shè)森林中有4棵樹(shù)，樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)依次為nl、n2、n3、n4,則把森林轉(zhuǎn)換成二叉樹(shù)后，其根結(jié)點(diǎn)的右子樹(shù)上有（）個(gè)結(jié)點(diǎn)。A. n1-1 B.n1C. n1+n2+n3 D.n2+n3+n411、 在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（）倍。A.1/2 B.1 C.2 D.412、下面關(guān)于工程計(jì)劃的AOE網(wǎng)的敘述中，不正確的是（ ）關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成所有的關(guān)鍵活動(dòng)都提前完成，那么整個(gè)工程將會(huì)提前完成某些關(guān)鍵活動(dòng)若提前完成，那么整個(gè)工程可能會(huì)提前完成13．已知數(shù)據(jù)元素為（34，76，45，18，26，54，92，65），按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)，則該樹(shù)的深度為（）。A.4 B.5 C.6 D.714、下面關(guān)于折半查找的敘述正確的是（ ）。長(zhǎng)江師范學(xué)院課程考核試卷表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ)表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型表必須有序，而且只能從小到大排列表必須有序，且表只能以順序方式存儲(chǔ)15、一組記錄的關(guān)鍵碼為{46,79,56,38,40,84}，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（）。A.{40,38,46,56,79,84} B.{40,38,46,79,56,84}C.{40,38,46,84,56,79} D.{84,79,56,46,40,38}二、 判斷（對(duì)的打“J”錯(cuò)的打“X”，每小題1.5分，共9分）TOC\o"1-5"\h\z1、每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本操作：插入、刪除和查找。（ ）2、線性表的邏輯順序和存儲(chǔ)順序總是一致的。（ ）3、線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。（ ）4、 若輸入序列為1,2,3,4,5,6,則通過(guò)一個(gè)?？梢暂敵鲂蛄?,2,5,6,4,1.（ ）5、空串與空格串是相同的。（ ）6、一個(gè)有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)個(gè)數(shù)一定相等。（ ）三、 填空題（每空1分，共25分）1、 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為 、 、 和 。2、 數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是 、 。3、在單鏈表L中，指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是： 。4、在一個(gè)長(zhǎng)度為n的順序表的第i（1<i<n+1）個(gè)元素之前插入一個(gè)元素，需向后移動(dòng) 個(gè)元素，刪除第i（l<i<n）個(gè)元素時(shí)，需向前移動(dòng) 個(gè)元素。5、 設(shè)有一個(gè)空棧（每個(gè)元素占2個(gè)字節(jié)），棧頂指針為1000H,現(xiàn)有輸入序列為1、2、3、4、5，經(jīng)過(guò)push，push，pop,push，pop,push，push后，輸出序列是 ，棧頂指針為 。6、串是一種特殊的線性表，其特殊性體現(xiàn)在__ 。7、兩個(gè)串相等的充分必要條件是_ 、 。8、一棵二叉樹(shù)的第i（Al）層最多有—個(gè)結(jié)點(diǎn)；一棵有n（n>0）個(gè)結(jié)點(diǎn)的滿二叉樹(shù)共有 個(gè)葉子結(jié)點(diǎn)和__個(gè)非終端結(jié)點(diǎn)。9、在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有 個(gè)指針域，其中 個(gè)指針域用于指向其左右孩子，剩下的—個(gè)指針域則是空的。10、 設(shè)無(wú)向圖G中頂點(diǎn)數(shù)為n,至多有 條邊；若G為有向圖，至多有 條弧。11、 圖的存儲(chǔ)結(jié)構(gòu)主要有兩種，分別是 和 。12、 設(shè)有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},請(qǐng)寫(xiě)出按2路歸并排序方法對(duì)該序列進(jìn)行一趟掃描后的結(jié)果 。四、設(shè)有數(shù)據(jù)結(jié)構(gòu)（D,R）,其中D={1,2,3,4,5,6}，R={v1,2>,v2,3>,v2,4>,v3,4>,v3,5>,v3,6>,v4,5>,v4,6>}。試畫(huà)出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)。（5分）五、將下面圖1所示的樹(shù)轉(zhuǎn)換為二叉樹(shù)，圖2所示的二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林。（6分）AABGBDFEG

AABGBDFEG數(shù)學(xué)與計(jì)算機(jī)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)軟件專業(yè)XXXX級(jí)本斗XXXX-XXXX年第X學(xué)期期末趣X圖XXXX-XXXX年第X學(xué)期期末趣X七、圖3所示是一個(gè)無(wú)向帶權(quán)圖,六、對(duì)給定的一組權(quán)值W=(5,2,9,11,8,3,7),試構(gòu)造相應(yīng)的哈夫曼樹(shù)，并計(jì)算它的帶權(quán)路徑長(zhǎng)度，并寫(xiě)出各個(gè)權(quán)對(duì)應(yīng)的哈夫曼編碼。(6七、圖3所示是一個(gè)無(wú)向帶權(quán)圖,八、 設(shè)散列函數(shù)hashf(x)=xmod11,散列表的地址空間為0-10,現(xiàn)要把數(shù)據(jù)：1,13,12,34,38,33,27,22插入到散列表中。(6分)(1)使用線性探