2023年數(shù)據(jù)結(jié)構(gòu)題庫

1.一個非空廣義表的表頭______。A.不也許是子表B.只能是子表C.只能是原子D.可以是子表或原子2.在以下的敘述中，對的的是________。A.二維數(shù)組可以看做它的每個數(shù)據(jù)元素為一個線性表的線性表B.棧的操作方式是先進先出C.線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)D.隊列的操作方式是先進后出3.如下陳述中對的的是________。A.串是一種特殊的線性表B.串的長度必須大于零C.串中元素只能是字母D.空串就是空白串4.如下陳述中對的的是______。A.串是一種特殊的線性表B.串的長度必須大于零C.串中元素只能是字母D.兩個串s1和s2若長度相同，則這兩個串相等5.數(shù)組A中,每個元素的長度為3字節(jié),行下標從1到8,列下標從1到10,從首地址SA開始連續(xù)存放在存儲器中,按行存放時,元素a[8][5]地址為。A.SA+141B.SA+180C.SA+222D.SA+2256.任何一個非空列表其表頭也許是原子，也也許是列表，而其表尾是。A.原子B.列表C.任何元素D.空7.稀疏矩陣一般的壓縮存儲方法有兩種。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表8.常對數(shù)組進行的兩種基本操作是。A.建立和刪除B.插入和修改C.查找和修改D.查找和索引9.假定運用數(shù)組a[N]順序存儲一個棧，用top表達棧頂指針，top==0表達?？?，并已知棧未滿，當元素x進棧時所執(zhí)行的操作為______。A.a[--top]=x;B.a[top--]=x;C.a[++top]=x;D.a[top++]=x;10.由兩個棧共享一個向量空間的好處是______。A.減少存取時間,減少下溢發(fā)生的機率B.節(jié)省存儲空間,減少上溢發(fā)生的機率C.減少存取時間,減少上溢發(fā)生的機率D.節(jié)省存儲空間,減少下溢發(fā)生的機率11.入棧順序是a,b,c,d,e，則出棧順序不也許是________A.e,d,c,b,aB.d,e,c,b,aC.d,c,e,a,bD.a,b,c,d,e12.假定運用數(shù)組a[N]循環(huán)順序存儲一個隊列，用front(指向隊首元素)和rear(指向隊尾元素的下一位置)分別表達隊首和隊尾指針，并已知隊列未空，當出隊并返回隊首元素時所執(zhí)行的操作為______。A.returna[++rear%N];B.returna[--rear%N];C.returna[++front%N];D.returna[front++%N];13.當運用大小為N的一維數(shù)組存儲一個循環(huán)隊列時，則該隊列的最大長度為______。A.N-2B.N-1C.ND.N+114.假定一個長度為n的循環(huán)順序隊列的隊首和隊尾指針分別為f和r，則判斷隊滿的條件是_____。A.(f+1)%n==rB.(r+1)%n==fC.f==0D.f==r15.假定一個鏈隊列的隊首和隊尾指針分別為front和rear，則判斷隊空的條件是_____。A.front==rearB.front!=NULLC.rear!=NULLD.front==NULL16.隊和棧的重要區(qū)別是________。A.邏輯結(jié)構(gòu)不同B.存儲結(jié)構(gòu)不同C.所包含的運算個數(shù)不同D.限定插入和刪除的位置不同17.假定一個順序隊列的隊首和隊尾指針分別為front和rear，則判斷隊空的條件是________。A.front+1==rearB.rear+1==frontC.front==0D.front==rear18.鏈式棧與順序棧相比，一個比較明顯的優(yōu)點是________。A.插入操作更加方便B.通常不會出現(xiàn)棧滿的情況C.不會出現(xiàn)?？盏那闆rD.刪除操作更加方便19.鑒定一個棧ST（最多元素為m0）為空的條件是_________A.ST->top<>0B.ST->top=0C.ST->top<>m0D.ST->top=m020.下面算法的時間復雜度為____________。intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A.O(1)B.O(n)C.O(n2)D.O(n!)21.在長度為n的順序存儲的線性表中，刪除第i個元素（1≤i≤n）時，需要從前向后依次前移()個元素。A.n-IB.n-i+1C.n-i-1D.i22.線性表若采用鏈式存儲結(jié)構(gòu)時，規(guī)定內(nèi)存中可用存儲單元的地址________。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)，不連續(xù)都可以23.計算機辨認、存儲和加工解決的對象被統(tǒng)稱為()A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型24.算法指的是。A.計算機程序B.解決問題的計算方法C.排序算法D.解決問題的有限運算序列25.在對n個元素進行快速排序的過程中，第一趟排序最多需要互換______對元素。A.n/2B.n-1C.nD.n+126.若對n個元素進行直接插入排序，在進行i趟(2≤i≤n)排序時，為尋找插入位置最多需要進行______次元素的比較。A.i+1B.i-1C.iD.127.對于哈希函數(shù)H(key)=key%13，被稱為同義詞（即沖突）的關(guān)鍵字是_______A.35和41B.23和39C.15和44D.25和5128.若一組記錄的排序碼為（46,79,56,38,40,84），則運用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為________A.38,40,46,56,79,84B.40,38,46,79,56,84C.40,38，46,56,79,84D.40,38,46,84,56,7929.在對n個元素進行簡樸選擇排序的過程中，需要進行______趟選擇。A.n/2B.n-1C.nD.n+130.用某種排序方法對關(guān)鍵字序列（23，72，21，47，15，27，59，35，20）進行排序時，前三趟的結(jié)果情況如下________：23，21，47，15，27，59，35，20，7221，23，15，27，47，35，20，59，7221，15，23，27，35，20，47，59，72則所采用的排序方法是________A.選擇排序B.起泡排序C.歸并排序D.快速排序31.設(shè)哈希表長為14，哈希函數(shù)f（k）=k％11，已知表中已有4個元素，關(guān)鍵字分別為15，38，61，84，存儲位置分別為4，5，6，7，其它存儲位置為空，如用二次探測再散列解決沖突，關(guān)鍵字為49的存儲位置是______。A.8B.3C.5D.932.對于順序存儲的有序表(5,12,20,26,37,42,46,50,64)，哨兵位在前，為查找元素26，若采用順序查找，需要比較______次才干查找成功。A.3B.4C.5D.633.具有e條邊的無向圖，它的鄰接表中有______個邊結(jié)點。A.e-1B.eC.2(e-1)D.2e34.具有e條邊的有向圖，它的逆鄰接表中有______個弧結(jié)點。A.e-1B.eC.2(e-1)D.2e35.由權(quán)值分別為3,8,6,2,5的葉子結(jié)點生成一顆哈夫曼樹，它的帶權(quán)途徑長度為______。A.24B.48C.72D.5336.假如某圖的鄰接矩陣是對角線元素以下元素均為零的上三角矩陣，則此圖是_______。A.有向完全圖B.連通圖C.強連通圖D.有向無環(huán)圖37.下面關(guān)于圖的存儲的敘述中，哪一個是對的的。A.用鄰接矩陣法存儲圖,占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關(guān),而與邊數(shù)無關(guān)B.用鄰接矩陣法存儲圖,占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān),而與結(jié)點個數(shù)無關(guān)C.用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關(guān)，而與邊數(shù)無關(guān)D.用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)38.圖的深度優(yōu)先遍歷類似于樹的_______。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷39.一個連通圖的生成樹是包含圖中所有頂點的一個______子圖。A.極小B.連通C.極小連通D.無環(huán)40.有向圖的一個頂點的度為該頂點的______。A.入度B.出度C.入度與出度之和D.(入度＋出度)/241.在一個有向圖中，所有頂點的度數(shù)之和等于所有弧數(shù)的______倍。A.3B.2C.1D.1/242.n個頂點的連通圖至少有______條邊。A.n-1B.nC.n+1D.043.頂點個數(shù)為n的無向圖最多有______條邊。A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)44.樹中所有結(jié)點的度數(shù)之和等于結(jié)點總數(shù)加______。A.0B.1C.-1D.245.在一棵樹中，每個結(jié)點最多有______個直接前驅(qū)結(jié)點。A.0B.1C.2D.任意多個46.將一棵有40個結(jié)點的完全二叉樹從上到下，從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1，則編號為15的結(jié)點的左孩子的編號為______。A.30B.31C.16D.3247.一棵樹的廣義表表達為a(b(c),d(e(g(h)),f))，則該樹的度為2的結(jié)點數(shù)為______。A.2B.3C.4D.548.一棵樹的廣義表表達為a(b(c),d(e(g(h)),f))，則該樹的度為______。A.2B.3C.4D.549.一棵樹的廣義表表達為a(b(c),d(e(g(h)),f))，則該樹的高度為______。A.2B.3C.4D.550.在一棵深度為h的完全二叉樹中，所含結(jié)點個數(shù)不少于______。A.2hB.2h+1C.2h-1D.2h-151.在一棵二叉樹的第5層上，最多具有______個結(jié)點。A.14B.16C.31D.3252.在一棵具有n個結(jié)點的二叉樹中，所有結(jié)點的空子樹個數(shù)等于______。A.nB.n-1C.n+1D.2*n53.數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的及它們之間的聯(lián)系。A.存儲和邏輯結(jié)構(gòu)B.存儲和抽象C.抱負和抽象D.抱負與邏輯在含100個結(jié)點的完全二叉樹，葉子結(jié)點的個數(shù)為__50______。2.一棵具有16個結(jié)點的完全二叉樹，對他按層編號，對于編號為7的結(jié)點，他的雙親結(jié)編號點為_3_____左孩子編號為__14____、右孩子編號為___15___。3.對任何一棵二叉樹，若n0，n1，n2分別是度為0，1，2的結(jié)點的個數(shù)，則n0=__n2+1_____。4.高度為k的二叉樹具有的結(jié)點數(shù)目，最少為___k___,最多為__2k-1____。5.對于一顆具有n個結(jié)點的二叉樹，相應二叉鏈表中指針域有_n-1_____個用于指向子結(jié)點。6.樹的雙親表達法便于實現(xiàn)涉及到_雙親_____的操作，孩子表達法便于實現(xiàn)涉及到孩子的操作。7.在一棵二叉樹中，度為2的結(jié)點有5個，度為1的結(jié)點有6個，那么葉子結(jié)點有_6_____個8.假定一棵樹的廣義表表達為A(B(C,D(E,F,G),H(I,J)))，則結(jié)點H的雙親結(jié)點為_B_____。9.假定一棵二叉樹的結(jié)點個數(shù)為32，則它的最小深度為__6____。10.已知廣義表ls=(a,(b,c,d),e),運用head和tail函數(shù)取出ls中的原子b的運算是__head(head(tail(ls)))______。11.廣義表（A,(a,b),d,e,((i,j),k)）,則廣義表的長度為_5____，深度為__3____，表頭為___A___，表尾為__（(a,b),d,e,((i,j),k)）__________。12.稀疏矩陣可用三元組進行壓縮存儲，存儲時需存儲非零元的_元素值_____和行、列數(shù)。13.在串的鏈式存儲方式中，結(jié)點越大，運算解決越___不方便），存儲占用量越__小）14.一個串的任意個連續(xù)的字符組成的子序列稱為該串的__子串____，包含該子序列的串稱為_主串_____，該子序列在串中的位置用_子串的第一個字符在主串中的位置_________________來表達。15.廣義表（（a））的表頭是（a）,表尾是（）。16.廣義表（（a）,a）的表頭是（a），表尾是（a)。17.數(shù)組A中，每個元素的長度為3個字節(jié)，行下標從1到8，列下標從1到10，從首地址開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)是240。18.棧的特點是__后進先出____________________。19.對于順序存儲的隊列，存儲空間大小為n，頭指針為F，尾指針為R。若在邏輯上看一個環(huán)，則隊列中元素的個數(shù)為__(R-F+n)%n_________。20.隊列又稱為__先進先出______的線性表。21.棧結(jié)構(gòu)允許進行刪除操作的一端為__棧頂______。22.已知循環(huán)隊列的存儲空間為數(shù)組a[21]，且頭指針（指向隊頭元素）和尾指針（隊尾元素的下一位置）分別為8和3，則該隊列的當前長度為__16______。23.在初始為空的隊列中插入元素A,B,C,D以后，緊接著做了兩次刪除操作，此時的隊尾元素是_D_______。24.在非空線性表中除第一個元素外，集合中每個數(shù)據(jù)元素只有一個_直接前驅(qū)________；除最后一個元素之外，集合中每個數(shù)據(jù)元素均只有一個__直接后繼________。25.在雙向鏈表中，每個結(jié)點具有兩個指針域，一個指向_直接前驅(qū)_______結(jié)點，另一個指向_直接后繼____結(jié)點。26.在單鏈表設(shè)立表頭結(jié)點的作用是插入和刪除表中第一個元素時不必對__頭指針______進行特殊解決。27.在一個單鏈表L中，若要在指針q所指結(jié)點的后面插入一個由指針p所指向的結(jié)點，則應進行的操作序列為：__p-next=q->next______________;q一>next=p。28.順序表中邏輯上相鄰的元素的物理位置_相鄰_______，單鏈表中邏輯上相鄰的元素的物理位置__不一定相鄰______。29.在以L為頭指針的帶頭結(jié)點的單鏈表和單循環(huán)鏈表中，判斷鏈表是否為空的條件分別為_L->next==NULL____和_L->next==L____。30.已知一順序存儲的線性表，每個元素占用k個存儲單元，若第一個元素的地址為Loc1，則第i個元素的地址為__Loc1+（i-1）*k______________。31.若經(jīng)常需要對線性表進行插入與刪除操作，該線性表最佳采用__鏈式______存儲結(jié)構(gòu)。32.若經(jīng)常需要對線性表進行查找操作，則最佳采用__順序______存儲結(jié)構(gòu)。33.若待散列的序列為(18,25,63,50,42,32,9)，散列函數(shù)為H(key)=key%9，與18發(fā)生沖突的元素有_63,9_____。34._循環(huán)鏈表_______鏈表從任何一個結(jié)點出發(fā)，都能訪問到所有結(jié)點。35.假定一組數(shù)據(jù)的關(guān)鍵字為{46,79,56,38,40,84}，則以第一個記錄為樞軸，對其進行第一趟快速排序的結(jié)果為_{40,38,46,56,79,84}_____。36.假定一組數(shù)據(jù)的關(guān)鍵字為{46,79,56,38,40,84}，則運用堆排序方法建立的初始小頂堆為_{38，40，56，79，46，84}_____。37.每次直接或通過“樞軸”元素間接比較兩個元素，若出現(xiàn)逆序排列時就互換它們的位置，此種排序方法叫做__互換____排序。38.每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序方法叫做_插入_____排序。39.每次從無序表中挑選出一個最大或最小元素，把它互換到有序表的一端，此種排序方法叫做_選擇_____排序。40.每次使兩個相鄰的有序表合并成一個有序表的排序方法叫做_2路歸并排序_____排序。41.先將整個待排序列分割成若干子序列分別進行直接插入排序，待整個序列“基本有序”時，再對全體進行一次直接插入排序，此種排序方法叫做__希爾____排序。42.將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列叫_排序_____。43.元素關(guān)鍵字轉(zhuǎn)換為該元素存儲位置的函數(shù)f稱為__哈希函數(shù)____。44.數(shù)據(jù)的邏輯結(jié)構(gòu)涉及集合、_線性結(jié)構(gòu)_______、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)四種類型。45.已知有實現(xiàn)同一功能的兩個算法，其時間復雜度分別為O(log2n)和O(n)，哪個算法的效率更高？___O(log2n)_____46.假設(shè)在有序線性表a[20]上進行折半查找，則比較一次查找成功的結(jié)點數(shù)為1；比較兩次查找成功的結(jié)點數(shù)為2；比較四次查找成功的結(jié)點數(shù)為8；平均查找長度為3.747.在數(shù)據(jù)的存放無規(guī)律而言的線性表中進行檢索的最佳方法是順序查找48.元素關(guān)鍵字轉(zhuǎn)換為該元素存儲位置的函數(shù)f稱為__哈希函數(shù)49.若要對某二叉排序樹進行遍歷，保證輸出元素的值序列按增序排列，應對該二叉排序樹采用_中序_遍歷法。50.通常用時間復雜度和__空間復雜度______兩種方法衡量算法的效率。51.在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的__2_____倍。52.在無向圖中，若從頂點A到頂點B存在_途徑______，則稱A與B之間是連通的。53.有一個n個頂點的有向完全圖的弧數(shù)__n(n-1)_______。54.對于一個具有n個頂點的圖，若采用鄰接矩陣表達，則矩陣大小為_n2_____。55.已知一棵樹的前序序列為ABCDEF，后序序列為CEDFBA，則對該樹進行層次遍歷得到的序列為____ABCDFE_______。56.若一棵完全二叉樹具有121個結(jié)點，則該樹的深度為__7_________。57.度數(shù)為0的結(jié)點，即沒有子樹的結(jié)點叫作葉子結(jié)點。同一個結(jié)點的兒子結(jié)點之間互稱為兄弟結(jié)點1.任何一棵二叉樹都有n0=n2+1的關(guān)系式。(√)2.插入與刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，因此這兩種操作在數(shù)組中也經(jīng)常被使用。（×）3.在完全二叉樹中,若某結(jié)點無左孩子,則它必是葉結(jié)點。（√）4.用樹的前序遍歷和中序遍歷可以導出樹的后序遍歷。（×）5.已知一棵二叉樹的前序序列和后序序列可以唯一地構(gòu)造出該二叉樹。（×）6.將一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點沒有左子樹。（×）7.設(shè)與一棵樹T所相應的二叉樹為BT，則與T中的葉子結(jié)點所相應的BT中的結(jié)點也一定是葉子結(jié)點。（×）8.滿二叉樹也是完全二叉樹。（√）9.哈夫曼樹一定是滿二叉樹。（×）10.樹的帶權(quán)途徑長度最小的二叉樹中必然沒有度為1的結(jié)點。（√）11.度為二的有序樹等價于二叉樹。（×）12.在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別進行中序遍歷和后序遍歷，則具有相同的結(jié)果。（√）13.算法和程序都應具有下面一些特性：輸入，輸出，擬定性，有窮性，可行性。（√）14.二叉樹是一棵無序樹。（×）15.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（×）16.廣義表的表頭和表尾既可以是單元素,也可以是廣義表。（×）17.假如兩個串中具有相同的字符，則這兩個串相等。（×）18.稀疏矩陣壓縮存儲后，必會失去隨機存取功能。（√）19.在對雙向循環(huán)鏈表做刪除一個結(jié)點操作時，應先將被刪除結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點鏈接好再執(zhí)行刪除結(jié)點操作。（√）20.只有用面向?qū)ο蟮挠嬎銠C語言才干描述數(shù)據(jù)結(jié)構(gòu)算法。（×）21.棧和隊列都是順序存取的線性表,但它們對存取位置的限制不同。（×）22.棧和隊列都是限制取點的線性結(jié)構(gòu)。（√）23.若某堆棧的輸入序列為1,2,3,4，則4,3,1,2不也許是堆棧的輸出序列之一。（√）24.數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應用需要建立的。（√）25.單鏈表形式的隊列，頭指針F指向隊列的第一個結(jié)點，尾指針R指向隊列的最后一個結(jié)點。（×）26.堆棧、隊列和數(shù)組的邏輯結(jié)構(gòu)都是線性表結(jié)構(gòu)。（×）27.鏈式棧與順序棧相比,一個明顯的優(yōu)點是通常不會出現(xiàn)棧滿的情況。（√）28.遞歸的算法簡樸、易懂、容易編寫，并且執(zhí)行效率也高。（×）29.順序表和一維數(shù)組同樣，都可以按下標隨機（或直接）訪問。（√）30.堆排序是所需輔助空間最少的排序。（√）31.在采用線性探測法解決沖突的散列表中,所有同義詞在表中一定相鄰。（×）32.對n個元素的表用堆排