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