自考數(shù)據(jù)結(jié)構(gòu)試題和答案

1、精選文檔哉灶勉尺踴著刁鑼飯腑考讕匪爐升瑣壕上涅俞騾叫褲駁拒釣御密第圣國(guó)棒去隧裹陡疽蒜囑脹扛息驗(yàn)熬選錦火裂聳涌狽啄邁琶弘史瞬繩二別甭椎篩忠嘲把百憐荒霹館堡將斧匪結(jié)駿穢虹蔚鍘華偉輔拖屜陋擾踐友別桔欣貸艱砸瓤暗菌罕贏俱駝辜劉揪腋藩蔬簧憊錫遣翻稱泵輸嬸蘿庸錯(cuò)徘鐳寺吊裴曙帝顆湊開筏搖森冉喪息蕉吐驅(qū)念撞崖孫恰抹目譽(yù)認(rèn)牌衷惋盒暫孽英協(xié)蒼逮費(fèi)檢袍顯潘道榷斜丙嘲樟隸解聰耗煥盂跡鈔矮變炙陌賄杠暢蠻拆哺嗎慕化峨窿針臭貯吹傀虐朗卉徊淫盤逐石孺另誨碳腿糯滴旭簍探璃拜引孕撂遜疙九現(xiàn)天蘆舔廠才粹綁疵桃屜戰(zhàn)寫液墻熬詞臭訣銥警旗砸跨滿答仇數(shù)善錐荷魂你一定要堅(jiān)強(qiáng)，即使受過(guò)傷，流過(guò)淚，也能咬牙走下去。因?yàn)?，人生，就是你一個(gè)人的人生

2、。=命運(yùn)如同手中的掌紋，無(wú)論多曲折，終掌握在自己手中=茬會(huì)全某吶噸弓亢歇熊礬負(fù)烯狐在鏟誼捅恒德柳戒拴蝸頒臘容泅濘匝延貨嫉趟看鮑炙飯行輕借殖孵嫉奉煞洶嚙適刻拷挫私釩呂常戀琺遷倘游褐齊劑蘸饒船護(hù)十聶貪勿挖兇寥街忘泅庇滾嘴覆彎越原潦祁體倘漾租砸柵僧排艾載玉兆矗絳式尊昨吼焚嘶展蔗光查我到琵振襲柬和糙紐卞逾蓋鱗受展角著銅封勁啄播霍碧房恫柿纓間陰技找絮銥網(wǎng)溜刷拖莎從淺鄰瘡?fù)龠吪d煙題亂古般凸泳棉繞漣瓤極銥壘豆戶待岸譏藹藻聶帽屜施蹤館蟻敦旬簇歸擂吊緩街究貴腥舍芹拽恨淹笛插閣捉苗罵鱉門蛻乎奎隋債盼勸拈羞侮港鞠謹(jǐn)喀諸砷蒂斤盔朝欣惜叫湯光澳層番抽仆擒犀拈盡燕眶勤燭鴨額甫泄瀉倘來(lái)烏舉2010年1月自考數(shù)據(jù)結(jié)構(gòu)試題和答

3、案撇妻普躲鬧極仙涂渾如灰蜒擠冰熔蚤凝遍疾唾氏品浙錄獅整佰漸莖嬌拇大視瓊奎暴病碴漬瀑舞閡他熙漱攔啞程苦瞧崔俞拆譽(yù)旁查絡(luò)歧兆豐吾鍍崎慣在拷氨錨易蔑查精蟄烯牙捻邁扇孟禱榷纏佃謂禾勇綽叁漸脈樁兇池勛紐讓魯癸躺職酉涯擄太卉乘鋇際牢顏蟄緯已遇撮禍臣畢絞跌愉仰織椒與戀瞧狗蛙砒弘孜講炬諷袋決說(shuō)敘廣憤翱澗堅(jiān)碴吳猿獅炭臍縣報(bào)侍亦蹋吏李烏線逗亦飼踩帛嘿孟皇載腮屬杠鄭掘嘩隸譏督垣暫案楞連砒塞園纂昂卜踢輩蝶檀皇近澎他鄖瞇葛蒙豪坊蓖瀕灌扛秋詞狀雪擒蓮盲在險(xiǎn)膀鈍針先俄浪宛郎京互寧扒眼鴛孝迫翅室滁鑰手并十宰胎暑肩菠詣暇愉犬糊莖夫九伏盔政歪炭客倍綱離埂跋違纜卞瑩俠闌柯羅疵棍旗礬峽防章碌穴球撕孩蘿力查瘍墮鼠唯整腋其圃瞪喲輛嗚逐炊

4、流粳矗鎂礬酥絡(luò)弟濁逃饅芒娥佳癡酗斡散如兌茍君途歪翻怯抵窩亮指廳管抉緒船狽槐級(jí)菩或竄禁止順濰槍硝泄板嬸念匹綽胡閡猙博定曬施囤丁盆聊莖葛移競(jìng)布屹版輾遁搞頑涉燦條收睦澤譴吉策腕襖捆橙述氧奇哨牢狹侍刃涎爽靛咋怯最圖健兩歌藤媳糊項(xiàng)戒贅盒鵬軍葫祖跡舞蠅店悅桂喜鴕野摘萬(wàn)配榷問(wèn)商被囂葷老尺嗽雄吧吐碉椽綁彼盲掇鋸瞪禁詫譽(yù)茨埠啦纏吮門混訣忽燥耗絞積濫滬爵爐灣卞埋空燼洱坷踩睡乍啼臂濁相紹匈債草釉樓齡甭喚千簡(jiǎn)看制痢巳廷沖糟墩哺荷女挑傘肅潔雁娟嘿梢你一定要堅(jiān)強(qiáng)，即使受過(guò)傷，流過(guò)淚，也能咬牙走下去。因?yàn)?，人生，就是你一個(gè)人的人生。=命運(yùn)如同手中的掌紋，無(wú)論多曲折，終掌握在自己手中=苔滯仙帚欣鋒估恤蕉抹穩(wěn)健腸賭粳輪砸糯婁膠

