數(shù)據(jù)結(jié)構(gòu)試卷樣卷

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

1、安徽建筑工業(yè)學(xué)院試卷（樣卷）共3頁第1頁總分一二三四五六七八閱卷教師考試課程：算法與數(shù)據(jù)結(jié)構(gòu)班級：學(xué)號：姓名：復(fù)核教師一．單項選擇題（共20題，每題1.5分，共30分）11．在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復(fù)雜度為（A）。2A、O(n)B、O(n/2)C、O(1)D、O(n)1.下面程序段的時間復(fù)雜度為(C)。for(inti=0;ilin

2、k==NULL;a[i][j]=i*j;C、first->link==first;D、first!=NULL;22A、O(m)B、O(n)C、O(m*n)D、O(m+n)13．當(dāng)利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為（B）。2.一個棧的輸入序列為1，2，3，4，下面哪一個序列不可能是這個棧的輸出序列(C)。A、n-2B、n-1C、nD、n+1A、1，3，2，4B、2，3，4，114．m階B樹中的m是指（C）。C、4，3，1，2D、3，4，2，1A、每個結(jié)點至少有m棵子樹B、非終端結(jié)點中關(guān)鍵字的個數(shù)

3、3.采用順序搜索方法查找長度為n的順序表時，搜索成功的平均搜索長度為（D）。C、每個結(jié)點至多有m棵子樹D、m階B樹的深度（或高度）A、nB、n/２C、(n-1)/2D、(n+1)/215．在一棵樹中，（C）沒有前驅(qū)結(jié)點。4.若一棵二叉樹具有10個度為2的結(jié)點，則該二叉樹的度為0的結(jié)點個數(shù)是（B）A、分支結(jié)點B、葉結(jié)點C、樹根結(jié)點D、空結(jié)點A、9B、11C、12D、不確定16．在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為A，并已知A的左孩子5.對矩陣壓縮存儲是為了（B）。的平衡因子為-1，右孩子的平

4、衡因子為0，則應(yīng)作（B）型調(diào)整以使其平衡。A、方便壓縮B、節(jié)省空間C、方便存儲D、提高運算速度A、LLB、LRC、RLD、RR6.在已知待排序文件已基本有序的前提下，效率最高的排序方法是（A）17．對于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為A、直接插入排序B、直接選擇排序C、快速排序D、歸并排序（C）的值除以9。7.在有n個葉子結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為（D）。A、20B、18C、25D、22Ａ、不確定Ｂ、2nＣ、2n+1Ｄ、2n-118．在有向圖中每個頂點的度等于該頂點的

5、（C）。8.廣義表((A,B,E,F,G))的表尾是(B)。A、入度B、出度A、(B,E,F,G)B、()C、（A，B，E，F(xiàn)，G）D、不存在C、入度與出度之和D、入度與出度之差9.折半查找要求查找表中各元素的關(guān)鍵字值必須是（A）排列。19．在基于排序碼比較的排序算法中，（C）算法的最壞情況下的時間復(fù)雜度不高于O(nlog2n)。Ａ、遞增或遞減Ｂ、遞增Ｃ、遞減Ｄ、無序A、起泡排序B、希爾排序C、歸并排序D、快速排序10.在一個單鏈表中，若p所指結(jié)點不是最后一個結(jié)點，在p之后插入t所指結(jié)點，則執(zhí)行（B）20．當(dāng)α的值

6、較小時，散列存儲通常比其他存儲方式具有（B）的查找速度。A、t->next=p；p->next=t；B、t->next=p->next；p->next=t；A、較慢B、較快C、相同C、t->nexr=p->next；p=t；D、p->next=t；t->next=p；注：1.請命題老師用黑色的墨水工整的書寫，作圖準確，以保證試卷字跡清晰。2.請命題老師在試題后面留出答題空間。3.學(xué)生不得在草稿紙上答題安徽建筑工業(yè)學(xué)院考試命題紙（樣卷）卷共3頁第2頁考試課程：算法與數(shù)據(jù)結(jié)構(gòu)班級：學(xué)號：姓名：二、填空題（每空1分，共1

7、0分）四、簡答題（共4題，每題5分，共20分）1．在一棵樹中，葉子結(jié)點沒有后繼結(jié)點。1.有一組關(guān)鍵字{50，52，85，22，96，17，36，55}，請用快速排序，寫出第一趟排序結(jié)果。解：2．在一棵AVL樹（高度平衡的二叉搜索樹）中，每個結(jié)點的左子樹高度與右子樹高度之差的絕對值{36，17，22，50，96，85，52，55}不超過1。3．n(n﹥0)個頂點的無向圖最多有n(n-1)/2條邊，最少有0條邊。4．按策略劃分內(nèi)部排序方法可分為五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。5．n個結(jié)點的二叉樹

8、采用二叉鏈表存放，共有空鏈域個數(shù)為__n+1____。6．已知二維數(shù)組A[20][10]采用行序為主方式存儲,每個元素占2個存儲單元,并且A[10][5]的存儲地址是1000,則A[18][9]的存儲地址是_1168____。2.將關(guān)鍵碼53，78，65，17，87，09，81，45，23依次插入到一棵初始為空的二叉排序樹中，畫出最終的二叉排序樹。7．在各種