數(shù)據(jù)結(jié)構(gòu)試題(含答案)

1、數(shù)據(jù)結(jié)構(gòu)試題一、 單選題1、 在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為 （C ） A 內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu) B 靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu) C 線性結(jié)構(gòu)與非線性結(jié)構(gòu) D 緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)。2、采用線性鏈表表示一個(gè)向量時(shí)，要求占用的存儲(chǔ)空間地址（D ） A 必須是連續(xù)的 B 部分地址必須是連續(xù)的 C 一定是不連續(xù)的 D 可連續(xù)可不連續(xù)3、采用順序搜索方法查找長(zhǎng)度為n的順序表時(shí)，搜索成功的平均搜索長(zhǎng)度為（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/24、在一個(gè)單鏈表中，若q結(jié)點(diǎn)是p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q與p之間插入結(jié)點(diǎn)s，則執(zhí)行（ D ）。A slink = plink; pli

2、nk = s; B plink = s; slink = q;C plink = slink; slink = p; D qlink = s; slink = p;5、如果想在4092個(gè)數(shù)據(jù)中只需要選擇其中最小的5個(gè)，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 錦標(biāo)賽排序 D 快速排序 6、設(shè)有兩個(gè)串t和p，求p在t中首次出現(xiàn)的位置的運(yùn)算叫做（ B ）。 A 求子串 B 模式匹配 C 串替換 D 串連接7、在數(shù)組A中，每一個(gè)數(shù)組元素Aij占用3個(gè)存儲(chǔ)字，行下標(biāo)i從1到8，列下標(biāo)j從1到10。所有數(shù)組元素相繼存放于一個(gè)連續(xù)的存儲(chǔ)空間中，則存放該數(shù)組至少需要的存儲(chǔ)字?jǐn)?shù)是（ C ）。A

3、80 B 100 C 240 D 2708、將一個(gè)遞歸算法改為對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用（ A ）。A 棧 B 隊(duì)列 C 循環(huán)隊(duì)列 D 優(yōu)先隊(duì)列9、一個(gè)隊(duì)列的進(jìn)隊(duì)列順序是1, 2, 3, 4，則出隊(duì)列順序?yàn)椋?C ）。10、在循環(huán)隊(duì)列中用數(shù)組A0.m-1 存放隊(duì)列元素，其隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % mC ( front - rear + m) % m D ( rear - front + m) % m11、一個(gè)數(shù)組元素ai與（ A ）的表

4、示等價(jià)。A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形參直接訪問(wèn)實(shí)參，則應(yīng)把形參變量說(shuō)明為（ B ）參數(shù)。A 指針 B 引用 C 值 D 變量13、下面程序段的時(shí)間復(fù)雜度為（ C ） for (int i=0;i<m;i+) for (int j=0;j<n;j+) aij=i*j;A O(m2) B O(n2) C O(m*n) D O(m+n)14、下面程序段的時(shí)間復(fù)雜度為（ B ） int f(unsigned int n) if(n= =0 | n= =1) return 1; else return n*f(n-1); A O(1)

5、B O(n) C O(n2) D O(n !)15、線性表若是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址( D )。A 必須是連續(xù)的B   部分地址必須是連續(xù)的C 一定是不連續(xù)的D   連續(xù)或不連續(xù)都可以16、數(shù)據(jù)結(jié)構(gòu)的定義為(D，S)，其中D是( B )的集合。A 算法 B數(shù)據(jù)元素 C 數(shù)據(jù)操作 D 邏輯結(jié)構(gòu)17、算法分析的目的是( A )。A    找出數(shù)據(jù)結(jié)構(gòu)的合理性B    研究算法中輸入和輸出的關(guān)系C    分析算法的效率以求改進(jìn)D   分析算法的易

6、懂性和文檔性18、在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行( B )。A s->link=p;p->link=s;B s->link=p->link;p->link=s;C s->link=p->link;p=s;D p->link=s;s->link=p;19、設(shè)單鏈表中結(jié)點(diǎn)結(jié)構(gòu)為(data,link).已知指針q所指結(jié)點(diǎn)是指針p所指結(jié)點(diǎn)的直接前驅(qū)，若在*q 與*p之間插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個(gè)操作（ B ）A s->link=p->link; p->link=s; B q

7、->link=s; s->link=pC p->link=s->link;s->link=p; D p->link=s; s->link=q;20、設(shè)單鏈表中結(jié)點(diǎn)結(jié)構(gòu)為(data,link).若想摘除結(jié)點(diǎn)*p的直接后繼，則應(yīng)執(zhí)行下列哪一個(gè)操作（ A ）A p->link=p->link->link; B p=p->link; p->link=p->link->link;C p->link=p->link; D p=p->link->link;21、設(shè)單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,l

8、ink）,且rear是指向非空的帶表頭結(jié)點(diǎn)的單循環(huán)鏈表的尾結(jié)點(diǎn)的指針。若想刪除鏈表第一個(gè)結(jié)點(diǎn)，則應(yīng)執(zhí)行下列哪一個(gè)操作（ D ）A s=rear; rear=rear->link; delete s; B rear=rear->link; delete rear; C rear=rear->link->link; delete rear; D s=rear->link->link; rear->link->link=s->link; delete s;22、設(shè)單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link）,且first為指向鏈表表頭的指針，c