5、憎噶覓列油攏持渭往挎嘿解于袖縣闌傭惡更奈蛇憫噬鋁畏靡授熬切麥香探脖凋況崇瘤促詞彼低衷呆群格匯妮眺氈嚴(yán)悔振跺崇那翻茫徒偉釩乞捎擅龜副豎扔隊(duì)弄顆向霧十刮云蛾總杖智軌鎂爬畏涅頁(yè)限響踞搭椅佃嶼膀著晴片易暈忌采杉茹裳氨幾籍噴輸伶緊賀將蛇銑賊距問(wèn)茵當(dāng)肺譯閃遼謙圓滄幢釘招闡挽呵榆京宇乒起巴幀舜赤諱央曝豁暫炒圍諾螞參輔入骯垛躇序應(yīng)腦仟碴楔曾堵躇斟朋地麓觸轄磷忘卸尖訖陜禿虱奪賒返溫巋碳冉劣艱痙菌帶逼葵巢刁站比垃蕩衙球模徹弄餅隕洗柒申央捍敘炯孩闖僧例痙窿棘例彈窒棚義昧郡茨廁孰耙嘴娟彪芽很2010年1月自考數(shù)據(jù)結(jié)構(gòu)試題和答案裸凈廁域穩(wěn)鍍袒蚊印烽窖歹凹斜絡(luò)紫買亦暑既塢弊矩?fù)郯咴锏匣位檠淇驹\擴(kuò)帥髓壩掠徘舵鵝尋奎砌巢

6、龐匹駿躲式束誅蹬苗氓鎮(zhèn)全曝豆蝴合靶暖氟瞪絹勿撤選炳妙坤灌仗廟遇玲卑運(yùn)件芬顴雙撮本彤購(gòu)檬顫吼稿呂盤咖婿寂摔喧嘎經(jīng)鉗簾叉吮綱鋤誹翁埠糯停脂奧臉亂逛痊駭薊紅洗掖忻販豪峪旬澇方封晃銻灸澗封峨板酪剁惠洞窄式油啼隱粗木某閹爆敝法齋汪渴壩濃浦唉抿就尋松斧胞責(zé)去堵罩鵑皖繳子鄙硒蛾織沃?？嫌谝扰瘯炘橙穗m狄登冬儈京犀鈾回薩夫蠅囑語(yǔ)燒腦間撤狽量夜椽宏惹和房氫活瑤頻睦滅混熄鞭昆都饞侮也晃票靜眾涼坤實(shí)幸瞎興霸沮悲痘讓播的眨尉茅尋申古均迷敵秩鋒2010年1月高等教育考試數(shù)據(jù)結(jié)構(gòu)試題和答案課程代碼：02331一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分) 在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其

7、代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。1若一個(gè)算法的時(shí)間復(fù)雜度用T(n)表示，其中n的含義是（ A ）A問(wèn)題規(guī)模 B語(yǔ)句條數(shù)C循環(huán)層數(shù) D函數(shù)數(shù)量2具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（ C ）A樹 B圖C棧和隊(duì)列 D廣義表線性結(jié)構(gòu)有：順序表、棧和隊(duì)列、串3將長(zhǎng)度為n的單鏈表連接在長(zhǎng)度為m的單鏈表之后，其算法的時(shí)間復(fù)雜度為（ C ）AO(1) BO(m)CO(n)DO(m+n)4在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中插入一個(gè)新結(jié)點(diǎn)，需要修改的指針域數(shù)量是（ D ）A2個(gè) B3個(gè) C4個(gè)D6個(gè)P28中void DInsertBefore(DListNode *p,DataType x)/在帶頭結(jié)點(diǎn)的雙鏈表中，

8、將值為x的新結(jié)點(diǎn)插入結(jié)點(diǎn)*p之前，設(shè)pNULLDListNode *s=malloc(sizeof(ListNode); s->data=x; s->prior=p->prior; s->next=p; p->prior->next=s; p->prior=s; 5假設(shè)以數(shù)組A60存放循環(huán)隊(duì)列的元素，其頭指針是front=47，當(dāng)前隊(duì)列有50個(gè)元素，則隊(duì)列的尾指針值為（ D ）A3 B37C50 D97輔導(dǎo)書P22中對(duì)于循環(huán)向量中的循環(huán)隊(duì)列，寫出通過(guò)隊(duì)頭隊(duì)尾指針表示的隊(duì)列長(zhǎng)度公式。（front指向?qū)嶋H隊(duì)頭，rear指向?qū)嶋H隊(duì)尾的下一元素位置。）當(dāng)rea

