廣西大學數據結構練習題及答案

A. 找套數據結構的題以及答案

數據結構》單元測驗(1-5)

一、 選擇題
1．數據是對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中並被計算機程序處理的符號的總稱，而（ B ）是數據不分割的最小單位。
A． 數據元素 B．數據項
C．數據對象 D．數據結構
2．下面程序段的時間復雜度為（ C ）
for(i=0;i<m;i++)
for(j=0;j<n;j++)
a[i][j]=i*j;
A．O（n2） B．O(m2) C．O(m*n) D．O(m+n)
3．在一個單鏈表L中，若要在指針q所指結點的後面插入一個由指針p所指向的結點，則執行( D )。
A．q一>next＝p一>next；p一>next＝q；
B．p一>next＝q一>next；q＝p；
C．q一>next＝p一>next；p一>next＝q；
D．p一>next＝q一>next； q一>next＝p；
4．當利用大小為N的一維數組順序存儲一個循環隊列時，該隊列的最大長度為（ B ）
A．N-2 B．N-1 C．N D．N+1
5．若編號為1，2，3，4，5，6的六節車廂依次通過一段棧形軌道，則在出口處不可能得到（ D ）
A．143562 B．456321 C．145326 D．426531
6．假設一個循環隊列的隊首和隊尾指針分別為f和r，則判斷隊空的條件是（ D ）
A．f+1==r B．r+1==f C．f==0 D．f==r
7．經過下列棧的運算後棧頂的值是（ A ）
InitStack(s);Push(s,a), Push(s,b);Pop(s);
A．a B．b C．1 D．2
8．單鏈表中，增加頭結點的目的是為了（ C ）
A．鏈表至少有一個結點
B．標示表結點中首結點的位置
C．方便運算的實現
D．說明單鏈表是線性表的鏈式存儲結構
二、 填空題
1．數據結構一般包括以下三個方面的內容：（ 邏輯結構 ）、（ 存儲結構 ）、（ 運算集合 ）。
2．數據的邏輯結構被分為（ 集合 ）、 （ 線性 ）、 （ 樹形 ）和（ 圖形 ）四種。
3．假設有二維數組A8×6，每個元素用相鄰的4個位元組存儲，存儲器按位元組編址。已知A的起始存儲位置（基地址）為2000，若按行存儲時，元素A41的第一個位元組地址為（ 2100 ）；若按列存儲時，元素A74的第一個位元組地址為（ 2156 ）。
4．棧是一種特殊的線性表，允許插入和刪除運算的一端稱為（ 棧頂 ）。不允許插入和刪除運算的一端稱為（ 棧低 ）。
5．向一個長度為n的順序表的第i個元素之前插入一個元素時，需向後移動（ n-i+1 ）個元素。
三、判斷題
（ 錯 ）1．鏈表的每個結點都恰好包含一個指針。
（ 錯 ）2．順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高。
（ 對 ）3．棧和隊列的存儲方式既可以是順序方式，也可以是鏈接方式。
（ 錯 ）4．一個棧的輸入序列是12345，則棧的輸出序列不可能是12345。
（ 錯 ）5．鏈表的刪除演算法很簡單，因為當刪除鏈中某個結點後，計算機會自動將後續各個單元向前移動。
（ 錯 ）6．順序表適合進行順序存取，而鏈表適合進行隨機存取。
（ 對 ）7．對矩陣進行壓縮存儲是為了節省存儲空間。
（ 錯 ）8．順序存儲方式只能用於存儲線性結構。
四、 簡述以下演算法的功能
1. Status algo1(Stack s,int e)
{ Stack T;int d;
InitStack(T);
While(!StackEmpty(S))
{Pop(S,d);
if(d!=e) Push(T,d);
}
While(!StackEmpty(T))
Pop(T,d);Push(S,d);
答：通過T的幫助將S中的e元素清除
}}
2. void algo2(Queue &Q)
{ Stack S;int d;
InitStack(S);
While(!QueueEmpty(Q))
{DeQueue(Q,d); Push(S,d);}
While(!StackEmpty(S))
{Pop(S,d);
EnQueue(Q,d);}}
答：通過棧S的幫助實現隊列Q的逆置
五、 演算法設計
編寫演算法，實現順序表上的逆置運算。
void reverse(int a[],int n)
{
int i;
for(i=0;i<n/2;i++)
{
push(s,a[i]);
a[i]=a[n-i-1];
pop(s,a[n-i-1]);
}
}

B. 數據結構練習題！求答案！

一．選擇題：
1． A 這個題目你是不是寫的不完整啊
要是：刪除它的第i數據元素 ，需要移動？個的話 你的答案錯了。例如：刪除第一個，移動N-1個；刪除第二個，移動N-2個 ----以此類推 刪除第n-1個移動1個 刪除第n個移動0 個

要是：刪除它的第i數據元素之前的元素，同理 就會選D

