数据结构复习参考(4)

06计算机——数据结构期末复习试卷

{ p->link=q->link; delete q; q=p->link; find=true; }

else {cout<data;p=q;q=q->link;} }

if(!find) cout<<”找不到”; }

4. 已知两个非递减的单链表A和B，试写一个算法函数实现将单链表B合并到A中，使A仍然保持非递减。 struct LNode /*线性表的单链表存储结构*/ {

ElemType data; struct LNode *next; };

typedef struct LNode *LinkList;

答：void MergeList(LinkList A,LinkList B)

{ /* 已知单链表A和B中的数据元素按值非递减排列。*/ /* 合并两表到A中，使A的数据元素仍然按值非递减排列*/ LinkList pa,qa,pb,qb; qa=A;

pa=A; qb=B; pb=B;

//初始化

while(pa&&pb) { qb=pb;

pb=pb->next; qa->next=qb; qb->next=pa; qa=qb;

} else { qa=pa; pa=pa->next; } }

if(pb) qa->next=pb; ｝

5. 已知二叉树中的结点类型用BTreeNode表示，被定义为: struct BTreeNode { char data;

BTreeNode *leftChild, *rightChild; };

//特殊情形的处理

//定义

{ if(pa->data>=pb->data)

第16页，共17页

06计算机——数据结构期末复习试卷

其中data为结点的数据域，leftChild和rightChild分别为指向左、右子女结点的指针域。

根据下面的函数声明，编写统计并返回一棵二叉树中所有叶子结点个数的递归算法。（假定参数BT为指向这棵二叉树的根结点的指针） int Count ( BTreeNode* BT ); 答：int Count(BtreeNode *BT)

{ if (BT= =NULL) return 0；

else if (BT->leftChild= = &&BT->rightChild= =NULL) return 1; else return Count(BT->leftChild)+Count(BT->rightChild);}

6．若矩阵Am?n中的某一元素A[i][j]是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵，试编写一个函数，确定鞍点在数组中的位置（若鞍点存在时），并分析该函数的时间复杂度。

答：int minmax(int A[ ][ ],const int m,const int n) { int *row=new int [m]; int *col=new int [n]; int i,j;

for(i=0;i

if(A[i][j]

}

for(j=0;j

col[i]=A[0][j]; for(i=1;i

if(A[i][j]>col[j]) col[j]=A[i][j]; }

for(i=0;i

cout<<”The saddle point is :(“<

delete[]row; delete[]col; } （7分）

此算法有3个并列二重循环，其时间复杂度为O(m*n).

7．设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。

答：templatevoid List ::Inverse(){ if(first==Null) return ;

ListNode*p=first->link,*pr=Null; while(p!=Null){ first->link=pr;

Pr=first;first=p;p=p->link;} first->link=pr;}

第17页，共17页