《数据结构C语言描述》期末试卷.docx

⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
号⋯
学
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
名⋯
姓
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
装
班⋯
⋯
）⋯
系
（⋯
院⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
0
1
∞
4
0
1
10
3
0
1
10
3
0
1
9
3
∞0
9
2
∞0
9
2
1209
2
11
0
8
2
3
4
0
7
3
4
0
6
3
4
0
6
3
4
0
6
∞∞6
0
∞∞60
9
10
6
0
9
10
60
五、（12分）设双链表结点结构为

llinkdatarlink，请设计算法将此中

P所指结点与其

rlink
所指结点地址交换的算法。
解：
typedefstructDLNode{
ElemTypedata;
structDLNode*llink,*rlink;
}DLNode,*DLinkList;
思想：将P->rlink先从链表中删除去，尔后再插入到P前
StatusSwapANode(DLNode*&P)
{
结点存在吗?
if(!P||!(P->rlink))returnERROR;
q=P->rlink;
删除q结点
if(!q->rlink)
P->rlink=NULL;
else{
P->rlink=q->rlink;
q->rlink->llink=P;
}
将q结点插入到P结点前面
if(!P->llink)
{
q->llink=NULL;
q->rlink=P;
P->llink=q;
}else{
q->llink=P->llink;
q->rlink=P;
P->llink->rlink=q;
P->llink=q;
}
returnOK;
}
六、（13分）如有一棵二叉树的储藏结构为二叉链表，T指向根结点，请写出一个非递归算法判断其可否为二叉排序数。
解：
解法一：
#defineTRUE1
#defineFALSE0
typedefintBOOL;
typedefstructBTreeNode{
ElemTypedata;
structBTreeNode*lchild,*rchild;
}BTreeNode,*BTree;
我是将教材P130的中序非递归遍历方法改的
说明没写，大家看书上的吧
BOOLIsBST(BTreeT)
{
if(!T)returnTRUE;
InitStack(S);
x=T->data;
Push(S,T);
while(!StackEmpty(S))
{
while(GetTop(S,p)&&p)Push(S,p->lchild);
Pop(S,p);
if(!StackEmpty(S))
{
Pop(S,p);
if(x>p->data)returnFALSE;
x=p->data;
Push(S,p->rchild);
}//if
whilereturnTRUE;
}
另解：
//我的其他一个解法,依据longeli的思想
//Author:Ritchie
Date:2002-10-12typedefintElemType;typedefstructBiTreeNode{
ElemTypedata;
structBTreeNode*lchild,*rchild;}BiTreeNode,*BiTree;
功能：判断二叉树T可否为二叉排序树,若是是返回TRUE,不然返回FALSE
思想：判断T中的结点可否符合要求,按层序进行判断,一旦不符合就返回
StatusIsBST(BiTreeT)
{
if(!T)returnTRUE;//空树是BST
InitQueue(Q);
EnQueue(Q,T);
while(!QueueEmpty(Q))
{
DeQueue(Q,t);
左右孩子先入队
if(t->lchild)EnQueue(Q,t->lchild);
if(t->rchild)EnQueue(Q,t->rchild);
if(t->lchild&&t->lchild){
//左右子树不为空且不知足BST的条件，返回FALSEif((t->lchild->data>=t->data)||(t->rchild->data<
t->data))
returnFALSE;
}elseif(t->lchild&&(t->lchild->data>=t->data)){
//右子树为空的状况returnFALSE;
}elseif(t->rchild&&(t->rchild->data<t->dat