嵌入式系統(tǒng)開(kāi)發(fā)人員C語(yǔ)言測(cè)試題函數(shù)問(wèn)答填空

填空題chars[]="\"Name\\Address\"\n";s所占的字節(jié)數(shù)是 。s[100],d[100];intj=0,i=0s中已賦字符串，請(qǐng)?zhí)睿ㄗⅲ翰坏檬褂枚禾?hào)表達(dá)式）while([i]){d[j]= ;j++;}d[j]=0;a"1234",b"5"，則輸入數(shù)據(jù)的形式應(yīng)該是 。Chara[10],b;Scanf("a=%sb=%c",a,%b);對(duì)于以下遞歸函數(shù)f，調(diào)用f(3)的返回值。f(intn){return((n>0)?2*f(n-1)+f(n-2):-1);}以下函數(shù)調(diào)用語(yǔ)句中含個(gè)實(shí)參。func((exp1,exp2),(exp3,exp4,exp5));下面程序的功能是在一個(gè)字符數(shù)組中查找一個(gè)指定的字符,若數(shù)組中含有該();-1#include<stdio.h>#include<string.h>main(){charc='a',t[50];intn,k,j;gets(t);n= ;for(k=0;k<n;k++){if(( elsej-=1;printf("%d",j);}}下面程序的功能是在三個(gè)字符串中找出最小的。請(qǐng)?zhí)羁铡?include<stdio.h>#inculde<string.h>main(){chars[20],str[3][20];inti;for(i=0;i<3;i++)gets(str[i]);strcpy(s, );if(strcmp(str[2],s)<0)strcpy(s,str[2]);printf("%s\n", );}下面程序段的運(yùn)行結(jié)果 charch[]="600";inta,s=0;for(a=0;ch[a]>='0'&&ch[a]<='9';a++){s=10*s+ch[a]-'0';}printf("%d",s);下列程序段的輸出結(jié)。intm;intf(intx){staticintk=0;x-=k++;returnx;}m=f(f(3));printf("%d",m);下列程序段的輸出。#includeintf(intm){staticintk=0;ints=0;for(;k<=m;k++)s++;returns;}voidmain(){ ints1,s1=f(5);s2=f(3);printf("%d%sn",s1,s2);}函數(shù)voidf(chars[],chart[]){intk=0;while(s[k]=t[k])k++;}等價(jià)于：voidf(char*s,char*t){while( );}下程序段的輸出。#include void fun(){staticinta=5;a++;printf("a=%d\n",a);}main(){for(inti=0;i<2;i++)fun();}問(wèn)答與設(shè)計(jì)指出下面的函數(shù)的錯(cuò)誤。intsquare(volatileint*ptr){return*ptr**ptr;}(recursion)??????return?說(shuō)明為什么要禁止函數(shù)直接或間接調(diào)用自己？exit()return??main()?switchif?switchdefault分支嗎？switchbreak?(nullloops)(infiniteloops)?continuebreak?(iterativeprocessing)?C?請(qǐng)修改以下代碼：includestudio.hmain{}/*thisprogramprintsthenumberofweeksinayear./*(intss:=52;print(Therearesweeksinayear");函數(shù)名可以作實(shí)參嗎？如果可以，請(qǐng)舉例說(shuō)明；如果不可以，請(qǐng)說(shuō)明原因。如何定義和說(shuō)明可變參數(shù)的函數(shù)？3a=pow(a,3.0);a=a*a*a;能夠優(yōu)化代碼，說(shuō)明原因。htoi(s（0x00~9，a~、以及A~。squeeze(s1,s1s2中字符匹配的各個(gè)字符都刪除掉。any(s1,s2s1中的第一次出s1s2-1。setbits(x,p,n,xx從第p位開(kāi)始的n位被置為y的最右邊n位的值，其余各位保持不變。invert(x,p,n)xxp位開(kāi)始的n位被求反（1變成，0變成，其余各位保持不變。rightrot(x,x向右循環(huán)移動(dòng)n位所得到的值。在求反碼時(shí)，表達(dá)式x&=(x-1)用于把x1的位刪除掉。請(qǐng)解釋一下這樣做的道理。用這一方法重寫bitcount使用條件表達(dá)式重寫用于將大寫字母轉(zhuǎn)換成小寫字母的函數(shù)lowe。escape(s,t，將字符串t拷貝到字符串s中，并在拷貝過(guò)程中將\n與\t等換碼序列。使用switch語(yǔ)句。再編寫一個(gè)具有相反功能的函數(shù)，在拷貝過(guò)程中將換碼序列轉(zhuǎn)換成實(shí)際字符。expand(s1,s2)s1a-z一類的速記等號(hào)在字符串s2中擴(kuò)展成等價(jià)的完整列表abc..xyz。允許處理大小寫字母和數(shù)字，并可以處理諸如a-b-c與a-z0-9與-a-z等情況。正確安排好前導(dǎo)與尾隨的"-"修改itoa函數(shù)使之改為接收三個(gè)變?cè)５谌齻€(gè)變?cè)亲钚∮驅(qū)?。為了保證轉(zhuǎn)換得的數(shù)（即字符串表示的數(shù)）格。ungets(s)ungets函數(shù)要bufbufpungetch函數(shù)？swap(t,x,t類型的兩個(gè)變?cè)ㄊ褂梅殖绦蚪Y(jié)構(gòu)。請(qǐng)比較一下值調(diào)用與引用調(diào)用的相同點(diǎn)和不同點(diǎn)。在函數(shù)調(diào)用時(shí)，實(shí)參與形參有哪幾種對(duì)應(yīng)關(guān)系？用遞歸方法求N的階乘。對(duì)于以下遞歸函數(shù)ff(3)的值。intf(intk){return(k<0?(k*=2):f(k-2)+k);}sum(number)number(number是長(zhǎng)整型sum(654321)=21。選擇題下面關(guān)于算法說(shuō)法錯(cuò)誤的。算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)為解決某問(wèn)題的算法同為該問(wèn)題編寫的程序含義是相同的算法的可行性是指指令不能有二義性以上幾個(gè)都是錯(cuò)誤的下面說(shuō)法錯(cuò)誤的.算法原地工作的含義是指不需要任何額外的輔助空間在相同的規(guī)模nO(n)O(2n)的算法所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度。for(inti;i<n;i++){for(intj=o;j<n;j++){x:=x+1;}}a.0(2n) b.0(n) c.0(n2) d.O(log2n)下面說(shuō)法正確的。數(shù)據(jù)元素是數(shù)據(jù)的最小單位；數(shù)據(jù)元素是數(shù)據(jù)的最小單位；數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)下面說(shuō)法正確的。在順序存儲(chǔ)結(jié)構(gòu)中，有時(shí)也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實(shí)現(xiàn)應(yīng)用程序與存儲(chǔ)結(jié)構(gòu)的獨(dú)立,它依賴于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu)下述 是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)。存儲(chǔ)密度大插入運(yùn)算方便刪除運(yùn)算方便可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示下面關(guān)于線性表的敘述中，錯(cuò)誤的。線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元線性表采用鏈接存儲(chǔ)，便于插入和刪除操作某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一元素，則采存儲(chǔ)方式最節(jié)省時(shí)間。a.順序表 b.雙鏈表 c.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 d.單循環(huán)鏈表靜態(tài)鏈表中指針表示的。a.內(nèi)存地址 b.數(shù)組下標(biāo) c.下一元素地址 d.左、右孩子地址下面的敘述不正確的。線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)下面說(shuō)法錯(cuò)誤的。i個(gè)元素的時(shí)間與i無(wú)關(guān)。靜態(tài)鏈表中能容納的元素個(gè)數(shù)的最大數(shù)在表定義時(shí)就確定了，以后不能增加。靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動(dòng)。靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。在雙向鏈表指針p的結(jié)點(diǎn)前插入一個(gè)指針q的結(jié)點(diǎn)操作。p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;下面說(shuō)法正確的。順序存儲(chǔ)結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作；線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的；順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好；順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。下面說(shuō)法正確的。線性表只能用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。,結(jié)構(gòu)中效率高。下面說(shuō)法正確的。數(shù)據(jù)元素是數(shù)據(jù)的最小單位。隊(duì)列邏輯上是一個(gè)下端口和上端能增加又能減少的線性表。任何一個(gè)遞歸過(guò)程都可以轉(zhuǎn)換成非遞歸過(guò)程。只有那種使用了局部變量的遞歸過(guò)程在轉(zhuǎn)換成非遞歸過(guò)程時(shí)才必須使用棧。下面說(shuō)法正確的。數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對(duì)它進(jìn)行插入、刪除等操作。兩分法插入排序所需比較次數(shù)與待排序記錄的初始排列狀態(tài)相關(guān)。當(dāng)待排序記錄已經(jīng)從小到大排序或者已經(jīng)從大到小排序時(shí)，快速排序的執(zhí)行時(shí)間最省。中元素個(gè)數(shù)有關(guān)，而且與每塊中元素個(gè)數(shù)有關(guān)。下面說(shuō)法正確的。在執(zhí)行某個(gè)排序算法過(guò)程中，出現(xiàn)了排序碼朝著最終排序序列相反方向移動(dòng)，則該算法是不穩(wěn)定的。堆排序是穩(wěn)定的排序方法。在分配排序時(shí)，最高位優(yōu)先分配法比最低位優(yōu)先分配法簡(jiǎn)單。最佳兩叉排序樹(shù)的任何子樹(shù)都是最佳的。具有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是。a.[log2n] b.[LOG2N]/1 c.[LOG2(N/1)] d.[LOG2N]-1用單循環(huán)鏈表表示隊(duì)列，正確的說(shuō)法是： ?？稍O(shè)一個(gè)頭指針使入隊(duì)、出隊(duì)都方便可設(shè)一個(gè)尾指針使入隊(duì)、出隊(duì)都方便必須設(shè)頭尾指針才能使入隊(duì)、出隊(duì)都方便只可能使入隊(duì)方便一個(gè)哈希函數(shù)被認(rèn)為"好的"，如果它滿足條件 。哈希地址分布均勻保證不產(chǎn)生沖突所有哈希地址在表長(zhǎng)范圍內(nèi)d.滿足(2)和(3)ISAM文件和VSAM文件屬。索引非排序文件索引順序文件順序文件散列文件在下述排序算法算法是穩(wěn)定的排序算法。希爾排序快速排序冒泡排序堆排序在下述三種排序算法中，所需輔助存儲(chǔ)量最多的，所需存儲(chǔ)量最的是 ，平均速度最快的。a.堆排列 b.快速排列 歸并排列存貯稀疏圖的數(shù)據(jù)結(jié)構(gòu)常有的。a.鄰接矩陣 b.三元組 c.鄰接表 d.十字鏈表內(nèi)部排序多個(gè)關(guān)鍵字的文件最壞情況下最快的排列方法相應(yīng)的間復(fù)雜度該算法是的穩(wěn)定。a.快速排序 b.插入排序 c.歸并排序 d.簡(jiǎn)單選擇排序e.O(nlog2(n)fO(n^2) gO(n^2log2(n)hO(ni.j.不穩(wěn)定倒排文件包含若干個(gè)倒排表，倒排表的內(nèi)容。一個(gè)關(guān)鍵字值和關(guān)鍵字的記錄地址；一個(gè)屬性值和該屬性的一個(gè)記錄地址；一個(gè)屬性值和該屬性的全部屬性地址；多個(gè)關(guān)鍵字值和它們對(duì)應(yīng)的某個(gè)記錄的地址。在下述幾種樹(shù)當(dāng), 可以表示靜態(tài)查找.;;B-樹(shù)平衡二叉樹(shù)選擇填空：在文件局部有序或文件長(zhǎng)度較小的情況最優(yōu)內(nèi)部排序的方法.快速排序在最壞的情況,時(shí)間復(fù)雜度, 的性能;就平均時(shí)間而, 最佳.:(1)直接插入排序:(1)O(nlog(n))(2)起泡排序(2)O(n^2)(3)簡(jiǎn)單選擇排序;(3)O(n^3)c.:(1)堆排序(2)起泡排序(3)選擇排序.d.:(1)堆排序(2)快速排序(3)歸并排序.算法的時(shí)間復(fù)雜度取決。問(wèn)題的規(guī)模待處理數(shù)據(jù)的初態(tài)bothaandb假定有k個(gè)關(guān)鍵字互為同義,若用線性探測(cè)法把這k個(gè)關(guān)鍵字存入散列中,至少要進(jìn)次探測(cè)。k-1kk=1d.k(k+1)/2O(nlog2(n)),,則可:快速排序堆排序歸并排序直接插入排序?qū)蓚€(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表,其最少的比較次數(shù)是 。n2n-12nn-1下述二叉樹(shù), 滿足性:從任意結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)列按其關(guān)鍵字有序。二叉排序樹(shù)哈夫曼樹(shù)AVL樹(shù)堆若在線性表中采用折半查找法查找元素，該線性表應(yīng)。元素按值有序"元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)若二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左右子樹(shù)的位置利用 遍歷方法最合適。a.前序 b.中序 c.后序 d.按層次對(duì)二叉排序樹(shù)進(jìn)遍歷，可以得到該二叉樹(shù)所有結(jié)點(diǎn)構(gòu)成的排序序列。a.前序 b.中序 c.后序 d.按層次后將其放在已排序序列的合適位置，該排序方法稱為 排序法。a.插入 b.選擇 c.謝爾 d.二路歸排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是a.插入 b.選擇 c.泡 d.快速

