大學《算法數據結構》復習試題及答案
數據結構是主體，通用算法是附屬(僅是查找,排序等)。以下是由陽光網小編整理關于大學《算法數據結構》復習試題的內容，希望大家喜歡!
大學《算法數據結構》復習試題及答案(一)
算法設計題(每小題6分.共12分)
1.請寫出在循環隊列上進行插入操作的算法。要求若插入成功則返目true，否則返回else.
循環隊列定義如下：
struet CyclicQueue {
ElemTy[ae elem[M]; //M為已定義過的整型常量，表示隊列數組空間長度
int rear,front; //rear指向隊尾元素后一個位置，front指向隊頭元索
int tag;
};
注意：當front=rear且tag=0時， 隊列空，當front=rear且tag=1時，隊列滿，即隊列中已有M個元素.
bool EnCQueue(CyclicQueue& Q, ElemType x){ {/*編寫該函數體。/}
//在下面編寫函數體
2.已知二又樹中的結點類型Bin·rreeNode定義為：
slruct BinTreeNode {char data;BinTreeNode * left, * right;};
其中data為結點值域，left和righ~分別為指向左、右子女結點的指針域，根據下面函數聲明編寫出求一棵二叉樹中結點總數的遞歸算法，該總數值由函數返回.假定BT初始指
向這棵二又樹的.根結點.
int BTreeCount(BinTreeNode* BT);
答案
算法設計題(2小題，每小題6‘分，共12分)
1.分步給分
if (Q. rear=Q, front && Q tag== 1) return false;
Q. elem[Q, rear] = x;
Q. rtar= (Q. rear+ 1) %M;
if(Q. rear== Q. front) Q. tag= 1;
return true;
2.分步給分
int BTreeCount(BinTreeNode * BT)
(
if(BT== NULL)
return O;
else
return BTreeCount ( BT->left) +BTreeCount(BT-> fight) + l;
大學《算法數據結構》復習試題及答案(二)
1.設字符串類String具有下列操作：
int Length()const; //計算字符串的長度
chargetData(k); //提取字符串第k個字符的值
若字符串Tar的值為“ababcabcacbab“，的值為‘abcac”時，
(1)給出下面算法執行后返回的結果，
(2)給出下面。算法的功能。
include "String, h"
int unknown(String& Tar, strlng& Pat) coast
{
for (int i<O; i<=Tar. LengthO-Pat. Length(); i++) {
iht j=O;
while (j<Pat. Length())
if (Tar. getOata(i+j) ==Pat. getData(j)) j+ +
else break;
if (j==Pat. Length()) return i;
return –1;
}
返回結果：
算法功能：
2。已知二叉樹中的結點類型BinTrceNode定義為：
struct BinTreeNode {ElemType data; BinTreeNode * left, * right; }
其中data為結點值域，left和right分別為指向左、右子女結點的指針域.下面函數的功能是返回二又樹BT中值為X的結點所在的層號.根據題意按標號把合適的內容填寫到算法后面相應標號的位置.
int NodeLevel(BinTreeNode * BT, ElemType X)
if (BT==NULL) return -- 1; //空樹的層號為一1
else if (BT->data==X) return 0; //根結點的層號為o
//向于樹中查找X結點
else {
im cl =NodeLevel(BT->left, X);
if (cl>=0) (1)
iht e2= (2) ;
if ( (3) ) return c2+1;
//若樹中不存在K結點則 返回一l
else return -1
}
}
(1)
(2)
(3)
3.假定一個有向無權圖采用鄰接矩陣存儲，請指出F面算法的功能。
Template<class Type>
void Graph<Type>::unknown(int i)
{
int d,j;
d=0;
for (j=0; j<CurremNodes; j++){ //CurremNodes為田中的頂點效
if (Edge[i][j]) {d++ ; Edge[i][j]=0; }
if (Edge[j][i]) {d+ +; Edge[j][i]=0; }
}
CurrentEdges-=d; //CurremEdges //為圖中的邊數
}
算法功能：
答案
1
返回結果，5
算法功能：字符串的模式匹配算法.
2.
(1)returncl+l
(2)NodeLevel(BT一>,right，X)
(3)<c2>=0)
3，從有向無權圖中刪除所有與頂點i相連的邊，包括出邊和人邊。
【大學《算法數據結構》復習試題及答案】相關文章：