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

1、選擇題1. 在數(shù)據(jù)結(jié)構(gòu)中，邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）A. 動態(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. 在一個單鏈表中，若刪除p所指結(jié)點的后繼結(jié)點，則執(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é)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為（ ）。A. 30B. 31C. 29D.

2、154. 已知二叉樹中有兩個孩子的結(jié)點數(shù)為18，僅有一個孩子的結(jié)點數(shù)為30，則總節(jié)點數(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個序列中，符合深度優(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個B. 4個C. 3個D. 2個6. 有一個有序表1,3,5,7,8,10,15,17,19,30,41,50,70，當(dāng)二分查找

3、值為19的結(jié)點時，（ ）次比較后查找成功。A. 2B. 3C. 4D. 97. 下列不是算法的特性的是（ ）。A. 有窮性 B. 確定性C. 可能性 D. 輸入和輸出特性8. 線性表若采用鏈?zhǔn)浇Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址( )。A. 一定是不連續(xù)的 B. 連續(xù)不連續(xù)都可以C. 必須是連續(xù)的 D. 部分地址必須是連續(xù)的9. 在一個單鏈表中，若刪除p所指結(jié)點的后續(xù)結(jié)點，則執(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. 一個棧的入棧序列是a,b,c,d,e,則棧的不可能輸出序列是( )。A. dceab B. abcde C. edcba D. decba11. 限定線性表有（ ）。A.棧 B.隊列 C.樹 D.A和B12. 進行入隊運算時，必須先判斷隊列是否（ ）。A. 空 B. 滿 C. 下溢 D. 上溢13. 進行出棧運算時，必須先判斷棧是否（ ）。A. 空 B. 滿 C. 下溢 D. 上溢14. 判定一個棧ST(棧的存儲空間大小為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ù)元素是一個字符 B. 數(shù)據(jù)元素可以是多個字符C. 可以順序存儲 D. 可以鏈?zhǔn)酱鎯?17. 若串S=”software”,則其子串的數(shù)目是( )。A. 8 B. 7 C. 6 D. 918. 兩個字符串相等的充分必要條件是（ ）。A 、兩個串的長度相等 B 、兩個串包含的字符相等C 、兩個串的長度相等，并且兩個串包含的字符相等。 D、 兩

6、個串的長度相等，并且對應(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)中，每一個結(jié)點都可以有（ ）個孩子結(jié)點。A. 2 B. 1 C. 0 D. 任意多23. 關(guān)鍵路徑是時間節(jié)點網(wǎng)絡(luò)中（ ）。A. 從源點到匯點的最長路徑 B. 從源點到匯點的最短路徑C. 最長回

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

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

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

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

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

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

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

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

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

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

17、->rear->front=p->front;3. 在雙向鏈表中，要在指針變量q所指結(jié)點之后插入一個新結(jié)點p，請按順序?qū)懗霰匾乃惴ú襟E。 (設(shè)：P所指結(jié)點不是鏈表的首尾結(jié)點，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)造該二叉樹。（注意用大寫字符按位置填寫，不要加其他符號）先序：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é)點間不要加空格或標(biāo)

19、點符號，例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個字符設(shè)置哈夫曼編碼，按下表對應(yīng)序號填空，并計算出帶權(quán)路徑長度WPL=（10）（注意構(gòu)造哈夫曼樹時要求左小右大，前小后大，編碼時用左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個字符設(shè)置哈夫曼編碼，按下表對應(yīng)序號填空，并計算出帶權(quán)路徑長度WPL=（10）（注意構(gòu)造哈夫曼樹時要求左小右大，前小后大，編碼時用左0右1編碼）字符ABCDEFGHK頻率4311161223157 編碼 00011 11 001 1010 100 01 00010 0000 1011 WPL=27410. 求下圖頂點1到其余頂點的最短路徑，按要求填表。（注意用頂點大寫字母V+序號表示，路徑用頂點序列構(gòu)成，如填寫V1V3V5等即可，不用分隔。其他填寫方式

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

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

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

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

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