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

1、線性結(jié)構(gòu)中元素之間存在著（一對一）關(guān)系，樹型結(jié)構(gòu)中元素之間存在著（一 對多）關(guān)系。評價數(shù)據(jù)結(jié)構(gòu)的兩條基本標(biāo)準(zhǔn)是：（存儲需要量）和（運算的時間效率）。算法的五個特性是指（有窮性/確定性、可行性、輸入和輸出）。數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的（存儲結(jié)構(gòu)）無關(guān)， 是獨立于計算機的。數(shù)據(jù)的邏輯結(jié)構(gòu)包括（線性結(jié)構(gòu)）和非線性結(jié)構(gòu)。針對線性鏈表的基本操作有很多，但其中最基本的4種操作分別為（插入）、 刪除、查找和排序。對于長度為n的順序存儲的線性表，當(dāng)隨機插入和刪除一個元素時，需平均 移動元素的個數(shù)為（n/2）。在單鏈表中設(shè)置頭結(jié)點的作用是（簡化插入、刪除算法）。訪問單鏈表中的結(jié)點，必須沿著

2、（指針域或next域）依次進行。在雙向鏈表中，每個結(jié)點有兩個指針域，一個指向（前驅(qū)結(jié)點），另一個指 向（后繼結(jié)點）。在一個帶頭結(jié)點的單循環(huán)鏈表中，P指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點 的指針 head 可用 p 表示為 head=（ p-next-next）。設(shè)單鏈表中指針P指向結(jié)點m，若要刪除m之后的結(jié)點（若存在），則需修改 指針的語句是：（p-next=p-next-next）。已知廣義表 A=（a,（b,（c,d），則表尾是（b,（c,d），深度為（3）。 廣義表 A（a，b，c），（d，e，f）的表頭為（a,b,c），長度為（2）。將一個n階三對角矩陣A的三條對角線上的元素按行壓縮存放

3、于一個一維數(shù) 組B中，A00存放于B0中。對于任意給定數(shù)組元素AIJ，如果它能夠 在數(shù)組B中找到，則它應(yīng)在（2*I+J位）置。存儲稀疏矩陣的方法是多種多樣的，其中的四種方法有（三元組表示法），（偽 地址表示法），（帶輔助行向量的二元組表示法），（行-列表示法）三元組表示法，每個結(jié)點包括3個字段，分別為該非零元素的（行下標(biāo)）（列 下標(biāo)）和（值）。在串S= stud”中，子串有（11）個。 設(shè) s1=” study”，s2=” hard”，則調(diào)用函數(shù) strcat（s1, s2）后得到（study hard ）o設(shè)有兩個串p和q，求q在p中首次出現(xiàn)位置的運算稱做（模式匹配） 設(shè)有一個順序棧S，元素

4、sl，s2，s3， s4， s5，s6依次進棧，如果6個 元素的出棧順序為s2, s3, s4, s6, s5, sl，則順序棧的容量至少應(yīng)為（3）。棧的特點是：（后進先出），棧頂?shù)奈恢檬请S著進棧和出棧一操作而變化的。若有一個棧的輸入序列為1,2,3, .,n,輸出序列的第一個元素為n,則第i 個輸出元素是（n-i+1 ）。通常程序在調(diào)用另一個程序時，都需要使用一個（棧）來保存被調(diào)用程序內(nèi) 分配的局部變量、形式參數(shù)的存儲空間以及返回地址。通常元素進棧的順序是（先移動棧頂指針，然后存入元素）。通常元素出棧的順序是（先取出棧頂元素，然后移動棧頂指針）。隊列的特點是：（先進先出），其插入操作在（隊尾

5、）進行，刪除操作在（對 頭）進行。有數(shù)據(jù)元素1、2、3,依次進隊列，其出隊列序列為（123）。從一個循環(huán)隊列中刪除一個元素，通常的操作是（先取出元素，然后移動隊 頭指針）。向一個循環(huán)隊列中插入一個元素，通常的操作是（先存放元素，然后移動隊 尾指針）。在一棵二叉樹上第8層的結(jié)點數(shù)最多是（128）在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為（16）。在深度為5的滿二叉樹中，共有（31）個結(jié)點。設(shè)一棵完全二叉樹共有699個結(jié)點，則在該二叉樹中的葉子結(jié)點數(shù)為（350）。深度為k的完全二叉樹至少有（）個結(jié)點，至多有（）個結(jié)點，若按自上而 下，從左到右的次序編號（從1開始），則編號最小的葉子結(jié)點的編號是（）。

