2022年數(shù)據(jù)結(jié)構(gòu)與算法期中考試卷(含答案)

1、學習必備歡迎下載考 試 時 間號:年 月日位下午座玉林師范學院期中課程考試試卷（ 2021 2021 學年度第一學期）a 、規(guī)律相鄰、物理不肯定相鄰b、不能隨機存取c 、插入與刪除需移動大量元素d、表容量易于擴充5、關(guān)于次序表的說法，請選出不正確的一項d ；:線名 姓 題答:號 學 要不:別 12345678cbccdaca9101112131415cdbbbad班 內(nèi)訂命題老師：劉恒命題老師所在系：數(shù)計系課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法考試專業(yè)：信計考試年級： 09 級題號一二三四五總分應(yīng)得分3010104010滿分： 100實得分評分：評卷人簽名一、單項挑選題（每題 2 分，共 30 分，把正確答

2、案填入表格中）a、規(guī)律相鄰、物理相鄰b、可實現(xiàn)隨機存取c、儲備空間使用緊湊d、表容量易于擴充6、設(shè) n為正整數(shù)，試確定以下程序段中前置以記號語句的頻度為 a ；x=91;y=100;whiley>0 ifx>100x-=10;y-;else x+;a、1100b、 9100c、110d、 9107、在次序表中刪除一個元素，平均需要移動 c 元素，設(shè)表長為 n；a、n/2-1b、n/2+1c、n/2d、n+1/28、對單鏈表執(zhí)行以下程序段，請選出正確的一項 a ； 1、在數(shù)據(jù)結(jié)構(gòu)中，從規(guī)律上可以把數(shù)據(jù)結(jié)構(gòu)分成c ；線 a、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)b、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)ht=p;2573p

3、q84 sr:業(yè) 封專 密:級 年 裝:院 系 c、線性結(jié)構(gòu)和非線性結(jié)構(gòu)d、規(guī)律結(jié)構(gòu)和儲備結(jié)構(gòu)2、結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個對多個的關(guān)系，稱為b 結(jié)構(gòu)；a、線性b、樹形c、圖狀d、網(wǎng)狀3、以下關(guān)于線性表的說法不正確選項 c ；a、線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型；b、線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的；c、線性表中的每個結(jié)點 都有且只有一個直接前驅(qū)和直接后繼；d、存在這樣的線性表：表中各結(jié)點都沒有直接前驅(qū)和直接后繼； 4、關(guān)于單鏈表的說法，請選出不正確的一項 c ；while t->next.=null t >data=t >data*2;t=t >

4、;next; a、r->data=4b、r->data=8c、h->data=4d、q->data=79、如一個棧的輸入序列是 1，2，3， n，輸出序列的第一個元素是 n, 就第 k 個輸出元素是 c ；a、kb、n-k-1cn-k+1d 、不確定10、判定一個次序棧 s 最多有 n 個元素 為滿的條件是 d ；a、s.top.=0b、s.top= =0c、s.top.=nd、s.top= =n11、一個隊列的出隊序列是 1 2 3 4，就隊列的入隊序列是 b ；a、4 3 2 1b、1 2 3 4c、1 4 3 2d、3 2 4 112、選出合適的答案， “隊列”結(jié)

5、構(gòu)實現(xiàn)的是 b ；(1) 先進/ 后出 2后進/ 先出 3先來/ 先服務(wù)4先進/ 先出 5后進/ 后出a 、1 、2b、3 、4 、5c、1 、4 、5 d、113、串是一種特別的線性表，其特別性表達在 b ；a、可以次序儲備b、數(shù)據(jù)元素是一個字符c、可以鏈接儲備d、數(shù)據(jù)元素可以是多個字符14、設(shè)串 s1=abcdefg， s2= pqrst ，函數(shù) conx,y返回 x 和 y 串的連接串，subss,i,j返回串 s 的從序號 i 的字符開頭的 j 個字符組成的字串， lens返回串 s 的長度，就： consubss1,3,lens2,subss1,lens2,3的結(jié)果串是 a ；a、c

6、defgefgb、cdefefg c、bcdefefgd、cdefgef15、以下說法哪個是不正確的： d ；a、空格串空串b、數(shù)據(jù)元素是由如干數(shù)據(jù)項組成c、串也稱字符串d、棧的表頭端稱為棧頂二、填空題（每題 1 分，共 10 分）1、數(shù)據(jù)結(jié)構(gòu) 是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合；2、一般情形下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n 的某個函數(shù)fn，算法的時間量度記作 tn=ofn；3、線性表中每個結(jié)點包含兩個指針域，稱此線性表為雙向鏈表 ；4、 一個次序表的開頭地址是 1000，每個元素的長度是 8，就第 7 個元素的儲備地址是 1048；5、 執(zhí)行 p=jd*malloc

