蘇州科技數(shù)據(jù)結(jié)構(gòu)早期的樣卷

1、蘇州科技學(xué)院數(shù)據(jù)結(jié)構(gòu)試題A使用專業(yè)計算機04級 考試方式：開卷()閉卷(y)共包頁名姓一線題號111111I111合計得分號-學(xué)一-班封業(yè)專一一密系一-一 單項選擇題(每小題2分，共24分)1在一棵深度為h且具有n個節(jié)點的二叉排序樹中，查找一個元素的最大查找長度(即經(jīng)過比較的結(jié)點數(shù))為。A n B log2nC h/2 D h2循環(huán)隊列中數(shù)組的下標(biāo)范圍是0到n-1 ,頭尾指針分別為front和rear ,則隊列的長度為OA r-f B r-f+1 C (f-r)% n+1 D (r-f+n) %n3在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可將數(shù)據(jù)結(jié)構(gòu)分為 。A動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C線性結(jié)構(gòu)和

2、非線性結(jié)構(gòu)D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)4在一個帶表頭結(jié)點的雙向循環(huán)鏈表中，若要在指針p所指向的節(jié)點之后插入一個q指針?biāo)赶虻墓?jié)點，則需要對 q->right賦值為。A p->left B p->right C p->right->right D p->left->left5快速排序方法在 情況下最不利于發(fā)揮其長處。A要排序的數(shù)據(jù)量太大B要排序的數(shù)據(jù)中含有多個相同的值C要排序的數(shù)據(jù)已基本有序D要排序的數(shù)據(jù)個數(shù)為奇數(shù)6在一個非空二叉樹的中序序列中，根結(jié)點的左邊。A只有右子樹上的所有節(jié)點B只有右子樹上的部分節(jié)點C只有左子樹上的所有節(jié)點D只有左子樹上的部分節(jié)點7若在中

3、序線索二叉樹中某一個結(jié)點存在右孩子，則該結(jié)點的后繼是 。A 不存在B其右子樹中最左側(cè)的結(jié)點C其左子樹中最右側(cè)的結(jié)點D其右孩子8以下關(guān)于圖的敘述中，正確的是 。A用鄰接矩陣存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點的個數(shù)有關(guān)，而與邊數(shù)無關(guān)B用鄰接矩陣存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點的個數(shù)無關(guān)C用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點的個數(shù)有關(guān)，而與邊數(shù)無關(guān)D用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點的個數(shù)無關(guān)9將一個n行n列的對稱矩陣采用下三角壓縮存儲方法存儲在下標(biāo)為0.k的一維數(shù)組b中，則k的值最少為。A n B 2n C n(n+1)/2 D n(n+1)

4、/2-1第 1 頁10對于具有e條邊的無向圖，它的鄰接表中含有 個邊結(jié)點。A e B 2e C e+2 D e/211下列關(guān)鍵字序列中， 是堆。A 16, 72, 31,23, 94, 53B 94, 23, 31,72, 16, 53C 16, 53, 23, 94, 31,72D 16, 23, 53, 31,94, 7212在具有n個單元的順序棧中，假定以地址頂端（即下標(biāo)為 n-1的單元）作為棧底，以top作為棧 頂指針，則當(dāng)作入棧處理時，top變化為。A top 不變 B top=0 C top- D top+二判斷題（正確的請在題后的括號中寫，否則請在題后的括號中寫X,共 8分）1線

5、性表在任何情況下均可以進行二分查找。（）2設(shè)哈希表長 m=14哈希函數(shù) H（key尸key MOD 11，假設(shè)表中已有 4個結(jié)點15, 38, 61, 84,如 果采用線性探測再散列解決沖突，關(guān)鍵字為49的結(jié)點的地址為9。（）3如果二叉樹中某結(jié)點的度為1,則說明該結(jié)點只有一棵子樹。（）4任何一個二叉樹的葉子結(jié)點在其先序序列、中序序列和后序序列中的次序是不變的。（）5已知一個有向圖的鄰接表表示，計算第 i個結(jié)點的出度必須遍歷整個鄰接表。（）6如果一個串r中的字符全部包含在另一個串s中則說明r是s的一個子串。（）7對一個堆，無論按二叉樹的層次遍歷還是先序遍歷，都不一定能得到有序序列。（）8無論是鏈

6、隊列還是循環(huán)隊列，作入隊運算操作時都必須判定隊列是否滿。（）三解答下列各題：（公辦學(xué)生作1,2,3, 5,7,8 題41分，民辦學(xué)生做1,2,4,5,6,9,10 題48分）1設(shè)有6個元素A,B,C,D,E,F依次入棧，允許任何時候出棧，能否得到下列的每一個出棧序列？如能，給出出棧操作的過程，若不能，簡述其理由。（6分）（1） CDBEFA （2） ABEDFC （3） DCEABF2對長度為10的順序存儲的線性表， 此表應(yīng)滿足什么條件才能進行折半查找？畫出進行折半查找的判定樹，并求其在等概率的條件下查找成功時的平均查找長度。（7分）第7頁3設(shè)一個工程有11項活動，9個事件，事件V1表示整個工

7、程開始，事件V9表示整個工程結(jié)束。（1）求出每個事件的最早和最晚發(fā)生時間？ （2）完成整項工程至少需要多少時間？ 哪些活動是影響工程進度的關(guān)鍵？ （10分）4寫出下圖的鄰接矩陣，并分別寫出對下圖從頂點B始進行深度優(yōu)先和廣度優(yōu)先遍歷的一個結(jié)果，并畫出其對應(yīng)的深度優(yōu)先和廣度優(yōu)先生成樹。（10分）5 已知一組元素為46, 74, 16, 53, 14, 26, 40, 86試寫出:(1)將其調(diào)整為小頂堆的過程。(2)快速排序一趟的過程和結(jié)果。(6分)6說明下列算法的功能。(5分)Void insert(Linklist &L,ElemType x, ElemType y) s=new Lno

8、de;s->data=y;P=L;while(p->next&&p->next.data!=x)p=p->next; s->next=p->next; p->next=s;7說明下列算法的功能。(5分)Status A (Linklist L ) / L不含表頭結(jié)點 if(L&&L->next )Q=L;L=L->next;p=L;While(p->next) p=p->next;P->next=q; q->next=NULL;(7分)8試將樹轉(zhuǎn)換為相應(yīng)的二叉樹，再畫出其對應(yīng)的中序線索二叉樹。（7分）9試將樹轉(zhuǎn)換為相應(yīng)的二叉樹，并寫出二叉樹后序遍歷的結(jié)果。DCBEHAG底畫出該二叉樹,B的思想方法。10已知二叉樹的前序遍歷序列為DACEBHFG中序遍歷序列為并簡述由任意二叉樹的前序遍歷序列和中序遍歷序列求二叉樹四 算法設(shè)計（公辦學(xué)生做1,2,3題27分，民辦學(xué)生做1,3題，20分）1假設(shè)以帶頭