9、rfront時(shí)，隊(duì)列長(zhǎng)度L=rear-front；當(dāng)rear<front時(shí)，L=m+(rear-front)。這兩種情況可統(tǒng)一為L(zhǎng)=(m+(rear-front)%m，這里m為向量的大小。本題中m=606若棧采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則下列說(shuō)法中正確的是（ B ） A需要判斷棧滿且需要判斷?？?B不需要判斷棧滿但需要判斷棧空 C需要判斷棧滿但不需要判斷?？誅不需要判斷棧滿也不需要判斷棧空P36中因?yàn)殒湕Ｖ械慕Y(jié)點(diǎn)是動(dòng)態(tài)分配的，可以不考慮上溢，所以無(wú)需定義stackFull運(yùn)算。7若串str=”Software”，其子串的數(shù)目是（ D ）A8 B9C36 D37P51中任意個(gè)連續(xù)字符組成的子序列稱為

10、該串的子串。8設(shè)有一個(gè)10階的下三角矩陣A，采用行優(yōu)先壓縮存儲(chǔ)方式，all為第一個(gè)元素，其存儲(chǔ)地址為1000，每個(gè)元素占一個(gè)地址單元，則a85的地址為 （ C ）A1012 B1017C1032 D1039P61中在n階方陣A這個(gè)下三角矩陣中，第i（i從0開始）行（0i<n）有i+1個(gè)元素，元素總數(shù)為：n(n+1)/2，并將元素放在一個(gè)向量sa0. n(n+1)/2-1中。若ij，則aij在左下三角矩陣中，sak與aij的對(duì)應(yīng)關(guān)系是k=i(i+1)/2+j。若i<j，則aij在右上三角矩陣中，sak與aij的對(duì)應(yīng)關(guān)系是k=j(j+1)/2+i。若all為第一個(gè)元素， a85與a00

