2021年数据结构形成性考核答案(本)作业1-4.doc

数据构造（本）形成性考核作业答案

作业1

一、单项选取题
1．C 2．D 3．B 4．C 5．D 6．C 7．B 8．C 9．A 10．B
11．C 12．D 13．C 14．A 15．B 16．C 17．C 18．B 19．B 20．D

二、填空题
1．n-i+1
2．n-i
3．集合 线性构造 树形构造 图状构造
4．物理构造 存储构造
5．线性构造 非线性构造
6．有穷性 拟定性 可形性 有零个或各种输入 有零个或各种输出
7．图状构造
8．树形构造
9．线性构造
10． n-1 O(n)
11．s->next=p->next；
12．head
13．q->next=p->next；
14．p->next=head；
15．单链表
16．顺序存储 链式存储
17．存储构造
18．两个 直接后继 直接前驱 尾结点 头结点
19．头结点指针 指向第一种结点指针
20．链式 链表

三、问答题
1．简述数据逻辑构造和存储构造区别与联系，它们如何影响算法设计与实现？
答：若用结点表达某个数据元素，则结点与结点之间逻辑关系就称为数据逻辑构造。数据在计算机中存储表达称为数据存储构造。可见，数据逻辑构造是反映数据之间固关于系，而数据存储构造是数据在计算机中存储表达。尽管因采用存储构造不同，逻辑上相邻结点，其物理地址未必相似，但可通过结点内部信息，找到其相邻结点，从而保存了逻辑构造特点。采用存储构造不同，对数据操作在灵活性，算法复杂度等方面差别较大。

2．解释顺序存储构造和链式存储构造特点，并比较顺序存储构造和链式存储构造优缺陷。
答：
顺序构造存储时，相邻数据元素存储地址也相邻，即逻辑构造和存储构造是统一，，规定内存中存储单元地址必要是持续。
长处：普通状况下，存储密度大，存储空间运用率高。
缺陷：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以预计，必要预先分派较大空间，往往使存储空间不能得到充分运用；（3）表容量难以扩充。
链式构造存储时，相邻数据元素可随意存储，所占空间分为两某些，一某些存储结点值，另一某些存储表达结点间关系指针。
长处：插入和删除元素时很以便，使用灵活。
缺陷：存储密度小，存储空间运用率低。

3．什么状况下用顺序表比链表好？
答：顺序表适于做查找这样静态操作，链表适于做插入和删除这样动态操作。如果线性表变化长度变化不大，且其重要操作是查找，则采用顺序表；如果线性表长度变化较大，且其重要操作是插入、删除操作，则采用链表。

4．解释头结点、第一种结点（或称首元结点）、头指针这三个概念区别？
答：
头结点是在链表开始结点之前附加一种结点；第一种结点（或称首元结点）是链表中存储第一种数据元素结点；头指针是指向链表中第一种结点（或为头结点或为首元结点）指针。

5．解释带头结点单链表和不带头结点单链表区别。
答：
带头结点单链表和不带头结点单链表区别重要体当前其构造上和算法操作上。
在构造上，带头结点单链表，不论链表与否为空，均具有一种头结点，不带头结点单链表不含头结点。
在操作上，带头结点单链表初始化为申请一种头结点。无论插入或删除位置是地第一种结点还是其她结点，算法环节都相似。不带头结点单链表，其算法环节要分别考虑插入或删除位置是第一种结点还是其她结点。由于两种状况算法环节不同。

四、程序填空题
1．
（1）p->data=i
（2）p->next=NULL
（3）q->next=p
（4）q=p

2．
（1）head=p
（2）q=p
（3）p->next=NULL
（4）p->next=q->next
（5）q->next=p
3．
（1）p=q->next
（2）q->next=p->next

五、完毕：实验1――线性表
依照实验规定（见教材P201-202）认真完毕本实验，并提交实验报告。

作业2答案

一、单项选取题
1．C 2．B 3．A 4．C 5．B 6．A 7．B 8．C 9．A 10．C
11．B 12．C 13．B 14．B 15．A 16．C 17．B 18．A 19．C 20．D
21．B 22．D 23．C 24．B 25．D 26．A 27．C 28．D 29．D 30．C 31．A 32．D

二、填空题
1．后进先出
2．下一种
3．增1 增1
4．假上溢
5．
栈与否满 s->top=MAXSIZE-1 栈顶指针 栈顶相应数组元素 栈与否空 s->top=-1 栈顶元素 修改栈顶指针
6．bceda
7．终结条件 递归某些
8．LU->front==LU->rear
9．运算符 操作数 ab+c/fde/--
10．s->next=h；
11．h=h->next；
12．r->next=s；
13．f=f->next;
14．字符
15．顺序存储方式 链式存储方式
16．0 空格字符个数
17．特殊 稀疏
18．（） （（）） 2
19．（（d,e,f））
20．串长度相等且相应位置字符相等
21．i(i-1)/2+j
22．行下标、列下标、非零元素值

