重慶郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)(11)

1、精品文檔，歡迎下載！重慶郵電大學(xué)2018年攻讀碩士學(xué)位研究生入學(xué)考試試題機密啟用前重慶郵電大學(xué)2018年攻讀碩士學(xué)位研究生入學(xué)考試試題科目名稱：數(shù)據(jù)結(jié)構(gòu)科目代碼：802考生注意事項1、答題前，考生必須在答題紙指定位置上填寫考生姓名、報考 單位和考生編號。2、所有答案必須寫在答題紙上，寫在其他地方無效。3、填（書）寫必須使用0.5mm黑色簽字筆。4、考試結(jié)束，將答題紙和試題一并裝入試卷袋中交回。5、本試題滿分150分，考試時間3小時。重慶郵電大學(xué)2018 年攻讀碩士學(xué)位研究生入學(xué)考試試題15 小題，每小題2 分，共 30 分).1 下面程序段的時間復(fù)雜度是(注： 所有答案必須寫在答題紙上，試卷上

2、作答無效！第 3 頁(共 6 頁)i = 1; while(i< = n)i = iX3；A.O(n) B. O(nlog(n) C. O(log(n)D. O(log3n).2 在 n 個元素的順序表中插入或刪除一個元素，需要平均移動表中()個元素。A.(n) B. (n/2)C. (n2)D. (1).3 設(shè)循環(huán)隊列中數(shù)組的下標(biāo)范圍是0, ., m 1，其頭指針front 指向隊首元素，rear指向隊尾元素，則隊列的長度為()。A(rearfront1)(m 1)B(rearfrontm+1)mC rear frontD rear front 1.4 設(shè)計一個十進(jìn)制轉(zhuǎn)換為八進(jìn)制的算法

3、，采用()數(shù)據(jù)結(jié)構(gòu)最佳。A. 棧B. 隊列D. 鏈?zhǔn)浇Y(jié)構(gòu)線性表C. 順序結(jié)構(gòu)線性表5若某個棧的輸入序列為1,2, 3,n,輸出序列的第一個元素為n,則第i 個輸出元素為() 。A. i B. n-iC. n-i+1D. 哪個元素?zé)o所謂.6 六個元素按6， 5， 4， 3， 2， 1 的順序進(jìn)棧，下列哪個出棧序列是錯誤的()。A 5 4 3 6 1 2B 4 5 3 1 2 6C 3 4 6 5 2 1D 2 3 4 1 5 6.7 某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是()二叉樹。A.空或只有一個結(jié)點C.任一結(jié)點無左孩子.8 高度為 k 的完全二叉樹至少有(A 2k-1C2k-

4、1B 高度等于其結(jié)點數(shù)D 任一結(jié)點無右孩子)個結(jié)點(空樹高度為0)B. 2kD. k.9 設(shè)高度為h 的二叉樹上只有度為0 和度為 2 的結(jié)點，則此二叉樹中至多有( )個結(jié)點。A. 2h-1B. 2h-1C. 2h+1D. 2h+1-1精品文檔，歡迎下載!重慶郵電大學(xué)2018年攻讀碩士學(xué)位研究生入學(xué)考試試題。數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j 從1至U 10,從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行優(yōu)先存放 時，元素A85的起始地址為（）。A. SA+141B. SA+222C. SA+144D. SA+2251任何一個無向連通圖的最小生成樹（）。A.有一棵或

5、多棵B. 一定只有一棵C. 一定有多棵D.可能不存在2 對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭 向量的大小為n；所有鄰接表中的結(jié)點總數(shù)是（）。A. e/2 B.eC.2e D.n+e3 設(shè)結(jié)點x和結(jié)點y是二叉樹T中的任意兩個結(jié)點，若在先序序列中x在y之前，而在后序序列中x在y之后，則x和y的關(guān)系是（）A. x是y的左兄弟B. x是y的右兄弟C. x是y的祖先D. x是y的后代4 關(guān)于下面的圖形，哪個說法正確（）。A.路徑 <1,2>, <2, 4>, <4, 1> 是一條回路；B頂點2的入度為2;C頂點4的出度為2;D以上皆非。5 下

6、列序列中，（）是執(zhí)行第一趟快速排序后得到的序列（排序的關(guān)鍵 字類型是字符串）。A.da,ax,eb,de,bb ff ha,gcB.cd,eb,ax,da ff ha,gc,bbC.gc,ax,eb,cd,bb ff da,haD.ax,bb,cd,da ff eb,gc,ha二、填空題（本大題共10小題，每小題3分，共30分）1采用順序查找方法查找長度為n的線性表時，在等概率情況下查找成功的 平均查找長度為。2已知數(shù)據(jù)表A中每個元素距其最終位置不遠(yuǎn)，則采用 排序算法最節(jié)省時間。3圖G是一個非連通圖，共有28條邊，則該圖至少有 個頂點。4設(shè)一循環(huán)隊列Q中，rear指針指向隊尾元素的下一個位置，

7、front指針指 向隊首元素，則判斷隊列中元素為空的條件是 。重慶郵電大學(xué)2018年攻讀碩士學(xué)位研究生入學(xué)考試試題5在大根堆中，關(guān)鍵字最小的元素可能存放在堆的任一 結(jié)點上。6 某后綴表達(dá)式為 abcd-*+ef/-,令 a=2, b=3, c=4, d=5, e=6, f=2,則該表達(dá) 式的值等于。7有n個頂點的連通圖用鄰接矩陣表示時，該矩陣至少有 個非零元素。8高度(空樹高度為0)為5的AVL樹，其結(jié)點數(shù)最少是 。9 .廣義表(a), (b), c), (d)的長度是,深度是。10 .在有n個結(jié)點的二叉鏈表中，空鏈域的個數(shù)為 。三、問答題(本大題共6小題，每小題10分，共60分)1.已知二叉