6、設(shè)二叉樹根結(jié)點的層次為O，對含有100個結(jié)點的二叉樹，可能的最大樹 深和最小樹深分別是（）。深度為n的二叉樹最多有（2N次方-1）個結(jié)點。設(shè)二叉樹的根為第一層，則第i層上的結(jié)點數(shù)最多有（2i）。在一棵二叉樹中，度為2的結(jié)點的個數(shù)是5，則葉結(jié)點的個數(shù)為（6）。n個結(jié)點的完全二叉樹，其深度h=（ log2n+1）。在一棵二叉樹中，度為2的結(jié)點個數(shù)為8,則葉結(jié)點個數(shù)為（9）。已知一顆完全二叉樹中共有767結(jié)點，則該樹中共有（384）個葉子結(jié)點。43.200個結(jié)點的完全二叉樹，其深度h=（8）。對有n個結(jié)點的完全二叉樹，編號為i（i 1）結(jié)點的雙親結(jié)點的編號為（）， 當(dāng)i%2=0時，該結(jié)點是其雙親的（

7、）。 顆有6個結(jié)點的完全二叉樹，其結(jié)點按編號存放數(shù)據(jù)為：A、B、C、D、E、F，若按中根遍歷該樹得到的數(shù)據(jù)序列為：（DBEAFC）。現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有（5）種不同形態(tài)的二叉樹可以 得到這一遍歷結(jié)果。若按（中序）遍歷二叉排序樹可得到一個關(guān)鍵字的有序序列。樹是結(jié)點的集合，它的根結(jié)點數(shù)目是（1）。若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是 dgbaechf，則其后序遍歷的結(jié)點訪問順序是（gdbehfca）。設(shè)樹T的度為4，其中度為1、2、3和4的結(jié)點的個數(shù)分別為4、2、1、1，則T中葉子結(jié)點的個數(shù)為（8）。樹和二叉樹的3個主要差別（樹的結(jié)點個數(shù)至少為1，

8、而二叉樹的結(jié)點個數(shù) 可以為0）；樹中的最大度數(shù)沒有限制，而二叉樹結(jié)點的最大度數(shù)為2 ；樹的結(jié) 點無左右之分，而二叉樹的結(jié)點有左右之分。從概念上說，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，通過某種算法將樹轉(zhuǎn)化成 二叉樹的基本目的是（樹可采用二叉樹的存儲結(jié)構(gòu)并利用二叉樹的已有的算法 解決樹的有關(guān)問題）。假定一棵樹的廣義表表示為A（B（E（K，L），C（G），D（H（M）,I,J）,則該 樹的度為（3），樹的深度為（3）。554.在一棵樹中，有且僅有一個結(jié)點沒有前驅(qū)，稱為（根）結(jié)點;非根結(jié)點有且 僅有一個（雙親）。n個頂點的無向完全圖具有（n（n-1）/2 ）條邊，n個頂點的有向完全圖具有 （n（n-1）條

9、弧。n個頂點的連通圖的生成樹具有（n-1）條邊。對長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為（n）行二分法查找，最大的比較次數(shù)是（log2n+1）。設(shè)線性表（al , a2，a500）元素的值由小到大排列，對一個給定的 k值用二分法查找線性表，在查找不成功的情況下至多需比較（9）次。二分法查找的存儲結(jié)構(gòu)僅限于（順序存儲結(jié)構(gòu)），且是有序的。61順序查找的平均查找長度為（0（n）折半查找只適用于 有序 表，且限 于順序存儲結(jié)構(gòu)，其平均查找長度為：（0（log2n）。設(shè)有100個元素，用折半查找時，最大比較次數(shù)是（7）。在有序表（12, 24，36, 48, 60，72, 84）中

10、二分查找關(guān)鍵字72時所需進 行的關(guān)鍵字比較次數(shù)為（2）。希爾排序法屬于（插入）排序。在對一組記錄（54 , 38 , 99 , 23，15，72 , 60 , 45 , 83）進行直接 插入排序時，當(dāng)把第7個記錄60插入到有序表時，為尋找插入位置需比較（3） 次。每次從無序子表中取出一個元素，然后把它插入到有序子表中的適當(dāng)位置， 此種排序方法叫做（插入）排序，每次從無序子表中挑選出一個最小或最大元 素，把它交換到有序表的一端，此種方法叫做（選擇）排序。在對一組記錄（10, 50, 25, 70, 35, 22, 30, 85, 40）進行直接插入排序時，當(dāng)把 第6個記錄22插入到有序表時，為尋找插入位置需比較（2）次。堆排序法屬于（選擇）排序。對一組記錄（50, 40, 95, 20, 15, 70, 60, 45, 80）進行簡單選擇排序時，第4次交換和選擇后，未排序記錄（即無序數(shù)）為（50, 70, 60, 95, 80）。假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要的比較次數(shù)為（n（n-1）/2）。對n個元素的序列進行冒泡排序時，最少的比較次數(shù)是（n-1）。（快速堆）排序方法采用的是二分法的思想，其數(shù)據(jù)的組