數(shù)據(jù)結(jié)構(gòu)網(wǎng)上教學(xué)活動(dòng)文本(2006511)

1、數(shù)據(jù)結(jié)構(gòu)網(wǎng)上教學(xué)活動(dòng)文本（2006.5.11）徐孝凱：歡迎大家積極參加計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程網(wǎng)絡(luò)答疑活動(dòng) 賀桂英：徐老師，能否請您將剛考過的試題(06年1月已考)上傳給我們，供學(xué)習(xí)和復(fù)習(xí)參考! 謝謝您! 徐孝凱：上學(xué)期試卷供參考！ 中央廣播電視大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)數(shù)據(jù)結(jié)構(gòu)試題（6）2004年9月題 號一二三四五六總 分得 分 一、單項(xiàng)選擇題，在括號內(nèi)填寫所選擇的標(biāo)號（9小題，每小題2分，共18分） 1. 一種抽象數(shù)據(jù)類型包括數(shù)據(jù)和( )兩個(gè)部分。 A. 數(shù)據(jù)類型 B. 操作 C. 數(shù)據(jù)抽象 D. 類型說明 2. 在一個(gè)長度為n的順序表的表尾插入一個(gè)新元素的時(shí)間復(fù)雜度為（ ）。 A

2、. O(1) B. O(n) C. O(n2) D. O(log2n) 3. 已知L是帶表頭附加結(jié)點(diǎn)的單鏈表, 刪除第一個(gè)結(jié)點(diǎn)的語句是（ ）。 A. L = L->link; B. L->link = L->link->link; C. L = L; D. L->link = L; 4. 下列廣義表中的線性表是（ ）。 AE(a,(b,c)BE(a,E)CE(a,b)DE(a,( ) 5. 在一棵樹的左子女-右兄弟表示法中，一個(gè)結(jié)點(diǎn)的右子女是該結(jié)點(diǎn)的( )結(jié)點(diǎn)。 A. 兄弟 B. 父子 C. 祖先 D. 子孫 6. 向一棵AVL樹插入元素時(shí)，可能引起對最小不平衡子

3、樹的雙向旋轉(zhuǎn)的調(diào)整過程，此時(shí)需要修改相關(guān)( )個(gè)指針域的值。 A. 2 B. 3 C. 4 D. 5 7. 在一個(gè)有向圖的鄰接矩陣表示中，刪除一條邊<vi,vj>需要的時(shí)間復(fù)雜度為 ( )。 AO(1) BO(i) CO(j) DO(i+j) 8. 在一棵高度為h的B樹中，插入一個(gè)新關(guān)鍵碼時(shí)，為搜索插入位置需讀?。?）個(gè)結(jié)點(diǎn)。 A. h-1 B. h C. h+1 D. h+2 9. 對存儲(chǔ)有n個(gè)元素的長度為m的散列表進(jìn)行搜索，平均搜索長度與（ ）有關(guān)。 A. n B. m C. n/m D. n*m 二、填空題，在橫線處填寫合適內(nèi)容（12小題，每小題1分，共12分） 1. 抽象數(shù)

4、據(jù)類型的特點(diǎn)是_、信息隱蔽、使用與實(shí)現(xiàn)分離。 2. 利用三元組表存放稀疏矩陣中的非零元素，則在三元組表中每個(gè)三元組元素對應(yīng)一個(gè)非零元素的行號、列號和_。 3. 在單鏈表中邏輯上相鄰的結(jié)點(diǎn)而在物理位置上_相鄰。 4. 向一個(gè)鏈?zhǔn)綏２迦胍粋€(gè)新結(jié)點(diǎn)時(shí)，首先把棧頂指針的值賦給新結(jié)點(diǎn)的指針域，然后把新結(jié)點(diǎn)的存儲(chǔ)位置賦給_。 5. 迷宮問題是一個(gè)回溯控制的問題，最好使用_的方法來解決。 6. 在一棵高度為3的四叉樹中，最多含有_個(gè)結(jié)點(diǎn)，假定樹根結(jié)點(diǎn)的高度為0。 7. 在一個(gè)堆的順序存儲(chǔ)中，若一個(gè)元素的下標(biāo)為i(0in-1)，則它的右子女元素的下標(biāo)為_。 8. 根據(jù)一組記錄(56,42,73,50,48,2

5、2)依次插入結(jié)點(diǎn)生成一棵AVL樹時(shí)，當(dāng)插入到值為_的結(jié)點(diǎn)時(shí)才出現(xiàn)不平衡，需要進(jìn)行旋轉(zhuǎn)調(diào)整。 9. 在使用Kruskal算法構(gòu)造連通網(wǎng)絡(luò)的最小生成樹時(shí)，只有當(dāng)一條候選邊的兩個(gè)端點(diǎn)不在同一個(gè)_ 上，才會(huì)被加入到生成樹中。 10. 在堆排序中，對n個(gè)記錄建立初始堆需要調(diào)用_次調(diào)整算法。 11. 在對n個(gè)數(shù)據(jù)對象的二路歸并排序中，每趟歸并的時(shí)間復(fù)雜度為_。 12. 在一棵m階B樹上，每個(gè)非根結(jié)點(diǎn)的關(guān)鍵碼數(shù)最少為_個(gè)。 三、判斷題，在每小題前面打?qū)μ柋硎菊_或打叉號表示錯(cuò)誤（10小題，每小題1分，共10分） 1. 多維數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的。 2. 若每次從

