演算法與數據結構習題
❶ 數據結構與演算法題需要回答
《數據結構與演算法》模擬題
一、填空題：（共15分）（每空一分）
按照排序時，存放數據的設備，排序可分為<1> 排序和<2> 排序。內部排序和外部排序
圖的常用的兩種存儲結構是<3> 和<4> 。鄰接矩陣和鄰接表
數據結構中的三種基本的結構形式是<5> 線性結構 和<6> 樹型結構 、圖型結構<7> 。
一個高度為6的二元樹，最多有<8> 63 個結點。
線性查找的時間復雜度為：<9> O(n^2) ，折半查找的時間復雜度為：<10> O(nlogn) 、堆分類的時間復雜度為：<11> O(nlogn) 。
在採用散列法進行查找時，為了減少沖突的機會，散列函數必須具有較好的隨機性，在我們介紹的幾種散列函數構造法中，隨機性最好的是<12> 隨機數 法、最簡單的構造方法是除留余數法<13> 。
線性表的三種存儲結構是：數組、<14> 鏈表 、<15> 靜態鏈表 。
二、回答下列問題：（共30分）
現有如右圖的樹，回答如下問題：看不見圖
根結點有：
葉結點有：
具有最大度的結點：
結點的祖先是：
結點的後代是：
棧存放在數組A[m]中，棧底位置是m-1。試問：
棧空的條件是什麼？top=m-1
棧滿的條件是什麼？top=-1
數據結構和抽象數據型的區別與聯系：
數據結構（data structure)—是相互之間存在一種或多種特定關系的數據元素的集合。數據元素相互之間的關系稱為結構。
抽象數據類型（ADT）：是指一個數學模型（數據結構）以及定義在該模型（數據結構）上的一組操作。
❷ 數據結構與演算法的題目，怎麼做
首先，要能夠讀懂代碼，總結演算法的思想，搞清楚該題演算法是完成什麼功能，然後是填空也好，寫演算法結果也好，就不成問題了。要想提高的快，就得多練啊。同時教材中的相關演算法也要熟，好多是書中的原演算法
1. 在計算機中，演算法是指什麼？
答案：解題方案的准確而完整的描述。
2. 在下列選項中，哪個不是一個演算法一般應該具有的基本特徵？
說明：演算法的四個基本特徵是：可行性、確定性、有窮性和擁有足夠的情報。 答案：無窮性。
3. 演算法一般都可以用哪幾種控制結構組合而成？ 答案：順序、選擇、循環。 4. 演算法的時間復雜度是指？
答案：演算法執行過程中所需要的基本運算次數。 5. 演算法的空間復雜度是指？
答案：執行過程中所需要的存儲空間。 6. 演算法分析的目的是？
答案：分析演算法的效率以求改進。 7. 下列敘述正確的是（C）
A．演算法的執行效率與數據的存儲結構無關
B．演算法的空間復雜度是指演算法程序中指令（或語句）的條數 C．演算法的有窮性是指演算法必須能在執行有限個步驟之後終止 D．演算法的時間復雜度是指執行演算法程序所需要的時間 8. 數據結構作為計算機的一門學科，主要研究什麼？
答案：主要研究數據的邏輯結構、對各種數據結構進行的運算，以及數據的存儲結構。 9. 數據結構中與所使用的計算機無關的是數據的（C） A．存儲結構 B．物理結構
C．邏輯結構 D．物理和存儲結構 10. 下列敘述中，錯誤的是（B）
A．數據的存儲結構與數據處理的效率密切相關 B．數據的存儲結構與數據處理的效率無關
C．數據的存儲結構在計算機中所佔的空間不一定是連續的 D．一種數據的邏輯結構可以有多種存儲結構 11. 數據的存儲結構是指什麼？
答案：數據的邏輯結構在計算機中的表示。 12. 數據的邏輯結構是指？
答案：反映數據元素之間邏輯關系的數據結構。
13. 根據數據結構中各數據元素之間前後件關系的復雜程度，一般將數據結構分為？ 答案：線性結構和非線性結構。
14. 下列數據結構具有記憶功能的是（C） A．隊列 B．循環隊列 C．棧
D．順序表
15. 下列數據結構中，按先進後出原則組織數據的是（B） A．線性鏈表 B．棧
C．循環鏈表 D．順序表
❸ 數據結構與演算法判斷題
1、錯。存儲結構才依賴計算機
2、正確
3、正確
4、錯。鏈式存儲的插入刪除效率高
5、錯。順序的結點也可以是復雜類型
6、正確
7、正確。 a進，a出，b進，b出，c進，d進，d出，c出就可得到這個輸出。
8、錯誤。遞歸實際上是利用棧結構進行定義。
9、正確。
❹ 演算法與數據結構填空題
1、 3
2、 15 (2^k-1)
3、 129 (2^7-1-3+5)
4、 logn (完全二叉樹最小深度)
5、 前序遍歷(DLR), 中序遍歷(LDR), 後序遍歷(LRD)
6、 深度優先搜索法, 廣度優先搜索法
7、 Kruskal演算法, prim演算法
8、 e, e
❺ 數據結構與演算法選擇題！
第一題，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：例如：環形圖就不滿足，比如長方形，四個頂點，兩種遍歷都能訪問到每個頂點，但不是完全圖
❻ 演算法與數據結構試題 急用！！！
這是我寫的順序查找和二分查找代碼
#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;
}
❼ 求數據結構與演算法分析高人幫忙做下這幾道題目。（希望能給出正確答案，在此謝過！！！）
填空題
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)即可