【正文】 :=i+1。 s:=s+10*i。 }while ((In) amp。amp。 (sn)) （968） 根據(jù)下面程序，回答下面問(wèn)題： (1) 試指出f(n)值的大小，并寫(xiě)出f(n) 值的推導(dǎo)過(guò)程。 (2) 假定n= 5，試指出f(5)值的大小和執(zhí)行f(5)時(shí)的輸出結(jié)果。 int f(int n) { int i, j, k, sum= 0。 for(i=l。 in+1。 i++) { for(j=n。 ji1。 j) { for(k=1。 kj+1。 k++ ) { sum++。 printf(sum=%d\n, sum)； } } } return (sum)。 } （969） 設(shè)n是偶數(shù)，試計(jì)算運(yùn)行下列程序段后m的值并給出該程序段的時(shí)間復(fù)雜度。 int m = 0。 For (int i = 0。 i n。 i++) { for (int j = 2*i, j n。 j++) { m = m + 1。 } } （970） 試給出下面兩個(gè)算法的運(yùn)算時(shí)間。 a. for (int I = 0。 I n。 I++) { x++。 } b. for (int I = 1。 I n。 I++) { for (int j = 1。 j n。 j++) { x++。 } } （971） 快速排序的最大遞歸深度是多少？最小遞歸深度是多少？ （972） 對(duì)鏈表設(shè)置表頭節(jié)點(diǎn)的作用是什么？ （973） 有五個(gè)數(shù)依次進(jìn)棧：1,2,3,4,，以3,4先出的序列有哪幾個(gè)。（３在４之前出棧） （974） 試寫(xiě)出進(jìn)棧操作，出棧操作算法的時(shí)間復(fù)雜性。 （975） 已知ＫＭＰ串匹配算法的模式串是AABBAAB,試寫(xiě)出改進(jìn)后的NEXT信息幀。 （976） 某整型數(shù)組Ａ的１０個(gè)元素值依次為6,2,9,7,3,8,4,5,0,1,用下列各排序方法，將Ａ中元素由小到大排序。 (1) 取第一個(gè)元素值６作為分割數(shù)，(2) 試寫(xiě)出快速排序第一次分隔后Ａ中的結(jié)果。 (3) 用堆排序，(4) 試寫(xiě)出將第一個(gè)選出的數(shù)據(jù)放在Ａ的最后位置上，(5) 將Ａ調(diào)整成堆后的Ａ中結(jié)果。 (6) 用基數(shù)為３的基數(shù)排序法，(7) 試寫(xiě)出第一次分配和收集后Ａ中的結(jié)果。 （977） 已知某排序平衡二叉樹(shù)Ｔ具有下列特點(diǎn)： (1) 結(jié)點(diǎn)的關(guān)鍵字均在1到9范圍內(nèi)； (2) 在Ｔ中存在一個(gè)關(guān)鍵字為n1的葉結(jié)點(diǎn)，若刪去該結(jié)點(diǎn)，立即插入一個(gè)關(guān)鍵字為n1的結(jié)點(diǎn)，得到的平衡樹(shù)與原Ｔ不相同； (３) 在Ｔ中存在另一個(gè)關(guān)鍵字為n2的非葉結(jié)點(diǎn)，刪去它，并立即插入n2結(jié)點(diǎn)，得到與原Ｔ相同的平衡樹(shù)； (４) 在Ｔ中插入某n3結(jié)點(diǎn)后立即刪除它，得到的平衡樹(shù)與原Ｔ不相同。 試畫(huà)出具有上述特點(diǎn)的最簡(jiǎn)單（結(jié)點(diǎn)個(gè)數(shù)最少）的平衡樹(shù)Ｔ，并寫(xiě)明n1,n2,n3分別等于幾？ （978） 設(shè)一單向鏈表的頭指針為head，鏈表的記錄中包含著整數(shù)類(lèi)型的key域,試設(shè)計(jì)算法，將此鏈表的記錄按照key遞增的次序進(jìn)行就地排序。 （979） 在排序連續(xù)順序文件中采用折半查找方法查找記錄存在與否的過(guò)程可以借助于一棵平衡二叉樹(shù)(也稱(chēng)判定樹(shù))來(lái)模擬，樹(shù)中結(jié)點(diǎn)的值為記錄在文件中的位置序號(hào)。 (1) 若文件中有l(wèi) 9個(gè)記錄，請(qǐng)畫(huà)出這棵判定樹(shù)； (2) 當(dāng)文件中有n個(gè)記錄時(shí)，求出該判定樹(shù)的深度。 （980） 試舉例說(shuō)明用程序設(shè)計(jì)語(yǔ)言描述堆棧結(jié)構(gòu)時(shí)，要涉及那些問(wèn)題？ （981） 在程序設(shè)計(jì)語(yǔ)言中實(shí)現(xiàn)遞歸的條件是什么？編寫(xiě)遞歸子程序，應(yīng)注意什么？ （982） 動(dòng)態(tài)查找樹(shù)，有哪幾項(xiàng)基本操作？ （983） 舉例說(shuō)明有向圖的最短路徑算法常用于哪幾種情形？ (1) 中斷和死鎖 (2) 變量與表達(dá)式 (3) 對(duì)象與屬性 (4) 虛擬地址與實(shí)地址 (5) 數(shù)據(jù)的物理結(jié)構(gòu)和邏輯結(jié)構(gòu) （984） 內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m），提供給兩個(gè)棧S1和S2使用，怎樣分配這部分存儲(chǔ)空間，使得對(duì)任一個(gè)棧，僅當(dāng)這部分空間全滿時(shí)才發(fā)生上溢。 （985） 一棵共有n個(gè)結(jié)點(diǎn)的樹(shù)，其中所有分枝結(jié)點(diǎn)的度均為k，求該樹(shù)中葉子結(jié)點(diǎn)的子數(shù)。 （986） 設(shè)有一個(gè)由正整數(shù)組成的無(wú)序（向后）單鏈表，編寫(xiě)完成下列功能的算法： (1) 找出最小值結(jié)點(diǎn)，且打印該數(shù)值； (2) 若該數(shù)值是奇數(shù)，則將其與直接后繼結(jié)點(diǎn)的數(shù)值交換； (3) 若該數(shù)值是偶數(shù)，則將其直接后繼結(jié)點(diǎn)刪除； （987） 給出下算法的時(shí)間復(fù)雜度： main( ) { int x , n , y 。 scanf(%d, amp。n)。 x=n。 y=0。 while (x = (y+1)(y+1)) { y++。 } } （988） 試舉例說(shuō)明對(duì)相同的邏輯結(jié)構(gòu)，同一種運(yùn)算在不同的存儲(chǔ)方式下實(shí)現(xiàn)，其運(yùn)算效率不同。 （989） 對(duì)鏈表設(shè)置表頭結(jié)點(diǎn)的作用是什么？（至少說(shuō)出2條好處） （990） 快速排序在什么情況下排序算法產(chǎn)生惡化，原因是什么？ （991） 設(shè)在一個(gè)有關(guān)串的程序編碼當(dāng)中，有如下定義與賦值： const char A[] = {39。a39。,39。b39。,39。c39。,39。\039。}。 char B[] = {39。a39。,39。b39。,39。c39。,39。d39。,39。\039。}。 … … for (i=0。 i4。 i++) { A[i] = 39。a39。 B[i] = 39。b39。 } … ... 在該程序編碼中是否有錯(cuò)？為什么？ （992） 若A為一下三角矩陣數(shù)組，則采用以行為主和以列為主的數(shù)據(jù)存放方式哪一種更合適？為什么？ （993） 線性表A和B均是按元素值遞增有序排列，均以單鏈表作存儲(chǔ)結(jié)構(gòu)。請(qǐng)編寫(xiě)一算法將表A和表B歸并成一個(gè)按元素值遞減有序排列的線性表C（允許表中含有值相同的元素），并要求利用原表空間。 （994） 編寫(xiě)一個(gè)算法，對(duì)于輸入的十進(jìn)制非負(fù)整數(shù)，將它的八進(jìn)制表示打印出來(lái)。 （995） 編寫(xiě)函數(shù)strcmp(char * s1, char * s2)。若s1和s2均是數(shù)字串（包括+/號(hào)），則按照十進(jìn)制整數(shù)大小進(jìn)行比較；否則按照Ascii序進(jìn)行比較。s1大于/等于/小于s2時(shí)，分別輸出1/0/1?？梢灾苯诱{(diào)用atoi函數(shù)。 （996） 請(qǐng)回答下列關(guān)于堆（Heap）的一些問(wèn)題： (1) 堆的存儲(chǔ)表示是順序的，還是鏈接的？ (2) 設(shè)有一個(gè)最小堆，即堆中任意節(jié)點(diǎn)的關(guān)鍵碼均大于它的左子女和右子女的關(guān)鍵碼。其具有最大值的元素可能在什么地方？ (3) 對(duì)n個(gè)元素進(jìn)行初始建堆的過(guò)程中，最多做多少次數(shù)據(jù)比較（不用大O表示法）？ （997） 快速排序的時(shí)間復(fù)雜度是多少？試推導(dǎo)之。 （998） 從鍵盤(pán)上輸入一串正整數(shù)，以1為輸入結(jié)束的標(biāo)志，試設(shè)計(jì)一個(gè)算法，生成一棵二叉排序樹(shù)（即依次把該序列中的結(jié)點(diǎn)插入二叉排序樹(shù)）。 （999） 試設(shè)計(jì)一個(gè)算法，在中序線索二叉樹(shù)中求指定結(jié)點(diǎn)P在后序遍歷序列中的前驅(qū)結(jié)點(diǎn)。要求算法為非遞歸的，空間復(fù)雜度為O（1）。 （1000） 修改冒泡排序法以實(shí)現(xiàn)雙向冒泡排序。即第一次把最大記錄放到表尾，第二次將最小記錄放到表頭，如此反復(fù)進(jìn)行，直至排序結(jié)束。試編寫(xiě)此算法。 （1001） 針對(duì)以下情況確定非遞歸的歸并排序的運(yùn)行時(shí)間(數(shù)據(jù)比較次數(shù)與移動(dòng)次數(shù)): (1) 輸入的n個(gè)數(shù)據(jù)全部有序。 (2) 輸入的n個(gè)數(shù)據(jù)全部逆向有序。 (3) 隨機(jī)地輸入n個(gè)數(shù)據(jù). （1002） 說(shuō)明下列算法的功能： void a1(stack amp。s) { int i, n, a[255]。 n = 0。 while (!stackempty(s)) { n++。 pos(s, a[n]。 } for (i = 1。 i = n。 i++) { push(s, a[i])。 } } （1003） 說(shuō)明下列算法的功能： void a2(stak amp。s, int e) { stack t。 int d。 initstack(t)。 while (!stackempty(s)) { pop(s, d)。 if (d!= e) push(t, d)。 } while (!stackempty(t)) { pop(t,d)。 push(s,d)。 } } （1004） 說(shuō)明下列算法的功能： void change(linklist amp。head) { linklist q, p。 if (head amp。amp。 headnext) { q = head。 head = headnext。 p = head。 while (pnext) p = pnext。 pnext = q。 qnext = NULL。 }