西北民族大學(xué)數(shù)據(jù)結(jié)構(gòu)題庫(kù)

1、選擇題1. 在數(shù)據(jù)結(jié)構(gòu)中，邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）A. 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C. 線性結(jié)構(gòu)和非線性結(jié)構(gòu)D. 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2. 在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行（ ）。A. p->next=p->next->nextB. p=p->next,p->next=p->next->nextC. p->next=p->nextD. p=p->next->next3. 設(shè)高度為15的二叉樹上只有度為0和1的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（ ）。A. 30B. 31C. 29D.

2、154. 已知二叉樹中有兩個(gè)孩子的結(jié)點(diǎn)數(shù)為18，僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為30，則總節(jié)點(diǎn)數(shù)為（ ）。A. 48B. 65C. 67D. 775. 無向圖G=（V,E），其中：V=(a,b),(a,e),(a,c),(b,e),(e,f),(f,d),(e,d),在下面的5個(gè)序列中，符合深度優(yōu)先遍歷的序列有多少？（ ）（1）a e b d f c （2） a c f d e b （3） a e d f c b（4）a e f d c b （5）a e f d b cA. 5個(gè)B. 4個(gè)C. 3個(gè)D. 2個(gè)6. 有一個(gè)有序表1,3,5,7,8,10,15,17,19,30,41,50,70，當(dāng)二分查找

3、值為19的結(jié)點(diǎn)時(shí)，（ ）次比較后查找成功。A. 2B. 3C. 4D. 97. 下列不是算法的特性的是（ ）。A. 有窮性 B. 確定性C. 可能性 D. 輸入和輸出特性8. 線性表若采用鏈?zhǔn)浇Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址( )。A. 一定是不連續(xù)的 B. 連續(xù)不連續(xù)都可以C. 必須是連續(xù)的 D. 部分地址必須是連續(xù)的9. 在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行( )。A. p->next=p->next-next; B. p=p->next;p->next=p->next->next;C. p->next=p->next; D

4、. p=p->next->next10. 一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能輸出序列是( )。A. dceab B. abcde C. edcba D. decba11. 限定線性表有（ ）。A.棧 B.隊(duì)列 C.樹 D.A和B12. 進(jìn)行入隊(duì)運(yùn)算時(shí)，必須先判斷隊(duì)列是否（ ）。A. 空 B. 滿 C. 下溢 D. 上溢13. 進(jìn)行出棧運(yùn)算時(shí)，必須先判斷棧是否（ ）。A. 空 B. 滿 C. 下溢 D. 上溢14. 判定一個(gè)棧ST(棧的存儲(chǔ)空間大小為M)為空的條件是( )。A. ST->top!=0 B. ST->top=0C. ST->top!=M

5、 D. ST->top=M15. 遞歸函數(shù)f(n)=f(n-1)+n(n>1)的遞歸體是( )。A. f(1)=0 B. f(0)=1C. f(n)=f(n-1)+n D. f(n)=n16. 串是一種特殊的線性表，其特殊性體現(xiàn)在( )。A. 數(shù)據(jù)元素是一個(gè)字符 B. 數(shù)據(jù)元素可以是多個(gè)字符C. 可以順序存儲(chǔ) D. 可以鏈?zhǔn)酱鎯?chǔ) 17. 若串S=”software”,則其子串的數(shù)目是( )。A. 8 B. 7 C. 6 D. 918. 兩個(gè)字符串相等的充分必要條件是（ ）。A 、兩個(gè)串的長(zhǎng)度相等 B 、兩個(gè)串包含的字符相等C 、兩個(gè)串的長(zhǎng)度相等，并且兩個(gè)串包含的字符相等。 D、 兩

6、個(gè)串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相等。19. 已知廣義表L=(a,(b,c),其表頭是( )。A. a B. b C. (a,b) D. (c,d)20. 廣義表(a,b),c,d)的表尾是( )。A. a B. b C. (a,b) D. (c,d)21. 樹最適合用來表示( )。A 、有序數(shù)據(jù)元素 B 、無序數(shù)據(jù)元素C 、元素之間具有分支層次關(guān)系的數(shù)據(jù) D、 元素之間無聯(lián)系的數(shù)據(jù)22. 在樹型結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)都可以有（ ）個(gè)孩子結(jié)點(diǎn)。A. 2 B. 1 C. 0 D. 任意多23. 關(guān)鍵路徑是時(shí)間節(jié)點(diǎn)網(wǎng)絡(luò)中（ ）。A. 從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 B. 從源點(diǎn)到匯點(diǎn)的最短路徑C. 最長(zhǎng)回

