《數據結構》模擬題

1、數據結構模擬題2002年7月 一、單選題 （每空2分，共10分）1、隊列的刪除操作是在（ ）進行。A隊首 B隊尾 C隊前 D對后2、當利用大小為N 的數組順序存儲一個棧時，假定用top = = N表示?？?，則退棧時，用（ ）語句修改top指針。Atop+; Btop=0; Ctop-; Dtop=N;3、由權值分別為3,6,7,2,5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（ ）。A51 B23 C53 D744、在一棵二叉樹中，第4層上的結點數最多為（ ）。A31 B8 C.15 D165、 向堆中插入一個元素的時間復雜度為（ ）。AO(log2n) BO(n) CO(1)

2、D O(nlog2n) 二、填空題（每空1分，共20分）1、數據的邏輯結構被分為_、_、_和_四種。2、若對一棵二叉樹的結點編號從1開始順序編碼，按順序存儲，把編號為1的結點存儲到a1中，其余類推，則ai元素的左孩子元素為_，右孩子元素為_，雙親元素(i>0)為_。3、從一個棧刪除元素時，首先取出 ，然后再前移一位 。4、后綴表達式“2 10 + 5 * 6 9 /”的值為 。5、假定一棵樹的廣義表表示為A(B(C(D,E),F,G(H,I,J),K)，則度為3、2、1、0的結點數分別為_、_、_和_個。6、在一個具有n個頂點的無向完全圖中，包含有_條邊，在一個具有n個頂點的有

3、向完全圖中，包含有_條邊。 7、在索引表中，若一個索引項對應主表中的一條記錄，則稱此索引為_索引，若對應主表中的若干條記錄，則稱此索引為_索引。8、對于二分查找所對應的判定樹，它既是一棵_ _，又是一棵_ _ _。三、運算題（每小題5分，共10分）1、 1、 空堆開始依次向堆中插入線性表（64,52, 12,48,45,26）中的每個元素，請以線性表的形式給出每插入一個元素后堆的狀態(tài)。（為小根堆）  2、在一份電文中共使用五種字符：A，G，F，U，Y，Z，它們的出現頻率依次為12,9,18,7,14，11，求出每個字符的哈夫曼編碼。 四、閱讀算法，回答問題（每小題

4、5分，共20分）1、void AA (LNode * HL,const ElemType & item) LNode * newptr=new Lnode ; newptr->data=item; LNode *p=HL; while ( p->next!=HL ) p=p->next;newptr->next=HL;p->next=newptr;對于結點類型為LNode的單鏈表，以上算法的功能為：  2、void BB(List &L)int i=0;while (i<L.size)int j=i+1;while (j&

5、lt;L.size)i)for (int k=j+1;k<L.size;k+)L.listk-1=L.listk;L.size-;else j+;i+;以上算法的功能為： 3、void CC(BTreeNode * & BST )ElemType a6 =45，23，78，35，77，25；BST=NULL；for( int i=0,i<6;i+)Insert(BST , ai);調用該算法后，生成的二叉搜索數的中序序列為：  4、void DD ( )ElemType A =1,3,5,7,9,2,4,6,8,10,B10;TwoMerge(

6、A, B,0,4,9);for ( int i=0; i<10; i+)cout<<Bi<<” “;cout<<endl;   調用該算法后，輸出結果為： 五、算法填空，在畫有橫線的地方填寫合適的內容(10分)。利用單鏈表進行數據排序。void LinkSort (ElemType a ,int n)LNode * head=new LNode;InitList (head);int i;for (i=0;i<n;i+)Insert(head, ai);LNode * p=head->next;i=0;whil

7、e ( )ai+=p->data; ClearList (head);  六、編寫算法(10分)編寫一個非遞歸算法，在稀疏有序索引表中二分查找出給定值K所對應的索引項，即索引值剛好大于等于K的索引項，返回該索引項的start域的值，若查找失敗則返回-1。數據結構模擬題答案及評分標準（供參考）一、單選題 （每空2分，共10分）1、A 2、 A 3、A 4、 B 5 、A 二、填空題（每空1分，共20分）1、順序結構、鏈接結構、索引結構、散列結構2、2i+1、2i+2、 3、棧頂元素、棧頂指針 4、6 5、2、2、0、76、n(n-1)/2 、n(n-1) 7、稠密、稀疏 8、二叉

8、搜索樹、理想平衡樹三、運算題（每小題5分，共10分）1、（64）（52，64）（12，64，52）（12，48，52，64）（12，45，52，64，48）（12，45，26，64，48，52）2、 A：111 G：011 F：10U：010 Y：00 Z：110（或0、1 相反） 四、閱讀算法，回答問題（每小題5分，共20分）1、向單鏈表的末尾添加一個元素。2、刪除線性表中所有重復的元素。3、23 25 35 45 77 784、 1 2 3 4 5 6 7 8 9 10五、算法填空，在畫有橫線的地方填寫合適的內容(10分)。p!=NULLp=p->next;delete head;六、編寫算法(10分)int Binsch(IndexList B, int m, IndexKeyType K)int low=0, high=m-1;while (low<= high)int mid=(low+high)/2;if (K= =Bmid. index