考研資料數(shù)據(jù)結(jié)構(gòu)試卷

得分1、填空題。(每小題2分，本題滿(mǎn)分20分)假設(shè)用一個(gè)一維數(shù)組B來(lái)按行存放一個(gè)對(duì)稱(chēng)矩陣A的下三角部份，那末訪問(wèn)A的第i行第j列元素的語(yǔ)句是：。(下標(biāo)都從0開(kāi)始)在單鏈表指針P所指結(jié)點(diǎn)后插入指針為s的結(jié)點(diǎn)操作是：-⑶線性表L=(ao,ai,a2,...az)用數(shù)組表示，假設(shè)刪除表中任一元素的概率相同，則刪除一個(gè)元素所需的平均挪移次數(shù)為。(4)在指針L指向一帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，則判斷該表中惟獨(dú)一個(gè)元素結(jié)點(diǎn)的條件是：------------(設(shè)結(jié)點(diǎn)結(jié)構(gòu)為iLinkdatarLink)(5)使用鄰接矩陣表示圖時(shí)，遍歷一個(gè)頂點(diǎn)的所有相鄰頂點(diǎn)的時(shí)間復(fù)雜度是:o(假設(shè)圖的頂點(diǎn)個(gè)數(shù)為n,邊的個(gè)數(shù)為e)⑹已知帶權(quán)有向圖如下，使用Dijkstra算法求解從頂點(diǎn)1到達(dá)各頂點(diǎn)的最短距離時(shí)，該算法將按照(列出頂點(diǎn)順序)的順序給出各個(gè)頂點(diǎn)的距離。假設(shè)一組關(guān)鍵碼為(20,41,22,17,19,56,35),則用堆排序的方法建立的初始最大堆為oKMP模式匹配算法的時(shí)間復(fù)雜度是：。設(shè)循環(huán)隊(duì)列存放在數(shù)組A[0..m-l]中，若用犧牲一個(gè)單元的辦法區(qū)分隊(duì)列滿(mǎn)和隊(duì)列空(設(shè)隊(duì)尾指針為rear,隊(duì)頭指針為first),則判斷隊(duì)滿(mǎn)的條件是：對(duì)n個(gè)元素進(jìn)行排序，如果用直接選擇排序，所需的關(guān)鍵碼比較次數(shù)至少為,如果用直接插入排序，則所需的關(guān)鍵碼比較次數(shù)至少為 O得分、選擇題。(每小題2分，本題滿(mǎn)分20分)_____假設(shè)使用轉(zhuǎn)換后的二叉樹(shù)來(lái)表示森林，那末對(duì)該二叉樹(shù)的前序遍歷對(duì)應(yīng)于對(duì)森林的____遍歷。先根次序遍歷B后根次序遍歷C廣度優(yōu)先遍歷D以上都不是假設(shè)我們將一個(gè)表達(dá)式表示為一棵二叉樹(shù)。比如a+b*c對(duì)應(yīng)的樹(shù)的根為+,其左子樹(shù)是一個(gè)葉子結(jié)點(diǎn)a,右子樹(shù)的根為*,擺布子結(jié)點(diǎn)分別為b和c。顯然每一個(gè)內(nèi)部結(jié)點(diǎn)代表了一個(gè)運(yùn)算。假設(shè)一個(gè)并行CPU有不少個(gè)ALU可以同時(shí)執(zhí)行計(jì)算任務(wù)，且完成所有計(jì)算需要的時(shí)間都是一個(gè)時(shí)間單位。那末完成一個(gè)表達(dá)式計(jì)算的最短期是-A樹(shù)的高度 B樹(shù)的寬度 C樹(shù)的內(nèi)部結(jié)點(diǎn)個(gè)數(shù) D樹(shù)的分支數(shù)假設(shè)在快速排序算法中總是選擇被排序子序列的最后一個(gè)元素作為基準(zhǔn)。那末這個(gè)算法的最壞情況浮現(xiàn)在_______被排序的初始序列已經(jīng)排好序時(shí)被排序的初始序列是逆序時(shí)被排序的初始序列呈現(xiàn)中間大，并逐次向兩邊減小的情況以上都不是散列方法中，線性探查法的“堆積”問(wèn)題是指。A不同探查序列的關(guān)鍵碼占領(lǐng)了可利用的空桶，使得尋覓某一關(guān)鍵碼需要經(jīng)歷很長(zhǎng)的 探查序列。不同探查序列的關(guān)鍵碼占領(lǐng)了可利用的空桶，使得插入某個(gè)關(guān)鍵碼時(shí)找不到空桶。不同探查序列的關(guān)鍵碼占領(lǐng)了可利用的空桶，導(dǎo)致尋覓某個(gè)關(guān)鍵碼時(shí)浮現(xiàn)錯(cuò)誤。D不同探查序列的關(guān)鍵碼占領(lǐng)了可利用的空桶，為了保證算法能夠?qū)ひ挼秸_的關(guān)鍵 碼，不得不將裝載因子限制在某個(gè)閥值之下。如果其rTagB為0,如果其0,rTagCD如果其rTag為1,如果其則后

