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

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

1、東北大學繼續(xù)教育學院數(shù)據(jù)結(jié)構(gòu)II試卷（作業(yè)考核線上）B卷學習中心：院校學號：姓名（共頁）總分題號一二三四五六七得分一、單選題（每小題2分，共10小題，20分）[A]1．抽象數(shù)據(jù)類型的三個組成部分分別為A．數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作B．數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)C．數(shù)據(jù)項、數(shù)據(jù)元素和數(shù)據(jù)類型D．數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型[D]2．下列各式中，按增長率由小至大的順序正確排列的是A．，n！，2n，n3/2B．n3/2，2n，nlogn，2100C．2n，logn，nlogn，n3/2D．2100

2、，logn,2n,nn[A]3.已知指針p和q分別指向某單鏈表中第一個結(jié)點和最后一個結(jié)點。假設(shè)指針s指向另一個單鏈表中某個結(jié)點，則在s所指結(jié)點之后插入上述鏈表應(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)先的存儲方法，若每個元素占2個存儲單元，且第1個元素的首地址

3、為200，則元素A[8][9]的存儲地址為A．374B．576C．378D．580[B]5．設(shè)有一個順序棧的入棧序列是a、b、c，則3個元素都出棧的可能不同排列個數(shù)為A．4B．5C.6D.710課程名稱:數(shù)據(jù)結(jié)構(gòu)II[D]6.設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1則T中的葉子數(shù)為A．5B．6C．7D．8[C]7．以下說法不正確的是A．無向圖中的極大連通子圖稱為連通分量B．連通圖的廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點C．圖的深度優(yōu)先搜索中一般要采用棧來暫存

4、剛訪問過的頂點D．有向圖的遍歷不可采用廣度優(yōu)先搜索[B]8.假設(shè)在構(gòu)建散列表時，采用線性探測解決沖突。若連續(xù)插入的n個關(guān)鍵字都是同義詞，則查找其中最后插入的關(guān)鍵字時，所需進行的比較次數(shù)為A.n-1B.nC.n+lD.n+2[B]9．設(shè)置溢出區(qū)的文件是A．索引非順序文件B．ISAM文件C．VSAM文件D．順序文件[A]10.已知一組關(guān)鍵字為{25,48,36,72,79,82,23,40,16,35}，其中每相鄰兩個為有序子序列。對這些子序列進行一趟兩兩歸并的結(jié)果是A.{25,36,48,72,2

5、3,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ù)量級是(log2n)。i=1；WHILE(inest=

6、L->next->next；L->next->next=S）。13．無表頭結(jié)點的鏈隊列Q為空的條件是（Q->real==Q->front=NULL）。14．設(shè)Q[0..N-1]為循環(huán)隊列，其頭、尾指針分別為P和R，則隊Q中當前所含元素個數(shù)為（（R-P+N）%N）。15．一棵含999個結(jié)點的完全二叉樹的深度為（10）。16．在AOV網(wǎng)中，存在環(huán)意味著某項活動以自己為先決條件；對程序的數(shù)據(jù)流圖來說，它表明存在（死循環(huán)）。17.有向圖G可拓撲排序的判別條件是(不存在環(huán))。18．如果結(jié)點A有3個兄弟，而

7、且B是A的雙親，則B的度是（4）。19．應(yīng)用回溯與分支限界法解決實際問題時，在搜索過程中利用判定函數(shù)，也稱為（.限界函數(shù)）。10課程名稱:數(shù)據(jù)結(jié)構(gòu)II20.若以1234作為雙端隊列的輸入序列，則既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列是(4231)。三、應(yīng)用題（每小題6分，共5小題，30分）21．比較線性表和棧的基本操作的不同點。主要區(qū)別是對插入和刪除操作的限制。如線性表允許在表內(nèi)任一位置進行插入和刪除；而隊列只允許在表尾一端進行插入，在表頭一端進行刪除；所以也稱

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