四川l某大學(xué)2022年碩士研究生考試自命試題816數(shù)據(jù)結(jié)構(gòu)與算法

機(jī)密★啟用前(滿分，150分，所有答案一律寫(xiě)在答題紙上)適用專業(yè)：085404計(jì)算機(jī)技術(shù)、085411大數(shù)據(jù)技術(shù)與工程考試科目：816數(shù)據(jù)結(jié)構(gòu)與算法B卷考試時(shí)間：3小貝/選擇題(每題2分，共40分)1,下述各項(xiàng)中屬于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)點(diǎn)的是().A.提取某位置元素方便 B.插入運(yùn)算方便C.存儲(chǔ)密度大 D.存儲(chǔ)完全二叉樹(shù)操作效率高.若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用()存儲(chǔ)結(jié)構(gòu)最節(jié)省運(yùn)算時(shí)間？A.單鏈表 B.給出表頭指針的循環(huán)單鏈表C.雙鏈表 D.帶頭結(jié)點(diǎn)的循環(huán)雙鏈表.在一個(gè)長(zhǎng)度為n(n>l)的帶頭結(jié)點(diǎn)的單鏈表h上,另設(shè)有尾指針r(指向尾結(jié)點(diǎn))，執(zhí)行()操作與鏈表的長(zhǎng)度無(wú)關(guān)。A.刪除單鏈表中的第一個(gè)結(jié)點(diǎn)B.刪除單鏈表中的最后一個(gè)結(jié)點(diǎn)C.在單鏈表第i個(gè)元素前插入一個(gè)新結(jié)點(diǎn)D.在單鏈表第i個(gè)元素后插入一個(gè)新結(jié)點(diǎn).對(duì)于順序表,訪問(wèn)第i個(gè)位置的元素和在第i個(gè)位置插入一個(gè)元素的時(shí)間復(fù)雜度為()oA.0⑴，0(1) B.O(n),0(1)C.O(l),O(n) D.O(n),O(n).帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空的條件是().A.L==NULL B.L->next->prior=NULLC.L->prior=NULL D.L->prior=L&&L->next=L.設(shè)線性表有n個(gè)元素，以下操作中，（）在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高。A.輸出第i（lv=i〈=n）個(gè)元素值B.交換第1個(gè)元素與第2個(gè)元素的值C.順序輸出這n個(gè)元素的值D,輸出與給定值x相等的元素在線性表中的序號(hào).入棧序列為ABC,出棧序列為BAC時(shí)，經(jīng)過(guò)的棧操作為（）push,pop,push,pop,push,poppush,push,push,pop,pop,poppush,push,pop,pop,push,poppush,push,pop,push,pop,pop.表達(dá)式a/（bc）+d*e的后綴表達(dá)式是（）.A.ab/c-d+e*B.abc/-de+*C.abcde*+-/D.abc-/de*+.數(shù)據(jù)序列｛8,4,9,5,6,1,2,10,20｝只能是下列排序算法中的（）兩趟排序后的結(jié)果。A.簡(jiǎn)單選擇排序B.冒泡排序C.直接插入排序 D.二路歸并排序.以下排序算法中，（）不能保證每趟排序至少能將一個(gè)元素放在其最終位置上.A.快速排序B.希爾排序C.堆排序D.冒泡排序.二路歸并排序中歸并的趟數(shù)為（）。A.nB.log2nC.nlog2nD.2.字符串S長(zhǎng)度是m,模式串P的長(zhǎng)度是n,則經(jīng)典字符串匹配算法（BF算法）的時(shí)間復(fù)雜度是（）。A.0（m+n）B.0（m*n）C.0（log（m*n）） D,不確定.設(shè)有二維數(shù)組A[m,n]按行優(yōu)先順序存儲(chǔ)，其每個(gè)元素占兩個(gè)字節(jié)，A[0]⑼存儲(chǔ)地址為100,元素A[6,6]的存儲(chǔ)地址為352,可知m,n的值是（）.A.20,10B.10,20C.n不能確定 D.m不能確定.3個(gè)結(jié)點(diǎn)的無(wú)序樹(shù)有（）種形狀。A.2B.3 C.4D.5.如果一棵二叉樹(shù)的先序和中序遍歷恰好相同，則該二叉樹(shù)的特點(diǎn)是（）.A.只有根結(jié)點(diǎn) B.只有左孩子C,只有右孩子 D.后序遍歷和先序遍歷相反.關(guān)于樹(shù)的存儲(chǔ)形式說(shuō)法錯(cuò)誤的是（>.A.滿二叉樹(shù)可以用數(shù)組存儲(chǔ)，方便計(jì)算結(jié)點(diǎn)B.孩子兄弟法可以讓任何樹(shù)變成唯一的二叉樹(shù)C.孩子鏈表表示法不方便查找雙親結(jié)點(diǎn)D.孩子兄弟法的好處是方便找到雙親結(jié)點(diǎn).對(duì)于有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其高度為（）A.nloginB.log2n C.向下取整（log2n）+1 D.不確定.n個(gè)頂點(diǎn)的連通有向圖，其邊的個(gè)數(shù)至少為（）.A.n-1 B.n C,n+1 D.不確定.設(shè)用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（）.A.第i行非0元素的個(gè)數(shù)之和 B.第i行。元素的個(gè)數(shù)之和C.第i列非0元素的個(gè)數(shù)之和 D.第i列0元素的個(gè)數(shù)之和.二叉排序樹(shù)的查找效率與二叉樹(shù)的樹(shù)型有關(guān)，在（）時(shí)其查找效率最低。A.呈單支樹(shù)形態(tài) B.結(jié)點(diǎn)很多 C.完全二叉樹(shù)時(shí) D.滿二叉樹(shù)時(shí)填空題（每空2分，共26分）.求整數(shù)n（n>=0）階乘的算法如下，其時(shí)間復(fù)雜度是.intfact（intn）（iRn<=l）return1;returnn*fact（n-1）;）.若長(zhǎng)度為n的非空線性表采用順序儲(chǔ)存結(jié)構(gòu)，在表的第i個(gè)位置刪除一個(gè)數(shù)據(jù)元素,i的合法值應(yīng)該是（填寫(xiě)格式a<=iv=b）。.給定數(shù)值大小無(wú)序的n個(gè)元素構(gòu)成的一維數(shù)組，建立一個(gè)有序單鏈表的最低時(shí)間復(fù)雜度是。.將長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表的第5個(gè)元素之后，其算法的時(shí)間復(fù)雜度是..表達(dá)式3+2*3/(5-2+8*3)求值過(guò)程中當(dāng)掃描到8時(shí)，操作數(shù)棧內(nèi)容為.(數(shù)字8還未做入棧操作，從棧底依次寫(xiě)，數(shù)字之間用逗號(hào)分隔)6,快速排序的空間復(fù)雜度為。7,廣義表A=(a.b,(c,d),e),寫(xiě)出得到字符d的操作(取表頭用H,表尾用T表示).一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是..假定在一棵二叉樹(shù)中，度為2的結(jié)點(diǎn)數(shù)為15,度為1的結(jié)點(diǎn)數(shù)為30,則葉子結(jié)點(diǎn)數(shù)為個(gè)。.對(duì)有n個(gè)頂點(diǎn)、e條邊的圖采用鄰接表表示時(shí)，進(jìn)行BFS遍歷的時(shí)間復(fù)雜度為，空間復(fù)雜度為.1】.有向網(wǎng)G的鄰接矩陣為A,如果圖中不存在弧則A[i,j]的值為一.折半查找的時(shí)間復(fù)雜度為.程序填空題(每空3分，共51分).假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針rear指向隊(duì)尾結(jié)點(diǎn)，且不設(shè)隊(duì)頭指針，請(qǐng)將入隊(duì)算法補(bǔ)充完整。己知循環(huán)鏈表結(jié)點(diǎn)類型為：typedefstructQNode{QEIemTypedata;structQNode*next;JQNode;StatusEnQueue(QNode*&rear,QEIemTypee){//rear是帶頭結(jié)點(diǎn)的循環(huán)鏈隊(duì)的尾指針，本算法將元素e插入到隊(duì)尾QNode*p;p=(QNode*)malloc(sizeof{QNode));ifljp)returnERROR;p->data=e;p->next=(1)；⑵ ：⑴ ；returnOK;}2、以下函數(shù)是用冒泡排序法將序列A中的元素按從小到大排列，將程序補(bǔ)充完整voidBubbleSort(intA[],intn){〃參數(shù)1為待排序數(shù)組，參數(shù)2數(shù)組長(zhǎng)度f(wàn)br(inti=0;i<n-l;i-H-){boolflag=false;fbr(intj=n-l: (I)j-)iff(2) )(swap(A[j-l],A[j]);(3) :}if{flag=flase)return;})3?以下算法是輸出一顆二叉樹(shù)的第i層的所有結(jié)點(diǎn)的值，假定根結(jié)點(diǎn)是第1層。在每條橫線處填入一條語(yǔ)句或語(yǔ)句的部分。typedefstructBtree{chardata;structBtree*lch,*rch;}Btree;voidprintInode(Btree*bt,inti)(if{bt==NULL)return;if(i=l){putchar(bt->data);return;}printlnode((D);printlnode((2J)；)4,已知遞增有序的單鏈表A、B分別存儲(chǔ)了一個(gè)集合(A、B中元素個(gè)數(shù)分別為m、n,且A、B都帶有頭結(jié)點(diǎn)，A中可能存在重復(fù)元素，B中沒(méi)有重復(fù)元素)，請(qǐng)?jiān)O(shè)計(jì)算法，以求出兩個(gè)集合A和B的差集A-B(僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成的集合)。將差集保存在單鏈表A中，并保持元素的遞增有序性。例：原A鏈表：1,2,2,3,4,5,5.8,10原B鏈表：3,5,6,8,12做差集后A轉(zhuǎn)表：1,2,2,4,10已知單鏈表結(jié)點(diǎn)類型為：typedefstructLNode{ElemTypedata; 〃數(shù)據(jù)域structLNode*next;〃指針域JLNode,*LinkList;voidDifference(LNode*A,LNode*B){LNode*p=A->next,*q=B->next;LNode*pre=A^/A中p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，方便刪除相關(guān)結(jié)點(diǎn)LNode*r;while(p!=NULL&&q!=NULL){if(p->data<q->data){TOC\o"1-5"\h\z-(1) ；-(2) ;Jelseif(p->data>q->data)⑶ ：else{pre->next=(4) ;(5) :⑹：free（r）;}））5,以下算法是將順序表中元素值超過(guò)Max的相關(guān)元素的值調(diào)整為Max”,請(qǐng)將函數(shù)撲充完整.夕defineMax100typedefstructSqlist（Elemtypc'data;intLength;）；voidRevcrsc（Sqlist&L）（fbr（inti=0;Qj:i++）{iff（2）H:））四、應(yīng)用題（共33分）.（共5分）一顆二叉利的光序序列mubdc吸，中序序列是ndbfegc,畫(huà)出這棵樹(shù)（2分），并求出其后序序列（3分）.（共8分）有一份電文中共使用6個(gè)字符:a,b,c,d,e￡它們的出現(xiàn)頻率依次為4,2,824,6,試畫(huà)出哈夫曼樹(shù)（2分），求加權(quán)路徑長(zhǎng)度WPL（4分）和字符a的編碼（2分，按照左。右1的規(guī)則）.WPL寫(xiě)出計(jì)算公式，編碼請(qǐng)?jiān)趫D分支上標(biāo)注0、I..（共6分）已知某圖的鄰接表為

（1）寫(xiě)出由（2）寫(xiě)出由vl開(kāi)始的廣度優(yōu)先遍歷的序列；（3分）4、（共6分）已知一個(gè)無(wú)向圖如下圖所示，用Prim算