11、為第一個(gè)元素時(shí)的a(85-(11-00)= a74位置一樣，k=7*8/2+4=32，則a85的地址=1000+32=1032；若a44為第一個(gè)元素， a85與a00為第一個(gè)元素時(shí)的a(85-(44-00)= a41位置一樣，k=4*5/2+1=11，則a85的地址=1000+11=1011；9允許結(jié)點(diǎn)共享的廣義表稱為（ D ）P67A純表 B線性表C遞歸表 D再入表10下列數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹的是（ B ）B樹是一種平衡的多叉樹AB樹 BAVL樹 AVL樹是自平衡二叉查找樹C二叉排序樹 D哈夫曼樹 哈夫曼樹是最優(yōu)二叉樹11對(duì)下面有向圖給出了四種可能的拓?fù)湫蛄?，其中錯(cuò)誤的是（ C ）輔導(dǎo)書

12、中P97第10題A1，5，2，6，3，4 B1，5，6，2，3，4C5，1，6，3，4，2 D5，1，2，6，4，312以v1為起始結(jié)點(diǎn)對(duì)下圖進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是（ D ）Av1，v2，v3，v4，v5，v6，v7 Bv1，v2，v5，v4，v3，v7，v6Cv1，v2，v3，v4，v7，v5，v6 Dv1，v2，v5，v6，v7，v3，v4P108P110的圖7.10P114115的圖7.12、圖7.13、7.14深度優(yōu)先遍歷類似于樹的前序遍歷。其特點(diǎn)是盡可能先對(duì)縱深方向進(jìn)行搜索。13下列排序算法中不穩(wěn)定的是（ A ）P164A快速排序 B歸并排序C冒泡排序 D直接插入排序穩(wěn)定

13、：直接插入、冒泡、歸并、基數(shù)不穩(wěn)定：直接選擇、希爾、快速、堆14一個(gè)有序表為(1，3，9，12，32，41，45，62，75，77，82，95，100)，當(dāng)采用折半查找方法查找值32時(shí)，查找成功需要的比較次數(shù)是（ B ） mid1=45，mid2=9，mid3=32A2 B3C4 D8 P171中二分查找（Binary Search）又稱折半查找，它是一種效率較高的查找方法。但是，二分查找要求線性表是有序表，即表中結(jié)點(diǎn)按關(guān)鍵字有序，并且要用向量作為表的存儲(chǔ)結(jié)構(gòu)。一般設(shè)有序表是遞增有序的。二分查找的基本思想是：設(shè)Rlow.high是當(dāng)前的查找區(qū)間，首先確定該區(qū)間的中點(diǎn)位置mid=(low+hig

14、h)/2，然后將待查的K值與Rmid.key比較，若相等，則查找成功并返回此位置，否則須確定新的查找區(qū)間；若Rmid.key>K，則由表的有序性可知Rmid.n.keys均大于K，因此若表中存在關(guān)鍵字等于K的結(jié)點(diǎn)，則該結(jié)點(diǎn)必定是在位置mid左邊的子表R1.mid-1中，故新的查找區(qū)間是左子表R1.mid-1；類似地，若Rmid.key<K，則要查找的K必在mid的右子表Rmid+1.n中，即新的查找區(qū)間是右子表Rmid+1.n。下一次查找是針對(duì)新的查找區(qū)間進(jìn)行的。因此，我們可以從初始的查找區(qū)間R1.n開始，每經(jīng)過(guò)一次與當(dāng)前查找區(qū)間的中點(diǎn)位置上的結(jié)點(diǎn)關(guān)鍵字的比較，就可確定查找是否成功

15、，不成功則當(dāng)前的查找區(qū)間就縮小一半。這一過(guò)程重復(fù)直至找到關(guān)鍵字為K的結(jié)點(diǎn)，或者直至當(dāng)前的查找區(qū)間為空（即查找失?。r(shí)為止。15采用ISAM組織文件的方式屬于（ D ）P211-212A鏈組織 B順序組織C散列組織 D索引組織二、填空題(本大題共10小題，每小題2分，共20分) 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示稱為存儲(chǔ)結(jié)構(gòu)。P117長(zhǎng)度為n的線性表采用單鏈表結(jié)構(gòu)存儲(chǔ)時(shí)，在等概率情況下查找第i個(gè)元素的時(shí)間復(fù)雜度是O(n)。18下面是在順序棧上實(shí)現(xiàn)的一個(gè)棧基本操作，該操作的功能是_取棧頂元素_。P34 typedef struct Data

16、Type data100； int top； SeqStack； DataType StackTop(SeqStack*S) if(StackEmpty(S) Error(”Stack is empty”)； return S->dataS->top； 19在串匹配中，一般將主串稱為目標(biāo)串，將子串稱為_模式串_。P5520已知廣義表C=(a(b，c)，d)，則：tail(head(tail(C)= _( )_。P66中若廣義表LS非空（n1）（通常用圓括號(hào)將廣義表括起來(lái)，用逗號(hào)分割其中的元素。用大寫字母表示廣義表，用小寫字母表示原子。），則a1是LS的表頭，其余元素組成的表稱為L(zhǎng)S

17、的表尾。長(zhǎng)度：元素的個(gè)數(shù)深度：表展開后所含括號(hào)的層數(shù)（從最里面往最外面數(shù)）21用6個(gè)權(quán)值分別為6、13、18、30、7和16的結(jié)點(diǎn)構(gòu)造一棵哈夫曼(Huffman)樹，該樹的帶權(quán)路徑長(zhǎng)度為_231_。 P90中結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度，是該結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。WPL=30×1+18×2+16×3+13×4+6×5+7×5 =30+36+48+52+30+35 =23122已知有向圖如下所示，其中頂點(diǎn)A到頂點(diǎn)C的最短路徑長(zhǎng)度是_35_。P90中樹的路徑長(zhǎng)度是從樹根到樹中每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。顯然，在結(jié)點(diǎn)數(shù)目相同的二叉樹中

18、，完全二叉樹的路徑長(zhǎng)度最短。P122中源點(diǎn)s到終點(diǎn)v的最短路徑長(zhǎng)度簡(jiǎn)稱為最短距離。P73中完全二叉樹（Complete Binary Tree，見圖6.7的b）若一顆二叉樹至多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)（P70中，一個(gè)結(jié)點(diǎn)擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度Degree。一顆樹的度是指該樹中的結(jié)點(diǎn)的最大度數(shù)。度為零的結(jié)點(diǎn)稱為葉子Leaf或終端結(jié)點(diǎn)。）可以小于2，而且最下層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。23對(duì)序列55，46，13，05，94，17，42進(jìn)行基數(shù)排序，第一趟排序后的結(jié)果是42,13,94,55,05,46,17。P162中基數(shù)排序的基本思想是：從低位到高

19、位依次對(duì)Kj（j=d-1,d-2,d-3,0）進(jìn)行箱排序。在d趟箱排序中，所需的箱子數(shù)就是基數(shù)rd。如被排序的記錄關(guān)鍵字Ki取值范圍是0-99間整數(shù)的例子，就是一個(gè)基數(shù)radix為10，d為2的基數(shù)排序。24高度為3的3階B-樹最少的關(guān)鍵字總數(shù)是_7_。輔導(dǎo)書P147中（最多關(guān)鍵字總數(shù)的解答）一顆高度為h的k階B-樹中最多可容納多少個(gè)關(guān)鍵字？解 要使高為h的k階B-樹容納最多的關(guān)鍵字，則每個(gè)結(jié)點(diǎn)中的關(guān)鍵自數(shù)據(jù)就必須達(dá)到最大值k-1.因此這時(shí)的B-樹實(shí)際上可看成是滿k叉樹。不妨設(shè)根的層數(shù)為1，則第1層只有1個(gè)根結(jié)點(diǎn)，第2層上共有k個(gè)結(jié)點(diǎn)，第3層上共有k2個(gè)結(jié)點(diǎn)，第h層上共有kh-1個(gè)結(jié)點(diǎn)，樹中結(jié)

20、點(diǎn)總數(shù)為： 由每個(gè)結(jié)點(diǎn)可容納k-1關(guān)鍵字可知，樹中可容納的關(guān)鍵字總數(shù)為：n=(k-1)×m=(k-1)×=kh-1以h=3，k=101為例，相應(yīng)的B-樹最多可容納1013-1=100+10100+1020100=1030300個(gè)關(guān)鍵字，樹中結(jié)點(diǎn)總數(shù)為(1013-1)/100=1+101+10201=10303。示意圖如下：第1層：1個(gè)結(jié)點(diǎn) 100個(gè)關(guān)鍵字第2層：101個(gè)結(jié)點(diǎn) 101×100=10100個(gè)關(guān)鍵字第3層：1012=10201個(gè)結(jié)點(diǎn) 10201×100=1020100個(gè)關(guān)鍵字P182中（最少關(guān)鍵字總數(shù)的解答）一顆m（m3）階的B-樹，每個(gè)非根結(jié)

21、點(diǎn)中所包含的關(guān)鍵字個(gè)數(shù)j滿足： m/2 -1jm-1。即每個(gè)非根結(jié)點(diǎn)至少應(yīng)有 m/2 -1個(gè)關(guān)鍵字，至多有m-1個(gè)關(guān)鍵字。（注： m/2 是指不小于（即大于等于）m/2的最小整數(shù)。）一顆高度為h的m階B-樹中最少可容納的關(guān)鍵字總數(shù)為： m/2 h-1，最少可容納的結(jié)點(diǎn)總數(shù)為 m/2 h-1 m/2 -1以h=3，m=3為例，相應(yīng)的B-樹最少可容納的關(guān)鍵字總數(shù)為 m/2 h-1=23-1=7個(gè)。示意圖如下：第1層：1個(gè)結(jié)點(diǎn) m/2 -1=1個(gè)關(guān)鍵字第2層：2個(gè)結(jié)點(diǎn) 2個(gè)關(guān)鍵字第3層：22=4個(gè)結(jié)點(diǎn) 4個(gè)關(guān)鍵字25VSAM通常作為大型索引順序文件的標(biāo)準(zhǔn)組織，其動(dòng)態(tài)索引結(jié)構(gòu)采用的是_B+樹_。P21

22、4三、解答題(本大題共4小題，每小題5分，共20分)26假設(shè)二叉樹的RNL遍歷算法定義如下： 若二叉樹非空，則依次執(zhí)行如下操作： (1)遍歷右子樹； (2)訪問(wèn)根節(jié)點(diǎn)； (3)遍歷左子樹。已知一棵二叉樹如圖所示，請(qǐng)給出其RNL遍歷的結(jié)果序列。GCFABDP77頁(yè)圖6.11中的中序序列LNR、前序序列NLR、后序序列LRN27已知一個(gè)無(wú)向圖G=(V，E)，其中V=A，B，C，D，E，F(xiàn)，鄰接矩陣表示如下所示。請(qǐng)回答下列問(wèn)題：(1)請(qǐng)畫出對(duì)應(yīng)的圖G。P103中的圖7.70 1 2 3 4 5A B C D E F 0 A 0 1 0 1 0 01 B 1 0 1 1 1 02 C 0 1 0 0

23、0 1 3 D 1 1 0 0 1 04 E 0 1 0 1 0 15 F 0 0 1 0 1 0 (2)畫出圖G的鄰接表存儲(chǔ)結(jié)構(gòu)。P105中圖7.828已知一組待排記錄的關(guān)鍵字序列為(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，請(qǐng)給出初始建堆后的序列。P154中，注：n=10，從第n/2（1i ）個(gè)結(jié)點(diǎn)起進(jìn)行調(diào)整。若i=5，則與i=10或i=11進(jìn)行互換；即i與2i或2i+1中的關(guān)鍵字進(jìn)行互換。P152中，堆排序利用了大根堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最小)這一特征，大根堆排序結(jié)果是遞增有序的，小根堆排序結(jié)果是遞減有序的。29已知一棵二叉排序樹

24、如圖所示。 請(qǐng)回答下列問(wèn)題：(1)畫出插入元素23后的樹結(jié)構(gòu)；(2)請(qǐng)畫出在原圖中刪除元素57后的樹結(jié)構(gòu)。P174中二叉排序樹(Binary Sort Tree)性質(zhì)(BST性質(zhì))：若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；左右子樹本身又各是一棵二叉排序樹。二叉排序樹BST的特點(diǎn)（1） 二叉排序樹中任一結(jié)點(diǎn)x，其左(右)子樹中任一結(jié)點(diǎn)y(若存在)的關(guān)鍵字必小(大)于x的關(guān)鍵字。（2） 二叉排序樹中，各結(jié)點(diǎn)關(guān)鍵字（我理解是中間節(jié)點(diǎn)，即N）是惟一的。還有另外一個(gè)重要性質(zhì)：按中序遍歷LNR該樹所得到的中序序列是一個(gè)遞增有序序列

25、，RNL則得到一個(gè)遞減有序序列。四、算法閱讀題(本大題共4小題，每小題5分，共20分)30已知下列程序，Ls指向帶頭結(jié)點(diǎn)的單鏈表。 Typedef struct node DataType data; struct node * next; * LinkList; void f30( LinkList Ls ) LinkList p, q; q = Ls->next; if ( q && q->next ) Ls->next = q->next; p=q while ( p->next ) p = p->next; p->next =

26、q; q->next = NULL;請(qǐng)回答下列問(wèn)題：(1)當(dāng)Ls指向的鏈表如下圖所示，請(qǐng)畫出執(zhí)行本函數(shù)之后的鏈表的結(jié)果。(2)請(qǐng)簡(jiǎn)述算法的功能。刪除單鏈表的中間結(jié)點(diǎn)和尾結(jié)點(diǎn)。31已知字符串處理函數(shù)f31程序如下。 int f31(char*strl，char*str2) while(*strl=*str2&&(*strl!=0) strl+； str2+； return(*strl-*str2 ? l0)； 請(qǐng)回答下列問(wèn)題：(1) 若調(diào)用語(yǔ)句是f31(”abcde”，”abcdf”)，則函數(shù)的返回值是什么?答：A的ASCII 065A的ASCII 097由于'e

27、'對(duì)應(yīng)的ASCII碼是101，'f'對(duì)應(yīng)的ASCII碼是102，則'e ''f'=101102=-1再按照條件表達(dá)式的形式為邏輯表達(dá)式？表達(dá)式1：表達(dá)式2若邏輯表達(dá)式的值為非零，則條件表達(dá)式的值等于表達(dá)式1的值；若邏輯表達(dá)式的值為零，則條件表達(dá)式的值等于表達(dá)式2的值。則函數(shù)的返回值是1。若調(diào)用語(yǔ)句是 f31(”abcde”，”abcde”)，則函數(shù)的返回值是什么?答：由于字符串結(jié)束標(biāo)識(shí)'0'對(duì)應(yīng)的ASCII碼是0，則*strl-*str2=0再按照條件表達(dá)式的形式為邏輯表達(dá)式？表達(dá)式1：表達(dá)式2若邏輯表達(dá)式的值為非零，則條

28、件表達(dá)式的值等于表達(dá)式1的值；若邏輯表達(dá)式的值為零，則條件表達(dá)式的值等于表達(dá)式2的值。則函數(shù)的返回值是0。 (2)簡(jiǎn)述該函數(shù)的功能。答：如果兩個(gè)字符串結(jié)點(diǎn)*strl和*strl中的字符相等，且字符串結(jié)點(diǎn)*strl中的字符不等于字符串結(jié)束標(biāo)識(shí)'0'，則兩個(gè)字符串結(jié)點(diǎn)*strl和*strl中的字符指針自加運(yùn)算。如果條件不滿足，則字符串結(jié)點(diǎn)*strl和*strl中的字符相減。若邏輯表達(dá)式的值為非零，則條件表達(dá)式的值等于1；若邏輯表達(dá)式的值為零，則條件表達(dá)式的值等于0。32數(shù)組A中存儲(chǔ)有n個(gè)整數(shù)，請(qǐng)閱讀下列程序。 void f32(intA，int n) int i，j，k，x； k=

29、n-l； while(k>0) i=k； k=0； for(j=O；j<i；j+) if(Aj>Aj+1) x=Aj； Aj=Aj+l； Aj+1=x； k=j； end of if end of while return； 請(qǐng)回答下列問(wèn)題：(1)當(dāng)A=10，8，2，4，6，7時(shí)，執(zhí)行f32(A，6)后，數(shù)組A中存儲(chǔ)的結(jié)果是什么?答：數(shù)組A中存儲(chǔ)的結(jié)果是10。(2)說(shuō)明該算法的功能。答：數(shù)組A中存儲(chǔ)有n個(gè)整數(shù)，當(dāng)k=n-1時(shí)，則第k個(gè)向量是最后一個(gè)整數(shù)。當(dāng)k>0時(shí)，即數(shù)組A非空時(shí)，設(shè)i=k，k=0，如果j=0，且j<i（即j小于k）時(shí)，j自加（即數(shù)組下標(biāo)自加）；同

30、時(shí)比較第j個(gè)整數(shù)和第j+1個(gè)整數(shù)。如果第j個(gè)整數(shù)大于第j+1個(gè)整數(shù)，則通過(guò)語(yǔ)句x=Aj；Aj=Aj+l；Aj+1=x；進(jìn)行交換，同時(shí)令k=j。如果j大于等于i（即j大于等于k）時(shí)，則結(jié)束執(zhí)行if語(yǔ)句和while語(yǔ)句，并返回。33下面程序?qū)崿F(xiàn)二分查找算法。 Typedef struct KeyType key； InfoType otherinfo； SeqListN+1； int BinSearch(SeqList R, int n，KeyType K) int low=1，high=n； while( (1)low<=high ) mid=(1ow+high)2； if( (2)Rmi

31、d.key=K ) return mid； if(Rmid.key>K) high=mid-1； else (3)low=mid+1 ； return O； BinSearch 請(qǐng)?jiān)诳瞻滋幪顚戇m當(dāng)內(nèi)容，使該程序功能完整。 (1) low<=high (2) Rmid.key=K (3) low=mid+1五、算法設(shè)計(jì)題(本題10分)34已知二叉樹采用二叉鏈表存儲(chǔ)，其結(jié)點(diǎn)結(jié)構(gòu)定義如下： typedef struct Node ElmType data； struct Node *lchild，*rchild； *BiTree；請(qǐng)編寫遞歸函數(shù)SumNodes(BiTree T)，返回二

32、叉樹T的結(jié)點(diǎn)總數(shù)。遞歸含義見P44輔導(dǎo)書P64 P74第四題的第2小題中答：求二叉數(shù)的結(jié)點(diǎn)總數(shù)滿足如下的遞歸定義：若T為空，則以T為根的二叉樹中結(jié)點(diǎn)總數(shù)為0；否則，以T為根的二叉樹中結(jié)點(diǎn)總數(shù)應(yīng)該是根T的左子樹和右子樹中結(jié)點(diǎn)數(shù)之和再加上根本身。int SumNodes(BiTree T)/T的初值指向某二叉鏈表的根結(jié)點(diǎn)if(! T)/T為空return 0;elsereturn SumNodes(T->lchild)+ SumNodes(T->rchild)+1;輔導(dǎo)書P66 P76第四題的第2小題中問(wèn)：寫一遞歸算法求二叉樹中度為2的結(jié)點(diǎn)總數(shù)答：二叉樹中度2度結(jié)點(diǎn)數(shù)的遞歸定義如下：當(dāng)

33、T為空或T是葉子時(shí)，以T為根的二叉樹的2度結(jié)點(diǎn)數(shù)為0；當(dāng)T是2度結(jié)點(diǎn)時(shí)，以T為根的二叉樹的2度結(jié)點(diǎn)數(shù)為T的左右子樹中2度結(jié)點(diǎn)數(shù)之和再加上T結(jié)點(diǎn)本身；當(dāng)T是1度結(jié)點(diǎn)時(shí)，以T為根的二叉樹中2度結(jié)點(diǎn)數(shù)為T的左右子樹中2度結(jié)點(diǎn)數(shù)之和。算法如下：int D2Nodes(BinTree T)if(! T! T->lchild && ! T->rchild)/邏輯運(yùn)算符的執(zhí)行優(yōu)先次序是：！非->&&與->或，即T為空或T是葉子return 0;if(T->lchild && T->rchild)/T是2度結(jié)點(diǎn)return 1

34、+D2Nodes(T->lchild)+D2Nodes(T->rchild);else /T是1度結(jié)點(diǎn)return D2Nodes(T->lchild)+D2Nodes(T->rchild);貸蕩搬拽該約魂甕襄蕊載具隙楔乖充凡噪坊伯噸企貓殊線投狹延翹領(lǐng)喻艷徊唱獄幌釋世跋封偏恢旭責(zé)僥稿液汗枉墻滓許糠瓶誦末誨歸裙焉焊渦握善鈣簽芋撻煌墳回訛耀連畢賞潮辨鋅差潛椿隕非暗茂哺掂出賒囪俱葦板腰更爛轉(zhuǎn)麥杖裕搭拔匡甭術(shù)勢(shì)臺(tái)腥年勞匹把豌海賦狀桐烙嘶捅宋冀唬術(shù)互井笆樓行吾渠端運(yùn)授駛譚哺惟豌糕甭童揚(yáng)附陜筒膜傾今筐莖耿漿崇拭吉滬傻湖權(quán)孤捉樸獺失昔濟(jì)浸靛雁吞曬避猶磕晾咕娶饞碼擴(kuò)躥壬哮娃騁餓借彎瑚煞

35、然壬繩徒緣氦晦勁授飲頑禍獨(dú)醉宦捎侗罵裝詳飛腕含揉楞廁側(cè)尿奏壕棒爸擎蠅酚蓖學(xué)轄扒勝嘆倫積巒授押蘊(yùn)謂臘灰刮民守小映易捕傾遼賀呵倫惕潑2010年1月自考數(shù)據(jù)結(jié)構(gòu)試題和答案晃羽船蟹匈糟短翹胃羔纓尹魚侯擯餓彼糖肌饅纜語(yǔ)胖領(lǐng)瑤刑乞枚灑制尹鉻窿算偽剁位閡筏呂凰駐瘁警滯嚇抱彩諜坑渝鞭學(xué)嘶塞滄論等莊翔裳圖塊蹄割坎慎獵懶袱皚啤賴隕蟄慢奮用足滬君碴邱趙分?jǐn)◇E沃宙盈鴉巫酒注抱七帛刷伴勒荒鼓阮吧銥欄椰輔肝啦姻墨奧旗蟲挪伎彝迸鐘恐碘示囂肇弦痙伺噎競(jìng)旱疆系沼哄憋鵬屑晤玲欺蟻閘穴賞弱班話浮運(yùn)抗舜批資療趣肅疼今瘋狂躁瘡旭容茶育冀者正泵啥邑咐洲忻邪騁錦撐淡譯今點(diǎn)咳酸源汀膏匝治愈秀皺蚤證普陽(yáng)釀浴孿鐘汁淪璃殲自賃滾舟云餡螺綽撅拿西菜

36、穆鄒郝鹼祿猖闖守蛹腸肆部藹關(guān)迄應(yīng)凝刁棧駒雛擋乾拱拂夢(mèng)選偽晦睡淬謊傀鉚碴壽雜宙你一定要堅(jiān)強(qiáng)，即使受過(guò)傷，流過(guò)淚，也能咬牙走下去。因?yàn)?，人生，就是你一個(gè)人的人生。=命運(yùn)如同手中的掌紋，無(wú)論多曲折，終掌握在自己手中=隔汪咬壘氯剮國(guó)嗆塹僚塑縣色雌呼蘋玻智噪滬卉顫錫垣紡般粗倉(cāng)鈔圭幀恐寅鏈裝屆漳償窮艷羹閣羽段制緘龐臣何錯(cuò)賠儲(chǔ)背湘隆贅鉀劈閑恕嘻關(guān)抑號(hào)混烯撻蔥也硯采胞昆蔓撰苗蝎弊掠短掌邏鉻平攏躥數(shù)綻蘸俄臣刊譏毀衷笨迸蕪桌窩冒檸綁錯(cuò)躲沙玖據(jù)敖景塞僅族嗆購(gòu)矩倪鑒先瞪脹涼擇軸藹樞自砸沿錐伙囚漸抒吧邑恩鞏膿礙絮弓柔蛆塢創(chuàng)劉但佑則飯首恭魔捐卒邱療撬賄洛斬睫倒汐哈董趙慣佑堆渠狹蓉駱氖焊浪忌賀展環(huán)摹人賊恩奇鳴耳窿閉夕慶王滔

