第一篇：2009考研數(shù)據(jù)結(jié)構(gòu)試題點(diǎn)評
2009年考研計(jì)算機(jī)專業(yè)綜合考試數(shù)據(jù)結(jié)構(gòu)試題點(diǎn)評
2009年考研計(jì)算機(jī)專業(yè)綜合考試是統(tǒng)一命題后的首次考試。本次考試統(tǒng)考科目包括四門計(jì)算機(jī)專業(yè)課：數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)組成原理、操作系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)，這四門課程合在一起稱為計(jì)算機(jī)科學(xué)專業(yè)基礎(chǔ)綜合，共150分。其中數(shù)據(jù)結(jié)構(gòu)占45分?？傮w上來看，2009年的考研數(shù)據(jù)結(jié)構(gòu)試題注重對基礎(chǔ)知識(shí)的考察。重點(diǎn)考察的是對基本知識(shí)點(diǎn)、基本概念的理解。在基礎(chǔ)題中又有拔高，重點(diǎn)考察了對基礎(chǔ)知識(shí)的應(yīng)用能力、應(yīng)變能力和實(shí)際動(dòng)手能力。題目總的來說不難，沒有出現(xiàn)超出考試大綱的題目。
下面我們對2009的考研數(shù)據(jù)結(jié)構(gòu)試題進(jìn)行簡要的點(diǎn)評。
一、單項(xiàng)選擇題，每小題2分，共80分。
單選題覆蓋了大綱列出的各章的知識(shí)點(diǎn)，主要考察對各種數(shù)據(jù)結(jié)構(gòu)、基本查找和排序算法的基本概念和特點(diǎn)的理解以及靈活運(yùn)用。1-10題是數(shù)據(jù)結(jié)構(gòu)部分的試題。
1.為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是
A.棧 B.隊(duì)列 C.樹 D.圖
點(diǎn)評：此題考察對各種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)的理解及應(yīng)用。棧的特點(diǎn)是后進(jìn)先出。隊(duì)列的特點(diǎn)是先進(jìn)先出。樹的特點(diǎn)是除根以外的結(jié)點(diǎn)有且只有唯一的前驅(qū)（雙親）。圖是最復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，它的任一結(jié)點(diǎn)都可以有多個(gè)前驅(qū)和后繼。據(jù)題意“輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)”，處理應(yīng)是先來先服務(wù)，因此答案為B。
2.設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序是bdcfeag，則棧S的容量至少是
A．1 B.2 C.3 D.4 點(diǎn)評：此題考察對棧和隊(duì)列的特點(diǎn)及基本操作的應(yīng)用。根據(jù)元素的出隊(duì)順序可知元素的進(jìn)棧、出棧順序，從而判斷棧中同時(shí)容納多少元素，得出棧的容量。因bdcfeag依次出隊(duì)，故元素的出棧順序也是這樣的，那么他們在棧中操作順序依次為：a入棧、b入棧、b出棧、c入棧、d入棧、d出棧、c出棧、e入棧、f入棧、f出棧、e出棧、a出棧、g入棧、g出棧。這其間棧中數(shù)據(jù)最多有3個(gè)。因此答案為C。
3.給定二叉樹如圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點(diǎn)的左子樹，R代表根結(jié)點(diǎn)的右子樹。若遍歷后的結(jié)點(diǎn)序列為3，7，5，6，1,2，4，則其遍歷方式是
A．LRN B.NRL C.RLN D.RNL 點(diǎn)評：此題考察對二叉樹的六種遍歷的理解及應(yīng)用。二叉樹有六種遍歷方式：先序遍歷、中序遍歷、后序遍歷。每種遍歷訪問根結(jié)點(diǎn)的順序不一樣。先序遍歷先訪問根，中序遍歷中間訪問根，后序遍歷最后訪問根。一般教材中都是先左子樹，后右子樹，但該題用另一種方式，先右子樹，后左子樹。從遍歷得到的序列中第一個(gè)遍歷出來的元素是3，可知是中序遍歷，因此答案是D。
4.下列二叉排序樹中，滿足平衡二叉樹定義的是
A．B.C.D.點(diǎn)評：此題考察對平衡二叉樹的定義的掌握，平衡二叉樹又稱AVL樹，它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差的絕對值不超過1。因此答案為B。
5.已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個(gè)葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多是
A．39 B.52 C.111 D.119 點(diǎn)評：此題考察對完全二叉樹的定義的理解及對二叉樹每層最大結(jié)點(diǎn)個(gè)數(shù)的計(jì)算。完全二叉樹第一層到倒數(shù)第二層結(jié)點(diǎn)個(gè)數(shù)均達(dá)到每層的最大值，2(i為層數(shù))，第6層有8個(gè)葉結(jié)點(diǎn)，說明這棵完全二叉樹最多7層，第6層的32個(gè)結(jié)點(diǎn)有24（32-8）結(jié)點(diǎn)有孩子結(jié)點(diǎn)，孩子結(jié)點(diǎn)最多有48個(gè)（24*2）,所以完全二叉樹的結(jié)點(diǎn)數(shù)最多為：1+2+4+8+16+32+48=111。
i-
1故答案為C。
6.將森林轉(zhuǎn)換為對應(yīng)的二叉樹，若在二叉樹中，結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)，則在原來的森林中，u和v可能具有的關(guān)系是
I．父子關(guān)系 II.兄弟關(guān)系 III.u的父結(jié)點(diǎn)與v的父結(jié)點(diǎn)是兄弟關(guān)系 A.只有II B.I和II C.I和III D.I、II和III 點(diǎn)評：此題考察森林轉(zhuǎn)化為二叉樹時(shí)結(jié)點(diǎn)之間的關(guān)系的變化。根據(jù)森林轉(zhuǎn)化為二叉樹的轉(zhuǎn)化過程可知，一個(gè)結(jié)點(diǎn)ｕ和它的第二個(gè)孩子結(jié)點(diǎn)ｖ轉(zhuǎn)化為二叉樹后就變?yōu)榻Y(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)，同一個(gè)結(jié)點(diǎn)的第一個(gè)孩子u和第三個(gè)孩子v轉(zhuǎn)化為二叉樹后也變?yōu)榻Y(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)，因此可以推出u和v在原來的森林中要么是父子關(guān)系，要么是兄弟關(guān)系。因此答案是B。
7.下列關(guān)于無向連通圖特性的敘述中，正確的是
I．所有頂點(diǎn)的度之和為偶數(shù) II.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1 III.至少有一個(gè)頂點(diǎn)的度為1 A.只有I B.只有II C.I和II D.I和III 點(diǎn)評：此題考察圖的度與邊的關(guān)系、無向連通圖特性。在圖中所有頂點(diǎn)的度之和為邊數(shù)的2倍，而連通圖中邊數(shù)不為零，所以一定是偶數(shù)。N個(gè)頂點(diǎn)的無向連通圖至少有n-1條邊，頂點(diǎn)的度至少是1。因此答案為A。
8.下列敘述中，不符合m階B樹定義要求的是
A．根節(jié)點(diǎn)最多有m棵子樹 B.所有葉結(jié)點(diǎn)都在同一層上 C．各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列 D.葉結(jié)點(diǎn)之間通過指針鏈接
點(diǎn)評：此題考察對m階B樹的定義的理解與應(yīng)用。B樹是一種多叉平衡查找樹。一棵m階的B樹，或?yàn)榭諛洌驗(yàn)闈M足下列特性的m叉樹：
①樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹；
②若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則它至少有兩棵子樹； ③除根之外的所有非葉子結(jié)點(diǎn)至少有「m/2]棵子樹；
④所有的非葉子結(jié)點(diǎn)中包含下列數(shù)據(jù)信息
(n，A0，K1，A1，K2，A2，?，Kn，An)
其中：Ki(i=1，2，?，n)為關(guān)鍵字，且Ki n+1為子樹個(gè)數(shù)） ⑤所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息(可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針為空)。據(jù)此定義可知答案為D。 9.已知關(guān)鍵序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關(guān)鍵字3，調(diào)整后得到的小根堆是 A．3，5，12，8，28，20，15，22，19 B.3，5，12，19，20，15，22，8，28 C．3，8，12，5，20，15，22，28，19 D.3，12，5，8，28，20，15，22，19 點(diǎn)評：此題考察對堆調(diào)整算法--“篩選”算法的應(yīng)用。篩選算法要求根的左右子樹必須是堆。把3插入后，關(guān)鍵序列變?yōu)?，8，12，19，28，20，15，22，3，以5為根的左右子樹的堆結(jié)構(gòu)可能被破壞，因此必須重建堆，從n/2個(gè)結(jié)點(diǎn)開始調(diào)用篩選算法，直到第一個(gè)結(jié)點(diǎn)，就可重建堆。答案為A。 10.若數(shù)據(jù)元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是 A．起泡排序 B.插入排序 C.選擇排序 D.二路歸并排序 點(diǎn)評：此題考察對各種排序方法的步驟、特點(diǎn)的理解及應(yīng)用。起泡排序第i趟結(jié)束后可以把第i大的數(shù)放到正確位置。插入排序第i趟結(jié)束后前i個(gè)元素是有序的，但不一定是這些元素的最后位置。選擇排序第i趟結(jié)束后可以把第i小的數(shù)放到正確位置。二路歸并排序第i趟結(jié)束后可以得到長度為2i 的有序子序列。故答案為B。 二、綜合應(yīng)用題 綜合應(yīng)用題主要考察綜合運(yùn)用基本知識(shí)分析問題、解決問題的能力。41-42為數(shù)據(jù)結(jié)構(gòu)部分的題。一道問答題、一道算法設(shè)計(jì)題。 41.（10分）帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩頂點(diǎn)間的距離）的最短路徑問題是找出從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑。假定從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑，現(xiàn)有一種解決該問題的方法： ①設(shè)最短路徑初始時(shí)僅包含初始頂點(diǎn)，令當(dāng)前頂點(diǎn)u為初始頂點(diǎn)； ②選擇離u最近且尚未在最短路徑中的一個(gè)頂點(diǎn)v，加入到最短路徑中，修改當(dāng)前頂點(diǎn)u=v； ③重復(fù)步驟②，直到u是目標(biāo)頂點(diǎn)時(shí)為止。 請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則，請舉例說明。點(diǎn)評：此題考察對最短路徑的理解及應(yīng)用。最短路徑就是從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的路徑上權(quán)值和最小的路徑。題目中的方法在選擇頂點(diǎn)時(shí)并沒有找到下一條權(quán)值最下的邊，所以該方法求得的路徑不一定是最短路徑。例如，對于下圖所示的帶權(quán)圖，如果按照題中的原則，從A到C的最短路徑為A→B→C，事實(shí)上其最短路徑為 A→D→C。 42.（15分）已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)結(jié)構(gòu)為 data link 假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)（k為正整數(shù)）。若查找成功，算法輸出該結(jié)點(diǎn)的data值，并返回1；否則，只返回0。要求： （1）描述算法的基本設(shè)計(jì)思想（2）描述算法的詳細(xì)實(shí)現(xiàn)步驟 （3）根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語言描述算法（使用C或C++或JAVA語言實(shí)現(xiàn)），關(guān)鍵之處請給出簡要注釋。 點(diǎn)評：此題是一道算法設(shè)計(jì)題，算法設(shè)計(jì)是數(shù)據(jù)結(jié)構(gòu)課程的一個(gè)重點(diǎn)內(nèi)容，也是一個(gè)難點(diǎn)。此題考察對單鏈表的基本運(yùn)算的理解及靈活運(yùn)用。一般教材中在單鏈表中查找結(jié)點(diǎn)都是從頭數(shù)第i個(gè)結(jié)點(diǎn)，而本題中要倒數(shù)第k個(gè)結(jié)點(diǎn)，難度就大了，要把單鏈表的基本運(yùn)算進(jìn)行改寫，關(guān)鍵在于要查倒數(shù)第K個(gè)位置上的結(jié)點(diǎn)，此時(shí)需要兩個(gè)流動(dòng)指針，一個(gè)整型變量，從鏈表頭向后遍歷，其中指針P1指向當(dāng)前遍歷的結(jié)點(diǎn)，指針P指向P1所指向結(jié)點(diǎn)的前K個(gè)結(jié)點(diǎn)，如果P1之前沒有K個(gè)結(jié)點(diǎn)，那么P指向表頭結(jié)點(diǎn)。用整型變量i表示當(dāng)前遍歷了多少結(jié)點(diǎn)，當(dāng)i>k時(shí)，指針P隨著每次遍歷，也向前移動(dòng)一個(gè)結(jié)點(diǎn)。當(dāng)遍歷完成時(shí)，P或者指向表頭就結(jié)點(diǎn)，或者指向鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)。 算法描述： int LocateElement(linklist list,int k){ P1=list->link;P=list;i=1;while(P1){ P1=P1->link;i++;if(i>k)P=P->next;//如果i>k,則p也往后移 } if(P==list)return 0;//說明鏈表沒有k個(gè)結(jié)點(diǎn) else { printf(“%dn“,P->data);return 1;} } 數(shù)據(jù)結(jié)構(gòu)試卷 （二）一、選擇題(24分)1．下面關(guān)于線性表的敘述錯(cuò)誤的是（）。 (A)線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間 (B)線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間(C)線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)(D)線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn) 2．設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹中總共有（）個(gè)空指針域。 (A)2m-1(B)2m(C)2m+1(D)4m 3．設(shè)順序循環(huán)隊(duì)列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（）。 (A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M 4．設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。 (A)BADC(B)BCDA(C)CDAB(D)CBDA 5．設(shè)某完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有（）條邊。 (A)n(n-1)/2(B)n(n-1)(C)n 2(D)n2-1 6．設(shè)某棵二叉樹中有2000個(gè)結(jié)點(diǎn)，則該二叉樹的最小高度為（）。 (A)9(B)10(C)11(D)12 7．設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對應(yīng)的鄰接表中有（）個(gè)表頭結(jié)點(diǎn)。 (A)n-1(B)n(C)n+1(D)2n-1 8．設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（）。 (A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，8 二、填空題(24分)1.1.為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問題是____________________和__________________________。 2.2.下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語句。 typedef struct {int s[100];int top;} sqstack;void push(sqstack &stack,int x){ if(stack.top==m-1)printf(“overflow”); else {____________________;_________________;} } 3.3.中序遍歷二叉排序樹所得到的序列是___________序列（填有序或無序）。4.4.快速排序的最壞時(shí)間復(fù)雜度為___________，平均時(shí)間復(fù)雜度為__________。5.5.設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為_________；若采用二叉鏈表作為該二叉樹的存儲(chǔ)結(jié)構(gòu)，則該二叉樹中共有_______個(gè)空指針域。 6.6.設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為d，則e=_______。 7.7.設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為___________________________。 v1??3??2??4v2??1??3v3??1??4??28.8.設(shè)某無向圖G的鄰接表為v4??1??3，則從頂點(diǎn)V1開始的深度優(yōu)先遍歷序列為___________；廣度優(yōu)先遍歷序列為____________。 三、應(yīng)用題(36分)1． 1． 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。 2． 2． 設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量q指向被插入結(jié)點(diǎn)B，要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列（設(shè)雙向鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別為llink和rlink）。 3． 3． 設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長度。 4． 4． 設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲(chǔ)結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。5． 5． 設(shè)有無向圖G（如右圖所示），要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。 6． 6． 設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。 數(shù)據(jù)結(jié)構(gòu)試卷 （二）參考答案 一、選擇題 1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C 二、填空題 1.1.構(gòu)造一個(gè)好的HASH函數(shù)，確定解決沖突的方法 2.2.stack.top++，stack.s[stack.top]=x 3.3.有序 4.4.O(n2)，O(nlog2n)5.5.N0-1，2N0+N1 6.6.d/2 7.7.(31，38，54，56，75，80，55，63)8.8.(1，3，4，2)，(1，3，2，4) 三、應(yīng)用題 1.1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2.2.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.3.2,ASL=91*1+2*2+3*4+4*2)=25/9 4.4.樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，二叉樹略 5.5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 6.6.略 數(shù)據(jù)結(jié)構(gòu)試卷 （三）一、選擇題(30分)1．設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數(shù)據(jù)結(jié)構(gòu)A是（）。 (A)線性結(jié)構(gòu)(B)樹型結(jié)構(gòu)(C)物理結(jié)構(gòu)(D)圖型結(jié)構(gòu) 2．下面程序的時(shí)間復(fù)雜為（） for（i=1，s=0； i<=n； i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)3．設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操作序列為（）。 (A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)； (C)q=p->next；p->next=q->next；free(q)； (D)q=p->next；p->data=q->data；free(q)； 4．設(shè)有n個(gè)待排序的記錄關(guān)鍵字，則在堆排序中需要（）個(gè)輔助記錄單元。 (A)1(B)n(C)nlog2n(D)n2 5．設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為()。(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21(C)10，15，14，20，18，40，36，2l(D)15，10，14，18，20，36，40，21 6．設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹的平均平均查找長度為（）。(A)O(1)(B)O(log2n)(C)(D)O(n)7．設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為（）。 (A)n，e(B)e，n(C)2n，e(D)n，2e 8.設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有（）條邊。 (A)n(n-1)(B)n+1(C)n(D)n(n+1)9．設(shè)有5000個(gè)待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字，則用下列（）方法可以達(dá)到此目的。 (A)快速排序(B)堆排序(C)歸并排序(D)插入排序 10.下列四種排序中（）的空間復(fù)雜度最大。 (A)插入排序(B)冒泡排序(C)堆排序(D)歸并排序 二、填空殖(48分，其中最后兩小題各6分)1.1.數(shù)據(jù)的物理結(jié)構(gòu)主要包括_____________和______________兩種情況。 2.2.設(shè)一棵完全二叉樹中有500個(gè)結(jié)點(diǎn)，則該二叉樹的深度為__________；若用二叉鏈表作為該完全二叉樹的存儲(chǔ)結(jié)構(gòu)，則共有___________個(gè)空指針域。 3.3.設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到___________種不同的輸出序列。 4.4.設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲(chǔ)結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)i的________，第i列上所有元素之和等于頂點(diǎn)i的________。 5.5.設(shè)哈夫曼樹中共有n個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有________個(gè)度數(shù)為1的結(jié)點(diǎn)。6.6.設(shè)有向圖G中有n個(gè)頂點(diǎn)e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d，則e和d的關(guān)系為_________。 7.7.__________遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列（填先序、中序或后序）。 8.8.設(shè)查找表中有100個(gè)元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較________次就可以斷定數(shù)據(jù)元素X是否在查找表中。 9.9.不論是順序存儲(chǔ)結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧，其入棧和出棧操作的時(shí)間復(fù)雜度均為____________。 10.10.設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號(hào)，則第i個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為____________，右孩子結(jié)點(diǎn)的編號(hào)為___________。11.11.設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為___________________________。 12.12.設(shè)有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓?fù)湫蛄袨開___________________。 13.13.下列算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請?jiān)谙聞澗€處填上正確的語句。 struct record{int key;int others;};int hashsqsearch(struct record hashtable[ ],int k){ int i,j;j=i=k % p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____)%m;if(i==j)return(-1);} if(_______________________)return(j);else return(-1);} 14.14.下列算法實(shí)現(xiàn)在二叉排序樹上查找關(guān)鍵值k，請?jiān)谙聞澗€處填上正確的語句。 typedef struct node{int key;struct node *lchild;struct node *rchild;}bitree;bitree *bstsearch(bitree *t, int k){ if(t==0)return(0);else while(t!=0)if(t->key==k)_____________;else if(t->key>k)t=t->lchild;else_____________;} 數(shù)據(jù)結(jié)構(gòu)試卷 （三）參考答案 一、選擇題 1.B 2.B 3.A 4.A 5.A 6.B 7.D 8.C 9.B 10.D 第3小題分析：首先用指針變量q指向結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，然后將結(jié)點(diǎn)B的值復(fù)制到結(jié)點(diǎn)A中，最后刪除結(jié)點(diǎn)B。 第9小題分析：9快速排序、歸并排序和插入排序必須等到整個(gè)排序結(jié)束后才能夠求出最小的10個(gè)數(shù)，而堆排序只需要在初始堆的基礎(chǔ)上再進(jìn)行10次篩選即可，每次篩選的時(shí)間復(fù)雜度為O(log2n)。 二、填空題 1.1.順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 2.2.9，501 3.3.5 4.4.出度，入度 5.5.0 6.6.e=d 7.7.中序 8.8.7 9.9.O(1)10.10.i/2，2i+1 11.11.(5，16，71，23，72，94，73)12.12.(1，4，3，2)13.13.j+1，hashtable[j].key==k 14.14.return(t)，t=t->rchild 第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進(jìn)行二分查找時(shí)的查找長度不超過二叉判定樹的高度1+log2n。 } 數(shù)據(jù)結(jié)構(gòu)試卷 （四）一、選擇題(30分)1．設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n)2．設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（）個(gè)結(jié)點(diǎn)。 (A)2k-1(B)2k(C)2k-1(D)2k-1 3．設(shè)某無向圖中有n個(gè)頂點(diǎn)e條邊，則該無向圖中所有頂點(diǎn)的入度之和為（）。 (A)n(B)e(C)2n(D)2e 4．在二叉排序樹中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為（）。 (A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)5．設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有（）條有向邊。 (A)n(B)n-1(C)m(D)m-1 6．設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進(jìn)行（）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。 (A)3(B)4(C)5(D)8 7．設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作（）。 (A)必須判別棧是否為滿(B)必須判別棧是否為空 (C)判別棧元素的類型(D)對棧不作任何判別 8．下列四種排序中（）的空間復(fù)雜度最大。 (A)快速排序(B)冒泡排序(C)希爾排序(D)堆 9．設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（）。 (A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l 10.設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（）。 (A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1) 二、填空題(42分)1． 1． 設(shè)有n個(gè)無序的記錄關(guān)鍵字，則直接插入排序的時(shí)間復(fù)雜度為________，快速排序的平均時(shí)間復(fù)雜度為_________。 2． 2． 設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X，則刪除結(jié)點(diǎn)X需要執(zhí)行的語句序列為_________________________________________________________（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink）。3． 3． 根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。4． 4． 深度為k的完全二叉樹中最少有____________個(gè)結(jié)點(diǎn)。5． 5． 設(shè)初始記錄關(guān)鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從第______個(gè)元素開始進(jìn)行篩選。 6． 6． 設(shè)哈夫曼樹中共有99個(gè)結(jié)點(diǎn)，則該樹中有_________個(gè)葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該樹中有_____個(gè)空指針域。 7． 7． 設(shè)有一個(gè)順序循環(huán)隊(duì)列中有M個(gè)存儲(chǔ)單元，則該循環(huán)隊(duì)列中最多能夠存儲(chǔ)________個(gè)隊(duì)列元素；當(dāng)前實(shí)際存儲(chǔ)________________個(gè)隊(duì)列元素（設(shè)頭指針F指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，尾指針指向當(dāng)前隊(duì)尾元素的位置）。 8． 8． 設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中_______個(gè)數(shù)據(jù)元素；刪除第i個(gè)位置上的數(shù)據(jù)元素需要移動(dòng)表中_______個(gè)元素。9． 9． 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結(jié)果為______________________________。 10．10．設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為________________________。 11．11．設(shè)某無向圖G中有n個(gè)頂點(diǎn)，用鄰接矩陣A作為該圖的存儲(chǔ)結(jié)構(gòu)，則頂點(diǎn)i和頂點(diǎn)j互為鄰接點(diǎn)的條件是______________________。 12．12．設(shè)無向圖對應(yīng)的鄰接矩陣為A，則A中第i上非0元素的個(gè)數(shù)_________第i列上非0元素的個(gè)數(shù)（填等于，大于或小于）。 13．13．設(shè)前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_____________。 14．14．設(shè)散列函數(shù)H(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點(diǎn)，成功時(shí)返回指向關(guān)鍵字的指針，不成功時(shí)返回標(biāo)志0。 typedef struct node {int key;struct node *next;} lklist;void createlkhash(lklist *hashtable[ ]){ int i,k;lklist *s;for(i=0;i 數(shù)據(jù)結(jié)構(gòu)試卷 （四）參考答案 一、選擇題 1．C 2．D 3．D 4．B 5．C 6．A 7．B 8．A 9．C 10．A 二、填空題 1.1.O(n2)，O(nlog2n)2.2.p>llink->rlink=p->rlink;p->rlink->llink=p->rlink 3.3.3 4.4.2k-1 5.5.n/2 6.6.50，51 7.7.m-1，(R-F+M)%M 8.8.n+1-i，n-i 9.9.(19，18，16，20，30，22)10.10.(16，18，19，20，32，22)11.11.A[i][j]=1 12.12.等于 13.13.BDCA 14.14.hashtable[i]=0，hashtable[k]=s 數(shù)據(jù)結(jié)構(gòu)試卷 （五）一、選擇題(30分) 1．?dāng)?shù)據(jù)的最小單位是（）。 (A)數(shù)據(jù)項(xiàng)(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量 2．設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（）。 (A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，20 3．設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個(gè)長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為（）。 (A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，85 4．函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為（）。 (A)“STRUCTURE”(B)“DATA” (C)“ASTRUCTUR”(D)“DATASTRUCTURE” 5．設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為（）。 (A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)6．設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，……，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，則N0=（）。 (A)Nl+N2+……+Nm (B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm 7．設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素X最多需要比較（）次。 (A)25(B)10(C)7(D)1 8．設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為（）。 (A)abedfc(B)acfebd(C)aebdfc(D)aedfcb 9．設(shè)輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個(gè)元素是n，則輸出序列中第i個(gè)輸出元素是（）。 (A)n-i(B)n-1-i(C)n+1-i(D)不能確定 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（）。 (A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，80 二、填空題(共30分)1.1.設(shè)有一個(gè)順序共享?xiàng)[0：n-1]，其中第一個(gè)棧項(xiàng)指針top1的初值為-1，第二個(gè)棧頂指針top2的初值為n，則判斷共享?xiàng)M的條件是____________________。 2.2.在圖的鄰接表中用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是____________________。 3.3.設(shè)有一個(gè)n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽蔷€上元素）存放在n(n+1)個(gè)連續(xù)的存儲(chǔ)單元中，則A[i][j]與A[0][0]之間有_______個(gè)數(shù)據(jù)元素。 4.4.棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為__________表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素必定先出隊(duì)列，所以又把隊(duì)列稱為_________表。 5.5.設(shè)一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為___________，中序遍歷序列為___________，后序遍歷序列為___________。 6.6.設(shè)一棵完全二叉樹有128個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為________，有__________個(gè)葉子結(jié)點(diǎn)。 7.7.設(shè)有向圖G的存儲(chǔ)結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的________，第i列中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的__________。 8.8.設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言滿足的條件為_______________________________。 9.9.下面程序段的功能是實(shí)現(xiàn)冒泡排序算法，請?jiān)谙聞澗€處填上正確的語句。void bubble(int r[n]){ for(i=1;i<=n-1;i++){ for(exchange=0,j=0;j<_____________;j++) if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if(exchange==0)return； } } 10.10.下面程序段的功能是實(shí)現(xiàn)二分查找算法，請?jiān)谙聞澗€處填上正確的語句。struct record{int key;int others;};int bisearch(struct record r[ ], int k){ int low=0,mid,high=n-1; while(low<=high){ ________________________________; if(r[mid].key==k)return(mid+1);else if(____________)high=mid-1;else low=mid+1; } return(0);} 三、應(yīng)用題(24分) 1.1.設(shè)某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。2.2.設(shè)無向圖G（如右圖所示），給出該圖的最小生成樹上邊的集合并計(jì)算最小生成樹各邊上的權(quán)值之和。 3.3.設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計(jì)算出成功查找時(shí)的平均查找長度。 4.4.設(shè)散列表的長度為8，散列函數(shù)H(k)=k mod 7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計(jì)算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。 數(shù)據(jù)結(jié)構(gòu)試卷 （五）參考答案 一、選擇題 1．A 2．B 3．A 4．A 5．D 6．B 7．B 8．B 9．C 10．C 二、填空題 1.1.top1+1=top2 2.2.可以隨機(jī)訪問到任一個(gè)頂點(diǎn)的簡單鏈表 3.3.i(i+1)/2+j-1 4.4.FILO，F(xiàn)IFO 5.5.ABDECF，DBEAFC，DEBFCA 6.6.8，64 7.7.出度，入度 8.8.ki<=k2i && ki<=k2i+1 9.9.n-i，r[j+1]=r[j] 10.10.mid=(low+high)/2，r[mid].key>k 三、應(yīng)用題 1.1.DEBCA 2.2.E={(1,5),(5,2),(5,3),(3,4)},W=10 3.3.ASL=(1*1+2*2+3*4)/7=17/7 4.4.ASL1=7/6，ASL2=4/3 數(shù)據(jù)結(jié)構(gòu)試卷 （六）一、選擇題(30分)1． 設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為（）。 (A)20(B)30(C)40(D)45 2．執(zhí)行一趟快速排序能夠得到的序列是（）。 (A)[41，12，34，45，27] 55 [72，63](B)[45，34，12，41] 55 [72，63，27](C)[63，12，34，45，27] 55 [41，72](D)[12，27，45，41] 55 [34，63，72] 3．設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點(diǎn)，則其判空條件是（）。(A)head==0(B)head->next==0(C)head->next==head(D)head!=0 4．時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（）。 (A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序 5．設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。 (A)空或只有一個(gè)結(jié)點(diǎn)(B)高度等于其結(jié)點(diǎn)數(shù) (C)任一結(jié)點(diǎn)無左孩子(D)任一結(jié)點(diǎn)無右孩子 6．一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是（）。 (A)堆排序(B)冒泡排序(C)快速排序(D)希爾排序 7．設(shè)某棵三叉樹中有40個(gè)結(jié)點(diǎn)，則該三叉樹的最小高度為（）。 (A)3(B)4(C)5(D)6 8．順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為（）。 21/2(A)O(n)(B)O(n)(C)O(n)(D)O(1og2n)9．二路歸并排序的時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)10.深度為k的完全二叉樹中最少有（）個(gè)結(jié)點(diǎn)。 (A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-1 11.設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為（）。 (A)front->next=s；front=s；(B)s->next=rear；rear=s； (C)rear->next=s；rear=s；(D)s->next=front；front=s； 12.設(shè)某無向圖中有n個(gè)頂點(diǎn)e條邊，則建立該圖鄰接表的時(shí)間復(fù)雜度為（）。(A)O(n+e)(B)O(n)(C)O(ne)(D)O(n)13.設(shè)某哈夫曼樹中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有（）個(gè)葉子結(jié)點(diǎn)。 (A)99(B)100(C)101(D)102 14.設(shè)二叉排序樹上有n個(gè)結(jié)點(diǎn)，則在二叉排序樹上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)15.設(shè)用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（）。 (A)第i行非0元素的個(gè)數(shù)之和(B)第i列非0元素的個(gè)數(shù)之和 (C)第i行0元素的個(gè)數(shù)之和(D)第i列0元素的個(gè)數(shù)之和 二、判斷題(20分)1．調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點(diǎn)。（） 2．分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。（）3．冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（）4．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（） 5．設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）6．層次遍歷初始堆可以得到一個(gè)有序的序列。（） 7．設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（）8．線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。（） 9．中序遍歷二叉排序樹可以得到一個(gè)有序的序列。（）10.快速排序是排序算法中平均性能最好的一種排序。（） 三、填空題(30分)1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的時(shí)間復(fù)雜度為_________。 2．設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的新結(jié)點(diǎn)X，則進(jìn)行插入操作的語句序列為__________________________（設(shè)結(jié)點(diǎn)的指針域?yàn)閚ext）。3．設(shè)有向圖G的二元組形式表示為G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，則給出該圖的一種拓?fù)渑判蛐蛄衉_________。4．設(shè)無向圖G中有n個(gè)頂點(diǎn)，則該無向圖中每個(gè)頂點(diǎn)的度數(shù)最多是_________。5．設(shè)二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為50，度數(shù)為1的結(jié)點(diǎn)數(shù)為30，則該二叉樹中總共有_______個(gè)結(jié)點(diǎn)數(shù)。 6．設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)隊(duì)列為空的條件為_____________________。 7．設(shè)二叉樹中結(jié)點(diǎn)的兩個(gè)指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_____________________________________________。8．簡單選擇排序和直接插入排序算法的平均時(shí)間復(fù)雜度為___________。 9．快速排序算法的空間復(fù)雜度平均情況下為__________，最壞的情況下為__________。10.散列表中解決沖突的兩種方法是_____________和_____________。 數(shù)據(jù)結(jié)構(gòu)試卷 （六）參考答案 一、選擇題 1．D 2．A 3．A 4．A 5．D 6．D 7．B 8．A 9．C 10．B 11．C 12．A 13．B 14．D 15．B 二、判斷題 1．錯(cuò) 2．對 3．對 4．對 5．錯(cuò) 6．錯(cuò) 7．對 8．錯(cuò) 9．對 10．對 三、填空題 1.1.O(n)2.2.s->next=p->next;p->next=s 3.3.(1，3，2，4，5)4.4.n-1 5.5.129 6.6.F==R 7.7.p->lchild==0&&p->rchild==0 8.8.O(n2)9.9.O(nlog2n)，O(n)10.10.開放定址法，鏈地址法 數(shù)據(jù)結(jié)構(gòu)試卷 （七）一、選擇題(30分)1．設(shè)某無向圖有n個(gè)頂點(diǎn)，則該無向圖的鄰接表中有（）個(gè)表頭結(jié)點(diǎn)。 (A)2n(B)n(C)n/2(D)n(n-1)2．設(shè)無向圖G中有n個(gè)頂點(diǎn)，則該無向圖的最小生成樹上有（）條邊。 (A)n(B)n-1(C)2n(D)2n-1 3．設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個(gè)關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（）。 (A)40，42，60，55，80，85(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，80 4．（）二叉排序樹可以得到一個(gè)從小到大的有序序列。 (A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷 5．設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進(jìn)行順序編號(hào)，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為（）。 (A)2i+1(B)2i(C)i/2(D)2i-1 6．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(n)(D)O(n/2)7．設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（）。 (A)head==0(B)head->next==0(C)head->next==head(D)head!=0 8．設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點(diǎn)最多有（）。 (A)20(B)256(C)512(D)1024 9．設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為（）。 (A)1(B)2(C)3(D)4 10.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（）。 (A)top=top+1;(B)top=top-1;(C)top->next=top;(D)top=top->next; 三、填空題(30分)1.1.設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為_________=p；s->right=p->right；__________=s； p->right->left=s；（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為left和right）。2.2.設(shè)完全有向圖中有n個(gè)頂點(diǎn)，則該完全有向圖中共有________條有向條；設(shè)完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中共有________條無向邊。 3.3.設(shè)關(guān)鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個(gè)元素開始進(jìn)行篩選。 4.4.解決散列表沖突的兩種方法是________________和__________________。 5.5.設(shè)一棵三叉樹中有50個(gè)度數(shù)為0的結(jié)點(diǎn)，21個(gè)度數(shù)為2的結(jié)點(diǎn)，則該二叉樹中度數(shù)為3的結(jié)點(diǎn)數(shù)有______個(gè)。 6.6.高度為h的完全二叉樹中最少有________個(gè)結(jié)點(diǎn)，最多有________個(gè)結(jié)點(diǎn)。7.7.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是__________________________________。 8.8.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結(jié)束后的結(jié)果的是__________________________________。 9.9.設(shè)一棵二叉樹的前序序列為ABC，則有______________種不同的二叉樹可以得到這種序列。 10.10.下面程序段的功能是實(shí)現(xiàn)一趟快速排序，請?jiān)谙聞澗€處填上正確的語句。 struct record {int key;datatype others;};void quickpass(struct record r[], int s, int t, int &i){ int j=t;struct record x=r[s];i=s; while(i while(i while(____________________)i=i+1;if(i } _________________;} 數(shù)據(jù)結(jié)構(gòu)試卷 （七）一、選擇題 1．B 2．B 3．C 4．B 6．A 7．C 8．C 9．B 三、填空題 1.1.s->left=p，p->right 2.2.n(n-1)，n(n-1)/2 3.3.n/2 4.4.開放定址法，鏈地址法 5.5.14 6.6.2h-1，2h-1 7.7.(12，24，35，27，18，26)8.8.(12，18，24，27，35，26)9.9.5 10.10.i 5．B 10．D 數(shù)據(jù)結(jié)構(gòu)試卷 （八）一、選擇題(30分)1.1.字符串的長度是指（）。 (A)串中不同字符的個(gè)數(shù)(B)串中不同字母的個(gè)數(shù) (C)串中所含字符的個(gè)數(shù)(D)串中不同數(shù)字的個(gè)數(shù) 2.2.建立一個(gè)長度為n的有序單鏈表的時(shí)間復(fù)雜度為（） (A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)3.3.兩個(gè)字符串相等的充要條件是（）。 (A)兩個(gè)字符串的長度相等(B)兩個(gè)字符串中對應(yīng)位置上的字符相等 (C)同時(shí)具備(A)和(B)兩個(gè)條件(D)以上答案都不對 4.4.設(shè)某散列表的長度為100，散列函數(shù)H(k)=k % P，則P通常情況下最好選擇（）。 (A)99(B)97(C)91(D)93 5.5.在二叉排序樹中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n)6.6.設(shè)一個(gè)順序有序表A[1:14]中有14個(gè)元素，則采用二分法查找元素A[4]的過程中比較元素的順序?yàn)?)。 (A)A[1]，A[2]，A[3]，A[4](B)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4] 7.7.設(shè)一棵完全二叉樹中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為（）。 (A)8(B)7(C)6(D)5 8.8.設(shè)一棵三叉樹中有2個(gè)度數(shù)為1的結(jié)點(diǎn)，2個(gè)度數(shù)為2的結(jié)點(diǎn)，2個(gè)度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有（）個(gè)度數(shù)為0的結(jié)點(diǎn)。 (A)5(B)6(C)7(D)8 9.9.設(shè)無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（）。 (A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc 10.10.隊(duì)列是一種（）的線性表。 (A)先進(jìn)先出(B)先進(jìn)后出(C)只能插入(D)只能刪除 三、填空題(30分)1． 1． 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為_____________________________。 2． 2． 下面程序段的功能是實(shí)現(xiàn)在二叉排序樹中插入一個(gè)新結(jié)點(diǎn)，請?jiān)谙聞澗€處填上正確的內(nèi)容。 typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;void bstinsert(bitree *&t,int k){ if(t==0){____________________________;t->data=k;t->lchild=t->rchild=0;} else if(t->data>k)bstinsert(t->lchild,k);else__________________________;} 3． 3． 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X需要執(zhí)行的語句序列：s->next=p->next;_________________。4． 4． 設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量p指向雙向鏈表中的第一個(gè)結(jié)點(diǎn)，則指針變量p和指針變量head之間的關(guān)系是p=_________和head=__________（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink）。 5． 5． 設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為__________。 6． 6． 完全二叉樹中第5層上最少有__________個(gè)結(jié)點(diǎn)，最多有_________個(gè)結(jié)點(diǎn)。7． 7． 設(shè)有向圖中不存在有向邊 8． 8． 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為_____________________________。 9． 9． 設(shè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則對應(yīng)的最小生成樹上有___________條邊。10． 10． 設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與___________相互交換即可。 數(shù)據(jù)結(jié)構(gòu)試卷 （八）參考答案 一、選擇題 1．C 2．C 3．C 4．B 5．B 6．C 7．B 8．C 9．A 10．A 三、填空題 1.1.(49，13，27，50，76，38，65，97)2.2.t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)3.3.p->next=s 4.4.head->rlink，p->llink 5.5.CABD 6.6.1，16 7.7.0 8.8.(13，27，38，50，76，49，65，97)9.9.n-1 10.10.50 一、數(shù)據(jù)結(jié)構(gòu)考查目標(biāo) 1、掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法。 2、掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn)，能夠?qū)λ惴ㄟM(jìn)行基 本的時(shí)間復(fù)雜度與空間復(fù)雜度的分析。 3、能夠數(shù)據(jù)結(jié)構(gòu)基本原理和方法進(jìn)行問題的分析與求解，具備采用C或 C++語言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。 二、數(shù)據(jù)結(jié)構(gòu)變化解析 1.變化一 【考察目標(biāo)】 3.能夠數(shù)據(jù)結(jié)構(gòu)基本原理和方法進(jìn)行問題的分析與求解，具備采用C或C++語言設(shè)計(jì)與實(shí)現(xiàn)算法的能力，刪去了“Java”。 2.變化二 四.圖 (二)圖的存儲(chǔ)及基本操作 1.鄰接矩陣法 2.鄰接表法 3.鄰接多重表、十字鏈表(新增考點(diǎn)) 3.變化三 五、查找 (一)查找的基本概念 (二)順序查找法 (三)分塊查找法(新增考點(diǎn)) (四)折半查找法 (五)B樹及其基本操作、B+樹的基本概念 (六)散列(Hash)表 (七)字符串模式匹配(新增考點(diǎn)) (八)查找算法的分析與應(yīng)用 三、復(fù)習(xí)與備考指導(dǎo) 1、扎實(shí)基礎(chǔ)，注意綜合應(yīng)用，特別是有關(guān)于線性表算法的綜合設(shè)計(jì)，一定要牢牢掌握。 2、加強(qiáng)對C語言基礎(chǔ)的學(xué)習(xí)，2014年新東方在線應(yīng)廣大考生的需求將開設(shè)C語言專項(xiàng)精講課程，保障大家考研（微博）成功。 3、大家在復(fù)習(xí)時(shí)，先要了解數(shù)據(jù)結(jié)構(gòu)科目的考試范圍、內(nèi)容，系統(tǒng)梳理教材中的考查知識(shí)點(diǎn)，建立層次分明的知識(shí)體系。 4、數(shù)據(jù)結(jié)構(gòu)科目的特點(diǎn)是思路靈活，概念聯(lián)系緊密。從線性表，樹，圖，以及后面的查找，排序，是一環(huán)扣一環(huán)的。如二叉樹遍歷的遞歸和非遞歸算法、圖的深度優(yōu)先遍歷等都要用道棧，樹的層次遍歷、圖的廣度優(yōu)先遍歷則要用到隊(duì)列。查找和排序則要綜合運(yùn)用線性表、棧、樹等知識(shí)。所以建議大家在復(fù)習(xí)時(shí)，先弄懂基本概念，然后多做習(xí)題來加深對基本概念、基礎(chǔ)知識(shí)的理解，掌握解題思路和技巧。 5、對于數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，難在其中的算法及實(shí)現(xiàn)。因此很多同學(xué)在復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)，有這樣的疑問：數(shù)據(jù)結(jié)構(gòu)中的算法是否需要背誦?數(shù)據(jù)結(jié)構(gòu)是非常靈活的科目，所以不建議大家死記硬背算法，大家應(yīng)該在理解的基礎(chǔ)上適當(dāng)?shù)挠洃浺恍┙?jīng)典算法。 6、大家在復(fù)習(xí)時(shí)，如果時(shí)間充足，可以在計(jì)算機(jī)上編寫程序，自己實(shí)現(xiàn)教材上的算法，加深對算法的理解。不過對于時(shí)間倉促的同學(xué)來說，可以使用實(shí)例來驗(yàn)證自己算法的正確性 一、選擇題 1.算法的計(jì)算量的大小稱為計(jì)算的（B）?！颈本┼]電大學(xué)2000 二、3（20/8分）】 A．效率 B.復(fù)雜性 C.現(xiàn)實(shí)性 D.難度 2.算法的時(shí)間復(fù)雜度取決于（C）【中科院計(jì)算所 1998 二、1（2分）】 A．問題的規(guī)模 B.待處理數(shù)據(jù)的初態(tài) C.A和B 3.計(jì)算機(jī)算法指的是（C），它必須具備（B）這三個(gè)特性。 (1)A．計(jì)算方法 B.排序方法 C.解決問題的步驟序列 D.調(diào)度方法 (2)A．可執(zhí)行性、可移植性、可擴(kuò)充性 B.可執(zhí)行性、確定性、有窮性 C.確定性、有窮性、穩(wěn)定性 D.易讀性、穩(wěn)定性、安全性 【南京理工大學(xué) 1999 一、1（2分）【武漢交通科技大學(xué) 1996 一、1（4分）】 4．一個(gè)算法應(yīng)該是（B）。【中山大學(xué) 1998 二、1（2分）】 A．程序 B．問題求解步驟的描述 C．要滿足五個(gè)基本特性 D．A和C.5.下面關(guān)于算法說法錯(cuò)誤的是（D）【南京理工大學(xué) 2000 一、1（1.5分）】 A．算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn) B.為解決某問題的算法同為該問題編寫的程序含義是相同的 C.算法的可行性是指指令不能有二義性 D.以上幾個(gè)都是錯(cuò)誤的 6.下面說法錯(cuò)誤的是（C）【南京理工大學(xué) 2000 一、2（1.5分）】(1）算法原地工作的含義是指不需要任何額外的輔助空間 （2）在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度nO(2)的算法 （3）所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界 （4）同一個(gè)算法，實(shí)現(xiàn)語言的級別越高，執(zhí)行效率就越低4 A．(1)B.(1),(2)C.(1),(4)D.(3)7．從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C）兩大類。【武漢交通科技大學(xué) 1996 一、4（2分）】 A．動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B．順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C．線性結(jié)構(gòu)、非線性結(jié)構(gòu) D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu) 8．以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是（D）【北方交通大學(xué) 2000 二、。1（2分）】 A．循環(huán)隊(duì)列 B.鏈表 C.哈希表 D.棧 9．以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（D）？【北方交通大學(xué) 2001 一、1（2分）】 A．廣義表 B.二叉樹 C.稀疏矩陣 D.串 10．以下那一個(gè)術(shù)語與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)？（A）【北方交通大學(xué) 2001 一、2（2分）】 A．棧 B.哈希表 C.線索樹 D.雙向鏈表 11．在下面的程序段中，對x的賦值語句的頻度為（C）【北京工商大學(xué) 2001 一、10（3分）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; 2nA． O(2n)B．O(n)C．O(n)D．O(log2)12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]與A[j+1]對換； 其中 n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（D） 32A.O（n）B.O(nlogn)C.O(n)D.O(n)【南京理工大學(xué)1998 一、1(2分)】 13．以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型（D）【中山大學(xué) 1999 一、3（1分）】 A．棧 B．廣義表 C．有向圖 D．字符串 14．以下數(shù)據(jù)結(jié)構(gòu)中，（A）是非線性數(shù)據(jù)結(jié)構(gòu)【中山大學(xué) 1999 一、4】 A．樹 B．字符串 C．隊(duì) D．棧 15.下列數(shù)據(jù)中，（C）是非線性數(shù)據(jù)結(jié)構(gòu)?！颈本├砉ご髮W(xué) 2001 六、1（2分）】 A．棧 B.隊(duì)列 C.完全二叉樹 D.堆 16．連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址（A）?！局猩酱髮W(xué) 1999 一、1（1分）】 A．一定連續(xù) B．一定不連續(xù) C．不一定連續(xù) D．部分連續(xù)，部分不連續(xù) 17．以下屬于邏輯結(jié)構(gòu)的是（C）?！疚靼搽娮涌萍即髮W(xué)應(yīng)用 200 1一、1】 A．順序表 B.哈希表 C.有序表 D.單鏈表 二、判斷題 1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。(X)【北京郵電大學(xué) 1998 一、1（2分）】【青島大學(xué) 2000 一、1（1分）】 【上海交通大學(xué) 1998 一、1】 【山東師范大學(xué) 2001 一、1（2分）】 2.記錄是數(shù)據(jù)處理的最小單位。(X)【上海海運(yùn)學(xué)院 1998 一、5（1分）】 3.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系；(X)【北京郵電大學(xué)2002 一、1（1分）】 4．算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計(jì)算機(jī)有關(guān)。(X)【大連海事大學(xué) 2001 一、10（1分）】 5．健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。(O)【大連海事大學(xué) 2001 一、11（1分）】 6．算法可以用不同的語言描述，如果用C 語言或PASCAL語言等高級語言來描述，則算法實(shí)際上就是程序了。(X)【西安交通大學(xué) 1996 二、7（3分）】 7．程序一定是算法。(X)【燕山大學(xué) 1998 二、2（2分）并改錯(cuò)】 8．?dāng)?shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。(O)【山東師范大學(xué)2001 一、2（2分）】 9.數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。(X)【華南理工大學(xué) 2002 一、1（1分）】 10.在順序存儲(chǔ)結(jié)構(gòu)中，有時(shí)也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。(X)【華南理工大學(xué) 2002 一、2（1分）】 11.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。(X)【上海海運(yùn)學(xué)院 1999 一、1（1分）】 12.數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實(shí)現(xiàn)應(yīng)用程序與存儲(chǔ)結(jié)構(gòu)的獨(dú)立。(O)【華南理工大學(xué) 2002 一、5（1分）】 13.數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系,它依賴于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu).(X)【上海海運(yùn)學(xué)院 1998 一、1（1分）】 三、填空 1．?dāng)?shù)據(jù)的物理結(jié)構(gòu)包括數(shù)據(jù)元素的表示和數(shù)據(jù)元素間關(guān)系的表示?！狙嗌酱髮W(xué) 1998 一、1（2分）】 2.對于給定的n個(gè)元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有集合 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖狀結(jié)構(gòu)(或網(wǎng)狀結(jié)構(gòu))四種。 【中科院計(jì)算所 1999 二、1（4分）】 3．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的組織形式，即數(shù)據(jù)元素之間邏輯關(guān)系的總體。而邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或稱“鄰接關(guān)系”?！颈本┼]電大學(xué) 2001 二、1（2分）】 4．一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中表示（又稱映像）稱為存儲(chǔ)結(jié)構(gòu)?！救A中理工大學(xué) 2000 一、1（1分）】 5．抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部使用?！旧綎|大學(xué) 2001 三、3（2分）】 6．?dāng)?shù)據(jù)結(jié)構(gòu)中評價(jià)算法的兩個(gè)重要指標(biāo)是算法的時(shí)間復(fù)雜度和空間復(fù)雜度【北京理工大學(xué) 2001 七、1（2分）】 7.數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的_邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，以及它們之間的相互關(guān)系，并對與這種結(jié)構(gòu)定義相應(yīng)的操作（運(yùn)算），設(shè)計(jì)出相應(yīng)的算法?！疚靼搽娮涌萍即髮W(xué) 1998 二、2（3分）】 8． 一個(gè)算法具有5個(gè)特性:（1）有窮性（2）確定性（3）可行性，有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。 【華中理工大學(xué) 2000 一、2（5分）】 【燕山大學(xué) 1998 一、2（5分）】 9．已知如下程序段 FOR i:= n DOWNTO 1 DO {語句1} BEGIN x:=x+1； {語句2} FOR j:=n DOWNTO i DO {語句3} y:=y+1; {語句4} END； 語句1執(zhí)行的頻度為 n+1 ；語句2執(zhí)行的頻度為n；語句3執(zhí)行的頻度為n(n+3)/2；語句4執(zhí)行的頻度為n(n+1)/2?！颈狈浇煌ù髮W(xué) 1999 二、4（5分）】 10．在下面的程序段中，對ｘ的賦值語句的頻度為1+（1+2++（1+2+3） 3+?+（1+2+?+n）=n(n+1)(n+2)/6 O(n)（表示為n的函數(shù)） FOR i：＝１ TO n DO FOR j：＝１ TO i DO FOR k：＝1 TO j DO ｘ：＝ｘ＋delta； 【北京工業(yè)大學(xué) 1999 一、6（2分）】 11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是：log2n【合肥工業(yè)大學(xué)1999 三、1（分）】 i：=1； WHILE i 三、1（2分）】 i:=1;WHILE i 三、1（2分）】 i：=n*n WHILE i<>1 DO i:=i div 2;14.計(jì)算機(jī)執(zhí)行下面的語句時(shí)，語句s的執(zhí)行次數(shù)為(n+3)(n-2)/2?！灸暇├砉ご髮W(xué)2000 二、1（1.5分）】 FOR(i=l；i for(i=0;sum 二、1（2分）】 16．設(shè)m.n均為自然數(shù)，m可表示為一些不超過n的自然數(shù)之和，f(m,n)為這種表示方式的數(shù)目。例f(5,3)=5，有5種表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。 ①以下是該函數(shù)的程序段，請將未完成的部分填入，使之完整 int f(m,n)int m,n;{ if(m==1)return 1;if(n==1){ return 1;} if(m 二、1（9分）】 17.在有n個(gè)選手參加的單循環(huán)賽中，總共將進(jìn)行n(n-1)/2 場比賽?！竞戏使I(yè)大學(xué)1999 三、8（2分）】 四、應(yīng)用題 1.數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學(xué)科？【燕山大學(xué) 1999 二、1（4分）】 數(shù)據(jù)結(jié)構(gòu)是一門研究在非數(shù)值計(jì)算的程序設(shè)計(jì)問題中，計(jì)算機(jī)的操作對象及對象間的關(guān)系和施加于對象的操作等的學(xué)科。 2.數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有幾種表示方法？各有什么特點(diǎn)？【燕山大學(xué)1999 二、2（4分）】 四種表示方法 （1）順序存儲(chǔ)方式。數(shù)據(jù)元素順序存放，每個(gè)存儲(chǔ)結(jié)點(diǎn)只含一個(gè)元素。存儲(chǔ)位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲(chǔ)密度大，但有些操作（如插入、刪除）效率較差。（2）鏈?zhǔn)酱鎯?chǔ)方式。每個(gè)存儲(chǔ)結(jié)點(diǎn)除包含數(shù)據(jù)元素信息外還包含一組（至少一個(gè)）指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲(chǔ)空間連續(xù)，便于動(dòng)態(tài)操作（如插入、刪除等），但存儲(chǔ)空間開銷大（用于指針），另外不能折半查找等。 （3）索引存儲(chǔ)方式。除數(shù)據(jù)元素存儲(chǔ)在一地址連續(xù)的內(nèi)存空間外，尚需建立一個(gè)索引表，索引表中索引指示存儲(chǔ)結(jié)點(diǎn)的存儲(chǔ)位置（下標(biāo)）或存儲(chǔ)區(qū)間端點(diǎn)（下標(biāo)），兼有靜態(tài)和動(dòng)態(tài)特性。 （4）散列存儲(chǔ)方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲(chǔ)地址，這種存儲(chǔ)方式稱為散列存儲(chǔ)。其特點(diǎn)是存取速度快，只能按關(guān)鍵字隨機(jī)存取，不能順序存取，也不能折半存取。3.數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主要特點(diǎn)是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？【北京郵電大學(xué) 1994 一（8分）】 數(shù)據(jù)類型是程序設(shè)計(jì)語言中的一個(gè)概念，它是一個(gè)值的集合和操作的集合。如C語言中的整型、實(shí)型、字符型等。整型值的范圍（對具體機(jī)器都應(yīng)有整數(shù)范圍），其操作有加、減、乘、除、求余等。實(shí)際上數(shù)據(jù)類型是廠家提供給用戶的已實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)?！俺橄髷?shù)據(jù)類型（ADT）”指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作?！俺橄蟆钡囊饬x在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)。無論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變就不影響它的外部使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念。此外，抽象數(shù)據(jù)類型的范圍更廣，它已不再局限于機(jī)器已定義和實(shí)現(xiàn)的數(shù)據(jù)類型，還包括用戶在設(shè)計(jì)軟件系統(tǒng)時(shí)自行定義的數(shù)據(jù)類型。使用抽象數(shù)據(jù)類型定義的軟件模塊含定義、表示和實(shí)現(xiàn)三部分，封裝在一起，對用戶透明（提供接口），而不必了解實(shí)現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類型的出現(xiàn)使程序設(shè)計(jì)不再是“藝術(shù)”，而是向“科學(xué)”邁進(jìn)了一步。 4.回答問題（每題2分）【山東工業(yè)大學(xué) 1997 一（8分）】（1）在數(shù)據(jù)結(jié)構(gòu)課程中，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算之間存在著怎樣的關(guān)系？ 數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系（即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”），數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，包括數(shù)據(jù)元素的表示及其關(guān)系的表示。數(shù)據(jù)的運(yùn)算是對數(shù)據(jù)定義的一組操作，運(yùn)算是定義在邏輯結(jié)構(gòu)上的，和存儲(chǔ)結(jié)構(gòu)無關(guān)，而運(yùn)算的實(shí)現(xiàn)則是依賴于存儲(chǔ)結(jié)構(gòu)。 （2）若邏輯結(jié)構(gòu)相同但存儲(chǔ)結(jié)構(gòu)不同，則為不同的數(shù)據(jù)結(jié)構(gòu)。這樣的說法對嗎？舉例說明之。 邏輯結(jié)構(gòu)相同但存儲(chǔ)不同，可以是不同的數(shù)據(jù)結(jié)構(gòu)。例如，線性表的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，采用順序存儲(chǔ)結(jié)構(gòu)為順序表，而采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。 （3）在給定的邏輯結(jié)構(gòu)及其存儲(chǔ)表示上可以定義不同的運(yùn)算集合，從而得到不同的數(shù)據(jù)結(jié)構(gòu)。這樣說法對嗎？舉例說明之。 棧和隊(duì)列的邏輯結(jié)構(gòu)相同，其存儲(chǔ)表示也可相同（順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)），但由于其運(yùn)算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。 （4）評價(jià)各種不同數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么？ 數(shù)據(jù)結(jié)構(gòu)的評價(jià)非常復(fù)雜，可以考慮兩個(gè)方面，一是所選數(shù)據(jù)結(jié)構(gòu)是否準(zhǔn)確、完整的刻劃了問題的基本特征；二是是否容易實(shí)現(xiàn)（如對數(shù)據(jù)分解是否恰當(dāng)；邏輯結(jié)構(gòu)的選擇是否適合于運(yùn)算的功能，是否有利于運(yùn)算的實(shí)現(xiàn)；基本運(yùn)算的選擇是否恰當(dāng)。） 5．評價(jià)一個(gè)好的算法，您是從哪幾方面來考慮的？ 評價(jià)好的算法有四個(gè)方面。一是算法的正確性；二是算法的易讀性；三是算法的健壯性；四是算法的時(shí)空效率（運(yùn)行）。 【大連海事大學(xué) 1996 二、3（2分）】【中山大學(xué) 1998 三、1（5分）】 6．解釋和比較以下各組概念【華南師范大學(xué) 2000 一（10分）】 （1）抽象數(shù)據(jù)類型及數(shù)據(jù)類型（2）數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)（3）抽象數(shù)據(jù)類型【哈爾濱工業(yè)大學(xué) 2000 一、1（3分）】（4）算法的時(shí)間復(fù)雜性 【河海大學(xué) 1998 一、2（3分）】（5）算法【吉林工業(yè)大學(xué)1999 一、1（2分）】（6）頻度【吉林工業(yè)大學(xué) 1999 一、2（2分）】（1）見上面題3（2）見上面題4（3）見上面題3 （4）算法的時(shí)間復(fù)雜性是算法輸入規(guī)模的函數(shù)。算法的輸入規(guī)?；騿栴}的規(guī)模是作為該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關(guān)的其它參數(shù)。有時(shí)考慮算法在最壞情況下的時(shí)間復(fù)雜度或平均時(shí)間復(fù)雜度。 （5）算法是對特定問題求解步驟的描述，是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法具有五個(gè)重要特性：有窮性、確定性、可行性、輸入和輸出。 （6）頻度。在分析算法時(shí)間復(fù)雜度時(shí)，有時(shí)需要估算基本操作的原操作，它是執(zhí)行次數(shù)最多的一個(gè)操作，該操作重復(fù)執(zhí)行的次數(shù)稱為頻度。7.根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般有哪幾類基本的數(shù)據(jù)結(jié)構(gòu)？ 集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形或網(wǎng)狀結(jié)構(gòu)。 【北京科技大學(xué) 1998 一、1】【同濟(jì)大學(xué) 1998】 8．對于一個(gè)數(shù)據(jù)結(jié)構(gòu)，一般包括哪三個(gè)方面的討論？【北京科技大學(xué) 1999 一、1（2分）】 邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、操作（運(yùn)算）。 9.當(dāng)你為解決某一問題而選擇數(shù)據(jù)結(jié)構(gòu)時(shí)，應(yīng)從哪些方面考慮？【西安電子北京科技大學(xué) 2000】 通常考慮算法所需要的存儲(chǔ)空間量和算法所需要的時(shí)間量。后者又涉及到四方面：程序運(yùn)行時(shí)所需輸入的數(shù)據(jù)總量，對源程序進(jìn)行編譯所需時(shí)間，計(jì)算機(jī)執(zhí)行每條指令所需時(shí)間和程序中指令重復(fù)執(zhí)行的次數(shù)。 10.若將數(shù)據(jù)結(jié)構(gòu)定義為一個(gè)二元組（D，R）,說明符號(hào)D，R 應(yīng)分別表示什么？ 【北京科技大學(xué) 2001 一、1（2分）】 D是數(shù)據(jù)元素的有限集合，S是D上數(shù)據(jù)元素之間關(guān)系的有限集合。11．?dāng)?shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別？【哈爾濱工業(yè)大學(xué) 2001 三、1（3分）】 “數(shù)據(jù)結(jié)構(gòu)”這一術(shù)語有兩種含義，一是作為一門課程的名稱；二是作為一個(gè)科學(xué)的概念。作為科學(xué)概念，目前尚無公認(rèn)定義，一般認(rèn)為，討論數(shù)據(jù)結(jié)構(gòu)要包括三個(gè)方面，一是數(shù)據(jù)的邏輯結(jié)構(gòu)，二是數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，三是對數(shù)據(jù)進(jìn)行的操作（運(yùn)算）。而數(shù)據(jù)類型是值的集合和操作的集合，可以看作是已實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)，后者是前者的一種簡化情況。12．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)由哪四種基本的存儲(chǔ)方法實(shí)現(xiàn)？【山東科技大學(xué) 2001 一、1（4分）】 12．見上面題2。 13．若有100個(gè)學(xué)生，每個(gè)學(xué)生有學(xué)號(hào)，姓名，平均成績，采用什么樣的數(shù)據(jù)結(jié)構(gòu)最方便，寫出這些結(jié)構(gòu)？ 【山東師范大學(xué) 1996 二、2（2分）】 將學(xué)號(hào)、姓名、平均成績看成一個(gè)記錄（元素，含三個(gè)數(shù)據(jù)項(xiàng)），將100個(gè)這樣的記錄存于數(shù)組中。因一般無增刪操作，故宜采用順序存儲(chǔ)。typedef struct {int num;//學(xué)號(hào) char name[8];//姓名 float score;/平均成績 }node； node student[100];14.運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面。試舉一例，說明兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)方式完全相同，只是對于運(yùn)算的定義不同。因而兩個(gè)結(jié)構(gòu)具有顯著不同的特性，是兩個(gè)不同的結(jié)構(gòu)。 【北京大學(xué) 1998 一、1（5分）】 見上面題4（3）。 15.在編制管理通訊錄的程序時(shí), 什么樣的數(shù)據(jù)結(jié)構(gòu)合適? 為什么?【 長沙鐵道學(xué)院1998 四、3(6分)】 應(yīng)從兩方面進(jìn)行討論：如通訊錄較少變動(dòng)（如城市私人電話號(hào)碼），主要用于查詢，以順序存儲(chǔ)較方便，既能順序查找也可隨機(jī)查找；若通訊錄經(jīng)常有增刪操作，用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)較為合適，將每個(gè)人的情況作為一個(gè)元素（即一個(gè)結(jié)點(diǎn)存放一個(gè)人），設(shè)姓名作關(guān)鍵字，鏈表安排成有序表，這樣可提高查詢速度。16.試舉一例，說明對相同的邏輯結(jié)構(gòu),同一種運(yùn)算在不同的存儲(chǔ)方式下實(shí)現(xiàn)，其運(yùn)算效率不同。 【北京理工大學(xué) 2000 三、1（4.5分）】 線性表中的插入、刪除操作，在順序存儲(chǔ)方式下平均移動(dòng)近一半的元素，時(shí)間復(fù)雜度為O（n）；而在鏈?zhǔn)酱鎯?chǔ)方式下，插入和刪除時(shí)間復(fù)雜度都是O（1）。 17.有實(shí)現(xiàn)同一功能的兩個(gè)算法A1和A2，其中A1的時(shí)間復(fù)雜度為n2Tl=O(2)，A2的時(shí)間復(fù)雜度為T2=O(n)，僅就時(shí)間復(fù)雜度而言，請具體分析這兩個(gè)算法哪一個(gè)好。【北京航空航天大學(xué) 2000 二（10分）】 2n對算法A1和A2的時(shí)間復(fù)雜度T1和T2取對數(shù)，得nlog和2log。顯然，算法A2好于A1。 18．設(shè)計(jì)一數(shù)據(jù)結(jié)構(gòu)，用來表示某一銀行儲(chǔ)戶的基本信息： 賬號(hào)、姓名、開戶年月日、儲(chǔ)蓄類型、存入累加數(shù)、利息、帳面總數(shù)?！菊憬髮W(xué) 1994 一、3（5分）】 struct node {int year,month,day;};typedef struct {int num;//帳號(hào) char name[8];//姓名 struct node date;//開戶年月日 int tag;//儲(chǔ)蓄類型，如：0-零存，1-一年定期?? float put;//存入累加數(shù)； float interest;//利息 float total;//帳面總數(shù) }count； 19.寫出下面算法中帶標(biāo)號(hào)語句的頻度。 TYPE ar=ARRAY[1..n] OF datatype;PROCEDURE perm(a: ar;k, n: integer);VAR x: datatype;i:integer;BEGIN（1）IF k=n THEN BEGIN（2）FOR i:=1 TO n DO（3）write(a[i]);writeln;END ELSE BEGIN（4）FOR i:=k TO n DO（5）a[i]:=a[i]+i*i;（6）perm(a, k+1, n);END;END;設(shè)k的初值等于1。 【北京郵電大學(xué) 1997二（10分）】 (1)n (2)n+1(3)n(4)(n+4)(n-1)/2(5)(n+2)(n-1)/2(6)n-1 這是一個(gè)遞歸調(diào)用，因k的初值為1，由語句（6）知，每次調(diào)用k增1，故第(1)語句執(zhí)行n次。（2）是FOR循環(huán)語句，在滿足(1)的條件下執(zhí)行，該語句進(jìn)入循環(huán)體(3)n次，加上最后一次判斷出界，故執(zhí)行了n+1次。(4)也是循環(huán)語句，當(dāng)k=1時(shí)判斷n+1次（進(jìn)入循環(huán)體(5)n次），k=2時(shí)判斷n次，最后一次k=n-1時(shí)判斷3次，故執(zhí)行次數(shù)是（n+1）+n+?+3=(n+4)(n-1)/2次。語句(5)是(4)的循環(huán)體，每次比(4)少一次判斷，故執(zhí)行次數(shù)是n+(n-1)+?+2=(n+2)(n-1)/2次。注意分析時(shí)，不要把(2)分析成n次，更不是1次。 20.分析下面程序段中循環(huán)語句的執(zhí)行次數(shù)。 i:=0;s:=0;n:=100;REPEAT i:=i+1;s:=s+10*i;UNTIL NOT((i 四、1（5分）】（這時(shí)i=4，s=100）REPEAT語句先執(zhí)行循環(huán)體，后判斷條件，直到條件為真時(shí)退出循環(huán)。 21．下列算法對一n位二進(jìn)制數(shù)加1，假如無溢出，該算法的最壞時(shí)間復(fù)雜性是什么？并分析它的平均時(shí)間復(fù)雜性。 TYPE num=ARRAY [1..n] of [0..1]； PROCEDURE Inc（VAR a：num）； VAR i：integer； BEGIN i：=n； WHILE A[i]=1 DO BEGIN A[i]：=0； i：=i-1；END； END； A[i]：=1； END Inc； 【東南大學(xué)1998 三(8分)1994 二（15分）】 算法在最好情況下，即二進(jìn)制數(shù)的最后一位為零時(shí)，只作一次判斷，未執(zhí)行循環(huán)體，賦值語句A[i]執(zhí)行了一次；最壞情況出現(xiàn)在二進(jìn)制數(shù)各位均為1（最高位為零，因題目假設(shè)無溢出），這時(shí)循環(huán)體執(zhí)行了n-1次，時(shí)間復(fù)雜度是O(n)，循環(huán)體平均執(zhí)行n/2次，時(shí)間復(fù)雜度仍是O(n)。22.閱讀下列算法，指出算法A的功能和時(shí)間復(fù)雜性 PROCEDURE A(h,g:pointer);(h,g分別為單循環(huán)鏈表（single linked circular list）中兩個(gè)結(jié)點(diǎn)指針)PROCEDURE B(s,q:pointer)； VAR p:pointer;BEGIN p:=s;WHILE p^.next<>q DO p:=p^.next;p^.next:=s;END;(of B)BEGIN B(h,g);B(g,h);END;（of A） 【東南大學(xué) 1999 二（10分）】 該算法功能是將原單循環(huán)鏈表分解成兩個(gè)單循環(huán)鏈表：其一包括結(jié)點(diǎn)h到結(jié)點(diǎn)g的前驅(qū)結(jié)點(diǎn)；另一個(gè)包括結(jié)點(diǎn)g到結(jié)點(diǎn)h的前驅(qū)結(jié)點(diǎn)。時(shí)間復(fù)雜度是O(n)。 23.調(diào)用下列C函數(shù)f(n)或PASACAL函數(shù)f(n)回答下列問題 :（1）試指出f(n)值的大小，并寫出f(n)值的推導(dǎo)過程;（2）假定n= 5，試指出f(5)值的大小和執(zhí)行f(5)時(shí)的輸出結(jié)果。 C函數(shù)： int f(int n){ int i,j，k,sum= 0;for(i=l;i sum++;printf(“sum=%dn”,sum)； } return(sum);} 【華中理工大學(xué) 2000 六（10分）】 第一層FOR循環(huán)判斷n+1次，往下執(zhí)行n次，第二層FOR執(zhí)行次數(shù)為(n+(n-1)+(n-2)+?+1)，第三層循環(huán)體受第一層循環(huán)和第二層循環(huán)的控制，其執(zhí)行次數(shù)如下表： i= 1 2 3 ? n j=n n n n ? n j=n-1 n-1 n-1 n-1 ? ? ? ? ? j=3 3 3 j=2 2 2 j=1 1 2執(zhí)行次數(shù)為(1+2+?+n)+(2+3+?+n)+?+n=n*n(n+1)/2-n(n-1)/6。在n=5時(shí)，f(5)=55，執(zhí)行過程中，輸出結(jié)果為：sum=15,sum=29,sum=41,sum=50,sum=55（每個(gè)sum= 占一行,為節(jié)省篇幅，這里省去換行）。 24．設(shè)n是偶數(shù)，試計(jì)算運(yùn)行下列程序段后m的值并給出該程序段的時(shí)間復(fù)雜度。 m:=0;FOR i:=1 TO n DO FOR j:=2*i TO n DO m:=m+1;【南京郵電大學(xué) 2000 一、1】 2O(n),m的值等于賦值語句m:=m+1的運(yùn)行次數(shù)，其計(jì)算式為n2(n?2i?1)??4 i?1n/2 25．有下列運(yùn)行時(shí)間函數(shù)： 2（1）T1(n)=1000; （2）T2(n)=n+1000n; （3）32T3(n)=3n+100n+n+1;分別寫出相應(yīng)的大O表示的運(yùn)算時(shí)間。 23(1)O(1)(2)O(n)(3)O(n)【吉林工業(yè)大學(xué) 1999 二（12分）】 26.試給出下面兩個(gè)算法的運(yùn)算時(shí)間。 （1）for i←1 to n do x ← x+1 END（2）for i← 1 to n do for j←1 to n do x← x+1 end end 【中科院自動(dòng)化研究所 1995 二、2（6分）】 2(1)O(n)(2)O(n)27.斐波那契數(shù)列Fn定義如下 F0=0，F(xiàn)l=1，F(xiàn)n=Fn-1+Fn-2，n=2,3...請就此斐波那契數(shù)列，回答下列問題。 (1)(7分)在遞歸計(jì)算Fn的時(shí)候，需要對較小的Fn-1，F(xiàn)n-2，?, Fl, F0精確計(jì)算多少次? (2)(5分)如果用大O表示法，試給出遞歸計(jì)算Fn時(shí)遞歸函數(shù)的時(shí)間復(fù)雜度錄多少? 【清華大學(xué) 2000 二（12分）】（1）由斐波那契數(shù)列的定義可得： Fn=Fn-1+Fn-=2Fn-2+Fn-=3Fn-3+2Fn-=5Fn-4+3Fn-=8Fn-5+5Fn-6 …… =pF1+qF0 設(shè)Fm的執(zhí)行次數(shù)為Bm(m=0、1、2、?、n-1)，由以上等式可知，F(xiàn)n-1被執(zhí)行一次，即Bn-1=1；Fn-2被執(zhí)行兩次，即Bn-2=2；直至F1被執(zhí)行p次、F0被執(zhí)行q次，即B1=p，B0=q。Bm的執(zhí)行次數(shù)為前兩等式第一因式系數(shù)之和，即Bm=Bm-1+Bm-2，再有Bn-1=1和Bn-2=2，這也是一個(gè)斐波那契數(shù)列?？梢越獾茫?/p> 1?551?5n-m+2n-m+2Bm=5[(2)-(2)](m=0,1,2,?,n-1)（2）時(shí)間復(fù)雜度為O(n) 28．將下列函數(shù)，按它們在n→∝時(shí)的無窮大階數(shù)，從小到大排序。 ?2n???n??35n/231/2n ??,n!, n, n-n+7n, nlogn, 2, n, logn, n+logn,(3/2), n+logn 【中科院計(jì)算所 1995 080385】 1/22335從小到大排列為：logn, n+logn, n, nlogn, n+logn，n, n-n+7n, 2?2n?????n/2nn?? 2,(3/2), n!, 證券市場基礎(chǔ)知識(shí)試題點(diǎn)評（上） 單選題 題目1：根據(jù)我國《證券發(fā)行與承銷管理辦法》規(guī)定，首次公開發(fā)行股票以（）方式確定股票發(fā)行價(jià)格。 A:累計(jì)投標(biāo)詢價(jià) B:上網(wǎng)競價(jià) C:詢價(jià) √D:協(xié)商定價(jià) 題目2：關(guān)于證券公司融資融券證點(diǎn)的業(yè)務(wù)規(guī)則敘述錯(cuò)誤的是（）。 A:客戶融資買人或者融券賣出的證券預(yù)定終止交易，且最后交易日在融資債務(wù)到期日之前的，融資融券的期限縮短至最后交易日的前1交易日 B:證券公司向客戶融資，只能使用融資專用資金賬戶內(nèi)的資金；向客戶融券，只能使用融券專用證券賬戶內(nèi)的證券 C:客戶融資買人證券的，應(yīng)當(dāng)以賣券還款或者直接還款的方式償還向證券公司融人的資金；客戶融券賣出的，應(yīng)當(dāng)以買券還券或者直接還券的方式償還向證券公司融人的證券 D:證券公司以客戶的名義在證券登記結(jié)算機(jī)構(gòu)分別開立融券專用證券賬戶、客戶信用交易擔(dān)保證券賬戶、信用交易證券交收賬戶和信用交易資金交收賬戶√ 題目3：下列有關(guān)金融期貨敘述不正確的是（）。 A:金融期貨交易實(shí)行保證金制度和每日結(jié)算制度 B:金融期貨交易是非標(biāo)準(zhǔn)化交易 √ C:金融期貨必須在有組織的交易所進(jìn)行集中交易 D:在世界各國，金融期貨交易至少要受到1家以上的監(jiān)管機(jī)構(gòu)監(jiān)管，交易品種、交易者行為均需符合監(jiān)管要求 題目4：世界上第一個(gè)股票交易所于1602年在（）成立。 A:美國的紐約 B:德國的柏林 C:英國的倫敦 D:荷蘭的阿姆斯特丹 √ 題目5：以下不屬于金融期貨合約的基礎(chǔ)工具的是（）。 A:股價(jià)指數(shù) B:債券 C:外匯 D:商業(yè)票據(jù) √ 題目6：我國有關(guān)法規(guī)規(guī)定基金收益分配原則是（）。 A:基金收益分配后基金份額凈值可適當(dāng)?shù)陀诿嬷?/p> B:基金收益分配采取現(xiàn)金方式，每半年至少分配一次 C:基金收益分配比例不得低于基金凈收益的80％ D:基金當(dāng)年收益應(yīng)當(dāng)彌補(bǔ)上一虧損后，才可進(jìn)行當(dāng)年收益分配 √ 題目7：根據(jù)我國《證券法》和《證券交易所管理辦法》的規(guī)定，證券交易所設(shè)理事會(huì)，理事會(huì)是證券交易所的決策機(jī)構(gòu)，其主要職責(zé)是（）。 A:制定、修改證券交易所的業(yè)務(wù)規(guī)則 √ B:制定和修改證券交易所章程 C:審議和通過證券交易所的財(cái)務(wù)預(yù)算、決算報(bào)告 D:選舉和罷免會(huì)員理事 題目8：《中華人民共和國公司法》規(guī)定，股份公司向發(fā)起人、國家授權(quán)投資的機(jī)構(gòu)、法人發(fā)行的股票應(yīng)當(dāng)是（）。 A:不記名股票 √ B:國有股 C:普通股 D:記名股票 題目9：世界各國對證券公司的劃分和稱呼不盡相同，美國的通俗稱謂是（），在法律上統(tǒng)稱為“經(jīng)紀(jì)人一交易商”。 A:商人銀行B:投資公司C:商業(yè)銀行D:投資銀行 √ 題目10：專業(yè)的證券投資咨詢機(jī)構(gòu)、資信的評估機(jī)構(gòu)的業(yè)務(wù)人員，必須具備證券專業(yè)知識(shí)和從事證券業(yè)務(wù)（）年以上經(jīng)驗(yàn)。 A:5B:3C:2 √ D:1 題目11：按（）分類，國債可分為實(shí)物國債和貨幣國債。 A:償還期限B:發(fā)行本位 √C:資金用途 D:流通與否 題目12：下列說法錯(cuò)誤的是（）。 A:注冊制要求發(fā)行人提供關(guān)于證券發(fā)行本身以及和證券發(fā)行有關(guān)的一切信息 B:發(fā)行人不僅要完全公開有關(guān)信息，不得有重大遺漏，并且要對所提供信息的真實(shí)性，完整性和可靠性承擔(dān)法律責(zé)任 C:證券發(fā)行注冊制度實(shí)行公開管理制度，實(shí)質(zhì)上是一種發(fā)行公司的財(cái)務(wù)公布制度D:實(shí)行證券發(fā)行注冊制可以向投資者提供證券發(fā)行有關(guān)資料，并保證發(fā)行的證券資質(zhì)優(yōu)良、價(jià)格適當(dāng) √ 題目13：戰(zhàn)略投資者不得參與首次公開發(fā)行股票的初步詢價(jià)和累計(jì)投標(biāo)詢價(jià)并應(yīng)當(dāng)承諾獲得本次配售的股票持有期限不少于（）個(gè)月。 A:24B:6C:18 D:12 √ 題目14：實(shí)際上，大多數(shù)清算公司的清算價(jià)格總是（）賬面價(jià)值。 A:低于 √ B:等于 C:高于 D:無關(guān)于 題目15：債券遠(yuǎn)期交易數(shù)額最小為債券面額（）萬元。 A:1B:25C:5 D:10 √ 題目16：利率期貨于1975年10月產(chǎn)生于（）。 A:倫敦國際金融期貨交易所B:紐約交易所 C:芝加哥期貨交易所 √ D:歐洲交易所 題目17：通過滬深證券交易所系統(tǒng)發(fā)行和交易的債券是（）。 A:票券式債券 B:記賬式債券 √ C:憑證式債券 D:實(shí)物債券 題目18：以下不屬于債券類資產(chǎn)的遠(yuǎn)期合約的是（）。 A:支票 √ B:長期債券 C:商業(yè)票據(jù) D:短期債券 題目19：證券業(yè)協(xié)會(huì)的權(quán)力機(jī)構(gòu)是（）。 A:會(huì)員大會(huì) √B:主席大會(huì) C:股東大會(huì) D:董事會(huì) 題目20：下列說法正確的是（）。 A:股票型基金的托管費(fèi)率要低于債券型基金及貨幣市場基金的托管費(fèi)率 B:我國封閉式基金按照0．33％的比例計(jì)提基金托管費(fèi) C:我國開放式基金根據(jù)基金合同的規(guī)定比例計(jì)提，通常高于0．25％ D:托管費(fèi)通常按照基金資產(chǎn)凈值的一定比率提取，逐日計(jì)算并累計(jì)，按月支付給托管人 √ 題目21：我國《公司法》規(guī)定，公司的剩余資產(chǎn)在分配給股東之前，其支付順序?yàn)椋ǎ?。A:清算費(fèi)用、職工的工資、繳納所欠稅款、社會(huì)保險(xiǎn)費(fèi)用和法定補(bǔ)償金、清償公司債務(wù)B:清算費(fèi)用、繳納所欠稅款、社會(huì)保險(xiǎn)費(fèi)用和法定補(bǔ)償金、職工的工資、清償公司債務(wù)C:清算費(fèi)用、繳納所欠稅款、職工的工資、社會(huì)保險(xiǎn)費(fèi)用和法定補(bǔ)償金、清償公司債務(wù)D:清算費(fèi)用、職工的工資、社會(huì)保險(xiǎn)費(fèi)用和法定補(bǔ)償金、繳納所欠稅款、清償公司債務(wù) √ 題目22：對契約型基金認(rèn)識(shí)正確的是（）。 A:又稱為單位信托 √ B:基金的投資者購買基金公司的股票后成為該公司的股東C:基金的設(shè)立程序類似于一般股份公司，基金本身為獨(dú)立法人機(jī)構(gòu) D:依據(jù)基金公司章程營運(yùn)基金 題目23：2004年6月1日，以法律形式確認(rèn)了基金業(yè)在資本市場及社會(huì)主義市場經(jīng)濟(jì)中的地位和作用，成為中國基金業(yè)發(fā)展史上的一個(gè)重要里程碑的事件是（）正式實(shí)施。 A:《貨幣市場基金管理暫行辦法》 B:《中華人民共和國證券投資基金法》 √ C:《證券投資基金會(huì)計(jì)核算辦法》 D:《管理暫行辦法》 題目24：中國證券業(yè)協(xié)會(huì)自（）成立以來，共召開了（）次會(huì)員大會(huì)。 A:1991；2B:1990；2C:1991；4 √D:1992；4 題目25：公司不以任何資產(chǎn)作擔(dān)保而發(fā)行的債券是（）。 A:抵押公司債B:信用公司債 √C:保證公司債 D:信托公司債 題目26：按股東享有權(quán)利的不同，股票可以分為（）。 A:份額股票和比例股票 B:有面額股票和無面額股票 C:普通股票和優(yōu)先股票 √ D:記名股票和不記名股票題目 27：中央銀行在證券市場上買賣有價(jià)證券是在開展他的（）業(yè)務(wù)。 A:公開市場操作 √B:投融資 C:政策性 D:保值 題目28：不屬于證券發(fā)行公司信息披露的重要文件是（） A:招股說明書B:上市承諾書 √ C:上市公告書D:招股意向書 題目29：我國有關(guān)法律規(guī)定，公司繳納所得稅后的利潤，在支付普通股票的紅利之前，分配順序?yàn)椋ǎ?/p> A:彌補(bǔ)虧損、提取法定公積金、提取任意公積金 √ B:提取法定公積金、提取任意公積金、彌補(bǔ)虧損 C:提取任意公積金、提取法定公積金、彌補(bǔ)虧損 D:彌補(bǔ)虧損、提取任意公積金、提取法定公積金 題目30：我國《基金法》規(guī)定，基金托管人由依法設(shè)立并取得基金托管資格的（）擔(dān)任。 A:商業(yè)銀行 √B:信托投資公司 C:實(shí)力雄厚的證券公司 D:基金公司 題目31：關(guān)于《基金法》總則的主要內(nèi)容，下列說法不正確的是（）。 A:基金投資活動(dòng)遵循的原則、運(yùn)行方式 B:公司的性質(zhì)及股東承擔(dān)的責(zé)任 √ C:《基金法》的立法宗旨、適用范圍 D:從業(yè)人員的資格規(guī)定 題目32：在美國發(fā)行的外國證券稱為（）。 A:武士債券 B:揚(yáng)基債券 √ C:龍債券 D:熊貓債券 題目33：下列有關(guān)債券含義的說法中，不正確的有（）。 A:發(fā)行人是借入資金的主體 B:反映了二者之間的委托與受托關(guān)系 √ C:投資者是出借資金的經(jīng)濟(jì)主體 D:發(fā)行人需要還本付息 題目34：證券是指各類記載并代表一定（）的法律憑證。它用以證明持有人有權(quán)依其所持憑證記載的內(nèi)容而取得應(yīng)有的（）。 A:利益；權(quán)力B:權(quán)力；利益C:權(quán)益；權(quán)利D:權(quán)利；權(quán)益 √ 題目35：我國《證券法》規(guī)定，證券交易所設(shè)總經(jīng)理1人，其產(chǎn)生方式是（）。A:由理事會(huì)任免 B:由會(huì)員大會(huì)選舉產(chǎn)生 C:由理事會(huì)選舉產(chǎn)生 D:由國務(wù)院證券監(jiān)督管理機(jī)構(gòu)任免 √ 題目36：財(cái)政部于1998年9月向四大國有商業(yè)銀行定向發(fā)行了1000億元，年利率為5.5％，期限為10年的附息國債，專項(xiàng)用于國民經(jīng)濟(jì)和社會(huì)發(fā)展急需的基礎(chǔ)設(shè)施投入，該國債屬于（） A:財(cái)政債券 B:特別國債 C:國家重點(diǎn)建設(shè)債券 D:長期建設(shè)國債 √ 題目37：證券公司的注冊資本應(yīng)當(dāng)是（）。 A:貨幣資本 B:虛擬資本 C:實(shí)繳資本 √ D:金融資本 題目38：利通證券公司正在籌建中，計(jì)劃主要經(jīng)營證券經(jīng)紀(jì)和證券承銷與保薦業(yè)務(wù)，依據(jù)《中華人民共和國證券法》的規(guī)定，其應(yīng)有的最低注冊資本應(yīng)該為（） A:1億元 √ B:5億元 C:3000萬元 D:5000萬元 題目39：以（）為主的債券期貨是各主要交易所最重要的利率期貨品種。 A:地方政府債券指數(shù)期貨 B:交易所上市債券期貨 C:國債期貨 √ D:倫敦銀行間同業(yè)拆放利率期貨 題目40：（）是指經(jīng)核準(zhǔn)的基金份額在基金合同期限內(nèi)不變，基金份額可以在依法設(shè)立的證券交易場所交易，但基金份額持有人不得申請贖回的基金。 A:開放式基金 B:封閉式基金 √ C:公司型基金 D:契約型基金 題目41：我國公司法規(guī)定，發(fā)行無記名股票的公司應(yīng)當(dāng)于股東大會(huì)會(huì)議召開前（）日公告會(huì)議召開的時(shí)間、地點(diǎn)和審議事項(xiàng)。 A:15 B:7 C:30 √ D:10 題目42：目前我國貨幣市場基金能夠進(jìn)行投資的金融工具不包括（）。 A:可轉(zhuǎn)換債券 √ B:1年以內(nèi)（含1年）的銀行定期存款、大額存單 C:期限在1年以內(nèi)（含1年）的中央銀行票據(jù) D:現(xiàn)金 題目43：我國《上市公司證券發(fā)行管理辦法》規(guī)定，非公開發(fā)行股票，發(fā)行對象均屬于原前（）名股東的，可以由上市公司自行銷售。 A:10 √ B:15 C:20 D:25 題目44：證券公司在辦理經(jīng)紀(jì)業(yè)務(wù)時(shí)是作為（）。 A:中介人 √ B:投資人 C:信托人 D:委托人 題目45：證券發(fā)行的最后環(huán)節(jié)是將證券推銷給投資者。發(fā)行人推銷證券的方式不包括（）。 A:直銷 √ B:自銷 C:包銷 D:代銷 題目46：2005年對《公司法》進(jìn)行了修訂，有限責(zé)任公司的最低注冊資本額降低至人民幣（）萬元。 A:15 B:3 √ C:5 D:10 題目47：申請證券從業(yè)人員資格者，必須年滿（）歲。 A:19 B:20 C:18 √ D:21 題目48：（）制訂了《關(guān)于從事相關(guān)創(chuàng)新活動(dòng)證券公司評審暫行辦法》。 A:人民銀行 B:全國人大 C:中國證券協(xié)會(huì) √ D:中國證監(jiān)會(huì) 題目49：B股是指（）。 A:香港上市外資股 B:紐約上市外資股 C:境內(nèi)上市外資股 √ D:境外上市外資股 題目50：關(guān)于股票性質(zhì)的描述，正確的是（）。 A:股票是設(shè)權(quán)證券 B:股票所代表的權(quán)利本來不存在C:股票只是把已存在的權(quán)利表現(xiàn)為證券的形式 √ D:股票所代表的權(quán)利的發(fā)生是以股票的制作和存在為條件的題目51：目前我國金融債券的最長年限為（）年。 A:20 B:10C:30 √ D:15 題目52：以下不屬于公司債券的是（）。 A:附有股權(quán)證的公司債券 B:混合資本債券 √ C:短期融資券 D:信用公司債券 題目53：股票是投入股份公司資本份額的證券化，由此可見股票屬于（）。A:物權(quán)證券 B:要式證券 C:綜合權(quán)利證券 D:資本證券 √ 題目54：政府證券不包括（）。 A:經(jīng)批準(zhǔn)的政府機(jī)構(gòu)發(fā)行的證券 B:地方政府發(fā)行的債券 C:金融債券 √ D:國債 題目55：證券包銷是指（） A:證券公司將發(fā)行人的證券按照協(xié)議全部購人的承銷方式 B:證券公司將發(fā)行人的證券按照市場價(jià)格全部購入，或者在承銷期結(jié)束時(shí)將售后剩余證券全部退回的承銷方式 C:證券公司在承銷期結(jié)束時(shí)將售后剩余證券全部自行購人的承銷方式 D:證券公司將發(fā)行人的證券按照協(xié)議全部購入，或者在承銷期結(jié)束時(shí)將售后剩余證券全部自行購人的承銷方式 √ 題目56：證券公司經(jīng)營證券經(jīng)紀(jì)業(yè)務(wù)的風(fēng)險(xiǎn)控制指標(biāo)標(biāo)準(zhǔn)錯(cuò)誤的是（）。 A:證券公司經(jīng)營證券承銷與保薦、證券自營、證券資產(chǎn)管理、其他證券業(yè)務(wù)中兩項(xiàng)及兩項(xiàng)以上的，其凈資本不得低于人民幣5億元√ B:證券公司經(jīng)營證券承銷與保薦、證券自營、證券資產(chǎn)管理、其他證券業(yè)務(wù)等業(yè)務(wù)之一的，其凈資本不得低于人民幣5000萬元 C:證券公司經(jīng)營證券經(jīng)紀(jì)業(yè)務(wù)的，其凈資本不得低于人民幣2000萬元 D:證券公司經(jīng)營證券經(jīng)紀(jì)業(yè)務(wù)，同時(shí)經(jīng)營證券承銷與保薦、證券自營、證券資產(chǎn)管理、其他證券業(yè)務(wù)等業(yè)務(wù)之一的，其凈資本不得低于人民幣1億元 題目57：以下不屬于證券市場顯著特征的是（）。 A:證券市場是價(jià)值直接交換的場所 B:證券市場是風(fēng)險(xiǎn)直接交換的場所 C:證券市場是財(cái)產(chǎn)權(quán)利直接交換的場所 D:證券市場是價(jià)值實(shí)現(xiàn)增值的場所 √ 題目58：在20世紀(jì)80年代，圍繞市場風(fēng)險(xiǎn)管理進(jìn)行的風(fēng)險(xiǎn)轉(zhuǎn)移型金融創(chuàng)新最為流行，其典型代表不包括（）。A:互換 B:期權(quán) C:期貨 D:遠(yuǎn)期 √ 題目59：（）年被稱為“中國資產(chǎn)證券化元年”。 A:2005 √ B:2004 C:2003 D:2006 題目60：關(guān)于規(guī)范類證券公司的評審，下列說法不正確的是（）。 A:向中國證券業(yè)協(xié)會(huì)報(bào)送申請材料時(shí)，申請?jiān)u審的公司應(yīng)不存在挪用或占用客戶交易結(jié)算資金的情況 B:申請?jiān)u審的證券公司最近1年凈資本不低于凈資產(chǎn)的50％ C:申請?jiān)u審的證券公司根據(jù)不同的業(yè)務(wù)范圍，近3年的凈資本達(dá)到相應(yīng)的規(guī)定要求 √ D:摸清風(fēng)險(xiǎn)底數(shù)第二篇：數(shù)據(jù)結(jié)構(gòu)試題及答案
第三篇：2014考研數(shù)據(jù)結(jié)構(gòu)變化
第四篇：數(shù)據(jù)結(jié)構(gòu)考研真題及其答案
第五篇：證券市場基礎(chǔ)知識(shí)試題點(diǎn)評
點(diǎn)擊咨詢 