6、隊(duì)列中取出的是具有最高優(yōu)先權(quán)的元素, 則稱這種隊(duì)列為優(yōu)先級隊(duì)列。 3. 遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常不需要用遞歸的算法來實(shí)現(xiàn)對它的操作。 4. 當(dāng)從一個(gè)最小堆中刪除一個(gè)元素時(shí)，需要把堆尾元素填補(bǔ)到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。 5. 對于一棵具有n個(gè)結(jié)點(diǎn)，其高度為h的二叉樹，進(jìn)行任一種次序遍歷的時(shí)間復(fù)雜度為O(n)。 6. 對于同一組記錄，生成二叉搜索樹的形態(tài)與插入記錄的次序無關(guān)。 7. 在每個(gè)AOE網(wǎng)絡(luò)中只有一條關(guān)鍵路徑。 8. 圖的深度優(yōu)先搜索是一種典型的回溯搜索的例子，可以通過遞歸算法求解。 9. 裝載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的裝滿程度。 1

7、0. 在一棵B樹中，所有葉結(jié)點(diǎn)都處在同一層上，所有葉結(jié)點(diǎn)中空指針數(shù)等于所有關(guān)鍵碼的總數(shù)加1。 四、運(yùn)算題（5小題，每小題6分，共30分） 1. 假定一棵二叉樹廣義表表示為a(b(c),d(e,f)，分別寫出對它進(jìn)行中序、后序、按層遍歷的結(jié)果。 中序： 后序： 按層： 2. 一個(gè)一維數(shù)組a10中存儲(chǔ)著有序表(15,26,34,39,45,56,58,63,74,76)，根據(jù)折半搜索所對應(yīng)的判定樹，寫出該判定樹中度為1的結(jié)點(diǎn)個(gè)數(shù)，并求出在等概率情況下進(jìn)行成功搜索時(shí)的平均搜索長度。 度為1的結(jié)點(diǎn)個(gè)數(shù)： 平均搜索長度： 3. 假定一個(gè)線性序列為(38,42,55,15,23,44,30,74,48,2

8、6)，根據(jù)此線性序列中元素的排列次序生成一棵二叉搜索樹，求出該二叉搜索樹中左子樹為空的所有單支結(jié)點(diǎn)、右子樹為空的所有單支結(jié)點(diǎn)和所有葉子結(jié)點(diǎn)，請按照結(jié)點(diǎn)值從小到大的次序?qū)懗觥?左子樹為空的所有單支結(jié)點(diǎn)： 右子樹為空的所有單支結(jié)點(diǎn)： 所有葉子結(jié)點(diǎn)： 4. 已知一個(gè)圖的頂點(diǎn)集V和邊集G分別為： V=1,2,3,4,5,6; E=<1,2>,<1,3>,<2,4>,<2,5>,<3,4>,<4,5>,<4,6>,<5,1>,<5,3>,<6,5> 假定該圖采用鄰接表表示，每個(gè)頂點(diǎn)鄰接

9、表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號（即數(shù)值域的值）從小到大的次序鏈接的，試寫出： (1) 從頂點(diǎn)1出發(fā)進(jìn)行深度優(yōu)先搜索所得到的頂點(diǎn)序列； (2) 從頂點(diǎn)1出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的頂點(diǎn)序列。 (1)： (2)： 5. 已知一個(gè)數(shù)據(jù)序列為6,45,27,23,41,5,56,64，把它調(diào)整為最大堆并給出進(jìn)行兩趟交換和堆排序后的結(jié)果(即尾部得到2個(gè)最大數(shù))。 最大堆： 兩趟排序后結(jié)果： 五、算法分析題（3小題，每小題6分，共18分） 1. 該算法功能為：從表頭指針為la的、按值從小到大排列的有序鏈表中刪除所有值相同的多余元素，并釋放被刪結(jié)點(diǎn)的動(dòng)態(tài)存儲(chǔ)空間。閱讀算法，按標(biāo)號填寫空缺的內(nèi)容，要求統(tǒng)一填寫在

10、算法后面的標(biāo)記處。 void purge_linkst(ListNode *& la) ListNode *p,*q; if(la=NULL) return; q=la; p=la->link; while (p) if(_(1)_) q=p; p=p->link; else q->link= _(2)_; delete(p); p=_(3)_; (1) (2) (3) 2. 請寫出下面算法的功能，其中Stack表示棧類，Queue表示隊(duì)列類。 void unknown(Queue &Q) Stack S; int d; S.InitStack( ); whi

