《數據結構》試題（閉卷）（電信系本科2006級2008年1月）班級：____________姓名：______________學號：_____________題號一二三總分題分403030100得分得分得分一、回答下列問題(每題5分，共40分)1．某算法的空間花費s(n)=100n*log2n+0.5*n1.1+2000*n+5000，其空間復雜度是多少？2．冒泡排序在最好情況下時間復雜度是多少？3．對于一個具有n個結點的二叉樹，若采用遞歸中序遍歷，在什么情況下其輔助空間最大，輔助空間大小是多少？在什么情況下其輔助空間最小，輔助空間大小是多少？4．由1000個結點構成的完全二叉樹，層次最大和次最大一層的葉子結點數分別是多少？5．給定25個結點的有序序列，建立二叉排序樹，在等概率查找情況下二叉排序樹其平均查找長度是多少？若采用折半查找方法進行查找，求出在等概率查找情況下其平均查找長度。6．設一模式串為“aabbccsabbccdbcv”，求其NEXT函數，NEXT函數值的大小與模式向右移動的距離有什么關系？7．給定序列(56，67，35，96，72，21，28，48)，給出初始堆。8．如果一個空棧的進棧序列為ABCDEFGHIJ，則出棧序列ABCDGEFHJI是否存在？如果存在，請說明進棧和出棧過程。9．對于一個有n個頂點的有向圖，如果有n(n-1)條邊，則這個圖是完全有向圖嗎？為什么？10．給定6個字符（A，B，C，D，E，F），權值為（5，3，2，9，11，7），畫出Huffman樹。得分二、綜合題（4小題，共32分）得分1．下圖為一個圖的邏輯結構ABＣDEFGH從下列答案中選擇出正確的遍歷結果深度優先搜索=1\*GB3①ABEFCGDH=2\*GB3②ACGBFEDH=3\*GB3③ADGCHBEF廣度優先搜索=1\*GB3①ABDCFEHG=2\*GB3②ACDBHGEF=3\*GB3③ADCBHGEF請畫出鄰接矩陣（10分）2．已知待排序列為（86，53，31，22，16，05，03），用快速排序得到非遞減序列，請完成以下工作：（10分）分別對序列寫出第一、第二趟劃分的結果，第一個元素為樞軸寫出完成整個排序的關鍵字的比較次數如果遞減序列有n個元素，快速排序的時間、空間復雜度是多少？如何改進？3．已知hash函數：H(k)=3kmod11(mod表示取余)，采用下列方法解決沖突：Hi=(H(k)+di)mod11，其中d1=1;di+1=(7di＋3)mod11(i>1)，請對下列線性表（6，8，10，17，20，23，53，41，54，57）構造一個長度為11的hash表，并求此表的平均查找長度ASL。（10分）得分得分三、算法設計題（3題，共30分）1．已知二叉樹有n個結點，以順序存儲結構存放，試用類C語言設計算法計算樹的深度。（10分）2．下面是某同學“樹”這一章的作業，設計算法實現某種功能，其中p是二叉樹的根節點，沒有任何注釋。請分析此算法的功能是什么？該算法是否正確？如不正確，分析不正確的原因，并給出正確算法的基本思路（不需用類c寫出算法）（10分）Booleanabc(Bitreep){ifp==NULLreturn(TRUE);if(p->lchild==NULL)and(p->rchild!=NULL)return(FALSE)elsereturn(abc(p->lchild)andabc(p->rchild)