《中山大学移动信息工程学院《902专业基础》(数据结构A)[专业硕士]历年考研真题汇编》由会员分享，可在线阅读，更多相关《中山大学移动信息工程学院《902专业基础》(数据结构A)[专业硕士]历年考研真题汇编（16页珍藏版）》请在金锄头文库上搜索。
1、目录2015年中山大学918专业基础（数据结构）专业硕士考研真題52014年中山大学907专业基础A （数据结构）专业硕士考研直題92013年中山大学867专业基础（数据结构）专业硕士考研直题162012年中山大学909专业基础（数据结构）专业硕士考研頁題232012年中山大学913专业基础（数据结构）专业硕士考研真题292011年中山大学913专业基础（数据结构）【专业硕士考研頁題362010年中山大学908专业基础（数据结构）专业硕士考研真題43说明:中山大学“专业基础（数据结构）I专业硕士”的科目代码每年都不同,2016年改为“902专业基础（数 据结构A）专业硕本书书名以此为准。201
2、5年中山大学9IX专业基础(故据堵构)|专业硕士考硏頁題中山二O五年攻读硕士学位研究生入学考试试题考生须知全部答案一律写在答题紙 上，答在试题纸上的不计分!答 成要写淸题号，不必抄题。科目代码：918科目名称：专业基础(数据结构)考试时间：12月28日下午考试完毕,试题随答嵋纸一起交冋。第1页共4页请问小明用的是什么排序算法？A.选择排序B.归并排序 C快速排序D.插入排序10. 以下的排序算法中，哪个算法在最坏情况下的时间复杂度是。（/）?A.堆排序B.快遥排序C.归并排序D,基数排序11. 给定一个算术表达式x.X的中缀形式是A*B 欄根是（）A. 3, 37 B. 3.24 C. 4,
3、37 D. 3, 5313下面哪个函数髄着n增大而增长得最怏？（）.A. 100n1 2log2n B n（log2n）s C. n21 D. n + lOOOnJoggn14、一个有n个顶点的无向图最多有（）条无向边（假设该图无自环）.A n B.n（n-l） G n（n-l）/ D. 2n15、一棵高度为k的二叉树最多有（）个节点A. 2kf|-l B. 2七 1 G 2k4-l D. 2k+l二、简答题（共55分）1. （11分给定一个整数数组4,632丄5,7.假设用选择排序算法对数组中的整数进行从小到大择 序。淸写出每次迭代后数组中的状态（即每次迭代后，数组中的7个整数是如何排序的）
4、2. （】1分）从空的二叉樹开始，根据字典顺序，严格按照二叉拜序树（或称二叉搜索树）的插入算 法，依次插入e, b, d, f, a, g, c。请画岀构造二叉排序树的每一步骤。3. （10分）假定一个堆为（56.38,42,30,25,4055.20）,则依次从中删除两个元素后得到的堆是什么？ 要求画出过程。4. 给定一个空的哈希表，依次把键12,34, 55, 54, 13, 21, 19, 70插入到哈希表中.假设采用的哈希函 数是h（k）=kmod 11,釆用线性探査（linearprobing）来解决冲突（1）当上述键值全部插入后，遺画出哈希表的状态（6分）（2）假如每个键值被査找的
5、概率均等，清计算出平均査找长度（avemge search length ） （6分）下标112J45 I64一8910 |键1-ZJ5.给定图G如下第3页共4页三. 編再覇(共50分1. (10分)以下是一个(不完整的)少接插入排序算法的代码，清根据注拜的提示把饿少狄 码补充完赛.void lnsertlon_sort(int entryQ, int count)int first_unsorted;/ position of first unsorted entryint position;U searches sorted part of listint current;/ holds
6、the entry temporarily removed from listforffirst unsorted = 1; first_unsorted count; first_unsorted) _if(entryfirst_unsorted entryfirst_unsorted -1) - -/p/ease complete the code here2. CIS分)逆转链衰：写一算法逆置帯头结点的单链表L,要求逆置后的单链衰利用L中的原结点. 不可以重新申请姑点空间.链去结点的声明如下，templote struct NodaEntry data;Node 9 next;；清实说下
7、面的函数：void reverse (Nodee L)3. (25分)写-个算法，逐层遍历一棵二又树(从上到下，从左到右)以卜是二又树及二叉树 中的节点的声明：temp/ate class Entryclass Ofnarytree public:Blnory_tree();void Layer_order(voM( vfsitjf Binary_ node &);protected:Binoryn ode root;template struct Binary_ncde(Entry data;Bir)ary_nodevEatry left;Binary_node* right：Bincry_
8、node();Binary node(const Entry &x);请实现下面的函数： void Layer_order(void(*visit)( Entry &|).第4页共4页2014年中山大学907专业基础A (数据结构)I专业硕士鹿研真题中山大学二。一四年攻读硕士学位研究生入学考试试题考生须知全部答案一律写在答题维上， 答在试黝纸上的不计分！答题要写 清题号，不必拶題.科目代码：907科目名称：专业基础A (数据结构)考试时间：1月5日下午 一、单项选择誣(每题2分，共40分)1. 算法复杂度通常是表达算法在最坏情况下所需要的计算员。一般不用来表达算法复杂度的表 达式为().(A)
9、.詢)(B). 0(100)(0成別。驮)(D). 0(1-5-)2. 数据培构有四类基本结构,不是其四类结构之一的是().(A).集含(B).线性结构(C).存储结构(D).树形结构3. 在存储信息过程中，通过对关键字的计算来确定其存储位置的数据结构是().(A). Hash表(B).二叉捜索树(C).链式结构(D),顾序结构4. 有关单向链表的正确描述是().(A).在0(1)时间为找到指定的关靈字(B)在插入和麗除操作时无需移动链表结点(C).在0(1)时间内删除指定的关權字(D).单向链表的存储效率高于数組的存储效率5. 假设Head是不带头结点的双向循环链的头纸点指针判断链表为空的条
10、件是()6.7.(A). Head = NULL(C). Hcad.next = NULL 在下列关于“字符串”的陈述中，(A).字符串一定有一个结束符(C) “空申”与“空白串”是同一个含义 关于队列的不正确描述是().(A). FIFO(C).可访问队列中任何元素(B). Head-next = Head(D). Hcad-next = NULL 正确的描述是().(B).字符串只能用连续存储空间来存储(D).字符串是一和特殊的线性表(B).可用鮭表实现动态队列P),可用动杏连续存储空间实现动态队列考试完毕，试题随答题纸-起交冋.第1页共7页8. 假设循环队列的长度为QSize,其头，尾下
11、标分别为From和Rear.在队列不满的情况下L入 队”后相应下标变化的语句为().(A). Rear= Rear+ 1(B). Rear= (Rear+ 1) % Qsize(C). Front -Front + 1(D). Front = (Front* I)% QSize9. 用链表来实现堆栈，next是舞表结点中的指针字段，Top为栈顶指針。在确定堆栈非空的情况 下，出栈的语句是()，其中：所有变量都合法定义了，free(Point)是释放指针Point所指 向的存储空间.(A). Top = Top-next;(B). free(Top); Top = Topnext;(C). To
12、p = Top-next; free(Top); (D). Pt=Top; Top = Top-next; free(Pt);10. 设A1010为一个对称炬阵，数组下标从开始.为了节省存储，将其下三角部分按行存放在一樂数组Bl0.54Jo所对应的数组元素()。(A).A3(8(B). A2J8(C).A(37J(D).A 711. 若一棵二又树的后序和中序序列分别是dfebca和物物c,她其先序序列是().(A), abdfec(B) abdefc(C). acbdef(D). ocbefd12. 用一维数组来存储满二叉树，若数组下拆从0开始，则元素下标为瓦总:0)的左子结点下标是(X不考虑
13、数组下标越界问题)(A). 2*-1(B).2t(C).21(D). ZH-213. 假设71和乙是二叉搜索树7的左右子树，(7)表示树7的高度。若树7是4皿树，则 ()(A).狀几)-丑)=0(B). i/m - nm=1(C). H(7Z) - 8(7) 1(D). Hm - 114. 用邻接短阵存储有”个项点(0,.kl)和。条边的无向图(0尘5止1)/2)。在图中没有无向边 (i,力(04JSI)的情况下，増加此边后，修改邻接矩阵的时间复杂度是()(A). 0(1)(B).物(C).m)(D).e)15. 用邻接矩阵存储有n个项点(0,l,.;n-l)和e条边的有向图(0ein(?-l
14、).计算结点，(0坎”.1)入 度的时间复杂度是().(A). 0(1)(B). X).0(。)(D).m+e)16. 下列排序算法中，时间复杂度最菱的是().(A).选择排序(B).归并排序(C).快速排序(D).堆掉序17. 对个数进行择序时，对基于比较的排序算法，其时间复杂度下界为().(A).。()(B).次1。函(C).剛。歆)(D). 0(n)18. 用基数(桶)排序算法对仅由字母和数字组成字符率进行排序(不区分字母大小写)时，需要桶的 个数是().A). 10(B). 26(C).36(D). 6219. 假设有个无序关键字，有关其查找算法的不正确描述是().(A).关键字可存储在数组中(C).关键字可存储在单向链表中(C).最坏搜索效率
