數(shù)據(jù)結(jié)構(gòu)與算法試題數(shù)據(jù)結(jié)構(gòu)與算法試題
數(shù)據(jù)結(jié)構(gòu)與算法試題數(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)/2
4、在一個(gè)單鏈表中,若q結(jié)點(diǎn)就是p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在q與p之間插入結(jié)點(diǎn)
s,則執(zhí)行( D )。A s→link = p→link;p→link = s; B p→link = s; s→link = q;C p→link = s→link;s→link = p;D q→link = s;s→link = 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ù)組元素A[i][j]占用3個(gè)存儲(chǔ)字,行下標(biāo)i從1到8,列下標(biāo)j從1到10。所有數(shù)組元素相繼存放于一個(gè)連續(xù)的存儲(chǔ)空間中,則存放該數(shù)
數(shù)據(jù)結(jié)構(gòu)與算法試題
組至少需要的存儲(chǔ)字?jǐn)?shù)就是( C )。
A 80 B 100
C 240
D 270
8、將一個(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ù)組A[0、、m-1] 存放隊(duì)列元素,其隊(duì)頭與隊(duì)尾指針分別為
front與rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)就是( D )。
A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m
D ( rear - front + m) % m
11、一個(gè)數(shù)組元素a[i]與( A )的表示等價(jià)。
A *(a+i)
B a+i
C *a+i
D &a+i
12、若需要利用形參直接訪問實(shí)參,則應(yīng)把形參變量說明為( B )參數(shù)。
A 指針
B 引用 C 值
D 變量
13、下面程序段的時(shí)間復(fù)雜度為( C ) for (int i=0;i<m;i++) for="" (int="" j="0;j<n;j++)" a[i][j]="i*j;" a="" o(m2)="" b="" o(n2)="" c="" o(m*n)="" d="" o(m+n)="" 14、下面程序段的時(shí)間復(fù)雜度為(="" )="" int="" f(unsigned="" n)="" {="" if(n="=0" ||="" n="=1)" return="" 1;="" 數(shù)據(jù)結(jié)構(gòu)與算法試題="" else="" n*f(n-1);="" }="" o(1)="" o(n)="" o(n="" !)="" 15、線性表若就是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí),要求內(nèi)存中可用存儲(chǔ)單元的地址(="" )。="" 必須就是連續(xù)的="" 部分地址必須就是連續(xù)的="" 一定就是不連續(xù)的="" 連續(xù)或不連續(xù)都可以="" 16、數(shù)據(jù)結(jié)構(gòu)的定義為(d,s),其中d就是(="" )的集合。="" 算法="" b數(shù)據(jù)元素="" 數(shù)據(jù)操作="" 邏輯結(jié)構(gòu)="" 17、算法分析的目的就是(="" 找出數(shù)據(jù)結(jié)構(gòu)的合理性="" 研究算法中輸入與輸出的關(guān)系="" 分析算法的效率以求改進(jìn)="" 分析算法的易懂性與文檔性="" 18、在一個(gè)單鏈表中,若p所指結(jié)點(diǎn)不就是最后結(jié)點(diǎn),在p之后插入s所指結(jié)點(diǎn),則執(zhí)行(="" 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->link=s; s->link=p C 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;
數(shù)據(jù)結(jié)構(gòu)與算法試題
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,link),且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;s為第一個(gè)結(jié)點(diǎn)硫
22、設(shè)單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data,link),且first為指向鏈表表頭的指針,current為鏈表當(dāng)前指針,在循環(huán)鏈表中檢測(cè)current就是否達(dá)到鏈表表尾的語句就是( D )。
A current->link =null B first->link=current C first=current D current->link=first
？23、一個(gè)棧的入棧序列為a,b,c,則出棧序列不可能的就是( C )。
A c,b,a B b,a,c C c,a,b D a,c,b 24、棧的數(shù)組表示中,top為棧頂指針,棧空的條件就是( A )。
A top=0 B top=maxSize C top=maxSize D top=-1 25、棧與隊(duì)列的共同特點(diǎn)就是( C )。
A 都就是先進(jìn)后出 B 都就是先進(jìn)先出 C 只允許在端點(diǎn)處插入與刪除 D 沒有共同點(diǎn)
26、假定一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列的隊(duì)頭與隊(duì)尾指針分別為f與r ,則判斷隊(duì)空的條件為( D )、 A f+1= =r
B r+1= =f
C f= =0
D f= =r
27、當(dāng)利用大小為n 的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí),該隊(duì)列的最大長(zhǎng)度為( B )
數(shù)據(jù)結(jié)構(gòu)與算法試題
A n-2
B n-1
C n D n+1
28、當(dāng)利用大小為n 的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí),假定用top= =n 表示?？?則向這個(gè)棧插入一個(gè)元素時(shí),首先應(yīng)執(zhí)行( )語句修改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 int Data Type; typedef struct {
Data Type data[Maxsize]; Int front, rear; } Queue;
若有一個(gè)Queue類型的隊(duì)列Q,試問判斷隊(duì)列滿的條件應(yīng)就是下列哪一個(gè)語句( D )
數(shù)據(jù)結(jié)構(gòu)與算法試題
的存儲(chǔ)位置就是( 1044)。
28、在插入與選擇排序中,若初始數(shù)據(jù)基本正序,則選擇(插入排序),若初始數(shù)據(jù)基本反序,則最好選擇(選擇排序)。
29、算法就是對(duì)特定問題的求解步驟的一種描述,它就是(指令)的有限序列,每一條(指令)表示一個(gè)或多個(gè)操作。
30、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)肯e 條邊的無向圖,進(jìn)行拓樸排序時(shí),總的進(jìn)間為(n) 31、構(gòu)造哈希函數(shù)有三種方法,分別為(平方取中)法、(除留余數(shù))法、(折迭移位)法。
32、處理沖突的三種方法,分別為(線性探測(cè))、( 隨機(jī)探測(cè) )、( 鏈地址法)。
33、對(duì)于含有n個(gè)頂點(diǎn)與e條邊的無向連通圖,利用普里姆算法產(chǎn)生的最小生成樹,其時(shí)間復(fù)雜度為( Ｏ(n2) )、利用克魯斯卡爾算法產(chǎn)生的最小生成樹,其時(shí)間復(fù)雜度為(Ｏ(elog2e) )
34、快速排序在平均情況下的時(shí)間復(fù)雜度為(Ｏ(nlog2n)),在最壞情況下的時(shí)間復(fù)雜度為(Ｏ(n2));快速排序在平均情況下的空間復(fù)雜度為(Ｏ(log2n)),在最壞情況下的空間復(fù)雜度為(Ｏ(n))。
35、假定一組記錄的排序碼為(４６,７９,５６,３８,４０,８０),對(duì)其進(jìn)行歸并排序的過程中,第二趟排序后的結(jié)果就是(［３８ ４６ ５６ ７９］［４０ ８０］)
36、假定一組記錄的排序碼為(４６,７９,５６,３８,４０,８０),對(duì)其進(jìn)行快速排序的第一次劃分的結(jié)果就是(［３８ ４０］４６［５６ ７９ ８０］)。
37、一個(gè)結(jié)點(diǎn)的子樹的( 個(gè)數(shù) )稱為該結(jié)點(diǎn)的度。度為( 零 )的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。度不為( 零 )的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。樹中各結(jié)點(diǎn)度的( 最大值 )稱為樹的度。
數(shù)據(jù)結(jié)構(gòu)與算法試題
38、設(shè)Ki=Kj (1<=i<=n, 1<=j<=n,j<>i)且在排序前的序列中Ri領(lǐng)先于Rj (i<j),若排序后的序列中ri仍領(lǐng)先于 rj,則這種排序方法就是(穩(wěn)定的),反之就是(不穩(wěn)定的)。="" 40="" 、在堆排序的過程中,對(duì)任一分支結(jié)點(diǎn)進(jìn)行調(diào)整運(yùn)算的時(shí)間復(fù)雜度為(Ｏ(log2n)),整個(gè)排序過程的時(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è)字母被劃分在一個(gè)子表中,則得到的a,b,c三個(gè)子表的長(zhǎng)度分別為(３),(３),(２)。="" 43、對(duì)于包含５０個(gè)關(guān)鍵碼的３階b-樹,其最小高度為(４),最大高度為(５)。="" 44、從一棵b-樹刪除關(guān)鍵碼的過程,若最終引起樹根結(jié)點(diǎn)的合并,則新樹比原樹的高度(減１)="" 45、假定要對(duì)長(zhǎng)度n="100的線性表進(jìn)行散列存儲(chǔ),并采用開散列法處理沖突,則對(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)的(入度)。在無向圖的鄰接矩陣中,第i行(列)中“1”的個(gè)數(shù)就是第i個(gè)頂點(diǎn)的(度),矩陣中“1”的個(gè)數(shù)的一半就是圖中的(邊數(shù))。="" 48、在對(duì)m階b-樹中,每個(gè)非根結(jié)點(diǎn)的關(guān)鍵碼數(shù)最少為(「m="" 2┐-1)個(gè),最多為(m-1)個(gè),其子樹棵數(shù)最少為(「m="" 2┐),最多為(m)。="" 數(shù)據(jù)結(jié)構(gòu)與算法試題="" 三、="" 判斷題="" 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ù)組元素為線性表的線性表(╳)。="" 7、="" 每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運(yùn)算:插入、刪除、搜索(√)。="" 8、="" 非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接前驅(qū)元素。(╳="" )="" 9、="" 空串與由空格組成的串沒有區(qū)別。(╳="" 10、將t在s中首次出現(xiàn)的位置作為t在s中的位置的操作稱為串的模式匹配。(√)="" 11、深度為h的非空二叉樹的第h層最多有2h-1個(gè)結(jié)點(diǎn)(╳="" 12、完全二叉樹就就是滿二叉樹。(╳)="" 13、已知一棵二叉樹的前序序列與中序序列可以唯一地構(gòu)造出該二叉樹。(√="" 14、帶權(quán)連通圖的最小生成樹的權(quán)值之與一定小于它的其它生成樹的權(quán)值之與。(√)="" 15、線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)就是邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也相鄰。(="" √="" 16、若有一個(gè)結(jié)點(diǎn)就是二叉樹中某個(gè)子樹的中序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn),="" 則它一定就是該子樹的前序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)。(√)="" 17、任一棵二叉搜索樹的平均搜索時(shí)間都小于用順序搜索法搜索同樣結(jié)點(diǎn)的順序表的平均搜索時(shí)間。(╳)="" 18、最優(yōu)二叉搜索樹一定就是平衡的二叉搜索樹。(√)="" 19、aoe網(wǎng)就是一種帶權(quán)的無環(huán)連通圖。(√="" 20、對(duì)于同一組待輸入的關(guān)鍵碼集合,雖然各關(guān)鍵碼的輸入次序不同,但得到的二叉搜索樹都就是相同的(╳)。="" 21、二叉排序樹可以就是一棵空樹(√="" 22、線性表中所有結(jié)點(diǎn)的類型必須相同。="" (√="" 23、n個(gè)結(jié)點(diǎn)的有向圖,若它有n(n－1)條邊,則它一定就是強(qiáng)連通的。(√="" 24、任何無環(huán)的有向圖,其結(jié)點(diǎn)都可以排在一個(gè)拓?fù)湫蛄欣铩?√="" 25、隊(duì)列邏輯上就是一個(gè)下端口與上端能增加又能減少的線性表(╳="" 26、二叉樹就是樹的一種特殊情況(="" 27、用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí),在不考慮壓縮存儲(chǔ)的情況下,所占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān),而與圖的邊數(shù)無關(guān)(√)。="" 28、鄰接表只能用于有向圖的存儲(chǔ),鄰接矩陣對(duì)于有向圖與無向圖的存儲(chǔ)都適用。(╳)="" 29、連通分量就是無向圖中的極小連通子圖。(╳)="" 30、在ＡＯＥ網(wǎng)絡(luò)中一定只有一條關(guān)鍵路徑。(╳)="" 31、關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間。(√)="" 32、平衡二叉樹的左右子樹深度之差的絕對(duì)值不超過1。(√="" 33、快速排序就是對(duì)起泡排序的一種改進(jìn)。(="" 34、直接選擇排序穩(wěn)定。(="" ╳="" 35、堆排序占用的輔助空間很大。(="" 36、在散列法中采取開散列法來解決沖突時(shí),其裝載因子的取值一定在(０,１)之間。(╳)="" 37、b-樹就是一種動(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-="" +="" 1個(gè)元素="" 2、當(dāng)一個(gè)棧的進(jìn)棧序列為1234567時(shí),可能的出棧序列有多少種？6457321就是否就是合理的出棧序列？="" 答案:="" 可能的出棧序列有="" 種,6457321不就是合理的出棧序列。="" 3、簡(jiǎn)單(直接)選擇排序就是一種穩(wěn)定的排序方法不？試舉例說明？="" 4291="" 234567891011121314811717="" 14=*************=+c數(shù)據(jù)結(jié)構(gòu)與算法試題="" (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、 寫出下列中綴表達(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||!&&!CE<||
8、 畫出下列廣義表的圖形表示與它們的存儲(chǔ)表示: (1) D(A(c), B(e), C(a, L(b, c, d)))
(2) J1(J2(J1, a, J3(J1)), J3(J1))
數(shù)據(jù)結(jié)構(gòu)與算法試題
答案:廣義表(1)的圖形表示為:
廣義表(2)的圖形表示為:
廣義表(1)的存儲(chǔ)表示為:
廣義表(2)的存儲(chǔ)表示為:
A
B C D
L c
e
a
b
c
d
J1
J3
J2 a
D
0 A 1 C ^ 0 B 1 e ^
A B
0 D
2
2
2 ^
0 C
1 a
2 ^
0 L
1 b
1 C
1 d ^
C L
0 J1
2
2 ^
0 J2
2
1 a
2 ^
0 J3
2 ^
J3
J2
J1
數(shù)據(jù)結(jié)構(gòu)與算法試題
9、題目:11、將下面的森林變換成二叉樹(7分)。
答案:
10、將算術(shù)表達(dá)式 ((a+b)+c*(d+e)+f)*(g+h) 轉(zhuǎn)化為二叉樹。(7分) 答案:
*
+
+
+
f
+ *
+
c b
a
h
g
A
C
D
B F
E
K
J
G
H
I
A
C
D
B
F
E
K
J
G
H
I
數(shù)據(jù)結(jié)構(gòu)與算法試題
11、根據(jù)所給有向圖,寫出一個(gè)拓?fù)湫蛄小?5分)
答案:
其中的一個(gè)拓?fù)湫蛄袨?V1,V2,V3,V4,V5,V6,V7
12、 將給定的圖簡(jiǎn)化為最小的生成樹,要求從頂點(diǎn)1出發(fā)。(7分)
答案:
1
3
2
5
4
7
6
1
3
2
5
4
7 6
8
5
15
3 10
12
2 7 9
6 1
3
2
5
4
7
6
5
15
3 6 2
7 數(shù)據(jù)結(jié)構(gòu)與算法試題
13、某子系統(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ì)赫夫曼編碼。
答案:
為方便起見,設(shè)各種字符的權(quán)值w={5,29,7,8,14,23,3,11}。因?yàn)閚=8,所以要構(gòu)造的赫夫曼樹共有m=2n-1=2*8-1=15個(gè)結(jié)點(diǎn)。生成的赫夫曼樹為下圖所示:
赫夫曼編碼為:概率為0、23的字符編碼為:00 概率為0、11的字符編碼為:010
概率為0、05的字符編碼為:0110
23
11
5
3
29 14
7 8
0 0
0
0 0 0 0 1 1
1
1 1 1 1 數(shù)據(jù)結(jié)構(gòu)與算法試題
概率為0、03的字符編碼為:0111 概率為0、29的字符編碼為:10
概率為0、14的字符編碼為:110 概率為0、07的字符編碼為:1110 概率為0、08的字符編碼為:1111
14、已知一棵二叉樹的前序遍歷的結(jié)果就是ABECDFGHIJ, 中序遍歷的結(jié)果就是EBCDAFHIGJ, 試畫出這棵二叉樹,并給出這棵二叉樹的后序遍歷序列。
答案:根據(jù)前序序列與中序序列能得到唯一的二叉樹,所得二叉樹如圖:
這棵二叉樹的后序遍歷序列為:EDCBIHJGFA
15、在結(jié)點(diǎn)個(gè)數(shù)為n(n>1)的各棵樹中,高度最小的樹的高度就是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？高度最大的樹的高度就是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？
答案:結(jié)點(diǎn)個(gè)數(shù)為n時(shí),高度最小的樹的高度為1,有2層;它有n-1個(gè)葉結(jié)點(diǎn),1個(gè)分支結(jié)點(diǎn);高度最大的樹的高度為n-1,有n層;它有1個(gè)葉結(jié)點(diǎn),n-1個(gè)分支結(jié)點(diǎn)。
16、 對(duì)于一個(gè)高度為h的AVL樹,其最少結(jié)點(diǎn)數(shù)就是多少？反之,對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的AVL樹, 其最大高度就是多少? 最小高度就是多少?
答案:設(shè)高度為h(空樹的高度為-1)的AVL樹的最少結(jié)點(diǎn)為Nh,則Nh = Fh+3 -1。
A
B
F G
E
C
D
H
J
I
數(shù)據(jù)結(jié)構(gòu)與算法試題
Fh 就是斐波那契數(shù)。又設(shè)AVL樹有n個(gè)結(jié)點(diǎn),則其最大高度不超過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í)的判定樹, 并計(jì)算搜索成功的平均搜索長(zhǎng)度與搜索不成功的平均搜索長(zhǎng)度。
____圖(1)____
答案:折半搜索時(shí)的判定樹為:
ASLSUCC=1/14(1+2*2+3*4+4*7)=45/14 ASLUNSUCC=1/15(3*1+4*14)=59/15
18、試對(duì)下圖所示的AOE網(wǎng)絡(luò)
(1) 這個(gè)工程最早可能在什么時(shí)間結(jié)束。
(2) 求每個(gè)事件的最早開始時(shí)間Ve[i]與最遲開始時(shí)間Vl[i]。
(3) 求每個(gè)活動(dòng)的最早開始時(shí)間e( )與最遲開始時(shí)間l( )。
(4) 確定哪些活動(dòng)就是關(guān)鍵活動(dòng)。畫出由所有關(guān)鍵活動(dòng)構(gòu)成的圖,指出哪些活動(dòng)加速可使整個(gè)工程提前完成。
509
154
677
017
275
170
503
094 553
897
512 612 765 908
數(shù)據(jù)結(jié)構(gòu)與算法試題
答案:按拓樸有序的順序計(jì)算各個(gè)頂點(diǎn)的最早可能開始時(shí)間Ve與最遲允許開始時(shí)間Vl,然后再計(jì)算各個(gè)活動(dòng)的最早可能開始時(shí)間e與最遲允許開始時(shí)間l,根據(jù)l-e就是否等于0來確定關(guān)鍵活動(dòng),從而確定關(guān)鍵路徑。
① ③ ② ④ ⑤ ⑥ Ve Vl
<1,2> <1,3> <3,2> <2,4> <2,5> <3,5> <4,6> <5,6> e 0 8 L 17 8 l-e
17
0
0
8
0
12
8
0
此工程最早完成時(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)用快速排序的方法將它們從小到大排列。
答案:
第一次排序:(076,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ù)不超過2次。試問散列表需要設(shè)計(jì)多大？ (設(shè)a就是散列表的裝載因子,則有ASLsucc = ( 1+1/ (1-a) )/2)。
數(shù)據(jù)結(jié)構(gòu)與算法試題
答案:已知要存儲(chǔ)的記錄數(shù)為n=150,查找成功的平均查找長(zhǎng)度為ASLsucc ≤2,則有:ASLsucc =1/2(1+1/(1-a))≤2 解得 a≤2/3 ,又有:a=n/m=150/m 兩式聯(lián)立得:150/m≤2/3,解得:m≥225、 所以散列表需要設(shè)計(jì)225個(gè)單位。
五、算法分析題
1、給出下列遞歸過程的執(zhí)行結(jié)果 void unknown ( int w ) {
if ( w ) {
unknown ( w-1 );
for ( int i = 1; i <= w; i++ ) cout << w<<' ';
cout << endl;
} }
調(diào)用語句為 unknown (4)。
答案:
(1) 1 2 2
3 3 3
4 4 4 4
2、給出遞歸過程的執(zhí)行結(jié)果 void unknown ( int n ) {
cout << n % 10 ;
if ( int ( n / 10 ) ) unknown ( int ( n / 10 ) );
數(shù)據(jù)結(jié)構(gòu)與算法試題
}
調(diào)用語句為unknown ( 582 )。
答案: 285
3、給出遞歸過程的執(zhí)行結(jié)果
int unknown ( int m ) {
int value;
if ( ! m ) value = 3;
else value = unknown ( m-1 ) + 5; return value;
}
執(zhí)行語句為 cout << unknown (3)。
答案: 18
4、 設(shè)有一個(gè)二維數(shù)組A[m][n],假設(shè)A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每個(gè)元素占一個(gè)空間,問A[3][3](10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。
答案:設(shè)數(shù)組元素A[i][j]存放在起始地址為L(zhǎng)oc(i,j)的存儲(chǔ)單元中。
因?yàn)?Loc(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=692 5、設(shè)單鏈表結(jié)構(gòu)為 struct ListNode {
int data ;
ListNode * link ;
};
數(shù)據(jù)結(jié)構(gòu)與算法試題
下面的程序就是以單鏈表為存儲(chǔ)結(jié)構(gòu), 實(shí)現(xiàn)二路歸并排序的算法, 要求鏈表不另外占用存儲(chǔ)空間, 排序過程中不移動(dòng)結(jié)點(diǎn)中的元素, 只改各鏈結(jié)點(diǎn)中的指針, 排序后r仍指示結(jié)果鏈表的第一個(gè)結(jié)點(diǎn)。在初始狀態(tài)下, 所有待排序記錄鏈接在一個(gè)以r為頭指針的單鏈表中。例如,
____圖(1)____
在算法實(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 ( );
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è)有序子鏈表即為所求。
在算法實(shí)現(xiàn)時(shí)有 6 處語句缺失,請(qǐng)閱讀程序后補(bǔ)上。
(1) 兩路歸并算法 void merge ( ListNode * ha, ListNode * hb,, ListNode *& hc ) {
ListNode *pa, *pb, *pc ;
if ( ha→data <= hb→data ) { hc = ha; pa = ha→link; pb = hb; }
數(shù)據(jù)結(jié)構(gòu)與算法試題
else { hc = hb; pb = hb→link; pa = ha ; } pc = hc;
while ( pa && pb )
if (
pa→data <= pb→data )
{
pc→link = pa; pc = pa;
pa = pa→link
;
}
else
{ pc→link = pb; pc = pb;
pb = pb→link
;
}
if ( pa ) pc→link = pa;
else pc→link = pb; };
(2) 歸并排序主程序 void mergesort ( ListNode * r ) { ListNode * s, t; Queue Q ;
if ( ! r ) return;
s = r; Q、EnQueue( r )
;
while ( s ) { t = s→link;
while ( t != 0 && s→data <= t→data ) { s = t; t = t→
link; }
if ( t ) {
s→link = 0; s = t;
Q、EnQueue( s )
;
數(shù)據(jù)結(jié)構(gòu)與算法試題
} }
while ( !Q、IsEmpty( ) ) { r = Q、DlQueue( );
if ( Q、IsEmpty( ) ) break;
s = Q、DlQueue( );
merge( r, s, t );
Q、EnQueue( t ) ;
}
}
6、請(qǐng)讀下列程序,該程序就是在單鏈表中刪除一個(gè)結(jié)點(diǎn)的算法,為空出的地方填上正確的語句。(7分)
void demo2(LinkList head,ListNode *p) {//head 就是帶頭結(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);
}
7、 已知一完全二叉樹從根結(jié)點(diǎn)開始,自頂向下,同一層自左向右連續(xù)編號(hào),根結(jié)
點(diǎn)的編號(hào)為0,閱讀以下程序請(qǐng)回答該程序所實(shí)現(xiàn)的功能: template
void linkedtosequent(Bintreenode *t,type a[ ],int i){ if (t!=Null){
數(shù)據(jù)結(jié)構(gòu)與算法試題
a[]=t->getData();
linkedtosequent(t->getleftchild(),a,2*i+1); linkedtosequent(t->getrightchild(),a,2*i+2); }}
主程序調(diào)用方式:linkedtosequent(t、root,a,0);
答案:該程序的功能就是:將用二叉鏈表表示的完全二叉樹轉(zhuǎn)換為二叉樹的順序(數(shù)組)表示。
8、設(shè)散列表為HT[13], 散列函數(shù)為 H (key) = key %13。用閉散列法解決沖突, 對(duì)下列關(guān)鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。
(1) 采用線性探查法尋找下一個(gè)空位, 畫出相應(yīng)的散列表, 并計(jì)算等概率下搜索成功的平均搜索長(zhǎng)度與搜索不成功的平均搜索長(zhǎng)度。
(2) 采用雙散列法尋找下一個(gè)空位, 再散列函數(shù)為 RH (key) = (7*key) % 10 + 1, 尋找下一個(gè)空位的公式為 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。畫出相應(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(78)=0,H(31)=5,H(15)=2,H(36)=10
利用線性探查法造表: 0 11 12 78 1 23 36 12 1
1
1
1
1
1
4
1
2
1
搜索成功的平均搜索長(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 利用雙散列法造表:
數(shù)據(jù)結(jié)構(gòu)與算法試題
Hi =(Hi-1 +RH(key))%13, Hi =H(key) 0 11 12 78 1 36 23 12 1
1
1
1
1
1
3
5
1
1
9、閱讀下面程序,指出其算法的功能并求出其時(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=1i!,該算法的時(shí)間復(fù)雜度為O(n)、
10、判斷一個(gè)帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表L就是否對(duì)稱相等的算法如下所示,請(qǐng)?jiān)谒惴ǖ?處填入正確的語句。
數(shù)據(jù)結(jié)構(gòu)與算法試題
int symmetry(DblList DL) { int sym=1;
DblNode p=DL->rLink,q=DL->lLink; While(p!=q&&p->lLink==q)&& sym==1 ) if (p->data==q->data){ p=p->rLink; q=q->lLink; }
else sym=0; return sym;} 11、閱讀下面程序,指出其算法的功能 #include “stack、h” int BaseTrans(int N,int B) { int i,result=0;StackS;
while(N!=0){i=N%B;N=N/B;S、Push(i);} while(!S、IsEmpty()){i=S、GetTop();S、Pop(); result=result*10+i;} return result; }
答案:該算法就是將一個(gè)非負(fù)的十進(jìn)制整數(shù)N轉(zhuǎn)換為另一個(gè)基數(shù)為B的B進(jìn)制數(shù)。
12、閱讀下面程序,指出其算法的功能 template
void BinaryTree::binsearchTree(BinTreeNode*t,int &bs) {
數(shù)據(jù)結(jié)構(gòu)與算法試題
if(t!=Null){
if((t->letfchild==Null||t->data>t->leftchild->data)&& (t->rightchild==Null||t->datarightchild->data)) { bs=1;
binsearchTree(t->leftchild,bs);
if(bs) binsearchTree(t->rightchild,bs); }
else bs=0; } }
答案:該算法就是判別給定的以二叉鏈表存儲(chǔ)的二叉樹就是否就是二叉搜索樹。采用遞歸算法,對(duì)樹中的所有結(jié)點(diǎn)檢查就是否左子樹上結(jié)點(diǎn)的關(guān)鍵碼都小于它的關(guān)鍵碼,右子樹上結(jié)點(diǎn)的關(guān)鍵碼都大于它的關(guān)鍵碼。如滿足上述條件,則就是二叉搜索樹。
六、綜合算法題
1、試設(shè)計(jì)一個(gè)實(shí)現(xiàn)下述要求的查找運(yùn)算函數(shù)Locate。設(shè)有一個(gè)帶表頭結(jié)點(diǎn)的雙向鏈表L, 每個(gè)結(jié)點(diǎn)有4個(gè)數(shù)據(jù)成員:指向前驅(qū)結(jié)點(diǎn)的指針llink、指向后繼結(jié)點(diǎn)的指針rlink,存放字符數(shù)據(jù)的成員data與訪問頻度freq。所有結(jié)點(diǎn)的freq 初始時(shí)都為0。每當(dāng)在鏈表上進(jìn)行一次Locate(L, x) 操作時(shí),令元素值為x的結(jié)點(diǎn)的訪問頻度freq加1,并將該結(jié)點(diǎn)前移,鏈接到與它的訪問頻度相等的結(jié)點(diǎn)后面,使得鏈表中所有結(jié)點(diǎn)保持按訪問頻度遞減的順序排列,以使頻繁訪問的結(jié)點(diǎn)總就是靠近表頭。
答案:
(1) 定義鏈表結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)與算法試題
struct DoubleListNode { char data ; int freq;
DoubleListNode * llink, *rlink ;
};
初始時(shí),所有結(jié)點(diǎn)的freq域的值都為0。
(2) 定義函數(shù)
DoubleListNode * locate ( DoubleListNode *f ; char &x ) { DoubleListNode * p, *q; p = f→rlink;
/*跳過表頭結(jié)點(diǎn)*/
while ( p != NULL && p→data != x ) p = p→rlink; /*搜索*/ if ( p ) {
p→freq ++; q = p→llink;
p→rlink→llink = q; q→rlink = p→rlink; /*從鏈中
摘下p*/
while ( q != f && q→freq < p→freq ) q =q→llink;
p→llink = q;
p→rlink = q→rlink; q→rlink→llink = p;
q→rlink = p; /*在q后面插入p*/
} return p;
}
2、已知A[n]為整數(shù)數(shù)組,試寫出實(shí)現(xiàn)下列運(yùn)算的遞歸算法:
(1) 求數(shù)組A中的最大整數(shù)。
數(shù)據(jù)結(jié)構(gòu)與算法試題
(2) 求n個(gè)整數(shù)的與。
(3) 求n個(gè)整數(shù)的平均值
答案:#include <iostream、h> class RecurveArray{ private: int *Elements; int ArraySize; int CurrentSize; public:
RecurveArray (int MaxSize=10):
ArraySize(MaxSize),Elements(new int[MaxSize]){ } ~ RecurveArray ( ){delete[ ] Elements;} void InputArray( ) ; int Maxkey(int n); int sum(int n); float Average (int n); };
void RecurveArray:: InputArray( ) { cout<<”Input the number of Array :\n”;
for (int i=0;i< ArraySize;i++) cin>> Elements[i]; }
int RecurveArray::Maxkey(int n) { if(n= =1) return Elements[0]; int temp= Maxkey(n-1);
數(shù)據(jù)結(jié)構(gòu)與算法試題
if(Elements[n-1]>temp) return Elements[n-1]; else return temp; }
int RecurveArray::Sum(int n) { if (n= =1) return Elements[0]; else return Elements[n-1]+Sum(n-1); }
float RecurveArray::Average(int n) { if (n= =1) return (float)Elements[0];
else return ((float) Elements[n-1]+(n-1)*Average(n-1))/n; }
int main(int argc, char *argv[ ]){ int size=1;
cout<<”No、of the Elements:”; while (size<1) cin>>size; RecurveArray ra(size); Ra、InputArray( );
Cout<<”\n The max is :”<<ra、maxkey(ra、maxsize)<<end1; cout<<”\n="" the="" sum="" is="" :”<<ra、="" (ra、maxsize)<<end1;="" ave="" :”<<ra、average(ra、maxsize)<<end1;="" return="" 0;="" }="" 3、="" 試編寫一個(gè)函數(shù)計(jì)算n!*2n的值,結(jié)果存放于數(shù)組a[arraysize]的第n個(gè)數(shù)="" 數(shù)據(jù)結(jié)構(gòu)與算法試題="" 組元素中,0="" ￡="" n="" arraysize。若設(shè)計(jì)算機(jī)中允許的整數(shù)的最大值為maxint,則當(dāng)n=""> arraySize或者對(duì)于某一個(gè)k (0 ￡ k ￡ n),使得k!*2k > maxInt時(shí),應(yīng)按出錯(cuò)處理?？捎腥缦氯N不同的出錯(cuò)處理方式: (1) 用cerr <<及exit (1)語句來終止執(zhí)行并報(bào)告錯(cuò)誤;
(2) 用返回整數(shù)函數(shù)值0, 1來實(shí)現(xiàn)算法,以區(qū)別就是正常返回還就是錯(cuò)誤返
回;
(3) 在函數(shù)的參數(shù)表設(shè)置一個(gè)引用型的整型變量來區(qū)別就是正常返回還就是
某種錯(cuò)誤返回。
用您認(rèn)為就是最好的方式實(shí)現(xiàn)它。
答案:#include “iostream、h” #define arraySize 100 #define MaxInt 0x7fffffff int calc (int t[ ],int n){ int i,edge=MaxInt/n/2; t[0]=1; if (n!=0) {
for (i=1;i<n;i++){ t[i]="t[i-1]*i*2;" if(t[i]="">edge) return 0; }
t[n]=t[n-1]*n*2; }
cout<<”t[“<<n<<”]=”<<t[n]<<end1; return="" 1;="" 數(shù)據(jù)結(jié)構(gòu)與算法試題="" }="" void="" main()="" {int="" a[arraysize];int="" i;="" for(i="0;i<arraySize;i++)" if(!calc(a,i)="" ){="" cout<<”failed="" at="" ”<<i<<”、”<<end1;="" break;}}="" 4、="" 編寫一個(gè)算法frequency,統(tǒng)計(jì)在一個(gè)輸入字符串中各個(gè)不同字符出現(xiàn)的頻度。用適當(dāng)?shù)臏y(cè)試數(shù)據(jù)來驗(yàn)證這個(gè)算法。="" 答案:="" include="" <iostream、h=""> include”string、h” const int charnumber=128;
void frequency(string&s,int C[ ]){ for(int i=0;i< charnumber;i++) C[i]=0; for( i=0;i< s、length();i++) C[atoi(s[i])]++; for( i=0;i< charnumber;i++)
if(C[i]>0) cout<<”(”<<i<<”):\t”<<c[i]<<”\t”; }="" 測(cè)試數(shù)據(jù)="" s="”cast" cast="" sat="" at="" a="" tasa\0”="" 測(cè)試結(jié)果="" c="" t="" 空格="" 2="" 7="" 4="" 5="" 5、="" 若矩陣am′n中的某一元素a[i][j]就是第i行中的最小值,同時(shí)又就是第j列中的最大值,則稱此元素為該矩陣的一個(gè)鞍點(diǎn)。假設(shè)以二維數(shù)組存放矩陣,試="" 數(shù)據(jù)結(jié)構(gòu)與算法試題="" 編寫一個(gè)函數(shù),確定鞍點(diǎn)在數(shù)組中的位置(若鞍點(diǎn)存在時(shí)),并分析該函數(shù)的時(shí)間復(fù)雜度="" 答案:int="" minmax(int="" a[="" ][="" ],const="" int="" m,const="" n)="" {="" *row="new" [m];="" *col="new" [n];="" i,j;="" for(i="0;i<m;i++){" row[i]="A[i][0];" for(j="1;j<n;j++)" if(a[i][j]<row[i])="" col[i]="A[0][j];" if(a[i][j]="">col[j]) col[j]=A[i][j]; }
for(i=0;i<m;i++){ for(j="0;j<n;j++)" if(row[i]="=col[j])" cout<<”the="" saddle="" point="" is="" :(“<<i<<”,”<<j<<”)”<<end1;="" delete[="" ]row;="" ]col;="" }="" 此算法有3個(gè)并列二重循環(huán),其時(shí)間復(fù)雜度為o(m*n)、="" 6、試編寫一個(gè)函數(shù),將一個(gè)有n個(gè)非零元素的整數(shù)一維數(shù)組a[n]拆分為兩個(gè)一維數(shù)組,使得a[="" ]中大于零的元素存放在b[="" ]中,小于零的元素存放在c[="" ]中。="" 數(shù)據(jù)結(jié)構(gòu)與算法試題="" 答案:="" void="" fenjie(int="" a[],int="" b[],int="" c[],int="" n,int="" &pb,int="" &pc){="" pb="pc=-1;" for(int="" k="0;k<n;k++)" if(a[k]="">0) B[++pb]=A[k]; else C[++pc]=A[k];}
7、已知在一維數(shù)組A[m+n]中依次存放著兩個(gè)順序表(a0, a1, 、、、 am-1,)與(b0, b1, 、、、 bn-1,),試編寫一個(gè)函數(shù),將數(shù)組中兩個(gè)順序表的位置互換,即交(b0, b1, 、、、 bn-1,)放在(a0, a1, 、、、 am-1,)的前面。
答案:#define mpn 20
typedef int DataType;
void inverse(DataType A[ ],int st, int ed); void exchange(DataType A[ ],int m, int n){ inverse(A,0,m+n-1); inverse(A,0,n-1); inverse(A,n,m+n-1); }
void inverse(DataType A[ ],int st, int ed){ int md=(st+ed)/2; for(int i=0;i<md-st;i++) {="" datatype="" temp="A[st+i];" a[st+i]="A[ed-i];" a[ed-i]="temp;}}" 8、="" 設(shè)有一個(gè)表頭指針為h的單鏈表。試設(shè)計(jì)一個(gè)算法,通過遍歷一趟鏈表,將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn),如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針h指向原鏈表的最后一個(gè)結(jié)點(diǎn)。="" 數(shù)據(jù)結(jié)構(gòu)與算法試題
____圖(1)____
答案:templatevoid List ::Inverse(){ if(first==Null) return ;
ListNode*p=first->link,*pr=Null; While(p!=Null){ First->link=pr;
Pr=first;first=p;p=p->link; }
first->link=pr; }
