1999年上海华东师范大学数据结构考研真题.doc

发布时间：2022-09-19 发布人：admin 分类：说明书资料大小：0.07M 资料格式：doc 举报版权申诉

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

1999 年上海华东师范大学数据结构考研真题一、简答题（共 52 分） 1.数据结构主要介绍哪三方面的内容?（6 分） _______________________________________________________________________________ _______________________________________________________________________________ _______________________________________________________________________________ ____________________________________________ 2.分别写出循环队列队空条件和队满条件。（6 分） _______________________________________________________________________________ _______________________________________________________________________________ _______________________________________________________________________________ ____________________________________________ 3.画出下图中树的一种存储结构，再将这个树转换为二叉树，画出这个二叉树的二种存储结构。（8 分） _______________________________________________________________________________ _______________________________________________________________________________ _______________________________________________________________________________ ________________________________________ 4.如果一个树有 n1 个度数为 1 的结点，n2 个度数为 2 的结点，……，nm 个度数为 m 的结点，请推导出该树有多少个叶结点.（8 分） _______________________________________________________________________________ _______________________________________________________________________________

_______________________________________________________________________________ ____________________________________________ 5.写出下图的邻接矩阵，下图中有多少个不同的生成树?画出全部最小生成树.（8 分） _______________________________________________________________________________ _______________________________________________________________________________ _______________________________________________________________________________ ____________________________________________ 6.对于关键字序列 40，15，80，2i;50，画出堆 s 排序的各趟建堆、排序的结果。（8 分） _______________________________________________________________________________ _______________________________________________________________________________ _______________________________________________________________________________ ____________________________________________ 7.分别写出冒泡排序和快速排序的平均时间复杂度，分别写出顺序查找和二分查找的平均查找长度（在等概率假设下）。（8 分） _______________________________________________________________________________ _______________________________________________________________________________ _______________________________________________________________________________ ____________________________________________ 二、假设在一个单循环链表中，既无头结点也无头指针，S 为指向链表中某个结点的指针，写一算法删除结点 S 个的直接前趋结点和直接后继结点。（10 分） _______________________________________________________________________________ _______________________________________________________________________________ _______________________________________________________________________________

____________________________________________ 三、写出实现图的深度优先搜索的非递归算法。（10 分） _______________________________________________________________________________ _______________________________________________________________________________ _______________________________________________________________________________ ____________________________________________ 四、写一算法实现归并排序中的三路归并排序。（12 分） _______________________________________________________________________________ _______________________________________________________________________________ _______________________________________________________________________________ ____________________________________________ 五、写一算法判断一个二叉树是否为一个平衡的二叉排序树。（16 分） _______________________________________________________________________________ _______________________________________________________________________________ _______________________________________________________________________________ ____________________________________________

分享到：

赞收藏

资料库

1999年上海华东师范大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料