《數(shù)據(jù)結(jié)構(gòu)》模擬題.doc

班級 姓名 學(xué)號 2011/2012學(xué)年第二學(xué)期數(shù)據(jù)結(jié)構(gòu)練習(xí)題 一、 單選題（每小題2分，共30分）（1）下列對算法要求不必考慮的是（ ）。A 正確性 B 可讀性 C 高效率 D 計(jì)算機(jī)硬件 （2）當(dāng)一個函數(shù)無返回值時，函數(shù)的類型應(yīng)為（ ）。A. 任意B. voidC. intD. char（3）循環(huán)while(i=0) i-；執(zhí)行次數(shù)是（ ）A. 0 B. 1 C. 5 D. 無限（4）在一個單鏈表HL中，若要在指針p所指結(jié)點(diǎn)的后面插入一個由指針q所指向的結(jié)點(diǎn)，則執(zhí)行( )。 A q一next=p一next；p一next=p； B p一next=q一next；q=p； C q一next=p一next；p一next=q； D p一next=q一next；q一next=p；（5）下面程序段的時間復(fù)雜度為( )。 for(int i=0; im; i+) for(int j=0; jnext=NULL; C first-next=first; D first!=NULL;（10）在一棵完全二叉樹中，若樹根結(jié)點(diǎn)的編號為0，對于編號為i(i0)的結(jié)點(diǎn)，其雙親結(jié)點(diǎn)的編號為( )。 A (i+1)/2 B (i-1)/2 C i/2 D i/2-1（11）下列符號中能夠作為 C+標(biāo)識符（變量名）的是_ Aconst B.2a C._shape D.-count（12）有定義： int a5=1,3,5,7,9,*p=a;那么下列表達(dá)式中不能得到數(shù)值 5 的是（ ） A）a2 B）a3 C）*(p+2) D）*p+4（13）下列陳述中正確的是( )。 A 二叉樹是度為2的有序樹 B 二叉樹中結(jié)點(diǎn)只有一個孩子時無左右之分C 二叉樹中必有度為2的結(jié)點(diǎn) D 二叉樹中最多只有兩棵子樹，并且有左右之分（14）下面概念中，不屬于面向?qū)ο蟾拍畹氖?A)對象 B)繼承 C)類 D)過程調(diào)用（15）對具有八個元素的序列(49,38,65,97,76,13,27,50)按從小到大排序，( )是直接選擇排序法第一趟的結(jié)果。A 13,65,38,97,76,49,27,50 B 13,27,38,49,50,65,76,97C 97,76,65,50,49 38,27,13 D 13,38,65,97,76,49,27,50二、填空題（每小題1分，共15分）1. 樹的常用存儲結(jié)構(gòu)是：雙親表示法、孩子表示法、雙親孩子表示法和_ _。2. 算法效率的估量有兩種方法： 和事后統(tǒng)計(jì)。3. 在面向?qū)ο蟮某绦蛟O(shè)計(jì)中，將數(shù)據(jù)和處理數(shù)據(jù)的操作封裝成一個整體就定義了一種事物的類型，稱作“類”。類是一種抽象的概念，屬于該類的一個實(shí)例叫做_。4. 對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復(fù)雜度為 。5. 在類的對象被創(chuàng)建的時候，_構(gòu)造_函數(shù)會被自動調(diào)用。6. 樹的帶權(quán)路徑長度最小的二叉樹稱做 最優(yōu)二叉樹 。7. 深度為k的二叉樹至多有 2k-1 個結(jié)點(diǎn)。8. 將個函數(shù)聲明為一個類的友元函數(shù)必須使用關(guān)鍵字 friend 。9. 樹的深度是指 每個節(jié)點(diǎn)孩子的最大數(shù)量 。10. 棧是一種 先進(jìn)后出的特殊 線性表。11. 數(shù)據(jù)在計(jì)算機(jī)中的存放方式稱為數(shù)據(jù)的_存儲結(jié)構(gòu)_。12. 關(guān)鍵字序列(52，80，63，44，48，91)進(jìn)行一趟快速排序之后得到的結(jié)果為_4844526381091 _。13. 鏈表是一種采用 鏈?zhǔn)?存儲結(jié)構(gòu)存儲的線性表。14. 有序順序表上的查找算法主要有順序查找和 鏈?zhǔn)讲檎?。15. 插入排序和快速排序，排序方法不穩(wěn)定的是_快速_。三、判斷題（正確的打P，錯誤的打。每小題2分，共20分）1. 在順序表中取出第J個元素所花的時間與J大小有關(guān)。（ 0 ）2. 任何一棵二叉樹中至少有一個結(jié)點(diǎn)的度為2。（ 1 ）3. 靜態(tài)查找表主要有順序表、有序順序表和索引順序表三種結(jié)構(gòu)。（ 1 ）4. 對具有n個元素的序列采用冒泡排序法進(jìn)行排序，最多需要的排序趟數(shù)為n-1。（ 1 ）5. 隊(duì)列的特點(diǎn)是要求在隊(duì)頭插入數(shù)據(jù)元素。（ 0 ）6. 線性表采用順序存儲結(jié)構(gòu)，每個數(shù)據(jù)元素占用4個存儲單元，第12個數(shù)據(jù)元素的存儲地址為144，則第1個數(shù)據(jù)元素的存儲地址是101。（ 1 ）7. 冒泡排序算法在最壞情況下的時間復(fù)雜度為0(n)。（ 0 ）8. 將一棵樹轉(zhuǎn)換為二叉樹表示后,該二叉樹的根結(jié)點(diǎn)沒有右子樹。（ 0 ）9. 滿二叉樹一定是完全二叉數(shù)，而完全二叉樹不一定是滿二叉樹。（ 1 ）10. 主關(guān)鍵字是能夠惟一區(qū)分各個不同數(shù)據(jù)元素的關(guān)鍵字。（ 1 ）四、（6分）已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECDFGHIJ，中序遍歷的結(jié)果序列是EBCDAFHIGJ。（1）畫出這棵二叉樹并寫出后序遍歷結(jié)果。五、（5分）假定用于通信的電文由8個字母a,b,c,d,e,f,g,h組成，各字母在電文中出現(xiàn)的頻率分別為5，15，9，26，10，11，20，4。試為這8個字母設(shè)計(jì)Huffman編碼，并畫出相應(yīng)的Huffman樹。六、算法設(shè)計(jì)題（每小題8分，共24分）1. 為順序表類（SeqList）編寫實(shí)現(xiàn)順序表就地逆置的成員函數(shù)，即要求利用原順序表的存儲單元，把數(shù)據(jù)元素序列（a0,a1,an-1）逆置為（an-1,a1,a0），順序表類的定義如下。class SeqList protected:DataType * list;int maxSize;int size;public:SeqList(int max=0);SeqList();int Size(void) const;void Insert(const DataType& item,int i);DataType Delete(const int i);DataType GetData(int i)const;2. 利用堆棧和隊(duì)列的特性編寫判斷一個字符序列是否是回文的函數(shù)，并設(shè)計(jì)一個主函數(shù)對字符序列“ABCDEDCBA”和“ABCDEDBAC”進(jìn)行測試，堆棧和隊(duì)列的類定義如下typedef int DataType;const int MaxQueueSize=100;class SeqQueueprivate:DataType dataMaxQueueSize;int front;int rear;int count;public:SeqQueue(void)front=rear=0;count=0;SeqQueue(void)void Append(const DataType& item);DataType Delete(void);DataType GetFront(void)const;int NotEmpty(void)constreturn count!=0;class SeqStackprivate:DataType dataMaxStackSize;int Top;public:SeqStack(void)Top=0;SeqStack(void)void Push(const DataType item);DataType Pop(void);DataType GetTop(void)const;int NotEmpty(void)const return Top!=0;。3. 編寫直接插入排序算法的InsertSort函數(shù)將若干整數(shù)按從小到大排序，（測試用的主函數(shù)見下面）。#include typ