數(shù)據(jù)結(jié)構(gòu)模擬題2010年7月 一、單選題 （每空2分，共10分）1、隊(duì)列的刪除操作是在（ ）進(jìn)行。A隊(duì)首 B隊(duì)尾 C隊(duì)前 D對(duì)后2、當(dāng)利用大小為N 的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top = = N表示棧空，則退棧時(shí)，用（ ）語(yǔ)句修改top指針。Atop+; Btop=0; Ctop-; Dtop=N;3、由權(quán)值分別為3,6,7,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為（ ）。A51 B23 C53 D744、在一棵二叉樹中，第4層上的結(jié)點(diǎn)數(shù)最多為（ ）。A31 B8 C.15 D165、 向堆中插入一個(gè)元素的時(shí)間復(fù)雜度為（ ）。AO(log2n) BO(n) CO(1) D O(nlog2n) 二、填空題（每空1分，共20分）1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_、_、_和_四種。2、若對(duì)一棵二叉樹的結(jié)點(diǎn)編號(hào)從1開始順序編碼，按順序存儲(chǔ)，把編號(hào)為1的結(jié)點(diǎn)存儲(chǔ)到a1中，其余類推，則ai元素的左孩子元素為_，右孩子元素為_，雙親元素(i>0)為_。3、從一個(gè)棧刪除元素時(shí)，首先取出 ，然后再前移一位 。4、后綴表達(dá)式“2 10 + 5 * 6 9 /”的值為 。5、假定一棵樹的廣義表表示為A(B(C(D,E),F,G(H,I,J),K)，則度為3、2、1、0的結(jié)點(diǎn)數(shù)分別為_、_、_和_個(gè)。6、在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有_條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有_條邊。 7、在索引表中，若一個(gè)索引項(xiàng)對(duì)應(yīng)主表中的一條記錄，則稱此索引為_索引，若對(duì)應(yīng)主表中的若干條記錄，則稱此索引為_索引。8、對(duì)于二分查找所對(duì)應(yīng)的判定樹，它既是一棵_ _，又是一棵_ _ _。三、運(yùn)算題（每小題5分，共10分）1、 1、 空堆開始依次向堆中插入線性表（64,52, 12,48,45,26）中的每個(gè)元素，請(qǐng)以線性表的形式給出每插入一個(gè)元素后堆的狀態(tài)。（為小根堆）  2、在一份電文中共使用五種字符：A，G，F(xiàn)，U，Y，Z，它們的出現(xiàn)頻率依次為12,9,18,7,14，11，求出每個(gè)字符的哈夫曼編碼。 四、閱讀算法，回答問(wèn)題（每小題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;對(duì)于結(jié)點(diǎn)類型為L(zhǎng)Node的單鏈表，以上算法的功能為：  2、void BB(List &L)int i=0;while (i<L.size)int j=i+1;while (j<L.size)if(L.listj = =L.listi)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);調(diào)用該算法后，生成的二叉搜索數(shù)的中序序列為：  4、void DD ( )ElemType A =1,3,5,7,9,2,4,6,8,10,B10;TwoMerge(A, B,0,4,9);for ( int i=0; i<10; i+)cout<<Bi<<” “;cout<<endl;   調(diào)用該算法后，輸出結(jié)果為： 五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(10分)。利用單鏈表進(jìn)行數(shù)據(jù)排序。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;while ( )ai+=p->data; ClearList (head);  六、編寫算法(10分)編寫一個(gè)非遞歸算法，在稀疏有序索引表中二分查找出給定值K所對(duì)應(yīng)的索引項(xiàng)，即索引值剛好大于等于K的索引項(xiàng)，返回該索引項(xiàng)的start域的值，若查找失敗則返回-1。數(shù)據(jù)結(jié)構(gòu)模擬題答案及評(píng)分標(biāo)準(zhǔn)（供參考）一、單選題 （每空2分，共10分）1、A 2、 A 3、A 4、 B 5 、A 二、填空題（每空1分，共20分）1、順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)2、2i+1、2i+2、 3、棧頂元素、棧頂指針 4、6 5、2、2、0、76、n(n-1)/2 、n(n-1) 7、稠密、稀疏 8、二叉搜索樹、理想平衡樹三、運(yùn)算題（每小題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 相反） 四、閱讀算法，回答問(wèn)題（每小題5分，共20分）1、向單鏈表的末尾添加一個(gè)元素。2、刪除線性表中所有重復(fù)的元素。3、23 25 35 45 77 784、 1 2 3 4 5 6 7 8 9 10五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(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 )return Bmid.start;else if (K<Bmid.index)high=mid-1;elselow=mid+1;if (low<m) return Blow.start;else return 1;    4 / 4