吉林省計算機專升本歷年真題資料

這是經(jīng)過本人一點點的積累寫下去的，你要做了保你嘿嘿。除了真題(不外泄只能靠回憶沒答案，其他的都有答案，完全符合專升本的難度 分四項一、歷年真題今年吉林省計算機類專升本2+3考試題 請大家分享！2009-04-2519:56(分類:專升本相關(guān))綜合卷第一道填空題：-0填空題.線性表的順序存儲結(jié)構(gòu)是()存儲結(jié)構(gòu)；.棧底S.base,棧頂S.top,棧的大小為Statesize,棧滿的條件是()。.順序隊列A[n],隊尾r隊頭f,隊滿滿足條件()。.給一樹的后續(xù)中續(xù)遍歷，寫出前序遍歷。.一個有n個頂點e條邊的圖，頂點i的度表示為TD(Vi),那么所有頂點的度與邊的關(guān)系表示為().一個二維數(shù)組A[7][8](具體的數(shù)字記不清楚了)，第一個元素的地址是1000,按行優(yōu)先存儲，每個元素占2個存儲單元，則A[5][6]的存儲地址是().給出一組數(shù)｛4,5,10,18,6,7,12｝構(gòu)成的哈弗曼樹的帶權(quán)路徑長度是().關(guān)鍵碼集合采用閉散列表存儲，散列表長度為14,散列函數(shù)為H(key)=key%ll,其中已經(jīng)有H(15)=4,H(38)=5,H(61)=6,H(84)=7存儲完畢，采用二次探測處理沖突，關(guān)鍵碼49存儲地址是().隨機產(chǎn)生(A,B)的隨機數(shù)的語句().給出一組數(shù)9,73,5,9,1,12,8,15,采用快速排序進行一次劃分后結(jié)果是().fp是文件指針類型，寫入打開文件''abc.dat"的語句()二。選擇題1.線性表的連接存儲結(jié)構(gòu)對存儲地址()A一定連續(xù)B一定不連續(xù)C有的連續(xù)有的不連續(xù)D連續(xù)不連續(xù)都可以2順序表第i個位置插入一個元素則需()個元素后移An-iBiCn-i-1Dn-i+13給一AOV網(wǎng)圖，要求按照字母下標序號由小到大寫出拓撲序列04.如果一個入棧順序是abed,出棧后依次入隊，那么入隊序列為()其實還有很多想不起來了.給出一個樹的順序存儲結(jié)構(gòu)圖，要求根據(jù)給出的順序表畫出給樹，并將該樹轉(zhuǎn)換為二叉樹,樹的度，樹的葉子節(jié)點：.給一個無向圖，用Prim算法求出最小生成樹，要求每加入一個結(jié)點就畫一個圖，并求權(quán)值；.是給出一組值然后給一個散列函數(shù)，畫出開散列表.給一組有序數(shù)字，讓你畫出折半查找樹，并求出查找長度，以及查找某個數(shù)字需要比較多少次.給出一個圖，進行深度和廣度優(yōu)先遍歷，然后畫深度和廣度生成樹數(shù)據(jù)結(jié)構(gòu)最后一道大題，是一個程序填空一個無序的單鏈表，然后按從小到大的順序組成一個有序的單鏈表(有五個空，共十分)四。程序填空1.5!.輸入幾個學(xué)生的成績，輸出學(xué)生成績總和以及個數(shù)(輸入-1的時候結(jié)束).一個十進制的數(shù)轉(zhuǎn)成八進制逆序輸出.有10個火車站，有幾種火車票五?？闯绦?qū)懡Y(jié)果l.if(a>b)elseif(!(b>c))t=a;elset=b;printf("t=%2d",t);寫結(jié)果2.chars[2][3]={"student","and","score")；for(i=0;i<2;i++)puts(s[i]);.main(){inta=l,b=2;m=fun(a,b)*2;printf("%d",m);}intfun(intx,inty){c=x+y;returnc;}整體是這樣的，也許變量不大一樣.for(i=4;i>=l;i—){for(j=l;j<=i;j++)printf("#");for(j=l;j<=4-i;j++)printf("*");}最后一個大題記得是個從鍵盤輸入一個3*3的二維數(shù)組，然后輸出它的下三角元素(帶主對角線)

計算機技術(shù)綜合考試試題

感謝507寢室工作組精心編制做題時間120分鐘一、填空題(每空2分，共40分).設(shè)有變量說明：inta=3,b=2;則表達式a>b的值為。.若有如下定義：intx=65；則語句prinlfx)；的輸出結(jié)果是。.有條件表達式：a>b?a:c>d?c:d,若a=l,b=2,c=3,d=4,則表達式的值為.已知inta[l[3]={l,2,3,4,5,6,7}；則數(shù)組a的第一維(行)的大小是.設(shè)有語句：inti；for(i=0；i<10；i++),循環(huán)結(jié)束后i的值為。.下面程序段運行的結(jié)果是。Charc[5]={'a','b',''0','c','\0'}；Printf("％s”，c)；.已知intb[]={1>2,3,4},y,*p-b;則執(zhí)行語句y=*p++;后，變量y的值為_.C語言中，十進制數(shù)10的八進制表示方法為。.C語言中，字符型常量以碼的形式在變量中存儲。.已知struct{inti;charc;floata;}test;則結(jié)構(gòu)體變量test的存儲長度為個字節(jié)。1L設(shè)元素1,2,3,4,5依次進入棧S,在經(jīng)過操作序列為push(S,l),push(S,2),push(S,3),pop(S),push(S,4),pop(S),pop(S),push(S,5),pop(S),pop(S)之后得至U的輸出序歹！J0020020-300000-15-0000-12.一個稀疏矩陣,按照行序遞增的順序，下標從1開始構(gòu)造對應(yīng)的三元組線性表為o.一顆具有35個結(jié)點的二叉樹可能的最小深度;最大深度為。.一顆樹的廣義表表示為a(b,c(e,f(g)),d),當用孩子兄弟鏈表表示時，右指針余非空的結(jié)點個數(shù)為。.利用n個值生成哈夫曼樹中共有個結(jié)點。.具有n個頂點的強連通圖至少有條邊。.已知一個有向圖的鄰接矩陣表示，計算第i個結(jié)點的入度的方法是。.已知8個數(shù)據(jù)元素(35,75,40,15,20,55,95,65)按照依次插入點結(jié)點的方法生成一顆二叉樹排序樹后，最后兩層上的結(jié)點總數(shù)為。.若對一組記錄(46,79,56,38,40,80,35,50,74)進行直接插入排序，當把第8個記錄50插入到前面已排序的有序表時，為尋找插入位置需比較次。二、單項選擇題(每小題2分，共40分).若定義了intx；則將x強制轉(zhuǎn)化為雙精度類型應(yīng)該寫成( )A.(double)xB.x(double)C.double(x)D.(x)double.已知inti=5,執(zhí)行語句i+=++i后，i的值是()A.10B.llC.12D.A,B,C答案都不對.C語言中的函數(shù)()A.可以嵌套定義 B.不可以嵌套調(diào)用 C.可以嵌套調(diào)用不可以遞歸調(diào)用 D.嵌套調(diào)用和遞歸調(diào)用均可.合法的數(shù)組說明語句是()A.chara[]={0,1,2,3,4,5};B.inta[5]={0,1,2,3,4,5}; C.chara=^^string^^;D.inta[]=MstringM;.有字符組a[80],b[80],正確在輸出語句是()A.puts(a,b);B.printf("%s,%s”,a[],b[]);C.putchar(a,b);D.puts(a),puts(b);.已知ini*p,a；則語句p=&a；中運算符&的含義是()A.位與運算 B.邏輯與運算C.取指針內(nèi)容D.取變量地址.若inti=10；則執(zhí)行下列語句后，變量i的正確結(jié)果是()Switch(i)(case9: i+=l;case10:i+=l;case11:i+=l;default:i+=l；1A.10B.llC.12 D.13.在C語言中，二維數(shù)組的元素在內(nèi)存中存放的順序是()A.按行存放 B.按列存放C.用戶自己定義 D.由編譯程序決定.已知char*p,*q：選擇正確的語句()A.p*=3; B.p/=q;C.p+=3; D.p+=q；10.設(shè)有以下說明語句，則錯誤的敘述是()Uniondata{inti;Charc;Floatf;}a；a所占內(nèi)存長度為成員f的長度a的地址和它的成員地址都是同一地址a不可作為函數(shù)的參數(shù)D.不能對a賦值，但可以在定義a時對它初始化11.下面列出的四種時間復(fù)雜性，最好的是()A.O(n)B.0(nlog2)C.O(n)D.O(log2n)12.在一個長度為n的順序存儲的線性表中，刪除值為x的元素時需要比較元素和移動元素的總次數(shù)為()A.(n+l)/2 B.n/2C.nD.n+1.二維數(shù)組M的行下標i的范圍從0到4,列下標j的范圍從。到5,每個元素占4個存儲單元，M按行序存儲元素M⑶⑸的起始地址與M按列序存儲時元素()的起始地址相同。A.M⑵[4] B.M[3][4]C.M[3][5]D.M[4][4].一棵度為3的樹中，度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為()個。A.3 B.4 C.5 D.6.對于一個具有n個頂點的無向連通圖，它包含的連通分量的個數(shù)為()A.0B.lC.nD.n+1.已知一個圖如下所示，若從從頂點a出發(fā)按深度優(yōu)先搜索遍歷，可能得到的一種遍歷序列為()a,b,e,c,d,fa,c,f,e,b,da,e,d,f,c,bD.a,e,b,c,f,d17.已知一個有向圖如下所示，由該圖得到的一種拓撲序列為（）V,,V4,V6,V2,V5,V3VI,V2,V3,V4,V5,V6V,,V4,V2,V3,V6,V5VI,V2,V4,V6,V3,V518.對于一個長度為18的順序存儲的有序表，若采用折半查找，則查找第15個元素的查找長度為()A.3 B.4C.5 D.619.對下列四個序列進行快速排序，各以第一個元素為基準進行第一次劃分，則在該次劃分過程中需要移動元素次數(shù)最多的序列是()A.1,3,5,7,9 B.5,7,9,1,3 C.5,3,1,7,9 D.9,7,5,3,120.一組記錄的關(guān)鍵字為 (45,80,55,40,42,85),則利用堆排序的方法建立的初始堆為()A.(80,45,55,40,42,85)B.(85,80,55,45,42,40)C.(85,80,55,40,42,45)D.(85,55,80,42,45,40)三、解答題（共50分）.設(shè)有一種數(shù)據(jù)結(jié)構(gòu)B的元素集合K和它的二元關(guān)系R為：B=（K,R）K={K,,K2……K7）R—{<K],K2>,<Ki，Kj>,<K|,Kf）>,<K2,K4>,<K3,K5>,<K4,K5>,<K5,K7>,<K6,K7>}（<2,1）>表示結(jié)點a到結(jié)點b是單向的）畫出此結(jié)構(gòu)對應(yīng)的圖形，并判斷它屬于哪種邏輯結(jié)構(gòu)？（6分）.將下面所示的森林轉(zhuǎn)換成一棵二叉樹（按字母序號順序），并分別寫出二叉樹的先序、中序、后序的遍歷序列。（6分）??①J\ /\??O ? ?X?T..假設(shè)用于通信的電文有8個字母A,B,C,D,E,F,GH組成，各字母在電文中出現(xiàn)的頻率為5%,25%,4%,7%,9%,12%,30%,8%,試為這8個字母設(shè)計哈夫曼編碼，并求其帶權(quán)路長度WPL。（要求權(quán)值集取{5,25,4,7,9,12,30,8},按照左子樹權(quán)值小于右子樹的權(quán)值的順序構(gòu)造哈夫曼樹，并注明每個節(jié)點的權(quán)值。）（10分）4對下面的帶權(quán)圖按照普里姆法從頂點V1出發(fā)構(gòu)造一棵最小生成樹，并求該生成樹的權(quán)值。（要求：每加入一個結(jié)點，畫一個圖）（8分）5,設(shè)有一組關(guān)鍵字（4,9,26,10,12,33,22,19）,利用哈希函數(shù)為：H（key）=key%12,采用線性探測散列處理沖突，試在0?10的散列地址空間中對該組關(guān)鍵字構(gòu)造哈希表，并求在關(guān)鍵字的查找概率相等的前提下查找成功的平均查找長度。（要求：直接寫出哈希表格，查找長度表示為分數(shù)形式）（10分）6,對長度為n的記錄序列進行快速排序時，所需要的比較次數(shù)依賴于這幾個元素的初始序列。點n=8時，在最好的情況下共需要進行多少次比較？（要求：寫出每一趟的劃分情況和比較次數(shù)。）（10分）四，算法設(shè)計題（共10分）試編寫一個在帶有頭結(jié)點的雙向循環(huán)鏈表中為x的結(jié)點之前，插入值為y的結(jié)點的算法。（要求：用C語言描述，結(jié)點類型定義為dlnode）StatusInsertPrior-L（DlinkList&L）五、程序填空題.華氏溫度與攝氏度的轉(zhuǎn)換公式為：C=5/9X(F-32),其中表示C攝氏溫度，F(xiàn)表示華氏溫度。要求輸出從華氏0°到華氏300°,每隔20°一個值。main(){intupper,step;floatfahr=0.0,Celsius;upper=3OO;step=2O;while( 〈upper){celsius=;printf(M%f%f\n,\fahr,Celsius);.求兩數(shù)中的較大值。#include<stdio.h>main(){inta,b,max;printfCpleaseinput:\n,,);scanfC%d%dM,); max=a; max=b;printf(themaxis:%d\n”,max);).輸入一行字符，分別統(tǒng)計出其中英文字母、空格、數(shù)字和其他字符的個數(shù)。#include<stdio.h>main(){chare;intIetters=0,space=0,digit=0,other=0;printfC'pleaseinputcharacters\n")；while((c=getchar())!=,\n,){if(c>=,a,&&c<=,z,||)elseif(c>=,0,&&C<=,9,)elseprintf(4t%d%d%d%d\n'\letter,space,digit,other);4程序讀入20個整數(shù)，統(tǒng)計非負數(shù)的個數(shù)，并計算非負數(shù)的和。#include<stdio.h>main(){inti?a[20]tstcounl;s=0;count=0;for(i=0;i<20;i++)scanf(4i%d,\);for(i=0;i<20;i++){if(a[i]<0)s+=a[i];count++;)printf(4Us=%d\tcount=%d\n,\s,count);}5.計算一個3X3矩形對角線元素之和。mian(){floata[3][3],sum=O;inti,j;print(4tpleaseinputthematrix:\n");for(i=0;i<3;i++)for(j=0;j<3;j++)scanf(t<%f,,);for(i=0;i<3;i++)sum=;prinf(Mtheresultis:%f\n,5,sum);)六、讀程序?qū)懡Y(jié)果#include"stdio.h"main(){inta,b,c;printfC'pleaseinput:\n");scanf(“％d,%d,%d”,&a,&b,&c);if(a<b)if(b<c)printfCumax=%d\n,,,c);elseprinlfCtmax=%d\n,,,b);elseif(a<c)prinlf("max=%d\n",c);elseprintfCtmax=%d\n,\a);)本程序的功能為.#include<stdio.h>main(){intcount,num,total;count=0;total=0;while(count<10){count++;printfCentertheNO.%d=",count)scanf("%d”,&num);total+=num;)printf("Total=%\rT,total);)本程序若輸入0123456789十個數(shù)，輸出的結(jié)果是#include<stdio.h>inta[2][3]={(l,2,3}J4,5,6)};main(){inti,j,b[3][2];for(i=0;i<=l;i++)for(j=0;j<=2;j++)bU][i]=a[i]U];for(i=0;i<=2;i++)for(j=0;j<=l;j++)printfr%dV\b[i][j]);)本程序的輸出結(jié)果為o#include<stdio.h>main(){inta[10]={1,2,345,6,7,890};int*p,i；for(p=a;p<(a+10);p++)printf("%d”,*p);printf(u\nv);)本程序的輸出的結(jié)果是O七、編程題(共10分)請編寫一個完整的程序，要求輸入一個整型3X4矩陣，求其中最大元素的值并輸出。(答案請聯(lián)系(mail)：xpengj@163.com)

