四川大學(xué)錦城學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法期末復(fù)習(xí)總結(jié).doc

1、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ C ）兩大類。A動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C線性結(jié)構(gòu)、非線性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2、以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（ D ）？ A廣義表 B. 二叉樹 C. 稀疏矩陣 D. 串3、在下面的程序段中，對x的賦值語句的頻度為（ C ）for (i=1;i=n;i+)for (j=1;j=n;i+) x=x+1;A O(2n) BO(n) CO(n2) DO(log2n) 4、下面關(guān)于線性表的敘述中，錯誤的是哪一個？（ B ）A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。5、某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ D ）存儲方式最節(jié)省運(yùn)算時間。A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表6、 靜態(tài)鏈表中指針表示的是（ B ）. A 內(nèi)存地址 B數(shù)組下標(biāo) C下一元素地址 D左、右孩子地址7、下面的敘述不正確的是（ BC ）A線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值成正比 B. 線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值無關(guān)C. 線性表在順序存儲時，查找第i個元素的時間同i 的值成正比D. 線性表在順序存儲時，查找第i個元素的時間同i的值無關(guān)8、 若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為（ C ）(1=inext=s;s-next=p-next; B s-next=p-next;p-next=s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s;10、對于一個頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（ B ）Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL11、 一個棧的輸入序列為123n，若輸出序列的第一個元素是n，輸出第i（1=i(空格串是由空格組成的)C模式匹配是串的一種重要運(yùn)算 D串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?7、設(shè)有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（ C ）A求子串 B聯(lián)接 C匹配 D求串長18、 設(shè)有數(shù)組Ai,j，數(shù)組的每個元素長度為3字節(jié)，i的值為1 到8 ，j的值為1 到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時，元素A5，8的存儲首地址為( B )。30*6180A. BA+141 B. BA+180 C. BA+222 D. BA+22519、已知廣義表L=（x,y,z），a，（u，t，w），從L表中取出原子項(xiàng)t的運(yùn)算是（ D ）。A. head（tail（tail（L） B. tail（head（head（tail（L） C. head（tail（head（tail（L） D. head（tail(head（tail（tail（L）)）20、廣義表A=(a,b,(c,d),(e,(f,g),則下面式子的值為（ D ）。Head(Tail(Head(Tail(Tail(A)A. (g) B. (d) C. c D. d二、判斷題1、 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。( )2、算法可以用不同的語言描述，如果用C 語言或PASCAL語言等高級語言來描述，則算法實(shí)際上就是程序了。( Y ) 3、 順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。( )4、線性表采用鏈表存儲時，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲空間可以是不連續(xù)的。( )5、線性表的特點(diǎn)是每個元素都有一個前驅(qū)和一個后繼。( )6、一個稀疏矩陣Am*n采用三元組形式表示， 若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把m和n的值互換，則就完成了Am*n的轉(zhuǎn)置運(yùn)算。（ ） 7、所謂取廣義表的表尾就是返回廣義表中最后一個元素。（ ）9在一棵高度為k的滿二叉樹中，結(jié)點(diǎn)總數(shù)為（ C）A2k-1 B2k C2k-1 Dlog2k+120由3 個結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（ D ）A2 B3 C4 D5 22從下列有關(guān)樹的敘述中,選出5條正確的敘述(共5分) （ CDFHI ）A二叉樹中每個結(jié)點(diǎn)有兩個子結(jié)點(diǎn),而樹無此限制,因此二叉樹是樹的特殊情況。B當(dāng)K1時高度為K的二叉樹至多有2k-1個結(jié)點(diǎn)。C用樹的前序周游和中序周游可以導(dǎo)出樹的后序周游。D線索二叉樹的優(yōu)點(diǎn)是便于在中序下查找前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。E將一棵樹轉(zhuǎn)換成二叉樹后,根結(jié)點(diǎn)沒有左子樹。F一棵含有N個結(jié)點(diǎn)的完全二叉樹,它的高度是LOG2N+1。G在二叉樹中插入結(jié)點(diǎn),該二叉樹便不再是二叉樹。H采用二叉樹鏈表作樹的存儲結(jié)構(gòu),樹的前序周游和其相應(yīng)的二叉樹的前序周游的結(jié)果是一樣的。I哈夫曼樹是帶權(quán)路徑最短的樹,路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。J用一維數(shù)組存儲二叉樹時,總是以前序周游存儲結(jié)點(diǎn)。判斷題1完全二叉樹中，若一個結(jié)點(diǎn)沒有左孩子，則它必是樹葉。2. 二叉樹只能用二叉鏈表表示。3在二叉樹的第i層上至少有2i-1個結(jié)點(diǎn)(i=1) 4度為二的樹就是二叉樹。5. 在中序線索二叉樹中，每一非空的線索均指向其祖先結(jié)點(diǎn)。第十章選擇題1下面給出的四種排序法中( D )排序法是不穩(wěn)定性排序法。 A. 插入 B. 冒泡 C. 二路歸并 D. 堆排序2下列排序算法中，其中（ D ）是穩(wěn)定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接選擇排序，歸并排序 D. 歸并排序，冒泡排序3下面的排序算法中，不穩(wěn)定的是（ CDF ） A.起泡排序 B.折半插入排序 C.簡單選擇排序 D.希爾排序 E.基數(shù)排序 F.堆排序。4對一組數(shù)據(jù)（84，47，25，15，21）排序，數(shù)據(jù)的排列次序在排序的過程中的變化為（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 則采用的排序是 (A )。 A. 選擇 B. 冒泡 C. 快速 D. 插入5. 在下面的排序方法中，輔助空間為O（n）的是( D ) 。 A希爾排序 B. 堆排序 C. 選擇排序 D. 歸并排序 6. 下列排序算法中，占用輔助空間最多的是：(A ) A. 歸并排序 B. 快速排序 C. 希爾排序 D. 堆排序7用直接插入排序方法對下面四個序列進(jìn)行排序（由小到大），元素比較次數(shù)最少的是（ C ）。A 94,32,40,90,80,46,21,69 B 32,40,21,46,69,94,90,80C 21,32,46,40,80,69,90,94 D 90,69,80,46,21,32,94,408直接插入排序在最好情況下的時間復(fù)雜度為（ B ） A O(logn) B O(n) C O(n*logn) D O(n2)9對下列關(guān)鍵字序列用快速排序法進(jìn)行排序時，速度最快的情形是（A ）。A 21,25,5,17,9,23,30 B25,23,30,17,21,5,9C 21,9,17,30,25,23,5 5,9,17,21,23,25,3010下列四個序列中，哪一個是堆（ C ）。 A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15判斷1內(nèi)排序要求數(shù)據(jù)一定要以順序方式存儲。 （ ）2排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。（ ）3直接選擇排序算法在最好情況下的時間復(fù)雜度為O（N）。（ ）4在待排數(shù)據(jù)基本有序的情況下，快速排序效果最好。（ ）5快速排序總比選擇排序快。（）填空1若不考慮基數(shù)排序，則在排序過程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的_比較_和記錄的_移動_。2關(guān)鍵碼序列（ Q，H，C，Y，Q，A，M，S，R，D，F(xiàn)，X），要按照關(guān)鍵碼值遞增的次序進(jìn)行排序，若采用初始步長為4的Shell排序法，則一趟掃描的結(jié)果是_ Q A C S Q D F X R H M Y _；若采用以第一個元素為分界元素的快速排序法，則掃描一趟的結(jié)果是_ F H C D M A Q S R Q Y X _。 第九章選擇題1、 對N個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為(A ) A（N+1）/2 B. N/2 C. N D. （1+N）*N /22. 下面關(guān)于二分查找的敘述正確的是 ( D ) A. 表必須有序，表可以順序方式存儲，也可以鏈表方式存儲 C. 表必須有序，而且只能從小到大排列B. 表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型 D. 表必須有序，且表只能以順序方式存儲3. 二叉查找樹的查找效率與二叉樹的( （1）C )有關(guān), 在 (（2）C)時其查找效率最低 (1): A. 高度 B. 結(jié)點(diǎn)的多少 C. 樹型 D. 結(jié)點(diǎn)的位置 (2): A. 結(jié)點(diǎn)太多 B. 完全二叉樹 C. 呈單枝樹 D. 結(jié)點(diǎn)太復(fù)雜。4. 若采用鏈地址法構(gòu)造散列表，散列函數(shù)為H（key）=key MOD 17，則需 (（1）A) 個鏈表。這些鏈的鏈?zhǔn)字羔槝?gòu)成一個指針數(shù)組，數(shù)組的下標(biāo)范圍為 (（2）C) （1） A17 B. 13 C. 1