數(shù)據(jù)結(jié)構(gòu)期中考試模試卷2014.doc

數(shù)據(jù)結(jié)構(gòu)模擬試卷一. 單選題（每題1分，共14分）1數(shù)據(jù)結(jié)構(gòu)所討論的基本數(shù)據(jù)單位是（B）。A、數(shù)據(jù)對象 B、數(shù)據(jù)元素 C、數(shù)據(jù)項 D、數(shù)據(jù)類2. 在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為（C）兩大類。A. 內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu) B. 靜態(tài)結(jié)構(gòu)與動態(tài)結(jié)構(gòu)C. 線性結(jié)構(gòu)與非線性結(jié)構(gòu) D. 緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)。3若一個算法的時間復(fù)雜度用T(n)表示，其中n的含義是（A ）A問題規(guī)模 B指令條數(shù)C循環(huán)層數(shù) D函數(shù)數(shù)量4. 算法分析的目的是（C）。A. 研究算法的輸入與輸出之間的關(guān)系B. 找出數(shù)據(jù)結(jié)構(gòu)的合理性C. 分析算法的效率以求改進(jìn)算法D. 分析算法的可讀性與可移植性5、采用線性鏈表表示一個向量時，要求占用的存儲空間地址（D）A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)C. 一定是不連續(xù)的 D. 可連續(xù)可不連續(xù)6. 在一個當(dāng)前長度為n的順序表中向第j個元素（1jnextNULLC、head一next= = headD、head!NULL8、設(shè)單鏈表中指針P指向結(jié)點A，若要刪除A之后的結(jié)點（若存在），則需要修改指針的操作為（A）A、pnext=pnextnextB、p=pnextC、p=pnextnextD、pnext=p9、若有一個最大長度為size，且設(shè)有隊首指針front和隊尾指針rear的順序循環(huán)隊列，試問判斷隊列滿的條件應(yīng)是下列哪一個語句（D）A、front=rear B、front- rear=sizeC、front+rear=size; D、front=(rear+1)%size10. 設(shè)一個棧的入棧序列為1，2，3，4，5，6，則出棧序列不可能的是（B ）。A、3，2，5，6，4，1B、1，5，4，6，2，3C、2，4，3，5，1，6D、4，5，3，6，2，111、數(shù)據(jù)結(jié)構(gòu)從總體上可分為兩大類，串的邏輯結(jié)構(gòu)與（D）的邏輯結(jié)構(gòu)不屬于同一類。A線性表 B、棧 C、隊列 D、樹12、對一非空廣義表，其表尾是指（C）A、廣義表的最后一個元素B、廣義表的最后一個單個元素C、廣義表的最后一個子表元素D、除第一個元素外的所有其余元素13. 廣義表A=( ),(a),(b,(c,d)的長度為（B）A、2B、3C、4D、514. 每種數(shù)據(jù)結(jié)構(gòu)都具備的三種最基本運(yùn)算是（A）A、插入、刪除、遍歷B、輸入、輸出、刪除C、初始化、創(chuàng)建、銷毀D、輸入、輸出、遍歷二、填空題(每小題2分，共28分)1、數(shù)據(jù)結(jié)構(gòu)學(xué)科討論的是_非數(shù)值計算_問題的數(shù)學(xué)模型及其涉及的基本操作在計算機(jī)中的表示與實現(xiàn)。2、數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲器中的映象，它需要解決的主要問題是_數(shù)據(jù)元素之間的關(guān)系如何映象_。3、抽象數(shù)據(jù)類型（ADT）是編程語言提供的用戶可自定義的一種數(shù)據(jù)類型，它主要由_數(shù)據(jù)_和_操作_兩大部分組成。4. 當(dāng)算法中所有語句的頻度之和T（n）與求解問題的規(guī)模無關(guān)時，那么該算法的時間復(fù)雜度為_O（1）_階。5、線性結(jié)構(gòu)反映數(shù)據(jù)元素間的邏輯關(guān)系是_一對一_的，圖形結(jié)構(gòu)中的數(shù)據(jù)元素之間的關(guān)系是_多對多_的，而樹形結(jié)構(gòu)中數(shù)據(jù)元素間的關(guān)系則是_一對多_的。6以數(shù)組A60存放順序循環(huán)隊列的元素。假設(shè)當(dāng)前隊列有50個元素，且頭指針front的值是47，則隊列的尾指針rear的值應(yīng)是_37_。6. 在雙向循環(huán)鏈表中，設(shè)指針p指向待刪除的結(jié)點，則刪除結(jié)點p需執(zhí)行的語句為_q-next = p-next;_p-next-prior = q7. 先進(jìn)先出隊列與優(yōu)先級隊列與隊列的不同，主要是在于_入隊_操作的處理。8. 矩陣中的非0元素與矩陣的規(guī)模之比稱為稀疏因子，如果的值不大于_0.05_，則稱矩陣為稀疏矩陣。9. 對于一個nn的對稱矩陣可以只用一個有_n(n+1）/2_個存儲單元的一維數(shù)組來存儲。10、廣義表表達(dá)式中()的_最大嵌套層數(shù)_稱為廣義表的深度。三.判斷題(每小題1分，共8分)1. 一個完整算法可以沒有輸入，但必須有輸出。T2. 線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲，也可以鏈接存儲。而非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲。F3. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。F4. 非空線性表中任意一個數(shù)據(jù)元素都有且僅有一個直接前驅(qū)元素。F5、雙循環(huán)鏈表中，任一結(jié)點的前驅(qū)指針均為不空。T6. 空串就是空格串。F7. 兩個串相等的充要條件是兩個串的長度相等且對應(yīng)位置的字符相等。T8. 棧和隊列都是限制數(shù)據(jù)元素存取點的線性結(jié)構(gòu)。T四、算法或程序設(shè)計題(共50分)1. 設(shè)計一個算法，計算數(shù)列2-4+6-8+10m的值并返回，該數(shù)列存放在一個整型數(shù)組中。要求時間復(fù)雜度為O(1)。（本題10分）status fun(a ,n) /a為存放數(shù)列的數(shù)組，n是數(shù)組的長度2、閱讀下面算法，指出其功能并給出其時間復(fù)雜度。（8分）status fun(LinkList &LA, LinkList &LB)n=LB.Length();for( i=1; inext;while(_cp!=NULL&cp-data!=e_) pp=cp; cp=cp-next; if(_cp=NULL|cp-data!=e_ )return FAIL;/表中無元素eif(_pp=head_)return FAIL; /元素?zé)o前驅(qū)_x=p-data_; /返回前驅(qū)return OK;4. 設(shè)計算法：將一個非單調(diào)的有序單鏈表（帶頭結(jié)點）修改成單調(diào)的有序單鏈表，即刪除表中所有值相同的多余元素。（16分）void Purge(