數(shù)據(jù)結(jié)構(gòu)練習(xí)

1、填空題1.在順序表中訪問(wèn)任意一個(gè)元素的時(shí)間復(fù)雜度均為O(1)，因此順序表也稱為隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)。2二維數(shù)組a43(下標(biāo)從0開(kāi)始)，假設(shè)a00的地址為50，數(shù)據(jù)以行序優(yōu)先方式存儲(chǔ)，每個(gè)元素的長(zhǎng)度為2字節(jié)，則a21地址是64。3.直接插入排序用監(jiān)視哨的作用是防止數(shù)組下標(biāo)越界。4.已知廣義表Ls=(a, (b, c), (d, e),運(yùn)用head和tail函數(shù)取出Ls中的原子d的運(yùn)算是Head（Head（Tail（Tail（LS）。5對(duì)有14個(gè)元素的有序表A1.14進(jìn)行折半查找，當(dāng)比較到A4時(shí)算法結(jié)束。被比較元素除A4外，還有A3A5A7。6.在AOV網(wǎng)中，頂點(diǎn)表示活動(dòng)，邊表示活動(dòng)之間的先后關(guān)系。

2、7.有向圖G可進(jìn)行拓?fù)渑判虻呐袆e條件是有向無(wú)環(huán)圖。8.若串S1=ABCDEFGHIJK,S2=451223,S3=#,則執(zhí)行Substring(S1,Strlength(S3),Index(S2,12,1)的結(jié)果是DEF。選擇題1.在下列存儲(chǔ)形式中，哪一個(gè)不是樹(shù)的存儲(chǔ)形式？（ D）A雙親表示法B孩子鏈表表示法C孩子兄弟表示法D順序存儲(chǔ)表示法2.查找n個(gè)元素的有序表時(shí)，最有效的查找方法是（C）。A順序查找B分塊查找C折半查找D二叉查找3.將所示的s所指結(jié)點(diǎn)加到p所指結(jié)點(diǎn)之后，其語(yǔ)句應(yīng)為（D）。As-next=p+1 ; p-next=s;B(*p).next=s; (*s).next=(*p).

3、next;Cs-next=p-next ; p-next=s-next;Ds-next=p-next ; p-next=s;4.在有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)中，頂點(diǎn)v在鏈表中出現(xiàn)的次數(shù)是（C）。A.頂點(diǎn)v的度B.頂點(diǎn)v的出度C.頂點(diǎn)v的入度D.依附于頂點(diǎn)v的邊數(shù)5.算法的時(shí)間復(fù)雜度為O（nlog2n）、空間復(fù)雜度為O(1)的排序算法是（A）。A.堆排序B.快速排序C.歸并排序D.直接選擇1. 設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角部分（如右圖所示）按行序存放在一維數(shù)組B 1, n(n-1)/2 中，對(duì)下三角部分中任一元素ai,j(ij),在一維數(shù)組B中下標(biāo)k的值是（B ）：i(i-1)/

4、2+j-1i(i-1)/2+ji(i+1)/2+j-1i(i+1)/2+j2.由一個(gè)長(zhǎng)度為11的有序表，按二分查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下，查找成功的平均查找長(zhǎng)度是（C）。A29/11B. 31/11C. 33/11D.35/113.AVL樹(shù)是一種平衡的二叉排序樹(shù)，樹(shù)中任一結(jié)點(diǎn)的（B）。A.左、右子樹(shù)的高度均相同B.左、右子樹(shù)高度差的絕對(duì)值不超過(guò)1C.左子樹(shù)的高度均大于右子樹(shù)的高度D.左子樹(shù)的高度均小于右子樹(shù)的高度4.下列四種排序方法中，不穩(wěn)定的方法是（D）。A.直接插入排序B.冒泡排序C.歸并排序D.堆排序5.設(shè)樹(shù)的度為4，其中度為1,2,3,4的結(jié)點(diǎn)個(gè)數(shù)分別為4, 2,

5、,1, 1,則T中的葉子數(shù)為（D）。A5B6C7D8判斷題1.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（ F）2.數(shù)組不適合作任何二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。（F）3.廣義表的取表尾運(yùn)算，其結(jié)果通常是個(gè)表，但有時(shí)也可是個(gè)原子。（F）4.在含有n個(gè)結(jié)點(diǎn)的樹(shù)中，邊數(shù)只能是n-1條。（T ）5.所謂一個(gè)排序算法是否穩(wěn)定，是指該算法在各種情況下的效率是否相差不大。（F）6.簡(jiǎn)單選擇排序在最好情況下的時(shí)間復(fù)雜度為O(n)。（ F）7.在二叉排序樹(shù)中插入一個(gè)新結(jié)點(diǎn)，總是插入到葉結(jié)點(diǎn)下面。（ F）8.采用線性探測(cè)處理沖突，當(dāng)從哈希表中刪除一個(gè)記錄時(shí)，不應(yīng)將該記錄所在位置置空，因?yàn)檫@會(huì)影響以后的查找。（

