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

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

2、ink = st link； st link = p;q t link = s; st link = p;如果想在4092個(gè)數(shù)據(jù)中只需要選擇其中最小的A起泡排序設(shè)有兩個(gè)串t12、若需要利用形參直接訪問(wèn)實(shí)參,A指針B 引用13、下面程序段的時(shí)間復(fù)雜度為（for (int i=0;i<m;i+)for (int j=0;j<n;j+)aij=i*j;A O（m 2）B O（n 2）14、下面程序段的時(shí)間復(fù)雜度為（int f(unsigned int n) if(n= =0 | n= =1)return 1;else return n*f(n-1);則應(yīng)把形參變量說(shuō)明為（值B )D 變量

3、C O(m*n)參數(shù)。D O(m+n)A O（1）B O（n）線性表若是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí), 必須是連續(xù)的15、部分地址必須是連續(xù)的C O（n2）要求內(nèi)存中可用存儲(chǔ)單元的地址D O(n !)5個(gè)，采用（B堆排序C錦標(biāo)賽排序和p，求p在t中首次出現(xiàn)的位置的運(yùn)算叫做（B模式匹配C 串替換每一個(gè)數(shù)組元素Aij占用3個(gè)存儲(chǔ)字，行下標(biāo)）方法最好。D 快速排序一定是不連續(xù)的連續(xù)或不連續(xù)都可以）°D串連接i從1到8，列下標(biāo)j從1到A 求子串7、在數(shù)組A中，10。所有數(shù)組元素相繼存放于一個(gè)連續(xù)的存儲(chǔ)空間中，則存放該數(shù)組至少需要的存儲(chǔ)字?jǐn)?shù)是16、數(shù)據(jù)結(jié)構(gòu)的定義為（D，S），其中D是（B ）的集合。A算

4、法B數(shù)據(jù)元素C數(shù)據(jù)操作D邏輯結(jié)構(gòu)10、在循環(huán)隊(duì)列中用數(shù)組 A0.m-1存放隊(duì)列元素，其隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（D)oA(front - rear+ 1) % mB(rear - front + 1) % mC(front - rear+ m) % mD(rear - front + m) % m11、一個(gè)數(shù)組元素ai與（A)的表示等價(jià)。A* (a+i )B a+iC *a+iD& a+i（ C ）°A 80B 100C 240D 2708、 將一個(gè)遞歸算法改為對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用（A ）°A 棧B隊(duì)列C循環(huán)隊(duì)列

5、D 優(yōu)先隊(duì)列9、 一個(gè)隊(duì)列的進(jìn)隊(duì)列順序是1,2, 3, 4，則出隊(duì)列順序?yàn)椋?C ）°17、算法分析的目的是（A ） °A找岀數(shù)據(jù)結(jié)構(gòu)的合理性B研究算法中輸入和輸岀的關(guān)系C分析算法的效率以求改進(jìn)D分析算法的易懂性和文檔性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è)單鏈表中