在中序線索二叉樹(shù)(使用ITag,rTag)中，一個(gè)結(jié)點(diǎn)的中序后繼是。(多選)則后繼是其rightChild所指結(jié)點(diǎn)的最左后代;則后繼是其rightChild所指結(jié)點(diǎn)；則后繼是其rightChild所指結(jié)點(diǎn)的最左后代;繼是其rightChild所指結(jié)點(diǎn)。假設(shè)有一棵二叉樹(shù)的結(jié)點(diǎn)前序羅列是1、2、3、4、5。下面的—序列不可能是這棵二A3、2、 1、4、5B2、3、 1、4、5C2、1、 4、5、3D2、 5、叉樹(shù)的中序羅列。⑺有11個(gè)結(jié)點(diǎn)的AVL樹(shù)的最大高度為。(假設(shè)葉結(jié)點(diǎn)的高度為1,樹(shù)的高度為根結(jié)點(diǎn)的高度)A3 B4 C5 D6下面的排序算法中，時(shí)間復(fù)雜度不是O(nlog2n)的算法是。(多選)A折半插入排序 B堆排序 C快速排序 D基數(shù)排序使用Prim算法求解最小生成樹(shù)時(shí)，使得算法效率較高的圖的表示方式是。A鄰接矩陣表示 B鄰接表表示 C以上表示方法都一樣____________________________________________________在B樹(shù)的刪除操作中，最壞情況下可能需要讀寫(xiě)磁盤(pán)___________________________________次。(假設(shè)內(nèi)存工作區(qū)足夠大，但操作之前各個(gè)結(jié)點(diǎn)都存放在磁盤(pán)上，B樹(shù)的高度為h)A2h-2 B2h-l C3h-1 D3h-2次得分 3、解答題。(每小題5分，本題滿(mǎn)分20分)(1) 使用一個(gè)32位整數(shù)以位向量集合的方式來(lái)表示0到31之間的整數(shù)的子集。請(qǐng)寫(xiě)出打印集合 s中所有元素的代碼。(2)假設(shè)一棵二叉樹(shù) T的中序遍歷序列和層次遍歷(按層次遞增順序羅列，同一層次自左向 右)序列分別是ABCDGEF和CAEBDFG。請(qǐng)寫(xiě)出該二叉樹(shù)的后序遍歷序列。已知圖的鄰接矩陣為:VIV2V3V4V5V6VI011000V2001100V3000010V4001001V5000000V6000010請(qǐng)寫(xiě)出全部拓?fù)渑判蛐蛄?。?duì)圖3-1所示的AOE網(wǎng)絡(luò)，求出每一個(gè)活動(dòng)的最早開(kāi)始時(shí)間e()和最遲開(kāi)始時(shí)間1(),并確哪些活動(dòng)是關(guān)鍵活動(dòng)。3-1CList<TyInverse()(CListNode<Type>*p,*q,*r;(first->link==first)p=first->link;q=p->link;p->link=first;r=q->link;q->link=p;p=q;q=r;1)請(qǐng)?jiān)谒惴ǖ臋M線上填入適當(dāng)?shù)恼Z(yǔ)句，每處只填一個(gè)語(yǔ)句或者一個(gè)表達(dá)式；(6分)2)請(qǐng)用大表示法表示算法的時(shí)間復(fù)雜度和空間復(fù)雜度，假設(shè)鏈表長(zhǎng)度為n。(4分)得分sortA[],n)(i=1;i<n-i+l)(min=max=i;(j=i+l；j<=n-i+l;++j)(A[j]<A[min])min=j;(A[j]>A[max])max=j;}(min!=i)Swap(A[min],A[j]);//Swap。函數(shù)的功能是交換兩個(gè)數(shù)(max!=n-i+l)(max==i)Swap(A[min],A[n-i+l]);Swap(A[max],A[n-i+l]);}i++；(1)閱讀此算法，說(shuō)明此算法的基本思想。(2分)2)對(duì)于下面給出的整數(shù)數(shù)組，請(qǐng)寫(xiě)出前4趟結(jié)束時(shí)數(shù)組中數(shù)據(jù)的變化。(每行僅寫(xiě)出一個(gè)循環(huán)的變化)(4分)步A[0]A[l]A⑵A[3]A[4]A[5]A[6]A[7]A[8]34238926345181024112343)請(qǐng)寫(xiě)出此排序算法最好情況下數(shù)據(jù)的挪移次數(shù)。(2分)4)請(qǐng)用大表示法表示算法的時(shí)間復(fù)雜度。(2分)得分 。(每小題 10分，本題滿(mǎn)分 20分)(1)二叉樹(shù)T以二叉鏈表的形式存儲(chǔ)，設(shè)計(jì)算法返回二叉樹(shù)T的先序序列的最后一個(gè)結(jié)