西北民族大學數(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. 154. 已知二叉樹中有兩個孩子的結(jié)點數(shù)為18，僅有一個孩子的結(jié)點數(shù)為30，則總節(jié)點數(shù)為

2、（ ）。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，當二分查找值為19的結(jié)點時，（ ）次比較后查找成功。A. 2B. 3C. 4D. 97. 下列不是

3、算法的特性的是（ ）。A. 有窮性 B. 確定性C. 可能性 D. 輸入和輸出特性8. 線性表若采用鏈式結(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. p=p-next-next10. 一個棧的入棧序列是a,b,c,d,e,則棧的不可能輸出序列是( )。A. dceab B. abcde C. ed

4、cba 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 D. ST-top=M15. 遞歸函數(shù)f(n)=f(n-1)+n(n1)的遞歸體是( )。A. f(1)=0 B. f(0)=1C. f(n)=f(n-1)+n D. f(n)=n16. 串

5、是一種特殊的線性表，其特殊性體現(xiàn)在( )。A. 數(shù)據(jù)元素是一個字符 B. 數(shù)據(jù)元素可以是多個字符C. 可以順序存儲 D. 可以鏈式存儲 17. 若串S=”software”,則其子串的數(shù)目是( )。A. 8 B. 7 C. 6 D. 918. 兩個字符串相等的充分必要條件是（ ）。A 、兩個串的長度相等 B 、兩個串包含的字符相等C 、兩個串的長度相等，并且兩個串包含的字符相等。 D、 兩個串的長度相等，并且對應(yīng)位置上的字符相等。19. 已知廣義表L=(a,(b,c),其表頭是( )。A. a B. b C. (a,b) D. (c,d)20. 廣義表(a,b),c,d)的表尾是( )。A.

6、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. 最長回路 D. 最短回路24. 設(shè)高度為15的二叉樹上只有度為0和1的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為（ ）。E. 30F. 31G. 29H. 1525. 已知二叉樹中有兩個孩子的結(jié)點數(shù)為18，僅有一個孩

7、子的結(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)，預算結(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. 當線性表的元素綜述總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)該采用（ ）存儲結(jié)構(gòu)4. 對于雙向鏈表，刪除一個存在的結(jié)點需修改的指針為（ ）個。 25. （ ）是限定僅在表尾進行插入或刪除操作的線性表。棧

8、 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é)果是（ ）。BCDEFEF8. 空格串是指由（ ）字符所組成的字符串。 空格9. 二維數(shù)組Mij的每個元素占4個存儲單元，行下表i的范圍從0到4，列下表j的范圍從0到6，M按列存儲時M15元素的起始地址與M按

9、行存儲時元素（ ）的起始地址相同。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. 深度為4的二叉樹至多有（ ）個結(jié)點。1515. 將一棵有50個結(jié)點的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1，則編號16. 二叉樹的第9層至多有（ ）個節(jié)點。25617.

10、深度為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. 數(shù)據(jù)的邏輯結(jié)構(gòu)可形式地用一個二元組S(D，R)來表示，其中D是_，R是_。24. 所有插入和刪除都在表的一端進行的線性表稱為 。25. 插入和刪除分別在表的兩端進行的線性表稱為 。26. 棧是一種 受限的

11、線性表。27. 當棧中元素為n個，作進棧運算時發(fā)生上溢，則說明該棧的最大容量為 ，設(shè)元素占1個空間容量。28. 串的兩種基本存儲方式是 和 。29. 串S=”hell o”的長度是_。30. 串S=”worker”的子串數(shù)目是_。31. 空串是指數(shù)據(jù)元素個數(shù)為_的串。32. 已知數(shù)組A0909的每個元素占5個存儲單元，將其按行存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A68的地址為 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的深度是 ,表頭

12、為 ，表尾是 。36. 空格串是指由_符所組成的字符串。37. 數(shù)據(jù)結(jié)構(gòu)包括_三個方面。38. 當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)該采用_存儲結(jié)構(gòu)39. 對于雙向鏈表，刪除一個存在的結(jié)點需修改的指針為_個。 240. _是限定僅在表尾進行插入或刪除操作的線性表。 判斷題1. 線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。2. 鏈表是采用鏈式存儲結(jié)構(gòu)的線性表，進行插入、刪除操作時，在鏈表中比在順序存儲結(jié)構(gòu)中效率高。3. 隊列是一種插入與刪除操作分別在表的兩段進行的線性表，是一種先進后出型結(jié)構(gòu)。4. 隊列邏輯上是一個上端