8、樹的先序序列和中序序列分別為 ABDGCEFH和DGBAECHF :(1)畫出該二叉樹；(2)寫出此二叉樹的后序序列；(3)畫出與此二叉樹對應(yīng)的森林。2.圖G各頂點的連接關(guān)系及相應(yīng)權(quán)值如下圖所示：(1)畫出圖的鄰接矩陣存儲圖示；(2)從頂點1開始對圖進(jìn)行廣度優(yōu)先遍歷，寫出遍歷結(jié)果；(3)使用Kruskal算法求該圖的最小生成樹，給出形成過程3.設(shè)散列表的長度為8,散列函數(shù)H(k)=k mod 7 ,初始記錄關(guān)鍵字序列為(25, 31, 8, 27, 13, 68),要求：(1)分別給出用線性探測法和鏈地址法作為解決沖突方法的過程；(2)計算(1)中兩種解決沖突方法的平均查找長度。4.已知一個圖

9、的頂點集V和邊集E分別為：V=1,2,3,4,5,6,7;E=<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序 號從小到大的次序鏈接的，重慶郵電大學(xué)2018年攻讀碩士學(xué)位研究生入學(xué)考試試題(1)畫出該圖的鄰接表存儲圖示；(2)按拓樸排序算法進(jìn)行排序，試給出得到的拓樸排序的序列。5 .假設(shè)一個線性鏈表的類名為linkedLi

10、st,鏈表結(jié)點的類名為ListNode,它 包含兩個數(shù)據(jù)成員data和link。data存儲該結(jié)點的數(shù)據(jù)，link是鏈接指 針。下面給定一段遞歸打印一個鏈表中所有結(jié)點中數(shù)據(jù)的算法：void PrintList (ListNode *L) if (L != NULL ) printf ("%d ", L->data);PrintList ( L->link );試問此程序在什么情況下不實用？給出具體修改后的可實用的程序？6 .對于如下圖所示的AOE網(wǎng)絡(luò)，計算各活動弧的e(a)(活動a的最早開 始時間)和l(aj)(活動aj的最遲開始時間)函數(shù)值、各事件(頂點)的

11、ve(vi)(事件Vi的最早發(fā)生時間)和vl(vj)(事件Vj的最遲發(fā)生時間)函 數(shù)值；列出各條關(guān)鍵路徑。ABCEDs4tFGHJIK四、問答題(本大題共2小題，每小題15分，共30分)1 .現(xiàn)有關(guān)鍵字序列45, 24, 37, 53, 12, 93, 47, 60,按以下要求完成：1根據(jù)給定的關(guān)鍵字序列構(gòu)造一棵二叉查找(排序)樹，以二叉鏈表形 式存儲，進(jìn)行中序遍歷可以得到從小到大排列的有序序列，請寫出構(gòu) 造過程(不要求算法)。重慶郵電大學(xué)2018年攻讀碩士學(xué)位研究生入學(xué)考試試題2 在(1)的基礎(chǔ)上，請編寫一個函數(shù)(int LeafCount ( Binary_tree BT), 求此二叉樹的

12、葉子結(jié)點個數(shù)。有關(guān)的數(shù)據(jù)結(jié)構(gòu)已描述如下：typedef struct /二叉樹結(jié)點int data;Binary_node *left;Binary_node *right;Binary_node, *Binary_tree;int LeftCount (Binary_tree bt)； 計算樹 bt的葉結(jié)點的個數(shù)2下面給出一個排序算法，其中n是數(shù)據(jù)類型為Type的數(shù)組A中元素總數(shù)。void unknown (Type a , int n) int d = 1, j;while ( d < n /3 ) d = 3*d+1;while ( d > 0 ) for ( int i = d; i < n; i+ ) Type temp = ai;j = i;while ( j >= d && aj-d > temp ) aj = aj-d; j -= d; aj = temp;d /= 3;(1)閱讀此算法，說明它的功能；(2)對于下面給出