數(shù)據(jù)結(jié)構(gòu)(本科)形成性考核冊(cè)答案-全文預(yù)覽
【正文】 。作業(yè)3答案（本部分作業(yè)覆蓋教材第67章的內(nèi)容）一、單項(xiàng)選擇題1．B 2．B 3．D 4．C 5．B 6．A 7．A 8．C 9．A 10. D11. A 12．C 13．C 14．B 15．B 16．C 17．B 18．C 19．A 20．B21．D 22．B 23. B 24. B 25. C 26. A 27．A 28．C二、填空題 1．子樹樹木或后繼結(jié)點(diǎn)數(shù)2．樹中所有結(jié)點(diǎn)的度的最大值3．分支結(jié)點(diǎn) 非終端結(jié)點(diǎn)4．葉子結(jié)點(diǎn) 終端結(jié)點(diǎn)5．子樹的根 后繼結(jié)點(diǎn) 孩子結(jié)點(diǎn)6．祖先7．樹中結(jié)點(diǎn)的最大層數(shù)8． 9．根結(jié)點(diǎn) 左子樹 右子樹10．左子樹 根結(jié)點(diǎn) 右子樹11．左子樹 右子樹 根結(jié)點(diǎn)12．權(quán)13．帶權(quán)路徑長(zhǎng)度之和14．最優(yōu)二叉樹 最小的二叉樹15．69 16．2m1 17．多對(duì)多18．所有頂點(diǎn) 一次19．先序 20．按層次21．n222．鄰接矩陣 鄰接表23．2(n1)24．n125．棧三、綜合題1．寫出如下圖所示的二叉樹的先序、中序和后序遍歷序列。 while (p!=Qrear) { printf(%c ,pdata)。 } int emptyqueue(LinkQueue *Q) /*判斷隊(duì)列是否為空算法*/ { if (Qrear==NULL) return(1)。 /*t指向第一個(gè)結(jié)點(diǎn)*/ Qrearnext=tnext。 return(0)。 /*將s鏈接到隊(duì)尾*/ Qrear=s。 if (Qrear==NULL) /*原為空隊(duì)時(shí)*/ { Qrear=s。 Qrear=NULL。}。（3）qrear=qfront五、綜合題1．答：出隊(duì)序列是e2,e4,e3,e6,e5,e1的過(guò)程：⑴ e1入棧（棧底到棧頂元素是e1）⑵ e2入棧（棧底到棧頂元素是e1,e2）⑶ e2出棧（棧底到棧頂元素是e1）⑷ e3入棧（棧底到棧頂元素是e1,e3）⑸ e4入棧（棧底到棧頂元素是e1,e3,e4）⑹ e4出棧（棧底到棧頂元素是e1,e3）⑺ e3出棧（棧底到棧頂元素是e1）⑻ e5入棧（棧底到棧頂元素是e1,e5）⑼ e6入棧（棧底到棧頂元素是e1,e5,e6）⑽ e6出棧（棧底到棧頂元素是e1,e5）⑾ e5出棧（棧底到棧頂元素是e1）⑿ e1出棧（棧底到棧頂元素是空）棧中最多時(shí)有3個(gè)元素，所以棧S的容量至少是3。答：廣義表是線性表的的推廣，它也是n(n0)個(gè)元素a1 ,a2…ai… an的有限序列，其中ai或者是原子或者是一個(gè)廣義表。各操作結(jié)果如下：S 1入棧X 1出棧 輸出序列：1S 2入棧S 3入棧X 3出棧 輸出序列：13S 4入棧 X 4出棧 輸出序列：134X 2出棧 輸出序列：1342 6．有5個(gè)元素，其入棧次序?yàn)椋篈、B、C、D、E，在各種可能的出棧次序中，以元素C、D最先的次序有哪幾個(gè)？答：從題中可知，要使C第一個(gè)且D第二個(gè)出棧，應(yīng)是A入棧，B入棧，C入棧，C出棧，D入棧。由A，B，C組成的數(shù)據(jù)項(xiàng)，除上述五個(gè)不同的組合外，還有一個(gè)C，A，B組合。A入，A出，B入，C入，C出，B出，輸出序列為ACB。3．鏈棧中為何不設(shè)頭結(jié)點(diǎn)？答：因?yàn)殒湕Ｖ辉阪滎^插入和刪除結(jié)點(diǎn)，不可能在鏈表中間插入和刪除結(jié)點(diǎn)，算法實(shí)現(xiàn)很簡(jiǎn)單，所以一般不設(shè)置頭結(jié)點(diǎn)。 14．字符 15．順序存儲(chǔ)方式 鏈?zhǔn)酱鎯?chǔ)方式 16．0 空格字符的個(gè)數(shù) 17．特殊 稀疏 18．（） （（）） 2 19．（（d,e,f）） 20．串長(zhǎng)度相等且對(duì)應(yīng)位置的字符相等 21．i(i1)/2+j 22．行下標(biāo)、列下標(biāo)、非零元素值 三、問(wèn)答題1．簡(jiǎn)述棧和一般線性表的區(qū)別。作業(yè)2答案（本部分作業(yè)覆蓋教材第35章的內(nèi)容）一、單項(xiàng)選擇題1．C 2．B 3．A 4．C 5．B 6．A 7．B 8．C 9．A 10．C 11．B 12．C 13．B 14．B 15．A 16．C 17．B 18．A 19．C 20．D 21．B 22．D 23．C 24．B 25．D 26．A 27．C 28．D 29．D 30．C 31．A 32．D 二、填空題 1．后進(jìn)先出2．下一個(gè)3．增1 增14．假上溢5． 棧是否滿 stop=MAXSIZE1 棧頂指針 棧頂對(duì)應(yīng)的數(shù)組元素 棧是否空 stop=1 棧頂元素 修改棧頂指針6．bceda7．終止條件 遞歸部分8．LUfront==LUrear9．運(yùn)算符 操作數(shù) ab+c/fde/10．snext=h。無(wú)論插入或刪除的位置是地第一個(gè)結(jié)點(diǎn)還是其他結(jié)點(diǎn)，算法步驟都相同。5．解釋帶頭結(jié)點(diǎn)的單鏈表和不帶頭結(jié)點(diǎn)的單鏈表的區(qū)別。缺點(diǎn)：存儲(chǔ)密度小，存儲(chǔ)空間利用率低。優(yōu)點(diǎn)：一般情況下，存儲(chǔ)密度大，存儲(chǔ)空間利用率高。盡管因采用的存儲(chǔ)結(jié)構(gòu)不同，邏輯上相鄰的結(jié)點(diǎn)，其物理地址未必相同，但可通過(guò)結(jié)點(diǎn)的內(nèi)部信息，找到其相鄰的結(jié)點(diǎn)，從而保留了邏輯結(jié)構(gòu)的特點(diǎn)。 14．pnext=head。 12．head
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1