今年吉林省計算機類專升本2+3今年吉林省計算機類專升本2+3考試題專升本相關(guān))請大家分享！2009-04-2519:56(分類:經(jīng)過同學(xué)們整理，回憶，暫時這些??明年需要的同學(xué)快來看看吧?！感謝，王曉麗，常萌萌，白彩秀，李秀等同學(xué)?！綜合卷第一道填空題：一。填空題.線性表的順序存儲結(jié)構(gòu)是()存儲結(jié)構(gòu)；.棧底S.base,棧頂S.top,粘的大小為Statesize,棧滿的條件是()。.順序隊列A[n],隊尾r對頭f,隊滿滿足條件()。.給一樹的后續(xù)中續(xù)遍歷，寫出前序遍歷。.一個有n個頂點e條邊的圖，頂點i的度表示為TD(Vi),那么所有頂點的度與邊的關(guān)系表示為().一個二維數(shù)組A[7][8](具體的數(shù)字記不清楚了)，第一個元素的地址是1000,按行優(yōu)先存儲，每個元素占2個存儲單元，則A[5][6]的存儲地址是().給出一組數(shù)｛4,5,10,18,6,7,12｝構(gòu)成的哈弗曼樹的帶權(quán)路徑長度是().關(guān)鍵碼集合采用閉散列表存儲，散列表長度為14,散列函數(shù)為H(key)=key%ll,其中已經(jīng)有H(15)=4,H(38)=5,H(61)=6,H(84)=7存儲完畢，采用二次探測處理沖突，關(guān)犍碼49存儲地址是().隨機產(chǎn)生(A,B)的隨機數(shù)的語句().給出一組數(shù)9,73,5,9,1,12,8,15,采用快速排序進行一次劃分后結(jié)果是()ILfp是文件指針類型，寫入打開文件“abc.dat"的語句()二。選擇題1.線性表的連接存儲結(jié)構(gòu)對存儲地址()A一定連續(xù)B一定不連續(xù)C有的連續(xù)有的不連續(xù)D連續(xù)不連續(xù)都可以2順序表第i個位置插入一個元素則需()個元素后移An-iBiCn-i-1Dn-i+13給一VOW網(wǎng)圖，要求按照字母下標序號由小到大寫出拓撲序列()4.如果一個入棧順序是abed,出棧后依次入隊，那么入隊序列為()其實還有很多想不起來了.給出一個樹的順序存儲結(jié)構(gòu)圖，要求根據(jù)給出的順序表畫出給樹，并將該樹轉(zhuǎn)換為二叉樹,樹的度，樹的葉子節(jié)點；.給一個無向圖，用Prim算法求出最小生成樹，要求每加入一個結(jié)點就畫一個圖，并求權(quán)值；.是給出一組值然后給一個散列函數(shù)，畫出開散列表.給一組有序數(shù)字，讓你畫出折半查找樹，并求出查找長度，以及查找某個數(shù)字需要比較多少次.給出一個圖，進行深度和廣度優(yōu)先遍歷，然后畫深度和廣度生成樹數(shù)據(jù)結(jié)構(gòu)最后一道大題，是一個程序填空一個無序的單鏈表，然后按從小到大的順序組成一個有序的單鏈表(有五個空，共十分)四。程序填空1.5!.輸入幾個學(xué)生的成績，輸出學(xué)生成績總和以及個數(shù)(輸入-1的時候結(jié)束).一個十進制的數(shù)轉(zhuǎn)成八進制逆序輸出.有10個火車站，有幾種火車票五。看程序?qū)懡Y(jié)果l.if(a>b)elseif(!(b>c))t=a;elset=b;printf("t=%2d",t);寫結(jié)果2.chars[2][3]={"student","and","score"};for(i=0;i<2;i++)puts(s[i]);.main(){inta=l,b=2;m=fun(a,b)*2;printf("%d",m);}intfun(intx,inty)(c=x+y;returnc;}整體是這樣的，也許變量不大一樣.for(i=4;i>=l;i—){forQ=l;j<=i;j++)printf("#");for(j=l;j<=4-i;j++)printf("*");}最后一個大題記得是個從鍵盤輸入一個3*3的二維數(shù)組，然后輸出它的下三角元素(帶主對角線)2010年吉林省普通高等學(xué)校招生“專升本”教育考試計算機科學(xué)與技術(shù)綜合試題2010.04.24考題統(tǒng)計：潘帥帥、江飛(根據(jù)回憶~題目中的數(shù)據(jù)幾乎完全正確一嘿嘿)試題一二三四五六七總分得分一、選擇題(20*2=40)(注：共20個題，只記起12個).在單鏈表的一個節(jié)點當中，指針域的個數(shù)為()A：0 B：1 C：2 D：3.intfun(float,char)函數(shù)的返回值類型()A：float B：int C：char D：voidnta=3,b=5;printf("％d,%d”,b,a);輸出的值()A：53B：3,5C：35 D：5,3.在一個有n個頂點的無向完全圖中，有()條邊A：nB：2nC：n-1 D：2x,y;for(i=l,i<x;i++)for(j=l,j<y；j++)(printfC'theonesent\n,9);)運行成尋輸出“theonesent”的行數(shù)()A：x*y B：(x-l)*y C：(x-l)*(y-l) D:x*(y-1).二叉樹中第K層，最多有()個節(jié)點A：2k B：2kJ C：2k-l D：2k+l.一個二叉樹中，有n個度為2的節(jié)點；該二叉樹有()個葉子節(jié)點;A：n+1 B：n-1 C：2n+l D：2n-l.在樹中，一個節(jié)點有三個兄弟節(jié)點，該節(jié)點的雙親節(jié)點的度為()A：2 B：3 C：4 D：5.一個循環(huán)隊列用數(shù)組A[m]存儲，沒有標記變量，則該隊列最多能輸入()個元素TOC\o"1-5"\h\zA：m-1B：mC：m+1 D：2mlO.inta=2,b=5,在TurobC中a>b的輸出值是()A：ture B:false C：1 D：01Linta=0,b=20,c=30,m,n;執(zhí)行(m=a++)&&(n=++b)后，n的值為()A：0 B：20 C：21 D：3012.在C語言中，調(diào)用數(shù)學(xué)函數(shù)，要引用的頭文件()A：stdio.hB：math.hC：graph.hD：stream.h二、填空題(20*2=40)(注：共20個題，只記起9個).一個n階的三角矩陣中它的存儲空間為.一個n個節(jié)點的的無向圖，是連通圖，至少有條邊.對圖進行廣度遍歷：要求盡量按字母序列輸出.一個有n個節(jié)點的二叉樹，用二叉鏈表儲存，有個空指針域.向一個隊列中以a,b,c,d依次入隊，則出隊的序列為.已知a[4]={l,2,3},那么a[3]的值為.已知a[4]={l,2,3},*p=a,那么*(p++)的值為.給定一待排序列{12,10,44,56,78,23},寫出用冒泡排序法進行第一趟排序后的結(jié)果 三、判斷題(5*2=10).順序表的存取結(jié)構(gòu)為順序存取.在一棵完全二叉樹當中，所有節(jié)點的度都為2.忘了~~.在一個有向圖的鄰接表中，邊表的節(jié)點數(shù)等于該圖的弧數(shù).在一個完全二叉樹中，如果一個節(jié)點沒有左子樹，那么該節(jié)點就是葉子節(jié)點

四、數(shù)據(jù)結(jié)構(gòu)應(yīng)用題.已知一棵樹如下圖所示（7分）（1）將該樹轉(zhuǎn)換成二叉樹（2）對該二叉樹，按照左根序、中根序、后跟序，寫出相應(yīng)的遍歷序列.給下列無向網(wǎng)圖（10分）（1）用鄰接矩陣存儲改圖（2）用Kruskal算法畫出最小生成樹，每一次只加一條邊.散列表題。（10分）散列函數(shù)的設(shè)計H（k）=k%7或（H（k）=kmod7），以線性探測法處理沖突，存儲下數(shù)據(jù)｛36,15,47,52,44）（1）請?zhí)顚懴卤?123456（2）查找關(guān)鍵碼44要比較幾次?.哈夫曼樹題(10分){4,5,6,7,18,10,12}(1)畫出該哈夫曼樹，要求左孩子的權(quán)值小于右孩子的權(quán)值(2)求WPL值.定義一個單鏈表節(jié)點結(jié)構(gòu)structnodeintdata;structnode*next;)；structnode*p,*q；已知指針*p和*q,p指向單鏈表中的一個節(jié)點，將q指向的節(jié)點插入到p節(jié)點的后面，寫出語句序列。五、程序填空題(每空2分，共30分)1.補充以下程序，將x和y換值voidmain()intx=5,y=3,temp;printf("％d%d”,x,y);2.用插入排序?qū)?shù)組排序intj；for(inti=2;i<n;i++)(x=r[i];j=i-l；while(j>=O&&r[j]>r[O])/*找到插入位置*/j-；); /*插入x*/).以下程序功能是輸入一個浮點型的數(shù)據(jù)，并輸出，要求保留2位小數(shù)voidmain()(floatx;printf("”,x);].忘了~~.忘了~~六、看程序?qū)懡Y(jié)果題voidmain()(inti;inta[6]={l,l};for(i=2;i<6;i++){a[i]=a[i-2]+a[i-l];)for(i=0;i<6;i++)printf(M%d }2.voidmain(){inti,j;for(i=l;i<=3;i++)(for(j=l；j<=i；j++)(printf("C”)；printf("\n"); }])#definePI3#include<stdio.h>intarea(intx,inty)(intz=PI*x*y;printf("％d”,z);}main()inta=4,b=5;area(a,b);5.main()intsage=70,s;s=sage/10;switch(s)(case9:case8:case7:case6:pintf("SUCCESS”)；break;default:printfCtFAILED,,);))七、編程題(1*10=程).在一個灰圖形脫色的時候，以如圖所示的RGB圖形矩陣為例，編寫一個程序，定義一個整型的二維數(shù)組，并在定義的時候?qū)⑵涑跏蓟?，用兩個雙For循環(huán)將矩陣中所有小于5的元素賦值為0,在用兩個For雙循環(huán)將修改后的二維矩陣按行序輸出。364914800269934二、模擬試題數(shù)據(jù)結(jié)構(gòu)模擬試卷(一)一.單項選擇題(本大題共15小題，每小題2分，共30分).如果只想得到1024個元素組成的序列中的前5個最小元素，那么用()方法最快。A、起泡排序 B、快速排序C、堆排序 D、直接選擇排序.算法分析的目的是（ ）A.辨別數(shù)據(jù)結(jié)構(gòu)的合理性B.評價算法的效率C.研究算法中輸入與輸出的關(guān)系D.鑒別算法的可讀性.在線性表的下列運算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運算是（ ）A.插入 B.刪除C.定位 D.排序.若進棧序列為1,2,3,4,5,6,且進棧和出?？梢源┎暹M行，則可能出現(xiàn)的出棧序列為（ ）A.3,2,6,1,4,5 B.5,6,4,2,3,1C.1,2,5,3,4,6 D.3,4,2,1,6,5.設(shè)串sl="DataStructureswithJava",s2="it",則子串定位函數(shù)index（sl,s2）的值為（）A.15 B.16C.17 D.186.一個順序存儲的線性表的第一個元素的存儲地址是100,每個元素的長度為4,則第4個元素的存儲地址是（）oA.108B.112C.116D.120.從一個具有n個結(jié)點的單鏈表中查找其值等于x的結(jié)點，在查找成功的情況下，平均需要比較（ ）個結(jié)點。A.n B.n/2 C.（n+l）/2D.（n-l）/2TOC\o"1-5"\h\z.在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系（ ）A.不一定相同 B.互為逆序C.都不相同 D.都相同.高度為5的二叉樹至多有結(jié)點數(shù)為（ ）A.63 B.32 C.24 D.64.若用鄰接矩陣表示一個有向圖，則其中每一列包含的"1"的個數(shù)為（ ）A.圖中每個頂點的出度 B.圖中每個頂點的入度C.圖中弧的條數(shù) D.圖中連通分量的數(shù)目.圖的鄰接矩陣表示法適用于表示（ ）A.無向圖 B.有向圖C.稠密圖 D.稀疏圖.在一個單鏈表中，若p所指的結(jié)點不是最后一個結(jié)點，在p之后插入s所指的結(jié)點，則執(zhí)行（ ）?A.s->next=p;p->next=s B.p-next=s;s->next=pC.p=s;s->next=p->next D.s->next=p->next;p->next=s.下列排序算法中，其時間復(fù)雜度和記錄的初始排列無關(guān)的是（ ）A.直接選擇排序 B.插入排序C.快速排序 D.冒泡排序.若有序表的關(guān)鍵字序列為（b,c,d,e,f,g,q,r,s,t）,則在二分查找關(guān)鍵字b的過程中，先后進

行比較的關(guān)鍵字依次為( )行比較的關(guān)鍵字依次為( ).填空題(本大題共15小題，每小題2分，共30分).在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)分線性結(jié)構(gòu)和?.稱算法的時間復(fù)雜度為0(f(n)),其含義是指算法的執(zhí)行時間和的數(shù)量級相同。.在一個長度為n的單鏈表L中，刪除鏈表中*p的前驅(qū)結(jié)點的時間復(fù)雜度為 0.假設(shè)為循環(huán)隊列分配的向量空間為Q[20],若隊列的長度和隊頭指針值分別為13和17,則當前尾指針的值為..對于棧只能在插入和刪除元素。.通常從正確性、、可讀性、效率和健壯性等5個方面評價算法(包括程序)的質(zhì)量。.在具有n個單元的循環(huán)隊列中，隊滿時共有個元素。.若對關(guān)鍵字序列(43,02,80,48,26,57,15,73,21,24,66)進行一趟增量為3的希爾排序，則得到的結(jié)果為。.在索引存儲中，若一個索引項對應(yīng)數(shù)據(jù)對象表中的一個表項(記錄)，則稱此索引為索引，若對應(yīng)數(shù)據(jù)對象表中的若干個表項，則稱此索引為索引。.二叉樹中度為0的結(jié)點數(shù)為30,度為1的結(jié)點數(shù)為30,總結(jié)點數(shù)為?.廣義表A((a,b,c),(d,e,f))的表尾為。.設(shè)有一個順序棧S,元素si,s2,s3,s4,s5,s6依次進棧，如果6個元素的出棧順序為s2,s3,s4,s6,s5,si,則順序棧的容量至少應(yīng)為。.根據(jù)一組記錄(56,42,50,64,48)依次插入結(jié)點生成一棵AVL樹(高度平衡的二叉搜索樹)時，當插人到值為的結(jié)點時需要進行旋轉(zhuǎn)調(diào)整。.n(n>0)個頂點的無向圖最多有條邊。.設(shè)無向圖的鄰接表如下圖所示，則該圖的邊的數(shù)目是o

.判斷題(本大題共10小題，每小題1分，共10分).()鏈式存儲在插人和刪除時需要保持物理存儲空間的順序分配，不需要保持數(shù)據(jù)元素之間的邏輯順序。.()在用循環(huán)單鏈表表示的鏈式隊列中，可以不設(shè)隊頭指針，僅在鏈尾設(shè)置隊尾指針。.()通常遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行的效率也高。.()一個廣義表的表尾總是一個廣義表。.()對于一棵具有n個結(jié)點，其高度為h的二叉樹，進行任一種次序遍歷的時間復(fù)雜度為0(h)?.()當從一個最小堆中刪除一個元素時，需要把堆尾元素填補到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。.()存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。.()進行折半搜索的表必須是順序存儲的有序表。.()直接選擇排序是一種穩(wěn)定的排序方法。.()在用單鏈表表示的鏈式隊列中，隊頭在鏈表的鏈尾位置。四.問答題(本大題共5小題，每小題6分，共30分).由如圖所示的二叉樹，回答以下問題。a.其中序遍歷序列為。b.其先序遍歷序列為oC.其后序遍歷序列為O.已知圖G=(V,E),其中V={a,b,c,d,e,f,g},E={<a,b>,<a,g>,<b,g>,<c,b>,<d,c>,<d,C>,<e,d>,<f,a>, <f,e>,<g,c>,<g,d>,<g,fi>},請畫出圖G,并寫出其鄰接矩陣和鄰接表表示。.寫出利用直接選擇排序?qū)﹃P(guān)鍵字序列(40,24,80,39,43,18,20)進行從小到大排序的每一趟結(jié)果。.設(shè)A、B、C是不同的關(guān)鍵字且A>B>C,可組成6種不同的輸入順序。問其中哪幾種輸入順序所構(gòu)造的二叉排序樹的高度為3?5.在如圖所示的AOE5.在如圖所示的AOE網(wǎng)中，試回答如下問題：(1)計算出每個頂點所表示的事件的最早發(fā)生時間和最遲發(fā)生時間；(2)計算出每條邊所表示的活動的最早開始時間和最遲開始時間;2數(shù)據(jù)結(jié)構(gòu)模擬試卷(二)姓名： 學(xué)號：20103856班名： 21003一、單項選擇題(每小題2分，共30分).線性結(jié)構(gòu)的邏輯特征是除第一個節(jié)點和最后一個節(jié)點，其它節(jié)點都有OA.一個直接前趨和一個直接后繼B.多個直接前趨和一個直接后繼C.一個直接前趨和多個直接后繼D.多個直接前趨和多個直接后繼.算法必須具備輸入、輸出和。A.計算方法B.排序方法C.解決問題的有限運算步驟D.程式序設(shè)計方法.將遞歸過程轉(zhuǎn)化為非遞歸過程需用到。A.棧B.隊C.線性表D.鏈表.在順序表上做增、刪節(jié)點運算的平均時間復(fù)雜度是。0(1)O(n)O(log2n)O(n2).設(shè)二維數(shù)組A[?！璶-1]按行優(yōu)先順序存儲，則元素的地址為。LOC(A[0][0])+(i*m+j)LOC(A[0][0])+(i*n+j)LOC(A[0][01)+[(i-l)*n+j-l]LOC(A[0][0])4-[(i-l)*m+j-l].設(shè)目標串T:"aababbadbbaa"，模式P二“bba”，則該模式匹配的有效位移為。A.4 B.5C.7 D.10.把長度為m的單鏈表接在長度為n的單鏈表之后的算法的時間復(fù)雜度為。O(m)O(n)O(m+n)0(1).在一個單鏈表中，若P所指節(jié)點不是最后節(jié)點,在P之后插入S所指節(jié)點,則執(zhí)行oS->next=P->next;P->next=S;P->next=S->next;S->next=P;S->next=P;P->next=S;P->next=S;S->next=P;.設(shè)將整數(shù)123,4,5依次進棧，最后都出棧，出?？梢栽谌魏螘r刻(只要棧不空)進行，則出棧序列不可能是。23415541322314515432.循環(huán)隊列是空隊列的條件是oQ->rear==Q->front(Q->rear+1)%maxsize~Q->frontQ->rear=0Q->front==0.設(shè)有一廣義表E=(a,b,(c,d))?其長度為o2345.某二叉樹的前序遍歷序列為ABDEFC,中序遍歷序列為DBEFAC,則后序遍歷序列為?DFEBCADBECFABDAECFDBEFCA.下列哪項不是利用查找表中數(shù)據(jù)元素的關(guān)系進行查找的方法。A.有序表的查找B.二叉排序樹的查找C.平衡二叉樹D.散列查找.下述幾種排序方法中，要求內(nèi)存量最大的是。A.插入排序B.快速排序C.歸并排序D.選擇排序.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的倍。A.1/2B.1 C.2 D.4二、填空題(每空2分，共20分).數(shù)據(jù)結(jié)構(gòu)一般包括三個方面內(nèi)容：數(shù)據(jù)的,數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算。.在包含n個結(jié)點的順序表上做等概率插入運算，平均要移動個結(jié)點。.隊列的特性是..已知二叉樹中葉子數(shù)為30,僅有一個孩子的結(jié)點數(shù)為20,則總結(jié)點數(shù)為o.遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列(選填“先序”、“中序”或“后序.n個節(jié)點的連通圖至少有條邊。.在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮，應(yīng)最好選擇 排序。.帶有一個頭結(jié)點的單鏈表head為空的條件是(假設(shè)指針域的名稱為next).設(shè)一組初始關(guān)鍵字序列為(38,65,97,76,13,27,10),則第3趟簡單選擇排序后的結(jié)果為。.在拓撲排序中，拓撲序列的第一個頂點必定是的頂點。三、簡答題(每題6分，共36分).已知一棵樹邊的集合為｛<e,i>,<b,e>,<b,d>,<a,b>,<g,j>,<g,k>,<c,g>,<c,f>,<h,l>,<c,h>,<a,c>｝,畫出這棵樹，并回答下列問題：(1)哪個是根結(jié)點？哪些是葉子結(jié)點？哪些是結(jié)點g的祖先？樹的深度是多少？樹的度數(shù)是多少？27.以數(shù)據(jù)集｛2,4,5,8｝作為葉子結(jié)點的權(quán)值構(gòu)造Huffman樹，畫出該樹并計算出其帶權(quán)路徑長度。28.給定關(guān)鍵字集合(45,28,52,20,10,35,40,70,30,75,63,32),(1)從一棵空的二叉搜索樹開始，按表中元素的次序構(gòu)造一棵二叉搜索樹。(2)畫出從該二叉搜索樹中刪除關(guān)鍵碼28和52后的結(jié)果。

.試畫出下面帶權(quán)無向圖的一棵最小生成樹。.寫出利用希爾排序?qū)﹃P(guān)鍵字序列(40,24,80,39,43,18,20,10,90,70)進行從小到大排序的每一趟結(jié)果。(假設(shè)gap取值分別為5、3、1).設(shè)一散列表長為13,采用線性探查法解決沖突。散列函數(shù)h(key尸key%13。(1)畫出在空表中依次插入關(guān)鍵字25,20,36,15,41,52,29,72,67后的散列表。(2)該散列表在等概率查找成功和不成功的平均查找長度。四、綜合題(共14分).試對下圖所示的AOE網(wǎng)絡(luò)回答下列問題：這個工程最早可能在什么時間結(jié)束。(2分)求每個活動的最早開始時間e()和最遲開始時間/().(8分)確定哪些活動是關(guān)鍵活動。(4分)

數(shù)據(jù)結(jié)構(gòu)模擬試卷（一）參考答案—.1-5ABCDA6-10BCDAB11-15CDABC二.1二.1.非線性結(jié)構(gòu)2.f(n)3.O(n)4.105.棧頂6.可使用性7.n-l 8.(15,02,21,24,26,57,43,66,80,48,73)9.稀疏10.89 e,f))12.3 13.50 14.n(n-l)/2 15. 5=.XVXVXVXVXX四.1.dgbaechifabdgcefhigdbeihfca2.鄰接矩陣：abcdefg0100001 a0000001 b0100000 c0010010 d0001000 e1000100 f001101° gIy

3.18,24,80,39,43,40,2018,20,80,39,43,40,2418,20,24,39,43,40,8018,20,24,39,43,40,803.18,24,80,39,43,40,2018,20,80,39,43,40,2418,20,24,39,43,40,8018,20,24,39,43,40,8018,20,24,39,40,43,8018,20,24,39,40,43,804.4種。評分標準：次序不限，寫對一種得1分，4種全寫對得6分。若在4種正確答案之外,又多寫一種則只能得4分，若6種排列順序全寫上則0分。事件的最早發(fā)生時間和最遲發(fā)生時間:活動的最早開始時間和最遲開始時間:abacadbecedfegehthgkhk權(quán)64511287424e0006457771514102366887101614網(wǎng)絡(luò)中的關(guān)鍵活動：ab,be,eh,hk關(guān)鍵路徑：aTbfefhTk數(shù)據(jù)結(jié)構(gòu)模擬試卷（二）參考答案1~5ACABB6~101~5ACABB6~10ABABA11-15BADCB邏輯結(jié)構(gòu) 邏輯結(jié)構(gòu) n/2 先進先出 79中序快速排序head->next==NULL10,13,27,76,65,97,38 入度為零n-1參考答案：1）參考答案：1）根結(jié)點是：a4）樹的深度：45）樹的度數(shù)：3參考答案：2）葉子結(jié)點是：difjkl 3）g的祖先：ac帶權(quán)路徑長度：WPL=(2+4)*3+5*2+8=36帶權(quán)路徑長度：WPL=(2+4)*3+5*2+8=3628.參考答案:（1）（評分標準：每個圖3分）參考答案：參考答案：Gap=5時 18,20, 10,39,43,40, 24,80, 90,70Gap=3時 18,20, 10,24,43,40, 39,80, 90,70Gap=1時 10,18, 20,24,39,40, 43,70, 80,90參考答案：(1)散列表：(2分)0123456789101112521541296720723625(2)ASLsucc=(5*1+3*2+1*4)/9=5/3(2分)ASLnsucc=Q+1+5+4+3+2+1+3+2+1+2+1+3)/13=30/13 (2分)

四.32.按拓撲有序的順序計算各個頂點的最早可能開始時間Vr和最遲允許開始時間VI.然后再計算各個活動的最早可能開始時間。和最遲允許開始時間/，根據(jù)是否等于。來確定關(guān)鍵活動，從而確定關(guān)鍵路徑.1?203?1。5?6。Ve01915293843VI01915373843VI,2><1,3><3,2><2,4><2,5><3,5><4,6><5,6>r00151919152938/】70152719273738l-e1700801280此工程最早完成時間為43.關(guān)鍵路徑為VI,3X3,2X2,5X5,6>三、習(xí)題練習(xí)習(xí)題1一'單項選擇題.數(shù)據(jù)結(jié)構(gòu)是指（）。A.數(shù)據(jù)元素的組織形式 B.數(shù)據(jù)類型C.數(shù)據(jù)存儲結(jié)構(gòu) D.數(shù)據(jù)定義.數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址不相同的，稱之為（）.A.存儲結(jié)構(gòu) B.邏輯結(jié)構(gòu)C.鏈式存儲結(jié)構(gòu) D.順序存儲結(jié)構(gòu).樹形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（）oA.一對一關(guān)系 B.多對多關(guān)系C.多對一關(guān)系 D.一對多關(guān)系.設(shè)語句x++的時間是單位時間，則以下語句的時間復(fù)雜度為（）.for（i=l;i<=n;i++）for（j=i;j<=n;j++）x++;A.0(1)B.O(n2)C.O(n)A.0(1)B.O(n2)C.O(n)D.O(n3).算法分析的目的是(1),算法分析的兩個主要方面是(2)oB.研究算法中的輸入和輸出關(guān)系D.B.研究算法中的輸入和輸出關(guān)系D.分析算法的易懂性和文檔性B.正確性和簡明性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性輸出和(2)等五個特性。B.排序方法D.調(diào)度方法B.可行性，確定性和有窮性D.易讀性，穩(wěn)定性和安全性C.分析算法的效率以求改進A.空間復(fù)雜度和時間復(fù)雜度C.可讀性和文檔性6.計算機算法指的是(1),它具備輸入,A.計算方法C.解決問題的有限運算序列A.可行性，可移植性和可擴充性C.確定性，有窮性和穩(wěn)定性.數(shù)據(jù)在計算機內(nèi)有鏈式和順序兩種存儲方式，在存儲空間使用的靈活性上，鏈式存儲比順序存儲要(),A.低 B.高 C.相同 D.不好說.數(shù)據(jù)結(jié)構(gòu)作為一門獨立的課程出現(xiàn)是在()年。A.1946 B.1953 C.1964 D.1968.數(shù)據(jù)結(jié)構(gòu)只是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，這種觀點()。A.正確 B.錯誤C.前半句對，后半句錯 D.前半句錯，后半句對.計算機內(nèi)部數(shù)據(jù)處理的基本單位是()oA.數(shù)據(jù) B.數(shù)據(jù)元素 C.數(shù)據(jù)項D.數(shù)據(jù)庫二'填空題.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，分別是和?.數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是、、和O.線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是的，非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是的。.一個算法的效率可分為效率和效率。.在樹型結(jié)構(gòu)中，樹根結(jié)點沒有結(jié)點，其余每個結(jié)點的有且只有個前趨驅(qū)結(jié)點；葉子結(jié)點沒有結(jié)點；其余每個結(jié)點的后續(xù)結(jié)點可以o.在圖型結(jié)構(gòu)中，每個結(jié)點的前趨結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以..線性結(jié)構(gòu)中元素之間存在 關(guān)系；樹型結(jié)構(gòu)中元素之間存在關(guān)系：圖型結(jié)構(gòu)中元素之間存在 關(guān)系。.下面程序段的時間復(fù)雜度是?for(i=0;i<n;i++)for(j=0;j<n;j++)A[i]U]=0：.下面程序段的時間復(fù)雜度是oi=s=0;while(s<n)(i++；s+=i;}.下面程序段的時間復(fù)雜度是Os=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=B[i|[j|;sum=s;H.下面程序段的時間復(fù)雜度是oi=l；whi1e(i<=n)i=i*3;.衡量算法正確性的標準通常是。.算法時間復(fù)雜度的分析通常有兩種方法，即和的方法，通常我們對算法求時間復(fù)雜度時，采用后一種方法。三、求下列程序段的時間復(fù)雜度。x=0;for(i=l;i<n;i++)for(j=i+l;j<=n;j++)x++;x=0;for(i=l;i<n;i++)for(j=l;j<=n-i;j++)x++;inti,jtk;for(i=0;i<n;i++)for(j=0;j<=n：j++){c[i]U]=O;fbr(k=O;k<n;k++)c[i]U]=a[i][k]*b[k]U])i=n-1;while((i>=O)&&A|i];=k))j-；return⑴；fact(n){if(n<=1)return(1);elsereturn(n*fact(n-l));習(xí)題1參考答案一、單項選擇題1.A2.C3.D4.B5.C、A6.C、B7,B8.D9.B10.B二、填空題.線性結(jié)構(gòu)，非線性結(jié)構(gòu).集合，線性，樹，圖.一■對一，一對多或多對多.時間，空間.前趨，一，后繼，多.有多個.一對一，一對多，多對多8.0(〃2)9.O(Vn)10.O(n2).O(log,n).程序?qū)τ诰脑O(shè)計的典型合法數(shù)據(jù)輸入能得出符合要求的結(jié)果。.事后統(tǒng)計，事前估計三、算法設(shè)計題l.O(n2) 2.O(n2) 3.0(n3) 4.0(n) 5.0(n)習(xí)題2一、單項選擇題.線性表是A_oA.一個有限序列，可以為空B.一個有限序列，不可以為空C.一個無限序列，可以為空D.一個無限序列，不可以為空.在一個長度為n的順序表中刪除第i個元素(0<=i<=n)時，需向前移動A個元素。A.n-i B.n-i+1 C.n-i-1 D.i.線性表采用鏈式存儲時，其地址D。A.必須是連續(xù)的 B.一定是不連續(xù)的C.部分地址必須是連續(xù)的 D.連續(xù)與否均可以.從一個具有n個結(jié)點的單鏈表中查找其值等于x的結(jié)點時，在查找成功的情況下，需平均比較一C一個元素結(jié)點。A.n/2B.n C.(n+1)/2D.(n-1)/2.在雙向循環(huán)鏈表中，在p所指的結(jié)點之后插入s指針所指的結(jié)點，其操作是_D_。p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;.設(shè)單鏈表中指針p指向結(jié)點m,若要刪除m之后的結(jié)點(若存在)，則需修改指針的操作為__人^。A.p->next=p->next->next; B.p=p->next;C.p=p->next->next; D.p->next=p;.在一個長度為n的順序表中向第i個元素(0<i<n+l)之前插入一個新元素時，需向后移動—B一個元素。A.n-i B.n-i+1 C.n-i-1 D.i.在一個單鏈表中，已知q結(jié)點是p結(jié)點的前趨結(jié)點，若在q和p之間插入s結(jié)點，則須執(zhí)行—Bs->next=p->next;p->next=sq->next=s;s->next=pp->next=s->next;s->next=pp->next=s;s->next=q.以下關(guān)于線性表的說法不正確的是_CoA.線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B.線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的。C.線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼。D.存在這樣的線性表：表中各結(jié)點都沒有宜接前趨和直接后繼。