13、和下端既能增加又能減少的線性表。5. 如果兩個含有相同的字符，則說他們相等。6. 空串與空格串是相同的。7. 所謂取廣義表的表尾就是返回廣義表中最后一個元素。8. 由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹就是一種特殊的樹。9. 二叉樹中的葉子結(jié)點就是二叉樹中沒有左右子樹的結(jié)點，除了根結(jié)點外。10. 二叉樹的中序遍歷中，任意一個結(jié)點均處在其子女結(jié)點的后面。11. 森林的先序遍歷次序與其轉(zhuǎn)換得到的二叉樹的中序遍歷次序相同。12. 已知一個森林的先序遍歷和中序遍歷，一定能構(gòu)造出該森林。 A13. 有向圖用鄰接矩陣表示后，頂點i的出度等于第i行中非0且非的元素個數(shù)。14. 在一個有向圖中，所有頂點

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. 鏈表是采用鏈式存儲結(jié)構(gòu)的線性表，進行插入、刪除操作時，在鏈表中比在順序存儲結(jié)構(gòu)中效率高。21. 隊列是一種插入與刪除操作分別在表的兩段進行的線性表，是一種先進后出型結(jié)構(gòu)。22. 順序表中邏輯上相鄰的元素，物理上一定鄰接。 23. 順序表中所有結(jié)點

15、的類型必須相同。 24. 由于不需預先分配空間，線性鏈表的結(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é)點元素的類型必須相同。 32. 廣義表是線性表的一種擴展。 33. 一個廣義表的表尾總是一個廣義表。 34. 如果兩個含有相同的字符，則說他們相等。35. 空串與空格串是相同的。36. 所謂取廣義表的表尾就是返回廣義表

16、中最后一個元素。應(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-rear-front=p-front;3. 在雙向鏈表中，要在指針變量q所指結(jié)點之后插入一個新結(jié)點p，請按順序?qū)懗霰匾乃惴ú襟E。 (設(shè)：P所指結(jié)點不是鏈表的首尾結(jié)點，q是與p同類型的指針變量)參考答案：p-front=q;p-r

17、ear=q-rear;q-rear-front=p;q-rear=p;4. 求后綴表達式。（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 * + 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）

18、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é)點間不要加空格或標點符號，例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個

19、字符設(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 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編碼）字符ABCDEF

20、GHK頻率4311161223157 編碼 00011 11 001 1010 100 01 00010 0000 1011 WPL=27410. 求下圖頂點1到其余頂點的最短路徑，按要求填表。（注意用頂點大寫字母V+序號表示，路徑用頂點序列構(gòu)成，如填寫V1V3V5等即可，不用分隔。其他填寫方式均不得分）源點終點路徑最小值V1V2V1V3V1V4V1V5V1V6V1V7V1V8V1V9V1V1011. 求下圖頂點1到其余頂點的最短路徑，按要求填表。（注意用頂點大寫字母V+序號表示，路徑用頂點序列構(gòu)成，如填寫V1V3V5等即可，不用分隔。其他填寫方式均不得分）源點終點路徑最小值V1V2V1V3V

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

22、填寫1,2,3,4,5即可。生成樹用序偶表示，如填寫等。次序必須按照遍歷生成次序依次填寫。其它填寫方式均不得分） 14. 用迪杰斯特拉算法求下圖頂點1到其余各頂點的最短路徑，按要求填表。（注意用頂點大寫字母V+序號表示，路徑用頂點序列構(gòu)成，如填寫V1V3V5等即可，不用分割。其它填寫方式均不得分）源點終點路徑最小值V1V2V1V3V1V4V1V5V1V6V1V7V1V8V1V9V1V10算法填空1. 下面程序是把兩個串s1和s2首尾相連的程序，即：r1=r1+r2typedef structchar vecMAXLEN;/定義合并后串的最大長度int len;/len為串的長度Str;void

23、 ConCatStr(Str *r1, Str *r2) /字符串連接函數(shù)int i;coutveclen+r2-len _ (1)_ )cout兩個串太長，溢出！;elsefor(i=0;ivec_ (3)_ =r2-veci;r1-vecr1-len+i= (4) ; /添上字符串結(jié)束標志r1-len= _(5) ;/修改新串長度MAXLEN,r2-len,r1-len+i,0,r1-len+r2-len2. 下列算法的功能是遞歸方法實現(xiàn)快速排序。void Quick_Sort(DataType 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)slen+r2-len _ (1)_ )cout兩個串太長，溢出！;elsefor(i=0;ivec_ (3)_ =r2-veci