自考數(shù)據(jù)結(jié)構(gòu)歷試題及答案?jìng)€(gè)人審批稿

在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、下列程序段的時(shí)間復(fù)雜度為()9A.O(1)B.O(n)C.O(2n)D.O(n2)鏈表的頭指針為head，則判定該表為空表的條件是()22head.棧是一種操作受限的線性結(jié)構(gòu)，其操作的主要特征是()32A.先進(jìn)先出B.后進(jìn)先出C.進(jìn)優(yōu)于出D.出優(yōu)于進(jìn)4.假設(shè)以數(shù)組A[n]存放循環(huán)隊(duì)列的元素，其頭、尾指針?lè)謩e為front和rear。若設(shè)定尾指針指向隊(duì)列中的隊(duì)尾元素，頭指針指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，則當(dāng)前存于隊(duì)列中的元素個(gè)數(shù)為()n5.判斷兩個(gè)串大小的基本準(zhǔn)則是()52A.兩個(gè)串長(zhǎng)度的大小B.兩個(gè)串中首字符的大小C.兩個(gè)串中大寫(xiě)字母的多少D.對(duì)應(yīng)的第一個(gè)不等字符的大小A.1012B.1017C.1034D.1036a00a01a02a03a04 A.16B.17 C.31D.32A.5B.8C.11D.18.下列所示各圖中是中序線索化二叉樹(shù)的是(A)81A10.已知含6個(gè)頂點(diǎn)(v，v，v，v，v，v)的無(wú)向圖的鄰接矩陣如圖所示，則從頂點(diǎn)v出發(fā)進(jìn)行深度優(yōu)先0123450頂點(diǎn)訪問(wèn)序列為()108012543012345015234014523是()A.ABCDEFB.FCBEADC.FEDCBAEBCF))172BBHkeykey則下一個(gè)插入)206 A.記錄組成的集合B.字符組成的集合 C.數(shù)據(jù)項(xiàng)組成的集合D.數(shù)據(jù)結(jié)構(gòu)組成的集合請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。_________。26.假設(shè)有一個(gè)形如若將上述矩陣中次對(duì)角線及其以下的元素按行優(yōu)先壓縮存儲(chǔ)在一維數(shù)組B中，請(qǐng)回答下列問(wèn)題：(2)若a存儲(chǔ)在B[0]中，a存儲(chǔ)在B[k]中，則k值為多少?1856(1)(1+8)*8/2=36存放次對(duì)角線以上的零為37；第一趟劃分過(guò)程223159687112359687112357689112356789第二趟劃分過(guò)程2231596877768912355678969592136930.假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示線性表，單鏈表的類型定義如下：typedefintDataType;typedefstructnode{DataTypedata;structnode*next;}LinkNode,*LinkList;閱讀下列算法，并回答問(wèn)題：(1)已知初始鏈表如圖所示，畫(huà)出執(zhí)行f30(head)之后的鏈表；fLinkListheadif(head->next){rheadnextprnextextNULLwhile(p){ppnextif(s->data%2==0){head->next=s;}else{r->next=s;}}}}以二叉鏈表表示二叉樹(shù)，其類型定義如下：typedefstructnode{DataTypedatatructnodelchildrchild}*BinTree;Td=f31(T->lchild)+f31(T->rchild);returnd+1;returnd;向圖鄰接表定義如下：typedefstruct{VertexNodeadjlist[MaxVertexNum];voidDFS(ALGraph*G,inti){dgeNodepvisited[i]=TRUE;NULLprintf("%c",G->adjlist[i].vertex)；else{pGadjlist[i].firstedge;while(p!=NULL){adjvexDFS(G,p->adjvex);ppnext}}}voidf32(ALGraph*G){for(i=0;i<G->n;i++)visited[i]=FALSE;for(i=0;i<G->n;i++)if(!visited[i])DFS(G,i);}ABECD交換將關(guān)鍵字最小的記錄移動(dòng)至前端，如此反復(fù)進(jìn)行，直#defineMAXLEN100typedefstruct{ypekey}NodeType;defNodeTypeSqListMAXLENvoidfSqListRintn)NodeTypet;while(i<j){for(1))k=i;k<j;k++if(R[k].key>R[k+l].key){R[k]=R[k+1];R[k+1]=t;}for(k=j;k>i;k--) if((2)){R[k].key<R[k-l].key R[k]=R[k-1];R[k-1]=t;} }}34.假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示線性表，單鏈表的類型定義如下：typedefintDataType;typedefstructnode{DataTypedata;structnode*next;}LinkNode,*LinkList;編寫(xiě)算法，刪除線性表中最大元素(假設(shè)最大值唯一存在)。函數(shù)原型為：voidf34(LinkListhead){kNodepmaxqheadnextmax=head->next;whileP){next}ta}}intj;}一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)選、多選或未選均1.按值可否分解，數(shù)據(jù)類型通?？煞譃閮深?，它們是(c)A.靜態(tài)類型和動(dòng)態(tài)類型B.原子類型和表類型A.Af(n)是0(g(n))B.Bg(n)是0(f(n))hnn3.指針p、q和r依次指向某循環(huán)鏈表中三個(gè)相鄰的結(jié)點(diǎn)，交換結(jié)點(diǎn)*q和結(jié)點(diǎn)*r在表中次序的程A.p->next=r；q->next=r->next；r->next=q；B.p->next=r；r->next=q；q->next=r->next；nextqqnextrnextpnextrD.r->next=q；p->next=r；q->next=r->next；A.3B.5D.75.假設(shè)以數(shù)組A[n]存放循環(huán)隊(duì)列的元素，其頭指針front指向隊(duì)頭元素的前一個(gè)位置、尾指rear存儲(chǔ)位置，則在少用一個(gè)元素空間的前提下，隊(duì)列滿的判定條件為()A.rear==frontontA.3B.4D.67.二維數(shù)組A[10][6]采用行優(yōu)先的存儲(chǔ)方法，若每個(gè)元素占4個(gè)存儲(chǔ)單元，已知元素A[3][4]的存儲(chǔ)地址為1000，則元素A[4][3]的存儲(chǔ)地址為()A.1020B.1024D1240D.(a)A.FEDCBAB.ABCDEFC.FDECBAD.FBDCEAA.2B.3D.11GGA.7B.8D.22A.塊內(nèi)有序B.塊間有序15.便于進(jìn)行布爾查詢的文件組織方式是()A.順序文件B.索引文件D二、填空題(本大題共10小題，每小題2分，若有兩個(gè)空格，每個(gè)空格1分，共20分)請(qǐng)1.數(shù)據(jù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是借助_指針__表示數(shù)據(jù)元素之間的邏輯關(guān)系。2.如果需要對(duì)線性表頻繁進(jìn)行_插入__或__刪除_操作，則不宜采用順序存儲(chǔ)結(jié)構(gòu)。toptopn滿”的判定條件是_top1>top2(或top2=top1-1或toptop+1)。5.廣義表L=(a，(b，()))的深度為_(kāi)3__。8.在5階B樹(shù)中，每個(gè)結(jié)點(diǎn)至多含4個(gè)關(guān)鍵字，除根結(jié)點(diǎn)之外，其他結(jié)點(diǎn)至少含_2__個(gè)關(guān)鍵字。9.若序列中關(guān)鍵字相同的記錄在排序前后的相對(duì)次序不變，則稱該排序算法是_穩(wěn)定__的。，共20分)1.答答案：0100，初始堆：第1趟：第2趟：fG#defineMaxNum20intvisited[MaxNum]；/*從頂點(diǎn)vi出發(fā)進(jìn)行深度優(yōu)先搜索，訪問(wèn)頂點(diǎn)vj時(shí)置visited[j]為1*/intf0(Graph*g)visited[i]=0；if(visited[i]==0)}returnk；}答案：(1)3(3分) (2)返回?zé)o向圖g中連通分量的個(gè)數(shù)。(2分)2.假設(shè)學(xué)生成績(jī)按學(xué)號(hào)增序存儲(chǔ)在帶頭結(jié)點(diǎn)的單鏈表中，類型定義如下：typedefstructNode{enextvoidf31(LinkListA,LinkListB)while(p&&q)core}}}答案：是一維整型數(shù)組，寫(xiě)出算法值；intf32(char*s,char*t,intpos[])do{{pos[k++]=i+j;}leiitisj}答案：(1)2；pos[0]=0,pos[1]=8(說(shuō)明：每個(gè)值1分)(3分) (2)返回串t在s中出現(xiàn)的次數(shù)，并將每次出現(xiàn)的位置依次存放在數(shù)組pos中。(2分)存儲(chǔ)結(jié)構(gòu)定義為以下類型：typedefintKeyType;typedefstructnode{KeyTypekey/childrchildodeBSTreeefBSTreeTKeyTypexLLildxTildx}答案：(1)10(2分) (2)T是空樹(shù)或T中所有結(jié)點(diǎn)的關(guān)鍵字均不大于給定值x時(shí)，返回空指針。(2分) (3)如果二叉排序樹(shù)T中存在含有關(guān)鍵字大于給定值x的結(jié)點(diǎn)，則返回指針指向它們中關(guān)鍵字最小的結(jié)點(diǎn)，否則返回空指針。(1分)五、算法設(shè)計(jì)題(本題10分)1.假設(shè)線性表采用順序存儲(chǔ)結(jié)構(gòu)，其類型定義如下：#defineListSize100typedefstruct{intdata[ListSize];答案：參考答案一：Llength{while(i<j&&L->data[i]%2)(1分)while(i<j&&L->data[j]%2==0)(1分)j--;L->data[i]=L->data[j];L->data[j]=t;j--;}}二：L->data[i]=L->data[j];L->data[j]=t;j++;(1分)}四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。1．若一個(gè)算法的時(shí)間復(fù)雜度用T(n)表示，其中n的含義是(A)2．具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是(C)線性結(jié)構(gòu)有：順序表、棧和隊(duì)列、串ABA．O(1)B．O(m)C．O(n)D．O(m+n)4．在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中插入一個(gè)新結(jié)點(diǎn)，需要修改的指針域數(shù)量是(C)ppNULLDListNodesmallocsizeofListNodesdataxspriorppriorsnextpppriornexts⑤p->prior=s;}⑥的尾指針值為(B)A．3B．37C0D．97對(duì)于循環(huán)向量中的循環(huán)隊(duì)列，寫(xiě)出通過(guò)隊(duì)頭隊(duì)尾指針表示的隊(duì)列長(zhǎng)度公式。(front指向?qū)嶋H隊(duì)頭，rear指向?qū)嶋H隊(duì)尾的下一元素位置。)當(dāng)rear≥front時(shí)，隊(duì)列長(zhǎng)度L=rear-front；當(dāng)rear<front6．若棧采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則下列說(shuō)法中正確的是(B)A．8B．9C．36D．371000，每個(gè)元素占一個(gè)地址單元，則a的地址為(C)85在n階方陣A這個(gè)下三角矩陣中，第i(i從0開(kāi)始)行(0≤i<n)有i+1個(gè)元素，元素總數(shù)為：9．允許結(jié)點(diǎn)共享的廣義表稱為(D)10．下列數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹(shù)的是(A)11．對(duì)下面有向圖給出了四種可能的拓?fù)湫蛄校渲绣e(cuò)誤的是(C)12．以v1為起始結(jié)點(diǎn)對(duì)下圖進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是(D)深度優(yōu)先遍歷類似于樹(shù)的前序遍歷。其特點(diǎn)是盡可能先對(duì)縱深方向進(jìn)行搜索。13．下列排序算法中不穩(wěn)定的是(A)穩(wěn)定：直接插入、冒泡、歸并、基數(shù)不穩(wěn)定：直接選擇、希爾、快速、堆A．2B．3C．4D．8ISAM式屬于(D)___O(n)______。typedefstruct{DataTypedata[100]；DataTypef18(SeqStack*S)Error(”Stackisempty”)；returnS->data[S->top]；}_42,13,94,55,05,46,17。一顆m(m≥3)階的B-樹(shù)，每個(gè)非根結(jié)點(diǎn)中所包含的關(guān)鍵字個(gè)數(shù)j滿足：┌m/2┐-1≤j≤m-1。即每個(gè)非根結(jié)點(diǎn)至少應(yīng)有┌m/2┐-1個(gè)關(guān)鍵字，至多有m-1個(gè)關(guān)鍵字。 (注：┌m/2┐是指不小于(即大于等于)m/2的最小整數(shù)。)一顆高度為h的m階B-樹(shù)中最少可容納的關(guān)鍵字總數(shù)為：┌m/2┐h-1，最少可容納的結(jié)點(diǎn)總數(shù)為┌m/2┐h-1┌m/2┐-1vertexfirstedgeadjvexnextA01301B124031240C12512D0143014E14551455F242邊表頂邊表361636163618i=2，不調(diào)整i=1，調(diào)整6060231238554536678910606031238545678910161612186015361418258516121818153614602585i=5，不調(diào)整i=5，不調(diào)整151400560123780925123780925518163612345671816361616121418153618602585小根堆初始建堆后的序列小根堆初始建堆后的序列請(qǐng)回答下列問(wèn)題：Typedefstructnode{DataTypedatavoidf30(LinkListLs)if(q&&q->next){Lsnextqnextwhile(p->next)ppnextp>next=q;回答下列問(wèn)題：}回答下列問(wèn)題：的值為零，則條件表達(dá)式的值等于0。k=n-l；whilek0){jijx=A[j]；A[j]=A[j+l]；A[j+1]=x；k=j；ofifreturn；}回答下列問(wèn)題：kj句defstructKeyTypekey；infoListNwhile((1)low<=high){mid=(1ow+high)／2；))returnmid；high=mid-1；}returnO；。ElmTypedata；Tree}一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分))A、索引存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu)C一對(duì)一存儲(chǔ)結(jié)構(gòu)、一對(duì)多存儲(chǔ)結(jié)構(gòu)和多對(duì)多存儲(chǔ)結(jié)構(gòu)使操作時(shí)間最少，下列選項(xiàng)中，應(yīng)選擇的存儲(chǔ)結(jié)構(gòu)是()A頭結(jié)點(diǎn)的單向鏈表B.帶頭結(jié)點(diǎn)的單向鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.帶頭結(jié)點(diǎn)的單循環(huán)鏈表()A.n-iB.n-i+lCniD.無(wú)法確定5.串匹配算法的本質(zhì)是()CD.子串鏈接CD.407.若一棵二叉樹(shù)的前序遍歷序列與后序遍歷序列相同，則該二叉樹(shù)可能的形狀是()A.樹(shù)中沒(méi)有度為2的結(jié)點(diǎn)B.樹(shù)中只有一個(gè)根結(jié)點(diǎn)CD結(jié)點(diǎn)均只有右子樹(shù)A.n.B.G兩個(gè)結(jié)點(diǎn)之間的最短路徑可以采用的算法是()A.迪杰斯特拉(Dijkstra)算法B.克魯斯卡爾(Kruskal)算法()A不穩(wěn)定的B.穩(wěn)定的C.基于交換的D.基于選擇的表，用拉鏈法解決沖突，散列地址為1的鏈中記錄個(gè)數(shù)為()A.1B.2CD.414.已知二叉樹(shù)結(jié)點(diǎn)關(guān)鍵字類型為字符，下列二叉樹(shù)中符合二叉排序樹(shù)性質(zhì)的是(D))A.順序文件B.索引文件CD.倒排文件二、填空題(本大題共10小題，每小題2分，共20分)chardata[16]；r三、解答題(本大題共4小題，每小題5分，共20分)A=(B,y)：四、算法閱讀題(本大題共4小題，每小題5分，共20分)xxwhile(a[m]<0&&m<n)while(k<n){while(a[k]>=0&&k<n)if(k<n){temp=a[k]；a[k]=a[m]；}}}{while(len>0&&*s)}}{chart[100];ens}}intkey;Infootherinfo;voidInsertSort(SeqListR[],intn){/*待排序列保存在R[1..n]中*/for(i=2；i<=n；i++){hi=i-l;while(lo<=hi){if((2))break;if(R[mi].key>x.key)hi=mi-l;}if(mi=lo)k=i-mi;for(j=0；j<k；j++) R[i-j]=x；}}}*LinkList;voidf33(LinkListhead,intA,intB){LinkListp=NULL;adNULL{}if(p!=NULL)}五、算法設(shè)計(jì)題(本題10分)tdata}*Bitptr；編寫(xiě)遞歸算法求二叉樹(shù)的高度。函數(shù)原型為：intf34(Bitptrt)；中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)1.下列選項(xiàng)中與數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是()A.順序表B.鏈表C.鏈隊(duì)列D.棧2.將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，最少的比較次數(shù)是()下一個(gè)位置，則向隊(duì)列中插入新元素時(shí)，修改指針的操作是()4.遞歸實(shí)現(xiàn)或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，應(yīng)采用的數(shù)據(jù)結(jié)構(gòu)是()A.堆棧B.多維數(shù)組CD.線性表pqq是p的子串，則求q在p中首次出現(xiàn)位置的算法稱為()AB串聯(lián)接6.對(duì)于廣義表A，若head(A)等于tail(A)，則表A為()A.()B.(())7.若一棵具有n(n>0)個(gè)結(jié)點(diǎn)的二叉樹(shù)的先序序列與后序序列正好相反，則該二叉樹(shù)一定是()A.結(jié)點(diǎn)均無(wú)左孩子的二叉樹(shù)B.結(jié)點(diǎn)均無(wú)右孩子的二叉樹(shù)C.高度為n的二叉樹(shù)D.存在度為2的結(jié)點(diǎn)的二叉樹(shù) ()AB.5CD.89.下列敘述中錯(cuò)誤的是()11.平均時(shí)間復(fù)雜度為O(nlogn)的穩(wěn)定排序算法是()A.快速排序B.堆排序關(guān)鍵字序列是()順序查找，則在等概率情況下，分塊查找成功的平均查找長(zhǎng)度是()AB.79D14.在含有10個(gè)關(guān)鍵字的3階B-樹(shù)中進(jìn)行查找，至多訪問(wèn)的結(jié)點(diǎn)個(gè)數(shù)為()A2B.3CD.515.ISAM文件系統(tǒng)中采用多級(jí)索引的目的是()A.提高檢索效率B.提高存儲(chǔ)效率CD.方便文件的修改，運(yùn)行26.已知一棵二叉排序樹(shù)(結(jié)點(diǎn)值大小按字母順序)的前序遍歷序列為EBACDFHG，下列問(wèn)題：(1)畫(huà)出堆排序的初始堆(大根堆)；堆。voidf30(intA[]，intn){inti,j,m;for(i=1；i<n；i++)for(j=0；j<i；j++){m=A[i*n+j]；A[i*n+j]=A[j*n+i]；A[j*n+i]=m；}}}*BinTree；{{whilewhile(T){}{}}}voidf32(intA[],intn){inti,j,m=l,t；for(i=0;i<n-l&&m;i++){for(j=1;j<n-i;j++)if(A[j-1]>A[j]){t=A[j-l];A[j-1]=A[j]；A[j]=t；}}}Intf33(SqListR，NodeTypeX,intp,intq){intm;if(p>q)return-1;if(R[m].key==X.key)returnm;ml}列問(wèn)題：性表，單鏈表的類型定義如下：floatf34(LinkListhead):1、在數(shù)據(jù)的邏輯結(jié)構(gòu)中，樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)都是()A.非線性結(jié)構(gòu)2.在一個(gè)長(zhǎng)度為n的順序表中插入一個(gè)元素的算法的時(shí)間復(fù)雜度為()A.O(1)B.O(logn)單循環(huán)鏈表，應(yīng)執(zhí)行的操作為()過(guò)程中棧中元素個(gè)數(shù)最多時(shí)為()AB.3個(gè)CD.6個(gè)5.隊(duì)列的特點(diǎn)是()A任何位置進(jìn)行插入和刪除B除如果每個(gè)字符占1個(gè)字節(jié)，指針占2個(gè)字節(jié)，該鏈串的存儲(chǔ)密度為()AB.1/27.廣義表A=(a,B,(a,B,(a,B,……)))的長(zhǎng)度為()A.1B.2CD.無(wú)限值址為420，則A[5][5]的存儲(chǔ)地址為()9.在一棵二叉樹(shù)中，度為2的結(jié)點(diǎn)數(shù)為15，度為1的結(jié)點(diǎn)數(shù)為3，則葉子結(jié)點(diǎn)數(shù)為()10.在帶權(quán)圖的最短路徑問(wèn)題中，路徑長(zhǎng)度是指()A.路徑上的頂點(diǎn)數(shù)B.路徑上的邊數(shù)C.路徑上的頂點(diǎn)數(shù)與邊數(shù)之和D.路徑上各邊的權(quán)值之和AeB.2eCneD.n2-112.要以O(shè)(nlogn)時(shí)間復(fù)雜度進(jìn)行穩(wěn)定的排序，可用的排序方法是()AB.快速排序)A.堆排序B.快速排序14.對(duì)有序表進(jìn)行二分查找成功時(shí)，元素比較的次數(shù)()A.僅與表中元素的值有關(guān)B.僅與表的長(zhǎng)度和被查元素的位置有關(guān)C.僅與被查元素的值有關(guān)D.僅與表中元素按升序或降序排列有關(guān)15.散列文件是一種()A.順序存取的文件B.隨機(jī)存取的文件---」| (1)畫(huà)出三元組表； (1)畫(huà)出該森林； (1)畫(huà)出該散列表； (2)求等概率情況下查找成功的平均查找長(zhǎng)度ASL; (3)寫(xiě)出刪除值為70的關(guān)鍵字時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)。 (2)簡(jiǎn)述f30的功能。{∥L為非空的有序表 {iLdataki+;}} (2)簡(jiǎn)述函數(shù)f31的功能。} (1)若向量BT為：AABCDEFG1234567畫(huà)出執(zhí)行函數(shù)f32(BT,7,1)的返回結(jié)果;{if(i＞n)returnNULL;}：intadjvex;∥圖的最大頂點(diǎn)數(shù)∥鄰接點(diǎn)域intn,e;}ALGraph;intn,e;∥鏈指針域∥邊表結(jié)點(diǎn)結(jié)構(gòu)∥頂點(diǎn)域∥邊表頭指針∥頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)∥鄰接表∥圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)∥鄰接表描述的圖∥頂點(diǎn)表∥鄰接矩陣∥圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)∥鄰接矩陣描述的圖{inti,j;G2－＞e=(1);for(i=0;i＜G1.n;i++){G2－＞vertex[i]=(2);for(j=0;j＜G1.n;j++)G2－＞adjmatrix[i][j]=0;while(p) (3);}}}34.設(shè)順序表L是一個(gè)遞增有序表。編寫(xiě)算法，要求利用二分查找法確定插入位置，將元素x插入到L中，使L保持有序。1.每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前趨和多個(gè)(或無(wú))直接后繼(第一個(gè)結(jié)點(diǎn)除外)的數(shù)據(jù)結(jié)構(gòu)稱為(A)CD.層次結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)是(D)A.單鏈表B.雙鏈表C.僅有頭指針的單循環(huán)鏈表D.僅有尾指針的單循環(huán)鏈表 (C)A.iB.n-iCC.n-i+lD.不確定4.下面關(guān)于串的敘述中，正確的是(A)AB5.無(wú)向完全圖G有n個(gè)結(jié)點(diǎn)，則它的邊的總數(shù)為(C)AnBnn-1)7.如圖所示，在下面的4個(gè)序列中，不符合深度優(yōu)先遍歷的序列是(A8.無(wú)論待排序列是否有序，排序算法時(shí)間復(fù)雜度都是O(n2)的排序方法是(D)A.快速排序B.歸并排序9.已知二叉排序樹(shù)G，要輸出其結(jié)點(diǎn)的有序序列，則采用的遍歷方法是(C)A.按層遍歷B.前序遍歷10.用ISAM和VSAM組織的文件都屬于(B)A文件B.索引順序文件CD.多關(guān)鍵字文件15)，則采用的排序方法是(C)A.選擇B.快速12.當(dāng)采用分塊查找時(shí)，數(shù)據(jù)的組織方式為(D)A若干塊，每塊內(nèi)數(shù)據(jù)有序C序，塊間是否有序均可13.下述編碼中不是前綴碼的是(B)14.若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針top為n+l，則x進(jìn)棧的正確操作是(A)指針在最head環(huán)鏈表中，指針p指向鏈尾結(jié)點(diǎn)的條件是(D)A[10][10]的每個(gè)元素占2個(gè)單元，現(xiàn)將其三條對(duì)角堆：：：{inti=0,j,k；.while(str[i]!='\0')i++；ifiki1；for(j=k;j<i;j++)ifstrjpops)}31.下列算法是利用二分查找方法在遞減有序表R中插入元素x，并保持表R的有序性。請(qǐng)?jiān)诳杖碧巤mid=(low+high)/2；}for(i=*n；i>=low；i--)R[i+1]=R[i]； ++(*n)；}{if(p==NULL)printf("error\n")；{}}}{//n<MaxLen-1RkkeyRklkey{Rn1]=R[k]；R[i-1]=R[i];R[i-l]=R[n+1]；}}A判斷?？誃空aAB．26CD．34BAB下列操作后頭、尾指針的當(dāng)前值。構(gòu)造過(guò)程。 (2)該算法的功能是什么？intlength；{inti,j；i=0；{for(j=i+1;j<L->length;j++}}} 例如，一個(gè)有向圖的鄰接矩陣如下所示：A=Voidf31(MGraphG){Inti,j,k=0;for(i=0;i<G.n;i++)for(j=0;j<G.n;j++)if(G.edges[i][j]==1)k++;printf(“%dn”,k)for(j=0;j<G.n;j++){k=0;for(i=0;i<G.n;j++)if(G.edges[i][j]==1)k++;printf(“%dn”,k)}}{{r[0]=r[i]；j=i-l；while(r[0]<r[j]){r[j+l]=r[j]；}r[j+l]=r[0]；}}if(r[0]<r[1])for(i=2；i<n；i++)if(r[i]<a)a=r[i];elseif(r[i]>b)b=r[i]；}在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題AB結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)CD構(gòu)D．A．5B.6C7D.8A．ACDBAA．ACDBADAB1CD.4AeB.2eA.n-lB.nA．2B.3C．4從大到下自底向上排序D.5AB.分塊有序D。=66kList算法，并回答問(wèn)題：voidf30(LinklListhead,DataTypex)}(2)若單鏈表的長(zhǎng)度為n，算法的時(shí)間復(fù)雜度是多少該時(shí)間復(fù)雜度和鏈表的初始狀態(tài)有關(guān)嗎31．閱讀下列算法(假設(shè)棧的操作函數(shù)都已定義)，并回答問(wèn)題：voidf31()y=′k′；}}{∥在中序線索樹(shù)中找結(jié)點(diǎn)*p的中序前趨，設(shè)p非空{(diào)}}一voidf33(inta[],intn)for(i=0；i<n；i++)∥語(yǔ)句1{j=i；if(a[k]<a[j])j=k；∥語(yǔ)句2t=a[i];a[i]=a[j];a[j]=t;}}五、算法設(shè)計(jì)題(本題10分)pedefstructnodestructnode*lchild,*rchild;在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題紙”的相應(yīng)代碼涂黑。錯(cuò)涂、多涂或未征的是A法的可讀性B程度D．執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間22．對(duì)需要頻繁插入和刪除結(jié)點(diǎn)的線性表，適合的存儲(chǔ)方式是A．順序儲(chǔ)存B．鏈?zhǔn)酱鎯?chǔ)CD．散列存儲(chǔ)3．在頭指針為head的循環(huán)鏈表中，判斷指針變量P指向尾結(jié)點(diǎn)的條件是C．p->next->next==NULLD．p->next==NULL4．迪杰斯特拉(Dijkstra)算法的功能是A．求圖中某頂點(diǎn)到其他頂點(diǎn)的最短路徑B．求圖中所有頂點(diǎn)之間的最短路徑C．求圖的最小生成樹(shù)D．求圖的拓?fù)渑判蛐蛄?．A是7×4的二維數(shù)組，按行優(yōu)先方式順序存儲(chǔ)，元素A[0][0]的存儲(chǔ)地址為1000，若每個(gè)元素占2個(gè)字節(jié)，則元素A[3][3]的存儲(chǔ)地址為7．深度為4的完全二叉樹(shù)的結(jié)點(diǎn)數(shù)至少為A．4B．88．若采用鄰接矩陣A存儲(chǔ)有向圖G，則結(jié)點(diǎn)k的入度等于A中A．結(jié)點(diǎn)k對(duì)應(yīng)行元素之和B．結(jié)點(diǎn)k對(duì)應(yīng)列元素之和C．結(jié)點(diǎn)k對(duì)應(yīng)行和列元素之和D．非零元素之和A．對(duì)稱矩陣B．對(duì)角矩陣C．三角矩陣D．單位矩陣10．下列關(guān)于有向帶權(quán)圖G的敘述中，錯(cuò)誤的是A．圖G的任何一棵生成樹(shù)都不含有回路B．圖G生成樹(shù)所含的邊數(shù)等于頂點(diǎn)數(shù)減1C．圖G含有回路時(shí)無(wú)法得到拓?fù)湫蛄蠨．圖G的最小生成樹(shù)總是唯一的A．冒泡排序B．希爾排序C．直接插入排序D．直接選擇排序12．對(duì)下圖進(jìn)行拓?fù)渑判颍梢缘玫降耐負(fù)湫蛄惺?3．下列線性表中，能使用二分查找的是A．順序查找B．分塊查找C．散列查找D．基于B樹(shù)的查找15．下列排序算法中，時(shí)間復(fù)雜度為O(nlogn)的算法是A序16．?dāng)?shù)據(jù)的同一種邏輯結(jié)構(gòu)，可以對(duì)應(yīng)多種不同的_____存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))_____。17．若在長(zhǎng)度為n的順序表第i個(gè)元素之前插入一個(gè)元素，則需要向后移動(dòng)的元素個(gè)數(shù)是_n-i+1_________。____操作。22．圖的遍歷方法有兩種，一種是深度優(yōu)先遍歷，另一種是____廣度優(yōu)先遍歷______。23．如果排序算法是穩(wěn)定的，則關(guān)鍵字相同的兩個(gè)記錄排序前后相對(duì)次序____不變______。查法處理沖突，則關(guān)鍵字為60的結(jié)點(diǎn)保存的地址是_____7____。26．設(shè)Q[M]是有M個(gè)元素存儲(chǔ)空間的循環(huán)隊(duì)列，若front指向隊(duì)首元素，rear指向隊(duì)尾分別用C語(yǔ)言描述下列操作：(1)將元素x入隊(duì)；(3)計(jì)算當(dāng)前隊(duì)列中元素個(gè)數(shù)。(1)畫(huà)出對(duì)應(yīng)的圖G(2)畫(huà)出圖G的最小生成樹(shù)下列函數(shù)并回答問(wèn)題}LinkNode；TypedefLinkNode*Linklist；{while(q!=NULL)if(q->data==x){}}}(1)執(zhí)行該函數(shù)后，單鏈表head中data值為x的結(jié)點(diǎn)數(shù)是多少?(2)該函數(shù)的功能是什么?函數(shù)并回答問(wèn)題}BinTNode；{if(bt!=NULL){Inorder(bt->lchild)；rchild}}(1)給出對(duì)如題31圖所示的二叉樹(shù)執(zhí)行函數(shù)Inorder后得到的輸出序列。(2)該函數(shù)的功能是什么?32．下列函數(shù)實(shí)現(xiàn)直接插入排序，請(qǐng)?zhí)顚?xiě)適當(dāng)內(nèi)容，使其功能完整。{{r[0]-r[i]；while((3)){r[j+1]_=r[j]；}r[j+l]=r[0]；}}(1)在空白處填寫(xiě)適當(dāng)內(nèi)容，使函數(shù)功能完整。(2)查找成功時(shí)函數(shù)的返回值是什么?(3)查找失敗時(shí)函數(shù)的返回值是什么?while(10w<=high){if(R[mid].key==k)if(R[mid].key>k)low=mid+l；}}}LinkNode；typedefLinkNode*LinkList；請(qǐng)編寫(xiě)原型為intListisequal(LinkListA，LinkListB)的函數(shù)，指針A、B分別指向兩個(gè)帶頭結(jié)點(diǎn)的單鏈表。函數(shù)功能是：若單鏈表A、B中全部對(duì)應(yīng)結(jié)點(diǎn)的data值相等，則返回1，否則返回0。，請(qǐng)將其選出并將“答題紙”的相應(yīng)A.棧B.鏈表C.順序表D.二叉鏈表A.2B.3C.4D..6A列是一種先進(jìn)先出的線性表B表C是否為空AB.節(jié)省存儲(chǔ)空間C便于輸入輸出D.降低時(shí)間復(fù)雜度A.14B.64AneB.eC2D.411.對(duì)序列(15,9,7,8,20,-1,4)進(jìn)行排序,若一趟排序后的結(jié)果為(-1,15,9,7,8,20,4),則采用的排序方法是A