浙江大学数据结构考研专业课试题

《浙江大学数据结构考研专业课试题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、浙江大学数据结构考研专业课试题2001来源：考试点www.kaoshidian.com2001年混合班99“数据结构与算法”试卷　　考试时间：2小时10分　　一、单项选择及填空题(除非特别注明，一般每小题2分，共38分，请选择题答案写在试卷左边)　　1若语句S的执行时间为O(1)，那么下列程序段的时间复杂度为：　　for(i=0;i　　for(j=0;j<=i;j++)　　S;　　A)O(n)B)O(n*n)C)O(nlogn)D)O(n*i)　　2已知一堆栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列：　　A)1234B)4321C)2143D)4123　　3深度为

2、5的二叉树至多有_____个结点.　　A)16B)32C)31D)10　　4堆(HEAP)是一种_____　　A)二叉树B)线性表C)图D)算法　　5若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少?　　A)1和5B)2和4C)4和2D)5和1　　6下列哪种排序算法的平均时间复杂度为O(nlogn)：　　A)简单选择排序B)简单插入排序C)冒泡排序D)归并排序　　7用冒泡排序(交换排序)算法对下列数据进行从小到大排序。在将最大的数“沉”到最后时，数据的顺序是什么?1237

3、42192735564210　　A)123742192735441056http://www.kaoshidian.com/考试点：微支付、高清、全国名师坐镇　　B)123742192735104456　　C)123719273542441056　　D)101219273537424456　　8下列哪种排序算法更适合于外部排序　　A)选择排序B)插入排序C)冒泡排序D)归并排序　　9数据结构中的DIJKSTRA方法是用来求:　　A)关键路径B)最短路径C)拓扑排序D)字符串匹配　　10对下列二叉树进行后序遍历，其遍历结果为：　　a　　bc　　def　　g　　A)gfedcbaB)

4、dbegfcaC)bdecgfaD)dbaecgf　　11稀疏矩阵(SPARSEMATRIX)一般的压缩存储方法有以下两种：　　A)二维数组和三维数组B)三元组(TRIPES)和哈希表(HASHTABLE)　　C)三元组(TRIPES)和十字链表(crosslinked)D)哈希表和十字链表　　12在待排序的元素基本有序的前提下，效率最高的排序方法是：　　A)简单插入排序B)简单选择排序C)快速排序D)归并排序　　13设以单向链表方式表示一个多项式(按指数expon递减方式),请写出链表中节点结构的C语言定义并对其中分量的用途作简要注释：　　14(4分)在简单插入排序、希尔排序、

5、简单选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有：___________________________________________________　　15(4分)请至少给出三种常用的算法设计方法并各给出对应的一个例子http://www.kaoshidian.com/考试点：微支付、高清、全国名师坐镇　　_________________________________________________________________________　　16(4分)按满二叉数的概念可推广出满K叉数的概念。若对满K叉树的节点逐层编号(从1开始，同层中从左到

6、右)，则编号为i的节点的父节点编号是_______________，编号为i的节点的第j个儿子的编号是___________________。　　二、请对下列有向图(共9分)：　　(1)画出相应邻接链表(adjacencylist)表示法(链表中，按节点编号大小从小到大向后排)，　　(2)指出按教材中TOPSORT算法在上述表示的基础上进行遍历的输出结果。　　三、(8分)对于下列二叉树　　(1)请画出其对应的中序线索(thread)　　(2)请将下列用于中序线索二叉树遍历的程序的空白部分填上。　　threaded_pointerinsucc(threaded_pointertre

7、e)　　{　　threaded_pointertemp;　　temp=tree->right_child;　　if(!tree->right_thread)　　while(______________)　　temp=temp->left_child;　　returntemp;　　}　　voidtinorder(threaded_pointertree)　　{threaded_pointertemp=tree;　　for(;;){http://www.kaoshidian.com/