重慶郵電大學數(shù)據(jù)結構(11)

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

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 設循環(huán)隊列中數(shù)組的下標范圍是0, ., m 1，其頭指針front 指向隊首元素，rear指向隊尾元素，則隊列的長度為()。A(rearfront1)(m 1)B(rearfrontm+1)mC rear frontD rear front 1.4 設計一個十進制轉換為八進制的算法

3、，采用()數(shù)據(jù)結構最佳。A. 棧B. 隊列D. 鏈式結構線性表C. 順序結構線性表5若某個棧的輸入序列為1,2, 3,n,輸出序列的第一個元素為n,則第i 個輸出元素為() 。A. i B. n-iC. n-i+1D. 哪個元素無所謂.6 六個元素按6， 5， 4， 3， 2， 1 的順序進棧，下列哪個出棧序列是錯誤的()。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.空或只有一個結點C.任一結點無左孩子.8 高度為 k 的完全二叉樹至少有(A 2k-1C2k-

4、1B 高度等于其結點數(shù)D 任一結點無右孩子)個結點(空樹高度為0)B. 2kD. k.9 設高度為h 的二叉樹上只有度為0 和度為 2 的結點，則此二叉樹中至多有( )個結點。A. 2h-1B. 2h-1C. 2h+1D. 2h+1-1精品文檔，歡迎下載!重慶郵電大學2018年攻讀碩士學位研究生入學考試試題。數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8,列下標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；所有鄰接表中的結點總數(shù)是（）。A. e/2 B.eC.2e D.n+e3 設結點x和結點y是二叉樹T中的任意兩個結點，若在先序序列中x在y之前，而在后序序列中x在y之后，則x和y的關系是（）A. x是y的左兄弟B. x是y的右兄弟C. x是y的祖先D. x是y的后代4 關于下面的圖形，哪個說法正確（）。A.路徑 <1,2>, <2, 4>, <4, 1> 是一條回路；B頂點2的入度為2;C頂點4的出度為2;D以上皆非。5 下

6、列序列中，（）是執(zhí)行第一趟快速排序后得到的序列（排序的關鍵 字類型是字符串）。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中每個元素距其最終位置不遠，則采用 排序算法最節(jié)省時間。3圖G是一個非連通圖，共有28條邊，則該圖至少有 個頂點。4設一循環(huán)隊列Q中，rear指針指向隊尾元素的下一個位置，

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

8、樹的先序序列和中序序列分別為 ABDGCEFH和DGBAECHF :(1)畫出該二叉樹；(2)寫出此二叉樹的后序序列；(3)畫出與此二叉樹對應的森林。2.圖G各頂點的連接關系及相應權值如下圖所示：(1)畫出圖的鄰接矩陣存儲圖示；(2)從頂點1開始對圖進行廣度優(yōu)先遍歷，寫出遍歷結果；(3)使用Kruskal算法求該圖的最小生成樹，給出形成過程3.設散列表的長度為8,散列函數(shù)H(k)=k mod 7 ,初始記錄關鍵字序列為(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>若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序 號從小到大的次序鏈接的，重慶郵電大學2018年攻讀碩士學位研究生入學考試試題(1)畫出該圖的鄰接表存儲圖示；(2)按拓樸排序算法進行排序，試給出得到的拓樸排序的序列。5 .假設一個線性鏈表的類名為linkedLi

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

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

12、葉子結點個數(shù)。有關的數(shù)據(jù)結構已描述如下：typedef struct /二叉樹結點int data;Binary_node *left;Binary_node *right;Binary_node, *Binary_tree;int LeftCount (Binary_tree bt)； 計算樹 bt的葉結點的個數(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)對于下面給出