7、路 D. 最短回路24. 設(shè)高度為15的二叉樹上只有度為0和1的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（ ）。E. 30F. 31G. 29H. 1525. 已知二叉樹中有兩個(gè)孩子的結(jié)點(diǎn)數(shù)為18，僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為30，則總節(jié)點(diǎn)數(shù)為（ ）。E. 48F. 65G. 67H. 77填空題1. 數(shù)據(jù)結(jié)構(gòu)包括（ ）三個(gè)方面。（用英文逗號(hào)分隔，即*結(jié)構(gòu)，*結(jié)構(gòu)，*結(jié)構(gòu)，注意按次序填寫） 邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)，預(yù)算結(jié)構(gòu)或邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)，操作結(jié)構(gòu)2. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為一個(gè)二元組DS=（D,S）其中D是（1）的有限集合，S是D上關(guān)系的有限集合。 數(shù)據(jù)元素3. 當(dāng)線性表的元素綜述總數(shù)基本穩(wěn)定，且

8、很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)該采用（ ）存儲(chǔ)結(jié)構(gòu)4. 對(duì)于雙向鏈表，刪除一個(gè)存在的結(jié)點(diǎn)需修改的指針為（ ）個(gè)。 25. （ ）是限定僅在表尾進(jìn)行插入或刪除操作的線性表。棧 6. 設(shè)有一個(gè)棧，棧頂指針為1000H（十六進(jìn)制），現(xiàn)有輸入序列為1,2,3,4,5經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，棧頂指針是（ ）H。設(shè)棧為順序棧，每個(gè)元素占4個(gè)字節(jié)。 100C7. 設(shè)串s1=”ABCDEFG”,s2=”PQRST”，則Strcat(substr(s1,2,strlen(s2),substr(s1,strlen(s2),2)結(jié)

9、果是（ ）。BCDEFEF8. 空格串是指由（ ）字符所組成的字符串。 空格9. 二維數(shù)組Mij的每個(gè)元素占4個(gè)存儲(chǔ)單元，行下表i的范圍從0到4，列下表j的范圍從0到6，M按列存儲(chǔ)時(shí)M15元素的起始地址與M按行存儲(chǔ)時(shí)元素（ ）的起始地址相同。M3510. 將整型數(shù)組A1818按行優(yōu)先次序存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A73的地址是（ ） 110011. 已知完全二叉樹的第6層有32個(gè)葉子節(jié)點(diǎn)，則整個(gè)二叉樹的節(jié)點(diǎn)數(shù)最少是（ ）6312. 已知完全二叉樹的第7層有14個(gè)葉子結(jié)點(diǎn)，則整個(gè)二叉樹的結(jié)點(diǎn)數(shù)最多時(shí)（ ）。22713. 二叉樹的第10層至多有（ ）個(gè)結(jié)點(diǎn)。51214. 深

10、度為4的二叉樹至多有（ ）個(gè)結(jié)點(diǎn)。1515. 將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)16. 二叉樹的第9層至多有（ ）個(gè)節(jié)點(diǎn)。25617. 深度為7的二叉樹至多有（ ）個(gè)結(jié)點(diǎn)。12718. 將一棵有81個(gè)結(jié)點(diǎn)的完全二叉樹從跟這一層開始，每一層從左到右以此對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為66的結(jié)點(diǎn)的雙親編號(hào)為（ ）3319. 設(shè)廣義表L=（a，（a，b），d，e（i，j），k），則L的深度是（ ） 320.21. 是對(duì)客觀事物的符號(hào)表示，能被計(jì)算機(jī)處理的符號(hào)總稱。22. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)通常包括數(shù)據(jù)的_存儲(chǔ)和_存儲(chǔ)。23