9、urrent為鏈表當(dāng)前指針，在循環(huán)鏈表中檢測(cè)current是否達(dá)到鏈表表尾的語(yǔ)句是( D )。A current->link =null B first->link=currentC first=current D current->link=first23、一個(gè)棧的入棧序列為a，b，c，則出棧序列不可能的是( C )。A     c,b,a B b,a,c C c,a,b D a,c,b24、棧的數(shù)組表示中，top為棧頂指針，?？盏臈l件是( A )。A    top=0 B top=maxSize C 

10、top=maxSize D top=-125、棧和隊(duì)列的共同特點(diǎn)是( C )。A     都是先進(jìn)后出 B 都是先進(jìn)先出C    只允許在端點(diǎn)處插入和刪除 D 沒(méi)有共同點(diǎn)26、假定一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e為f和r ,則判斷隊(duì)空的條件為( D ).A f+1= =r B r+1= =f C f= =0 D f= =r27、當(dāng)利用大小為n 的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為（ B ）A n-2 B n-1 C n D n+128、當(dāng)利用大小為n 的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top= =n 表示?？?，則向這個(gè)棧

11、插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行（ ）語(yǔ)句修改top指針。A top+; B top-; C top=0; D top;29、設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為（data, link）,且top是指向棧頂?shù)闹羔槨Ｈ粝胝準(zhǔn)綏５臈ｍ斀Y(jié)點(diǎn)，并將被摘除結(jié)點(diǎn)的值保存到x中，則應(yīng)執(zhí)行下列（ A ）操作。A x=top->data; top=top->link; B top=top->link; x=top->data; C x=top; top=top->link; D x=top->data;30、設(shè)循環(huán)隊(duì)列的結(jié)構(gòu)是： const int Maxsize=100; typedef

12、int Data Type; typedef struct Data Type dataMaxsize; Int front, rear; Queue;若有一個(gè)Queue類型的隊(duì)列Q，試問(wèn)判斷隊(duì)列滿的條件應(yīng)是下列哪一個(gè)語(yǔ)句（ D ）A Q.front= = Q.rear; B Q.front - Q.rear= = Maxsize; C Q.front + Q.rear= = Maxsize; D Q.front= = (Q.rear+1)% Maxsize;31、設(shè)有一個(gè)遞歸算法如下：int fact (int n ) if (n<=0) return 1;else return n*

13、fact(n-1);下面正確的敘述是（ B ）A 計(jì)算fact(n) 需要執(zhí)行n次遞歸 B fact(7)=5040 C 此遞歸算法最多只能計(jì)算到fact(8) D 以上結(jié)論都不對(duì)32、設(shè)有一個(gè)遞歸算法如下int x (int n) if (n<=3) return 1;else return x(n-2)+x(n-4)+1;試問(wèn)計(jì)算 x(x(8)時(shí)需要計(jì)算（ D ）次x函數(shù)。A 8 次 B 9次 C 16次 D 18次33、設(shè)有廣義表D(a,b,D),其長(zhǎng)度為（ B ），深度為（ A ）A B 3 C 2 D 534、廣義表A(a),則表尾為（ C ）A a B ( ) ) C 空表

14、D （a）35、下列廣義表是線性表的有（ C ）A E（a,(b,c)） B E(a,E) C E (a,b) D E(a,L( ) )36、遞歸表、再入表、純表、線性表之間的關(guān)系為（ C ）A 再入表>遞歸表>純表>線性表 B 遞歸表>線性表>再入表>純表 C 遞歸表>再入表>純表>線性表 D遞歸表>再入表>線性表>純表37、某二叉樹(shù)的前序和后序序列正好相反，則該二叉樹(shù)一定是（B）的二叉樹(shù)。A 空或只有一個(gè)結(jié)點(diǎn) B 高度等于其結(jié)點(diǎn)數(shù) C 任一結(jié)點(diǎn)無(wú)左孩子 D 任一結(jié)點(diǎn)無(wú)右孩子38、對(duì)于任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為

15、n0，度為2的結(jié)點(diǎn)為n2.,則( A )A n0= n2+1 B n2= n0+1 C n0= 2n2+1 D n2=2n0+1 39、 由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（B ）A 24 B 73 C 48 D 5340、已知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)需占m個(gè)存儲(chǔ)單元，若第一個(gè)結(jié)點(diǎn)的地址為da1,則第I 個(gè)結(jié)點(diǎn)的地址為（A）。A da1+(I-1)*m B da1+I*m C da1-I*m D da1+(I+1)*m41、34 具有35個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為( A )A 5 B 6 C 7 D 842、對(duì)線性表進(jìn)行折半搜索時(shí)，要求線性表

