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