第4 10章作业

发布 2022-07-04 19:56:28 阅读 5362

第4-5章作业:

1. 什么称为空串;什么称为空白串?

2. 设数组a[1…60, 1…70]的基地址为2048,每个元素占2个存储单元,若以列序为主序顺序存储,则元素a[32,58]的存储地址为。

第6章作业:

1.画出和下列二叉树相应的森林。

2.编写递归算法,计算二叉树中叶子结点的数目。

3.编写递归算法,求二叉树中以元素值为a的结点为根的子树的深度。

4.假设用于通信的电文仅由8个字母组成,字母在电文**现的频率分别为0.07,0.

19,0.02,0.06,0.

32,0.03,0.21,0.

10。试为这8个字母设计哈夫曼编码。使用0~7的二进制表示形式是另一种编码方案。

对于上述实例,比较两种方案的优缺点。

第7章作业:

1. 已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是什么?广度优先遍历的结点序列是什么?

2. 已知图的邻接矩阵同上题8,根据算法,则从顶点0出发,按广度优先遍历的结点序列是什么?

简答题(每题6分,共24分)

1.已知如图所示的有向图,请给出该图的:

1) 每个顶点的入/出度;

2) 邻接矩阵;

3) 邻接表;

4) 逆邻接表。

2.请对下图的无向带权图:

1) 写出它的邻接矩阵,并按普里姆算法求其最小生成树;

2) 写出它的邻接表,并按克鲁斯卡尔算法求其最小生成树。

3.已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

4.试利用dijkstra算法求图中从顶点a到其他各顶点间的最短路径,写出执行算法过程中各步的状态。

第9章作业:

1. 假定对有序表:(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找,试回答下列问题:

1) 画出描述折半查找过程的判定树;

2) 若查找元素54,需依次与哪些元素比较?

3) 若查找元素90,需依次与哪些元素比较?

4) 假定每个元素的查找概率相等,求查找成功时的平均查找长度。

2. 设哈希(hash)表的地址范围为0~17,哈希函数为:h(k)=k mod 16。

k为关键字,用线性探测法再散列法处理冲突,输入关键字序列:

造出hash表,试回答下列问题:

1) 画出哈希表的示意图;

2) 若查找关键字63,需要依次与哪些关键字进行比较?

3) 若查找关键字60,需要依次与哪些关键字比较?

4) 假定每个关键字的查找概率相等,求查找成功时的平均查找长度。

第10章作业:

1. 设要将序列(q, h, c, y, p, a, m, s, r, d, f, x)中的关键码按字母序的升序重新排列,则:

冒泡排序一趟扫描的结果是。

初始步长为4的希尔(shell)排序一趟的结果是。

二路归并排序一趟扫描的结果是。

快速排序一趟扫描的结果是。

堆排序初始建堆的结果是。

计量作业第2章 第4章

第二章一元线性回归模型。1 最小二乘法对随机误差项u作了哪些假定?说明这些假定条件的意义。答 假定条件 1 均值假设 e ui 0,i 1,2,2 同方差假设 var ui e ui e ui 2 e ui2 u2 i 1,2,3 序列不相关假设 cov ui,uj e ui e ui uj e u...

第3章作业

第3章栈和队列作业。1 若用一个大小为6的数组来实现循环队列,且当rear和front的值分别为0和3时,从队列中删除一个元素,再加入两个元素后,rear和front的值分别为多少?复旦大学98年 2和42 设栈s和队列q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈s,一个元素出...

第3章作业

第3章统计数据的整理与显示。一 判断题 把 或 填在题后的括号里 1 能够对统计总体进行分组,是由统计总体中的各个单位所具有的 同质性 特点决定的。2 按数量标志分组,各组的变量值能准确地反映社会经济现象性质上的区别。3 按数量标志分组所形成的变量数列就是次数分布数列。4 由于离散型变量不能用小数表...