排序法。下面給出的四種排序法排序法是不穩(wěn)定性排序法。a.插入 b.泡 c.二路歸并 d.堆積下面哪一個(gè)方法可以判斷出一個(gè)有向圖中是否有環(huán)（回路）？a.深度優(yōu)先遍歷 b.拓樸排序 c.求最短路徑 d.求關(guān)鍵路徑下面關(guān)于程序設(shè)計(jì)風(fēng)格的說(shuō)法正確的。中序遍歷一棵二叉排序樹(shù)的節(jié)點(diǎn)就可得到排好序的節(jié)點(diǎn)序列。順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。順序查找法適用于存儲(chǔ)結(jié)構(gòu)為順序或鏈接存儲(chǔ)的線性表。棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。已知變量定義：charS[3]="AB"char*P;在執(zhí)行了語(yǔ)句P＝S之后，*（P＋2）的值。a.'B'b.'\0'c.不確定d.字符'B'的地址下面程序段的時(shí)間復(fù)雜度。for(inti=0;i<m;i++){for(intj=0;j<n;j++){A[i][j]=i*j;}}a.O(m2) b.O(n2) c.O(m*n) d.O(m+n)下列程序?yàn)閷⒁粭l數(shù)據(jù)插入棧上：voidadd(inttop,elementitem){if(top>=MAX_STACK_SIZE-1)returnstack_full();stack[ ]=item;}則在stack[ ]的中括號(hào)內(nèi)橫線上的正確內(nèi)容應(yīng)為。a.++*top b.*top++ c.*top-- d.*top有如下函數(shù)：voidfun(structnodeh1,structnodeh2){structnode*t;t=h1;while(t->next!='\0')t=t->next;t->next=h2;}其中形參h1和h2分別指向2個(gè)不同鏈表的第一個(gè)結(jié)點(diǎn)，此函數(shù)的功能是。h2h1后h1h2后h1的最后一個(gè)結(jié)點(diǎn)由指針?lè)祷豩1拆分成兩個(gè)鏈表一個(gè)棧的入棧序列是abcde，則棧的不可能輸出序列是： 。a.edcba b.decbac.dceab d.abcde下面說(shuō)法正確的。隊(duì)列邏輯上是一個(gè)表頭和表尾既能插入又能刪除的線性表。任何一個(gè)遞歸過(guò)程都可以轉(zhuǎn)換成非遞歸過(guò)程。n{k1,k2,…,kn}相對(duì)應(yīng)的堆是唯一的。數(shù)有關(guān)，而與每塊中元素個(gè)數(shù)無(wú)關(guān)。下面說(shuō)法正確的。105Shell排序、堆排序及各種直接排序法都快。哈希表查找無(wú)需進(jìn)行關(guān)鍵字的比較。在執(zhí)行某個(gè)排序過(guò)程中，出現(xiàn)排序碼朝著最終位置相反方向移動(dòng)，則該算法是不穩(wěn)定的。B樹(shù)查找算法的時(shí)間復(fù)雜性為（。下列有關(guān)線性表的敘述中，正確的。線性表中的元素之間隔是線性關(guān)系線性表中至少有一個(gè)元素線性表中任何一個(gè)元素有且僅有一個(gè)直接前趨線性表中任何一個(gè)元素有且僅有一個(gè)直接后繼下列關(guān)于串的敘述中，正確的。一個(gè)串的字符個(gè)數(shù)即該串的長(zhǎng)度1空串是由一個(gè)空格字符組成的串S1S2若長(zhǎng)度相同，則這兩個(gè)串相等4個(gè)元素3和4依次通過(guò)一個(gè)棧在4進(jìn)棧前棧的狀態(tài) 。不可能的出棧序。a.a4，a3，a2，a1 b.a3，a2，a4，a1c.a3，a1，a4，a2 d.a3，a4，a2，a1Q[0..m－1]rearqulen分別指示循 。rear－qulenrear－qulen＋mm－qulen1＋（rear＋m－qulen）modm115個(gè)結(jié)點(diǎn)的二叉樹(shù)中，最小高度是 。a.6 b.5 c.4 d.3下列四種排序方法中，不穩(wěn)定的方法。a.直接插入排序 b.冒泡排序c.歸并排序 d.直接選擇排序設(shè)有一個(gè)長(zhǎng)度為100的已排好序的表用二分查找進(jìn)行查找若查找不成功至少比較 次。a.9 b.8 c.7 d.6一棵二叉排序樹(shù)T，用 方法進(jìn)行遍歷，可以得到各結(jié)點(diǎn)鍵值的遞增列。a.先根遍歷 b.中根遍歷c.層次遍歷 d.后根遍歷xyTxy之前，而在后根序列中x在y之后，則x和y的關(guān)系。a.x是y的左兄弟 b.x是y的右兄弟c.x是y的祖先 d.x是y的后代下面說(shuō)法正確的。數(shù)據(jù)的機(jī)內(nèi)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。線性表的鏈接存儲(chǔ)，表中元素的邏輯順序與物理順序一定相同。2。由二叉樹(shù)結(jié)點(diǎn)的先根序列的后根序列可以唯一地確定一棵二叉樹(shù)。下面說(shuō)法正確的。a.和序列3，2，4，1，6）進(jìn)行排序，兩者的比較次數(shù)不相同。1的結(jié)點(diǎn)。用二分查找法對(duì)一個(gè)順序表進(jìn)行查找，這個(gè)順序表可以是按各鍵值排好序的，也可以是沒(méi)有按鍵值排好序的。順序文件適宜順序存取，不適宜隨機(jī)存取。下列算法中，某一輪結(jié)束后未必能選出一個(gè)元素放在其最終位置上的是 。a.堆排序 b.冒泡排序 c.直接插入排序 d.快速排序 是不穩(wěn)定的排序方法。a.冒泡排序 b.歸并排序 c.堆排序 d.選擇排序從邏輯上，可以將數(shù)據(jù)結(jié)構(gòu)分兩類。a.動(dòng)態(tài)表和靜態(tài)表 b.順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)c.線性結(jié)構(gòu)和非線性結(jié)構(gòu) d.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)填空題下面程序段的時(shí)間復(fù)雜度。sum=1；for(i=0;sum<n;i++){sum+=1;}下列程序的功能是創(chuàng)建單向鏈表，請(qǐng)補(bǔ)充完整。#include<stdio.h>#include<alloc.h>structlink{char int mark;structlink *next;};voidinsert(char*name,intmark);structlink*head=NULL;main(){char int mark;struct link*t;while(1){scanf("%s%d", name, if(strcmp(name,"#")==0){break;} (1) ;}for(t=head; (2) ){printf("<%s>:%d\n", t->name, t->mark);}}voidinsert(char*name,intmark){structlink*p;p= (3) ;strcpy(p->name, p->mark=mark; (4) if(head!=NULL){ (5) ;}head=p;}用循環(huán)鏈表表示的隊(duì)列長(zhǎng)度為n，若只設(shè)頭指,則出隊(duì)和入隊(duì)的時(shí)間復(fù)度分別是 和 ；若只設(shè)尾指針,則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是 和 。在n個(gè)記錄的有序順序表中進(jìn)行折半查,最大的比較次數(shù)。仔細(xì)閱讀下列程序，在空白處填入適當(dāng)?shù)恼Z(yǔ)句。match(s,t)st匹配的字符，若存在一個(gè)匹配，則返回t在s-1*b始終指向s的第一元素。Match(s,t)Chars,t;｛char*b=s;char*p,*r;for ｛for(p=s,r=t;*r!=`\0`&&*p==*r;p++,r++);if return(s-b);｝return(-1);｝補(bǔ)充下列程序：設(shè)一棵二叉序列樹(shù)b，下列算法函數(shù)是實(shí)現(xiàn)在bs。函數(shù)：voidinsert（btree*b，btree*s）{if（b==NULL）b=s；elseif（s->data==b->data）return();elseif(s->data<b->data)；else；}n×n的下三角矩陣A按行存于一個(gè)一維數(shù)組B[1..n（n＋1）/2]中，對(duì)其中的任一元素aij，若在B中的位置為k，則k＝ 。含有100個(gè)結(jié)點(diǎn)的樹(shù)條邊。設(shè)一個(gè)閉散列表的容量為m，用線性控測(cè)法解決沖突，要插入一個(gè)鍵值，插入成功，至多要進(jìn)次比較。設(shè)二維數(shù)組每個(gè)元素（整數(shù)）占２個(gè)存儲(chǔ)單元元素按行的順序存儲(chǔ)數(shù)組的起始地址為元素的地址 線性表L＝（a1，a2，...，an）采用順序存儲(chǔ)，假定在不同的n＋1個(gè)位置上插入的概率相同，則插入一個(gè)新元素平均需要移動(dòng)的元素個(gè)數(shù)。設(shè)棧S和隊(duì)列Q的初始狀態(tài)皆為空，元素a1，a2，a3，a4，a5和a6依次通過(guò)一個(gè)棧，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)列的順序是a6，a2，a1則棧S至少應(yīng)該容個(gè)元素。兩個(gè)序列如下：L1＝{25，57，48，37，92，86，12，33}L2＝{25，37，33，12，48，57，86，92}用冒泡排序方法分別對(duì)序列 L1和L2進(jìn)行排序，交換次序較少的是序列 。將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根結(jié)點(diǎn)開(kāi)始，由根向下，每一層從左右順序地存儲(chǔ)在一個(gè)一維數(shù)組bt[1..50]中這棵二叉樹(shù)最下面一層上最左邊一個(gè)結(jié)點(diǎn)存儲(chǔ)在數(shù)組元中。一個(gè)索引文件兩部分組成。問(wèn)答與設(shè)計(jì)說(shuō)明線性插入排序的算法及時(shí)間、空間復(fù)雜度說(shuō)明折半插入排序的算法及時(shí)間、空間復(fù)雜度說(shuō)明堆排序的算法及時(shí)間、空間復(fù)雜度說(shuō)明希爾排序的算法及時(shí)間、空間復(fù)雜度說(shuō)明快速排序的算法及時(shí)間、空間復(fù)雜度說(shuō)明基數(shù)排序的算法及時(shí)間、空間復(fù)雜度說(shuō)明交換排序的算法及時(shí)間、空間復(fù)雜度說(shuō)明選擇排序的算法及時(shí)間、空間復(fù)雜度說(shuō)明歸并排序的算法及時(shí)間、空間復(fù)雜度說(shuō)明分布排序的算法及時(shí)間、空間復(fù)雜度說(shuō)明順序查找的算法及時(shí)間、空間復(fù)雜度說(shuō)明折半查找的算法及時(shí)間、空間復(fù)雜度說(shuō)明分塊查找的算法及時(shí)間、空間復(fù)雜度說(shuō)明比較查找的算法及時(shí)間、空間復(fù)雜度說(shuō)明基數(shù)查找的算法及時(shí)間、空間復(fù)雜度說(shuō)明哈希查找的算法及時(shí)間、空間復(fù)雜度?在一個(gè)包含n個(gè)元素的數(shù)組M中查找一個(gè)元素x。算法假設(shè)M升序排列了，請(qǐng)寫出二分搜索算法的步驟。已知鏈表節(jié)點(diǎn)的類型定義如下，需要按照成員value寫出算法：#include<stdio.h>#include<stdlib.h>typedefstructSTRUCT{intvalue;structSTRUCT*next;}TS;什么是算法？算法的主要特點(diǎn)是什么？如何評(píng)價(jià)一個(gè)算法？什么是順序存儲(chǔ)結(jié)構(gòu)？什么是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)？線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)各有什么特點(diǎn)？若順序表Ax以保證表的有序性，試給出其算法。（934）A=(11,16,8,5,14,10,38,23)轉(zhuǎn)換成一個(gè)按升序排列的有序線性表（用鏈表實(shí)現(xiàn)。簡(jiǎn)述棧和線性表的區(qū)別和聯(lián)系。何為棧和隊(duì)列？簡(jiǎn)述兩者的區(qū)別和聯(lián)系。若依次讀入數(shù)據(jù)元素序列{a,b,c,d}進(jìn)棧，進(jìn)棧過(guò)程中允許出棧,試寫出各種可能的出棧元素序列。將下列各算術(shù)運(yùn)算式表示成波蘭式和逆波蘭式：(A*(B+C)+D)*E-F*GA*(B-D)+H/(D+E)-S/N*T(A-C)*(B+D)+(E-F)/(G+H)3+4/25*8-6的操作數(shù)棧和運(yùn)算符棧的變化情況。a,b,c,d后棧的狀態(tài)，然后再畫(huà)出此時(shí)的棧頂元素出棧后的狀態(tài)。一個(gè)結(jié)點(diǎn)的算法。有一個(gè)循環(huán)隊(duì)列r和，stackQ(m)，其中進(jìn)隊(duì)指針r，stack中逐個(gè)出棧并同時(shí)將出棧的元素進(jìn)隊(duì)的算法。兩個(gè)字符串相等的充要條件是什么？串有哪幾種存儲(chǔ)結(jié)構(gòu)？設(shè)字符串采用塊鏈存儲(chǔ)結(jié)構(gòu)，塊鏈中每個(gè)結(jié)點(diǎn)存放m（m=4）寫出實(shí)現(xiàn)字符串刪除的算法。s1s21s2s1中出現(xiàn)的字符的算法。按行優(yōu)先存儲(chǔ)方式，寫出三維數(shù)組A[3][2][4]在內(nèi)存中的排列順序及地址計(jì)算公式（假設(shè)每個(gè)數(shù)組元素占用 L個(gè)字節(jié)的內(nèi)存單元，a[0][0][0]的內(nèi)存地址為。按列優(yōu)先存儲(chǔ)方式，寫出三維數(shù)組A[3][2][4]在內(nèi)存中的排列順序及地址計(jì)算公式（假設(shè)每個(gè)數(shù)組元素占用 L個(gè)字節(jié)的內(nèi)存單元，a[0][0][0]的內(nèi)存地址為。.An′n，它的下三角部分全為B[m]中(m足夠大)B[k]=a[i][j]k=f1(i)+f2(j)+c。試推出f1、f2及常數(shù)c（f1f2中不含常數(shù)項(xiàng)。Am′nA[i][j]ij列中Am′n，試編寫求出矩陣中所有馬鞍點(diǎn)的算法，并分析你的算法在最壞情況下的時(shí)間復(fù)雜度。試寫一個(gè)算法，查找十字鏈表中某一非零元素x。??畫(huà)出下列廣義表的圖形表示(1) A(b,(A,a,C(A)),C(A))(2) D(A(),B(e),C(a,L(b,c,d)))舉例說(shuō)明之。的數(shù)據(jù)結(jié)構(gòu)。這樣說(shuō)法對(duì)嗎？舉例說(shuō)明之。評(píng)價(jià)各種不同數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么？評(píng)價(jià)一個(gè)好的算法，需要從哪幾方面來(lái)考慮的？什么是算法的時(shí)間復(fù)雜性？什么是抽象數(shù)據(jù)類型？數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別？數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)由哪四種基本的存儲(chǔ)方法實(shí)現(xiàn)？運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面。試舉一例，說(shuō)明兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)是兩個(gè)不同的結(jié)構(gòu)。,??試舉一例，說(shuō)明對(duì)相同的邏輯結(jié)構(gòu),其運(yùn)算效率不同。A1A2A1Tl=O(2n)，2的時(shí)間復(fù)雜度為分析下面程序段中循環(huán)語(yǔ)句的執(zhí)行次數(shù)。Inti=0,s=0,n=100;Do{i:=i+1;s:=s+10*i;}while((I<n)&&(s<n))根據(jù)下面程序，回答下面問(wèn)題：f(n)f(n);假定n=5，試指出f(5)值的大小和執(zhí)行f(5)時(shí)的輸出結(jié)果。intf(int n){inti,j,k,sum=0;for(i=l;i<n+1;i++){for(j=n;j>i-1;j--){for(k=1;k<j+1;k++){sum++;printf("sum=%d\n",sum)；}}}return(sum);}nm度。intm=0;For(inti=0;i<n;i++){for(intj=2*i,j<n;j++){m=m+1;}}試給出下面兩個(gè)算法的運(yùn)算時(shí)間。for(intI=0;I<n;I++){x++;}for(intI=1;I<n;I++){for(intj=1;j<n;j++){x++;}}快速排序的最大遞歸深度是多少？最小遞歸深度是多少？對(duì)鏈表設(shè)置表頭節(jié)點(diǎn)的作用是什么？3,4先出的序列有哪（３在４之前出棧）試寫出進(jìn)棧操作，出棧操作算法的時(shí)間復(fù)雜性。NEXT信息幀。（976）某整型數(shù)組Ａ的１０個(gè)元素值依次為6,2,9,7,3,8,4,5,0,1,用下列各排序方法，將Ａ中元素由小到大排序。(1)取第一個(gè)元素值６作為分割數(shù)，(2)試寫出快速排序第一次分隔后Ａ中的結(jié)果。(3)用堆排序，(4)試寫出將第一個(gè)選出的數(shù)據(jù)放在Ａ的最后位置上，(5)將Ａ調(diào)整成堆后的Ａ中結(jié)果。(6)用基數(shù)為３的基數(shù)排序法，(7)試寫出第一次分配和收集后Ａ中的結(jié)果。已知某排序平衡二叉樹(shù)Ｔ具有下列特點(diǎn)：19范圍內(nèi)；n1的葉結(jié)點(diǎn)，若刪去該結(jié)點(diǎn)，立即插入一個(gè)關(guān)鍵字為n1的結(jié)點(diǎn)，得到的平衡樹(shù)與原Ｔ不相同；(３)在Ｔ中存在另一個(gè)關(guān)鍵字為n2的非葉結(jié)點(diǎn)，刪去它，并立即插入n2結(jié)點(diǎn)，得到與原Ｔ相同的平衡樹(shù)；(４)在Ｔ中插入某n3結(jié)點(diǎn)后立即刪除它，得到的平衡樹(shù)與原Ｔ不相同。試畫(huà)出具有上述特點(diǎn)的最簡(jiǎn)單（結(jié)點(diǎn)個(gè)數(shù)最少）n1,n2,n3于幾？head，鏈表的記錄中包含著整數(shù)類型的key域key遞增的次序進(jìn)行就地排序。()來(lái)模擬，樹(shù)中結(jié)點(diǎn)的值為記錄在文件中的位置序號(hào)。若文件中有l(wèi)9個(gè)記錄，請(qǐng)畫(huà)出這棵判定樹(shù)；當(dāng)文件中有n個(gè)記錄時(shí)，求出該判定樹(shù)的深度。試舉例說(shuō)明用程序設(shè)計(jì)語(yǔ)言描述堆棧結(jié)構(gòu)時(shí)，要涉及那些問(wèn)題？動(dòng)態(tài)查找樹(shù)，有哪幾項(xiàng)基本操作？舉例說(shuō)明有向圖的最短路徑算法常用于哪幾種情形？中斷和死鎖變量與表達(dá)式對(duì)象與屬性虛擬地址與實(shí)地址數(shù)據(jù)的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到，提供給兩個(gè)棧1和2使一棵共有n個(gè)結(jié)點(diǎn)的樹(shù)，其中所有分枝結(jié)點(diǎn)