試題(張艷玲)-6

《試題(張艷玲)-6》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、學(xué)院領(lǐng)導(dǎo)審批并簽名廣州大學(xué)學(xué)年第學(xué)期考試卷課程考試形式（閉卷，考試）信息學(xué)院系專業(yè)級班學(xué)號：姓名：題次—二三四五/、總分評卷人分?jǐn)?shù)201010302010100評分一、填空題：（每空2分，共20分）1、抽象數(shù)據(jù)類型的特點是使用與實現(xiàn)分離。2、算法的一個特性是，即算法必須執(zhí)行有限步就結(jié)束。3、一維數(shù)組所占用的空間是連續(xù)的。但數(shù)組元素不一定順序存放，而是按元素的存放的。4、將一個n階對稱矩陣的上三角部分或下三角部分壓縮存放于一個一維數(shù)組中，則一維數(shù)組需要存儲個矩陣元素。5、在單鏈表中設(shè)置表頭結(jié)點的作用是在插入和刪除表中第一個元素時不必對逬行特殊處理。6、中綴表達(dá)式3*（x+2）-5所對應(yīng)

2、的后綴表達(dá)式為。7、廣義表A（（a，b，c），（d，e，f））的表尾為。8、假定一棵三叉樹（即度為3的樹）的結(jié)點個數(shù)為50,則它的最小高度為o假定根結(jié)點的高度為0。9、101個頂點的連通網(wǎng)絡(luò)N有100條邊，其中權(quán)值為1，2,3,4,5,6,7,8,9,10的邊各10條，則網(wǎng)絡(luò)N的最小生成樹各邊的權(quán)值之和為。二、單項選擇題（每空1分，共10分）1.一個數(shù)組元素a[i]與（）的表示等價。A.*（a+i）B.a+iC.*a+iD.&a+i2.—種抽象數(shù)據(jù)類型包括數(shù)據(jù)和（）兩個部分。A.數(shù)據(jù)類型B.操作C.數(shù)據(jù)抽象D.類型說明3.以下說法錯誤的是（）。A.抽象數(shù)據(jù)類型具有封裝性。B.抽象數(shù)據(jù)

3、類型具有信息隱蔽性。C.抽象數(shù)據(jù)類型的用戶可以自己定義對抽象數(shù)據(jù)類型中數(shù)據(jù)的各種操作。D.抽象數(shù)據(jù)類型的一個特點是使用與實現(xiàn)分離。4、在一個長度為n的順序表中順序搜索一個值為x的元素時，在等概率的情況下，搜索成功的數(shù)據(jù)平均比較次數(shù)為（）。A.nB.n/2C.（n+l）/2D.（n-l）/25、在一個長度為n的順序表中向第i個元素（0link==NULL;C.first->link==

4、first;D.first!=NULL;7、桟的插入和刪除操作在（）進行。A.棧頂B.棧底C.任意位置D.指定位置8、在系統(tǒng)實現(xiàn)遞歸調(diào)用時需利用遞歸工作記錄保存實際參數(shù)的值。在傳值參數(shù)情形，需為對應(yīng)形式參數(shù)分配空間，以存放實際參數(shù)的副本；在引用參數(shù)情形，需保存實際參數(shù)的（），在被調(diào)用程序中可直接操縱實際參數(shù)。A.空間B.地址C.返回地址D.副本9、在一棵樹中，（）沒有前驅(qū)結(jié)點。A.分支結(jié)點B.葉結(jié)點C.根結(jié)點D.空結(jié)點10、在一個帶權(quán)連通圖G中，權(quán)值最小的邊一定包含在0的（）生成樹中。A.某個最小B.任何最小C.廣度優(yōu)先D.深度優(yōu)先三、判斷題（在括號內(nèi)填上“v”或“X”，每題1分，共

5、io分，做錯不倒扣）1、（）數(shù)據(jù)結(jié)構(gòu)是具有結(jié)構(gòu)的數(shù)據(jù)對象。2、（）數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體。3、（）數(shù)組是一種靜態(tài)的存儲空間配置，就是說，在程序設(shè)計時必須預(yù)先定義數(shù)組的數(shù)據(jù)類型和存儲空間大小，由編譯程序在編譯時逬行配置。4、（）n階三對角矩陣總共n2個矩陣元素中最多只有3n-2個非零元素，因此它是稀疏矩陣。5、（）鏈?zhǔn)酱鎯υ诓迦牒蛣h除時需要保持?jǐn)?shù)據(jù)元素原來的物理順序，不需要保持原來的邏輯順序。6、（）若讓元素1,2,3依次進桟，則出棧次序3,1，2是不可能出現(xiàn)的情況。7、（）遞歸調(diào)用算法與相同功能的非遞歸算法相比，主要問題在于重復(fù)計算太多，而且調(diào)用本身需

6、要分配額外的空間和傳遞數(shù)據(jù)和控制，所以時間與空間幵銷都比較大。8、（）在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別逬行前序遍歷和后序遍歷，則具有相同的遍歷結(jié)果。9、（）如果無向圖中各個頂點的度都大于2,則該圄中必有回路。10、（）當(dāng)輸入序列已經(jīng)有序時，起泡排序需要的排序碼比較次數(shù)比快速排序要少。四、計算題/畫圖題/證明題(30分)1.指出算法的功能并求出其時閻復(fù)雜度。voidmatrimult(inta[][],intb[][],intc[][],intM,intN,intL){//數(shù)組a[M][N]、b[N][L]、c[M][L]均為整型數(shù)組inti，j，k;for

7、(i=0;i

8、j];}}2、對于一個nxn的矩陣A的任意矩陣元素a[i]U]，按行存儲時和按列存儲時的地址之差是多少。(若設(shè)兩種存儲的幵$臺存儲地址LOC(0,0)及元素所占存儲單元數(shù)d相同)3、設(shè)散列表的長度m=13;散列函數(shù)為H(K)=K%m，給定的關(guān)鍵碼序列為19,14,23,01，68,20,84,27,55,