16、必須（ C ）A 以鏈接方式存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵碼有序排列 B 以數(shù)組方式存儲(chǔ) C 以數(shù)組方式存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵碼有序排列 D以鏈接方式存儲(chǔ)43、順序搜索算法適合于存儲(chǔ)結(jié)構(gòu)為（ B ）的線性表。A 散列存儲(chǔ) B 順序存儲(chǔ)或鏈接存儲(chǔ) C 壓縮存儲(chǔ) D 索引存儲(chǔ)44、采用折半搜索算法搜索長(zhǎng)度為n的有序表時(shí)，元素的平均搜索長(zhǎng)度為（ C ）A O（n2） B O（n log2n） C O（log2n） D O（n）45、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，進(jìn)行拓?fù)渑判驎r(shí)，總的時(shí)間為( A )A n B n+1 C n-1 D n+e46、判斷一個(gè)有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ㄍ猓€可以利用（

17、C ）。A 求關(guān)鍵路徑的方法 B 求最短路徑的Dijkstra方法 C 深度優(yōu)先遍歷算法 D 廣度優(yōu)先遍歷算法47、在10階B-樹(shù)中根結(jié)點(diǎn)所包含的關(guān)鍵碼個(gè)數(shù)最多為（C ），最少為( A )A 1 B 2 C 9 D 1048、對(duì)包含n 個(gè)元素的散列表進(jìn)行搜索，平均搜索長(zhǎng)度為（ C ）A O（log2n） B O（n）C 不直接依賴于n D 上述都不對(duì)二、 填空題（）1、   數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu) 四種 2、   數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu) 四種3、一種抽象

18、數(shù)據(jù)類型包括（數(shù)據(jù) ）和（操作 ）兩個(gè)部分。4、 設(shè)有兩個(gè)串p和q，求p在q中首次出現(xiàn)的位置的運(yùn)算稱為（模式匹配） 5、    棧、隊(duì)列邏輯上都是（線性存儲(chǔ)）結(jié)構(gòu)。6、 線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是（一對(duì)一）的，圖中的數(shù)據(jù)元素之間的關(guān)系是（多對(duì)多）的，樹(shù)形結(jié)構(gòu)中數(shù)據(jù)元素間的關(guān)系是（一對(duì)多）的。7、 棧中存取數(shù)據(jù)的原則（后進(jìn)先出），隊(duì)列中存取數(shù)據(jù)的原則（先進(jìn)先出）8、 串是由（零個(gè)或多個(gè)）字符組成的序列。（長(zhǎng)度為零的串）稱為空串，（由一個(gè)或多個(gè)空格組成的串）稱為空格串。9、 設(shè)目標(biāo)串T=”abccdcdccbaa”,模式P=”cdcc”則第（6）次匹配成功。10、一維數(shù)組的

19、邏輯結(jié)構(gòu)是（線性結(jié)構(gòu)），存儲(chǔ)結(jié)構(gòu)是（順序存儲(chǔ)表示）。對(duì)于二維數(shù)組，有（行優(yōu)先順序）和（列優(yōu)先順序）兩種不同的存儲(chǔ)方式，對(duì)于一個(gè)二維數(shù)組Amn,若采用按行優(yōu)先存放的方式，則任一數(shù)組元素Aij相對(duì)于A00的地址為（ n*i+j）。11、向一個(gè)順序棧插入一個(gè)元素時(shí)，首先使（ 棧頂指針 ）后移一個(gè)位置，然后把待插入元素（ 寫 ）到這個(gè)位置上。從一個(gè)順序棧刪除元素時(shí)，需要前移一位（棧頂指針）。12、在一個(gè)循環(huán)隊(duì)列Q中，判斷隊(duì)空的條件為（Q.front= =Q.rear）, 判斷隊(duì)滿的條件為（ (Q.rear+1)%MaxSize= =q.front ）13、對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，該樹(shù)中所有結(jié)點(diǎn)的度數(shù)

20、之和為（ n-1 ）。14、一棵高度為5的滿二叉樹(shù)中的結(jié)點(diǎn)數(shù)為（ 63 ）個(gè)，一棵高度為3滿四叉樹(shù)中的結(jié)點(diǎn)數(shù)為（ 85 ）個(gè)。15、若對(duì)一棵二叉樹(shù)從0開(kāi)始進(jìn)行結(jié)點(diǎn)編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到a0中，其余類推，則ai元素的左子女結(jié)點(diǎn)為（ 2*i+1），右子女結(jié)點(diǎn)為（ 2*i+2 ），雙親結(jié)點(diǎn)（i>=1 ）為（(i-1)/2 ）.16、在一個(gè)最大堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的（最大值），在一個(gè)最小堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的（最小值）。17、已知具有n個(gè)元素的一維數(shù)組采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占k個(gè)存儲(chǔ)單元，第一個(gè)元素的地址為L(zhǎng)OC(a1)

21、，那么，LOC(ai)= LOC(a1)+(i-1)*k 。18、在霍夫曼編碼中，若編碼長(zhǎng)度只允許小于等于4,則除掉已對(duì)兩個(gè)字符編碼為0和10外，還可以最多對(duì)（ 4 ）個(gè)字符編碼。19、設(shè)高度為h的空二叉樹(shù)的高度為-1，只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的高度為0，若設(shè)二叉樹(shù)只有度為2上度為0的結(jié)點(diǎn)，則該二叉樹(shù)中所含結(jié)點(diǎn)至少有（2h+1）個(gè)。20、由一棵二叉樹(shù)的前序序列和（中序序列）可唯一確定這棵二叉樹(shù)。 21、以折半搜索方法搜索一個(gè)線性表時(shí)，此線性表必須是（順序）存儲(chǔ)的（有序）表。22、已知完全二叉樹(shù)的第8層有8個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)是（68）。若完全二叉樹(shù)的第7有10個(gè)葉子結(jié)點(diǎn)，則整個(gè)二叉樹(shù)的結(jié)點(diǎn)數(shù)最多