6、 T）9.n個(gè)數(shù)存放在一維數(shù)組A1.n中，在進(jìn)行順序查找時(shí)，這n個(gè)數(shù)的排列有序或無(wú)序，其平均查找長(zhǎng)度不同。（F ）10.廣義表中原子個(gè)數(shù)即為廣義表的長(zhǎng)度。(F)將下列由三棵樹(shù)組成的森林轉(zhuǎn)換為二叉樹(shù)。給定下列圖，完成以下問(wèn)題（1）畫(huà)出該圖的鄰接矩陣和鄰接表（2）根據(jù)所畫(huà)的鄰接表，從頂點(diǎn)B出發(fā)，畫(huà)出圖的深度優(yōu)先搜索樹(shù)（3）根據(jù)普里姆（Prim）算法，求它的最小生成樹(shù)（不必寫(xiě)出全部過(guò)程，在生成樹(shù)中標(biāo)出邊生成的次序即可）(1)鄰接矩陣：鄰接表：(2)深度優(yōu)先搜索樹(shù)為：(3)最小生成樹(shù)：輸入一個(gè)正整數(shù)序列（53,17,12,66,58,70,87,25,56,60），試完成下列各題：（1）構(gòu)造一棵二叉排

7、序樹(shù)，計(jì)算查找成功的平均查找長(zhǎng)度；（2）依此二叉排序樹(shù)，如何得到一個(gè)從大到小的有序序列；（3）畫(huà)出在此二叉排序樹(shù)中，刪除“66”后的樹(shù)結(jié)構(gòu)。(1)二叉排序樹(shù)如下：平均查找長(zhǎng)度ASL=(1+2X2+4X3+3X4)/10=2.9(2) 按照右子樹(shù)根節(jié)點(diǎn)左子樹(shù)的順序遍歷該二叉樹(shù)，即可得到從大到小的順序(3)將序列25, 34, 12, 7, 15, 47, 65, 79，47+，16中的關(guān)鍵字按升序重新排列，請(qǐng)寫(xiě)出（1）冒泡排序一趟掃描的結(jié)果（2）以第一個(gè)元素為分界點(diǎn)的快速排序一趟掃描的結(jié)果（3）堆排序所建的初始堆和第一趟排序結(jié)果。（1）25、12、7、15、34、47、65、47+、16、79（

8、2）16、15、12、7、25、47、65、79、47+、34（3）初始堆：79、47+、65、34、16、47、12、7、25、15第一趟排序后：65、47+、47、34、16、15、12、7、25、79（最好劃出二叉樹(shù)表示）程序填空題下列算法是建立單鏈表的算法，請(qǐng)?zhí)顚?xiě)適當(dāng)?shù)恼Z(yǔ)句，完成該功能。typedef struct LnodeElemTypedata;struct Lnode*next;LNode, *LinkList;Status CreatList_L(LinkList &L, int n)/正序輸入n個(gè)元素的值,建立帶表頭結(jié)點(diǎn)的單鏈線性表LL=(LinkList) malloc(

9、sizeof(LNode);if(!L) return ERROR;L-next=NULL;p=( 1 );for(i=0;idata);(2);(3);p-next=NULL;return OK;/CreatList_L1.L2.p-next = s3.p = s用鏈表實(shí)現(xiàn)的簡(jiǎn)單選擇排序。設(shè)鏈表頭指針為L(zhǎng),鏈表無(wú)頭結(jié)點(diǎn)，請(qǐng)?zhí)顚?xiě)適當(dāng)?shù)恼Z(yǔ)句，完成該功能。void SelectSort(LinkList L)p=L;while(p)q=p; r=q-next;while( r )if(1)q=r;r=(2);tmp=q-data; q-data=p-data; p-data=tmp;p=(3);1

10、.q-data r-data2.r-next3.p-next1.棧和隊(duì)列的共同特點(diǎn)是(A)。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒(méi)有共同點(diǎn)2.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)(D).A.僅修改頭指針B.頭、尾指針都要修改 C.僅修改尾指針D. 頭、尾指針可能都要修改3.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？(D)A.隊(duì)列B.棧C.線性表D.二叉樹(shù)4.設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在644(10)，A22存放位置在676(10)，每個(gè)元素占一個(gè)空間，問(wèn)A33(10)存放在什么位置？腳注(10)表示用10進(jìn)制表示（C）。A688B678C692D696

11、5.樹(shù)最適合用來(lái)表示(C)。A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無(wú)聯(lián)系的數(shù)據(jù)1.二叉樹(shù)的第k層的結(jié)點(diǎn)數(shù)最多為(D).A2k-1B.2K+1C.2K-1 D. 2k-12.若有18個(gè)元素的有序表存放在一維數(shù)組A19中，第一個(gè)元素放A1中，現(xiàn)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為(D)A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，33.對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為（C）A. O（1）B. O（n）C. O（1og2n）D. O（n2）4.對(duì)于線性表（7，34，55，25，64，46，20，10）進(jìn)行