- 相關(guān)推薦
2001數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)真題
試題內(nèi)容:一、試給出下列有關(guān)并查集(mfsets)的操作序列的運(yùn)算結(jié)果：
union(1,2) , union(3,4) , union(3,5) , union(1,7) , union(3,6) , union(8,9) , union(1,8) , union(3,10) , union(3,11) , union(3,12) , union(3,13) , union(14,15) , union(16,0) , union(14,16) , union(1,3) , union(1,14)。（union是合并運(yùn)算，在以前的書中命名為merge）
要求
(1) 對于union(i,j)，以i作為j的雙親； （5分）
(2) 按i和j為根的樹的高度實(shí)現(xiàn)union(i,j)，高度大者為高度小者的雙親； （5分）
(3) 按i和j為根的樹的結(jié)點(diǎn)個(gè)數(shù)實(shí)現(xiàn)union(i,j)，結(jié)點(diǎn)個(gè)數(shù)大者為結(jié)點(diǎn)個(gè)數(shù)小者的雙親； （5分）
二、設(shè)在4地（A,B,C,D）之間架設(shè)有6座橋,如圖所示:
要求從某一地出發(fā),經(jīng)過每座橋恰巧一次,最后仍回到原地
(1) 試就以上圖形說明:此問題有解的條件是什么? (5分)
(2) 設(shè)圖中的頂點(diǎn)數(shù)為n,試用C或Pascal描述與求解此問題有關(guān)的數(shù)據(jù)結(jié)構(gòu)并編寫一個(gè)算法,找出滿足要求的一條回路. (10分)
三、針對以下情況確定非遞歸的歸并排序的運(yùn)行時(shí)間(數(shù)據(jù)比較次數(shù)與移動次數(shù)):
(1) 輸入的n個(gè)數(shù)據(jù)全部有序; (5分)
(2) 輸入的n個(gè)數(shù)據(jù)全部逆向有序; (5分)
(3) 隨機(jī)地輸入n個(gè)數(shù)據(jù). (5分)
四、簡單回答有關(guān)AVL樹的問題.
(1) 在有N個(gè)結(jié)點(diǎn)的AVL樹中,為結(jié)點(diǎn)增加一個(gè)存放結(jié)點(diǎn)高度的數(shù)據(jù)成員,那么每一個(gè)結(jié)點(diǎn)需要增加多少個(gè)字位(bit)? (5分)
(2) 若每一個(gè)結(jié)點(diǎn)中的高度計(jì)數(shù)器有8bit,那么這樣的AVL樹可以有多少層?最少有多少個(gè)關(guān)鍵碼? (5分)
五、設(shè)一個(gè)散列表包含hashSize=13個(gè)表項(xiàng),.其下標(biāo)從0到12,采用線性探查法解決沖突. 請按以下要求,將下列關(guān)鍵碼散列到表中.
10 100 32 45 58 126 3 29 200 400 0
(1) 散列函數(shù)采用除留余數(shù)法,用%hashSize(取余運(yùn)算)將各關(guān)鍵碼映像到表中. 請指出每一個(gè)產(chǎn)生沖突的關(guān)鍵碼可能產(chǎn)生多少次沖突. (7分)
(2) 散列函數(shù)采用先將關(guān)鍵碼各位數(shù)字折疊相加, 再用%hashSize將相加的結(jié)果映像到表中的辦法. 請指出每一個(gè)產(chǎn)生沖突的關(guān)鍵碼可能產(chǎn)生多少次沖突.;(8分)
六、設(shè)一棵二叉樹的結(jié)點(diǎn)定義為
struct BinTreeNode{
ElemType data;
BinTreeNode *leftChild, *rightChild;
}
現(xiàn)采用輸入廣義表表示建立二叉樹. 嚀騫娑ㄈ縵?
(1) 樹的根結(jié)點(diǎn)作為由子樹構(gòu)成的表的表名放在表的最前面;
(2) 每個(gè)結(jié)點(diǎn)的左子樹和右子樹用逗號隔開. 若僅有右子樹沒有左子樹, 逗號不能省略.
(3) 在整個(gè)廣義表表示輸入的結(jié)尾加上一個(gè)特殊的符號(例如”#”)表示輸入結(jié)果.
例如,對于如右圖所示的二叉樹, 其廣義表表示為A(B(D,E(G,)),C(,F))
A
/
B C
/
D E F
/
G
此算法的基本思路是:依次從保存廣義表的字符串ls中輸入每個(gè)字符. 若遇到的是字母(假定以字母作為結(jié)點(diǎn)的值), 則表示是結(jié)點(diǎn)的值, 應(yīng)為它建立一個(gè)新的結(jié)點(diǎn), 并把該結(jié)點(diǎn)作為左子女(當(dāng)k=1)或有子女(當(dāng)k=2)鏈接到其雙親結(jié)點(diǎn)上. 若遇到的是左括號”(“, 則表明子表的開始,將k置為1;若遇到的是右括號”)”, 則表明子表結(jié)果. 若遇到的是逗號”,”, 則表示以左子女為根的子樹處理完畢,應(yīng)接著處理以右子女為根的子樹, 將k置為2.
在算法中使用了一個(gè)棧s, 在進(jìn)入子表之前,將根結(jié)點(diǎn)指針進(jìn)棧, 以便括號內(nèi)的子女鏈接之用. 在子表處理結(jié)束時(shí)退棧. 相關(guān)的棧操作如下:
MakeEmpty(s) 置空棧
Push(s,p) 元素p進(jìn)棧
Pop(s) 進(jìn)棧
Top(s) 存取棧頂元素的函數(shù)
下面給出了建立二叉樹的算法, 其中有5個(gè)語句缺失. 請閱讀此算法并把缺失的語句補(bǔ)上. (每空3分)
Void CreateBinTree(BinTreeNode *&BT, char ls){
Stack<BinTreeNode*>s; MakeEmpty(s);
BT=NULL; //置二叉樹
BinTreeNode *p;
int k;
istream ins(ls); //把串ls定義為輸入字符串流對象ins
Char ch;
ins>>ch; //從ins順序讀入一個(gè)字符
While(ch!=”#”){ //逐個(gè)字符處理,直到遇到’#’為止
Switch(ch){
case’(‘: _______(1)_______
k=1;
break;
case’)’: pop(s);
break;
case’,‘: _______(2)_______
break;
default: p=new BinTreeNode;
_______(3)_______
p->leftChild=NULL;
p->rightChild=NULL;
if(BT==NULL)
_______(4)_______
else if (k==1) top(s)->leftChild=p;
else top(s)->rightChild=p;
}
_______(5)_______
}
}
七、下面是一個(gè)用C編寫的快速排序算法. 為了避免最壞情況,取基準(zhǔn)記錄pivot采用從left,right和mid=[(left+right)/2]中取中間值, 并交換到right位置的辦法. 數(shù)組a存放待排序的一組記錄, 數(shù)據(jù)類型為Type, left和right是呆排序子區(qū)間的最左端點(diǎn)和最右端點(diǎn).
Void quicksort(Type a&#;,int left,int right){
Type temp;
If(left<right){
Type pivot=median3(a,left,right);
Int I=left, j=right-1;
For( ; ; ){
While(i<j && a[i]<pivot) i++;
While(i<j && pivot<a[j]) j--;
if(i<j){
temp=a[i]; a[j]=a[i]; a[i]=temp;
I++; j--;
}
else break;
}
if(a[i]>pivot)
{temp=a[i]: a[i]=a[right]; a[right]=temp;}
quicksort(a,left,i-1); //遞歸排序左子區(qū)間
quicksort(a,i+1,right); //遞歸排序右子區(qū)間
}
}
(1) 用C或Pascal實(shí)現(xiàn)三者取中子程序 median3(a,left,right); (5分)
(2) 改寫 quicksort 算法, 不用棧消去第二個(gè)遞歸調(diào)用 quicksort(a,i+1,right); (5分)
(3) 繼續(xù)改寫 quicksort 算法, 用棧消去剩下的遞歸調(diào)用. (5分) http://krishna123.com/
【數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)真題】相關(guān)文章：
UPS面試真題07-18
奔馳面試真題07-18
聯(lián)想面試真題07-18
華爾街的面試真題07-24
寶潔筆試面試真題02-10
康佳2014面試真題07-19
建行筆試真題07-31
農(nóng)信社筆試真題10-27
事業(yè)單位面試真題02-11
HTC面試真題（帶有答案）07-20