(全)2024版數(shù)據(jù)結(jié)構(gòu)考試內(nèi)部題庫(kù)含答案解析（全考點(diǎn)）

數(shù)據(jù)結(jié)構(gòu)考試內(nèi)部題庫(kù)含答案解析（全考點(diǎn)）.以下屬于邏輯結(jié)構(gòu)的是（） ?A:順序表?B:哈希表?C:有序表?D:單鏈表解析順序表、哈希表和單鏈表是三種不同的數(shù)據(jù)結(jié)構(gòu)，既描述邏輯結(jié)構(gòu)，又描述存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)運(yùn)算。而有序表是指關(guān)鍵字有序的線性表，僅描述元素之間的邏輯關(guān)系，它既可以鏈?zhǔn)酱鎯?chǔ)，又可以順序存儲(chǔ)，故屬于邏輯結(jié)構(gòu)。答案：C2、鏈?zhǔn)酱鎯?chǔ)設(shè)計(jì)時(shí)，結(jié)點(diǎn)內(nèi)的存儲(chǔ)單元地址（）。?A:一定連續(xù)?B:一定不連續(xù)?C:不一定連續(xù)?D:部分連續(xù)，部分不連續(xù)答案：B2、從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中檢索其值等于x的結(jié)點(diǎn)時(shí)，在檢索成功的情況下，需平均比較的結(jié)點(diǎn)個(gè)數(shù)是A:n/2B:nC:(n+l)/2D:(n-l)/2解析由于單鏈表只能進(jìn)行單向順序查找，以從第一個(gè)節(jié)點(diǎn)開(kāi)始查找為例，查找第m個(gè)節(jié)點(diǎn)需要比較的節(jié)點(diǎn)數(shù)f(m)=m，查找成功的最好情況是第一次就查找成功，只用比較1個(gè)節(jié)點(diǎn)，最壞情況則是最后才查找成功，需要比較n個(gè)節(jié)點(diǎn)。所以一共有n種情況，平均下來(lái)需要比較的節(jié)點(diǎn)為(1+2+3+...+(n-l)+n)/n=(n+l)/2答案：C3.當(dāng)n足夠大時(shí)，下述函數(shù)中漸近時(shí)間最小的是—o??A:T(n)=nlog(n)-1000log(n).?B:T(n)=nlog(3)-1000log(n)??C:T(n)=-lOOOIog(n).?D:T(n)=2nlog(n)-1000log(n)解析ABCD四個(gè)選項(xiàng)時(shí)間復(fù)雜度依次為0( n)、0(n)、0( )、0(nn)o所以n足夠大時(shí)，時(shí)間復(fù)雜度最小的是0(n),選Bo答案：B4.倒排文件包含有若干個(gè)倒排表，倒排表的內(nèi)容是—o?A:一個(gè)關(guān)鍵字值和該關(guān)鍵字的記錄地址?B:一個(gè)屬性值和該屬性的一個(gè)記錄地址?C:一個(gè)屬性值和該屬性的全部記錄地址?D:多個(gè)關(guān)鍵字和它們相對(duì)應(yīng)的某個(gè)記錄的地址解析有倒排索引的文件我們稱(chēng)為倒排索引文件，簡(jiǎn)稱(chēng)倒排文件。倒排索引，也常被稱(chēng)為反向索引，是一種索引方法，被用來(lái)存儲(chǔ)在全文搜索下某個(gè)單詞在一個(gè)文檔或者一組文檔中的存儲(chǔ)位置的映射。倒排索引源于實(shí)際應(yīng)用中需要根據(jù)屬性的值來(lái)查找記錄。這種索引表中的每一項(xiàng)都包括一個(gè)屬性值和具有該屬性值的各記錄的地址。答案：C5、下述編碼中不是前綴碼的是—o?A:{0,10,110,111)?B:{0,1,00,11}?C:{1,01,000,001)?D:{00,01,10,11}解析前綴編碼是指對(duì)字符集進(jìn)行編碼時(shí)，要求字符集中任一字符的編碼都不是其他字符的編碼的前綴。選項(xiàng)B中。和00不符合前綴碼要求。答案：B6、下面程序段的時(shí)間復(fù)雜度是i=s=0;while(s<n)i++;s+=i;A:O(log(n))B:oOC:0(n)\)//(\\)//(\O??D解析第一次執(zhí)行完s+=is=l第二次s=3=l+2第三次s=6=1+2+3第四次s=10=l+2+3+4第k次l+2+3+4+...+k=L那么當(dāng)>=n的時(shí)々房停止，也就是k=□所以復(fù)雜度是答案：B7、在有向圖中每個(gè)頂點(diǎn)的度等于該頂點(diǎn)的—oA:入讀B:出度C:入讀與出度之和D:入讀與出度之差解析在有向圖中每個(gè)頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。答案：C8、具有n個(gè)頂點(diǎn)的無(wú)向完全圖有一條邊。?A:n?B:n*(n-l)/2?C:n*(n+l)/2?D:n*n/2解析具有n個(gè)頂點(diǎn)的無(wú)向完全圖有n*(n-l)/2條弧答案：B9、下列程序段的時(shí)間復(fù)雜度是一ocount=0;for(k=l;k<=n;k*=2)for(j=l;j<=n;j++)count++;A:0(n)B:0(n)r?IC:0(nn)D:0(ZJ解析內(nèi)層循環(huán)條件j<=n與外層循環(huán)的變量無(wú)關(guān)，各自獨(dú)立。每執(zhí)行一次j自增1每次內(nèi)層循環(huán)都執(zhí)行n次。外層循環(huán)條件k<=n,增量定義為k*=2,可知循環(huán)I !■ |次數(shù)t滿(mǎn)足kJ<=n,gpt<=n。即內(nèi)層循環(huán)的時(shí)間復(fù)雜度為0(n)，外層循環(huán)的時(shí)間復(fù)雜度為0(n)o對(duì)于嵌入循環(huán)，根據(jù)乘法規(guī)則可知，該程序的時(shí)間復(fù)雜度T(n)= (n)* (n)=0(n)*0(—n)=0(n答案：C10.一個(gè)算法所需時(shí)間由下述遞歸方程表示，試求出該算法的時(shí)間復(fù)雜度的級(jí)別(或階)。式中n是問(wèn)題的規(guī)模，為簡(jiǎn)單起見(jiàn)，設(shè)n是2的整數(shù)次幕。解析設(shè)n=「(k—O),根據(jù)題目所給定義有4?——1 卜」-一?一I1 —!|!I[?一——???一，| [?-?一t(M=2t(U)+I—I=Ut(U)+2I L由此可得一般遞推公式t(O)=二r(_)+i匚口，進(jìn)而得r-n 「一一「- r-T(—hl—IT(I—l)+k——=(k+l)L即卜―] ['?■—| |'a*9l'ir.lW?| I'.J'Jfl!T(n)=2A{n}+ {nn}=n(n+1),也就是O(nlIn)o解析鏈?zhǔn)酱鎯?chǔ)設(shè)計(jì)時(shí)，各個(gè)不同結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但結(jié)點(diǎn)內(nèi)的存儲(chǔ)單元地址必須連續(xù)。答案：A3、對(duì)于兩種不同的數(shù)據(jù)結(jié)構(gòu)，邏輯結(jié)構(gòu)或物理結(jié)構(gòu)一定不相同嗎？數(shù)據(jù)的運(yùn)算也是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面。對(duì)于兩種不同的數(shù)據(jù)結(jié)構(gòu)，它們的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)完全有可能相同。比如二叉樹(shù)和二叉排序樹(shù)，二叉排序樹(shù)可以采用二叉樹(shù)的邏輯表示和存儲(chǔ)方式，前者通常用于表示層次關(guān)系，而后者通常用于排序和查找。雖然它們的運(yùn)算都有建立樹(shù)、插入結(jié)點(diǎn)、刪除結(jié)點(diǎn)和查找結(jié)點(diǎn)等功能，但對(duì)于二叉樹(shù)和二叉排序樹(shù)，這些運(yùn)算的定義是不同的，以查找結(jié)點(diǎn)為例，二叉樹(shù)的時(shí)間復(fù)雜度為0(n),而二叉排序樹(shù)的時(shí)間復(fù)雜度為O(logc\n4、試舉一例，說(shuō)明對(duì)相同的邏輯結(jié)構(gòu)，同一種運(yùn)算在不同的存儲(chǔ)方式下實(shí)現(xiàn)時(shí)，其運(yùn)算效率不同。線性表既可以用順序存儲(chǔ)方式實(shí)現(xiàn)，又可以用鏈?zhǔn)酱鎯?chǔ)方式實(shí)現(xiàn)。在順序存儲(chǔ)方式下，在線性表中插入和刪除元素，平均要移動(dòng)近一半的元素，時(shí)間復(fù)雜度為0(n);而在鏈?zhǔn)酱鎯?chǔ)方式下，插入和刪除的時(shí)間復(fù)雜度都是0(1)。5、下面關(guān)于倒排文件的說(shuō)法中正確的是一o.?A:倒排文件是對(duì)主關(guān)鍵字建立索引B:倒排文件是對(duì)次關(guān)鍵字建立索引C:倒排文件的優(yōu)點(diǎn)是維護(hù)簡(jiǎn)單?D:采用倒排文件是為了節(jié)省存儲(chǔ)空間解析倒排文件：用記錄的非主屬性(也叫副鍵)來(lái)查找記錄而組織的文件叫倒排文件，即次索引。倒排文件中包括了所有副鍵值，并列出了與之有關(guān)的所有記錄主鍵值，主要用于復(fù)雜查詢(xún)。倒排文件的優(yōu)點(diǎn)是檢索記錄較快。特別是對(duì)某些詢(xún)問(wèn)，不用讀取記錄，就可得到解答。答案：B6、下列術(shù)語(yǔ)中與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)。?A:循環(huán)隊(duì)列?B:堆棧.?C:散列表?D:單鏈表解析數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ)。棧是一種抽象數(shù)據(jù)類(lèi)型，可采用順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，是一種邏輯結(jié)構(gòu)。散列表和單鏈表表示幾種數(shù)據(jù)結(jié)構(gòu)，既描述邏輯結(jié)構(gòu)，又描述存儲(chǔ)結(jié)構(gòu)。答案：B7.下面程序的時(shí)間復(fù)雜度為一ofor(i=1,s=0;i<n;i++){t=1;for(j=1;j<=i;j++)s=s+t;}?A:0(n)B:0(n2.D:0(n4解析分析代碼：內(nèi)層循環(huán)執(zhí)行i次，外層循環(huán)執(zhí)行n次，i從1取到no得知執(zhí)行最內(nèi)層循環(huán)語(yǔ)句總次數(shù)為(1+n)*no n2N，即o()o答案：B8、下面算法的時(shí)間復(fù)雜度是一oVoidfun(intn)intiwhile(s<n)++i；s=s+i;A:0(n)n2B:0( )?C:0(?C:0(D:O(nlog(n))解析最底層的代碼為S=s+i,s到達(dá)n的過(guò)程剛好是1+2+3+4….+m這樣累加起來(lái)的,根據(jù)等差隊(duì)列之和的公式，（l+m）*m=2n,故m約等于根號(hào)n,所以此題選C。答案：C9、下面算法的空間復(fù)雜度為—floataver(floata[n]){intj;for(j=n;j>0;j一)printf(H%8.2fnAa[j]);A:0(1)c\nB:O(log，)C:0(n)n2D:0( )解析函數(shù)體定義中出現(xiàn)數(shù)組，數(shù)組在初始化時(shí)需要分配空間,此時(shí)空間復(fù)雜度為0(n),所以選Co答案：C10,已知程序如下所示，程序運(yùn)行時(shí)使用棧來(lái)保存調(diào)用過(guò)程的信息，自棧底到棧頂保存的信息依次對(duì)應(yīng)的是intS(intn){return(n<=0)?0:S(n-1)+n;voidmain(){cout<<S(1);)?A:main()->S(l)->S(0)?B:S(0)->S(l)->main()?C:main()->S(0)->S(l)?D:S(l)->S(0)->main()解析程序都是從main函數(shù)開(kāi)始的,進(jìn)入main函數(shù)后執(zhí)行S(l),之后遞歸執(zhí)行S(0)o答案：A1.下列函數(shù)的時(shí)間復(fù)雜度是一。intfunc(intn)int