數(shù)據(jù)結(jié)構(gòu)ii試卷b(孟凡榮)20)

《數(shù)據(jù)結(jié)構(gòu)ii試卷b(孟凡榮)20)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、實(shí)用標(biāo)準(zhǔn)文案東北大學(xué)繼續(xù)教育學(xué)院數(shù)據(jù)結(jié)構(gòu)II試卷（作業(yè)考核線上）B卷學(xué)習(xí)中心：院校學(xué)號(hào)：姓名（共頁）總分題號(hào)一二三四五六七得分一、單選題（每小題2分，共10小題，20分）[A]1．抽象數(shù)據(jù)類型的三個(gè)組成部分分別為A．?dāng)?shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作B．?dāng)?shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)C．?dāng)?shù)據(jù)項(xiàng)、數(shù)據(jù)元素和數(shù)據(jù)類型D．?dāng)?shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型[D]2．下列各式中，按增長(zhǎng)率由小至大的順序正確排列的是A．，n！，2n，n3/2B．n3/2，2n，nlogn，2100C．2n，logn，nlogn，n3/2D．2100，logn,2n,nn[A]3.已知指針p和q分別指向某單鏈表中第一個(gè)結(jié)點(diǎn)和最后一個(gè)

2、結(jié)點(diǎn)。假設(shè)指針s指向另一個(gè)單鏈表中某個(gè)結(jié)點(diǎn)，則在s所指結(jié)點(diǎn)之后插入上述鏈表應(yīng)執(zhí)行的語句為A.q->next=s->next；s->next=p；B.s->next=p；q->next=s->next；C.p->next=s->next；s->next=q；D.s->next=q；p->next=s->next；[C]4．二維數(shù)組A[20][10]采用行優(yōu)先的存儲(chǔ)方法，若每個(gè)元素占2個(gè)存儲(chǔ)單元，且第1個(gè)元素的首地址為200，則元素A[8][9]的存儲(chǔ)地址為A．374B．576C．378D．580[B]5．設(shè)有一個(gè)順序棧的入棧序列是a、b、c，則3個(gè)元素都出棧的可能不同排列個(gè)數(shù)為A．4B．5C

3、.6D.7[D]6.設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1精彩文檔實(shí)用標(biāo)準(zhǔn)文案則T中的葉子數(shù)為A．5B．6C．7D．8[C]7．以下說法不正確的是A．無向圖中的極大連通子圖稱為連通分量B．連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來暫存剛訪問過的頂點(diǎn)C．圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點(diǎn)D．有向圖的遍歷不可采用廣度優(yōu)先搜索[B]8.假設(shè)在構(gòu)建散列表時(shí)，采用線性探測(cè)解決沖突。若連續(xù)插入的n個(gè)關(guān)鍵字都是同義詞，則查找其中最后插入的關(guān)鍵字時(shí)，所需進(jìn)行的比較次數(shù)為A.n-1B.nC.n+lD.n+2[B]9．設(shè)置溢出區(qū)的文件是A．索引非順序文件B．ISAM文

4、件C．VSAM文件D．順序文件[A]10.已知一組關(guān)鍵字為{25,48,36,72,79,82,23,40,16,35}，其中每相鄰兩個(gè)為有序子序列。對(duì)這些子序列進(jìn)行一趟兩兩歸并的結(jié)果是A.{25,36,48,72,23,40,79,82,16,35}B.{25,36,48,72,16,23,40,79,82,35}C.{25,36,48,72,16,23,35,40,79,82}D.{16,23,25,35,36,40,48,72,79,82}二、填空題（每小題1分，共10小題，10分）11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是(log2n)。i=1；WHILE(i

5、*2;12．假設(shè)帶頭結(jié)點(diǎn)的非空單循環(huán)鏈表中僅設(shè)尾指針L，則在第1個(gè)結(jié)點(diǎn)之前插入指針s所指結(jié)點(diǎn)的語句依次是（s->nest=L->next->next；L->next->next=S）。13．無表頭結(jié)點(diǎn)的鏈隊(duì)列Q為空的條件是（Q->real==Q->front=NULL）。14．設(shè)Q[0..N-1]為循環(huán)隊(duì)列，其頭、尾指針分別為P和R，則隊(duì)Q中當(dāng)前所含元素個(gè)數(shù)為（（R-P+N）%N）。15．一棵含999個(gè)結(jié)點(diǎn)的完全二叉樹的深度為（10）。16．在AOV網(wǎng)中，存在環(huán)意味著某項(xiàng)活動(dòng)以自己為先決條件；對(duì)程序的數(shù)據(jù)流圖來說，它表明存在（死循環(huán)）。17.有向圖G可拓?fù)渑判虻呐袆e條件是(不存在環(huán))。18

6、．如果結(jié)點(diǎn)A有3個(gè)兄弟，而且B是A的雙親，則B的度是（4）。19．應(yīng)用回溯與分支限界法解決實(shí)際問題時(shí)，在搜索過程中利用判定函數(shù)，也稱為（.限界函數(shù)）。20.若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是(4231)。三、應(yīng)用題（每小題6分，共5小題，30分）21．比較線性表和棧的基本操作的不同點(diǎn)。精彩文檔實(shí)用標(biāo)準(zhǔn)文案主要區(qū)別是對(duì)插入和刪除操作的限制。如線性表允許在表內(nèi)任一位置進(jìn)行插入和刪除；而隊(duì)列只允許在表尾一端進(jìn)行插入，在表頭一端進(jìn)行刪除；所以也稱隊(duì)列為受限的線性表。表頭為隊(duì)列頭；表尾為隊(duì)列尾。插入　　　　　刪除線性表In

7、sert(L,i,x)　　Delete(L,i)　　　　(1≤i≤n+1)　　(1≤i≤n)隊(duì)列　　Insert(L,n+1,x)　Delete(L,1)22．有一個(gè)二叉樹按層次順序存放在一維數(shù)組中，如下圖所示：試求：（1）該樹的后序遍歷序列。（2）畫出該樹的后序線索樹。1234567891011ACBED（1）后序遍歷序列CEDBA（2）后序線索樹ABEDC23．分析順序查找算法的“監(jiān)視哨”設(shè)置作用為了考慮查找不成功的