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

1、浙江大學(xué)遠(yuǎn)程教育學(xué)院試卷模擬考卷(1)課程代碼及名稱 07040320數(shù)據(jù)結(jié)構(gòu)與算法考試時(shí)間：90分鐘大題一四五總分得分閱卷人請(qǐng)保持卷面整潔，答題字跡工整。一、判斷題(共20小題，每小題1分，共20分，正確的打“”，錯(cuò)誤的打“X”。)1234567891011121314151617181920下列算法的時(shí)間復(fù)雜性是O(n2)。sum = 0;for(i=n; i=0; i-)for(j=0; j0)個(gè)結(jié)點(diǎn)的樹有n-1條邊。二叉樹中第3層結(jié)點(diǎn)數(shù)至多是4個(gè)結(jié)點(diǎn)。若用雙親表示法存儲(chǔ)樹，則無法找到結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)。滿二叉樹一定是完全二叉樹，反之亦然。5個(gè)頂點(diǎn)的無向圖最多可能有20條邊。連通圖的連通

2、分量就是它自己。有向圖各頂點(diǎn)入度之和就等于邊的數(shù)量。不連通的圖不能用深度優(yōu)先遍歷各個(gè)頂點(diǎn)。圖的生成樹包含了圖的全部頂點(diǎn)。一般來說，二分查找比順序查找快。n(n0)個(gè)結(jié)點(diǎn)的二叉排序樹至多有l(wèi)og n層。對(duì)二叉樹進(jìn)行中序遍歷得到的序列一定有序表。二叉排序樹一般用于查找某個(gè)元素。序列 12, 23, 15, 24, 26, 14, 16, 30, 27 是一個(gè)堆。二、選擇題（共20空，每空1.5分，共30分）算法分析的目的是分析算法的效率以求改進(jìn)，算法分析的兩個(gè)主要方面是。A空間復(fù)雜性和時(shí)間復(fù)雜性正確性和簡明性可讀性和文檔性數(shù)據(jù)復(fù)雜性和程序復(fù)雜性判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m）為空隊(duì)列的條件是。

3、QU-front=QU-rearQU-front!=-QU-rearQU-front=（QU-rear+1）% mQU-front!=（QU-rear+1）% m在一個(gè)單鏈表中，已知p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行s-next = p; p-next=s;B. s-next = p-next; p-next = s;C. s-next = p-next; p = s;D. p-next = s; s-next = p;數(shù)組A中，每個(gè)元素的長度為4個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址100開始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的單元素是。A. 80 B

4、. 180 C. 320D. 420在下列敘述中，正確的是 。數(shù)據(jù)的邏輯結(jié)構(gòu)要考慮數(shù)據(jù)元素本身的內(nèi)容不同類型的數(shù)據(jù)元素可以歸類到同一的邏輯結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)聯(lián)關(guān)系在數(shù)據(jù)的邏輯結(jié)構(gòu)中體現(xiàn)數(shù)據(jù)元素是數(shù)據(jù)不可分割的最小標(biāo)識(shí)單位將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí),通常需要使用 。A.棧 B.隊(duì)列 C鏈表 D樹按照二叉樹的定義，具有2個(gè)及2個(gè)以下結(jié)點(diǎn)的二叉樹有 種。A. 2 B. 3 C. 4 D. 5已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示（a） 根據(jù)有向圖的深度優(yōu)先遍歷算法，從v1頂點(diǎn)出發(fā)，所得到的頂點(diǎn)序列是，A. v1,v2,v3,v5,v4B. v1,v2,v3,v4,v5C. v1,v3,v4

5、,v5,v2D.v1,v4,v3,v5,v2（b）根據(jù)有向圖的寬度優(yōu)先遍歷算法，從v1頂點(diǎn)出發(fā)，所得到的頂點(diǎn)序列是A. v1,v2,v3,v4,v5B.v1,v3,v2,v4,v5C. v1,v2,v3,v5,v4D.v1,v4,v3,v5,v2如果某二叉樹的前序?yàn)閟tuwv，中序?yàn)閡wtvs，那么該二叉樹的后序。A. uwvtsvwuts C. wutsv D. wuvts在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要 條邊。A. n B. n+1 C. n/2 D. n-1串是一種特殊的線性表，其特殊性體現(xiàn)在。只能順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈接存儲(chǔ)D.數(shù)據(jù)元素可以是多個(gè)字

