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

2、線性結構和非線性結構 D 內部結構和外部結構4在一個帶表頭結點的雙向循環鏈表中，若要在指針p所指向的節點之后插入一個q指針所指向的節點，則需要對q->right賦值為_。A p->left B p->right C p->right->right D p->left->left5 快速排序方法在_情況下最不利于發揮其長處。A 要排序的數據量太大 B 要排序的數據中含有多個相同的值C 要排序的數據已基本有序 D 要排序的數據個數為奇數6在一個非空二叉樹的中序序列中，根結點的左邊_。A 只有右子樹上的所有節點 B只有右子樹上的部分節點C 只有左子樹上的所有

3、節點 D只有左子樹上的部分節點7若在中序線索二叉樹中某一個結點存在右孩子，則該結點的后繼是_。 A 不存在 B 其右子樹中最左側的結點 C其左子樹中最右側的結點 D 其右孩子8以下關于圖的敘述中，正確的是_。 A 用鄰接矩陣存儲圖，占用的存儲空間數只與圖中結點的個數有關，而與邊數無關B 用鄰接矩陣存儲圖，占用的存儲空間數只與圖中邊數有關，而與結點的個數無關C 用鄰接表法存儲圖，占用的存儲空間數只與圖中結點的個數有關，而與邊數無關D 用鄰接表法存儲圖，占用的存儲空間數只與圖中邊數有關，而與結點的個數無關9將一個n行n列的對稱矩陣采用下三角壓縮存儲方法存儲在下標為0.k的一維數組b中，則k的值最少

4、為_。 A n B 2n C n(n+1)/2 D n(n+1)/2-110 對于具有e條邊的無向圖，它的鄰接表中含有_個邊結點。 A e B 2e C e+2 D e/2 11下列關鍵字序列中，_是堆。 16, 72, 31, 23, 94, 53 94, 23, 31, 72, 16, 53 16, 53, 23, 94，31, 72 16, 23, 53, 31, 94, 7212在具有n個單元的順序棧中，假定以地址頂端（即下標為n-1的單元）作為棧底，以top作為棧頂指針，則當作入棧處理時，top變化為_。A top不變 B top=0 C top- D top+ 二 判斷題（正確的請

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

6、對一個堆，無論按二叉樹的層次遍歷還是先序遍歷，都不一定能得到有序序列。（ ）8 無論是鏈隊列還是循環隊列，作入隊運算操作時都必須判定隊列是否滿。（ ）三 解答下列各題：(公辦學生作1,2,3, 5,7,8題41分, 民辦學生做1,2,4,5,6,9,10題48分)1 設有6個元素A,B,C,D,E,F依次入棧，允許任何時候出棧，能否得到下列的每一個出棧序列？如能，給出出棧操作的過程，若不能，簡述其理由。（6分）(1) CDBEFA (2) ABEDFC (3) DCEABF 2 對長度為10 的順序存儲的線性表，此表應滿足什么條件才能進行折半查找？畫出進行折半查找的判定樹，并求其在等概率的條件

7、下查找成功時的平均查找長度。（7分）密封線3 設一個工程有11項活動，9個事件,事件 V1表示整個工程開始,事件V9表示整個工程結束。(1)求出每個事件的最早和最晚發生時間？（2）完成整項工程至少需要多少時間？ (3)哪些活動是影響工程進度的關鍵？（10分）4 寫出下圖的鄰接矩陣，并分別寫出對下圖從頂點B始進行深度優先和廣度優先遍歷的一個結果，并畫出其對應的深度優先和廣度優先生成樹。（10分）ABCGED4 對數據表44，25，88，12，75，84，-6，60，寫出： (1) 快速排序第一趟的過程和結果。(2) 間隔為3時第一趟希爾排序的結果。(3) 調整為小頂堆的過程。（7分）5已知一組元

8、素為46，74，16，53，14，26，40， 86試寫出： （1）將其調整為小頂堆的過程。 （2）快速排序一趟的過程和結果。（6分）6 說明下列算法的功能。（5分）Void insert(Linklist &L,ElemType x, ElemType y) s=new Lnode; 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）

9、/ L不含表頭結點 if(L&&L->next ) Q=L;L=L->next;p=L;While(p->next) p=p->next;P->next=q; q->next=NULL;8 試將樹轉換為相應的二叉樹，再畫出其對應的中序線索二叉樹。（7分）ABCHGFEID 密封線9 試將樹轉換為相應的二叉樹，并寫出二叉樹后序遍歷的結果。（7分）ABCHGFEID 10 已知二叉樹的前序遍歷序列為DACEBHFGI，中序遍歷序列為DCBEHAGIF試畫出該二叉樹，并簡述由任意二叉樹的前序遍歷序列和中序遍歷序列求二叉樹B的思想方法。 四 算法設計（公辦學生做1,2,3題27分, 民辦學生做1,3題