6、結(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->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;p=p->

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

8、;link;typedef int Data Type;typedef struct Data Type dataMaxsize;Int front, rear; Queue;若有一個(gè)Queue類(lèi)型的隊(duì)列Q,試問(wèn)判斷隊(duì)列滿的條件應(yīng)是下列哪一個(gè)語(yǔ)句(A Q.front= = Q.rear;B Q.front - Q.rear= = Maxsize;rear->link->link=s->link;delete s;22、設(shè)單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data,link 表當(dāng)前指針，在循環(huán)鏈表中檢測(cè)，且first為指向鏈表表頭的指針， current是否達(dá)到鏈表表尾的語(yǔ)句是( D

9、)。curre nt 為鏈A current->link =nullB first->link=currentC first=currentD current->link=first23、一個(gè)棧的入棧序列為b，c,則出棧序列不可能的是C c,a,b24、c,b,aB b,a,c棧的數(shù)組表示中，top為棧頂指針，?？盏臈l件是(C )。a,c,bA )。25、top=0B top=maxSize棧和隊(duì)列的共同特點(diǎn)是(C )。都是先進(jìn)后岀只允許在端點(diǎn)處插入和刪除C top=maxSize都是先進(jìn)先岀沒(méi)有共同點(diǎn)D top=-126、假定一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e為f+

10、1= =rB 葉仁=ff和r ,則判斷隊(duì)空的條件為(DC f= =0D f= =r).27、當(dāng)利用大小為的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為(A n-2B n-1D n+128、當(dāng)利用大小為個(gè)元素時(shí)，首先應(yīng)執(zhí)行的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用 top= =n 表示棧空，則向這個(gè)棧插入一 ()語(yǔ)句修改top指針。A top+;29、設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為(C Q.front + Q.rear= = Maxsize;31、設(shè)有一個(gè)遞歸算法如下：D Q.front= = (Q.rea 葉1)% Maxsize;int fact (int n ) if (n<=0) return 1;el

11、se return n*fact(n-1);下面正確的敘述是(B )A計(jì)算fact(n)需要執(zhí)行n次遞歸C此遞歸算法最多只能計(jì)算到fact(8)32、設(shè)有一個(gè)遞歸算法如下int x (intif (n<=3)else returnn) return 1;x(n_2)+x(n_4)+1;試問(wèn)計(jì)算x(x(8)時(shí)需要計(jì)算(D )次33、設(shè)有廣義表D(a,b,D),其長(zhǎng)度為A aB 334、廣義表A(a),則表尾為(B fact(7)=5040D以上結(jié)論都不對(duì)函數(shù)。C 16D 18次B )，深度為(CB top-;C top=0;D top;data, link ) ，且 top是指向棧頂?shù)闹羔?/p>

12、。若想摘除鏈?zhǔn)綏５臈ｍ?結(jié)點(diǎn)，并將被摘除結(jié)點(diǎn)的值保存到x中，則應(yīng)執(zhí)行下列(A )操作。B ()35、下列廣義表是線性表的有(空表(a)A x=top->data; top=top->link;C x=top; top=top->link;30、設(shè)循環(huán)隊(duì)列的結(jié)構(gòu)是：B top=top->link; x=top->data;D x=top->data;A E ( a,(b,c)36、遞歸表、再入表、純表、線性表之間的關(guān)系為A 再入表 > 遞歸表 > 純表 > 線性表E(a,E)C E (a,b)E(a,L()遞歸表 > 線性表 >

13、再入表 > 純表const int Maxsize=100;C 遞歸表 > 再入表 > 純表 > 線性表D遞歸表 > 再入表 > 線性表 > 純表37、某二叉樹(shù)的前序和后序序列正好相反，則該二叉樹(shù)一定是(B )的二叉樹(shù)。A 24C 48B da1+I*mD 53m個(gè)存儲(chǔ)單元，若第一個(gè)結(jié)點(diǎn)的地址為da1,C da1-l*mD da1+(l+1)*m）以數(shù)組方式存儲(chǔ)D以鏈接方式存儲(chǔ)的線性表。）順序存儲(chǔ)或鏈接存儲(chǔ)D 索引存儲(chǔ)的有序表時(shí)，元素的平均搜索長(zhǎng)度為（B n+1D n+e48、平均搜索長(zhǎng)度為（C不直接依賴(lài)于C ）n D 上述都不對(duì)四種四種A空或只有一個(gè)

14、結(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ù)為no,度為2的結(jié)點(diǎn)為n2.，則（A ）A n o= n2+1 B n 2= n o+1 C n 0= 2n 2+1D n 2=2n o+139、由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（B）B 7340、已知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)需占 則第I個(gè)結(jié)點(diǎn)的地址為（A ）oA da1+（l-1）*m41、34具有35個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為42、對(duì)線性表進(jìn)行折半搜索時(shí)，要求線性表必須 A 以鏈接方式存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵碼有序排列C以數(shù)組方式存儲(chǔ)且結(jié)點(diǎn)按

15、關(guān)鍵碼有序排列43、順序搜索算法適合于存儲(chǔ)結(jié)構(gòu)為（A散列存儲(chǔ)C壓縮存儲(chǔ)44、 采用折半搜索算法搜索長(zhǎng)度為nA O （n2）B O （n log 2n）C O （log 2n）45、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，進(jìn)行拓?fù)渑判驎r(shí)，總的時(shí)間為C n-146、判斷一個(gè)有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用（A求關(guān)鍵路徑的方法B 求最短路徑的Dijkstra方法C深度優(yōu)先遍歷算法D廣度優(yōu)先遍歷算法47、在10階B-樹(shù)中根結(jié)點(diǎn)所包含的關(guān)鍵碼個(gè)數(shù)最多為（ C ），最少為（A10對(duì)包含n個(gè)元素的散列表進(jìn)行搜索，O （log 2n）B O （n）填空題（）數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)

16、、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)3、 一種抽象數(shù)據(jù)類(lèi)型包括（數(shù)據(jù)）和（操作）兩個(gè)部分。4、 設(shè)有兩個(gè)串p和q，求p在q中首次出現(xiàn)的位置的運(yùn)算稱(chēng)為（模式匹配）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)先出）& 串是由（ 零個(gè)或多個(gè)）字符組成的序列。（長(zhǎng)度為零的串）稱(chēng)為空串，（由一個(gè)或多個(gè)空格組成的串）稱(chēng)為空格串。9、設(shè)目標(biāo)串T= ” abccdc