11、le(!Q.IsEmpty( ) Q.DeQueue(d); /出隊(duì)列元素值由變量d帶回 S.Push(d); while(!S.IsEmpty( ) S.Pop(d); /出棧元素值由變量d帶回 Q.EnQueue(d); 算法功能： 3. 已知二叉樹中的結(jié)點(diǎn)類型BinTreeNode定義為: struct BinTreeNode ElemType data;BinTreeNode *left, *right; 其中data為結(jié)點(diǎn)值域，left和right分別為指向左、右子女結(jié)點(diǎn)的指針域。下面函數(shù)的功能是從二叉樹BT中查找值為X的結(jié)點(diǎn)，若查找成功則返回結(jié)點(diǎn)地址，否則返回空。按標(biāo)號填寫空缺的內(nèi)

12、容，要求統(tǒng)一填寫在算法后面的標(biāo)記處。 BinTreeNode* BTF(BinTreeNode* BT, ElemType x) if(BT=NULL) _(1)_; else if(BT->data=x) _(2)_; else BinTreeNode* t; if(t=BTF(BT->left, x) return t; _(3)_; return NULL; (1) (2) (3) 六、算法設(shè)計(jì)題（2小題，每小題6分，共12分） 1.在一個(gè)帶表頭附加結(jié)點(diǎn)的單鏈表L中，假定所有結(jié)點(diǎn)的值按遞增順序排列，試編寫一個(gè)while循環(huán)補(bǔ)充下面函數(shù)，功能是刪除表L中所有其值大于等于min，

13、同時(shí)小于等于max的結(jié)點(diǎn)。 void rangeDelete(ListNode*& L, ElemType min, ElemType max) ListNode *q=L, *p=L->link; /添加的while循環(huán)位置 /請把while循環(huán)內(nèi)容寫在此行下面 2. 已知二叉搜索樹中的結(jié)點(diǎn)類型BinTreeNode定義為: struct BinTreeNode ElemType data; BinTreeNode *left, *right; 其中data為結(jié)點(diǎn)值域，left和right分別為指向左、右子女結(jié)點(diǎn)的指針域。參數(shù)BST指向一棵二叉搜索樹的根結(jié)點(diǎn)。試根據(jù)下面的函數(shù)聲

14、明編寫一個(gè)非遞歸算法，從BST樹中搜索出具有item參數(shù)值的結(jié)點(diǎn)，若搜索成功則返回該結(jié)點(diǎn)的地址，否則返回NULL。 BinTreeNode* Find(BinTreeNode* BST, const ElemType& item); /請把函數(shù)定義寫在此行下面中央廣播電視大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)數(shù)據(jù)結(jié)構(gòu)試題（6）參考解答及評分標(biāo)準(zhǔn)2004年9月 一、單項(xiàng)選擇題，在括號內(nèi)填寫所選擇的標(biāo)號（9小題，每小題2分，共18分） 1. B 2. A 3. B 4. C 5. A 6. D 7. A 8. B 9. C 二、填空題，在橫線處填寫合適內(nèi)容（12小題，每小題1分，共12分） 1. 數(shù)據(jù)封

15、裝 2. 值 3. 不一定 4. 棧頂指針 5. 遞歸 6. 85 7. 2i+2 8. 48 9. 連通分量 10. n/2 11. O(n) 12. ém/2ù-1 三、判斷題，在每小題前面打?qū)μ柋硎菊_或打叉號表示錯(cuò)誤（10小題，每小題1分，共10分） 1. 對 2. 對 3. 錯(cuò) 4. 對 5. 對 6. 錯(cuò) 7. 錯(cuò) 8. 對 9. 對 10. 對 四、運(yùn)算題（5小題，每小題6分，共30分） 1. 中序：c,b,a,e,d,f /2分 后序：c,b,e,f,d,a /2分 按層：a,b,d,c,e,f /2分 2. 度為1的結(jié)點(diǎn)個(gè)數(shù)：3 /3分 平均搜索長度：29

16、/10 /3分 3. 左子樹為空的所有單支結(jié)點(diǎn)：15,23,42,44 /2分 右子樹為空的所有單支結(jié)點(diǎn)：30 /2分 所有葉子結(jié)點(diǎn)：26,48,74 /2分 4. (1) 1,2,4,5,3,6 /3分 (2) 1,2,3,4,5,6 /3分 5. 最大堆： 64,45,56,23,41,5,27,6 /3分 兩趟排序結(jié)果：45,41,27,23,6,5,56,64 /3分 五、算法分析題（3小題，每小題6分，共18分） 1. (1) p->data>q->data（或p->data!=q->data） /2分 (2) p->link /2分 (3) q-

17、>link /2分 2. 利用"棧"作為輔助數(shù)據(jù)結(jié)構(gòu),將隊(duì)列Q中的元素逆置（即按相反次序放置）。 3. (1) NULL /2分 (2) return BT /2分 (3) if(t=BTF(BT->right, x) return t /2分 六、算法設(shè)計(jì)題（2小題，每小題6分，共12分） 評分標(biāo)準(zhǔn)：根據(jù)編寫正確程度酌情給分。 1. while(p!=NULL) if(p->data>=min && p->data<=max) q->link=p->link; delete p; p=q->link; else q=p; p=p->link; 2. BinTreeNode* Find(BinTreeNode* BST, const ElemType& item) while(BST!=NULL) if(item=BST->data