11、. 數(shù)據(jù)的邏輯結(jié)構(gòu)可形式地用一個(gè)二元組S(D，R)來表示，其中D是_，R是_。24. 所有插入和刪除都在表的一端進(jìn)行的線性表稱為 。25. 插入和刪除分別在表的兩端進(jìn)行的線性表稱為 。26. 棧是一種 受限的線性表。27. 當(dāng)棧中元素為n個(gè)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說明該棧的最大容量為 ，設(shè)元素占1個(gè)空間容量。28. 串的兩種基本存儲(chǔ)方式是 和 。29. 串S=”hell o”的長(zhǎng)度是_。30. 串S=”worker”的子串?dāng)?shù)目是_。31. 空串是指數(shù)據(jù)元素個(gè)數(shù)為_的串。32. 已知數(shù)組A0909的每個(gè)元素占5個(gè)存儲(chǔ)單元，將其按行存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A68的地址為

12、 33. 廣義表(a,(a,b),d,e,(i,j),k)的長(zhǎng)度是 34. 設(shè)廣義表L=（a），則L的長(zhǎng)度為_，深度為 .35. 設(shè)廣義表L=（a，（a，b），d，e,（i，（j），k），則L的深度是 ,表頭為 ，表尾是 。36. 空格串是指由_符所組成的字符串。37. 數(shù)據(jù)結(jié)構(gòu)包括_三個(gè)方面。38. 當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)該采用_存儲(chǔ)結(jié)構(gòu)39. 對(duì)于雙向鏈表，刪除一個(gè)存在的結(jié)點(diǎn)需修改的指針為_個(gè)。 240. _是限定僅在表尾進(jìn)行插入或刪除操作的線性表。 判斷題1. 線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不

13、連續(xù)的。2. 鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表，進(jìn)行插入、刪除操作時(shí)，在鏈表中比在順序存儲(chǔ)結(jié)構(gòu)中效率高。3. 隊(duì)列是一種插入與刪除操作分別在表的兩段進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。4. 隊(duì)列邏輯上是一個(gè)上端和下端既能增加又能減少的線性表。5. 如果兩個(gè)含有相同的字符，則說他們相等。6. 空串與空格串是相同的。7. 所謂取廣義表的表尾就是返回廣義表中最后一個(gè)元素。8. 由于二叉樹中每個(gè)結(jié)點(diǎn)的度最大為2，所以二叉樹就是一種特殊的樹。9. 二叉樹中的葉子結(jié)點(diǎn)就是二叉樹中沒有左右子樹的結(jié)點(diǎn)，除了根結(jié)點(diǎn)外。10. 二叉樹的中序遍歷中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的后面。11. 森林的先序遍歷次序與其轉(zhuǎn)

14、換得到的二叉樹的中序遍歷次序相同。12. 已知一個(gè)森林的先序遍歷和中序遍歷，一定能構(gòu)造出該森林。 A13. 有向圖用鄰接矩陣表示后，頂點(diǎn)i的出度等于第i行中非0且非的元素個(gè)數(shù)。14. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于出度之和。15. 所謂平衡二叉樹是指左、右子樹的深度差的絕對(duì)值不大于1的二叉排序樹。且左、右子樹均為平衡二叉樹。16. 所謂平衡二叉樹是指左右子樹的高度差的絕對(duì)值不大于1的二叉排序樹。 B17. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu) 。 18. 程序一定是算法。19. 線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。20. 鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表，進(jìn)行插

15、入、刪除操作時(shí)，在鏈表中比在順序存儲(chǔ)結(jié)構(gòu)中效率高。21. 隊(duì)列是一種插入與刪除操作分別在表的兩段進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。22. 順序表中邏輯上相鄰的元素，物理上一定鄰接。 23. 順序表中所有結(jié)點(diǎn)的類型必須相同。 24. 由于不需預(yù)先分配空間，線性鏈表的結(jié)點(diǎn)結(jié)構(gòu)可以不相同。 25. 隊(duì)列是一種先進(jìn)后出的線性結(jié)構(gòu)。26. 隊(duì)列邏輯上是一個(gè)下端和上端既能增加又能減少的線性表。 27. 棧是一種先進(jìn)后出的線性結(jié)構(gòu)。 28. 循環(huán)隊(duì)列通常用指針來實(shí)現(xiàn)隊(duì)列的首尾相接。 29. 串是一種數(shù)據(jù)對(duì)象和操作都特殊的線性表。 30. 矩陣壓縮存儲(chǔ)的目的是為了節(jié)省運(yùn)算時(shí)間。 31. 廣義表的節(jié)點(diǎn)元素的類

