深圳大学计算机与软件学院907数据结构与算法历年考研真题答案汇编17p

《深圳大学计算机与软件学院907数据结构与算法历年考研真题答案汇编17p》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、名般最新资料WORD格式f可编辑修改!2013年深圳大学计算机与软件学院831数据结构与算法考研真题32012年深圳大学计算机与软件学院819数据结构与算法考研真题82011年深圳大学计算机与软件学院811数据结构与算法考研真题13说明：数据结构与算法科目代码每年都不同。2016年科目代码是907z本书以此为准。2013年深圳大学计算机与软件学院831数据结构与算法考研真题深圳大学2013年硕士研究生入学考试初试试题（答题必须写在答题纸上，写在本试题纸上无效）考试科目代码：819考试科目名称:数据结构与算法专业:计算机科学与技术、软件工程、模式识别与智能系

2、统一、判断题（每小题2分，共14分。给正确的打U错误的打“X”）1、数据的逻辑结构说明数据元素之间的次序关系，它不依赖于计算机的存储结构2、线性表的特点是每个元素都有一个前驱和一个后继3、冒泡（起泡）排序算法是一种稳定的排序算法4、在n个结点的无向图中，若边数大于叶1,则该图必是连通图5、任何一棵树都可以先转换成二叉树，再用二叉链表进行存储6、用单链表和顺序表表示的有序表均可使用折半查找方法来提高查找速度7、快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少二、选择题（每小题3分，共18分。在以下每小题给出的4个选项中只有一个是正确的）1、对于顺

3、序存储且长度为n的的线性表，访问结点和增加结点的时间复杂度为（Av0（n）0（n）B、0（1）0（n）C、0（n）0（1）D、0（1）0（1）2、设一个链表最常用的操作是在表尾插入结点和删除表尾结点，则选用（）最节省时间。A、单循环链表B、带尾指针的单循环链表C、带头结点的双向循环链表D、单链表3、含有n个顶点和e条边的无向图的邻接矩阵中，零元素（表示两个顶点之间没有边）的个数为（A、『B、0(1)0(n)C、0(n)0(1)）0)oB、e4、栈和队列的共同特点是（）A、都是先进先出C、只允许在端点处插入和删除元素5、设Huffman树中的叶子结点总数为n

4、,有（）个空指针域。D、n-2eA、2nB、2n_1B、都是后进先出D、没有共同点若用二叉链表作为存储结构,则该Huffman树中总共C、2n+1D、4nB、串中所含字符的个数D、串中所含不同字符的个数6、串的长度是指（）A、串中所含非空格字符的个数C、串中所含不同字母的个数三、填空题（每小题3分，共18分）1、数据结构中，算法是指2、for（j=1;j<=n;j*二2）;的时间复杂度为03、用数组intA[20]实现循环队列，front,rear分别指向队头和队尾，则判断队空的语句为,判断队满的语句为。4、一棵高度为6的二叉树中，最少含有个结点，最多含有

5、个结点。5、在对m阶的B-树插入元素的过程中，每向一个结点插入一个索引项（关键字）（叶子结点中的索引项为关键字和空指针）后，若该结点的索引项（关键字）数等于个,则必须把它分裂为个结点。6、模式串bcbbcd的next值为。应用题四、某无向网的邻接表如下所示，其中i:->j,w表示边（i,j）的权值为w,1、请画岀该无向网；2、请用克鲁斯卡尔算法（Kruskal）或者普里姆算法（PCm）（从结点2开始）求最小生成树，并输出树的生长过程。（10分）1:->2:->3:->2,21,21.93,93.32.34,4->5,8八5,r4,E4:->1,43,65:

6、->1,82.74,5五、有一棵树，如右图所示，1、请求出该树的后根遍历序列；2、请画出该树对应的二叉树，并求岀其先根遍历序列。（10分）六、画出在初始为空的二叉排序树中依次插入54,41,43,66,74,58,42,59时该树的生长全过程;请画出在该二叉排序树中删除节点54后的处理结果（请说明删除结点操作的原理）。（10分）七、对给定序列33,51,42,23,26,35,43,18选择第一个元素（33）进行划分，写出其快速排序第一趟的排序过程。（10分）八、已有中缀表达式2+3*4,请利用运算符顺序栈0PTR将其转换为后缀表达式，并存放到字符串S中。

7、设栈空时，栈顶指针top二0；请画岀转换过程中每一步（每处理中缀表达式中一个操作数或一个运算符为一步），栈的内容及栈顶指针的变化状态，以及S的内容，并请最后写出转换后的后缀表达式。（10分）九、假设关键字输入顺序为21,31,15,27,19,24,17,13,已知散列（哈希）表长为10（从0〜9进行编址），散列（哈希）函数采用平方取中法，用线性探测再散列开放定址法解决冲突，1、请画出插入所有关键字后得到的散列表，并指出发生碰撞的次数；2、假设每个关键字的查找概率相同，请计算该散列表查找成功的平均查找长度。（10分）十、请用简单选择排序对序列18,21,5

8、4,11,37,43,15,28,33进行升序排序（要求写岀排序过