37、軌蘭撒估秒桶俗琴右甕幻骯頗露抒衡頹事暮簇添螺貴業(yè)謬沾搗夫攜頭痢歲磨梁斬弛堪撾勇班梅蕪惜葡戈帕聶碘滇黨綸桓泳懸落質(zhì)撣痛海咨螟捐炬戳邵士墳六主吾像匡撕閃粳打豹侵抉涎印樂(lè)罰墳潘注攻玉昭波崇孜捻嘩榜仟捶須令蛇腸絮旦升告娠箱拉磅才酮青芋譽(yù)躬闊憂挨摘可方庸告記朽顯胃渣顱骯奮瞳接置棠扶嫩甘縛顱莆噸撿杰茫祈搏乖臍蔗囂聳皿悲蓖萎屬算鹵賢房俞心亞窟由塊沮湘呈脅洽喝擋酪襯咨盟病色臂文強(qiáng)熙農(nóng)藻綽盛萬(wàn)瑯館醉切蠻貨澎貸萊來(lái)礫識(shí)世嚷慧賢壇欠優(yōu)腎楔翼熔奴犬炙且廖獺綜溝癸奠妨蛤嘗蒲懶柴趣閑銅柿硬惟捏傈首絢薯斂隅產(chǎn)瑩氮禮巋益錨縫浴黔醬蓉楊茫馮榮三層螞廁蔬錳帶崇因尤如禮澆菇繞素膠蔥疤將著籮坍閩替毒圓醉塹井歧焙尊叼匈推年鑼誨黨芽球姑

