2007年山东师范大学数据结构考研真题.doc

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

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2007 年山东师范大学数据结构考研真题一、填空题（40 分。本大题共 9 小题，10 个空，每空 4 分，将应填在下划线处的答案，按填空顺序写在答题纸上） 1.设有一个 10x10 的对称矩阵 A[10][10]，采取上三角矩阵按行压缩存储的方式存放于一个一维数组 B[]中，A[0][0]为第一个元素，存放于 B[0]，[A]中每个数据元素在 B[]中占一个位置，则 A[8]5]在数组 B[]中的位置为（1）。 2.向一个长度为 n 的向量的第 i 个元素（1≤i≤n+1）之前插入一个元素时，需向后移动（2）个元素。 3. 一棵有 n（n>0）个结点的满二义树共有（3）个叶子和（4）个非终端结点。 4.用一维数组存放的一棵完全二叉树∶ABCDEFGHIJKL.后序遍历该二叉树的访问结点序列为（5）。 5. 具有 6 个顶点的无向图至少应有（6）条边才能确保是一个连通图。 6. 对用邻接表表示的图进行任一种遍历时，其时间复杂度是（7））。 7.假设在有序线性表 A[1.20]上进行二分查找，则比较四次查找成功的结点个数为（8）。 8. 若表中有 256 个记录，采用分块查找时，用顺序查找确定记录所在的块时，则分成（9）块最好。 9.对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第 7 个记录 60 插入到有序表时，为寻找插入位置，需比较（10）次。二、写算法（本大题共 5 小题，65 分） 1.针对带表头结点的单链表，编写算法，求单链表中具有给定值 x 的元素个数。（13 分） 2. 所谓回文，是指从前往后顺读和从后向前倒读都一样的不含空白字符的串。设计一个算法，判断一个字符串是否是回文。（13 分） 3. 已知 Ackerman 函数的定义如下∶ 根据定义，写出它的递归求解算法。（13 分）

4.在二叉树中查找值为 x 的结点。假设值为 x 的结点不多于一个，打印出值为 x 的结点的所有祖先。 5. 写出快速排序的算法。（13 分）二、设有一段正文由字符集{A,B,C,D,E,F}中的字母组成，这 6 个字母在正文中出现的次数分别为{12，18，26，6，4，34）。 1.为这 6 个字母设计哈大曼编码; 2. 设每个字节由 8 位二进制位组成，请计算按哈夫曼编码存储该段电文共需多少字节。（15 分）四、已知一棵二义树，如图所示∶ （1）画出该二叉树的后序线索二又树

（2）画出该二叉树对应的森林（15 分）五、下面画出了一个 AOE 网表示各工序之间的优先关系和各工序所需时间，求∶ （1）列出各事件的最早最迟发生时间; （2）找出该 AOE 网中的关键路径，并回答完成该工程所需要的最短时间（15 分）。按下面给出的表格形式在答题纸上写出事件的最早最迟发生时间。

分享到：

赞收藏

资料库

2007年山东师范大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料