1、2008年安徽工業大學數據結構考研真題A卷一、單項選擇題1.程序段FOR(i=n-1;i=0;i-)FOR(j=1;jAj+1Aj與Aj+1對換；其中n為正整數，則最后一行的語句頻度在最壞情況下是_。A.O（n）B.O(nlogn)C.O(n)D.O(n)2.用鏈表表示線性表的優點是_。A.便于隨機存取B.花費的存儲空間較順序存儲少C.便于插入和刪除D.數據元素的物理順序與邏輯順序相同3.帶頭結點的單鏈表head為空的判定條件是_。A.head=NULLB.head-next=NULLC.head-next=headD.head!=NULL4.在循環雙鏈表的p所指結點之后插入s所指結點的操作是

2、_。A.p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;B.p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;C.s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;D.s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;5.棧應用在_。A.遞歸調用B.子程序調用C.表達式求值D.A，都對6.設abcdef(a先進棧)順序進棧，若在進棧操作時，允許出棧操作,則下面得不到的序列為_。AfedcbaB.bcafedC.

3、dcefbaD.cabdef注：序列xyz表示x先出棧；z最后出棧。7.若一個棧的輸入序列為1,2,3,4,5則輸出序列有_種可能。A.14B.120C.60D.428.循環隊列存儲在數組A0.m中，則入隊時隊尾的操作為_。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)9.在簡單模式匹配中，當模式串位j與主串位i的比較時，新一趟匹配開始，主串的位移公式是_。Ai=i+1Bi=j+1Ci=i-j+1Di=i-j+210.稀疏矩陣一般的壓縮方法是_。A.二維數組和三維數組B.三元組和散列表C.三元組和

4、十字鏈表D.散列和十字鏈表11.若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數組B1.(n(n+1)/2中，a00存放于數組B1中，則在B中確定aij(i2，則該二叉樹的高度為_。5.一棵樹按照左孩子一右兄弟表示法轉換成對應的二叉樹，則該二叉樹中樹根結點肯定沒有_。6.設圖G(V，E)，V1，2，3，4，E，,從頂點1出發，對圖G進行廣度優先搜索的序列有_種。7.在哈希查找中，裝填因子為，若用m表示哈希表的長度，n表示哈希存儲的元素個數，則等于_。8.在順序表(8,11,15,19,25,26,30,33,42,48,50)中，用折半法查找關鍵字

5、值20，需做的關鍵字比較次數為_。9.快速排序的遞歸算法在平均情況下的空間復雜度為_。10.設圖的頂點數為n，則求解最短路徑的Dijkstra算法的時間復雜度為_。三、判斷1.數據結構的抽象操作的定義與具體實現有關。（）2.在鏈式存儲表中存取表中的數據元素時，不一定要按順序訪問。（）3.鏈表中的頭結點僅起到標識的作用。（）4.消除遞歸不一定需要使用棧。（）5.循環隊列只能通過鏈式存儲結構實現。（）6.個廣義表的表尾總是一個表。()7若一個葉子結點是某二叉樹中序遍歷序列的最后一個結點，那么它也是該二叉樹的先序遍歷序列的最后一個結點。()8.對一個無向連通圖進行一次深度優先搜索可以訪問圖中的所有頂

6、點。()9.鄰接矩陣適用于稀疏圖(邊數遠小于頂點數的平方)，鄰接表適用于稠密圖(邊數接近于頂點數的平方)。()10.對二叉排序樹進行先序遍歷得到的結點的值的序列是一個有序序列。()四、應用題1已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，畫出這棵二叉樹。并寫出其先序遍歷序列。（5分）2.已知廣義表：B(b,c)C=(a,(d,e,f)D=(B,C)E=(a,E)設廣義表原子節點和表節點的存儲映像如下圖所示（其中hp表示表頭指針，tp表示表尾指針），請畫出廣義表B、C、D、E的存儲映像圖。（5分）3已知一個文件中有5個字符a、b、c、d、e，各個字符的出現的次數依次

7、分別是3、4、8、10、16，試為這5個字符編碼，以節省存儲空間。（5分）4 對于下圖所示的無向連通圖，請用Prim算法構造其最小生成樹，設算法從圖中頂點1開始處理。（5分。注：要求寫出求解過程）5給出待排序序列的關鍵字序列為87,52,61,27,37,45,請寫出對該序列進行堆排序的過程（注：升序排序，寫出每趟排序的過程）。（5分）6請將下列計算二叉數深度的算法補充完整，每個空格一分。（5分）intBtreeDepth(BTreeNode*BT)7已知完全二叉樹的第8層有7片葉子，請指出所有可能的情況下的葉子數目，不需要畫出圖形，文字說明即可。（5分）五、算法設計題1.已知帶頭節點的單鏈表

8、L，寫一算法，刪除其中的重復結點(15分)。設單鏈表節點存儲結構定義如下：TypedefstructnodeDataTypedata;/*每個元素數據信息*/structnode*next;/*存放后繼元素的地址*/Lnode,*LinkList;2.奇偶交換排序算法如下所述：第一趟對所有下標i為奇數的元素，將ai與ai+1比較，第二趟對所有下標i為偶數的元素，將ai與ai+1比較，如aiai+1則將二者交換；第三趟對奇數i，第四趟對偶數i，重復上述處理過程直到整個文件有序（10分）。(1)問此種排序算法的結束條件是什么？（3分）(2)用C語言實現此算法。（7分）設待排序文件采用如下存儲結構：defineMAXSIZE100typedefstructDataTyperMAXSIZE+1;intlength;/*表長度*/SqList,*PsqList;3.寫出對中序線索二叉樹進行中序遍歷的算法，不允許使用棧。（15分）設中序線索二叉樹的存儲結