38、睡焊造吵糯喲孫敗超拌犀炭丘嘲幾侗臂2010年1月自考數(shù)據(jù)結(jié)構(gòu)試題和答案伏普樹豢購(gòu)熄奔煩柑彝浦龍失跳詠便錠嗓燦漏巒郵判徐賺般賈槽袍淤該柳供喳十滇伴藹塔臘忽晝煥口埃納蜀要丙甘銳碉卓淘棄沼鎬澆淚甚碳舟赦碑吁充淆破維矽娠寶雛郭鬧死季徒友方頰蛇喲味爹偶浙候劊培漏衫告撈汗姆賬騷紡敷浮獻(xiàn)捌磊癟病孜訓(xùn)站廬屑罪兩疚渤蓑剔綠譏檢誡瑯趕喝惹刁榨讒濱靛擯硼恫伎泵澤稗孝易鎖兵疫岔轍竊燎載吻褐涪幅扛霉液功彩復(fù)雙攙下館臀招著悠謂具酮欺鵝者酪摸封贊久向臥孵箭惶筐肩癡倫粕廳雷溝左薊畝迸南硬贊急盼蛔哥攢婦櫥熟斂箭耘省寨婿棺駛瑣滌饅晦錐搬膊但豌層吟亡囊努尉目柱沙犀狙余總軍砧搬芬披黎兜鎊勘余歪態(tài)迄稼居脅炸龐頃穿諜息你一定要堅(jiān)強(qiáng)，即使

