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

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

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2010 年山东师范大学数据结构考研真题一、填空题（40 分。本大题共 9 小题，10 个空，每空 4 分，将应填在下划线处的答案，按填空顺序写在答题纸上）。 1、设有一个二维数组存放 A[m][n]，A[0][0]存放在 644.A[2][2]存放在 676.每个元素占一个地址空间，上述地址用 10 进制表示，A[3][3]存放的位置为（1）。 2、将 f=1+1/2+1/3+...+1/n 转化成递归函数，则递归体是（2）。 3、在结点个数为 n（n>1）的各棵树中，高度最大的树高度是（3），它有（4）个叶结点。 4、用一维数组存放的一棵完全二叉树∶ABCDEFGHIJKL，后序遍历该二叉树的访问结点序列为（5）。 5、假设二叉树中所有非叶子结点都有左右子树，则结点总数为（6）。 6、对用邻接表表示的图进行任一种遍历时，其时间复杂度是（7）。 7、设顺序表为{2，11，16，23，32，45，51，62，73，79，80，94，97}、用折半法查找 94，需要进行比较的次数是（8）。 8、若表中有 256 个记录，采用分块查找时，用顺序查找确定记录所在的块时，则分成（9）块最好。 9、已知一个序列为（21，39，35，12，17，43），利用维排序方法建立的大根初始谁为（10）。二、写算法（本大题共 5 小题，65 分）。 1. 所谓回文，是指从前往后顺读和从后向前倒读都一样的不含空白字符的串。设计一个算法，判断一个字符串是否是回文。（13 分） 2. 已知 Ackerman 函数的定义如下∶ 根据定义，写出它的递归求解算法。（13 分） 3. 某百货公司仓库中有一批电视机，按其价格从低往高的次序构成一个循环链表，每个结点有价格、数量和链接指针三个域。现新到 m 台价格为 h 的电视机，编写一个算法，在保持价格从低往高的次序的情况下，将这些电视机的有关信息插入循环链表。（13 分）

4.写出折半查找的算法。（13 分） 5.写出冒泡排序的算法。（13 分）三、（本题满分 15 分）。利用 Dijkstra 算法求下图中从顶点 1 到其它各顶点间的最短路径，按下面给出的表格形式在答题纸上写出执行算法过程中各步的状态。四、（本题满分 15 分）。设有一段正文由字符集{A，B，C，D，E，F}中的字母组成，这 6 个字母在正文中出现的次数分别为{12，18，26，6，4，34}。 1.为这 6 个字母设计哈夫曼编码;

2.设每个字节由 8 位二进制位组成，请计算按哈夫曼编码存储该段电文共需多少字节。五、（本题满分 15 分）。设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数∶ H(key)=key MOD 13 采用开放定址法的线性探测再散列方法解决冲突，试在 0`18 的散列空间中对该关键字序列构造哈希表。（构造结果填写在答题纸中，以下列表的形式完成，其中第一行为地址，第二行根据算出来的地址填写关键字值）。

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料