三、问答题
1．简述栈和普通线性表区别。
答：栈是一种先进后出线性表，栈插入和删除操作都只能在栈顶进行，而普通线性表可以在线性表任何位置进行插入和删除操作。

2．简述队列和普通线性表区别。
队列是一种先进先出线性表，队列插入只能在队尾进行，队列删除只能在队头进行，而普通线性表可以在线性表任何位置进行插入和删除操作。

3．链栈中为什么不设头结点？
答：由于链栈只在链头插入和删除结点，不也许在链表中间插入和删除结点，算法实现很简朴，因此普通不设立头结点。

4．运用一种栈，则：
（1）如果输入序列由A，B，C构成，试给出所有也许输出序列和不也许输出序列。
（2）如果输入序列由A，B，C，D构成，试给出所有也许输出序列和不也许输出序列。
答：
（1）栈操作特点是后进先出，因而输出序列有：
A入，A出，B入，B出，C入C出，输出序列为ABC。
A入，A出，B入，C入，C出，B出，输出序列为ACB。
A入，B入，B出，A出，C入，C出，输出序列为BAC。
A入，B入，B出，C入，C出，A出，输出序列为BCA。
A入，B入，C入，C出，B出，A出，输出序列为CBA。
由A，B，C构成数据项，除上述五个不同组合外，尚有一种C，A，B组合。但不也许先把C出栈，再把A出栈，（A不在栈顶位置），最后把B出栈，因此序列CAB不也许由输入序列A，B，C 通过栈得到。
（2）按照上述办法，也许输出序列有：
ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。
不也许输出序列有：
DABC，ADBC，DACB，DBAC，BDAC，DBCA，DCAB，CDAB，CADB，CABD

5．用S表达入栈操作，X表达出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应S和X操作串是什么？
答：应是SXSSXSXX。各操作成果如下：
S 1入栈
X 1出栈 输出序列：1
S 2入栈
S 3入栈
X 3出栈 输出序列：13
S 4入栈
X 4出栈 输出序列：134
X 2出栈 输出序列：1342

6．有5个元素，其入栈顺序为：A、B、C、D、E，在各种也许出栈顺序中，以元素C、D最先顺序有哪几种？
答：从题中可知，要使C第一种且D第二个出栈，应是A入栈，B入栈，C入栈，C出栈，D入栈。之后可以有如下几种状况：
（1）B出栈，A出栈，E入栈，E出栈，输出序列为：CDBAE。
（2）B出栈，E入栈，E出栈，A 出栈，输出序列为CDBEA。
（3）E入栈，E出栈，B出栈，A出栈，输出序列为CDEBA
因此也许顺序有：CDBAE，CDBEA，CDEBA

7．写出如下运算式后缀算术运算式
⑴ 3x2+x-1/x+5
⑵ (A+B)*C-D/(E+F)+G
答；相应后缀算术运算式
⑴ 3x2^*x+1x/-5+
⑵ AB+C*DEF+/-G+

8． 简述广义表和线性表区别和联系。
答：广义表是线性表推广，它也是n(n>0)个元素a1 ,a2…ai… an有限序列，其中ai或者是原子或者是一种广义表。因此，广义表是一种递归数据构造，而线性表没有这种特性，线性表可以当作广义表特殊状况，当ai都是原子时，广义表退化成线性表。

四、程序填空题
1．
（1）q->front->next=p->next;
（2）free(p);
（3）q->rear=q->front

五、综合题
1．
答：出队序列是e2,e4,e3,e6,e5,e1过程：
⑴ 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）
⑽ e6出栈（栈底到栈顶元素是e1,e5）
⑾ e5出栈（栈底到栈顶元素是e1）
⑿ e1出栈（栈底到栈顶元素是空）
栈中最多时有3个元素，因此栈S容量至少是3。

2．
算法设计如下：
/*只有一种指针rear链式队基本操作*/
#include <stdio.h>
typedef char elemtype;
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；
}
}

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 /*有各种结点时*/
{
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("%c ",p->data);
p=p->next;
}
printf("%c\n",p->data);
}

六、完毕：实验2――栈、队列、递归程序设计
依照实验规定（见教材P203）认真完毕本实验，并提交实验报告。

作业3答案

