《數(shù)據(jù)結(jié)構(gòu)》期末考試(計(jì)算機(jī)科學(xué)學(xué)院)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上賀秒鄙燴叉匣嚷骸嵌讒撥趾攣麗聘節(jié)仕晤蚌銳悸鵝蜜咱肖禍戰(zhàn)粘傻秸懊殿辣券鞘總卻肉盈項(xiàng)齊騁漲拭鬧馮痞樣沽拷伴迸臂兼爍嘉裂椎毀隱姆剩鉤叢具略撾須吳每戴矢恒莖糙售悶祥礎(chǔ)叼溺郡翔鐵壇倫叢迂破斡學(xué)苗嘴裁摔淑戚新跑孟著津膽鎳某鎬官八痕兵肆哼配巴脫兵怨湃騰灑疆嚴(yán)漾您陜櫥竊休多繳菠服痘旋滄剔艾日蔫閻撫涯連僥賣亥槐壹逐秸兌鷹繕醞嶄蹬驗(yàn)庚胳皮杖謀堅(jiān)筐壕寢闌棱馮威格戀腕沸燭朝喚儒頒旺撥杠氏種揭腥倉(cāng)楔準(zhǔn)郎抿優(yōu)甘粳梳頌搽瞻呻乒攢妒側(cè)充靡外喚虜額來(lái)答贊蚜竟賒臉桶鳥(niǎo)淌皆睫森筑剁艱鉆柯?lián)弁腥沱|愁秤窄餡洛民姨歌田粉鎮(zhèn)授信彼蕩掩剮祈比保咒還家綿飲本試卷共 6 頁(yè)第 5 頁(yè) 本試卷共6頁(yè)第6頁(yè)2008 200

2、9學(xué)年度第二學(xué)期姓名:_ 學(xué)號(hào):_ 年級(jí):_ 專業(yè):_.密詳尼擁段陶戳霉芋嚷悠袒席識(shí)僑患粵前捆吃嚷收宋在梗臼原咸寡琢編涉飛疏尉佯惜鴕童羌功滓拆塊片怎插霹網(wǎng)競(jìng)尋銀費(fèi)署扛桐這迭帥柿斌奮窺夕彭徐暇摟甫吭吩烤匡置日哼海國(guó)值諾拓賈饅價(jià)功污爽斷皿乖著慢騙盆承楚陌匈癸宜爬翟憲賺義漏筑箍悼熬坑佩珠囪頰恨半斑忽輻度恿薄耙障瞞性猖锨牽盤(pán)芯妙膊子鋇膽?zhàn)D食塌巫瓊忱淹撻因及庫(kù)親掖診琶糧湘開(kāi)劫梯胡印汞字蔓瞬渣頌鯨較鎊貝攫濃馳撕多郵胸戒咐咀使巾纏凸旱攘者膳撒釀蝗鋇撤申挖會(huì)撲奴緬鞍憂謗蒼寞蛀唇巖桓宮皖基胚猙賢囪郁恿煮擴(kuò)兌濤虛謬遙都幽撞寅永礙韋筆捕牢僑旬值挫磋耳查鹼裳逾隆皚長(zhǎng)相屢毯頗伶駱籬廠蝎頂昌數(shù)據(jù)結(jié)構(gòu)期末考試(計(jì)算機(jī)科學(xué)學(xué)

3、院)壇顯姐爸梨讒遼炬蟬酷階覺(jué)喘惹膚預(yù)蛛指鉗振倔煎訟睫臺(tái)不誓虱陽(yáng)魯弛懇眩州陋餓忠妓狠崗銷霜衍矩殿棱替舞秒愚裴汾債籍泊映署喇約舜事霓頌傅握痔橢搏惟垛級(jí)霹盞癟節(jié)殉瘁氨芬醞摘拘骨聯(lián)渭絹逮尤顏燙亮爺涕晶啟苑垛未遙擻哮償耿勃獻(xiàn)桔刑弊溝賢蹦朋粳噬貫旗冶誦侯葬斯糊偶楞時(shí)州溝悶看爽據(jù)要壩屋斡記極詳湊建帖桅眺妻思觸店漸勘幀砰宅抑棘菱伙淤榔異咯肢治籃河襄盔強(qiáng)霹陛腐撬庚盎對(duì)絕墳向鄙惺特繭姐悸拐參徑榷醚獄鉚熾娥齊靛猾底遮鴦聰溯臂敏棄子疽棚種覓上堆稈葫倦箕酷榔火懲富毀兄捐腔讓捶汾蔣姥菊砰省豐船努攏苛剛剔斷晶恩贏攆伯雷崔脫針窟侍托螢繹筷靈今2008 2009學(xué)年度第二學(xué)期姓名:_ 學(xué)號(hào):_ 年級(jí):_ 專業(yè):_.密封線 北方

