河北地質大學數據結構期末考試題及答案

⑴ 尋一份《數據結構》試題及答案

《數據結構》試題一、選擇題（每小題2分，共30分）1． 若某線性表中最常用的操作是取第i 個元素和找第i個元素的前趨元素，則採用（ ）存儲方式最節省時間。A、單鏈表 B、雙鏈表 C、單向循環 D、順序表2． 串是任意有限個（ ）A、符號構成的序列 B、符號構成的集合C、字元構成的序列 D、字元構成的集合3． 設矩陣A（aij ，l≤i,j≤ 10）的元素滿足：aij≠0(i≥j, l≤i, j≤ 10)aij=0 (i<j, l≤i, j≤ 10)現將A的所有非0元素以行序為主序存放在首地址為2000的存儲區域中，每個元素佔有4個單元，則元素A[9][5]的首址為A、2340 B、2336 C、2164 D、21604． 如果以鏈表作為棧的存儲結構，則退棧操作時（ ）A、 必須判別棧是否滿 B、 對棧不作任何判別C、 必須判別棧是否空 D、 判別棧元素的類型5． 設數組Data[0..m]作為循環隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執行出隊操作的語句為（ ）A、front=front+1 B、front=(front+1)% mC、rear=(rear+1)%m D、front=(front+1)%(m+1)6． 深度為6（根的層次為1）的二叉樹至多有（ ）結點。A、 64 B、32 C、31 D、637． 將含100個結點的完全二叉樹從根這一層開始，每層上從左到右依次對結點編號，根結點的編號為1。編號為49的結點X的雙親編號為（ ）A、24 B、25 C、23 D、無法確定8． 設有一個無向圖G=（V，E）和G』=（V』，E』）如果G』為G的生成樹，則下面不正確的說法是（ ）A、G』為G 的子圖 B、G』為G 的邊通分量C、G』為G的極小連通子圖且V』=V D、G』為G的一個無環子圖9． 用線性探測法查找閉散列表，可能要探測多個散列地址，這些位置上的鍵值（ ）A、 一定都是同義詞 B、一定都不是同義詞 C、都相同 D、不一定都是同義詞10． 二分查找要求被查找的表是（ ）A、 鍵值有序的鏈接表 B、鏈接表但鍵值不一定有序C、 鍵值有序的順序表 D、順序表但鍵值不一定有序11． 當初始序列已經按鍵值有序，用直接插入演算法對其進行排序，需要循環的次數為（ ）A、n2 B、nlog2n C、log2n D、n-1 12． 堆是一個鍵值序列{k1,k2,…, kn},對i=1,2,…,|_n/2_|,滿足( )A、ki≤k2i≤k2i+1 B、ki<k2i+1<k2iC、ki≤k2i且ki≤k2i+1(2i+1≤n) D、ki≤k2i 或ki≤k2i+1(2i+1≤n) 13．一個具有n個頂點的無向完全圖的邊數為（ ）A、n(n+1)/2 B、n(n-1)/2 C、n(n-1) D、n(n+1)14．在索引順序表中查找一個元素，可用的且最快的方法是（ ）A、用順序查找法確定元素所在塊，再用順序查找法在相應塊中查找B、用順序查找法確定元素所在塊，再用二分查找法在相應塊中查找C、用二分查找法確定元素所在塊，再用順序查找法在相應塊中查找D、用二分查找法確定元素所在塊，再用二分查找法在相應塊中查找15．若某線性表中最常用的操作是在最後一個元素之後插入一個元素和刪除最後一個元素，則採用（ ）存儲方式最節省運算時間。A、 單鏈表 B、雙鏈表C、帶頭結點的雙循環鏈表D、容量足夠大的順序表 二、判斷題（每小題1分，共10分）1．雙鏈表中至多隻有一個結點的後繼指針為空。（ ）2．在循環隊列中，front指向隊列中第一個元素的前一位置，rear指向實際的隊尾元素，隊列為滿的條件是front=rear。（ ）3．對鏈表進行插入和刪除操作時，不必移動結點。（ ）4．棧可以作為實現程序設計語言過程調用時的一種數據結構。（ ）5．在一個有向圖的拓樸序列中，若頂點a在頂點b之前，則圖中必有一條弧<a,b>。( )i6．對有向圖G，如果從任一頂點出發進行一次深度優先或廣度優先搜索就能訪問每個頂點，則該圖一定是完全圖。( )7．「順序查找法」是指在順序表上進行查找的方法。（ ）8．向二叉排序樹插入一個新結點時，新結點一定成為二叉排序樹的一個葉子結點。（）9．鍵值序列{A，C，D，E，F，E，F}是一個堆。10．二路歸並時，被歸並的兩個子序列中的關鍵字個數一定要相等。（） 三、填空題（每小題2分，共20分）1．在帶有頭結點的單鏈表L中，若要刪除第一個結點，則需執行下列三條語句：＿＿＿＿＿＿＿＿；L->next=U->next；free(U)；2．有一個長度為20的有序表採用二分查找方法進行查找，共有＿＿＿＿＿＿個元素的查找長度為3。3．採用冒泡排序對有n個記錄的表A按鍵值遞增排序，若L的初始狀態是按鍵值遞增，則排序過程中記錄的比較次數為＿＿＿＿＿。若A的初始狀態為遞減排列，則記錄的交換次數為＿＿＿＿＿＿＿。4．在無頭結點的雙鏈表中，指針P所指結點是第一個結點的條件是＿＿＿＿＿＿。5．G為無向圖，如果從G的某個頂點出發，進行一次廣度優先搜索，即可訪問圖的每個頂點，則該圖一定是＿＿＿＿＿圖。6．如果一個有向圖中沒有＿＿＿＿＿＿，則該圖的全部頂點可能排成一個拓撲序列。7．深度為8（根的層次號為1）的滿二叉樹有＿＿＿＿＿＿個葉子結點。 8．將一棵有100個結點的完全二叉樹按層編號，則編號為49的結點X，其雙親PARENT（X）的編號為＿＿＿＿＿＿＿。9．設某閉散列表HT未滿，散列函數H（KEY）為鍵值第一字母在字母表中的序號，處理沖突方法為線性探測法，請在下列演算法劃線處填上適當內容，以實現按鍵值第一字母的順序輸出閉散列表中所有鍵值的演算法。void printword(keytype HT[m]) { for(i=1;i<=26;i++) { j=i; while(____________________) { if (____________________) printf(「datatype」,HT[j]); j=(j+1)% m; } } }10．設有一個鏈隊，結點結構為data|next，front為隊頭指針，rear為隊尾指針，當執行入隊操作時需執行下列語句：malloc(p)；p->data=x; p->next=NULL；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿； 四、簡答題：（每小題4分，共20分）1. 對於一個有10000個結點的二叉樹，樹葉最多有多少個？最少有多少個？2. 已知一棵二叉樹的中序序列和後序序列分別為： DBGEACHF和DGEBHFCA，則該二叉樹的前序序列是什麼？3. 設有1000個無序的元素，需排出前10個最大（小）的元素，你認為採用哪種排序方法最快？為什麼？4. 在KMP演算法中，已知模式串為ADABCADADA ，請寫出模式串的next[j]函數值。5. 中序遍歷的遞歸演算法平均空間復雜度為多少？ 五、 演算法設計題（每小題10分，共20分）1. 試編寫一個演算法，判斷一給定的整型數組a[n]是不是一個堆。2. 一棵二叉樹的繁茂度定義為各層結點數的最大值與樹的高度的乘積。試寫一高效演算法，求二叉樹的繁茂度。參考答案一、選擇題1、D 2、C 3、D 4、C 5、D 6、D 7、A 8、B 9、D 10、C 11、D 12、C 13、B14、C15、D二、判斷題 1. √ 2. × 3. √ 4. √ 5. × 6. × 7. × 8. √ 9. √ 10. × 三、填空題1．U=L - > next2．4。3．n-1、n(n-1)/2。4．p - > prior = NULL。5．連通6．迴路或環7．28-1 = 27 = 1288．249．HT[j]!=NULL或HT[j]不為空、H(HT[j])=I10．rear - > next = p、rear = p四、簡答題：1. 答： 最多是完全二叉樹的形態，即5000個葉子；最少是單支樹的形態，即1個葉子。2.答：是：ABDEGCFH3. 答：用錦標賽排序或堆排序很合適，因為不必等全部元素排完就能得到所需結果，時間效率為O(nlog2n)； 即O（1000log21000）=O(10000) 錦標賽排序的准確比較次數為：n-1+9log2n=999+9log21000=999+9×10=1089堆排序的准確比較次數為：n-1+9log2n=999+9log21000=999+9×10=1089若用冒泡排序也較快，最多耗費比較次數為（n-1+n-2+……＋n-10）=10n-55=10000-55=9945（次）4. 答： 01121123435. 答： 要考慮遞歸時佔用了棧空間，但遞歸次數最多不超過樹的高度，所以空間復雜度為O(log2n) 五、 演算法設計題1.解：提示：堆的定義是：ki<k2i和K2i＋1 void SortA(sqlist &A, int n) { if(n==0) return(0); //空表if (a[1]<a[2]) { for( i=1; i<=n/2; i++) if (a[i]>a[2*i]|| a[i]>a[2*i+1])return(-1);return(minleap)};else { for( i=1; i<=n/2; i++) if (a[i]<a[2*i]|| a[i]<a[2*i+1])return(-1);return(「maxleap」)};}2. 要用層次遍歷以及隊列來處理，可以增設一個寬度計數器，在統計完每一層的結點個數之後,再從計數器中挑出最大值。typedef struct { BTNode node; int layer; //layer是結點所在層數 } BTNRecord, r ; int Width(Bitree T ){ //求樹寬 int count[ ]; //增開count向量，存放各層對應的結點數 InitQueue(Q); //隊列初始化，Q的元素為BTNRecord類型 EnQueue(Q,{T, 0}); //根結點入隊, 0 表示count[0]，下標值 while(!QueueEmpty(Q)) { DeQueue(Q, r); //結點出隊 count[r.layer]++; //出隊時再把結點對應層的計數器加if(r.node->lchild) EnQueue(Q,{r.node->lchild, r.layer+1}); if(r.node->rchild) EnQueue(Q,{r.node->rchild, r.layer+1}); } //按層序入隊時要隨時標注結點所在層號 h=r.layer; //最後一個隊列元素所在層就是樹的高度 for(maxn=count[0], i=1; h; i++) if(count[i]>maxn) maxn=count[i]; //求出哪一層結點數最多 return (h*maxn)} // Width

⑵ 數據結構考試(復習題)答案 急求~~~~~

1.同2
2. C．教科書第一頁，緒論1.1基本術語..........數據元素版是數據的基本單位，
數據項是構成權數據元素的不可分割的具有獨立含義的最小標識單位
、
3.B插入和刪除最好的和最壞的時間復雜度是O（1），O(n).品均時間復雜度是O(n);
4.B
5.B
6.詳情請看數據結構實用教程c語言版的教材第86頁，具有相同的邏輯結構（都是線性表）
可以採用相同的存儲方法（順序存儲，鏈接存儲）具有不同的運算特點棧是後進先出，隊列是先進先出。
8.b//79頁
12.有向圖頂點與邊的關系是n(n-1)，無向圖是n(n-1)/2,
13.無向圖中一個頂點的度是指與該頂點相關的邊的條數，同（路徑）
14.C
15.D
16.2
17.
18.Push pop