杭電-數(shù)據(jù)結(jié)構(gòu)-期末復(fù)習(xí)卷及答案

1.數(shù)據(jù)結(jié)構(gòu)可用三元式表示〔D，S，P〕。其中：D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的根本操作集。×3.隊(duì)列是數(shù)據(jù)對(duì)象特定的線性表?！?.二叉樹是一棵結(jié)點(diǎn)的度最大為二的樹?！?．一棵無(wú)向連通圖的生成樹是其極大的連通子圖?！?．二叉排序樹的查找長(zhǎng)度至多為log2ｎ?！?0．對(duì)于目前所知的排序方法，快速排序具有最好的平均性能。√12.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。√14.折半查找不適用于有序鏈表的查找?！?5.完全二叉樹必定是平衡二叉樹。Right中序二叉樹的優(yōu)點(diǎn)是便于在中序下查找直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)?！?8.平均查找長(zhǎng)度與記錄的查找概率有關(guān)?！?9.廣義表的表頭和表尾都有可能是原子或廣義表?！?.假設(shè)廣義表LS滿足GetHead(LS)==GetTail(LS)，那么LS為(b)。A.()B.(())C.((),())D.((),(),())5.對(duì)二叉排序樹按〔c〕可得到有序序列。a:層次遍歷b:前序遍歷c:中序遍歷d:后序遍歷8．關(guān)鍵路徑是指在只有一個(gè)源點(diǎn)和一個(gè)匯點(diǎn)的有向無(wú)環(huán)網(wǎng)中源點(diǎn)至匯點(diǎn)〔c〕的路徑。a:弧的數(shù)目最多b:弧的數(shù)目最少c:權(quán)值之和最大d:權(quán)值之和最小9.哈希表的查找效率取決于〔d〕。a:哈希函數(shù)b:處理沖突的方法。c:哈希表的裝填因子d:以上都是10．從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成(c)。c:線性結(jié)構(gòu)和非線性結(jié)構(gòu)13．當(dāng)待排序序列的關(guān)鍵字次序?yàn)榈剐驎r(shí)，假設(shè)需為之進(jìn)行正序排序，以下方案中(d)為佳。a:起泡排序b:快速排序c:直接插入排序d:簡(jiǎn)單項(xiàng)選擇擇排序14．假設(shè)從二叉樹的根結(jié)點(diǎn)到其它任一結(jié)點(diǎn)的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字遞增有序，那么該二叉樹是(c)。a:二叉排序樹b:赫夫曼樹c:堆d:平衡二叉樹15．以下圖所有可能的拓?fù)湫蛄杏?b)種。a:2b:3c:4d:516．以下排序算法中，(d)算法可能會(huì)出現(xiàn)：初始數(shù)據(jù)為正序時(shí)，花費(fèi)的時(shí)間反而最多。a:堆排序b:起泡排序c:歸并排序d:快速排序18．設(shè)森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為m1、m2和m3，那么與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是(d)。a:m1b:m1+m2c:m3d:m2+m319.根據(jù)插入次序〔80，90，100，110，85，70，75，60，72〕建立二叉排序樹。圖〔a〕是最終變化的結(jié)果。假設(shè)仍以該插入次序建立平衡二叉樹。圖〔c〕是最終變化的結(jié)果。a:b:8080709075906075851006070851007211072110c:d:909075100801007080110757085110607285607220.設(shè)輸入序列為20,45,30,89,70,38,62，19，依次插入到一棵2-3樹中(初始狀態(tài)為空)，該B-樹為〔b〕。再刪除38，該B-樹為〔f〕。a:b:〔3062〕〔45〕〔19，20〕〔3845〕〔70，89〕〔30〕〔70〕〔1920〕〔38〕〔62〕〔89〕c:d:〔4570〕〔45〕〔20〕〔62〕〔89〕〔20〕〔70〕〔19〕〔30〕〔19〕(30,38〕〔62〕〔89〕e:f:〔3070〕〔45〕〔19，20〕〔4562〕〔89〕〔20〕〔70〕〔19〕〔30〕〔62〕〔89〕22．假設(shè)有序表中關(guān)鍵字序列為：14，20，25，32，34，45，57，69，77，83，92。對(duì)其進(jìn)行折半查找，那么在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度是(c)。查找32時(shí)需進(jìn)行(c)次比擬。a:1b:223.設(shè)一棵二叉樹BT的存儲(chǔ)結(jié)構(gòu)如下:12345678lchild23006000dataABCDEFGHrchild05408700其中l(wèi)child，rchild分別為結(jié)點(diǎn)的左、右孩子指針域，data為結(jié)點(diǎn)的數(shù)據(jù)域。那么該二叉樹的高度為(d)；第3層有(a)個(gè)結(jié)點(diǎn)〔根結(jié)點(diǎn)為第1層〕。a:2b:3c:4d:525．假設(shè)某二叉樹有20個(gè)葉子結(jié)點(diǎn)，有20個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，那么該二叉樹的總結(jié)點(diǎn)數(shù)是(c)。a:40b:55c:59d:6127．某有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖。0E21∧1D034∧2C40E21∧1D034∧2C4∧3B120∧4A2∧根據(jù)存儲(chǔ)結(jié)構(gòu)，依教材中的算法其深度優(yōu)先遍歷次序?yàn)椤瞕〕。廣度優(yōu)先遍歷次序?yàn)椤瞔〕。各強(qiáng)連通分量的頂點(diǎn)集為〔f〕。a:abcdeb:edcba.c:ecdab.d:ecadb.e:abc及edf:ac及bedg:ab及cedh:bc及aed29．設(shè)有二維數(shù)組A5x7,每一元素用相鄰的4個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。A的起始地址為100。那么按行存儲(chǔ)時(shí)，元素A06的存儲(chǔ)地址是〔d〕；按列存儲(chǔ)時(shí)，元素A06的存儲(chǔ)地址是〔a〕。a.220b.200c.140d.12430.假設(shè)順序表中各結(jié)點(diǎn)的查找概率不等，那么可用如下策略提高順序查找的效率：假設(shè)找到指定的結(jié)點(diǎn)，將該結(jié)點(diǎn)與其后繼〔假設(shè)存在〕結(jié)點(diǎn)交換位置，使得經(jīng)常被查找的結(jié)點(diǎn)逐漸移至表尾。以下為據(jù)此策略編寫的算法，請(qǐng)選擇適當(dāng)?shù)膬?nèi)容，完成此功能。順序表的存儲(chǔ)結(jié)構(gòu)為：typedefstruct{ElemType*elem;//數(shù)據(jù)元素存儲(chǔ)空間，0號(hào)單元作監(jiān)視哨intlength;//表長(zhǎng)度}SSTable;intsearch_seq(SSTableST,KeyTypekey){//在順序表ST中順序查找關(guān)鍵字等于key的數(shù)據(jù)元素。//假設(shè)找到，那么將該元素與其后繼交換位置，并返回其在表中的位置，否那么為0。ST.elem[0].key=key;i=ST.length;while(ST.elem[i].key!=key)f;if(g){ST.elem[i]←→ST.elem[i+1]；e；}returni;}a:i>0b:i>=0c:i<ST.lengthd:i<=ST.lengthe:i++f:i--g:A和C同時(shí)滿足h:B和D同時(shí)滿足1.單鏈表結(jié)點(diǎn)的類型定義如下：typedefstructLNode{intdata;structLNode*next;}LNode,*Linklist;寫一算法，Contrary(linklist&L),對(duì)一帶頭結(jié)點(diǎn)且僅設(shè)尾指針L的循環(huán)單鏈表就地逆置。〔即首元變尾元，尾元變首元?！硋oidContrary(linklist&L){p=L->next;q=L;while(p!=L){r=p->next;p->next=q;q=p;p=r;}p->next=q;}2．二叉樹用二叉鏈表存儲(chǔ)表示。typedefstructBiTNode{TelemTypedata;StructBiTNode*lchild,*rchild;}BiTNode,*BiTree;試編寫銷毀二叉樹T的算法DestroyBiTree(BiTree&T)。voidDestroyBiTree(BiTree&T){if(!T)return;if(T-lchild)DestroyBiTree(T->lchild);if(T-rchild)DestroyBiTree(T->rchild);free(T);T=NULL;}3．設(shè)帶頭結(jié)點(diǎn)的單鏈表中的元素以值非遞減有序排列，試編寫算法，刪除表中所有值相同的多余元素。單鏈表結(jié)點(diǎn)的類型定義如下