22、是（235）23、對(duì)于折半搜索所對(duì)應(yīng)的判定樹(shù)，它既是一棵（二叉搜索樹(shù)），又是一棵（理想平衡樹(shù)）。24、假定對(duì)長(zhǎng)度n=50的有序表進(jìn)行折半搜索，則對(duì)應(yīng)的判定樹(shù)高度為（），判定樹(shù)中前層的結(jié)點(diǎn)數(shù)為（），最后一層的結(jié)點(diǎn)數(shù)為（）。25、在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍。在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有（ n(n-1)/2 ）條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有（ n(n-1) ）條邊。26、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的連通圖，其生成樹(shù)中的頂點(diǎn)數(shù)和邊數(shù)分別為（n）和（n-1）。27、設(shè)線性表中元素的類型是實(shí)型，其首地址為1024，則線性表中第6個(gè)元素的存儲(chǔ)位置是(

23、 1044)。28、在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選擇（插入排序），若初始數(shù)據(jù)基本反序，則最好選擇（選擇排序）。29、算法是對(duì)特定問(wèn)題的求解步驟的一種描述，它是（指令）的有限序列，每一條（指令）表示一個(gè)或多個(gè)操作。30、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)肯e 條邊的無(wú)向圖，進(jìn)行拓樸排序時(shí)，總的進(jìn)間為（n）31、構(gòu)造哈希函數(shù)有三種方法，分別為(平方取中)法、(除留余數(shù))法、(折迭移位)法。32、處理沖突的三種方法，分別為(線性探測(cè))、（ 隨機(jī)探測(cè) ）、（ 鏈地址法）。33、對(duì)于含有n個(gè)頂點(diǎn)和e條邊的無(wú)向連通圖，利用普里姆算法產(chǎn)生的最小生成樹(shù)，其時(shí)間復(fù)雜度為（ （n2） ）、利用克魯斯卡爾算法產(chǎn)生的

24、最小生成樹(shù)，其時(shí)間復(fù)雜度為（elog2e） ）34、快速排序在平均情況下的時(shí)間復(fù)雜度為（nlog2n），在最壞情況下的時(shí)間復(fù)雜度為（n2）；快速排序在平均情況下的空間復(fù)雜度為（log2n），在最壞情況下的空間復(fù)雜度為（n）。35、假定一組記錄的排序碼為（，），對(duì)其進(jìn)行歸并排序的過(guò)程中，第二趟排序后的結(jié)果是（）36、假定一組記錄的排序碼為（，），對(duì)其進(jìn)行快速排序的第一次劃分的結(jié)果是（）。37、一個(gè)結(jié)點(diǎn)的子樹(shù)的（ 個(gè)數(shù) ）稱為該結(jié)點(diǎn)的度。度為（ 零 ）的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。度不為（ 零 ）的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。樹(shù)中各結(jié)點(diǎn)度的（ 最大值 ）稱為樹(shù)的度。38、設(shè)Ki=Kj (1<

25、=i<=n, 1<=j<=n,j<>i)且在排序前的序列中Ri領(lǐng)先于Rj (i<j),若排序后的序列中Ri仍領(lǐng)先于Rj，則這種排序方法是（穩(wěn)定的），反之是（不穩(wěn)定的）。40 、在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行調(diào)整運(yùn)算的時(shí)間復(fù)雜度為（log2n），整個(gè)排序過(guò)程的時(shí)間復(fù)雜度為（nlog2n）。41、在索引表中，每個(gè)索引項(xiàng)至少包含有（關(guān)鍵碼值）域和（子表地址）域這兩項(xiàng)。42、假定一個(gè)線性表為（”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”）,若按照字符串的第一個(gè)字母進(jìn)行劃分，使得同一個(gè)字母被劃分

26、在一個(gè)子表中，則得到的a,b,c三個(gè)子表的長(zhǎng)度分別為（），（），（）。43、對(duì)于包含個(gè)關(guān)鍵碼的階B-樹(shù)，其最小高度為（），最大高度為（）。44、從一棵B-樹(shù)刪除關(guān)鍵碼的過(guò)程，若最終引起樹(shù)根結(jié)點(diǎn)的合并，則新樹(shù)比原樹(shù)的高度（減）45、假定要對(duì)長(zhǎng)度n=100的線性表進(jìn)行散列存儲(chǔ)，并采用開(kāi)散列法處理沖突，則對(duì)于長(zhǎng)度m=20的散列表，每個(gè)散列地址的同義詞子表的長(zhǎng)度平均為（）。46、在散列存儲(chǔ)中，裝載因子又稱為裝載系數(shù)，若用m表示散列表的長(zhǎng)度，n表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則等于（n/m）。47、在有向圖的鄰接矩陣中，第i行中“1”的個(gè)數(shù)是第i個(gè)頂點(diǎn)的（出度），第i列中“1”的個(gè)數(shù)是第i個(gè)頂點(diǎn)的（入度）。