6、符在循環(huán)雙鏈表的p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作 。p-right=s;s-left=p;p-right-left=s;s-right=p-right;p-right=s;p-right-left=s;s-left=p;s-right=p-right;s-left=p;s-right=p-right;p-right=s;p-right-left=s;s-left=p;s-right=p-right; p-right-left=s;p-right=s; 快速排序方法在情況下最不利于發(fā)揮其長處。A.要排序的數(shù)據(jù)量太大B.要排序的數(shù)據(jù)中含有多個(gè)值C.要排序的數(shù)據(jù)已基本有序D.要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)

7、在待排序的元素序列基本有序的前提下，效率最高的排序方法。A.插入排序B,選擇排序C.快速排序 D.歸并排序用某種排序方法對(duì)線性表(25，84, 21，47, 15，27, 68, 35，20)進(jìn)行排序時(shí)，元素序列的 變化情況如下，則采用的排序方法是。(1)25，84，21，47，15，27，68，35，20(2)20，15，21，25，47，27，68，35，84(3)15，20，21，25，35，27，47，68，84(4)15，20，21，25，27，35，47，68，84A.選擇排序 B.希爾排序C.歸并排序 D.快速排序 關(guān)于圖的鄰接矩陣，下列結(jié)論 是正確的。有向圖的鄰接矩陣總是不對(duì)稱

8、的無向圖的鄰接矩陣總是不對(duì)稱的有向圖的鄰接矩陣可以是對(duì)稱的，也可以是不對(duì)稱的無向圖的鄰接矩陣可以是不對(duì)稱的，也可以是對(duì)稱的在長度為n的雙鏈表中某結(jié)點(diǎn)(已知其地址)之前，插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是。A. O(n)B. 0(1)C. O(log2n)D. O(n2)給定字符串this_is_a_string”，如果用一個(gè)字節(jié)存儲(chǔ)一個(gè)字符，那么存儲(chǔ)這個(gè)串需要(a) 位存儲(chǔ)空間，而用Huffman編碼，則只需要(b)位存儲(chǔ)空間。A. 36 B. 49C. 70 D. 128三、填空題(共19空，每空1-2分，共23分)設(shè)每個(gè)元素需要4個(gè)字節(jié)，順序存儲(chǔ)1200個(gè)元素，若首地址是2000，那么第150個(gè)

9、 元素的地址是。(每空2分)已知兩個(gè)字符串 s1=” Data structure is very useful. ” , s2= ” uct” ,那么 Strlen(s1)=, StrEmpty(s2)=, Substr(s1,9,4)=， Index(s1，s2,1)=。下列表示的圖中，共 個(gè)是樹；有個(gè)是滿二叉樹；個(gè)是完全二叉樹。下列二叉樹的中序遍歷序列是;后序遍歷序列是。（每空2分）5個(gè)頂點(diǎn)的無向圖，若要求其各個(gè)頂點(diǎn)的度都相同，則這種無向圖有 個(gè)（不考慮頂點(diǎn)的差異）。（2分）下列有向圖中，入度最大的頂點(diǎn)是 ；從v3到v2的最短簡單路徑有；包含所有頂點(diǎn)的簡單路徑有 ；有一簡單回路是如果一棵

10、完全二叉樹有26個(gè)結(jié)點(diǎn)，從上到下、從左到右對(duì)它的結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié) 點(diǎn)為1號(hào)。則該完全二叉樹有 層；葉子結(jié)點(diǎn)有 個(gè)；第8號(hào)結(jié)點(diǎn)的雙親結(jié)點(diǎn)是 號(hào)；第11號(hào)結(jié)點(diǎn)的右孩子結(jié)點(diǎn)是 號(hào)。四、綜合計(jì)算簡答題（共5小題，共27分）舉出樹結(jié)構(gòu)的兩個(gè)應(yīng)用實(shí)例，并說明樹的某個(gè)操作對(duì)應(yīng)在實(shí)例中的意義。（5分）判斷序列（16，19，10，15, 4, 23, 36, 是，請(qǐng)按照建立堆的思想把它調(diào)整為堆，20）是否為（小頂）堆？為什么？如果不 并用圖表示建堆的過程。（6分）下面遞歸函數(shù)用于在二叉排序樹T中的查找x元素。請(qǐng)?zhí)羁铡?4分)Position Find( ElementType X, SearchTree T )if ( T = NULL )return NULL;/* not found in an empty tree */if ( )return Find( X, T-Left );/* search left subtree */elseif ( X T-Element )/* if larger than root */return ;else /* if X = root */ return T; /* found */ 設(shè)將整數(shù)a、b、c、d依次進(jìn)棧，而只要棧非空，就可以將出