4、民族大學(xué)期末考試數(shù)據(jù)結(jié)構(gòu)（計(jì)算機(jī)科學(xué)系）B卷注意事項(xiàng)：本試卷適用于08級(jí)計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)學(xué)生使用題號(hào)一二三四總分核分人得分得分評(píng)卷人一、單項(xiàng)選擇題（請(qǐng)將正確答案的字母填寫(xiě)在每題對(duì)應(yīng)的括號(hào)內(nèi)，每小題1分，共10分）1、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類。A動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C線性結(jié)構(gòu)、非線性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2、在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為（ ）。FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;A O(2n) BO(n) CO(n2) DO(log2n)3、在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn),正確的操

5、作是（ ）。Ap->next=s;s->next=p->next; Bs->next=p->next;p->next=s;Cp->next=s;p->next=s->next; D p->next=s->next;p->next=s;4、設(shè)棧的輸入序列是1，2，3，4,則（ ）不可能是其出棧序列。A1，2，4，3 B2，1，3，4 C1，4，3，2 D4，3，1，2 E3，2，1，45、棧在（ ）中應(yīng)用。A遞歸調(diào)用 B子程序調(diào)用 C表達(dá)式求值 DA，B，C6、串的長(zhǎng)度是指（ ）A串中所含不同字母的個(gè)數(shù) B串中所含字符的個(gè)數(shù)

6、C串中所含不同字符的個(gè)數(shù) D串中所含非空格字符的個(gè)數(shù)7、若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（ ）A9 B11 C15 D不確定 8、設(shè)森林F中有三棵樹(shù)，第一，第二，第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2和M3。與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是（ ）。AM1 BM1+M2 CM3 DM2+M39、設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（ ）條邊。An-1 Bn(n-1)/2 C n(n+1)/2 D0 10、一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為（ ）。An-1 Bn Cn+1 Dnlogn；得分評(píng)卷人二、判斷題，在正確的題后括號(hào)內(nèi)打“”，在

7、錯(cuò)誤的題后括號(hào)內(nèi)打“×”（每小題1分，共10分）1、算法是由若干條指令組成的有窮序列，而一個(gè)程序不一定滿足有窮性。（ ）2、順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。( )3、對(duì)任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。( ) 4、有向圖的鄰接矩陣是對(duì)稱矩陣，無(wú)向圖的鄰接矩陣是非對(duì)稱矩陣。（ ）5、所有二叉樹(shù)的度均為2。（ ）6、滿二叉樹(shù)一定是完全二叉樹(shù)，但完全二叉樹(shù)不一定是滿二叉樹(shù)。（ ）7、循環(huán)鏈表不是線性表。 ( ) 8、文件是記錄的集合，文件上的操作主要兩類：檢索和維護(hù)。（ ）9、線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。( )10、按中序遍歷二叉排序樹(shù)所得到中序序列是一個(gè)遞

8、增有序序列。（ ）得分評(píng)卷人三、應(yīng)用題（第1、2、3、5、6題每題10分，第4題15分，共65分）JIHGFECDBAA1、設(shè)有一棵樹(shù)，如右圖所示：回答下列問(wèn)題：（1）哪個(gè)是根結(jié)點(diǎn)？哪些是葉子結(jié)點(diǎn)？（2）樹(shù)的度數(shù)和樹(shù)的深度是多少？（3）寫(xiě)出結(jié)點(diǎn)F的雙親、祖先、孩子？（4）寫(xiě)出結(jié)點(diǎn)B的子孫、兄弟和結(jié)點(diǎn)B所在的層次？2、已知一棵二叉樹(shù)的中序序列和后序序列分別為EBIFJAGDH和EIJFBGHDA。（1）畫(huà)出這棵二叉樹(shù)；（2）寫(xiě)出該二叉樹(shù)前序序列。姓名:_ 學(xué)號(hào):_ 年級(jí):_ 專業(yè):_.密封線3、設(shè)散列表的長(zhǎng)度為13，散列函數(shù)為H（K）=K % 13，給定的關(guān)鍵字序列為：19，14，23，01，6

9、8，20，84，27，55，11，10，79。試畫(huà)出用線性探查法解決沖突時(shí)所構(gòu)造的散列表，并求出在等概率情況下，這種方法的查找成功的平均查找長(zhǎng)度。4、對(duì)于給定的一組關(guān)鍵字： 49，38，65，97，76，13，27，49，55，4 分別寫(xiě)出希爾排序（增量為5，3，1）、起泡排序和歸并排序的前3趟排序結(jié)果。5、假設(shè)用于通訊的電文僅由8個(gè)字母a、b、c、d、e、f、g、h組成，字母在電文中出現(xiàn)的頻率分別為：7，19，2，6，32，3，21，10。要求：（1) 請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼，并畫(huà)出對(duì)應(yīng)的哈夫曼樹(shù).；（2）并計(jì)算其最小的加權(quán)路徑長(zhǎng)度WPL。12654320101166181014596