.線性表的順序存儲結(jié)構(gòu)是一種一A―的存儲結(jié)構(gòu)。A.隨機存取B.順序存取C.索引存取D.散列存取.在順序表中，只要知道一D一,就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。A.基地址 B.結(jié)點大小C.向量大小 D.基地址和結(jié)點大小.在等概率情況下，順序表的插入操作要移動一B—結(jié)點。A.全部 B. 一半C.三分之一 D.四分之一.在一C—運算中，使用順序表比鏈表好。A.插入 B.刪除C.根據(jù)序號查找 D.根據(jù)元素值查找.在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并保持該表有序的時間復(fù)雜度B.O(n)A.0B.O(n)C.O(n2)C.O(n2)15.設(shè)有一個棧,元素的進棧次序為A,B,C,D,E,下列是不可能的出棧序列A.A,B,C,D,EE,A,B,C,DA.A,B,C,D,EE,A,B,C,DB. B, C, D, E, AE, D, C, B, A.在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為—C一.D.top++A.top不變B.top=0C.top一D.top++.向一個棧頂指針為hs的鏈棧中插入一個s結(jié)點時，應(yīng)執(zhí)行—B.hs->next=s;s->next=hs;hs=s;s->next=hs->next;hs->next=s;s->next=hs;hs=hs->next;.在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為一D。rear%n==rear%n==front(front+1)%n==rearC.rear%n-1==frontD.(rear+1)%n==front.在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊空的條件為_C0A.rear%n==frontB.front+1=rearC.rear==front D.(rear+1)%n=front.在一個鏈隊列中，假定from和rear分別為隊首和隊尾指針，則刪除一個結(jié)點的操作為A_oA.front二front->next B.rear=rear->nextC.rear=front->next D.front=rear->next二、填空題.線性表是一種典型的結(jié)構(gòu)。.在一個長度為n的順序表的第i個元素之前插入一個元素，需要后移一個元素。.順序表中邏輯上相鄰的元素的物理位置 。.要從一個順序表刪除一個元素時，被刪除元素之后的所有元素均需一個位置，移動過程是從向依次移動每一個元素。.在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過決定的。.在雙向鏈表中，每個結(jié)點含有兩個指針域，一個指向結(jié)點，另一個指向 結(jié)點。.當對一個線性表經(jīng)常進行存取操作，而很少進行插入和刪除操作時，則采用存儲結(jié)構(gòu)為宜。相反，當經(jīng)常進行的是插入和刪除操作時，則采用存儲結(jié)構(gòu)為宜。.順序表中邏輯上相鄰的元素，物理位置 相鄰，單鏈表中邏輯上相鄰的元素，物理位置相鄰。.線性表、棧和隊列都是結(jié)構(gòu)，可以在線性表的 位置插入和刪除元素：對于棧只能在 位置插入和刪除元素；對于隊列只能在 位置插入元素和在 位置刪除元素。.根據(jù)線性表的鏈式存儲結(jié)構(gòu)中每個結(jié)點所含指針的個數(shù)，鏈表可分為和;而根據(jù)指針的聯(lián)接方式，鏈表又可分為和。.在單鏈表中設(shè)置頭結(jié)點的作用是?.對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點p后插入一個新結(jié)點的時間復(fù)雜度為,在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為..對于一個棧作進棧運算時，應(yīng)先判別棧是否為,作退棧運算時，應(yīng)先判別棧是否為,當棧中元素為m時，作進棧運算時發(fā)生上溢，則說明棧的可用最大容量為。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當 時才產(chǎn)生上溢。.設(shè)有一空棧，現(xiàn)有輸入序列1,2,3,4,5,經(jīng)過push,push,pop,push,pop,push,push后，輸出序列是..無論對于順序存儲還是鏈式存儲的棧和隊列來說，進行插入或刪除運算的時間復(fù)雜度均相同為?三,簡答題.描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，表頭結(jié)點。.線性表的兩種存儲結(jié)構(gòu)各有哪些優(yōu)缺點？.對于線性表的兩種存儲結(jié)構(gòu)，如果有n個線性表同時并存，而且在處理過程中各表的長度會動態(tài)發(fā)生變化,線性表的總數(shù)也會自動改變，在此情況下，應(yīng)選用哪一種存儲結(jié)構(gòu)？為什么？.對于線性表的兩種存儲結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲結(jié)構(gòu)？試說明理由。.在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么？.假定有四個元素A,B,C,D依次進棧，進棧過程中允許出棧，試寫出所有可能的出棧序列。.什么是隊列的上溢現(xiàn)象？一般有幾種解決方法，試簡述之。.下述算法的功能是什么？LinkList*Demo(LinkList*L){〃L是無頭結(jié)點的單鏈表LinkList*q,*p;if(L&&L->next){q=L;L=L->next;p=L;while(p->next)p=p->next;p->next=q;q->next=NULL;)return(L);)四、算法設(shè)計題.設(shè)計在無頭結(jié)點的單鏈表中刪除第i個結(jié)點的算法。.在單鏈表上實現(xiàn)線性表的求表長ListLength(L)運算。.設(shè)計將帶表頭的鏈表逆置算法。.假設(shè)有一個帶表頭結(jié)點的鏈表，表頭指針為head,每個結(jié)點含三個域：data,next和prior。其中data為整型數(shù)域，next和prior均為指針域?，F(xiàn)在所有結(jié)點已經(jīng)由next域連接起來，試編一個算法，利用prior域(此域初值為NULL)把所有結(jié)點按照其值從小到大的順序鏈接起來。.已知線性表的元素按遞增順序排列，并以帶頭結(jié)點的單鏈表作存儲結(jié)構(gòu)。試編寫一個刪除表中所有值大于min且小于max的元素(若表中存在這樣的元素)的算法。.已知線性表的元素是無序的，且以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)。設(shè)計一個刪除表中所有值小于max但大于min的元素的算法。.假定用一個單循環(huán)鏈表來表示隊列(也稱為循環(huán)隊列)，該隊列只設(shè)一個隊尾指針，不設(shè)隊首指針，試編寫下列各種運算的算法：(1)向循環(huán)鏈隊列插入一個元素值為x的結(jié)點；(2)從循環(huán)鏈隊列中刪除一個結(jié)點。.設(shè)順序表L是一個遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。習(xí)題2參考答案一、單項選擇題1.A 2.A3.D4. C5.D 6.A 7.B8.B9.C10. A11.D12.B13.C 14.B15.C16.C17.B18. D19.C20.A二、填空題.線性.n-i+1.相鄰.前移，前，后.物理存儲位置，鏈域的指針值.前趨，后繼.順序，鏈接.一定，不一定.線性，任何，棧頂，隊尾，隊頭.單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表.使空表和非空表統(tǒng)一；算法處理一致.0(1),0(n).棧滿，?？眨琺,棧底，兩個棧的棧頂在棧空間的某一位置相遇.2、3.0(1)三、簡答題.頭指針是指向鏈表中第一個結(jié)點(即表頭結(jié)點)的指針；在表頭結(jié)點之前附設(shè)的結(jié)點稱為頭結(jié)點；表頭結(jié)點為鏈表中存儲線性表中第一個數(shù)據(jù)元素的結(jié)點。若鏈表中附設(shè)頭結(jié)點，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。.線性表具有兩種存儲結(jié)構(gòu)即順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)。線性表的順序存儲結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時將會引起元素的大量移動,因而降低效率：而在鏈接存儲結(jié)構(gòu)中內(nèi)存采用動態(tài)分配，利用率高，但需增設(shè)指示結(jié)點之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結(jié)點的插入、刪除操作較簡單。.應(yīng)選用鏈接存儲結(jié)構(gòu)，因為鏈式存儲結(jié)構(gòu)是用一組任意的存儲單元依次存儲線性表中的各元素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲結(jié)構(gòu)對于元素的刪除或插入運算是不需要移動元素的，只需修改指針即可，所以很容易實現(xiàn)表的容量的擴充。.應(yīng)選用順序存儲結(jié)構(gòu)，因為每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個數(shù)據(jù)元素都可隨機存取，因此，線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)，而鏈表則是一種順序存取的存儲結(jié)構(gòu)。.設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設(shè)一帶頭結(jié)點的單循環(huán)鏈表，其尾指針為rear,則開始結(jié)點和終端結(jié)點的位置分別是rear->next->next和rear,查找時間都是0(l)o若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為0(n)。.共有14種可能的出棧序列，即為：ABCD,ABDC,ACBD,ACDB,BACD,ADCB,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA.在隊列的順序存儲結(jié)構(gòu)中，設(shè)隊頭指針為front,隊尾指針為rear,隊列的容量(即存儲的空間大小)為maxnum。當有元素要加入隊列(即入隊)時，若rear=maxnum,則會發(fā)生隊列的上溢現(xiàn)象，此時就不能將該元素加入隊列。對于隊列，還有一種“假溢出”現(xiàn)象,隊列中尚余有足夠的空間，但元素卻不能入隊，一般是由于隊列的存儲結(jié)構(gòu)或操作方式的選擇不當所致，可以用循環(huán)隊列解決。一般地，要解決隊列的上溢現(xiàn)象可有以下幾種方法：(1)可建立一個足夠大的存儲空間以避免溢出，但這樣做往往會造成空間使用率低，浪費存儲空間。(2)要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決：第一種：采用移動元素的方法。每當有一個新元素入隊，就將隊列中已有的元素向隊頭移動一個位置，假定空余空間足夠。第二種：每當刪去一個隊頭元素，則可依次移動隊列中的元素總是使front指針指向隊列中的第一個位置。第三種：采用循環(huán)隊列方式。將隊頭、隊尾看作是一個首尾相接的循環(huán)隊列，即用循環(huán)數(shù)組實現(xiàn)，此時隊首仍在隊尾之前，作插入和刪除運算時仍遵循“先進先出”的原則。.該算法的功能是：將開始結(jié)點摘下鏈接到終端結(jié)點之后成為新的終端結(jié)點，而原來的第二個結(jié)點成為新的開始結(jié)點，返回新鏈表的頭指針。四、算法設(shè)計題1.算法思想為：(1)應(yīng)判斷刪除位置的合法性，當i<0或i>n-l時，不允許進行刪除操作；(2)當i=0時，刪除第一個結(jié)點：(3)當0<i<n時，允許進行刪除操作，但在查找被刪除結(jié)點時，須用指針記住該結(jié)點的前趨結(jié)點。算法描述如下：delete(LinkList*q,inti){〃在無頭結(jié)點的單鏈表中刪除第i個結(jié)點LinkList*p,*s;intj;if(i<0)printf("Canrtdelete");elseif(i==0){s=q;q=q->next;frce(s);1else{j=0；s=q;while((j<i)&&(s!=NULL)){P=s；s=s->next;j++；Jif(s==NULL)printf("Cant'tdelete");p->next=s->next;free(s);2.由于在單鏈表中只給出一個頭指針，所以只能用遍歷的方法來數(shù)單鏈表中的結(jié)點個數(shù)了。算法描述如下：intListLength(LinkList*L)1〃求帶頭結(jié)點的單鏈表的表長intIen=0;ListList*p;p=L;while(p->next!=NULL){p=p->next;len++;return(len);.設(shè)單循環(huán)鏈表的頭指針為head,類型為LinkList?逆置時需將每一個結(jié)點的指針域作以修改，使其原前趨結(jié)點成為后繼。如要更改q結(jié)點的指針域時，設(shè)s指向其原前趨結(jié)點，p指向其原后繼結(jié)點，則只需進行q->next=s;操作即可，算法描述如下：voidinvert(LinkList*head)(〃逆置head指針所指向的單循環(huán)鏈表linklist*p,*q,*s;q=head;p=head->next;while(p!=head)〃當表不為空時，逐個結(jié)點逆置{s=q;q=p；p=p->next;q->next=s;)p->next=q;).定義類型LinkList如下：typedefstructnode{intdata;structnode*next,*prior;(LinkList;此題可采用插入排序的方法，設(shè)p指向待插入的結(jié)點，用q搜索已由prior域鏈接的有序表找到合適位置將p結(jié)點鏈入。算法描述如下：insert(LinkList*head){LinkList*p,*s,*q;p=head->next;//p指向待插入的結(jié)點，初始時指向第一個結(jié)點while(p!=NULL){s=head;〃s指向q結(jié)點的前趨結(jié)點q=hcad->prior;〃q指向由prior域構(gòu)成的鏈表中待比較的結(jié)點while((q!=NULL)&&(p->data>q->data))〃查找插入結(jié)點p的合適的插入位置{s=q;q=q->prior;)s->prior=p;p->prior=q;〃結(jié)點p插入到結(jié)點s和結(jié)點q之間p=p->next;}1.算法描述如下：de!ete(LinkList*head,intmax,intmin){linklist*p,*q;if(head!=NULL)(q=head;p=head->next;while((p!=NULL)&&(p->data<=min)){q=p；p=p->next;)while((p!=NULL)&&(p->data<max))p=p->next;q->next=p;)).算法描述如下：delele(LinkList*head,intmax,intmin)(LinkList*p,*q;q=head;p=head->next;while(p!=NULL)if((p->data<=min)||(p->data>=max)){q=p；p=p->next;)else{q->next=p->next;free(p);p=q->next;}).本題是對一個循環(huán)鏈隊列做插入和刪除運算，假設(shè)不需要保留被刪結(jié)點的值和不需要回收結(jié)點，算法描述如下：(1)插入(即入隊)算法：insert(LinkList*rear,elemtypex)(〃設(shè)循環(huán)鏈隊列的隊尾指針為rear,x為待插入的元素LinkList*p;p=(LinkList*)malloc(sizeof(LinkList));if(rear==NULL)//如為空隊，建立循環(huán)鏈隊列的第一個結(jié)點{rear=p;rear->next=p; 〃鏈接成循環(huán)鏈表)else〃否則在隊尾插入p結(jié)點{p->next=rear->next;rear->next=p;rear=p;(2)刪除(即出隊)算法:delete(LinkList*rear){//設(shè)循環(huán)鏈隊列的隊尾指針為rearif(rear==NULL)〃空隊printf(Munderflow\n");if(rear->next==rear)〃隊中只有一個結(jié)點rear=NULL;elserear->next=rear->next->next;//rear->next指向的結(jié)點為循環(huán)鏈隊列的隊頭結(jié)點}.只要從終端結(jié)點開始往前找到第一個比x大(或相等)的結(jié)點數(shù)據(jù)，在這個位置插入就可以了。算法描述如下：iniInsertDecreaseList(SqList*L,elemtypex)1inti;if((*L).len>=maxlen){printfToverflow")；retum(O);)for(i=(*L).len;i>0&&(*L).elem[i-1]<x;i-)(*L).elem[i]=(*L).elem[i-1]; //比較并移動元素(*L).elem|i]=x;(*L).len++;relum(1);習(xí)題3一、單項選擇題.空串與空格字符組成的串的區(qū)別在于()?A.沒有區(qū)別 B.兩串的長度不相等C.兩串的長度相等 D.兩串包含的字符不相同.一個子串在包含它的主串中的位置是指()oA.子串的最后那個字符在主串中的位置B.子串的最后那個字符在主串中首次出現(xiàn)的位置C.子串的第一個字符在主串中的位置D.子串的第一個字符在主串中首次出現(xiàn)的位置.下面的說法中，只有()是正確的。A.字符串的長度是指串中包含的字母的個數(shù)B.字符串的長度是指串中包含的不同字符的個數(shù)C.若T包含在S中，則T一定是S的一個子串D.一個字符串不能說是其自身的一個子串.兩個字符串相等的條件是().A.兩串的長度相等B.兩串包含的字符相同C.兩串的長度相等，并且兩串包含的字符相同D.兩串的長度相等，并且對應(yīng)位置上的字符相同.若SUBSTR(S,i,k)表示求S中從第i個字符開始的連續(xù)k個字符組成的子串的操作，則對于S="Beijing&Nanjing"，SUBSTR(S,4,5)=().A.”ijing" B."jing&”C."ingNa” D,“ing&N”.若INDEX(S,T)表示求T在S中的位置的操作，則對于S="Beijing&Nanjing”，T="jing"，INDEX(S,T)=()?A.2 B.3 C.4 D.5.若REPLACE(S,S