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

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