⑴ e1入栈（栈底到栈顶元素是e1） ⑵ e2入栈（栈底到栈顶元素是e1,e2） ⑶ e2出栈（栈底到栈顶元素是e1） ⑷ e3入栈（栈底到栈顶元素是e1,e3） ⑸ e4入栈（栈底到栈顶元素是e1,e3,e4） ⑹ e4出栈（栈底到栈顶元素是e1,e3） ⑺ e3出栈（栈底到栈顶元素是e1） ⑻ e5入栈（栈底到栈顶元素是e1,e5） ⑼ e6入栈（栈底到栈顶元素是e1,e5,e6） void delqueue(LinkQueue *Q) /*出队算法*/ {
struct node *t; if (Q->rear==NULL) { printf(\队列为空!\\n\ return(0); }
else if (Q->rear->next==Q->rear) /*只有一个结点时*/ { t=Q->rear; Q->rear=NULL; }
else /*有多个结点时*/ ⑽ e6出栈（栈底到栈顶元素是e1,e5） ⑾ e5出栈（栈底到栈顶元素是e1） ⑿ e1出栈（栈底到栈顶元素是空）
栈中最多时有3个元素，所以栈S的容量至少是3。
2．假设用循环单链表实现循环队列，该队列只使用一个尾指针rear，其相应的存储结构和基本算法如下；
（1）初始化队列initqueue(Q):建立一个新的空队列Q。 （2）入队列enqueue(Q,x):将元素x插入到队列Q中。 （3）出队列delqueue(Q):从队列Q中退出一个元素。 （4）取队首元素gethead(Q):返回当前队首元素。 （5）判断队列是否为空：emptyqueue(Q)。 （6）显示队列中元素：dispqueue(Q)。 算法设计如下：
/*只有一个指针rear的链式队的基本操作*/ #include
struct node /*定义链队列结点*/ {
elemtype data; struct node *next; };
typedef struct queue /*定义链队列数据类型*/ {
struct node *rear; } LinkQueue;
void initqueue(LinkQueue *Q)/*初始化队列*/ {
Q=(struct queue *)malloc(sizeof(struct queue)); Q->rear=NULL; }
void enqueue(LinkQueue *Q,elemtype x) /*入队算法*/ {
struct node *s,*p;
s=(struct node *)malloc(sizeof(struct node)); s->data=x;
if (Q->rear==NULL) /*原为空队时*/ { Q->rear=s; s->next=s; }
else /*原队不为空时*/ { p=Q->rear->next; /*p指向第一个结点*/ Q->rear->next=s; /*将s链接到队尾*/ Q->rear=s; /*Q->rear指向队尾*/ s->next=p; } }
{ t=Q->rear->next; /*t指向第一个结点*/ Q->rear->next=t->next; /*引成循环链*/ }
free(t); }
elemtype gethead(LinkQueue *Q) /*取队首元素算法*/ {
if (Q->rear==NULL) printf(\队列为空!\\n\ else return(Q->rear->next->data); }
int emptyqueue(LinkQueue *Q) /*判断队列是否为空算法*/ {
if (Q->rear==NULL) return(1); /*为空,则返回true*/ else return(0); /*不为空,则返回flase*/ }
void dispqueue(LinkQueue *Q) /*显示队列中元素算法*/ {
struct node *p=Q->rear->next; printf(\队列元素:\ while (p!=Q->rear) { printf(\ p=p->next; }
printf(\}
六、完成：实验2――栈、队列、递归程序设计
根据实验要求（见教材P203）认真完成本实验，并提交实验报告。 数据结构（本）课程作业 作业3
（本部分作业覆盖教材第6-7章的内容） 一、单项选择题
1.假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ B ）。
A．15 B．16 C．17 D．47 2．二叉树第k层上最多有（ B ）个结点。 A．2k B．2
k-1
C．2k
-1 D．2k-1
3．二叉树的深度为k,则二叉树最多有（ D ）个结点。
A．2k B．2k-1 C．2k-1
D．2k
-1
4. 设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（ C ）。
A．abdec B．debac C．debca D．abedc
6
5．将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（ B ）。
A．33 B．34 C．35 D．36
6．如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（ A ）。
A．哈夫曼树 B．平衡二叉树 C．二叉树 D．完全二叉树 7．下列有关二叉树的说法正确的是（ A ）。
A．二叉树中度为0的结点的个数等于度为2的结点的个数加1 B．二叉树中结点个数必大于0
C．完全二叉树中，任何一个结点的度，或者为0或者为2 D．二叉树的度是2
8．在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。
A．4 B．5 C．6 D．7
9．在一棵度具有5层的满二叉树中结点总数为（ A ）。
A．31 B．32 C．33 D．16
10. 利用n个值作为叶结点的权生成的哈夫曼树中共包含有( D )个结点。 A. n B. n+1 C. 2*n D. 2*n-1
11. 利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为( A )。
A. 18 B. 16 C. 12 D. 30 12．在一棵树中，（ C ）没有前驱结点。
A．分支结点 B．叶结点 C．树根结点 D．空结点
13．在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ C ）。
A．2i B．2i-1 D．2i+1 C．2i+2
14．设一棵哈夫曼树共有n个叶结点，则该树有（ B ）个非叶结点。
A．n B．n-1 C．n+1 D．2n
15．设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（ B ）个结点。
A．2n B．2n-1 C．2n+1 D．2n+2
16．在一个图G中，所有顶点的度数之和等于所有边数之和的（ C ）倍。
A．1/2 B．1 C．2 D．4
17．在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。
A．邻接矩阵表示法 B．邻接表表示法 C．逆邻接表表示法 D．邻接表和逆邻接表 18．在图的存储结构表示中，表示形式唯一的是（ C ）。 A．n B．n?1 C．n?1 D．n/2 19．一个具有n个顶点的无向完全图包含（ A ）条边。
A．n（n?1） B．n（n?1） C． n（n?1）/2 D． n（n?1）/2
20．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ B ）。 A．n B．n C．n?1 D．（n?1）
2
2
21．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ D ）。
A．n B．e C．2n D．2e
22．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（ B ）邻接点。 A．入边 B． 出边 C．入边和出边 D． 不是入边也不是出边 23．邻接表是图的一种（ B ）。
A．顺序存储结构 B．链式存储结构 C．索引存储结构 D．散列存储结构
24．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该
图一定是（ B ）。
A．完全图 B．连通图 C．有回路 D．一棵树 25．下列有关图遍历的说法不正确的是（ C ）。
A．连通图的深度优先搜索是一个递归过程
B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次
26．无向图的邻接矩阵是一个（ A ）。
A．对称矩阵 B． 零矩阵 C．上三角矩阵 D．对角矩阵 27．图的深度优先遍历算法类似于二叉树的（ A ）遍历。 A．先序 B． 中序 C．后序 D．层次
28．已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ C ）。
A．V1V2V4V8V3V5V6V7 B．V1V2V4V5V8V3V6V7
C．V1V2V4V8V5V3V6V7 D．V1V3V6V7V2V4V5V8
二、填空题
V1 1．结点的度是指结点所拥有的 子树树木或后继结点数 。 2．树的度是指 树中所有结点的度的最大值 。
V2 V3 3．度大于0的结点称作 分支结点 或 非终端结点 。 4．度等于0的结点称作 叶子结点 或 终端结点 。
5．在一棵树中，每个结点的 子树的根 或者说每个结点的 后继结点 称
V4 V5 V6 V7 为该结点的 孩子结点 ，简称为孩子。
6．从根结点到该结点所经分支上的所有结点称为该结点的 祖先 。 7．树的深度或高度是指 树中结点的最大层数 。 8．具有n个结点的完全二叉树的深度是
?log2n??1 。
V8 9．先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的 根结点 ；先序遍历二叉树的 左子树 ，先序遍历二叉树
7
的 右子树 。
10．中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的 左子树 ；访问而叉树的 根结点 ，中序遍历二叉树的 右子树 。
11．后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的 左子树 ；后序遍历二叉树的 右子树 ，访问而叉树的 根结点 。
12．将树中结点赋上一个有着某种意义的实数，称此实数为该结点的 权 。 13．树的带权路径长度为树中所有叶子结点的 带权路径长度之和 。 14．哈夫曼树又称为 最优二叉树 ，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL 最小的二叉树 。
15．若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 69
。
16．具有m个叶子结点的哈夫曼树共有 2m-1 结点。
17．在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种
多对多 的关系。
18．图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中 所有顶点 各做
一次 访问的过程。
19．图的深度优先搜索遍历类似于树的 先序 遍历。 20．图的广度优先搜索类似于树的 按层次 遍历。 21．具有n个顶点的有向图的邻接矩阵，其元素个数为 n2 。 22．图常用的两种存储结构是 邻接矩阵 和 邻接表 。 23．在有n个顶点的有向图中，每个顶点的度最大可达 2(n-1) 。 24．在一个带权图中，两顶点之间的最段路径最多经过 n-1 条边。
25．为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为 栈 。 三、综合题
1．写出如下图所示的二叉树的先序、中序和后序遍历序列。
A。
3．已知一棵完全二叉树共有892个结点，求 ⑴ 树的高度 ⑵ 叶子结点数 ⑶ 单支结点数
答：二叉树的定义是递归的，所以，一棵二叉树可看作由根结点，左子树和右子树这三个基本部分组成，即依次遍历整个二叉树，又左子树或者右子树又可看作一棵二叉树并继续分为根结点、左子树和右子树三个部分…..，这样划分一直进行到树叶结点。
(1)先序为“根左右”，先序序列为：fdbacegihl (2)中序为“左根右”，中序序列为：abcdefghij (3)后序为“左右根”，后序序列为：acbedhjigf
2．已知某二叉树的先序遍历结果是：A，B，D，G，C，E，H，L，I，K，M，F和J，它的中序遍历结果是：G，D，B，A，L，H，E，K，I，M，C，F和J，请画出这棵二叉树，并写出该二叉树后续遍历的结果。
（1）二叉树图形表示如下：
ABDGLHKEIMCFJ （2）该二叉树后序遍历的结果是：G、D、B、L、H、K、M、I、E、J、F、C和
f ⑷ 最后一个非终端结点的序号 d g 答 ⑴ 已知深度为k的二叉树最多有2k-1个结点(K≥1)， 29-1<892< 210-1，故树的高度为10
b e c h i ⑵ 对于完全二叉树来说，度为1的结点只能是0或1 因为n=n0+n1+n2和n0=n2+1
a 得：设n1=0，892=n0+0+n2=2n2+1 得n2不为整数出错 j 设n1=1，892=n0+1+n2=2n2+2
得n2 =445→ n0=n2+1=446 叶子结点数为446。 ⑶ 由⑵得单支结点数为1
⑷ 对于n个结点的完全二叉树，最后一个树叶结点，即序号为n的叶结点其双亲结
8
点 即为最后一个非终端结点，
序号为892/2=446。 V={V1，V2，V3，V4，V5}
E={（V1，V2），（V1，V4），（V2，V4），（V3，V4），（V2，V5），（V3，V4），（V3，V5）}
4．给出满足下列条件的所有二叉树。 （1）先序和中序相同 （2）中序和后序相同 （3）先序和后序相同
（1）先序序列和中序序列相同的二叉树为空树或任一结点均无左孩子的非空二叉树 （2）中序和后序序列相同的二叉树为空树或任一结点均无右孩子的非空二叉树 （3）先序和后序序列相同的二叉树为空树或仅有一个结点
5．假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I组成，它们出现的频率分别是：10、20、5、15、8、2、3、7和30。请请用这9个字母出现的频率作为权值求：
（1）设计一棵哈夫曼树； （2）计算其带权路径长度WPL； （3）写出每个字符的哈夫曼编码。
（1）哈夫曼树如图B-4所示。
010101013020I01B1510D01A01875EHC0123FG 图B-4
（2）其带权路径长度WPL值为270。
（3）每个字符的哈夫曼编码为：A:100, B:11, C:1010, D:000, E:0010, F:10110, G:10111, H:0011, I:01
6．请根据以下带权有向图G
（1）给出从结点v1出发分别按深度优先搜索遍历G和广度优先搜索遍历G所得的结点序列；
（2）给出G的一个拓扑序列；
（3）给出从结点v1到结点v8的最短路径。 答
（1）深度优先遍历：v1,v2,v3,v8,v5,v7,v4,v6 广度优先遍历：v1,v2,v4,v6,v3,v5,v7,v8 (2) G的拓扑序列为：v1,v2,v4,v6,v5,v5,v3,v5,v7,v8 (3)最短路径为：v1,v2,v5,v7,v8 7．已知无向图G描述如下：
G=（V，E）
（1）画出G的图示；
（2）然后给出G的邻接矩阵和邻接表； （3）写出每个顶点的度。
① g1的图示和图g1的邻接表如下图所示。
v1v4v2v3v5 图G
② 图G的邻接矩阵如下图所示：
v124^0 1 0 1 0 v2 14 5^1 0 0 1 1 0 0 0 1 1 v3 45^1 1 1 0 0 v4 12 3^0 1 1 0 0 v5 23^ 图G的邻接矩阵 图G的邻接表
③ V1、V2、V3、V4、V5的度分别为：2，3，2，3，2 四、程序填空题
1. 下面函数的功能是返回二叉树BT中值为X的结点所在的层号，请在划有横线的地方填写合适内容。
int NodeLevel(struct BinTreeNode* BT, char X) {
if(BT==NULL) return 0; /*空树的层号为0*/ else if(BT->data==X) return 1; /*根结点的层号为1*/ /*向子树中查找X结点*/ else {
int c1=NodeLevel(BT->left,X);
if(c1>=1) ___(1) return c1+1___________;
int c2=______(2) NodeLevel(BT->right,X)________ __; if ___(3)_ (c2>=1) return c2+1_________________; //若树中不存在X结点则返回0 else return 0; } }
9
2. 下面函数的功能是按照图的深度优先搜索遍历的方法，输出得到该图的生成树中的各条边，请在划有横线的地方填写合适内容。
else if(BT->left==NULL && BT->right==NULL) return 1;
else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right); }
void dfstree(adjmatrix GA, int i, int n) {
int j;
visited[i]=1;
(1) for(j=0; j if(GA[i][j]!=0 && GA[i][j]!=MaxValue && !visited[j]) { 六、完成：实验3――栈、队列、递归程序设计 实验4——图的存储方式和应用 根据实验要求（见教材P203）认真完成本实验，并提交实验报告。 数据结构（本）课程作业（4） （本部分作业覆盖教材第8-9章的内容） 一、单项选择题 1.顺序查找方法适合于存储结构为（ D ）的线性表。 printf(\ (2) dfstree(GA,j,n); } } 五、算法设计题 1．写一个将一棵二叉树复制给另一棵二叉树的算法。 define NULL 0 typedef struct btnode { elemtype data; struct btnode *lchild, *rchild; }bitnode, *bitree; bitree *CopyTree( bitnode *p ) { /*复制一棵二叉树*/ bitnode *t; if ( p!=NULL ) { t=(bitnode *)malloc (sizeof (bitnode)); t->data=p->data; t->lchild=CopyTree(p->lchild); t->rchild=CopyTree(p->rchild); return(t); } else return(NULL); }/*CopyTree*/ 2．根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指向二叉树的根结点。 int BTreeLeafCount(struct BTreeNode* BT); int BTreeLeafCount(struct BTreeNode* BT) { if(BT==NULL) return 0; A．散列存储 B．索引存储 C．散列存储或索引存储 D．顺序存储或链接存储 2．对线性表进行二分查找时，要求线性表必须（ C ）。 A．以顺序存储方式 B．以链接存储方式 C．以顺序存储方式 ，且数据元素有序 D．以链接存储方式，且数据元素有序 3. 对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该（ B ）。 A．以顺序存储方式 B．以链接存储方式 C．以索引存储方式 D．以散列存储方式 4．采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ C ）。 A．n B．n/2 C．(n+1)/2 D．(n-1)/2 5．哈希函数有一个共同的性质，即函数值应当以（ D ）取其值域的每个值。 A．最大概率 B．最小概率 C．平均概率 D．同等概率 6．有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ A ）。 A．29/10 B．31/10 C．26/10 D．29/9 7．已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（ C ）次。 A．3 B．4 C．5 D．6 8．顺序查找法与二分查找法对存储结构的要求是（ D ）。 A．顺序查找与二分查找均只是适用于顺序表 B．顺序查找与二分查找均既适用于顺序表，也适用于链表 C．顺序查找只是适用于顺序表 D．二分查找适用于顺序表 9．有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（ B ）。 A．45,24,53,12,37,96,30 B．37,24,12,30,53,45,96 C．12,24,30,37,45,53,96 D．30,24,12,37,45,96,53 10．对有18个元素的有序表作二分（折半）查找，则查找A[3]的比较序列的下标可能为（ D ）。 A．1、2、3 B．9、5、2、3 C．9、5、3 D．9、4、2、3 10
2017年电大电大数据结构(本)形成性考核册(作业1-4)原题带答案