27、在無(wú)向圖的鄰接矩陣中，第i行（列）中“1”的個(gè)數(shù)是第i個(gè)頂點(diǎn)的（度），矩陣中“1”的個(gè)數(shù)的一半是圖中的（邊數(shù)）。48、在對(duì)m階B-樹(shù)中，每個(gè)非根結(jié)點(diǎn)的關(guān)鍵碼數(shù)最少為（m/2-1）個(gè)，最多為（m-1）個(gè)，其子樹(shù)棵數(shù)最少為（m/2），最多為（m）。三、 判斷題1、 數(shù)據(jù)元素是數(shù)據(jù)的最小單位（）。2、 數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的().3、 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體（）。4、 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)（）。5、 線性表的邏輯順序與物理順序總是一致的（）。6、 二維數(shù)組是其數(shù)組元素為線性表的線性表（

28、）。7、 每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運(yùn)算：插入、刪除、搜索（）。8、 非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接前驅(qū)元素。（ ）9、 空串與由空格組成的串沒(méi)有區(qū)別。（ ）10、 將T在S中首次出現(xiàn)的位置作為T在S中的位置的操作稱為串的模式匹配。（）11、 深度為h的非空二叉樹(shù)的第h層最多有2h-1個(gè)結(jié)點(diǎn)（ ）12、 完全二叉樹(shù)就是滿二叉樹(shù)。（）13、 已知一棵二叉樹(shù)的前序序列和中序序列可以唯一地構(gòu)造出該二叉樹(shù)。（ ）14、 帶權(quán)連通圖的最小生成樹(shù)的權(quán)值之和一定小于它的其它生成樹(shù)的權(quán)值之和。（）15、線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也相鄰。（）16、 若有一

29、個(gè)結(jié)點(diǎn)是二叉樹(shù)中某個(gè)子樹(shù)的中序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)，則它一定是該子樹(shù)的前序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)。（）17、 任一棵二叉搜索樹(shù)的平均搜索時(shí)間都小于用順序搜索法搜索同樣結(jié)點(diǎn)的順序表的平均搜索時(shí)間。（）18、最優(yōu)二叉搜索樹(shù)一定是平衡的二叉搜索樹(shù)。（）19、AOE網(wǎng)是一種帶權(quán)的無(wú)環(huán)連通圖。（ ）20、對(duì)于同一組待輸入的關(guān)鍵碼集合，雖然各關(guān)鍵碼的輸入次序不同，但得到的二叉搜索樹(shù)都是相同的（）。21、二叉排序樹(shù)可以是一棵空樹(shù)（）22、線性表中所有結(jié)點(diǎn)的類型必須相同。 （）23、n個(gè)結(jié)點(diǎn)的有向圖，若它有n(n1)條邊，則它一定是強(qiáng)連通的。（）24、任何無(wú)環(huán)的有向圖，其結(jié)點(diǎn)都可以排在一個(gè)拓?fù)湫蛄欣?/p>

30、。（ ）25、隊(duì)列邏輯上是一個(gè)下端口和上端能增加又能減少的線性表（ ）26、二叉樹(shù)是樹(shù)的一種特殊情況（ ）27、用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)（）。28、鄰接表只能用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無(wú)向圖的存儲(chǔ)都適用。（）29、連通分量是無(wú)向圖中的極小連通子圖。（）30、在網(wǎng)絡(luò)中一定只有一條關(guān)鍵路徑。（）31、關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間。（）32、平衡二叉樹(shù)的左右子樹(shù)深度之差的絕對(duì)值不超過(guò)1。（ ）33、快速排序是對(duì)起泡排序的一種改進(jìn)。()34、直接選擇排序穩(wěn)定。（）35、堆排序占用的輔助空間很

31、大。（）36、在散列法中采取開(kāi)散列法來(lái)解決沖突時(shí)，其裝載因子的取值一定在（，）之間。（）37、B-樹(shù)是一種動(dòng)態(tài)索引結(jié)構(gòu)，它既適用于隨機(jī)搜索，也適用于順序搜索。（）38、在散列法中，一個(gè)可用散列函數(shù)必須保證絕對(duì)不產(chǎn)生沖突。（）39、任何一個(gè)關(guān)鍵活動(dòng)延遲，那么整個(gè)工程將會(huì)延遲。（）40、任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成。（）四、運(yùn)算應(yīng)用題 1、在一個(gè)有n個(gè)元素的順序表的第i個(gè)元素（1 £ i £ n）之前插入一個(gè)新元素時(shí)，需要向后移動(dòng)多少個(gè)元素？答案：需要向后移動(dòng) n- i + 1個(gè)元素2、 當(dāng)一個(gè)棧的進(jìn)棧序列為1234567時(shí)，可能的出棧序列有多少種？645

