4. 设有向图 G 用邻接矩阵 A[n][n]作为存储结构，则该邻接矩阵中第 i 行上所有元素之和
等于顶点 i 的________，第 i 列上所有元素之和等于顶点 i 的________。
5. 设哈夫曼树中共有 n 个结点，则该哈夫曼树中有________个度数为 1 的结点。
6. 设有向图 G 中有 n 个顶点 e 条有向边，所有的顶点入度数之和为 d，则 e 和 d 的关系
为_________。
7. __________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序
或后序）。
8. 设查找表中有 100 个元素，如果用二分法查找方法查找数据元素 X，则最多需要比较
________次就可以断定数据元素 X 是否在查找表中。
9. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均
为____________。
10. 设有 n 个结点的完全二叉树，如果按照从自上到下、从左到右从 1 开始顺序编号，则
第 i 个结点的双亲结点编号为____________，右孩子结点的编号为___________。
11. 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字 72 为
基准的一趟快速排序结果为___________________________。
12. 设有向图 G 中有向边的集合 E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该
图的一种拓扑序列为____________________。
13. 下列算法实现在顺序散列表中查找值为 x 的关键字，请在下划线处填上正确的语句。
struct record{int key; int others;};
int hashsqsearch(struct record hashtable[ ],int k)
{
int i,j; j=i=k % p;
while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);}
if (_______________________ ) return(j); else return(-1);
}
14. 下列算法实现在二叉排序树上查找关键值 k，请在下划线处填上正确的语句。
typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree;
bitree *bstsearch(bitree *t, int k)
{
if (t==0 ) return(0);else while (t!=0)
if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________;
}
三、计算题(每题 10 分，共 30 分)
1.已知二叉树的前序遍历序列是 AEFBGCDHIKJ，中序遍历序列是 EFAGBCHKIJD，画出
此二叉树，并画出它的后序线索二叉树。
2．已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为 [0..6]，假
定选用的散列函数是 H（K）= K mod 7，若发生冲突采用线性探查法处理，试：
（1）计算出每一个元素的散列地址并在下图中填写出散列表：
` 0 1 2 3 4 5 6
（2）求出在查找每一个元素概率相等情况下的平均查找长度。
3．已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。
四、算法设计题(每题 15 分，共 30 分)
8
剩余41页未读，继续阅读
qq_27243353
- 粉丝: 0
- 资源: 2
我的内容管理
展开
最新资源
- 计算机人脸表情动画技术发展综述
- 关系数据库的关键字搜索技术综述：模型、架构与未来趋势
- 迭代自适应逆滤波在语音情感识别中的应用
- 概念知识树在旅游领域智能分析中的应用
- 构建is-a层次与OWL本体集成：理论与算法
- 基于语义元的相似度计算方法研究：改进与有效性验证
- 网格梯度多密度聚类算法：去噪与高效聚类
- 网格服务工作流动态调度算法PGSWA研究
- 突发事件连锁反应网络模型与应急预警分析
- BA网络上的病毒营销与网站推广仿真研究
- 离散HSMM故障预测模型：有效提升系统状态预测
- 煤矿安全评价：信息融合与可拓理论的应用
- 多维度Petri网工作流模型MD_WFN：统一建模与应用研究
- 面向过程追踪的知识安全描述方法
- 基于收益的软件过程资源调度优化策略
- 多核环境下基于数据流Java的Web服务器优化实现提升性能
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