7、sizeofjd的作用是 生成一個 jd型結(jié)點，并用指針變量 p 指向（答出前半句即得分） ；6、所謂次序表 sqlist是線性表的 次序儲備表示 ；7、棧是限定僅在表尾進行插入或就刪除操作的線性表；8、人們?nèi)粘＿\算用到的表達式，都被稱為中綴表達式 ，這是由于這種算術(shù)表達式的運算符被置于兩個操作數(shù)中間；9、隊列的插入操作是在 隊尾進行；10、設(shè)每個字符占 1 個字節(jié)，如結(jié)點大小為 4 的鏈串的儲備密度為 50%，就其每個指針占 4 個字節(jié)；三、名詞說明（每題 2 分，共 10 分） 1、抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型簡稱 adt，是指一個數(shù)學模型以及定義在該模型上的一組操作；可用三元組表示（ d,s

8、,p），其中， d是數(shù)據(jù)對象， s是 d上的關(guān)系集， p是對 d的基本操作集；（1 分）如： adt 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象： <數(shù)據(jù)對象的定義 > 數(shù)據(jù)關(guān)系： <數(shù)據(jù)關(guān)系的定義 > 基本操作： <基本操作的定義 >adt抽象數(shù)據(jù)類型名 （ 1 分）2、物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在運算機中的表示（又稱映像或儲備結(jié)構(gòu)） ；（ 1 分）數(shù)據(jù)元素之間的關(guān)系在運算機中有兩種不同的表示方法： 次序映像和非次序映像， 并由此得到兩種不同的儲備結(jié)構(gòu)：次序儲備結(jié)構(gòu)和鏈式儲備結(jié)構(gòu)； （1 分）3、語句的頻度該語句重復(fù)執(zhí)行的次數(shù)； （2 分）4、循環(huán)鏈表是線性表的一種鏈式儲備結(jié)構(gòu)； （

9、 1 分）其特點是表中最終一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)； （1 分）5、算法的可行性一個算法是能行的， 即算法中描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的； （2 分）注：可視答案的合理程度酌情給分；四、解答題（每題 5 分，共 40 分）1、分別寫出循環(huán)隊列中判定隊空和隊滿的條件（設(shè)循環(huán)隊列的最大儲備空間是 m ）；隊空： front= =rear（2.5 分） 隊滿： rear+1%m= =front（2.5 分）5、已知以下字符串 : a= this ,f= a sample,c= good ,d=ne ,b= ,2、已知 l 是帶表頭結(jié)點的非空單鏈表，

10、且p 結(jié)點既不是第一個元素結(jié)點， 也不是最終一個元素結(jié)點，請寫出刪除p 結(jié)點的直接后繼結(jié)點的語句序列：s=concata,concatsubstringf,2,7,concatb,substringa,3,2, t=replacef, substringf,3,6,c,a goodu= concatsubstringc,3,1,done,g= is,v= concats, concatb, concatt, concatb,u,la1aipanthis sample is a good one試問： s,v,strlengths,indexv,g,indexu,g各是什么？s: this sa

11、mple is（1 分）q=p->next;（ 2 分）p->next=p->next->next;（ 2 分）freeq;（ 1 分）3、簡述以下算法的功能： status algostack s,int e stack t; int d; initstackt; while.stackemptys pops,difd.=e pusht,d; while.stackemptyt popt,d;pushs,d;v: this sample is a good one（1 分）strlengths=14（1 分）indexv,g=3（1 分）indexu,g=0（1 分）

12、6、下面算法實現(xiàn)串的基本操作 strinsert&s,pos,ts、t 用定長次序儲備表示 ，請?zhí)羁胀瓿?；status strinsertsstring &s, int pos, sstring t ifpos<1|pos>s0+1|s0+t0>maxstrlen return error; spos+t0s0+t0=sposs0;spos pos+t0-1=t1 t0; （ 2.5 分）s0=s0+t0; （2.5 分）return ok;借助棧 t 把棧 s 中與 e 相等的元素刪掉（ 5 分） p22 3.424、寫出以下程序段的輸出結(jié)果（隊列中的元素類

13、型qelemtype為 char ）；void main queue q; init queue q; char x=e,y= c ;enqueueq, h; enqueueq, r ; enqueueq,y; dequeueq,x; enqueueq,x;dequeueq,x; enqueueq,a;while.queueemptyq dequeueq,y;printfy; printfx;char（5 分） p23 3.127、設(shè)有 3 個元素 a，b，c 依次進棧，給出它們?nèi)靠赡艿某鰲４涡颍籥 b ca c b c b a b c a b a c8、以下算法的功能是 : 已知線性表 l

14、a 和 lb 中的元素按值非遞減排列；歸并 la 和 lb 得到新的線性表 lc ，lc 的元素也按值非遞減排列；填空完成該算法；void mergelistlist la, list lb, list &lc initlistlc;i = j = 1;k = 0;la_len = listlengthla; lb_len = listlengthlb;while i<=la.len&&j<=lb.len2.5 分 getelemla, i, ai; getelemlb, j, bj; if ai <= bj listinsertlc, +k, ai; +i; else listinsertlc, +k, bj; +j; while i <= la_len getelemla, i+, ai; listinsertlc, +k, ai;while j <= lb_len getelemlb, j+, bj;listinsertlc,+k,bj;課本 p21 算法 2.2五、算法設(shè)計題