2. B 你的答案錯了，這個題的答案是 B ,注意：題目是 q是p的前驅
3. C 你的答案錯了這個題的答案是C， C.d,c,a,b 棧是先進後出 d一個出 說明c ,b,a都還在棧中 而出的序列 只能是c ,b,a
4.C 你的答案錯了，這個題的答案是 C 只有根結點沒有直接前驅
5. C 給你一個公式： 一棵深度為H（根的層次號為1）的滿二叉樹共有_2^H-1_____個結點.推到過程：第i層結點數目為：2^(i-1) i取值 從1到樹深h，所以，每層的結點數目相加 就是樹的總節點數 ，利用等比公式 得到上面給你的公式。
6. 這個沒有圖啊：
下面二叉樹的中序遍歷序列為________。( )
A. DBEAFC
B. DEBFCA
C. BDEACF
D. ABCDEF
7. C 因為題目說是聯通同 因此是無向圖 所以C
8. C
9. B 拓撲排序就是對邊和頂點操作 所以與邊和頂點的個數相關
10. B
二．填空題：
1.LOC(ai)=__LOC(a1)+(i-1)*k________。
2. 9 （n0=n2+1）
3. log2(n+1)
4. （a,b,c,d）
5. 對稱
6. 2
7. 指針
8. 棧空
9. 變成兄弟結點
10.0
三．判斷題：
數組是一種沒有插入與刪除操作的線性結構。(錯 )
稀 疏矩陣中值為0的元素分布有規律，因此可以採用三元組方法進行壓縮存儲。(錯 )
空串與由空格組成的串沒有區別。( 錯 )
完全二叉樹就是滿二叉樹。( 錯)
有向圖是一種非線性結構。(對 )
帶權連通圖的最小生成樹的權值之和一定小於它的其它生成樹的權值之和。( 對 )
AOE 網是一種帶權的無環連通圖。( 對 )
一個廣義表的表尾總是一個廣義表。( 錯 )
存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數有關，而且與圖的邊數也有關。( 對 )
對於有n個對象的待排序序列進行歸並排序，所需平均時間為O（nlog2n）。( 對 )

已發送 查收吧

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

《數據結構》試題一、選擇題（每小題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

D. 《數據結構》復習題（二）(1)

一,
1.X
2.X
3.X
4.√
5.X
6.√
7.√
8.√
9.√
10.
二.
1.
2.隊列,隊尾.
3.
4.
5.Cn2 (n個中任取2個)
6.AOV網
7.O(n^2)
8.直接插入排序
三.
1.B
2.C
3.2^(i-1)
4.C
5.

E. 《數據結構》復習題（三）(1)

1.X.數據是計算機接收,識別,存儲,加工處理的對象的全體.
2.√.最後不知道要不要加上一個"運算及實現"
3.√
4.X.先進後出.
5.X
6.√
7.X.最多有2^h -1個結點
8.X
9.√
10.X
二,
1.數據結構.
2.線性結構和非線性結構.
3.順序表.
4.隊列.
5.2^h -1.
6.順序表.
7.排序.
8.
三.
1.A
2.A.先進先出.
3.沒有學.
4.C.
5.B.一串下去.

F. 《數據結構》復習題 答案 高分求救！

一、選擇題（每題2分，共20分）
1、二分查找，要求被查找的表是（ A ）
A 順序表 B 分塊有序表 C 鏈表 D 無限制
2、一完二叉樹有30個接點，則該樹有（C ） 層。(根為0層) log2n+1
A 3 B 4 C 5 D 6
3、下列排序演算法中，第一趟排序後，其最大的或最小的數一定在最終的位置上的是（ D）
A 歸並排序 B 直接插入排序 C 快速排序 D 冒泡排序
4、設八棧序列為A,B,C,D,則棧可能產生的出棧序列是（ A）
A、 A C D B B、 C A D B
C、 D C A B D、 D A B C
5、如有一顆二叉樹按先序遍歷所得結果為（? ）
A A、C G B E F D A
B D B、A B C G D E F
C E F C、C G B A E D F
G D、G C B E F D A
6、下面哪個結構屬於線形結構 （C ）
A 二叉排序樹 B 線索樹 C 隊列 D 圖
7、棧和隊列都是 （ ）
A 沒有限制的線形表 B 沒有限制的非線形表
CD
8、在線性表操作中，常對某元素插入或刪除。則採用什麼存貯結構最節省運算時間（A ）
A、單鏈表 B、散列表 C、二叉鏈表 D、順序表
9、設H為帶頭結點單向循環鏈表的頭指針，P為移動指針，指針域為link，則表尾的判斷條件是（D ）
A、H->link = H B、P = H C、P->link = nil D、P->link = H
10、先序遍歷能得到A，B，C序列的不同二叉樹，最多有幾種（ ）
A、4 B、5 C、6 D、7

二、填空題（每題2分，共20分）
1、在單鏈表中，欲刪除某一指定結點時，必須找到該結點的 結點。 前驅結點
2、 和 是操作點受限的線性表。 棧和隊列
3、二分查找的條件是 。 有序順序存儲結構
4、深度為K的二叉樹中結點總數最多為 。 2^k-1
5、在有n（n>0）個結點的二叉鏈表中，空鏈域的個數為 個。 n+1
6、在對有15個數據的有序表中作二分查找時，有 個結點查找長度為3。
7、在單鏈表中，若要在指針P所指結點後插入指針S所指結點，則需執行下列語句： 。 s=p->next;p->next=s;
8、舉出插入排序的兩種排序法： 。
9、快速排序的時間復雜度是 。