17、dccbaa ”，模式P= ” cdcc ”則第（6）次匹配成功。10、 一維數(shù)組的邏輯結(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è)位置，然后把待插入元素（寫(xiě)） 到這個(gè)位置上。從一個(gè)順序棧刪除元素時(shí)，需要前移一位（棧頂指針）。12、 在一個(gè)循環(huán)隊(duì)列Q中，判斷隊(duì)空的條件為（ Q.front= =Q.rear ）,判斷隊(duì)滿的條件為（Q.rea 葉1）%MaxSi

18、ze= =q.front）13、對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，該樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和為（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中，其余類(lèi)推，則ai元素的左子女結(jié)點(diǎn)為（2*i+1 ），右子女結(jié)點(diǎn)為（2*i+2），雙親結(jié)點(diǎn)（i>=1 ）為（i-1）/2 n ）.16、在一個(gè)最大堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的（最大值），在一個(gè)最小堆中，堆頂結(jié)點(diǎn)的 值是所有結(jié)點(diǎn)中的（最小值）。17、 已知具有n個(gè)元素的一維數(shù)組采用順序存

19、儲(chǔ)結(jié)構(gòu)，每個(gè)元素占k個(gè)存儲(chǔ)單元，第一個(gè)元素的地址為 LOC（a1），那么，LOC（ai）= L0C（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ù)

20、是（68 ）o若完全二叉樹(shù)的第7有10 個(gè)葉子結(jié)點(diǎn)，則整個(gè)二叉樹(shù)的結(jié)點(diǎn)數(shù)最多是（235 ）23、 對(duì)于折半搜索所對(duì)應(yīng)的判定樹(shù)，它既是一棵（二叉搜索樹(shù)），又是一棵（理想平衡樹(shù)）。24、假定對(duì)長(zhǎng)度n=50的有序表進(jìn)行折半搜索，則對(duì)應(yīng)的判定樹(shù)高度為（5）,判定樹(shù)中前5層的結(jié)點(diǎn)數(shù)為（3 1），最后一層的結(jié)點(diǎn)數(shù)為（19）。25、 在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（2）倍。在一個(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

21、-1 ）27、 設(shè)線性表中元素的類(lèi)型是實(shí)型，其首地址為1024，則線性表中第 6個(gè)元素的存儲(chǔ)位置是（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

22、條邊的無(wú)向連通圖，利用普里姆算法產(chǎn)生的最小生成樹(shù)， 其時(shí)間復(fù)雜 度為（0（n2）、利用克魯斯卡爾算法產(chǎn)生的最小生成樹(shù)，其時(shí)間復(fù)雜度為（0（elog 2e）34、 快速排序在平均情況下的時(shí)間復(fù)雜度為（0 （nlog 2n），在最壞情況下的時(shí)間復(fù)雜度為（0（n2）;快速排序在平均情況下的空間復(fù)雜度為（0（ log 2n）,在最壞情況下的空間復(fù)雜度為（0（ n ）。35、假定一組記錄的排序碼為（46，79,5 6,38,40,80)，對(duì)其進(jìn)行歸并排序的過(guò)程中，第二趟排序后的結(jié)果是（3 84 65 679 408 0)36、假定一組記錄的排序碼為（46，79,5 6,3 8,40,80)，對(duì)其進(jìn)行快速

