1、 共10 PAGE 5*2 頁 第 = PAGE 5*2-1 9 PAGE 5*2-1 頁 共10 PAGE 5*2 頁 第 PAGE 5*2 PAGE 5*2-1 頁20232023學年第二學期閩江學院期末試卷考試課程：?數據結構與算法?試卷類別：A卷 B卷 考試形式：閉卷 開卷適用專業年級：13級金融效勞、13級軟件效勞 裝 裝 訂 線題號一二三總分得分一、單項選擇題60%請將答案填入答題卡相應位置，30題，每題2分，共60分得分1、計算機算法必須具備輸入、輸出和 等5個特性。 A可行性、可移植性和可擴充性 B可行性、確定性和有窮性 C確定性、有窮性和穩定性 D易讀性、穩定性和平安性 2、

2、設語句x+的時間是單位時間，那么以下語句的時間復雜度為。 for(i=1; ilast是表尾結點指針。假設想刪除鏈表的首元結點，那么應執行以下操作？ As = L-last; L-last= L-last-next; free(s); BL-last= L-last-next; free(L-last); CL-last= L-last-next-next; free(L-last); Ds = L-last-next-next; L-last-next-next = s-next; free(s);7、帶頭結點的單鏈表L為空的判定條件是 AL-next = NULL; BL!= NULL;

3、CL-next= L; DL= NULL; 8、設結點結構為(prior,data,next)，L是不帶頭結點循環雙鏈表，L是表頭結點指針。假設想刪除循環雙鏈表中p結點的后繼結點(假設存在)，那么應執行以下操作？ Ap-next =p-next-next; Bp-next = p-next-next; p-next-prior = p; Cp-next = p-next-next; p-next-next-prior = p;Dp-next-prior = p; p-next = p-next-next;9、假設在線性表中經常涉及插入刪除操作，那么采用以下哪種表進行元素存儲比較好？A有序表 B

4、順序表 C鏈表 D棧10、在一個長度為n的順序表中插入第i個元素(1=ivexnum), &(G-arcnum);/輸入圖的頂點數與弧數/構造頂點數組for(i=0; ivexnum; i+)getchar();/吸收輸入的回車符scanf(%c, _(1)_);/輸入圖的頂點信息_(2)_;/構造邊結點for(k=0; karcnum; k+)getchar();/吸收回車符scanf(%c,%c, &v1,&v2);/輸入弧的兩個端點i=LocateVex(G,v1);/起點的編號j=LocateVex(G,v2);/終點的編號pi=_(3)_; pi-adjvex=_(4)_;pi-ne

5、xtarc=_(5)_;G-verticesi.firstarc=pi;(1) A&(G-verticesj.data) B. &(G-verticesi.data)C. &(G-verticesj.adjvex) D. &(G-verticesi.adjvex)(2) AG-vexnum+ B.此處不需要添加代碼C. G-datai.firstarc=NULL D. G-verticesi.firstarc=NULL(3) Anew Node B. new VNodeC. new ArcNode D. new ALGraph(4) AiB.j C.v1 D.v2(5) AG-vertices

6、i.firstarcB. G-verticesj.firstarcC. G-verticesi.nextarcD. G-verticesj.nextarc三、填空題30%請將答案填入答題卡相應位置，除第3題第一空為4分外，其余都為2分，共30分得分1、記錄 (46,74,53,14,26,38,86,65,27,34)，請給出歸并排序的第一趟排序結果(以第一個元素作為基準)：_2、從一棵二叉排序樹中查找一個元素時，假設元素的值大于根結點的值，那么繼續向_查找。3、假設一棵二叉樹的后序序列為DCEGBFHKJIA，中序序列為DCBGEAHFIJK，請畫出該二叉樹_(4分)，并寫出該二叉樹的先序遍

7、歷序列_。4、二叉樹的二叉鏈表表示法定義如下：typedef char TElemType;typedef struct BiTnodeTElemType data; struct BiTnode *lchild, *rchild;BiTNode, *BiTree;請將以下二叉樹的查找算法補充完整：int LocateElem(BiTree T, TElemType e)/e為要查找的元素int floor;/用于記錄層數if(T)/假設樹不空if(_(1)_)/假設在根處找到return 1;floor = LocateElem(_(2)_);/在左子樹查找if(floor0)/假設在左子樹中找到return _(3)_;floor = LocateElem(_(4)_);if(floor0)return _(5)_;return 0;/假設樹為空，那么直接返回0，說明找不到5、圖的鄰接表定義如第二題所示，以下程序段為圖的深度優先搜索算法，請將算法中缺失的語句補充完整：void DFS (ALGraph G,int v) /從編號為v的頂點出發進行深度優先搜索遍歷 /假設所有變量、函數皆已定義 visitedv=true;/訪問標志數組，true表示訪問過，false表示未被訪問過 VisitFunc(v); /訪問v標點for(