32、7321是否是合理的出棧序列？答案：可能的出棧序列有種，6457321不是合理的出棧序列。3、 簡(jiǎn)單（直接）選擇排序是一種穩(wěn)定的排序方法嗎？試舉例說(shuō)明？答案：是不穩(wěn)定的排序方法。下面就是不穩(wěn)定的例子。只要能舉出反例即可。 275 275* 512 061 i = 1 061 275* 512 275 i = 2 061 275* 512 275 i = 3 061 275* 275 512 4、設(shè)有序順序表為 10, 20, 30, 40, 50, 60, 70 ，采用折半搜索時(shí)，搜索成功的平均搜索長(zhǎng)度是多少？答案：ASLsucc = (1*1 + 2*2 + 3*4 ) / 7 = 17 /

33、 75、 在結(jié)點(diǎn)個(gè)數(shù)為n(n>1)的各棵樹(shù)中，高度最小的樹(shù)的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？高度最大的樹(shù)的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？答案：結(jié)點(diǎn)個(gè)數(shù)為n時(shí)，高度最小的樹(shù)的高度為1，有2層；它有n-1個(gè)葉結(jié)點(diǎn)，1個(gè)分支結(jié)點(diǎn)；高度最大的樹(shù)的高度為n-1,有n層；它有1個(gè)葉結(jié)點(diǎn)，n-1個(gè)分支結(jié)點(diǎn)。6、 一棵高度為h的滿k叉樹(shù)有如下性質(zhì): 第h層上的結(jié)點(diǎn)都是葉結(jié)點(diǎn), 其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹(shù), 如果按層次自頂向下, 同一層自左向右, 順序從1開(kāi)始對(duì)全部結(jié)點(diǎn)進(jìn)行編號(hào), 試問(wèn)：(1) 各層的結(jié)點(diǎn)個(gè)數(shù)是多少?(2) 編號(hào)為i的結(jié)點(diǎn)的父結(jié)點(diǎn)(若存在)的編號(hào)是多少

34、?(3) 編號(hào)為i的結(jié)點(diǎn)的第m個(gè)孩子結(jié)點(diǎn)(若存在)的編號(hào)是多少?(4) 編號(hào)為i的結(jié)點(diǎn)有右兄弟的條件是什么? 其右兄弟結(jié)點(diǎn)的編號(hào)是多少?(5) 若結(jié)點(diǎn)個(gè)數(shù)為 n, 則高度h是n 的什么函數(shù)關(guān)系?答案：（1）各層的結(jié)點(diǎn)個(gè)數(shù)是ki (i=0,1,2,.,h)（2）編號(hào)為i的結(jié)點(diǎn)的父結(jié)點(diǎn)(若存在)的編號(hào)是 (i+k-2)/k（3）編號(hào)為i的結(jié)點(diǎn)的第m個(gè)孩子結(jié)點(diǎn)(若存在)的編號(hào)是(i-1)*k+m+1（4）當(dāng)(i-1)%k<>0時(shí)有右兄弟， 右兄弟的編號(hào)為 i+1（5）若結(jié)點(diǎn)個(gè)數(shù)為 n ，則高度h和n 的關(guān)系為：h=logk(n*(k-1)+1)-1 (n=0時(shí)h=-1)7、 寫出下列中綴

35、表達(dá)式的后綴形式：(1) A* - B + C(2) (A + B) * D + E / (F + A * D) + C(3) A && B| ! (E > F)注：按C+的優(yōu)先級(jí))(4) !(A && !( (B < C)|(C > D) ) )|(C < E) 答案：各中綴表達(dá)式的后綴形式如下： （1）AB-*C+(2)AB+D*EFAD*+/+C+ (3)AB&&EF>!|(4)ABC<CD>|!&&!CE<|8、 畫出下列廣義表的圖形表示和它們的存儲(chǔ)表示：(1) D(A(c)

36、, B(e), C(a, L(b, c, d)(2) J1(J2(J1, a, J3(J1), J3(J1) 答案：廣義表（1）的圖形表示為：廣義表（2）的圖形表示為：DABCDLceabcd J1J3J2a廣義表（1）的存儲(chǔ)表示為：0 A 1 C 0 B 1 e AB0 D 2 2 2 0 C 1 a 2 0 L 1 b 1 C 1 d CLD廣義表（2）的存儲(chǔ)表示為：0 J1 2 2 0 J2 2 1 a 2 0 J3 2 J3J2J19、題目：11、將下面的森林變換成二叉樹(shù)（7分）。ACDBFEKJGHIACDBFEKJGHI答案：10、將算術(shù)表達(dá)式 (a+b)+c*(d+e)+f)*(

37、g+h) 轉(zhuǎn)化為二叉樹(shù)。（7分）答案：*+f+*+cbahgde11、根據(jù)所給有向圖，寫出一個(gè)拓?fù)湫蛄?。?分）1325476答案：其中的一個(gè)拓?fù)湫蛄袨椋篤1，V2，V3，V4，V5，V6，V7 12、 將給定的圖簡(jiǎn)化為最小的生成樹(shù)，要求從頂點(diǎn)1出發(fā)。（7分）13254768515310122796 答案: 1325476515362713、某子系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其出現(xiàn)的概率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11試設(shè)計(jì)赫夫曼編碼。答案：為方便起見(jiàn)，設(shè)各種字符的權(quán)值w=5,29,7,8,14,23,3,11。因?yàn)閚=8，所以要構(gòu)造的