23、排序的第一次劃分的結(jié)果是（3 84 0 46567 98 0)。37、 一個(gè)結(jié)點(diǎn)的子樹(shù)的（個(gè)數(shù)）稱(chēng)為該結(jié)點(diǎn)的度。度為（ 零）的結(jié)點(diǎn)稱(chēng)為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。度不為（零）的結(jié)點(diǎn)稱(chēng)為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。樹(shù)中各結(jié)點(diǎn)度的（ 最大值 ）稱(chēng)為樹(shù)的度。38、 設(shè)Ki=Kj（1<=i<=n, 1<=jv=n,jv>i）且在排序前的序列中 Ri領(lǐng)先于R （i<j）,若排序后的序 列中Ri仍領(lǐng)先于 Rj，則這種排序方法是（穩(wěn)定的），反之是（不穩(wěn)定的）。40、在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行調(diào)整運(yùn)算的時(shí)間復(fù)雜度為（0（log 2n），整個(gè)排序過(guò)程的時(shí)間復(fù)雜度為（0（ nlog 2n）

24、。41、在索引表中，每個(gè)索引項(xiàng)至少包含有（關(guān)鍵碼值）域和（子表地址）域這兩項(xiàng)。42、假定一個(gè)線性表為（” abed ”，” baabd ”，” beef ”，” cfg ”，” ahij”，” bkwte ”，” ccdt ” / aayb ”），若按照字符串的第一個(gè)字母進(jìn)行劃分，使得同一個(gè)字母被劃分在一個(gè)子表中，則得到的a，b，c三個(gè)子表的長(zhǎng)度分別為（3），（3），（2）。43、 對(duì)于包含5 0個(gè)關(guān)鍵碼的3階B-樹(shù)，其最小高度為（4），最大高度為（5）。44、從一棵B-樹(shù)刪除關(guān)鍵碼的過(guò)程，若最終引起樹(shù)根結(jié)點(diǎn)的合并，則新樹(shù)比原樹(shù)的高度（減1）45、假定要對(duì)長(zhǎng)度n=100的線性表進(jìn)行散列存儲(chǔ)，

25、并采用開(kāi)散列法處理沖突， 則對(duì)于長(zhǎng)度m=20的散列表，每個(gè)散列地址的同義詞子表的長(zhǎng)度平均為（5）。46、在散列存儲(chǔ)中，裝載因子 a又稱(chēng)為裝載系數(shù)，若用 m表示散列表的長(zhǎng)度，n表示待散列存儲(chǔ) 的元素的個(gè)數(shù)，則a等于（n/m ）。47、 在有向圖的鄰接矩陣中，第 i行中“ 1 ”的個(gè)數(shù)是第i個(gè)頂點(diǎn)的（岀度），第i列中“ T的個(gè) 數(shù)是第i個(gè)頂點(diǎn)的（入度）。在無(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 n -1 ）個(gè)，最多為（m-1 ）個(gè)，其子樹(shù)棵數(shù)最少為（m/2

26、n ），最多為（m ）。三、判斷題1、數(shù)據(jù)元素是數(shù)據(jù)的最小單位（X）o2、 數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的（V）.3、數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體（X）。4、從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為兩大類(lèi)：線性結(jié)構(gòu)和非線性結(jié)構(gòu)（V）。5、線性表的邏輯順序與物理順序總是一致的（X）。6、二維數(shù)組是其數(shù)組元素為線性表的線性表（X）。7、每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運(yùn)算：插入、刪除、搜索（V）。8、 非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接前驅(qū)元素。（X ）9、 空串與由空格組成的串沒(méi)有區(qū)別。（X ）10、 將T在S中首次出現(xiàn)的位置作為 T

27、在S中的位置的操作稱(chēng)為串的模式匹配。（V）11、 深度為h的非空二叉樹(shù)的第h層最多有2h-1個(gè)結(jié)點(diǎn)（X ）12、 完全二叉樹(shù)就是滿二叉樹(shù)。（X）13、 已知一棵二叉樹(shù)的前序序列和中序序列可以唯一地構(gòu)造岀該二叉樹(shù)。（V ）14、 帶權(quán)連通圖的最小生成樹(shù)的權(quán)值之和一定小于它的其它生成樹(shù)的權(quán)值之和。（V）15、線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也相鄰。(1 ) AB-*C+(3)AB&&EF>!|16、若有一個(gè)結(jié)點(diǎn)是二叉樹(shù)中某個(gè)子樹(shù)的中序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)，則它一定是該子樹(shù)的前序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)。（V）17、任一棵二叉搜索樹(shù)的平均

