2004年山东大学数据结构考研真题.doc

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

第1页 / 共2页

第2页 / 共2页

文本预览

2004 年山东大学数据结构考研真题一、简答题： 1、10 分（1）数据结构和数据类型的区别，一个好的数据结构类型有哪几个标准？（2）顺序和链式存取的特点是什么，什么时候顺序存取有优势？ 2、12 分 g（m，n）=0(m=0,n>=0)=g(m-1,2n)+n(m>=0,n>=0) 写出递归算法并画出 g(5,2)的栈的变化。 3、8 分求下列算法里@区域的时间执行频度和整个算法最时间复杂度。 X=0,y=0; For(i-1;i++;i<=n){ Ifodd(i) @{for(j=i;j++;j<=n)x++; For(j=i;j++;j<=i)y++;} } 4、10 分 a(x)=7+3x+9x^8+5x^17b(x)=8x+22x^7-9x^8 (1)画出 a(x)和 b(x)的单链表的存储表示，做一下结构说明。 (2)执行插入删除运算得出 a(x)+b(x)的存储表示，利用 a(x)和 b(x)原有的空间。 5、6 分有中序线索 2 叉树序列 cbedahgijf,后续序列：cedbhjigfa,画出前序、中序和后序的线索二叉树。 6、6 分树的度为 m，度为 1 的结点数为 N1,度为 2 的结点数为 N2,度为 m 的结点数为 Nm, 求树的叶子结点数。 7、8 分无向图 G=（V，E），G 的各顶点的度>=2，证明这个无向图中一定含有回路。 8、10 分求关键路径。 9、8 分，平衡 2 叉树中的插入元素调整平衡的过程。

10、8 分，什么是哈希表？冲突可能与哪些因素有关？为什么？ 11、8 分，有 5000 个无序列的元素，如果要快速选择最大的 10 个元素，那么在快速、堆、归并、基数、希尔排序中哪个最好，为什么？ 12、10 分，n 个不同的英语单词排序，长度均为 m,n>>50,m<5,那种排序方式最佳？为什么？二、算法设计题目： 1、8 分，写折半查找（2 分法）的递归算法 2、8 分，三叉堆（同去年的题目） 3、10 分，设计选举人得票数，按得票数输出，一张选票只能选一个被选举人，一共有 n 个被选举人，m 张选票。 4、8 分，P 是中序线索 2 叉树的非根接点，写出不用栈删除 P 的子树的算法。 5、12 分，写出 2 叉中序非递归的算法。

分享到：

赞收藏

资料库

2004年山东大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料