數(shù)據(jù)結構ii試卷b孟凡榮

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

2、n！，2n，n32Bn32，2n，nlogn，2100nC2n，logn，nlogn，n32D2100，logn2nnn[A]3.已知指針p和q分別指向某單鏈表中第一個結點和最后一個結點。假設指針s指向另一個單鏈表中某個結點，則在s所指結點之后插入上述鏈表應執(zhí)行的語句為A.qnext=snext；snext=p；B.snext=p；qnext=snext；C.pnext=snext；snext=q；D.snext=q；pnext=sne

3、xt；[C]4二維數(shù)組A[20][10]采用行優(yōu)先的存儲方法，若每個元素占2個存儲單元，且第1個元素的首地址為200，則元素A[8][9]的存儲地址為A374B576C378D580[B]5設有一個順序棧的入棧序列是a、b、c，則3個元素都出棧的可能不同排列個數(shù)為A4B5C.6D.7課程名稱:數(shù)據(jù)結構II320.若以1234作為雙端隊列的輸入序列，則既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列是(4231)。

4、三、應用題（每小題三、應用題（每小題6分，共分，共5小題，小題，3030分）分）21比較線性表和棧的基本操作的不同點。主要區(qū)別是對插入和刪除操作的限制。如線性表允許在表內任一位置進行插入和刪除；而隊列只允許在表尾一端進行插入，在表頭一端進行刪除；所以也稱隊列為受限的線性表。表頭為隊列頭；表尾為隊列尾。插入刪除線性表(Lix)(Li)(1≤i≤n1)(1≤i≤n)隊列(Ln1x)(L1)22有一個二叉樹按層次順序存放在一維數(shù)組中，如下圖所

5、示：試求：（1）該樹的后序遍歷序列。（2）畫出該樹的后序線索樹。1234567891011（1）后序遍歷序列CEDBA（2）后序線索樹ABEDC23分析順序查找算法的“監(jiān)視哨”設置作用為了考慮查找不成功的情況在每次進行關鍵字的比較前，首先要判斷循環(huán)變量i是否數(shù)組越界，這對算法來說是必要的。如果每步省略數(shù)組下標是否越界的判斷，則可以大大提高算法運行的效率。為此，可以利用預留的0號單元，作為所設的“監(jiān)視哨”控制循環(huán)變量i的出界。假設數(shù)據(jù)從后