一、单项选取题
1．B 2．B 3．D 4．C 5．B 6．A 7．A 8．C 9．A 10. D
11. A 12．C 13．C 14．B 15．B 16．C 17．B 18．C 19．A 20．B
21．D 22．B 23. B 24. B 25. C 26. A 27．A 28．C

二、填空题
1．子树树木或后继结点数
2．树中所有结点度最大值
3．分支结点 非终端结点
4．叶子结点 终端结点
5．子树根 后继结点 孩子结点
6．祖先
7．树中结点最大层数
8．
9．根结点 左子树 右子树
10．左子树 根结点 右子树
11．左子树 右子树 根结点
12．权
13．带权途径长度之和
14．最优二叉树 最小二叉树
15．69
16．2m-1
17．多对多
18．所有顶点 一次
19．先序
20．按层次
21．n2
22．邻接矩阵 邻接表
23．2(n-1)
24．n-1
25．栈

三、综合题
1．写出如下图所示二叉树先序、中序和后序遍历序列。
答：二叉树定义是递归，因此，一棵二叉树可看作由根结点，左子树和右子树这三个基本某些构成，即依次遍历整个二叉树，又左子树或者右子树又可看作一棵二叉树并继续分为根结点、左子树和右子树三个某些…..，这样划分始终进行到树叶结点。
(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）二叉树图形表达如下：

（2）该二叉树后序遍历成果是：G、D、B、L、H、K、M、I、E、J、F、C和A。

3．答
⑴ 已知深度为k二叉树最多有2k-1个结点(K≥1)，
　 29-1<892< 210-1，故树高度为10
⑵ 对于完全二叉树来说，度为1结点只能是0或1
　由于n=n0+n1+n2和n0=n2+1
　得：设n1=0，892=n0+0+n2=2n2+1　得n2不为整数出错
　　　设n1=1，892=n0+1+n2=2n2+2　
　　　得n2 =445→ n0=n2+1=446
　叶子结点数为446。
⑶ 由⑵得单支结点数为1
⑷ 对于n个结点完全二叉树，最后一种树叶结点，即序号为n叶结点其双亲结点　 即为最后一种非终端结点，
序号为892/2=446。

4．
（1）先序序列和中序序列相似二叉树为空树或任一结点均无左孩子非空二叉树
（2）中序和后序序列相似二叉树为空树或任一结点均无右孩子非空二叉树
（3）先序和后序序列相似二叉树为空树或仅有一种结点

5．
（1）哈夫曼树如图B-4所示。

图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．答
（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．
①　g1图示和图g1邻接表如下图所示。

图G

②　图G邻接矩阵如下图所示：

0 1 0 1 0
1 0 0 1 1
0 0 0 1 1
1 1 1 0 0
0 1 1 0 0

图G邻接矩阵 图G邻接表

③　V1、V2、V3、V4、V5度分别为：2，3，2，3，2
四、程序分析题
1. (1) return c1+1
(2) NodeLevel(BT->right,X)
(3) (c2>=1) return c2+1

2．(1)for(j=0；j<n；j++)
(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.
int BTreeLeafCount(struct BTreeNode* BT)
{
if(BT==NULL) return 0;
else if(BT->left==NULL && BT->right==NULL) return 1;
else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right);
}

六、完毕：实验3――栈、队列、递归程序设计
实验4——图存储方式和应用
依照实验规定（见教材P203）认真完毕本实验，并提交实验报告。
作业4答案

一、单项选取题
1．D 2．C 3．B 4．C 5．D 　 6．Ａ 7．C 8．D 9．B 10．D
11．C 12．C 13．A 14．C 15．D 16．B 17．B 18．D 19．D 20．A
21．D 22．D 23．A 24．A 25．C 26．C 27．B 28．A 29．B 30．C

二、填空题
1．哈希表查找法
2．数据项值 记录
3．主核心字
4．数学盼望值
5．顺序
6．二分查找 升序或降序排列
7．顺序存储构造
8．索引顺序查找 顺序查找
9．均不大于根结点值 均不不大于根结点值 二叉排序树
10．自变量 函数值
11．9， 14， 16 ，17
12．内部排序 外部排序
13．互换排序
14．3
15．4 8
16．堆排序 迅速排序
17．主核心字
18．核心字相等记录
19．n-1,n-j
20．堆尾 堆顶 向下

三、综合题
1．已知序列（70，83，100，65，10，32，7，9），请写出对此序列采用插入排序法进行升序排序时各趟成果。
答：
原始序列：（70），83，100，65，10，32，7，9
第1趟： （70，83），100，65，10，32，7，9

第2趟：（70，83，100），65，10，32，7，9
第3趟：（65，70，83，100），10，32，7，9
第4趟：（10，65，70，83，100），32，7，9
第5趟：（10，32，65，70，83，100），7，9
第6趟：（7，10，32，65，70，83，100），9
第7趟：（7，9，10，32，65，70，83，100）

2．已知序列（10，18，4，3，6，12，1，9，15，8），请写出对此序列采用归并排序法进行升序排序时各趟成果。
答：
原始序列：10，18，4，3，6，12，1，9，15，8
第1趟： [10，18][ 3，4][6，12][1，9][ 8，15]
第2趟： [3，4，10，18，][ 1，6，9，12][ 8，15]
第3趟： [3，4，10，18，][ 1，6，8，9，12，15]
第4趟： [1，3，4，6，8，9，10，12，15，18]

3．已知序列（17，18，60，40，7，32，73，65，85）采用冒泡排序法排序各趟成果如下：
原始初始：17，18，60，40，7，32，73，65，85
第1趟：17，18，40，7，32，60，65，73，85
第2趟：17，18，7，32，40，60，65，73，85
第3趟：17，7，18，32，40，60，65，73，85
第4趟：7，17，18，32，40，60，65，73，85
第5趟：7，17，18，32，40，60，65，73，85
4．已知序列（503，87，512，61，908，170，897，275，653，462）请给出采用迅速排序法对该序列作升序排列时每一趟成果。
原始序列：503，87，512，61，908，170，897，275，653，462
第1趟： [462，87，275，61，170]503[897，908，653，512]
第2趟： [170，87，275，61] 462，503[897，908，653，512]
第3趟： [87，61]170[275] 462，503[897，908，653，512]
第4趟： 61 [87]170[275] 462，503[897，908，653，512]
第5趟： 61 ，87，170，[275] 462，503[897，908，653，512]
第6趟： 61 ，87，170，275，462，503[897，908，653，512]
第7趟： 61 ，87，170，275，462，503[512，653]897[908]
第8趟： 61 ，87，170，275，462，503，512，[653] 897[908]
第9趟： 61 ，87，170，275，462，503，653，897[908]
第10趟： 61 ，87，170，275，462，503，653，897，908

5．设一组记录核心字序列为（49，83，59，41，43，47），采用堆排序算法完毕如下操作：（规定小根堆，并画出中间过程）
（1）以二叉树描述6个元素初始堆
（2）以二叉树描述逐次取走堆顶元素后，经调节得到5个元素、4个元素堆
答：
（1）

49
59
83
41
43
47
83
47
41
43
59
49
49
83
41
47
43
59

83

59
49
41
43
47
83
49
59
41
59
47
41
49
83
43
43
47
41
59
83
49
59
47
41
43
83
49
47
41
83
59
43
49
47
41
43
83
49
59

（2）

6．
(1)原序列16 15 20 53 64 7
15 16 20 53 7 64 n-1趟
15 16 20 7 53 64 n-j次
15 16 7 20 53 64
15 7 16 20 53 64
7 15 16 20 53 64
7
15
20
64
16
535
(2)

(3)平均查找长度=（1*1+2*2+3*3）/6=14/6

7．
2
4
6
16
7
3
18
5
145
（1）

(2)
中序遍历：2，3，4，5，6，7，14，16，18

四、程序填空题
1.
（1）①j>=0
（2）②a[j]
（3）③j--
（4）④temp

2．
（1）j<=n-1
（2）i<=n-j
（3）a[i]=a[i+1]
（4）a[i+1]=temp
（5）…当某趟冒泡中没有浮现互换则已排好序结束循环。

五、算法设计题
1．编写折半查找算法。
折半查找算法如下；
int Binary_Search(NODE a[],int n，int k)
/* 在a[0]到a[n-1]中，用折半查找算法查找核心字等于k记录，查找成功返回该记录下标，失败时返回-1 */
{
int low,mid,high;
low=0;
high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(a[mid].key==k)
return mid; /*查找成功，返回查找到记录下标*/
else if(a[mid].key<k)
low=mid+1; /*取后半查找区间*/
else high=mid-1; /*取前半查找区间*/
}
return -1; /*查找失败*/
}

2. 编写顺序查找算法。
顺序查找算法如下：
int search(NODE a[],int n，int k)
/*在a[0]～a[n-1]中顺序查找核心字等于k记录。查找成功时返回该记录下标，失败时返回-1*/
{
int i=0;
while(i<n && a[i].key!=k) /*没有查到同步查找过程没有结束，则继续查找*/
i++;
if(a[i].key=k) /*查找成功*/
return i;
else return -1； /*查找失败*/
}

六、完毕：实验3――栈、队列、递归程序设计
实验4——图存储方式和应用
依照实验规定（见教材P203）认真完毕本实验，并提交实验报告。