《數(shù)據(jù)結(jié)構(gòu)》期末考題(doc 8頁(yè)).doc

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