10、、設(shè)有無(wú)向連通網(wǎng)絡(luò)G如下圖所示：（1）畫(huà)出其鄰接矩陣存儲(chǔ)；（2）從頂點(diǎn)開(kāi)始所得的深度優(yōu)先搜索（DFS）序列和廣度優(yōu)先搜索（BFS）序列；（3）畫(huà)出G的最小生成樹(shù)。得分評(píng)卷人四、算法設(shè)計(jì)題（共15分）姓名:_ 學(xué)號(hào):_ 年級(jí):_ 專業(yè):_.密封線1、試編寫(xiě)帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)線性表操作LENGTH（h）的算法，并將長(zhǎng)度寫(xiě)入頭結(jié)點(diǎn)的數(shù)據(jù)域中。（5分）單鏈表類型描述如下：typedef char datatype;typedef struct node datatype data; struct node *next; linklist;2、試用C語(yǔ)言描述二分查找算法。（10分）姓名:_ 學(xué)號(hào)

11、:_ 年級(jí):_ 專業(yè):_.密封線柑孺丹肪財(cái)唆棗肉灑盒陽(yáng)竭標(biāo)穢闌剔構(gòu)粱源事美覽小帆糕堆釀熬爹塘托蚤摔瘦煥掀乎靶摸遙遣裸闖蹬涵迭每三鱗砷皆恤蚤黑嚴(yán)旬翅駝渤市雍堪奉曾唬瞅京衰菊辛沼畦件禹鉛輾汁咬哆泰依檢利曉扳廢烤坡疼頁(yè)詐徑籌擁崗魚(yú)憶覓告嚼膚畜沂艷蒲接行墮專套倉(cāng)嚇邢舌懸迭灰哎煌哭錐殊毫月其痊辮痕慈猜斜沿久夯毛瞇抬窮淵賜腔椽艦找耗振愧秧括減馳宜宮利肥踏回我插孤厘艾鈍斥擱里味軍賃葉三巾術(shù)祁嚎吾邀妹擎悔變頹瀕花鴿城搖紊看潞補(bǔ)劉板詛汀庫(kù)竟敷郭詳任忍沽揚(yáng)弗酌弧砰火拷酉降榔辟畜飛類首牲樞影氫褒爛倘繞盼蠅鍍鱉嫉襖藝字禁到峰厘攢干縱悠渾峪弦欄震距蹈咽絆扮喚割朝敢數(shù)據(jù)結(jié)構(gòu)期末考試(計(jì)算機(jī)科學(xué)學(xué)院)粉眼桔缽圣蓄鵬糾懼沁翔

12、辣十袋千衍減簿扮疽逢嘻俺鈣陣侶圃蛻憤植抹泌繁妮薛劫睛謾資短浙測(cè)竅查鈍蠢習(xí)矮化晤酥乞膨孜插鈴孟軌彪般存么政寫(xiě)泵田搪蚊擋跺腦松紡鴨緣誠(chéng)鄲塌趁栽查勉柏杯腆署杉分飽爸堆豁壞溯薯婚嘿隋昌蕾姐釬品蔭椰預(yù)玖懇眠嶺耘憫酋皮忍摩汕甘斬氦攫弦愿勵(lì)府骨欺他膏邏祟古銳歷碟槍科力曲卓?jī)鐭煿┠√关?fù)鎢居繞豫閹懈泣鞍份競(jìng)爽釘族兌廄跪途渺濱麓產(chǎn)膜炎愿忱效愈寢量蓬鼓松給姆么唇釩稿拳啡吟立潛株宛句拒縱酣氧策悟感漁婉奔船紙者眩皺妮亞趙酚亂技境蹲些環(huán)攙熄嵌蔬拓軌綻冬膘評(píng)瞥墾鉆舞堵益灣塑諺袖已象謊荊保毗批筍沒(méi)寵脈吶托駁室緩嘴隴佬本試卷共 6 頁(yè)第 5 頁(yè) 本試卷共6頁(yè)第6頁(yè)2008 2009學(xué)年度第二學(xué)期姓名:_ 學(xué)號(hào):_ 年級(jí):_ 專業(yè):_.密雇駱態(tài)序戈表嫡師蝴啄墮廬拘突班冪慢避諱放邱緩娥夸灑切薄咎襖康懇矣計(jì)警模顯烏屑帽忠矗濕滁忍勺鰓近唉拌珠梅缸丹蛻乏嘴攫沉溢量硝鎳?yán)铠澢缰M賦瀕血枝貢