【文章內(nèi)容簡介】 dge=p，并回答下列問題： (1)該算法采用何種策略進行排序? 插入排序(2)算法中R[n+1]的作用是什么? 監(jiān)視哨Typedef struct { KeyType key。 infoType otherinfo。 } nodeType。 typedef nodeType SqList［MAXLEN］。 void sort(SqList R,int n) { //n小于MAXLEN1 int k。i。 for(k=n1。k=1。k) if(R[k].keyR[k+1].key) { R[n+1]=R[k]。 for(i=k+1。R[i].keyR[n+1].key。i++) R[i1]=R[i]。 R[i1]=R[n+1]。 } } 12．設(shè)某二叉樹以二叉鏈表為存儲結(jié)構(gòu)，請寫出求其高度的遞歸算法。 答：void BTdepth (BinTree BT,int h) { int hr, h1。if(BT==null) h=0。 (1分)else { BTdepth (BT→lchild,h1)。 2分BTdepth (BT→rchild,hr)。if(h1=hr)h=h1+1。 2分else h=hr+1}}四、算法填空和分析ListInsert_L(LinkList L, int pos, ElemType e) //在帶頭結(jié)點的單鏈表L中第pos個數(shù)據(jù)元素之前插入數(shù)據(jù)元素eStatus ListInsert_L(LinkList L, int pos, ElemType e) {p = L。 j = 0。while (p amp。amp。 j pos1) { p = pnext。 ++j。 } // 尋找第pos1個結(jié)點if (!p || j pos1) return ERROR。 // pos小于1或者大于表長s = (LinkList) malloc ( sizeof (LNode))。 // 生成新結(jié)點sdata = e。 snext = pnext。 // 插入L中pnext = s。return OK。}void Merge (Elem SR[], Elem TR[], int i, int m, int n) {// 將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]for (j=m+1, k=i。 i=m amp。amp。 j=n。 ++k) { // 將SR中記錄由小到大地并入TRif (SR[i].key=SR[j].key) TR[k] = SR[i++]。else TR[k] = SR[j++]。}if (i=m) TR[k..n] = SR[i..m]。// 將剩余的SR[i..m]復(fù)制到TRif (j=n) TR[k..n] = SR[j..n]。// 將剩余的SR[j..n]復(fù)制到TR} // Mergeint Partition (Elem R[], int low, int high) {// 交換記錄子序列R[low..high]中的記錄，使樞軸記錄到位，并返回//其所在位置，此時，在它之前（后）的記錄均不大（?。┯谒黂[0] = R[low]。// 用子表的第一個記錄作樞軸記錄pivotkey = R[low].key。 // 樞軸記錄關(guān)鍵字while (lowhigh) {// 從表的兩端交替地向中間掃描while(lowhighamp。amp。 R[high].key=pivotkey)high。R[low] = R[high]。// 將比樞軸記錄小的記錄移到低端while (lowhigh amp。amp。 R[low].key=pivotkey) ++low。R[high] = R[low]。// 將比樞軸記錄大的記錄移到高端}R[low] = R[0]。 // 樞軸記錄到位return low。 // 返回樞軸位置} // Partition折半查找算法：int binsrch(JD r[],int n,int k){ int low,high,mid,found。 low=1。 high=n。 found=0。 while((low=high)amp。amp。(found==0)) { mid=(low+high)/2。 if(kr[mid].key) low=mid+1。 else if(k==r[mid].key) found=1。 else high=mid1。 } if(found==1) return(mid)。 else return(0)。}設(shè)有一個表頭為head的單鏈表。通過遍歷一趟鏈表，將鏈表中所有結(jié)點按逆序鏈接。Typedef struct node{int data。 struct node *next。}pointer。Void invert(pointer head){p=NULL。while (head!=NULL){u=head。 head=headnext。unext= p 。p=u。}had=p。}五、編寫算法：設(shè)某單鏈表L的結(jié)點結(jié)構(gòu)如下，單鏈表L用于存放某人的電話薄，現(xiàn)在由于電話號碼從7位升為8位（加60000000），請用C語言編寫算法，實現(xiàn)電話薄中所有電話號碼從7位升為8位。Typedef struct node{ char name[9]。//姓名long data。//電話號碼 struct node *next。}pointer。int length(pointer L){ p=L。 while(p!=NULL) { pdata= pdata+60000000。p=pnext。}}設(shè)二叉樹采用二叉鏈表表示，編寫算法，將二叉樹中所有結(jié)點的左右子樹相互交換。void Bitree_Revolute(Bitree T)//交換所有結(jié)點的左右子樹{TlchildTrchild。 //交換左右子樹if(Tlchild) Bitree_Revolute(Tlchild)。if(Trchild) Bitree_Revolute(Trchild)。 //左右子樹再分別交換各自的左右子樹} 設(shè)計題：1． 設(shè)某單鏈表L的結(jié)點結(jié)構(gòu)為data,next,試畫出該鏈表的結(jié)構(gòu)圖，并用類C語言編寫算法，判斷該鏈表的元素是否是遞增的。2． 設(shè)某單鏈表L的結(jié)點結(jié)構(gòu)為data,next,試畫出該鏈表的結(jié)構(gòu)圖，并用類C語言編寫算法，統(tǒng)計該鏈表的長度。3． 設(shè)一棵二叉樹以二叉鏈表作為存儲結(jié)構(gòu)，結(jié)點結(jié)構(gòu)為lch,data,rch，其中data域中存放一個字符，設(shè)計一個算法按前根遍歷順序打印出data域為數(shù)字的字符。4． 設(shè)BT為二叉排序樹，t指向根結(jié)點，每個結(jié)點的結(jié)構(gòu)為lch,key,rch，試用類C語言寫出算法，用來輸出二叉排序樹中最小的鍵值。5． 設(shè)一棵二叉樹以二叉鏈表為存儲結(jié)構(gòu)，結(jié)點結(jié)構(gòu)為lch,data,rch，設(shè)計一個算法求此二叉樹上度為2的結(jié)點數(shù)。6． 設(shè)一個環(huán)上有若干個整數(shù)，若采用單循環(huán)鏈表L存儲該環(huán)，L的存儲結(jié)構(gòu)為：data,next，試畫出鏈表L的結(jié)構(gòu)圖，并編寫算法判斷環(huán)上任意兩個相鄰的鍵值之差的絕對值是否不超過2。： typedef struct node { DataType data。 struct node *lchild,*rchild。 }PBinTree。 其中，結(jié)點的lchild域和rchild域已分別填有指向其左、右孩子結(jié)點的指針。請編寫一個遞歸算法，將該存儲結(jié)構(gòu)中各結(jié)點的lchild和rchild域的值進行交換。 2001年10月數(shù)據(jù)結(jié)構(gòu)試題及答案一、 單項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內(nèi)。1．算法指的是（ ） A．計算機程序 B．解決問題的計算方法 C．排序算法 D．解決問題的有限運算序列2．線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址（ ） A．必須是不連續(xù)的 B．連續(xù)與否均可 C．必須是連續(xù)的 D．和頭結(jié)點的存儲地址相連續(xù)3．將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復(fù)雜度為（ ） A．O（1） B．O（n） C．O（m） D．O（m+n）4．由兩個棧共享一個向量空間的好處是：（ ） A．減少存取時間，降低下溢發(fā)生的機率 B．節(jié)省存儲空間，降低上溢發(fā)生的機率 C．減少存取時間，降低上溢發(fā)生的機率 D．節(jié)省存儲空間，降低下溢發(fā)生的機率5．設(shè)數(shù)組data[m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（ ） A．front=front+1 B．front=(front+1)%(m1) C．front=(front1)%m D．front=(front+1)%m6．如下陳述中正確的是（ ） A．串是一種特殊的線性表 B．串的長度必須大于零 C．串中元素只能是字母 D．空串就是空白串7．若目標(biāo)串的長度為n，模式串的長度為[n/3]，則執(zhí)行模式匹配算法時，在最壞情況下的時間復(fù)雜度是（ ） A．O（ ） B．O（n） C．O（n2） D．O（n3）8．一個非空廣義表的表頭（ ） A．不可能是子表 B．只能是子表 C．只能是原子 D．可以是子表或原子9．假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表0 2 3 3 5 對應(yīng)的稀疏矩陣是（ ） 10．在一棵度為3的樹中,度為3的結(jié)點個數(shù)為2,度為2 的結(jié)點個數(shù)為1,則度為0的結(jié)點個數(shù)為( ) A．4 B．5 C．6 D．711．在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為( ) A．e B．2e C．n2－e D．n2－2e12．假設(shè)一個有n個頂點和e條弧的有向圖用鄰接表表示,則刪除與某個頂點vi相關(guān)的所有弧的時間復(fù)雜度是( ) A．O(n) B．O(e) C．O(n+e) D．O(n*e)13．用某種排序方法對關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進行排序時，序列的變化情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采用的排序方法是（ ） A．選擇排序 B．希爾排序 C．歸并排序 D．快速排序14．適于對動態(tài)查找表進行高效率查找的組織結(jié)構(gòu)是（ ）A．有序表 B．分塊有序表 C．三叉排序樹 D．線性鏈表15．不定長文件是指（ ）A．文件的長度不固定 B．記錄的長度不固定C．字段的長度不固定 D．關(guān)鍵字項的長度不固定第二部分 非選擇題（共70分）二、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯填或不填均無分。16．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的 無關(guān)，是獨立于計算機的。17．在一個帶頭結(jié)點的單循環(huán)鏈表中，p指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針head可用p表示為head= 。18．棧頂?shù)奈恢檬请S著 操作而變化的。19．在串S=“structure”中，以t為首字符的子串有 個。20．假設(shè)一個9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在一維數(shù)組B中，其中Bamp。0。存儲矩陣中第1個元素a1,1,則B中存放的元素是 。21．已知一棵完全二叉樹中共有768結(jié)點，則該樹中共有 個葉子結(jié)點。 22．已知一個圖的廣度優(yōu)先生成樹如右圖所示，則與此相