28、搜索時(shí)間都小于用順序搜索法搜索同樣結(jié)點(diǎn)的順序表的平均搜索 時(shí)間。（X）18、 最優(yōu)二叉搜索樹(shù)一定是平衡的二叉搜索樹(shù)。（V）19、 AOE網(wǎng)是一種帶權(quán)的無(wú)環(huán)連通圖。（V ）20、對(duì)于同一組待輸入的關(guān)鍵碼集合，雖然各關(guān)鍵碼的輸入次序不同，但得到的二叉搜索樹(shù)都是 相同的（X）。21、二叉排序樹(shù)可以是一棵空樹(shù)（ V ）22、 線性表中所有結(jié)點(diǎn)的類(lèi)型必須相同。（V ）23、n個(gè)結(jié)點(diǎn)的有向圖，若它有 n（n - 1）條邊，則它一定是強(qiáng)連通的。（ V ）24、任何無(wú)環(huán)的有向圖，其結(jié)點(diǎn)都可以排在一個(gè)拓?fù)湫蛄欣铩＃?V）25、 隊(duì)列邏輯上是一個(gè)下端口和上端能增加又能減少的線性表（X ）26、 二叉樹(shù)是樹(shù)的一種特

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

30、突時(shí)，其裝載因子的取值一定在（0,1）之間。（X）37、 B-樹(shù)是一種動(dòng)態(tài)索引結(jié)構(gòu)，它既適用于隨機(jī)搜索，也適用于順序搜索。（X）38、 在散列法中，一個(gè)可用散列函數(shù)必須保證絕對(duì)不產(chǎn)生沖突。（X）39、 任何一個(gè)關(guān)鍵活動(dòng)延遲，那么整個(gè)工程將會(huì)延遲。（V）40、 任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成。（X）四、運(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í)，可能的出棧序列有多少種？6457321是否是合理的岀棧序列？答案：可能的岀

31、棧序列有種，6457321不是合理的岀棧序列3、簡(jiǎn)單（直接）選擇排序是一種穩(wěn)定的排序方法嗎？試舉例說(shuō)明？答案：是不穩(wěn)定的排序方法。下面就是不穩(wěn)定的例子。只要能舉岀反例即可。 275275*512061i = 1 061275*512275i = 2 061275 *512275i = 3 061275 *275512 4、設(shè)有序順序表為 10, 20, 30, 40, 50, 60, 70，采用折半搜索時(shí)，搜索成功的平均搜索長(zhǎng)度是多少？答案：ASLsucc = （1*1 + 2*2 + 3*4 ） / 7 = 17 / 75、在結(jié)點(diǎn)個(gè)數(shù)為n（n>1）的各棵樹(shù)中，高度最小的樹(shù)的高度是多少？

32、它有多少個(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)是多少？（3）編號(hào)為i的結(jié)點(diǎn)的第m個(gè)孩子結(jié)點(diǎn)（若存在）的編號(hào)是多少？（4）編號(hào)為i的結(jié)點(diǎn)有右兄

33、弟的條件是什么？其右兄弟結(jié)點(diǎn)的編號(hào)是多少？（5）若結(jié)點(diǎn)個(gè)數(shù)為n,則高度h是n的什么函數(shù)關(guān)系？答案：（1）各層的結(jié)點(diǎn)個(gè)數(shù)是 口（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=log k（n*（k-1）+1）-1（n=0時(shí)h=-1）7、寫(xiě)岀下列中綴表達(dá)式的后綴形式：（1）A* - B + C（2） （A + B） * D + E / （F + A * D）

