c語言資料結構自測題,C語言資料結構複習題.doc

C語言資料結構複習題.doc

一、單選題1. 在資料結構中，從邏輯上可以把資料結構分為( )。A動态結構和靜态結構 B緊湊結構和非緊湊結構C線性結構和非線性結構D内部結構和外部結構2. 算法具備輸入，輸出和( )等五個特性A.可行性，可移植性和可擴充性 B.可行性，确定性和有窮性C.确定性，有窮性和穩定性 D.易讀性，穩定性和安全性3. 連結清單不具備的特點是( )。A可随機通路任一結點B插入删除不需要移動元素C不必事先估計存儲空間D所需空間與其長度成正比4線性表是( )。 A一個有限序列，可以為空B一個有限序列，不可以為空C一個無限序列，可以為空D一個無限序列，不可以為空5下面關于線性表的叙述中，錯誤的是哪一個 ( )。A線性表采用順序存儲，必須占用一片連續的存儲單元B線性表采用順序存儲，便于進行插入和删除操作。C線性表采用鍊式存儲，不必占用一片連續的存儲單元D線性表采用鍊式存儲，便于進行插入和删除操作。6以下關于線性表的說法不正确的是()。A線性表中的資料元素可以是數字、字元、記錄等不同類型。B線性表中包含的資料元素個數不是任意的。C線性表中的每個結點都有且隻有一個直接前趨和直接後繼。D存在這樣的線性表表中各結點都沒有直接前趨和直接後繼。7設有一個棧，元素的進棧次序為A, B, C, D, E,下列是不可能的出棧序列()。 AA, B, C, D, E BB, C, D, E, ACE, A, B, C, D DE, D, C, B, A8在一個具有n個單元的順序棧中，假定以位址低端(即0單元)作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為()。 Atop不變 Btop0 Ctop Dtop9在循環隊列中，若front與rear 分别表示對頭元素和隊尾元素的位置，則判斷循環隊列空的條件是()。Afrontrear1 Brearfront1 Cfrontrear Dfront010若INDEX(S，T)表示求T在S中的位置的操作，則對于S“BeijingNanjing”，T“jing”，INDEX(S，T)()。A.2 B.3 C.4 D.511串是一種特殊的線性表，其特殊性展現在()。A可以順序存儲B資料元素是一個字元C可以鍊式存儲D資料元素可以是多個字元12稀疏矩陣一般的壓縮存儲方法有兩種，即()。A.二維數組和三維數組 B.三元組和散列C.三元組和十字連結清單 D.散列和十字連結清單13對矩陣進行壓縮存儲是為了()。A友善運算B友善存儲C提高運算速度 D減少存儲空間14假設在一棵二叉樹中，雙分支結點數為15，單分支結點數為30個，則葉子結點數為()個。A. 15 B. 16 C. 17 D. 4715樹最适合用來表示( )。A有序資料元素B無序資料元素C元素之間具有分支層次關系的資料D元素之間無聯系的資料16根據先序序列ABDC(根左右)和中序序列DBAC(左根右)确定對應的二叉樹，該二叉樹( )。A. 是完全二叉樹 AB. 不是完全二叉樹 B CC. 是滿二叉樹D D. 不是滿二叉樹 17已知一棵完全二叉樹的結點總數為9個，則最後一層的結點數為 。A. 1 B. 2 C. 3 D. 4 12 34 5 6 78 918對于一個無向圖，下面 種說法是正确的。A. 每個頂點的入度等于出度 B. 每個頂點的度等于其入度與出度之和C. 每個頂點的入度為0 D. 每個頂點的出度為019對于長度為18的順序存儲的有序表，若采用折半查找，則查找第15個元素的比較次數為 。A. 3 B. 4 C. 5 D. 620若要對1000個元素排序，要求既快又節省存儲空間，則最好采用( )方法。A. 直接插入排序B. 歸并排序C. 堆排序D. 快速排序二、判斷題1. 順序存儲方式隻能用于存儲線性結構。( F )2. 已知指針P指向鍵表L中的某結點，執行語句PP.next不會删除該連結清單中的結點。( T )3. 隊列是一種插入和删除操作分别在表的兩端進行的線性表，是一種先進後出的結構。( F )4.如果一個串中的所有字元均在另一串中出現，則說前者是後者的子串。( F )5. 用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小隻與圖中結點個數有關，而與圖的邊數無關。( T )6.快速排序是不穩定排序。( T )7. 在哈夫曼樹中，權值最小的結點離根結點最近。( F )8.若圖G的最小生成樹不唯一，則G的邊數一定多于n-1，并且權值最小的邊有多條(其中n為G的頂點數)。( T )9.給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。( F )10.冒泡排序算法關鍵字比較的次數與記錄的初始排列次序無關。( F )三、填空題1資料的邏輯結構有四種基本形态，分别是集合、 線性表 、樹和圖。2. 一個算法的效率可分為時間效率和 空間 效率。3在單連結清單中，要删除某一指定的結點，必須找到該結點的( 前驅 )結點。4當對一個線性表經常進行插入和删除操作時，采用 鍊式 存儲結構為宜。5對于隊列而言，隻能在( 隊尾 )位置插入元素。7稀疏矩陣一般的壓縮存儲方法有兩種，即( 三元組 )和十字連結清單。8 在一棵二叉樹中，度為零的結點的個數為n0，度為2 的結點的個數為n2，則有n0( n21 )。9. 三叉連結清單比二叉連結清單多一個指向( 雙親 )的指針域。10. 具有10個頂點的無向圖，邊的總數最多為( 45)。NN-1/2四、綜合應用題要點1.二叉樹先序周遊、中序周遊、後序周遊 根左右 左根右 左右根要點2.哈夫曼樹的生成 排序 選數 連接配接最小的數 比較 要點3.森林和二叉樹的互相轉換 要點4.将圖轉換成最小生成樹要點5.根據稀疏矩陣對應的三元組線性表，畫出稀疏矩陣要點6.根據無向圖或者有向圖的鄰接表，畫出無向圖或者有向圖要點7.求最短路徑的Dijkstra算法五、算法設計題。要點着重關注單連結清單的基本操作(資料插入、删除、判斷單連結清單是否為空，傳回單連結清單元素個數等)，棧或者隊列兩種結構鍊式或者順序存儲結構定義中的方法。比如出棧(隊列)、進棧(隊列)，擷取棧(隊列)首元素，判斷棧(隊列)是否為空等等。includestdio.hdefine MAXSIZE 20 define OK 1define ERROR 0typedef int Status; typedef int ElemType;typedef structElemType dataMAXSIZE;int length; 線性表中元素個數SqList;初始化線性表SqList InitListSqList L;L.length0;return L;插入元素Status ListInsertSqList *L,int i,ElemType eint k;ifL-lengthMAXSIZE i0 iL-lengthreturn ERROR;forkL-length-1;ki;kL-datak1L-datak;L-dataie;L-length;return OK;擷取元素ElemType GetElemSqList L,int iifL.length0 i0 iL.length-1printf位置錯誤;return L.datai;删除元素Status ListDeleteSqList *L,int i,ElemType *eint k;ifL-length0 i0 iL-length-1return ERROR;*eL-datai;forki;kL-length;kL-datak-1L-datak;L-length;return OK;清空線性表void ClearListSqList *LL-length0;判斷線性表是否為滿Status ListFullSqList LifL.lengthMAXSIZEreturn OK;elsereturn ERROR;判斷線性表是否為空Status ListFullSqList LifL.length0return OK;elsereturn ERROR;int mainStatus x;ElemType y,*e,z;SqList LInitList;ListInsertListInsertListInsertyGetElemL,1;e ListDeletezGetElemL,1;printfdn,z;ClearListreturn 1;