數(shù)據(jù)結(jié)構(gòu)算法設(shè)計題及答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)算法設(shè)計題及答案 1、 對帶表頭結(jié)點的有序單鏈表，編寫算法向單鏈表中插入元素x，使其保持有序。答案：typedef datatype int;struct node /結(jié)點結(jié)構(gòu) datatype data; node * next; /注：也可以用自然語言描述void insertOrder(node *head, datatype x) /統(tǒng)計 node *s;p=head;while (p->next ->data<x)p=p->next;s=( node *)malloc(sizeof(node) ;s->data=x;s-

2、>next= p->next;p->next=s; 2、 對帶表頭結(jié)點的單鏈表，編寫算法求單鏈表的長度。答案：typedef datatype int;struct node /結(jié)點結(jié)構(gòu) datatype data; node * next; /注：也可以用自然語言描述int Length(node *head) / 求單鏈表的長度 int num=0;node *p=head->next;while (p)num+ ; p=p->next;return num; 3、 試寫出單鏈表的插入與刪除算法，并用C編寫相應(yīng)的程序。答案：typedef datatype i

3、nt;struct node /結(jié)點結(jié)構(gòu) datatype data; node * next; 單鏈表的插入?yún)⒖妓惴ǎ?/在包含元素x的結(jié)點前插入新元素bvoid ins_linked_LList(node * head , datatype x, datatype b) node *p, *q;p=new node ;/申請一個新結(jié)點p->d=b;/置新結(jié)點的數(shù)據(jù)域if (head=NULL)/原鏈表為空head=p; p->next=NULL; return;if (head->d=x)/在第一個結(jié)點前插入p->next=head;head=p;return; q

4、=head;while (q->next!=NULL)&&(q->next)->d)!=x)q=q->next;/尋找包含元素x的前一個結(jié)點qp->next=q->next;q->next=p;/新結(jié)點p插入到結(jié)點q之后return;單鏈表的刪除參考算法： int del_linked_LList(node * head ,T x) /刪除包含元素x的結(jié)點元素node *p, *q;if (head=NULL) return(0); /鏈表為空，無刪除的元素if (head->d)=x)/刪除第一個結(jié)點p=head->nex

5、t; delete head; head=p; return(1); q=head;while (q->next!=NULL)&&(q->next)->d)!=x)q=q->next;/尋找包含元素x的前一個結(jié)點qif (q->next=NULL)return(0); /鏈表中無刪除的元素p=q->next; q->next=p->next;/刪除q的下一個結(jié)點pdelete p;/釋放結(jié)點p的存儲空間return(1);4、 對帶表頭結(jié)點的單鏈表，編寫算法統(tǒng)計單鏈表中大于x的元素個數(shù)。答案：typedef datatype in

6、t;struct node /結(jié)點結(jié)構(gòu) datatype data; node * next; /注：也可以用自然語言描述int CountX(node *head, datatype x) /統(tǒng)計 int num=0;p=head->next;while (p)if(p->data>x) num+ ; p=p->next;return num; 5、 對帶表頭結(jié)點的單鏈表，編寫算法將單鏈表就地逆置。答案：typedef datatype int;struct node /結(jié)點結(jié)構(gòu) datatype data; node * next; /注：也可以用自然語言描述voi

7、d ReverseList(node *head) / 將單鏈表就地逆置 node *q, *p=head->next;head->next=NULL；while (p)q=p;p=p->next;q->next= head->next;head->next=q ; 6、 寫出鏈隊列的入隊、出隊的算法。 答案：typedef datatype int;struct node /結(jié)點結(jié)構(gòu) datatype data; node * next; /注：也可以用自然語言描述struct LinkQueue /結(jié)點結(jié)構(gòu) node * front; node * re

8、ar; int EnterQueue(LinkQueue *q, datatype e) /帶頭結(jié)點的鏈隊列入隊q->rear->next=( node *)malloc(sizeof(node);q->rear->data=e;q->rear= q->rear->next;return 1;int DeleteQueue(LinkQueue *q, datatype *e) /帶頭結(jié)點的鏈隊列出隊if(q->rear= q->front) return 0;p= q->front->next;*e= p->data;q-

9、>front->next=p->next;free(p);if(q->front->next=NULL)q->rear= q->front;return 1;7、 編寫算法對二叉鏈表存儲的二叉樹進行前序遍歷，并統(tǒng)計二叉樹中葉子結(jié)點數(shù)。答案：typedef datatype int;struct node /結(jié)點結(jié)構(gòu) datatype data; node * lchild, *rchild; /注：也可以用自然語言描述void preOrder(node* root) /前序遍歷 if(root=NULL) return ; / 空樹 printf(&

10、quot;%5d", root->data); preOrder (root->lchild );/ 前序遍歷根的左子樹 preOrder (root->rchild ); / 前序遍歷根的右子樹 int numOfLeaf (node* root) /統(tǒng)計二叉樹中結(jié)點總數(shù) if(root=NULL) return 0; / 空樹 if(root->lchild =NULL)&& (root->rchild =NULL) ) return 1; / 葉子 return numOfLeaf (root->lchild )+ numOf

11、Leaf (root->rchild ); /說明：算法的表達形式及方法多種多樣，不可拘泥于固法。8、 對以二叉鏈表存儲的二叉樹，編寫對二叉樹進行中序遍歷的算法，以及求二叉樹高度的算法。答案：typedef datatype int;struct node /結(jié)點結(jié)構(gòu) datatype data; node * lchild, *rchild; /注：也可以用自然語言描述void inOrder(node* root) /前序遍歷 if(root=NULL) return ; / 空樹 inOrder (root->lchild );/ 中序遍歷根的左子樹 printf("

12、;%5d", root->data); inOrder (root->rchild ); / 中序遍歷根的右子樹 int height (node* root) /求二叉樹的高度 int h1,h2 if(root=NULL) return 0; / 空樹 h1=height (root->lchild );h2= height (root->rchild );return 1+(h1>=h2)?h1:h2; /說明：算法的表達形式及方法多種多樣，不可拘泥于固法。9、 編寫對有序順序表的折半查找算法。 答案：#define MaxSize 100type

13、def struct KeyType key; OtherType otherData;datatype; struct SeqList /結(jié)點結(jié)構(gòu) datatype dataMaxSize; /0號單元不用 int len; int BinSearch(SeqList SL, KeyType k) low=1, high=SL.len;while(low<=high) mid=( low+high)/2; if(SL.datamid.key=k) return mid; /查找成功 if(SL.datamid.key<k)high= mid-1;elselow= mid+1;Return 0;/查找失敗10、 試寫一個算法，判別一行字符中的圓括號是否配對。 答案：int BracketMatch(char*str) /