數據演算法題
❶ 數據結構演算法題
int BTreeCount(BinTreeNode* BT, char x){
if(BT){
if(BT->data>x) return BTreeCount(BT->left,x)+BTreeCount(BT->right,x)+1;
else return BTreeCount(BT->left,x)+BTreeCount(BT->right,x);
}}
❷ 求數據結構與演算法分析高人幫忙做下這幾道題目。（希望能給出正確答案，在此謝過！！！）
填空題
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)即可
❸ 數據結構與演算法選擇題
1.A
存取任一指定序號，用順序表最方便，在最後進行插入和刪除運算，順序表也可以方便的實現。
2.C
第一個是5，第二個是4，都可以，表示5、4是最後進棧的，之後再要出棧1，不可能
3.D
4.C
5.A
生成樹
6.D
二分查找的前提是該查找必須是順序存儲的有序表
7.C
8.不清楚
9.B
abc,cba正好倒過來。
10.B
❹ 有三道數據結構演算法與分析的題不太明白，求助達人幫忙。在此十分感謝！！！
1 根據一組記錄（56，42，50，64，48）依次插入結點生成一棵AVL樹，當插入到值為___50___的結點時需要進行旋轉調整。
2、函數實現單鏈表的刪除演算法，請在空格處將演算法補充完整。
int ListDelete(LinkList L,int i,ElemType *s){
LNode *p,*q;
int j;
p=L;j=0;
while(( p->next__)&&(j<i-1)){
p=p->next;j++;
}
if(p->next==NULL||j>i-1) return ERROR;
q=p->next;
p->next=q->next ;
*s=q->data;
free(q);
return OK;
}/*listDelete*/
____p->next____ ； _____p->next=q->next ____
3、描述下面演算法的功能
int fun(sqstring *s,sqstring *t,int start)
{ int i=start-1,j=0;
while(i<s->len&&j<t->len)
if(s->data[i]==t->data[j]){
i++;j++;
}
else{
i=i-j+1;j=0;
}
if(j>=t->len)
return i-t->len+1;
else
return -1;
}
這是字元串的模式匹配。在主串S中尋找與子串T匹配的串，如果找到匹配的串，就返回這個子串的首元素下標值，否則返回-1
❺ 數據結構演算法 試題 急！ 試構造下圖的最小生成樹，要求分步給出構造過程。
圖有如下參數:
邊數=8頂點數=5
頂點頂點邊的權值
v1v26
v1v34
v1v42
v2v35
v2v48
v2v56
v3v45
v4v57
用Kruskal(克魯斯卡爾)演算法,求最小生成樹.
先將所有邊的權值按照從小到大排序:
頂點頂點邊的權值
v1v42
v1v34
v2v35
v3v45
v1v26
v2v56
v4v57
v2v48
然後,每次提取權值最小邊,逐步組成最小生成樹:
(1)取最小邊(v1,v4,2)
v1--v4
(2)取邊(v1,v3,4),不會產生環路.
v1--v4
|
|
v3
(3)取邊(v2,v3,5),不會產生環路.
v1--v4
|
|
v3--v2
(4)如果取邊(v3,v4,5),會產生環路,所以不能取.
如果取邊(v1,v2,6),會產生環路,所以不能取.
取邊(v2,v5,6),不會產生環路.
v1--v4
|
|
v3--v2--v5
這就是最小生成樹,連通了所有頂點,總權值最小.
頂點邊的權值
(v1,v4)2
(v1,v3)4
(v2,v3)5
(v2,v5)6
//C語言測試程序
//最小生成樹Kruskal(克魯斯卡爾)演算法
#include"stdio.h"
#defineMAXEDGE20
#defineMAXVEX20
#defineINF65535
typedefstruct
{
intarc[MAXVEX][MAXVEX];
intnumVertexes,numEdges;
}MGraph;
typedefstruct
{
intbegin;
intend;
intweight;
}Edge;//對邊集數組Edge結構的定義
//創建圖
voidCreateMGraph(MGraph*G)
{
inti,j;
G->numEdges=8;//邊數
G->numVertexes=5;//頂點數
for(i=0;i<G->numVertexes;i++)//初始化圖
{
for(j=0;j<G->numVertexes;j++)
{
if(i==j)
G->arc[i][j]=0;
else
G->arc[i][j]=G->arc[j][i]=INF;
}
}
G->arc[0][1]=6;
G->arc[0][2]=4;
G->arc[0][3]=2;
G->arc[1][2]=5;
G->arc[1][3]=8;
G->arc[1][4]=6;
G->arc[2][3]=5;
G->arc[3][4]=7;
for(i=0;i<G->numVertexes;i++)
{
for(j=i;j<G->numVertexes;j++)
{
G->arc[j][i]=G->arc[i][j];
}
}
}
//交換權值以及頭和尾
voidSwapn(Edge*edges,inti,intj)
{
inttemp;
temp=edges[i].begin;
edges[i].begin=edges[j].begin;
edges[j].begin=temp;
temp=edges[i].end;
edges[i].end=edges[j].end;
edges[j].end=temp;
temp=edges[i].weight;
edges[i].weight=edges[j].weight;
edges[j].weight=temp;
}
//對權值進行排序(選擇排序法)
voidsort(Edgeedges[],MGraph*G)
{
inti,j,min;
for(i=0;i<(G->numEdges-1);i++)
{
min=i;
for(j=i+1;j<G->numEdges;j++)
{
if(edges[min].weight>edges[j].weight)
{
min=j;
}
}
if(i!=min)
{
Swapn(edges,i,min);
}
}
printf("邊的權值排序之後: ");
for(i=0;i<G->numEdges;i++)
{
printf("(%d,%d)%d ",edges[i].begin,edges[i].end,edges[i].weight);
}
}
//查找連線頂點的尾部下標
intFind(int*parent,intf)
{
while(parent[f]>0)
{
f=parent[f];
}
returnf;
}
//生成最小生成樹
voidMiniSpanTree_Kruskal(MGraphG)
{
inti,j,n,m;
intk=0;
intparent[MAXVEX];//定義一數組用來判斷邊與邊是否形成環路
Edgeedges[MAXEDGE];//定義邊集數組,edge的結構為begin,end,weight,均為整型
//用來構建邊集數組並排序
for(i=0;i<G.numVertexes-1;i++)
{
for(j=i+1;j<G.numVertexes;j++)
{
if(G.arc[i][j]<INF)
{
edges[k].begin=i;
edges[k].end=j;
edges[k].weight=G.arc[i][j];
k++;
}
}
}
sort(edges,&G);//從小到大排序
for(i=0;i<G.numVertexes;i++)
{
parent[i]=0;
}
printf("列印最小生成樹： ");
for(i=0;i<G.numEdges;i++) //循環每一條邊
{
n=Find(parent,edges[i].begin);
m=Find(parent,edges[i].end);
if(n!=m)//假如n與m不等，說明此邊沒有與現有的生成樹形成環路
{
parent[n]=m; //將此邊的結尾頂點放入下標為起點的parent中
//表示此頂點已經在生成樹集合中
printf("(%d,%d)%d ",edges[i].begin,edges[i].end,edges[i].weight);
}
}
}
intmain(void)
{
MGraphG;
CreateMGraph(&G);
MiniSpanTree_Kruskal(G);
return0;
}
❻ 數據結構與演算法題需要回答
《數據結構與演算法》模擬題
一、填空題：（共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）：是指一個數學模型（數據結構）以及定義在該模型（數據結構）上的一組操作。
❼ 數據結構與演算法試題，高分，求答案啊
給你第一題解法吧：後面的實在是不想做。
先根：ABCDEFGHI
中根：CBEDAGFHI
遍歷的基本方法：先左子樹後右子樹。
1,先根遍歷可以確定根節點為A,
2,依據1步，可以在中根遍歷中確定左子樹為：CBED,右為：GFHI
3,在可以重復1,2步。就可以得到結果。
A
BF
CDGH
I
4,O(n^3)+O(1)