16、型必須相同。 32. 廣義表是線性表的一種擴(kuò)展。 33. 一個(gè)廣義表的表尾總是一個(gè)廣義表。 34. 如果兩個(gè)含有相同的字符，則說他們相等。35. 空串與空格串是相同的。36. 所謂取廣義表的表尾就是返回廣義表中最后一個(gè)元素。應(yīng)用題1. 設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)椋篈，B，C，D，E，用I表示進(jìn)棧操作，O表示出棧操作，寫出下列出棧的操作序列。（1）C，B，A，D，E（2）A，C，B，E，D參考答案：（1）IIIOOOIOIO（2）IOIIOOIIOO2. 在雙鏈表中，刪除指針變量p所指結(jié)點(diǎn)，請(qǐng)按順序?qū)懗霰匾牟僮鞑襟E。參考答案：p->front->rear=p->rear;p

17、->rear->front=p->front;3. 在雙向鏈表中，要在指針變量q所指結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)p，請(qǐng)按順序?qū)懗霰匾乃惴ú襟E。 (設(shè)：P所指結(jié)點(diǎn)不是鏈表的首尾結(jié)點(diǎn)，q是與p同類型的指針變量)參考答案：p->front=q;p->rear=q->rear;q->rear->front=p;q->rear=p;4. 求后綴表達(dá)式。（1） ABC/D（2） -A+B*C+D/E（3） A*(B+C)*D-E（4） (A+B)*C-E/(F+G/H)-D（5） 8/(5+2)-6參考答案: （1）A B C D / （2）A B C *

18、 + D E / +（3）A B C + * D * E -（4）A B + C * E F G H / + / - D -（5）8 5 2 + / 6 -5. 一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來，填空構(gòu)造該二叉樹。（注意用大寫字符按位置填寫，不要加其他符號(hào)）先序：A（1）CD（2）F（3）H Z（4）K中序：（5）B E D F A（6）J K Z G后序：C（7）F（8）B（9）J Z H G（10）B E G J C H E D K A6. 根據(jù)下圖所示，分別求二叉樹的先序遍歷次序（1），中序遍歷次序（2），后序遍歷次序（3）。（注意次序結(jié)點(diǎn)間不要加空格或標(biāo)

19、點(diǎn)符號(hào)，例ABCDE即可）7.參考答案： 先序：ABDCGKHTY 中序：BCGDAHYTK 后序：GCDBYTHKA8. 某通信系統(tǒng)中只可能有A、B、C、D、E、F、G、H、K 9種字符，其出現(xiàn)的概率分別為0.03,0.06，0.04,0.05,0.1,0.18,0.22,0.12,0.2，試為這9個(gè)字符設(shè)置哈夫曼編碼，按下表對(duì)應(yīng)序號(hào)填空，并計(jì)算出帶權(quán)路徑長(zhǎng)度WPL=（10）（注意構(gòu)造哈夫曼樹時(shí)要求左小右大，前小后大，編碼時(shí)用左0右1編碼）字符ABCDEFGHK頻率0.030.060.040.050.10.180.220.120.2 編碼 11000 1001 11001 1000 1101

20、 111 01 101 00 WPL=2.939. 通信電文由A、B、C、D、E、F、G、H、K 9種字符組成，其出現(xiàn)的概率如下表所示，試為這9個(gè)字符設(shè)置哈夫曼編碼，按下表對(duì)應(yīng)序號(hào)填空，并計(jì)算出帶權(quán)路徑長(zhǎng)度WPL=（10）（注意構(gòu)造哈夫曼樹時(shí)要求左小右大，前小后大，編碼時(shí)用左0右1編碼）字符ABCDEFGHK頻率4311161223157 編碼 00011 11 001 1010 100 01 00010 0000 1011 WPL=27410. 求下圖頂點(diǎn)1到其余頂點(diǎn)的最短路徑，按要求填表。（注意用頂點(diǎn)大寫字母V+序號(hào)表示，路徑用頂點(diǎn)序列構(gòu)成，如填寫V1V3V5等即可，不用分隔。其他填寫方式

