2001年混合班99數(shù)據(jù)結(jié)構(gòu)與算法試卷

1、2001年混合班99“數(shù)據(jù)結(jié)構(gòu)與算法”試卷考試時(shí)間：2小時(shí)10分一、 單項(xiàng)選擇及填空題（除非特別注明，一般每小題2分，共38分，請(qǐng)選擇題答案寫(xiě)在試卷左邊）1 若語(yǔ)句S的執(zhí)行時(shí)間為O（1），那么下列程序段的時(shí)間復(fù)雜度為：for(i=0; i<n; i+)for(j=0; j<=i; j+)S;A) O(n) B) O(n*n) C) O(nlogn) D) O(n*i)2 已知一堆棧的進(jìn)棧序列為：1234，則下列哪個(gè)序列為不可能的出棧序列：A）1234 B）4321 C）2143 D）41233 深度為5的二叉樹(shù)至多有_個(gè)結(jié)點(diǎn).A) 16 B) 32 C）31 D) 104 堆(HE

2、AP)是一種_A) 二叉樹(shù) B) 線(xiàn)性表 C) 圖 D) 算法5 若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？A） 1和5 B）2和4 C）4和2 D）5和16 下列哪種排序算法的平均時(shí)間復(fù)雜度為O（nlogn）：A） 簡(jiǎn)單選擇排序 B）簡(jiǎn)單插入排序 C）冒泡排序 D）歸并排序7 用冒泡排序（交換排序）算法對(duì)下列數(shù)據(jù)進(jìn)行從小到大排序。在將最大的數(shù)“沉”到最后時(shí)，數(shù)據(jù)的順序是什么？ 12 37 42 19 27 35 56 42 10A） 12 37 42 19 27 35 44

3、10 56B） 12 37 42 19 27 35 10 44 56C） 12 37 19 27 35 42 44 10 56D） 10 12 19 27 35 37 42 44 568 下列哪種排序算法更適合于外部排序A） 選擇排序 B）插入排序 C）冒泡排序 D）歸并排序9 數(shù)據(jù)結(jié)構(gòu)中的DIJKSTRA方法是用來(lái)求:A) 關(guān)鍵路徑 B) 最短路徑 C) 拓?fù)渑判?D) 字符串匹配10 對(duì)下列二叉樹(shù)進(jìn)行后序遍歷，其遍歷結(jié)果為： a b c d e f gA) gfedcba B) dbegfca C) bdecgfa D) dbaecgf11稀疏矩陣（SPARSE MATRIX）一般的壓縮存

4、儲(chǔ)方法有以下兩種：A）二維數(shù)組和三維數(shù)組 B）三元組（TRIPES）和哈希表（HASH TABLE）C）三元組（TRIPES）和十字鏈表（cross linked） D）哈希表和十字鏈表12 在待排序的元素基本有序的前提下，效率最高的排序方法是：A）簡(jiǎn)單插入排序 B）簡(jiǎn)單選擇排序 C）快速排序 D）歸并排序13 設(shè)以單向鏈表方式表示一個(gè)多項(xiàng)式（按指數(shù)expon遞減方式）,請(qǐng)寫(xiě)出鏈表中節(jié)點(diǎn)結(jié)構(gòu)的C語(yǔ)言定義并對(duì)其中分量的用途作簡(jiǎn)要注釋?zhuān)?4（4分）在簡(jiǎn)單插入排序、希爾排序、簡(jiǎn)單選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，排序是不穩(wěn)定的有：_15（4分）請(qǐng)至少給出三種常用的算法設(shè)計(jì)方法并各給出

5、對(duì)應(yīng)的一個(gè)例子 _16（4分）按滿(mǎn)二叉數(shù)的概念可推廣出滿(mǎn)K叉數(shù)的概念。若對(duì)滿(mǎn)K叉樹(shù)的節(jié)點(diǎn)逐層編號(hào)（從1開(kāi)始，同層中從左到右），則編號(hào)為i的節(jié)點(diǎn)的父節(jié)點(diǎn)編號(hào)是_，編號(hào)為i的節(jié)點(diǎn)的第j個(gè)兒子的編號(hào)是_。二、請(qǐng)對(duì)下列有向圖（共9分）：（1） 畫(huà)出相應(yīng)鄰接鏈表（adjacency list）表示法（鏈表中，按節(jié)點(diǎn)編號(hào)大小從小到大向后排），（2） 指出按教材中TOPSORT算法在上述表示的基礎(chǔ)上進(jìn)行遍歷的輸出結(jié)果。三、（8分）對(duì)于下列二叉樹(shù)（1） 請(qǐng)畫(huà)出其對(duì)應(yīng)的中序線(xiàn)索（thread）（2） 請(qǐng)將下列用于中序線(xiàn)索二叉樹(shù)遍歷的程序的空白部分填上。threaded_pointer insucc( threa

6、ded_pointer tree) threaded_pointer temp; temp = tree->right_child; if ( !tree->right_thread )while( _ )temp = temp->left_child; return temp;void tinorder ( threaded_pointer tree) threaded_pointer temp=tree; for(; ;)temp = insucc (temp);if (_) break;printf ("%3c", temp->data); 四

7、、（8分）選取哈希函數(shù)H(k)=k mod 11, 用線(xiàn)性探測(cè)（linear probing）沖突解決策略(H(k)+i)%11. 試在0-10的哈希地址空間中對(duì)關(guān)鍵字序列(22,41,53,46,30,13,01,67)構(gòu)造哈希表, 并求等概率情況下查找成功與不成功的平均查找長(zhǎng)度。五、（9分）下面是將刪除最大堆(MAX HEAP)堆頂元素的算法，請(qǐng)將空白部分填上：element delete_max_heap(int *n) int parent,child; element item, temp; if (HEAP_EMPTY(*n) fprintf (stderr, "The

8、heap is emptyn"); exit (1); item = heap1; temp = heap_ ; parent = 1; child = 2; while (child <=*n) if (child < *n) && (heapchild.key< heapchild+1.key) _; if (temp.key >= heapchild.key) break; heapparent = _; parent = child; child* = 2; heap parent = temp; return item;六、 （8分）Deap是將最小堆作為左子樹(shù)、最大堆作為右子樹(shù)的堆。在Deap中要求最小堆中任何元素i的值均小于等于最大堆中對(duì)應(yīng)元素j（按教材中定義）的值。（1） 請(qǐng)寫(xiě)出i和j間的函數(shù)關(guān)