数据结构习题参考答案

1. 算法设计：利用顺序存储结构实现PriorElem(L,cur_e,&pre_e)操作。 #define OK 1 #define ERROR 0 typedef int Status;

//---------------------线性表的顺序存储表示----------------------- typedef struct { ElemType *elem; int length; int listsize;

}SqList;

//----------------------算法描述----------------------------------------- Status PriorElem(SqList L,ElemType cur_e,ElemType pre_e) { //若cur_e是顺序表L中的元素，且不是第一个，则用pre_e返回它的前驱，

//否则，操作失败，pre_e无意义。 for(j=1;j<=L.length;j++)

if(L.elem[j-1]==cur_e)

break;

if(j==1||j>L.length) return ERROR;

pre_e=L.elem[j-2]; return OK;

}//PriorElem

2.

算法设计：编写算法实现带有头结点的线性链表L（L为头指针）的长度，即 LinkLength(L)。

//-------------------------线性链表的存储表示--------------- typedef struct LNode{ ElemType data;

struct LNode *next;

}LNode, *LinkList;

//-------------------------算法描述----------------------------- int LinkLength(LinkList L)

{ //求带有头结点的线性链表L的长度 p=L; j=0;

while(p->next!=NULL) { p=p->next; j++;

}

return j;

}//LinkLength

1.

试写一个算法，识别依次读入的一个以‘@’作为结束符的字符序列是否为形如“序列1&序列2”模式的字符序列。其中序列1和序列2中都不包含字符‘&’，且序列2是序列1的逆序列。如“a+b&b+a”。 参考算法： #define TURE 1 #define FALSE 0 typedef int Status; Status panding() { InitStack(S); ch=getchar();

while(ch!=’@’&&ch!=’&’) { Push(S,ch); ch=getchar();

}

if(ch==’@’)

return FALSE;

ch=getchar();

while(ch!=’@’&&!StackEmpty(S)) { Pop(S,e); if(ch!=e) return FALSE;

ch=getchar();

}

if(ch==’@’)&&StackEmpty(S) return TRUE; else return FALSE;

}

2.

假设称正读和反读都相同的字符序列为“回文”，试写一个算法判别读入的一个以‘@’结束的字符序列是否为回文。 #define TURE 1 #define FALSE 0 typedef int Status; Status HuiWen()

{ InitQueue(Q); InitStack(S);

ch=getchar(); while(ch!=’@’) { EnQueue(Q, ch); Push(S, ch); ch=getchar(); }

while(!StackEmpty(S))

{ Pop(S, e1); DeQueue(Q,e2);

if(e1!=e2) return FALSE;

}

return TRUE; }

1. 二维数组A[10][20]采用列序为主方式存储，每个元素占用一个存储单元，且A[0][0]的存储地址是200，则求元素A[6][12]的地址。

解：LOC(6,12)=LOC(0,0)+(12×10+6)=200+120+6=326

2. 二维数组A[10..20][5..10]采用行序为主序存储，每个元素占4个

存储单元，且A[10][5]的存储地址为1000，则求A[18][9]的地址。 解：LOC(18,9) = LOC(10,5)+(8×6+4)×4=1000+52×4=1208 1.

1. 简述度为2的树与二叉树的区别。 答：

（1）度为2的树至少有一个结点的度为2，二叉树的度最多为2，也可以是0或1。

（2）二叉树一定是有序树，度为2的树不一定

是有序树。

2.

已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，?，nk个度为k的结点，试计算该树中叶子结点的数目。

解：设该树中叶子结点的数目为n0，树的总结点数目为n，总分支数目为B，则有： n=n0+n1+n2+…+nk (1) B=n-1

(2)

B=n1+2n2+3n3+…+knk

(3)

解得：n0=n2+2n3+3n4+…+(k-1)nk+1

3.

已知如图二叉树，写出二叉树的先序、中序和后序遍历序列。

先序遍历序列：ABDGCEFH

中序遍历序列：DGBAECHF

后序遍历序列：GDBEHFCA

A

B C D E F 4. 已知一棵二叉树的先序遍历序列为

G H EBADCFHGIKJ，

中序遍历序列为ABCDEFGHIJK，试画出该二叉树的形态。 恢复二叉树如图1所示：

5.

已知一棵二叉树的中序序列为DCBGEAHFIJK，后序序列为DCEGBFHKJIA，试写出其先序遍历序列，并画出其先序线索二叉树。

先序遍历序列：ABCDGEIHFJK，其先序线索二叉树如图2所示。

6. 设叶子结点的权值集合为W={4,5,6,7,10,12,18}，试构造一棵赫夫曼树，并计算其WPL值。

WPL=(12+18)×2+(6+7+10)×3+(4+5)×4=165

7.

有一份电文，共使用5种字符，H={a,b,c,d,e}，对应的频率次数为W={4,7,5,2,9}，试画出对应的赫夫曼树，写出每个字符的赫夫曼编码。赫夫曼编码：

a：011 b：10 c：00 d：010

e：11

10. 编写算法实现二叉树T的按层遍历。（二叉树采用二叉链表存储）

参考算法： #define OK 1 #define ERROR 0 typedef int Status;

//-------------------二叉链表的存储表示-------------------- typedef struct BiTNode { TElemType data;

struct BiTNode *lchile, *rchild;

}BiTNode, *BiTree; //-------------------算法描述------------------------------------

Status LayerTraverse(BiTree

T,

Status (*visit)(TElemType e))

{ //按层遍历二叉链表T。 if(!T)

return OK;

InitQueue(Q); EnQueue(Q,T); while(!QueueEmpty(Q)) { DeQueue(Q,p); if(!(*visit)(p->data)) return ERROR; if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild)

EnQueue(Q,p->rchild);

}

return OK;

}//LayTraverse

11. 编写算法实现对二叉树T交换左右子树的操作。（二叉树采用二叉链表存储）

参考算法：

符号常量和类型的定义及二叉链表的存储表示如上题。 Status Exchange(Bitree &T) { if(!T)

return OK;

p=T->lchild;

T->lchild=T-rchild;

T->rchild=p;

Exchange(T->lchild);

Exchange(T->rchild);

return OK;

}//Exchange

12. 编写算法实现统计二叉树T的叶子结点的数目的操作。（二叉树采用二叉链表存储）

参考算法：

符号常量和类型的定义及二叉链表的存储表示如第10题。 ` int Countleaf(Bitree T) {

if(!T)

return 0;

if(T->lchild==NULL&&T->rchild==NULL) return 1;

return(Countleaf(T->lchild)+Countleaf(T->rchild)); }

2.

根据上述邻接表，写出以V2开始的深度优先搜索与广度优先搜索的结果。 深度优先搜索：v2,v1,v3,v4,v5。 广度优先搜索：v2,v1,v3,v5,v4。

3.

使用Prim和Kruskal算法构造下面连通网络的最小生成树，写出构造过程。

4.

计算下面有向网络中，顶点v0到其他顶点的最短路径，写

出计算过程。（使用Dijkstra算法）

补充：若有待排序记录关键字序列为（35，24，68，75，12，44，07，19，39，50，01，24），使用以下方法进行升序排列，写出排序过程。

插入排序类：直接插入排序、希尔排序（设d1=6,d2=3,d3=1）

交换排序类：冒泡排序、快速排序（设子表的第一个元素为枢轴元素）

选择排序类：简单选择排序、堆排序（创建大顶堆，反复调整堆） 归并排序

本文来源：https://www.bwwdw.com/article/d7o2.html