數(shù)據(jù)結構試題

PAGE1一、填空題（每空1分，共15分）1.【李春葆】向量、棧和隊列都是線性結構，可以在向量的任何位置插入和刪除元素；對于棧只能在棧頂插入和刪除元素；對于隊列只能在隊尾插入和隊首刪除元素。2.棧是一種特殊的線性表，允許插入和刪除運算的一端稱為棧頂。不允許插入和刪除運算的一端稱為棧底。3.隊列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。4.在一個循環(huán)隊列中，隊首指針指向隊首元素的前一個位置。5.在具有n個單元的循環(huán)隊列中，隊滿時共有n-1個元素。6.向棧中壓入元素的操作是先移動棧頂指針，后存入元素。7.從循環(huán)隊列中刪除一個元素時，其操作是先移動隊首指針，后取出元素。8.〖00年統(tǒng)考題〗帶表頭結點的空循環(huán)雙向鏈表的長度等于0。L=head頭結點RL=head頭結點R=headhead二、判斷正誤（判斷下列概念的正確性，并作出簡要的說明。）（每小題1分，共10分）（×）1.線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。錯，線性表是邏輯結構概念，可以順序存儲或鏈式存儲，與元素數(shù)據(jù)類型無關。（×）2.在表結構中最常用的是線性表，棧和隊列不太常用。錯，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊列。（√）3.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結構。（√）4.對于不同的使用者，一個表結構既可以是棧，也可以是隊列，也可以是線性表。正確，都是線性邏輯結構，棧和隊列其實是特殊的線性表，對運算的定義略有不同（×）5.棧和鏈表是兩種不同的數(shù)據(jù)結構。錯，棧是邏輯結構的概念，是特殊殊線性表，而鏈表是存儲結構概念，二者不是同類項。（×）6.棧和隊列是一種非線性數(shù)據(jù)結構。錯，他們都是線性邏輯結構，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（√）7.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。（√）8.兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內(nèi)存空間的兩端。（×）9.隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。錯，后半句不對。（×）10.一個棧的輸入序列是12345，則棧的輸出序列不可能是12345。錯，有可能。三、單項選擇題（每小題1分，共20分）（B）1.〖00年元月統(tǒng)考題〗棧中元素的進出原則是Ａ．先進先出Ｂ．后進先出Ｃ．棧空則進Ｄ．棧滿則出（C）2.〖李春葆〗若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為Ａ．iＢ．n=iＣ．n-i+1Ｄ．不確定解釋：當p1=n，即n是最先出棧的，根據(jù)棧的原理，n必定是最后入棧的（事實上題目已經(jīng)表明了），那么輸入順序必定是1，2，3，…，n，則出棧的序列是n，…，3，2，1。（若不要求順序出棧，則輸出序列不確定）（B）3.〖李春葆〗判定一個棧ST（最多元素為m0）為空的條件是Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0（A）4.〖李春葆〗判定一個隊列QU（最多元素為m0）為滿隊列的條件是Ａ．QU->rear－QU->front==m0Ｂ．QU->rear－QU->front－1==m0Ｃ．QU->front==QU->rearＤ．QU->front==QU->rear+1解：隊滿條件是元素個數(shù)為m0。由于約定滿隊時隊首指針與隊尾指針相差1，所以不必再減1了，應當選A。當然，更正確的答案應該取模，即：QU->front==(QU->rear+1)%m0（D）5．數(shù)組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數(shù)小于ｎ，計算隊列中元素的公式為（Ａ）r－f;（Ｂ）（n＋f－r）%n;（Ｃ）n＋r－f;（Ｄ）（n＋r－f）%n6.【98初程P71】從供選擇的答案中，選出應填入下面敘述？內(nèi)的最確切的解答，把相應編號寫在答卷的對應欄內(nèi)。設有4個數(shù)據(jù)元素a1、a2、a3和a4，對他們分別進行棧操作或隊操作。在進?；蜻M隊操作時，按a1、a2、a3、a4次序每次進入一個元素。假設棧或隊的初始狀態(tài)都是空?，F(xiàn)要進行的棧操作是進棧兩次，出棧一次，再進棧兩次，出棧一次；這時，第一次出棧得到的元素是A，第二次出棧得到的元素是B是；類似地，考慮對這四個數(shù)據(jù)元素進行的隊操作是進隊兩次，出隊一次，再進隊兩次，出隊一次；這時，第一次出隊得到的元素是C，第二次出隊得到的元素是D。經(jīng)操作后，最后在棧中或隊中的元素還有E個。供選擇的答案：A～D：①a1②a2③a3④a4E：①1②2③3④0答：ABCDE＝2,4,1,2,27.【94初程P75】從供選擇的答案中，選出應填入下面敘述？內(nèi)的最確切的解答，把相應編號寫在答卷的對應欄內(nèi)。棧是一種線性表，它的特點是A。設用一維數(shù)組A[1,…,n]來表示一個棧，A[n]為棧底，用整型變量T指示當前棧頂位置，A[T]為棧頂元素。往棧中推入（PUSH）一個新元素時，變量T的值B；從棧中彈出（POP）一個元素時，變量T的值C。設?？諘r，有輸入序列a，b，c，經(jīng)過PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是D，變量T的值是E。供選擇的答案：A：①先進先出②后進先出 ③進優(yōu)于出 ④出優(yōu)于進 ⑤隨機進出B，C： ①加1②減1③不變 ④清0⑤加2⑥減2D：①a,b②b,c ③c,a ④b,a⑤c,b⑥a,cE：①n+1②n+2③n ④n-1⑤n-2答案：ABCDE=2,2,1,6,4注意，向地址的高端生長，稱為向上生成堆棧；向地址低端生長叫向下生成堆棧，本題中底部為n，向地址的低端遞減生成，稱為向下生成堆棧。8.【91初程P77】從供選擇的答案中，選出應填入下面敘述？內(nèi)的最確切的解答，把相應編號寫在答卷的對應欄內(nèi)。在做進棧運算時，應先判別棧是否A；在做退棧運算時，應先判別棧是否B。當棧中元素為n個，做進棧運算時發(fā)生上溢，則說明該棧的最大容量為C。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應將兩棧的D分別設在這片內(nèi)存空間的兩端，這樣，只有當E時，才產(chǎn)生上溢。供選擇的答案：A，B：①空②滿③上溢④下溢C： ①n-1②n③n+1④n/2D：①長度②深度③棧頂④棧底E：①兩個棧的棧頂同時到達?？臻g的中心點②其中一個棧的棧頂?shù)竭_棧空間的中心點③兩個棧的棧頂在達?？臻g的某一位置相遇④兩個棧均不空，且一個棧的棧頂?shù)竭_另一個棧的棧底答案：ABCDE＝2,1,2,4,3四、簡答題（每小題4分，共20分）1.【嚴題集3.2①和3.11①】說明線性表、棧與隊的異同點。劉答：相同點：都是線性結構，都是邏輯結構的概念。都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運算加以限制。不同點：①運算規(guī)則不同，線性表為隨機存取，而棧是只允許在一端進行插入、刪除運算，因而是后進先出表LIFO；隊列是只允許在一端進行插入、另一端進行刪除運算，因而是先進先出表FIFO。②用途不同，堆棧用于子程調(diào)用和保護現(xiàn)場，隊列用于多道作業(yè)處理、指令寄存及其他運算等等。2.【統(tǒng)考書P604-11，難于嚴題集3.1①】設有編號為1，2，3，4的四輛列車，順序進入一個棧式結構的車站，具體寫出這四輛列車開出車站的所有可能的順序。劉答：至少有14種。①全進之后再出情況，只有1種：4，3，2，1②進3個之后再出的情況，有3種，3,4,2,13,2,4,13,2,1,4③進2個之后再出的情況，有5種，2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4④進1個之后再出的情況，有5種，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,31.數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和運算等的學科。2.數(shù)據(jù)結構被形式地定義為（D,R），其中D是數(shù)據(jù)元素的有限集合，R是D上的關系有限集合。3.數(shù)據(jù)結構包括數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構和數(shù)據(jù)的運算這三個方面的內(nèi)容。4.數(shù)據(jù)結構按邏輯結構可分為兩大類，它們分別是線性結構和非線性結構。5.線性結構中元素之間存在一對一關系，樹形結構中元素之間存在一對多關系，圖形結構中元素之間存在多對多關系。6．在線性結構中，第一個結點沒有前驅(qū)結點，其余每個結點有且只有1個前驅(qū)結點；最后一個結點沒有后續(xù)結點，其余每個結點有且只有1個后續(xù)結點。7.在樹形結構中，樹根結點沒有前驅(qū)結點，其余每個結點有且只有1個前驅(qū)結點；葉子結點沒有后續(xù)結點，其余每個結點的后續(xù)結點數(shù)可以任意多個。8.在圖形結構中，每個結點的前驅(qū)結點數(shù)和后續(xù)結點數(shù)可以任意多個。9．數(shù)據(jù)的存儲結構可用四種基本的存儲方法表示，它們分別是順序、鏈式、索引和散列。10.數(shù)據(jù)的運算最常用的有5種，它們分別是插入、刪除、修改、查找、排序。11.一個算法的效率可分為時間效率和空間效率。二、單項選擇題（B）1.非線性結構是數(shù)據(jù)元素之間存在一種：A）一對多關系B）多對多關系C）多對一關系D）一對一關系（C）2.數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的結構；A)存儲B)物理C)邏輯D)物理和存儲（C）3.算法分析的目的是：A)找出數(shù)據(jù)結構的合理性B)研究算法中的輸入和輸出的關系C)分析算法的效率以求改進D)分析算法的易懂性和文檔性（A）4.算法分析的兩個主要方面是：A)空間復雜性和時間復雜性B)正確性和簡明性C)可讀性和文檔性D)數(shù)據(jù)復雜性和程序復雜性（C）5.計算機算法指的是：A)計算方法B)排序方法C)解決問題的有限運算序列D)調(diào)度方法（B）6.計算機算法必須具備輸入、輸出和等5個特性。A)可行性、可移植性和可擴充性B)可行性、確定性和有窮性C)確定性、有窮性和穩(wěn)定性D)易讀性、穩(wěn)定性和安全性2.【嚴題集1.2②】數(shù)據(jù)結構和數(shù)據(jù)類型兩個概念之間有區(qū)別嗎？答：簡單地說，數(shù)據(jù)結構定義了一組按某些關系結合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結構的數(shù)據(jù)元素，而且還在其上定義了一組操作。3.簡述線性結構與非線性結構的不同點。答：線性結構反映結點間的邏輯關系是一對一的，非線性結構反映結點間的邏輯關系是多對多的。3.x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;解：因為3.x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;解：因為x++共執(zhí)行了n-1+n-2+……＋1=n(n-1)/2，所以執(zhí)行時間為O（n2）2.s=0;2.s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;答：O（n2）1.for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;答：O（m*n）4.4.i=1;while(i<=n)i=i*3;答：O（log3n）五、設有數(shù)據(jù)邏輯結構S=（D,R），試按各小題所給條件畫出這些邏輯結構的圖示，并確定相對于關系R，哪些結點是開始結點，哪些結點是終端結點？1.【嚴蔚敏習題集P71.3②】D={d1,d2,d3,d4}R={(d1,d2),(d2,d3),(d3,d4)}答：d1→d2→d3→d4d1—無直接前驅(qū)，是首結點d4—無直接后繼是尾結點2。D={d1,d2,…,d9}R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5),(d6,d7),(d8,d9)}答：此圖為樹形結構d1—無直接前驅(qū)，是根結點d2,d5,d7,d9—無直接后繼是葉子結點3．D={d1,d2,…,d9}R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9),(d5,d6),(d8,d9),(d9,d7),(d4,d7),(d4,d6)}答：此圖為圖形結構d1，d2—無直接前驅(qū)，是開始結點d6,d7—無直接后繼是終端結點1.不包含任何字符（長度為0）的串稱為空串；由一個或多個空格（僅由空格符）組成的串稱為空白串。（對應嚴題集4.1①，簡答題：簡述空串和空格串的區(qū)別）2.設S=“A;/document/Mary.doc”，則strlen(s)=20,“/”的字符定位的位置為3。4.子串的定位運算稱為串的模式匹配；被匹配的主串稱為目標串，子串稱為模式。5.設目標T=”abccdcdccbaa”，模式P=“cdcc”，則第6次匹配成功。6.若n為主串長，m為子串長，則串的古典（樸素）匹配算法最壞的情況下需要比較字符的總次數(shù)為(n-m+1)*m。7.假設有二維數(shù)組A6×8，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置（基地址）為1000，則數(shù)組A的體積（存儲量）為288B；末尾元素A57的第一個字節(jié)地址為1282；若按行存儲時，元素A14的第一個字節(jié)地址為(8+4)×6+1000=1072；若按列存儲時，元素A47的第一個字節(jié)地址為(6×7＋4)×6＋1000）＝1276。(注：數(shù)組是從0行0列還是從1行1列計算起呢？由末單元為A57可知，是從0行0列開始！)8.〖00年計算機系考研題〗設數(shù)組a[1…60,1…70]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a[32,58]的存儲地址為8950。答：不考慮0行0列，利用列優(yōu)先公式：LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝89509.三元素組表中的每個結點對應于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的行下標、列下標和元素值。10.求下列廣義表操作的結果：（1）GetHead【((a,b),(c,d))】===(a,b);//頭元素不必加括號（2）GetHead【GetTail【((a,b),(c,d))】】===(c,d);（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】===b;（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】===（d）;二、單選題（每小題1分，共15分）（B）1.〖李〗串是一種特殊的線性表，其特殊性體現(xiàn)在：Ａ．可以順序存儲Ｂ．數(shù)據(jù)元素是一個字符Ｃ．可以鏈式存儲Ｄ．數(shù)據(jù)元素可以是多個字符（B）2.〖李〗設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作：Ａ．連接Ｂ．模式匹配Ｃ．求子串Ｄ．求串長D）3.〖李〗設串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號i開始的j個字符組成的子串，len(s)返回串s的長度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結果串是：Ａ．BCDEFＢ．BCDEFGＣ．BCPQRSTＤ．BCDEFEF解：con(x,y)返回x和y串的連接串，即con(x,y)＝‘ABCDEFGPQRST’；subs(s,i,j)返回串s的從序號i開始的j個字符組成的子串，則subs(s1,2,len(s2))＝subs(s1,2,5)=’BCDEF’;subs(s1,len(s2),2)＝subs(s1,5,2)=’EF’;所以con(subs(s1,2,len(s2)),subs(s1,len(s2),2))＝con(’BCDEF’,’EF’)之連接，即BCDEFEF（A）4.〖01年計算機系考研題〗假設有60行70列的二維數(shù)組a[1…60,1…70]以列序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第32行第58列的元素a[32,58]的存儲地址為。（無第0行第0列元素）Ａ．16902Ｂ．16904Ｃ．14454Ｄ．答案A,B,C均不對答：此題與填空題第8小題相似。（57列×60行＋31行）×2字節(jié)＋10000=16902(B)5.設矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分（如下圖所示）按行序存放在一維數(shù)組B[1,n(n-1)/2]中，對下三角部分中任一元素ai,j(i≤j),在一維數(shù)組B中下標k的值是：Ａ．i(i-1)/2+j-1Ｂ．i(i-1)/2+jＣ．i(i+1)/2+j-1Ｄ．i(i+1)/2+j解：注意B的下標要求從1開始。先用第一個元素去套用，可能有B和C；再用第二個元素去套用B和C，B=2而C＝3（不符）；所以選B6.【91初程P78】從供選擇的答案中，選出應填入下面敘述解：注意B的下標要求從1開始。先用第一個元素去套用，可能有B和C；再用第二個元素去套用B和C，B=2而C＝3（不符）；所以選B有一個二維數(shù)組A，行下標的范圍是0到8，列下標的范圍是1到5，每個數(shù)組元素用相鄰的4個字節(jié)存儲。存儲器按字節(jié)編址。假設存儲數(shù)組元素A[0,1]的第一個字節(jié)的地址是0。存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是A。若按行存儲，則A[3,5]和A[5,3]的第一個字節(jié)的地址分別是B和C。若按列存儲，則A[7,1]和A[2,4]的第一個字節(jié)的地址分別是D和E。供選擇的答案：A～E：①28②44③76④92⑤108⑥116⑦132⑧176⑨184⑩188答案：ABCDE=8,3,5,1,67.【94程P12】有一個二維數(shù)組A，行下標的范圍是1到6，列下標的范圍是0到7，每個數(shù)組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。那么，這個數(shù)組的體積是A個字節(jié)。假設存儲數(shù)組元素A[1,0]的第一個字節(jié)的地址是0，則存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是B。若按行存儲，則A[2,4]的第一個字節(jié)的地址是C。若按列存儲，則A[5,7]的第一個字節(jié)的地址是D。供選擇的答案A～D：①12②66③72④96⑤114⑥120⑦156⑧234⑨276⑩282（11）283（12）288答案：ABCD=12,10,3,91.【嚴題集2.2①】在順序表中插入或刪除一個元素，需要平均移動表中一半元素，具體移動的元素個數(shù)與表長和該元素在表中的位置有關。2.線性表中結點的集合是有限的，結點間的關系是一對一的。3.向一個長度為n的向量的第i個元素(1≤i≤n+1)之前插入一個元素時，需向后移動n-i+1個元素。4.向一個長度為n的向量中刪除第i個元素(1≤i≤n)時，需向前移動n-i個元素。5.在順序表中訪問任意一結點的時間復雜度均為O(1)，因此，順序表也稱為隨機存取的數(shù)據(jù)結構。6.【嚴題集2.2①】順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。7.【嚴題集2.2①】在單鏈表中，除了首元結點外，任一結點的存儲位置由其直接前驅(qū)結點的鏈域的值指示。8．在n個結點的單鏈表中要刪除已知結點*p，需找到它的前驅(qū)結點的地址，其時間復雜度為O（n）。（×）1.鏈表的每個結點中都恰好包含一個指針。答：錯誤。鏈表中的結點可含多個指針域，分別存放多個指針。例如，雙向鏈表中的結點可以含有兩個指針域，分別存放指向其直接前趨和直接后繼結點的指針。（×）2.鏈表的物理存儲結構具有同鏈表一樣的順序。錯，鏈表的存儲結構特點是無序，而鏈表的示意圖有序。（×）3.鏈表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續(xù)的各個單元向前移動。錯，鏈表的結點不會移動，只是指針內(nèi)容改變。（×）4.線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。錯，混淆了邏輯結構與物理結構，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)。（×）5.順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。錯，正好說反了。順序表才適合隨機存取，鏈表恰恰適于“順藤摸瓜”（×）6.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。錯，前一半正確，但后一半說法錯誤，那是鏈式存儲的優(yōu)點。順序存儲方式插入、刪除運算效率較低，在表長為n的順序表中，插入和刪除一個數(shù)據(jù)元素，平均需移動表長一半個數(shù)的數(shù)據(jù)元素。（×）7.線性表在物理存儲空間中也一定是連續(xù)的。錯，線性表有兩種存儲方式，順序存儲和鏈式存儲。后者不要求連續(xù)存放。（×）8.線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯誤。線性表有兩種存儲方式，在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序上也相鄰。（×）9.順序存儲方式只能用于存儲線性結構。錯誤。順序存儲方式不僅能用于存儲線性結構，還可以用來存放非線性結構，例如完全二叉樹是屬于非線性結構，但其最佳存儲方式是順序存儲方式。（后一節(jié)介紹）（×）10.線性表的邏輯順序與存儲順序總是一致的。錯，理由同7。鏈式存儲就無需一致。（C）1．數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：（A）存儲結構（B）邏輯結構（C）順序存儲結構（D）鏈式存儲結構（B）2.一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（A）110（B）108（C）100（D）120（A）3.在n個結點的順序表中，算法的時間復雜度是O（1）的操作是：訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅(qū)（2≤i≤n）在第i個結點后插入一個新結點（1≤i≤n）刪除第i個結點（1≤i≤n）將n個結點從小到大排序（B）4.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動個元素（A）8（B）63.5（C）6