大學(xué)《算法數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)試題及答案

時間：2017-04-19 11:48:47 算法與數(shù)據(jù)結(jié)構(gòu) 我要投稿

　　數(shù)據(jù)結(jié)構(gòu)是主體，通用算法是附屬(僅是查找,排序等)。以下是由陽光網(wǎng)小編整理關(guān)于大學(xué)《算法數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)試題的內(nèi)容，希望大家喜歡!

大學(xué)《算法數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)試題及答案

　　大學(xué)《算法數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)試題及答案(一)

　　算法設(shè)計(jì)題(每小題6分.共12分)

　　1.請寫出在循環(huán)隊(duì)列上進(jìn)行插入操作的算法。要求若插入成功則返目true，否則返回else.

　　循環(huán)隊(duì)列定義如下：

　　struet CyclicQueue {

　　ElemTy[ae elem[M]; //M為已定義過的整型常量，表示隊(duì)列數(shù)組空間長度

　　int rear,front; //rear指向隊(duì)尾元素后一個位置，front指向隊(duì)頭元索

　　int tag;

　　};

　　注意：當(dāng)front=rear且tag=0時，隊(duì)列空，當(dāng)front=rear且tag=1時，隊(duì)列滿，即隊(duì)列中已有M個元素.

　　bool EnCQueue(CyclicQueue& Q, ElemType x){ {/*編寫該函數(shù)體。/}

　　//在下面編寫函數(shù)體

　　2.已知二又樹中的結(jié)點(diǎn)類型Bin·rreeNode定義為：

　　slruct BinTreeNode {char data;BinTreeNode * left, * right;};

　　其中data為結(jié)點(diǎn)值域，left和righ~分別為指向左、右子女結(jié)點(diǎn)的指針域，根據(jù)下面函數(shù)聲明編寫出求一棵二叉樹中結(jié)點(diǎn)總數(shù)的遞歸算法，該總數(shù)值由函數(shù)返回.假定BT初始指

　　向這棵二又樹的.根結(jié)點(diǎn).

　　int BTreeCount(BinTreeNode* BT);

　　答案

　　算法設(shè)計(jì)題(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;

　　大學(xué)《算法數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)試題及答案(二)

　　1.設(shè)字符串類String具有下列操作：

　　int Length()const; //計(jì)算字符串的長度

　　chargetData(k); //提取字符串第k個字符的值

　　若字符串Tar的值為“ababcabcacbab“，的值為‘abcac”時，

　　(1)給出下面算法執(zhí)行后返回的結(jié)果，

　　(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;

　　}

　　返回結(jié)果：

　　算法功能：

　　2。已知二叉樹中的結(jié)點(diǎn)類型BinTrceNode定義為：

　　struct BinTreeNode {ElemType data; BinTreeNode * left, * right; }

　　其中data為結(jié)點(diǎn)值域，left和right分別為指向左、右子女結(jié)點(diǎn)的指針域.下面函數(shù)的功能是返回二又樹BT中值為X的結(jié)點(diǎn)所在的層號.根據(jù)題意按標(biāo)號把合適的內(nèi)容填寫到算法后面相應(yīng)標(biāo)號的位置.

　　int NodeLevel(BinTreeNode * BT, ElemType X)

　　if (BT==NULL) return -- 1; //空樹的層號為一1

　　else if (BT->data==X) return 0; //根結(jié)點(diǎn)的層號為o

　　//向于樹中查找X結(jié)點(diǎn)

　　else {

　　im cl =NodeLevel(BT->left, X);

　　if (cl>=0) (1)

　　iht e2= (2) ;

　　if ( (3) ) return c2+1;

　　//若樹中不存在K結(jié)點(diǎn)則返回一l

　　else return -1

　　}