《2014年中南大学943数据结构考研真题》由会员分享，可在线阅读，更多相关《2014年中南大学943数据结构考研真题（4页珍藏版）》请在金锄头文库上搜索。
1、 中南大学2014年硕士研究生入学考试试题考试科目代码及名称：943数据结构注总：1、所有答案（含迭择题、填空题、判断题、作图懸等）一律答在专用答题纸上，写在试題纸上或其 他地点一律不给分.2、作图題可以在原试题图上作答，然后将图”撕下来贴在答题紙上相应位負3. 考试时限3小时9总少】50分.考生编号（考生填写）| / | 3 I next=s;p-next=s-next; D. p-next=s-next;p-next=s;3.设有数组Aij,数组的每个元素长度为3宇节，i的值为1到8 , j的值为1到10,数组 从内存首地址S开始顺序存放，当用以列为主存放时，元素A5, 8的存储首地址为（
2、）。2. 在单链茨指针为p的结点之后插入指针为s的结点，正确的操作是:+141 B. S+180 C. S+222 D. S+2254. 己知广义表:A=仏求下列运5. 设无向图的顶点个数为m则该图最多有()条边。A. n-1/n(n-l)/2 C n(n+l)/2 D n26. 初始状态为递增序列的表按邂增咽序排序,最省时间的是()算法A.堆排序B.快速排斥W插只排序D. g并排序7. 下面程序段的时间复杂度为()。八fbr( i=0; im; i+)for(j=0;jsubString(s 1 ,Strlength(s2),2)的结果串是()A. BCDEF B. BCDEFG C. BC
3、PQRST/BCDEFEF11已知一棵完全二叉树的第6层(设根为第1层甬8个叶子结点，则韶二叉树的结点个数量多是/X 39 B52 对1町 D. 119( 纟耳山 12.设一组初始记录关键字序列为(占，孟，去星,乙7,鱼83, 90, 115, 134),则利 用二分法查找关键字90需舉比较的关键字个数为().A. 12C. 3D. 4具有n个结点的满二叉树有()个叶结点。A. n/2 ； B/ (n+l”2； C(nl”2；D. n/2+lo在常用的描述二叉排序树的存储结构中，关键字值最大的结点()A左指针一定为空喊右指针一定为空C.左右指针均为空D.左右指针均不为空B. 5213.14.)
4、取其值域的每个值.15.散列函数有一个共同的性质，即函数值应当以(A.最大概率 B.最小概車C.平均槪率7同等概率三. 名词解释（每小题2分，共】0分）1. 内部排序2. 算法3. 二叉树4. 平均査找长度（Average Search Length）5. 平衡因子 BF（Balance Factor）：四. 算法应用题（每小题8分，共48分）1. 对给定数据（18, 04, 28, 11, 50, 16, 80, 19, 60, 31）选择第一个元素18进行划 分，写出其快速排序第一遍的排序过程。2. 有七个带权结点，其权值分别为3,7,8,2,6,10,14,试以它们为叶子结点构造一棵哈夫
5、曼 树，并计算出带权路径长度WPL.3. 有一个10000项线性表，若采用等分区间顺序查找（索引顺序查找）方法进行資找，问：a）每块的理想长度为多少？b）分成多少块较为理想？c）平均査找长度为多少？d）若每块长度为40,则平均查找长度为多少？4. 已知二叉树的前序遍历序列是AEFBGCDHIKJ,中序遍历序列是EFAGBCHK1JD,画 出此二叉树，并画出它的后序线索二:5. 设哈希表长度为11,哈希函数H （K） = （K的第一字母在字母表中的序号）MOD11, 若输入顺序为（D, BA, TN, M, CI, I, K, X, TA）,处理冲突方法为线性探测再散 列或链地址法，要求构造哈希表，并求出箸概率情况下査找成功平均查找长度。6. 假设P是图G中从结点s到结点t的一条最短路径，而w是路径P上的任一结点。证 明：沿着路径P上从S到XV的子路径一定是从结点S到结点W的一条最短路径。（提示: 可考虑用反证法）。五. 算法设计题（每小题14分，共42分/1. 已知线性表（al, a2,a3,an）按顺序存储，且每个元素都是整数均不相同，设计把 所有偶数移到所有奇数前边的算法。（要求时间最少，辅助空间最少）。2. 给定一不带权值有m条边的连通图G,设计一个时间复杂度为0（“的算法构造图G的一棵 生成树。3. 编写算法求二叉树中以值为x的结点为根的子树的深度。
