2018年山东工商学院数据结构考研真题A卷.doc

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

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2018 年山东工商学院数据结构考研真题 A 卷一、简答题（共 4 题，每题 10 分） 1.简述数据的逻辑结构和存储结构的区别与联系? 2.在单链表、双链表和单循环表中，若仅知道指针 p 指向某结点，不知道头指针，能否将结点*p 从相应的链表中删去?若可以，其时间复杂度各为多少? 3.比较栈和队列两种数据结构的异同，举例说明哪些算法中，会用到栈或者队列。 4.对比分析简单选择排序和堆排序两种算法。二、应用题（共 6 题，每题 15 分） 1.什么是二叉树的前序、中序和后序遍历。写出下图二叉树的前序、中序和后序遍历。

2.简述哈夫曼编码的基本思想。假设用于通讯的电文由字符集{A，B，C，D，E，F}中字符构成，各字符出现的次数分别为{2，8，6，7，10，3}，要求∶ （1）画出对应的 Huffman 树（请按照左孩子的权值比右孩子的权值小的原则构造），计算加权路径长度 WPL。（2）写出每个字符的哈夫曼编码。 3.简述 Prim 算法的基本思想。请写出使用 Prim 算法，构造出下图所示的带权值图的一棵最小生成树的过程。 4.什么是散列表?什么是散列冲突?设散列表的长度 m=13;散列函数为 H（K）=Kmod m，给定的关键码序列为 19，14，23，01，68，20，84，27，55，11，试画出用线性探查法解决冲突时所构造的散列表。并求出在等概率情况下，这种方法的搜索成功时的平均搜索长度。 5.简述直接插入排序算法的基本思想。已知待排序记录的关键字序列为{83，69，41，22， 15，33，8}，用直接插入排序法按从小到大顺序写出每趟排序的结果，直到排序结束

6.简述图的深度优先遍历算法的基本思想。已知一个图的邻接表如下，画出对应的图，请写出从顶点 C0 出发按深度优先遍历时得到的顶点序列。三、编程题（共 2 题，每题 10 分。先描述算法基本思想，然后给出代码。） 1 已知数组 a[n]中的元素为整型，设计算法将其划分为左右两部分，左边所有元素为偶数，右边所有元素为奇数，要求算法的时间复杂度为 0（n）。 2 已知二叉树中的结点类型用 BinTreeNode 表示，被定义为; 其中 data 为结点值域，leftChild 和 rightChild 分别为指向左、右孩子结点的指针域，根据下面函数声明编写求一棵二叉树高度的算法，该高度由函数返回。假定根结点的层次为 0，参数 BT 初始指向这棵二叉树的根结点。 int BTreeHeight (BinTreeNode* BT);

分享到：

赞收藏

资料库

2018年山东工商学院数据结构考研真题A卷.doc

相关推荐

考研

热门标签

最新资料