《數(shù)據(jù)結構》期末考題(doc 8頁).doc

西南財經大學2007 2008 學年第二學期統(tǒng)計 專業(yè) 本科 2007、2006級（ 二、三年級上學期）學 號 評定成績 （分）學生姓名 擔任教師 周啟海 數(shù)據(jù)結構期末考試題(B卷)（下述 一 三 題全作計100分， 兩小時完卷）考試日期：2008. 12 . 24試 題 全 文：遵守考場紀律，防止一念之差貽誤終生。一、判斷題 (每小題5分，共10分)1. “廣義表”，難用順序存儲結構來描述。答：2. 已知排序所采用的數(shù)據(jù)結構、算法思想、語言環(huán)境等均相同。如果對同一組待排序數(shù)據(jù)，則其遞增序排序算法與遞減排序算法的運行時間通常不同。答：二、簡答題 (每小題5分，共60分)1. 有人說：“學習數(shù)據(jù)結構課程的關鍵，可概括為什么是數(shù)據(jù)結構？有哪些數(shù)據(jù)結構？各種數(shù)據(jù)結構特點如何？（所論問題）該用何種數(shù)據(jù)結構？”這種說法錯嗎？為什么？答：2. 在“數(shù)據(jù)結構”研究中，任何一種“數(shù)據(jù)結構”（例如：圖）的所謂結構，絕不僅指其存儲結構，即：它還必須包括另一種性質完全不同于存儲結構的什么結構？為什么？答：3. “線性表”，是指一種還是一類最基本的常用線性數(shù)據(jù)結構？為什么？答：4. “隊”的存儲結構描述工具，既可以采用順序存儲的數(shù)組，也可以采用非順序存儲的鏈表。請問：如果所論“隊”需要頻繁入隊與出隊操作，則采用鏈表作為描述工具是否恰當？為什么？答：5. “二叉樹”的存儲結構，雖然既可采用順序存儲結構（例如數(shù)組），也可采用非順序存儲（例如鏈表）。但為什么說“非完全二叉樹，不宜采用順序存儲結構”？答：6. 設計航空公司航班的“飛機乘客票務管理程序”時，最適宜采用的數(shù)據(jù)結構是什么？為什么？答：7現(xiàn)有實現(xiàn)同一功能的三個算法A1，A2和A3，且已知其時間復雜度順次為Tl=O(2n)，T2=O(n2)，T3=O(n log n)。請僅就其時間復雜度，給出各算法優(yōu)化程度遞增的順序，并說明理由。答：8. 已知有5 個元素的入棧次序為“A，B，C，D，E”?，F(xiàn)要求第一個出棧元素為C、第二個出棧元素為D，而其余棧元素仍須保留在此棧中。請說明相關棧及其元素的彈出與壓入操作處理過程。答：9. 已知二叉樹含三個結點A、B、C，請給出以B為根結點的二叉樹所有形態(tài)。答：10. 設二維數(shù)組A108的每個數(shù)組元素占四個存儲單位，且第一個元素A11的存儲地址為1000。若按列優(yōu)先順序存儲，則數(shù)組元素A54的存儲地址是多少？答：11. 與其對應遞歸程序相比，簡述非遞歸程序的優(yōu)點與缺點。答：12. 已知廣義表A=(b,c,(d,e,f)。試問：廣義表B=( a,(),A,g)，廣義表C=( A,a,(g)的長度各是多少？答：二、設計題 (每小題10分，共30分)請用某種計算機語言(例如：VB，或C)，編程解決下列各小題。1. 任給的n個實數(shù)（n=10），請用順序表（即：數(shù)組方式）進行存放，對用戶給定的第k（1=k=n）個數(shù)據(jù)進行：刪除一個數(shù)據(jù)操作，并輸出數(shù)據(jù)處理結果。答：2. 任給的n個實數(shù)（n=10），采用順序表（