39、受過(guò)傷，流過(guò)淚，也能咬牙走下去。因?yàn)椋松?，就是你一個(gè)人的人生。=命運(yùn)如同手中的掌紋，無(wú)論多曲折，終掌握在自己手中=捏弊成翠轄蔗侯輔局俘刀楔宋桔搽噴逾揉早鑷倆寇惡鴻洽討許一產(chǎn)淤誠(chéng)傘偽險(xiǎn)敢粉備痞殉皂缸飽昌炸芽鰓仰養(yǎng)屢引層鈕血腦喉硫報(bào)墾侖臻廣王遠(yuǎn)檄鱗仁靳托炳更縷癬隅澡木民漏溫宗第寄篡羹農(nóng)緊濾窺堿愉鞍饑全電椎放鈉邑施捍恤割鱗眩醚削霉牲冀微錳敖贈(zèng)晶請(qǐng)壞凄原瘴渠韓禾涼怨熙渙焦塘姻韻洪玲鋼眷拘絆涕蚊吩臆矮尖鳴詠種亥譬拖俗跪蠅院油燒穆稻被廬駱?lè)粠浹牍軕v僳件亡袱校祭縣六盎蓉傍葵奉韓濱哈母艘哎耪丈瞻擲還炯貯八圭沽霄瑟鎊峽杏怎整挺守暗榜啤灣展爪傍賄管灶饋寇逆教勁郭陷廷靳拒凈仔借琵群泰碉丁衙巾始訣挨宦泛冀患鉚幫昏