34、+ C（3） A && B| ! （E > F）注：按 C+ 的優(yōu)先級(jí)）!（A && !（ （B < C）|（C > D） ） ）|（C < E）答案：各中綴表達(dá)式的后綴形式如下：(2) AB+D*EFAD*+/+C+(4) ABC<CD>|!&& !CE<|Cu1413121110 9 8 = 4298、畫(huà)岀下列廣義表的圖形表示和它們的存儲(chǔ)表示: D(A(c), B(e), C(a, L(b, c, d)(2) J1(J2(J1, a, J3(J1), J3(J1)廣義表（2）的圖形表示為:9、題目：1

35、1、將下面的森林變換成二叉樹(shù)（7分）廣義表（2）的存儲(chǔ)表示為:425答案：其中的一個(gè)拓?fù)湫蛄袨椋篤1，將給定的圖簡(jiǎn)化為最小的生成樹(shù),12、1V2，V3，V4，要求從頂點(diǎn)V5，V6，V7出發(fā)。（7分）答案:11、根據(jù)所給有向圖，寫(xiě)岀一個(gè)拓?fù)湫蛄?。? 分）（7 分）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)造的赫夫曼樹(shù)共有m=2n-1=2*8-1=15個(gè)結(jié)點(diǎn)。生成的赫夫曼樹(shù)為下圖所示。概率為0.05的字符編碼為：0110概率為0.03的字符編碼為

36、：0111概率為0.29的字符編碼為：10概率為0.14的字符編碼為：110概率為0.07的字符編碼為：1110概率為0.08的字符編碼為：111114、已知一棵二叉樹(shù)的前序遍歷的結(jié)果是ABECDFGHIJ,中序遍歷的結(jié)果是 EBCDAFHIGJ,答案：根據(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è)葉

37、結(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)的AVL樹(shù)的最少結(jié)點(diǎn)為 Nh，則Nh = F h+3 -1。Fh是斐波那契數(shù)。又設(shè) AVL樹(shù)有n個(gè)結(jié)點(diǎn)，則其最大高度不超過(guò)3/2*log 2(n+1),最小高度為log 2(n+1) n -1。17、 7-7 設(shè)有序順序表中的元素依次為017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677,

38、765, 897, 908 。試畫(huà)岀對(duì)其進(jìn)行折半搜索時(shí)的判定樹(shù)，并計(jì)算搜索成功的平均搜索長(zhǎng)度和搜索不成功的平均搜索長(zhǎng)度。答案：折半搜索時(shí)的判定樹(shù)為：ASLsucc=1/14(1+2*2+3*4+4*7) =45/14ASLunsucc=1/15(3*1+4*14 ) =59/1518、試對(duì)下圖所示的 AOE網(wǎng)絡(luò)10(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)。畫(huà)出由所有關(guān)鍵活動(dòng)構(gòu)成的圖，指出哪些活動(dòng)加速可使整個(gè)工程unknown ( w-1 );fo

39、r ( int i = 1 ; i <= w; i+ ) cout <<w<<'cout << endl;Ve01915293843Vl01915373843答案:提前完成。答案：按拓樸有序的順序計(jì)算各個(gè)頂點(diǎn)的最早可能開(kāi)始時(shí)間Ve和最遲允許開(kāi)始時(shí)間 Vl，然后再計(jì)算各個(gè)活動(dòng)的最早可能開(kāi)始時(shí)間e和最遲允許開(kāi)始時(shí)間I,根據(jù)l-e是否等于0來(lái)確定關(guān)鍵活動(dòng)，從而確定關(guān)鍵路徑。調(diào)用語(yǔ)句為12 2unknown (4)<1,2><1,3><3,2><2,4><2,5><3,5><

40、4,6i><5,6>334 4t行結(jié)果n ( int n ) e00151919152938 44L17015271927372、給出遞歸過(guò)程的扌l(wèi)-e170080128vd unknowcout <<此工程最早完成時(shí)間為43，關(guān)鍵路徑為<1,3><3,2><2,5><5,6>if ( int ( nn19、已知有五個(gè)待排序的記錄，其關(guān)鍵字分別為：256，301，751，129，937,863076，438請(qǐng)用快速排序的方法將它們從小到大排列。答案：第一次排序：(076，129)，256，第二次排序:076，129，

41、256，第三次排序:076，129，256，第四次排序:076，129，256，301，第五次排序:076，129，256，301，742 ， 694 ，/ 10 ) ) unknown ( int ( n / 10 );調(diào)用語(yǔ)句為unknown ( 582 )。(751，937，863，742，694，301，439 )!，301，694，742)，751，( 863，937 )438，(694，742)，751，( 863，937 )301，694，742，751，( 863，937)438，(438438，694，742，751，863，937285答案：3、給岀遞歸過(guò)程的執(zhí)行結(jié)果int

42、 unknown ( int m ) int value;if ( ! m ) value = 3 ;else value = unknown ( m-1 ) + 5 ;20、設(shè)有150個(gè)記錄要存儲(chǔ)到散列表中，并利用線性探查法解決沖突，要求找到所需記錄的平均比較次數(shù)不超過(guò) 2次。試問(wèn)散列表需要設(shè)計(jì)多大？(設(shè) 堤散列表的裝載因子，則有ASLsucc=(1+1/ (1- ：) )/2)。答案：已知要存儲(chǔ)的記錄數(shù)為n = 150,查找成功的平均查找長(zhǎng)度為ASLsucc < 2，則有：ASLsucc=1/2(1+1/(1-< 2 解得 辱 2/3 ，又有：Cfen/m=150/m兩式聯(lián)立得

43、：150/m < 2/3,解得：m > 225.所以散列表需要設(shè)計(jì) 225個(gè)單位。五、算法分析題1、給岀下列遞歸過(guò)程的執(zhí)行結(jié)果void unknown ( int w ) if ( w ) return value;執(zhí)行語(yǔ)句為 cout << unknown (3)。答案： 184、 設(shè)有一個(gè)二維數(shù)組 Amn，假設(shè)A00存放位置在644 (10)，A22存放位置在676每個(gè)元素占一個(gè)空間，問(wèn)A33 ( 10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。答案：設(shè)數(shù)組元素 Ai j存放在起始地址為L(zhǎng)oc(i,j)的存儲(chǔ)單元中。因?yàn)椋篖oc(2,2)= Loc(0,0)+

44、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=692(10)，5、 設(shè)單鏈表結(jié)構(gòu)為struct ListNode int data ;ListNode * link pct link = pb; pc = pb ; pb = pb T|ink；下面的程序是以單鏈表為存儲(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為頭指針的單鏈表中。例如

45、，r*在算法實(shí)現(xiàn)時(shí)，利用了一個(gè)隊(duì)列做為輔助存儲(chǔ)，存儲(chǔ)各有序鏈表構(gòu)成的歸并段的鏈頭指針。初始時(shí)，各初始?xì)w并段為只有一個(gè)結(jié)點(diǎn)的有序鏈表。隊(duì)列的數(shù)據(jù)類(lèi)型為Queue，其可直接使用的63A相關(guān)操作有置空隊(duì)列操作：makeEmpty ();將指針x加入到隊(duì)列的隊(duì)尾操作：EnQueue ( ListNode * x );退出隊(duì)頭元素，其值由函數(shù)返回的操作：ListNode *DlQueue ();判隊(duì)列空否的函數(shù)，空則返回1,不空則返回0: int IsEmpty ()。解決方法提示：程序首先對(duì)待排序的單鏈表進(jìn)行一次掃描，將它劃分為若干有序的子鏈表，其表頭指針存放在一個(gè)指針隊(duì)列中。當(dāng)隊(duì)列不空時(shí)，從隊(duì)列中退

46、岀兩個(gè)有序子鏈表，對(duì)它們進(jìn)行二路歸并，結(jié)果鏈表的表頭指 針存放到隊(duì)列中。如果隊(duì)列中退岀一個(gè)有序子鏈表后變成空隊(duì)列，則算法結(jié)束。這個(gè)有序子鏈表即為所求。在算法實(shí)現(xiàn)時(shí)有 6處語(yǔ)句缺失，請(qǐng)閱讀程序后補(bǔ)上。(1) 兩路歸并算法void merge ( ListNode * ha ，ListNode * hb，ListNode * & he ) ListNode *pa，*pb，*pe ;if ( hatdata <= hbtdata ) he = ha; pa = hatlink； pb = hb ; else he = hb; pb = hbtlink; pa = ha ; pe =

47、he;while ( pa && pb )if ( pa t data <= pb tdata) pe t link = pa;pe = pa;pa = pa t link;elseif ( pa ) pe t link = pa; else pe t link = pb;(2) 歸并排序主程序void mergesort ( ListNode * r ) ListNode * s，t;Queue Q ;if ( ! r ) return;s = r;Q.EnQueue ( r );while ( s ) t = st link ;while ( t != 0 &

48、& st data <= tt data ) s = t; t = t t link;if ( t ) st link = 0 ; s = t;Q.EnQueue ( s );while ( !Q.lsEmpty( ) ) r = Q.DlQueue ();if ( Q.IsEmpty ( ) ) break;s = Q.DlQueue ();merge ( r，s，t );Q.EnQueue ( t );6、請(qǐng)讀下列程序，該程序是在單鏈表中刪除一個(gè)結(jié)點(diǎn)的算法，為空岀的地方填上正確的語(yǔ)句。(7分)void demo2(LinkList head，L istNode *p)/hea

49、d是帶頭結(jié)點(diǎn)的單鏈表，刪除P指向的結(jié)點(diǎn)ListNode *q=head;while(q&& q->next!=p ) q=q->next;if (q) Error( “ *p not in head ” );q->next=p->next;free(p);10、已知一完全二叉樹(shù)從根結(jié)點(diǎn)開(kāi)始，自頂向下，同一層自左向右連續(xù)編號(hào)，根結(jié)點(diǎn)的編號(hào)為0 ,閱讀以下程序請(qǐng)回答該程序所實(shí)現(xiàn)的功能：templatevclass type >void linkedtosequent(Bintreenode<Type> *t,type a ,int i)if

50、 (t!=Null)a=t->getData();linkedtosequent(t->getleftchild(),a,2*i+1); linkedtosequent(t->getrightchild(),a,2*i+2);主程序調(diào)用方式：linkedtosequent(t.root,a,0);答案：該程序的功能是：將用二叉鏈表表示的完全二叉樹(shù)轉(zhuǎn)換為二叉樹(shù)的順序(數(shù)組)表示。8、設(shè)散列表為HT13,散列函數(shù)為 H (key) = key %13。用閉散列法解決沖突，對(duì)下列關(guān)鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。(1)采

51、用線性探查法尋找下一個(gè)空位，畫(huà)岀相應(yīng)的散列表，并計(jì)算等概率下搜索成功的平均搜索長(zhǎng)度和搜索不成功的平均搜索長(zhǎng)度。 采用雙散列法尋找下一個(gè)空位 ，再散列函數(shù)為 RH ( key) = (7* key) % 10 + 1,尋找下一個(gè)空 位的公式為 Hi = (H i-1 + RH ( key) % 13, H 1 = H ( key)。畫(huà)出相應(yīng)的散列表，并計(jì)算等概率下搜 索成功的平均搜索長(zhǎng)度。答案：使用散列函數(shù)H(key)=key mod 13 有：H (12 ) =12 , H (23) =10 , H (45) =6 , H (57) =5 , H (20) =7 , H (03) =3 , H

52、 (78 ) =0 , H (31 ) =5 , H (15 ) =2 , H (36) =10利用線性探查法造表：0123456789101112781503574520312336121111114121搜索成功的平均搜索長(zhǎng)度為：ASLsucc =1/10( 1+1+1+1+1+1+4+1+2+1) =14/10搜索不成功的平均搜索長(zhǎng)度為：ASLunsucc =1/13(2+1+3+2+1+5+4+3+2+1+5+4+3) =36/13利用雙散列法造表：Hi = (H i-1 + RH(key) ) %13, Hi =H(key)012345678910111278150357452031

53、36231211111135119、閱讀下面程序，指岀其算法的功能并求岀其時(shí)間復(fù)雜度(1) int Prime(int n)int i=2,x=(int)sqrt(n); while(i<=x) if(n%i=0)break; i+;if(i>x) return 1;else return 0;(2)int sum1(int n)int p=1,s=0;for(int i=1;i<=n;i+)p*=i;s+=p;return s;答案：(1 )程序功能是判斷n是否是一個(gè)素?cái)?shù)，若是則返回?cái)?shù)值1，否則返回?cái)?shù)值 0,該算法的時(shí)間復(fù)雜度為O (sqrt(n).(2)程序功能是計(jì)算刀ni=1 i!，該算法的時(shí)間復(fù)雜度為O (n).10、判斷一個(gè)帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表L是否對(duì)稱(chēng)相等的算法如下所示，請(qǐng)?jiān)谒惴ǖ奶幪钊胝_的語(yǔ)句。int symmetry(DblList DL) int sym=1;DblNode p=DL->rLink, q=DL->lLink;Whi