大連理工大學(xué)《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)2答卷

1、大工21秋數(shù)據(jù)結(jié)構(gòu)在線作業(yè)2試卷總分:100 得分:100一、單選題 (共 10 道試題,共 50 分)若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn),5個(gè)度為1的結(jié)點(diǎn),則度為0的結(jié)點(diǎn)個(gè)數(shù)是( )。91115不確定答案:B2.具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有( )個(gè)度為2的結(jié)點(diǎn)。891011答案:B3.設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n,則該圖最多有( )條邊。n-1n(n-1)/2n(n+1)/20答案:B4.一個(gè)n個(gè)頂點(diǎn)的連通無向圖,其邊的個(gè)數(shù)至少為( )。n-1nn+1nlogn答案:A5.n個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目( )。n*nn（n1)n2n*（nl）答案:D6.設(shè)有兩個(gè)串p和q,其中q是p的子串,求q在

2、p中首次出現(xiàn)的位置的算法稱為( )。求子串聯(lián)接模式匹配求串長答案:C7.串的長度是指( )。串中所含不同字母的個(gè)數(shù)串中所含字符的個(gè)數(shù)串中所含不同字符的個(gè)數(shù)串中所含非空格字符的個(gè)數(shù)答案:B8.樹的后根遍歷序列等同于該樹對(duì)應(yīng)的二叉樹的( )。先序序列中序序列后序序列以上都不對(duì)答案:B9.在下列存儲(chǔ)形式中,哪一個(gè)不是樹的存儲(chǔ)形式?( )雙親表示法孩子鏈表表示法孩子兄弟表示法順序存儲(chǔ)表示法答案:D10.已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為( )。CBEFDAFEDCBACBEDFA不定答案:A二、判斷題 (共 10 道試題,共 50 分)11.完全二叉樹一定存在度為1的結(jié)點(diǎn)。答案:錯(cuò)誤12.二叉樹的遍歷結(jié)果不是唯一的.答案:正確13.一個(gè)樹的葉結(jié)點(diǎn),在前序遍歷和后序遍歷下,皆以相同的相對(duì)位置出現(xiàn)。答案:正確14.完全二叉樹中,若一個(gè)結(jié)點(diǎn)沒有左孩子,則它必是樹葉。答案:正確15.在n個(gè)結(jié)點(diǎn)的無向圖中,若邊數(shù)大于n-1,則該圖必是連通圖。答案:錯(cuò)誤16.強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)。答案:正確17.用鄰接矩陣法存儲(chǔ)一個(gè)圖所需的存儲(chǔ)單元數(shù)目與圖的邊數(shù)有關(guān)。答案:錯(cuò)誤18.有向圖的鄰接矩陣是對(duì)稱的。答案:錯(cuò)誤19.無向圖的鄰接矩陣一定是對(duì)稱矩陣,有向圖的鄰接矩陣一定是非對(duì)稱矩陣。答案:錯(cuò)誤20.有n