數(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、采用順序搜索方法查找長度為n的順序表時(shí),搜索成功的平均搜索長度為( 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è)遞歸算法改為對應(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
答案:折半搜索時(shí)的判定樹為: ASLSUCC=1/14(1+2*2+3*4+4*7)=45/14 ASLUNSUCC=1/15(3*1+4*14)=59/15 18、試對下圖所示的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請用快速排序的方法將它們從小到大排列。 答案: 第一次排序:(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,查找成功的平均查找長度為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]存放在起始地址為Loc(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( )。
解決方法提示:
? 程序首先對待排序的單鏈表進(jìn)行一次掃描, 將它劃分為若干有序的子鏈表, 其表頭 指針存放在一個(gè)指針隊(duì)列中。
? 當(dāng)隊(duì)列不空時(shí), 從隊(duì)列中退出兩個(gè)有序子鏈表, 對它們進(jìn)行二路歸并, 結(jié)果鏈表的表頭指針存放到隊(duì)列中。
? 如果隊(duì)列中退出一個(gè)有序子鏈表后變成空隊(duì)列, 則算法結(jié)束。這個(gè)有序子鏈表即為所求。
在算法實(shí)現(xiàn)時(shí)有 6 處語句缺失,請閱讀程序后補(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、請讀下列程序,該程序就是在單鏈表中刪除一個(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ù)編號,根結(jié)
點(diǎn)的編號為0,閱讀以下程序請回答該程序所實(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。用閉散列法解決沖突, 對下列關(guān)鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。
(1) 采用線性探查法尋找下一個(gè)空位, 畫出相應(yīng)的散列表, 并計(jì)算等概率下搜索成功的平均搜索長度與搜索不成功的平均搜索長度。
(2) 采用雙散列法尋找下一個(gè)空位, 再散列函數(shù)為 RH (key) = (7*key) % 10 + 1, 尋找下一個(gè)空位的公式為 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。畫出相應(yīng)的散列表, 并計(jì)算等概率下搜索成功的平均搜索長度。
答案:使用散列函數(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
搜索成功的平均搜索長度為:
ASLsucc =1/10(1+1+1+1+1+1+4+1+2+1)=14/10 搜索不成功的平均搜索長度為:
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就是否對稱相等的算法如下所示,請?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ǔ)的二叉樹就是否就是二叉搜索樹。采用遞歸算法,對樹中的所有結(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
答案: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; }