21、均不得分）源點(diǎn)終點(diǎn)路徑最小值V1V2V1V3V1V4V1V5V1V6V1V7V1V8V1V9V1V1011. 求下圖頂點(diǎn)1到其余頂點(diǎn)的最短路徑，按要求填表。（注意用頂點(diǎn)大寫字母V+序號(hào)表示，路徑用頂點(diǎn)序列構(gòu)成，如填寫V1V3V5等即可，不用分隔。其他填寫方式均不得分）源點(diǎn)終點(diǎn)路徑最小值V1V2V1V3V1V4V1V5V1V6V1V7V1V8V1V9V1V1012. 已知圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖，試求從1頂點(diǎn)出發(fā)求深度優(yōu)先遍歷次序（ ）及深度優(yōu)先遍歷生成樹（ ）和廣度優(yōu)先遍歷次序（ ）以及廣度優(yōu)先遍歷生成樹（ ）。24312124553312345（注意次序用頂點(diǎn)序號(hào)表示，用英文逗號(hào)分隔，如填寫

22、1,2,3,4,5即可。生成樹用序偶表示，如填寫<1,5><2,3><3,6>等。次序必須按遍歷生成次序依次填寫。其它填寫方式均不得分）13. 已知圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖，試求從頂點(diǎn)1出發(fā)求深度優(yōu)先遍歷次序（ ）及深度優(yōu)先遍歷生成樹（ ）和廣度優(yōu)先遍歷次序（ ）及廣度優(yōu)先遍歷生成樹（ ）（注意次序用頂點(diǎn)序號(hào)表示，用英文逗號(hào)隔開，如填寫1,2,3,4,5即可。生成樹用序偶表示，如填寫<1,5><2,3><3,6>等。次序必須按照遍歷生成次序依次填寫。其它填寫方式均不得分） 14. 用迪杰斯特拉算法求下圖頂點(diǎn)1到其余各頂點(diǎn)的

23、最短路徑，按要求填表。（注意用頂點(diǎn)大寫字母V+序號(hào)表示，路徑用頂點(diǎn)序列構(gòu)成，如填寫V1V3V5等即可，不用分割。其它填寫方式均不得分）源點(diǎn)終點(diǎn)路徑最小值V1V2V1V3V1V4V1V5V1V6V1V7V1V8V1V9V1V10算法填空1. 下面程序是把兩個(gè)串s1和s2首尾相連的程序，即：r1=r1+r2typedef structchar vecMAXLEN;/定義合并后串的最大長(zhǎng)度int len;/len為串的長(zhǎng)度Str;void ConCatStr(Str *r1, Str *r2) /字符串連接函數(shù)int i;cout<<r1->vec<vec;if(r1->

24、;len+r2->len _ (1)_ )cout<<"兩個(gè)串太長(zhǎng)，溢出！"elsefor(i=0;i< _ (2)_ ;i+)/把r2連接到r1r1->vec_ (3)_ =r2->veci;r1->vecr1->len+i= (4) ; /添上字符串結(jié)束標(biāo)志r1->len= _(5) ;/修改新串長(zhǎng)度MAXLEN,r2->len,r1->len+i,'0',r1->len+r2->len2. 下列算法的功能是遞歸方法實(shí)現(xiàn)快速排序。void Quick_Sort(DataType

25、 R,int s,int t)/對(duì)順序表RsRt作快速排序if (_(1)_) i=Partition(R,s,t); /算法Partition(R,s,t)功能為將表RsRt一分為二，返回值為分界點(diǎn)Quick_Sort(R,s,_(2)_); Quick_Sort(R,i+1,_(3)_); void Quick(DataType R,int n)Quick_Sort(R,1,n);(1)s<t (2)i-1 (3)t1.下面程序是把兩個(gè)串r1和r2首尾相連的程序，即：r1=r1+r2，閱讀程序并填空。typedef struct char vecMAXLEN; /定義串的最大長(zhǎng)度int len;/len為串的長(zhǎng)度Str;void ConCatStr(Str *r1, Str *r2) /字符串連接函數(shù)int i;if(r1->len+r2->len _ (1)_ )cout<<"兩個(gè)串太長(zhǎng)，溢出！"elsefor(i=0;i< _ (2)_ ;i+) /把r2連接到r1r1->vec_ (3)_ =r2->veci;r1->vecr1->len+i= (4) ; /添上字符串結(jié)束標(biāo)志r1->le