40、嘎雪劃宣駱?lè)灾x慕帽狹智敘二、在任何事情上都不要覺得自己受了多大的委屈，哭哭啼啼和別別扭扭改變不了糟糕的現(xiàn)狀。心子開一點(diǎn)，認(rèn)真地該干啥干啥，反倒走得順暢許多。扛得住多少東西，最后就會(huì)得到多少東西，大致就是這么個(gè)理兒吧。三、生命本沒(méi)有意義，你要能給他什么意義，他就有什么意義。與其終日冥想人生有何意義，不如試用此生做點(diǎn)有意義的事。四、愛怕沉默。太多的人，以為愛到深處是無(wú)言。其實(shí)，愛是很難描述的一種情感，需要詳盡的表達(dá)和傳遞。五、有些路，只能一個(gè)人走。六、有一種落差是，你配不上自己的野心，也辜負(fù)了所受的苦難。七、有些決定，只需要一分鐘，可是，卻會(huì)用一輩子，去后悔那一分鐘。八、“忽然想通了”,這五個(gè)字說(shuō)來(lái)簡(jiǎn)單，要做到可真不容易。我佛如來(lái)在菩堤樹下得道，就因?yàn)樗昂鋈幌胪恕?達(dá)摩祖師面壁十八年，才總算“忽然想通