《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)題

《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)題一、判斷題1（ ）一個算法可以沒有輸入，但不能沒有輸出。2（ ）數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。3（ ）鏈表是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性進(jìn)行插入、刪除操作時，在鏈表中比在順序儲結(jié)構(gòu)中效率高。4（ ）棧和隊列邏輯上都是線性表。5（ ）若輸入序列為1,2,3,4,5,6,則通過一個棧可以輸出序列3,2,5,6,4,1。6（ ）隊列在數(shù)據(jù)中的存儲原則是后進(jìn)先出。7（ ）數(shù)組是同類型值的集合。8（ ）無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣是不對稱的。9（ ）查找成功與否的關(guān)鍵在于是否按主關(guān)鍵字查找。10（ 排序是計算機程序設(shè)計中的一種重要操作它的功能是將一個數(shù)據(jù)元（或記錄的任意序列，重新排列成一個按關(guān)鍵字有序的序列。1（ ）線性表的邏輯順序與物理順序總是一致的。2（ ）線性表的順序存儲表示優(yōu)于鏈?zhǔn)酱鎯Ρ硎尽?（ ）深度為h第i層最多有2i-1個結(jié)點。4（ ）棧和隊列邏輯上都是線性表。5（ ）一般樹和二叉樹的結(jié)點數(shù)目都可以為。6（ ）隊列在數(shù)據(jù)中的存儲原則是后進(jìn)先出。7（ ）給定一組權(quán)值，可以唯一構(gòu)造出一棵哈夫曼樹。二、選擇題1、在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為（ 。A內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu) B靜態(tài)結(jié)構(gòu)與動態(tài)結(jié)構(gòu)C線性結(jié)構(gòu)與非線性結(jié)構(gòu) D緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)2、算法指的是（ 。A計算機程序 B解決問題的計算方法C排序算法 D解決問題的有限運算序列3、線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址（ ）A必須是不連續(xù)的 B連續(xù)與否均可C必須是連續(xù)的 D和頭結(jié)點的存儲地址相連續(xù)4a[10][10a[2][0的地址為4a[1][0]的地址為（ 。A520 B522C524 D5185、樹最適合用來表( )。A有序數(shù)據(jù)元素B無序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù)D元素之間無聯(lián)系的數(shù)據(jù)6、計算機識別、存儲和加工處理的對象被統(tǒng)稱 A數(shù)據(jù) B數(shù)據(jù)元素C數(shù)據(jù)結(jié)構(gòu) D數(shù)據(jù)類型7、設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)( )條邊才能確保是一個連通圖。A5 B6C7 D88、二叉樹中第5層上的結(jié)點個數(shù)最多 A8 B15C16 D329、當(dāng)采用分快查找時，數(shù)據(jù)的組織方式為( )A．?dāng)?shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊C.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊D.數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個數(shù)需相同10、順序查找方法的優(yōu)點之一( )A適合排序連續(xù)順序文件的查找B對于被查找的對象幾乎沒有限制C適合鏈接順序文件的查找D查找時間效率高1、數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（）以及對數(shù)據(jù)的各種操作。A存儲和邏輯結(jié)構(gòu) B存儲和抽C理想和抽象 D理想與邏2、在堆棧中存取數(shù)據(jù)的原則是（）A先進(jìn)先出 B后進(jìn)先出C后進(jìn)后出 D隨意進(jìn)出3、將一棵有100個結(jié)點的完全二叉樹從上到下，從左到右依次對結(jié)點進(jìn)行編號，根結(jié)點編號為1，則編號為49的結(jié)點的左孩子的編號。A98 B99 C50 D484、圖的深度優(yōu)先遍歷類似于二叉樹。A先序遍歷 B中序遍歷C后序遍歷 D層次遍歷5、設(shè)單鏈表中結(jié)點的結(jié)構(gòu)為typedefstructnode 鏈表結(jié)點定義{ElemTypedata；//數(shù)據(jù)structnode*Link；//結(jié)點后繼指針}ListNode；已知指針p所指結(jié)點不是尾結(jié)點，若在*p之作后插入 。結(jié)點*s，則應(yīng)執(zhí)行下列哪一個操Ak=；k=； Bk=kk=；Cs->link=p->link；p=s；D p->link=s->link=三、填空題1、數(shù)據(jù)結(jié)構(gòu)課程研究的主要內(nèi)容包括邏輯結(jié)構(gòu)和算法三個方面。2、線性表的常見鏈?zhǔn)酱鎯Y(jié)構(gòu)、雙向鏈表、循環(huán)鏈表。3、若頻繁地對線性表進(jìn)行插入與刪除操作，該線性表應(yīng)采存儲結(jié)構(gòu)。4、通常像交通、道路問題的數(shù)學(xué)模型是一種稱的數(shù)據(jù)結(jié)構(gòu)。5、在棧的順序?qū)崿F(xiàn)中，棧頂指針棧為空條。6、順序查找n個元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多次。7、設(shè)有一個行優(yōu)先順序存儲的數(shù)組A[5][6]，A[0][0]的地址為且每個元素占2個儲單元，則A[2][3]的地址。度數(shù)為0的結(jié)點即沒有子樹的結(jié)點叫結(jié)點結(jié)點同一個結(jié)的兒子結(jié)點之間互稱結(jié)點。9、散列法存儲的基本思想是決定數(shù)據(jù)的存儲地址。10排序是指將無序的數(shù)據(jù)元素序列轉(zhuǎn)變成一個有序序列把序列中的記錄通過某些方整理遞增或遞減次序排列的處理過程。1《數(shù)據(jù)結(jié)構(gòu)》課程討論的主要內(nèi)容是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)。2、一個算法應(yīng)該具，確切性，可行性，輸入和輸出。3、若頻繁地對線性表進(jìn)行插入與刪除操作，該線性表應(yīng)采存儲結(jié)構(gòu)。4、鏈?zhǔn)酱鎯Y(jié)構(gòu)中的結(jié)點包域。5、在棧的順序?qū)崿F(xiàn)中，棧頂指針棧為空條件 。6、允許在線性表的一端插入，另一端進(jìn)行刪除操作的線性表稱為 ，刪除的一端。

。插入的一端為7、設(shè)有一個行優(yōu)先順序存儲的數(shù)組A[5][6]，A[0][0]的地址為且每個元素占2個儲單元，則A[2][3]的地址。度數(shù)為0的結(jié)點即沒有子樹的結(jié)點叫結(jié)點結(jié)點同一個結(jié)的兒子結(jié)點之間互稱結(jié)點。四、程序題1、寫出下列程序段的輸出結(jié)果。voidmain(){StackS;charx,y;x=’c’;y=’k’;push(S,x);push(S,’a’); push(S,y);pop(S,x);push(S,’t’);push(S,x);pop(S,x);push(S,’s’);while(!StackEmpty(S)){pop(S,y);printf(y);};printf(x);}結(jié)果 2、寫出下列程序段的輸出結(jié)果（隊列中的元素類型QElemType為r。voidmain(){QueueQ; InitQueue(Q);Charx=’e’;y=’c’;EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,’y’);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,’a’);while(!QueueEmpty(Q)){}結(jié)果

DeQueue(Q,y);printf(y);};Printf(x);3、完成下列程序,并說出該算法所完成的功能。voidweizhisort(structnoder[n],intn){intlow,high,mid,j,i;for(i=2;i<=n;i++){r[0]=r[i];low=①;high=②;while(low<=high){mid=(low+high)/2;if(r[0].key<r[mid].key) ;elselow=mid+1;}for(j=i-1;j>=l;j--)r[j+1]=r[j];r[low]=r[0];}}4、完成二叉樹中序遍歷的算法。typedefstructnode/*鏈?zhǔn)酱鎯Φ闹羔橆愋秃徒Y(jié)點定義*/{chardata;structnode*lchild,*rchild;}BTnode;void inorder(BTnode*bt) /**/{if(bt!=NULL){ ;printf("%c",bt->data); }}五、應(yīng)用題1、分別寫出二叉樹的前序遍歷和中序遍歷序列（6'）先序遍歷：ABDECFGH中序遍歷：DBEAGHFC后序遍歷:DEBHGFCA2、AOE（ActivityOnE