38、赫夫曼樹(shù)共有m=2n-1=2*8-1=15個(gè)結(jié)點(diǎn)。生成的赫夫曼樹(shù)為下圖所示。23115329147800000001111111赫夫曼編碼為：概率為0.23的字符編碼為：00概率為0.11的字符編碼為：010概率為0.05的字符編碼為：0110概率為0.03的字符編碼為：0111概率為0.29的字符編碼為：10 概率為0.14的字符編碼為：110 概率為0.07的字符編碼為：1110 概率為0.08的字符編碼為：111114、已知一棵二叉樹(shù)的前序遍歷的結(jié)果是ABECDFGHIJ, 中序遍歷的結(jié)果是EBCDAFHIGJ, 試畫出這棵二叉樹(shù)，并給出這棵二叉樹(shù)的后序遍歷序列。ABFGECDHJI、答

39、案：根據(jù)前序序列和中序序列能得到唯一的二叉樹(shù)，所得二叉樹(shù)如圖：這棵二叉樹(shù)的后序遍歷序列為：EDCBIHJGFA15、在結(jié)點(diǎn)個(gè)數(shù)為n(n>1)的各棵樹(shù)中，高度最小的樹(shù)的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？高度最大的樹(shù)的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？答案：結(jié)點(diǎn)個(gè)數(shù)為n時(shí)，高度最小的樹(shù)的高度為1，有2層；它有n-1個(gè)葉結(jié)點(diǎn)，1個(gè)分支結(jié)點(diǎn)；高度最大的樹(shù)的高度為n-1,有n層；它有1個(gè)葉結(jié)點(diǎn)，n-1個(gè)分支結(jié)點(diǎn)。16、 對(duì)于一個(gè)高度為h的AVL樹(shù)，其最少結(jié)點(diǎn)數(shù)是多少？反之，對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的AVL樹(shù), 其最大高度是多少? 最小高度是多少?答案：設(shè)高度為h(空樹(shù)的高度為-1

40、)的AVL樹(shù)的最少結(jié)點(diǎn)為Nh，則Nh = Fh+3 -1。Fh 是斐波那契數(shù)。又設(shè)AVL樹(shù)有n個(gè)結(jié)點(diǎn)，則其最大高度不超過(guò)3/2*log2(n+1),最小高度為log2(n+1) -1。17、7-7 設(shè)有序順序表中的元素依次為017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。試畫出對(duì)其進(jìn)行折半搜索時(shí)的判定樹(shù), 并計(jì)算搜索成功的平均搜索長(zhǎng)度和搜索不成功的平均搜索長(zhǎng)度。509154677017275170503094553897512612765908答案：折半搜索時(shí)的判定樹(shù)為：ASLSUCC=1/14（1+2*2

41、+3*4+4*7）=45/14ASLUNSUCC=1/15（3*1+4*14）=59/1518、試對(duì)下圖所示的AOE網(wǎng)絡(luò)(1) 這個(gè)工程最早可能在什么時(shí)間結(jié)束。(2) 求每個(gè)事件的最早開(kāi)始時(shí)間Vei和最遲開(kāi)始時(shí)間Vli。(3) 求每個(gè)活動(dòng)的最早開(kāi)始時(shí)間e( )和最遲開(kāi)始時(shí)間l( )。(4) 確定哪些活動(dòng)是關(guān)鍵活動(dòng)。畫出由所有關(guān)鍵活動(dòng)構(gòu)成的圖，指出哪些活動(dòng)加速可使整個(gè)工程提前完成。答案：按拓樸有序的順序計(jì)算各個(gè)頂點(diǎn)的最早可能開(kāi)始時(shí)間Ve和最遲允許開(kāi)始時(shí)間Vl，然后再計(jì)算各個(gè)活動(dòng)的最早可能開(kāi)始時(shí)間e和最遲允許開(kāi)始時(shí)間l,根據(jù)l-e是否等于0來(lái)確定關(guān)鍵活動(dòng)，從而確定關(guān)鍵路徑。Ve0191529384

42、3Vl01915373843<1,2><1,3><3,2><2,4><2,5><3,5><4,6><5,6>e00151919152938L170152719273738l-e1700801280此工程最早完成時(shí)間為43，關(guān)鍵路徑為<1,3><3,2><2,5><5,6>19、已知有五個(gè)待排序的記錄，其關(guān)鍵字分別為：256，301，751，129，937,863，742，694，076，438請(qǐng)用快速排序的方法將它們從小到大排列。答案：第一次排序：（0

43、76，129），256，（751，937，863，742，694，301，439）第二次排序：076，129，256，（438，301，694，742），751，（863，937）第三次排序：076，129，256，301，438，（694，742），751，（863，937）第四次排序：076，129，256，301，438，694，742，751，（863，937）第五次排序：076，129，256，301，438，694，742，751，863，937 20、設(shè)有150個(gè)記錄要存儲(chǔ)到散列表中, 并利用線性探查法解決沖突, 要求找到所需記錄的平均比較次數(shù)不超過(guò)2次。試問(wèn)散列表需要設(shè)計(jì)多大？

