數據與演算法期末試題

1. 數據結構與演算法選擇題！

第一題，DFS（深度優先遍歷）是一個遞歸演算法，在遍歷的過程中，先訪問的點被壓入棧底（棧是先進後出），再說：拓撲有序是指如果點U到點V有一條弧，則在拓撲序列中U一定在V之前。深度優先演算法搜索路徑恰恰是一條弧，棧的輸出是從最後一個被訪問點開始輸出，最後一個輸出的點是第一個被訪問的點。所以是逆的拓撲有序序列
第二題：無向圖路徑長度是指兩個頂點之間弧的條數，如果兩頂點路徑長度有2條弧，則有3個頂點例如A——B——C；
第三題：A：極小連通圖是一棵生成樹，只有N-1條邊，但是連通分量可能有N條邊，例如極小連通圖A—— B——C，連通分量「A」——B——C——「A」(這里的最後一個「A」跟第一個「A」一致）：；
B:你查下極大強連通子圖概念就明白了；
C:你看看第二題的例子就明白了，AC之間沒有弧，但他們是一個拓撲序列；
D：例如：環形圖就不滿足，比如長方形，四個頂點，兩種遍歷都能訪問到每個頂點，但不是完全圖

2. 求數據結構與演算法分析高人幫忙做下這幾道題目。（希望能給出正確答案，在此謝過！！！）

填空題
1. n-1
因為隊尾指針總是指向空。
2. 1
因為無向圖的鄰接矩陣是對稱的。
3. 61
元素數量=
(rear+max-front) 當front > rear
(front+max-rear) 當rear > front
4. 深度優先搜索演算法

5.

判斷題
1. F
二叉樹就可以用數組存儲。
2. F
當發生沖突時，它要在下一個位置找，但如果該位置已被佔用，仍需要繼續向前。故同

義詞不一定相鄰。
3. F
圖的鄰接矩陣的行列數只取決於頂點數量。
4. F
沒有最快的排序演算法，只有特定條件下的相對較快。
5. T

選擇題
1. D
2. B
Loc(a[6]) = Loc(a[1]) + (6-1)*2
= 90 + 10 =100
3. A
4. C
5. C
進堆排序時，每個元素在最底下的葉子層都有，然後較大的非葉子結點存儲。

6. C
構造一棵二叉樹：
/
* +
A + - F
B C D E
對該二叉樹進行後序遍歷即可。

7. C
折半查找要求查找表有序，並且可以根據下標定位，要求是直接存取。
順序存儲方式：可直接存取，但插入刪除需耗時間
鏈式存儲方式：只能順序存取，插入刪除方便

8. D
二次探測再散列法：
addr(key) = (初始哈希值+di)%表長
di=1、-1、4、-4、9、-9...

addr(15) = 15 % 11 = 4
addr(38) = 38 % 11 = 5
addr(61) = 61 % 11 = 6
addr(84) = 84 % 11 = 7

addr(49) = 49 % 11 = 5 有沖突
addr(49) = (5+1)%14=6 有沖突
addr(49) = (5-1)%14=4 有沖突
addr(49) = (5+4)%14=9

9. D
執行p的後繼指針(next)指向p的直接後繼結點(next)的下一個結點(next)即可

3. 數據結構與演算法判斷題

1、錯。存儲結構才依賴計算機
2、正確
3、正確
4、錯。鏈式存儲的插入刪除效率高
5、錯。順序的結點也可以是復雜類型
6、正確
7、正確。 a進，a出，b進，b出，c進，d進，d出，c出就可得到這個輸出。
8、錯誤。遞歸實際上是利用棧結構進行定義。
9、正確。

4. 求北郵數據結構和演算法歷年期末考題~~~~郵箱[email protected]

2005年http://wenku..com/view/87ffa663caaedd3383c4d37f.html
2006年http://wenku..com/view/fe0dd56427d3240c8447ef7f.html
數據結構的。其他年的宿舍樓下列印店也都有

5. 數據結構與演算法試題，高分，求答案啊

給你第一題解法吧：後面的實在是不想做。

先根：ABCDEFGHI

中根：CBEDAGFHI

遍歷的基本方法：先左子樹後右子樹。

1,先根遍歷可以確定根節點為A,

2,依據1步，可以在中根遍歷中確定左子樹為：CBED,右為：GFHI

3,在可以重復1,2步。就可以得到結果。

A

BF

CDGH

I

4,O(n^3)+O(1)

6. 演算法與數據結構試題 急用！！！

這是我寫的順序查找和二分查找代碼
#include<iostream.h>
#define elemtype int

int sqsearch(elemtype a[],int n,elemtype x); //順序查找
int sqsearch2(elemtype a[],int n,elemtype x); //順序查找，列印查找過程
int binsearch(elemtype a[],int n,elemtype x); //折半查找
int binsearch2(elemtype a[],int n,elemtype x); //折半查找，列印查找過程

void printarray(elemtype a[],int n); //列印數組數據

int main()
{
int i,x;
const int n=9;
elemtype a1[10]={0,34,23,12,56,90,78,89,45,67};
elemtype a2[10]={0,12,23,34,45,56,67,78,89,90};

//順序查找
cout<<"順序查找："<<endl;
cout<<"a1[]=";
printarray(a1,n);
cout<<"輸入要查找的數據：";
cin>>x;
if((i=sqsearch(a1,n,x))>0) //找到
cout<<"找到x==a1["<<i<<"]"<<endl;
else //未找到
cout<<"找不到"<<x<<endl;
cout<<endl<<"查找過程："<<endl;
sqsearch2(a1,n,x); //查找過程
cout<<"完成順序查找！"<<endl;
//二分法查找
cout<<"二分法查找："<<endl;
cout<<"a2[]=";
printarray(a2,n);
cout<<"輸入要查找的數據：";
cin>>x;
if((i=binsearch(a2,n,x))>0) //找到
cout<<"找到x==a1["<<i<<"]"<<endl;
else //未找到
cout<<"找不到"<<x<<endl;
cout<<endl<<"查找過程："<<endl;
binsearch2(a2,n,x);
cout<<"完成順序查找！"<<endl;
return 0;
}

//在數組a[1.2...n]中順序查找x
//找到時返回元素下標，否則返回0
int sqsearch(elemtype a[],int n,elemtype x) //a[]是數組，n是元素個數，x是要查找的數
{
int i;
if(a[0]==x)
return 1;
else
{
a[0]=x;
for(i=n;!(a[i]==x);--i); //若找到則i大於0
return i;
}
}

//在數組a[1.2...n]中順序查找x,列印每次比較結果
//找到時返回元素下標，否則返回0
int sqsearch2(elemtype a[],int n,elemtype x) //a[]是數組，n是元素個數，x是要查找的數
{
int i;
a[0]=x;
for(i=n;!(a[i]==x);--i)
if(a[i]>x)
cout<<a[i]<<">"<<x<<endl;
else
cout<<a[i]<<"<"<<x<<endl;
return i;
}

//在數組a[1.2...n]中二分法查找x
//找到時返回元素下標，否則返回0
//前提：a[1.2...n]是非遞減有序的
int binsearch(elemtype a[],int n,elemtype x) //二分查找
{
int mid,low=1,high=n;
while(low<=high)
{
mid=(low+high)/2;
if(x==a[mid])
return mid;
else if(x<a[mid])
high=mid-1;
else
low=mid+1;
}
return 0;
}

//在數組a[1.2...n]中二分法查找x，每次列印比較結果
//找到時返回元素下標，否則返回0
//前提：a[1.2...n]是非遞減有序的
int binsearch2(elemtype a[],int n,elemtype x) //查找過程
{
int mid,low=1,high=n;
while(low<=high)
{
mid=(low+high)/2;
if(x==a[mid])
{
cout<<a[mid]<<"="<<x<<endl;
return mid;
}
else if(x<a[mid])
{
cout<<a[mid]<<">"<<x<<endl;
high=mid-1;
}
else
{
cout<<a[mid]<<"<"<<x<<endl;
low=mid+1;
}
}
return 0;
}

//列印順組數據a[1....n]
void printarray(int a[],int n)
{
int i;
cout<<"{";
for(i=0;i<=n;i++)
{
cout<<a[i];
while(i<n)
{
cout<<",";
break;
}
}
cout<<"}"<<endl;
}