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

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

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2009 年山东师范大学数据结构考研真题一、填空题（40 分。本大题共 9 小题，10 个空，每空 4 分，将应填在下划线处的答案，按填空顺序写在答题纸上） 1.二维数组 A[10][20]采用列序为主的方式存储，每个元素占一个存储单元，A[0][0]为第一个元素，存储地址是 200，则 A[612]的地址是（1）。 2. 在具有 n 个元素的循环队列中，队满时共有（2）个元素。 3. 一棵有 n（n>0）个结点的满二叉树共有（3）个叶子和（4）个非终端结点。 4. 将 f=1+1/2+1/3+..+1/n 转化成递归函数，则递归体是（5）。 5. 具有 6 个顶点的无向图至少应有（6）条边才能确保是一个连通图。 6. 对用邻接表表示的图进行任一种遍历时，其时间复杂度是（7）。 7.假设在有序线性表 A[1...20]上进行二分查找，则比较四次查找成功的结点个数为（8）。 8. 若表中有 625 个记录，采用分块查找时，用顺序查找确定记录所在的块时，则分成（9）块最好。 9.对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第 7 个记录 60 插入到有序表时，为寻找插入位置，需比较（10）次。二、写算法（本大题共 5 小题，65 分） 1. 针对带表头结点的单链表，编写算法，求单链表中具有给定值 x 的元素个数。（13 分） 2. 设计一个算法，将 A[0.n-1]中所有奇数移到偶数之前，要求不另增加存储空间，且时间复杂度为 O（n）。（13 分） 3.在图的邻接表结构上，写一个非递归优先遍历算法。（13 分） 4. 某百货公司仓库中有一批电视机，按其价格从低往高的次序构成一个循环链表，每个结点有价格、数量和链接指针三个域。现新到 m 台价格为 h 的电视机，编写一个算法，在保持价格从低往高的次序的情况下，将这些电视机的有关信息插入循环链表。（13 分） 5. 设算术表达式由字符串 b 表示，其中可以包括三种括号∶圆括号、方括号和花括号，嵌

套的顺序任意，如{[（）]（）}是正确的。请编写一个算法，实现判别给定表达式中所含括号是否正确配对。（13 分）三、设有一组关键字;{19，01，23，14，55，20、84、27，68，11，10.77};，采用哈希函数∶ H(key)=xkey MOD 13 采用开放定址法的线性探测再散列方法解决冲突，，试在 0'18 的散列空间中对该关键字序列构造哈希表。（构造结果填写在答题纸中，以下列表的形式完成，其中第一行为地址，第二行根据算出来的地址填写关键字值）四、已知一棵二叉树，如图所示∶ （1）画出该二叉树的后序线索二叉树（2）画出该二叉树对应的森林（15 分）五、下面画出了一个 AOE 网表示各工序之间的优先关系和各工序所需时间，求∶ （1）列出各事件的最早最迟发生时间∶

（2）找出该 AOE 网中的关键路径，并回答完成该工程所需要的最短时间（15 分）。按下面给出的表格形式在答题纸上写出事件的最早最迟发生时间。

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料