44、 (設(shè)a是散列表的裝載因子，則有ASLsucc = ( 1+1/ (1-a) )/2)。答案：已知要存儲(chǔ)的記錄數(shù)為n=150,查找成功的平均查找長(zhǎng)度為ASLsucc 2，則有：ASLsucc =1/2（1+1/（1-a）2 解得 a2/3 ，又有：a=n/m=150/m兩式聯(lián)立得：150/m2/3,解得：m225.所以散列表需要設(shè)計(jì)225個(gè)單位。五、算法分析題1、給出下列遞歸過(guò)程的執(zhí)行結(jié)果 void unknown ( int w ) if ( w ) unknown ( w-1 ); for ( int i = 1; i <= w; i+ ) cout << w<&l

45、t;' ' cout << endl; 調(diào)用語(yǔ)句為 unknown (4)。 答案：(1)1 2 23 3 3 4 4 4 4 2、給出遞歸過(guò)程的執(zhí)行結(jié)果 void unknown ( int n ) cout << n % 10 ; if ( int ( n / 10 ) ) unknown ( int ( n / 10 ) ); 調(diào)用語(yǔ)句為unknown ( 582 )。答案： 2853、給出遞歸過(guò)程的執(zhí)行結(jié)果int unknown ( int m ) int value; if ( ! m ) value = 3; else value = unk

46、nown ( m-1 ) + 5; return value;執(zhí)行語(yǔ)句為 cout << unknown (3)。答案： 18 4、 設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在644（10），A22存放位置在676（10），每個(gè)元素占一個(gè)空間，問(wèn)A33（10）存放在什么位置？腳注（10）表示用10進(jìn)制表示。答案：設(shè)數(shù)組元素Aij存放在起始地址為L(zhǎng)oc(i,j)的存儲(chǔ)單元中。 因?yàn)椋篖oc(2,2)= Loc(0,0)+2*n+2=644+2*n+2=676 所以：n=(676-2-644)/2=15 所以：Loc(3,3)= Loc(0,0)+3*15+3=644+45+3=69

47、25、設(shè)單鏈表結(jié)構(gòu)為 struct ListNode int data ; ListNode * link ; ;下面的程序是以單鏈表為存儲(chǔ)結(jié)構(gòu), 實(shí)現(xiàn)二路歸并排序的算法, 要求鏈表不另外占用存儲(chǔ)空間, 排序過(guò)程中不移動(dòng)結(jié)點(diǎn)中的元素, 只改各鏈結(jié)點(diǎn)中的指針, 排序后r仍指示結(jié)果鏈表的第一個(gè)結(jié)點(diǎn)。在初始狀態(tài)下, 所有待排序記錄鏈接在一個(gè)以r為頭指針的單鏈表中。例如, 在算法實(shí)現(xiàn)時(shí)，利用了一個(gè)隊(duì)列做為輔助存儲(chǔ), 存儲(chǔ)各有序鏈表構(gòu)成的歸并段的鏈頭指針。初始時(shí), 各初始?xì)w并段為只有一個(gè)結(jié)點(diǎn)的有序鏈表。隊(duì)列的數(shù)據(jù)類型為Queue, 其可直接使用的相關(guān)操作有n 置空隊(duì)列操作：makeEmpty ( );

48、n 將指針x加入到隊(duì)列的隊(duì)尾操作：EnQueue ( ListNode * x ); n 退出隊(duì)頭元素, 其值由函數(shù)返回的操作：ListNode *DlQueue ( );n 判隊(duì)列空否的函數(shù), 空則返回1, 不空則返回0：int IsEmpty( )。 解決方法提示：Ø 程序首先對(duì)待排序的單鏈表進(jìn)行一次掃描, 將它劃分為若干有序的子鏈表, 其表頭 指針存放在一個(gè)指針隊(duì)列中。Ø 當(dāng)隊(duì)列不空時(shí), 從隊(duì)列中退出兩個(gè)有序子鏈表, 對(duì)它們進(jìn)行二路歸并, 結(jié)果鏈表的表頭指針存放到隊(duì)列中。Ø 如果隊(duì)列中退出一個(gè)有序子鏈表后變成空隊(duì)列, 則算法結(jié)束。這個(gè)有序子鏈表即為所求。在算

49、法實(shí)現(xiàn)時(shí)有 6 處語(yǔ)句缺失，請(qǐng)閱讀程序后補(bǔ)上。(1) 兩路歸并算法void merge ( ListNode * ha, ListNode * hb, ListNode *& hc ) ListNode *pa, *pb, *pc ; if ( hadata <= hbdata ) hc = ha; pa = halink; pb = hb; else hc = hb; pb = hblink; pa = ha ; pc = hc; while ( pa && pb ) if ( padata <= pbdata) pclink = pa; pc = pa; pa = palink; else pclink = pb; pc = pb; pb = pblink; if ( pa ) pclink = pa; else pclink = pb; ;(2) 歸并排序主程序void mergesort ( ListNode * r ) ListNode * s, t; Queue Q ; if ( ! r ) return;s = r; Q.EnQueue( r ); while ( s ) t = slink; while ( t