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

1、蘇州科技學(xué)院數(shù)據(jù)結(jié)構(gòu)試題A使用專業(yè)計(jì)算機(jī)04級(jí) 考試方式：開卷()閉卷(y)共包頁名姓一線題號(hào)111111I111合計(jì)得分號(hào)-學(xué)一-班封業(yè)專一一密系一-一 單項(xiàng)選擇題(每小題2分，共24分)1在一棵深度為h且具有n個(gè)節(jié)點(diǎn)的二叉排序樹中，查找一個(gè)元素的最大查找長度(即經(jīng)過比較的結(jié)點(diǎn)數(shù))為。A n B log2nC h/2 D h2循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是0到n-1 ,頭尾指針分別為front和rear ,則隊(duì)列的長度為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動(dòng)態(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在一個(gè)帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表中，若要在指針p所指向的節(jié)點(diǎn)之后插入一個(gè)q指針?biāo)赶虻墓?jié)點(diǎn)，則需要對(duì) q->right賦值為。A p->left B p->right C p->right->right D p->left->left5快速排序方法在 情況下最不利于發(fā)揮其長處。A要排序的數(shù)據(jù)量太大B要排序的數(shù)據(jù)中含有多個(gè)相同的值C要排序的數(shù)據(jù)已基本有序D要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)6在一個(gè)非空二叉樹的中序序列中，根結(jié)點(diǎn)的左邊。A只有右子樹上的所有節(jié)點(diǎn)B只有右子樹上的部分節(jié)點(diǎn)C只有左子樹上的所有節(jié)點(diǎn)D只有左子樹上的部分節(jié)點(diǎn)7若在中

3、序線索二叉樹中某一個(gè)結(jié)點(diǎn)存在右孩子，則該結(jié)點(diǎn)的后繼是 。A 不存在B其右子樹中最左側(cè)的結(jié)點(diǎn)C其左子樹中最右側(cè)的結(jié)點(diǎn)D其右孩子8以下關(guān)于圖的敘述中，正確的是 。A用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)的個(gè)數(shù)有關(guān)，而與邊數(shù)無關(guān)B用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)的個(gè)數(shù)無關(guān)C用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)的個(gè)數(shù)有關(guān)，而與邊數(shù)無關(guān)D用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)的個(gè)數(shù)無關(guān)9將一個(gè)n行n列的對(duì)稱矩陣采用下三角壓縮存儲(chǔ)方法存儲(chǔ)在下標(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對(duì)于具有e條邊的無向圖，它的鄰接表中含有 個(gè)邊結(jié)點(diǎn)。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個(gè)單元的順序棧中，假定以地址頂端（即下標(biāo)為 n-1的單元）作為棧底，以top作為棧 頂指針，則當(dāng)作入棧處理時(shí)，top變化為。A top 不變 B top=0 C top- D top+二判斷題（正確的請?jiān)陬}后的括號(hào)中寫，否則請?jiān)陬}后的括號(hào)中寫X,共 8分）1線

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

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

7、程開始，事件V9表示整個(gè)工程結(jié)束。（1）求出每個(gè)事件的最早和最晚發(fā)生時(shí)間？ （2）完成整項(xiàng)工程至少需要多少時(shí)間？ 哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？ （10分）4寫出下圖的鄰接矩陣，并分別寫出對(duì)下圖從頂點(diǎn)B始進(jìn)行深度優(yōu)先和廣度優(yōu)先遍歷的一個(gè)結(jié)果，并畫出其對(duì)應(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é)點(diǎn) 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)的二叉樹，再畫出其對(duì)應(yīng)的中序線索二叉樹。（7分）9試將樹轉(zhuǎn)換為相應(yīng)的二叉樹，并寫出二叉樹后序遍歷的結(jié)果。DCBEHAG底畫出該二叉樹,B的思想方法。10已知二叉樹的前序遍歷序列為DACEBHFG中序遍歷序列為并簡述由任意二叉樹的前序遍歷序列和中序遍歷序列求二叉樹四 算法設(shè)計(jì)（公辦學(xué)生做1,2,3題27分，民辦學(xué)生做1,3題，20分）1假設(shè)以帶頭