《(NEW)浙江理工大学信息学院《991数据结构》历年考研真题汇编》由会员分享，可在线阅读，更多相关《(NEW)浙江理工大学信息学院《991数据结构》历年考研真题汇编（50页珍藏版）》请在金锄头文库上搜索。
1、目录 2014年浙江理工大学信息学院991数据结构考研真题 2013年浙江理工大学信息学院991数据结构考研真题 2012年浙江理工大学信息学院991数据结构考研真题 2011年浙江理工大学信息学院991数据结构考研真题 2008年浙江理工大学信息学院935数据结构考研真题 2007年浙江理工大学信息学院435数据结构考研真题 2014年浙江理工大学信息学院991数据结构 考研真题 浙江理工大学 2014年硕士学位研究生招生入学考试试题 考试科目：数据结构 代码：991 （请考生在答题纸上答题，在此试题纸上答题无效） 一、单选题：（每小题2分，共30分） 1不带头结点的单链表simple Li
2、st为空的判定条件是_。 Asimple List = null Bsimple List-next = null Csimple List-next = simple List Dsimple List！= null 2某线性表最常用的操作是在最后一个结点之后插入一个结点或 删除第一个结点，故采用_存储方式最节省运算时间。 A单链表 B仅有头结点的单循环链表 C双链表 D仅有尾指针的单循环链表 3向一个栈顶指针为top的链栈中插入一个S所指结点时，则执行 _。 Atop-next = S； BS-next = top-next top-next = S； CS-next = top； top
3、 = S DS-next = top； top = top-next； 4一维数组和线性表的区别是_。 A前者长度固定，后者长度可变 B后者长度固定，前者长度可变 C两者长度均固定 D两者长度均可变 5设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按 行序存放在一维数组B1, n（n-1）/2中，对任一下三角部分中任一元素 aij（）,在一组数组B的下标位置K的值是_。 Ai（i-1）/2+j-1 Bi（i-1）/2+j Ci（i+1）/2+j-1 Di（i+1）/2+j 6在线索化二叉树中，P所指的结点没有左子树的充要条件是 _。 AP-left = null BP-ltag =1 C
4、P-ltag =1 且 P-left =null D以上都不对 7如果Tree2是由有序树Tree1转换而来的二叉树，那么Tree1中结 点的后序就是Tree2中结点的_。 A先序 B中序 C后序 D层次序 8判定一个有向图上是否存在回路除了可以利用拓扑排序方法 外，还可以用_。 A求关键路径的方法 B求最短路径的Dijkstra方法 C广度优先遍历算法 D深度优先遍历算法 9采用邻接表存储的图的深度优先遍历算法类似于二叉树的 _。 A先序遍历 B中序遍历 C后序遍历 D按层遍历 10采用折半查找法查找长度为n的线性表时，每个元素的平均查 找长度为_。 AO（n2） BO（nlog2n） CO
5、（n） DO（log2n） 11二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中 序遍历：HFIEJKG 。该二叉树根的右子树的根是：_。 AE BF CG DH 12已知有向图G=（V,E），其中V=V1,V2,V3,V4,V5,V6,V7， E=, , ,G的拓扑序列是_。 AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7 CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V7 13采用邻接表存储的图的广度优先遍历算法类似于二叉树的 _。 A先序遍历 B按层遍历 C后序遍历 D中序遍历 14设有一组记录的关键
6、字为19，14，23，1，68，20，84，27， 55，11，10，79，用链地址法构造散列表，散列函数为H（key）=key MOD 13，散列地址为1的链中有_个记录。 A1 B2 C3 D4 15对数列25，84，21，47，15，27，68，35，20进行排序，元 素序列的变化情况如下： 第一趟25，84，21，47，15，27，68，35，20， 第二趟20，15，21，25，47，27，68，35，84， 第三趟15，20，21，25，35，27，47，68，84， 第四趟15，20，21，25，27，35，47，68，84， 则采用的排序方法是_。 A希尔排序 B简单选择排序
7、C快速排序 D归并排序 二、填空题：（每空3分，共30分） 1在循环双链表的P所指结点之前插入S所指结点的操作如下： S-next = P； S-prior =_ P-prior-next = S； P-prior = S； 2分析以下程序段的时间复杂度为_。 k=1； While （k=n） k= k*2； 3向一个长度为n的顺序表中的第i个元素（）之前插入一 个元素时，需向后移动_个元素。 4设有一个背包可以放入的物品重量为S，现有n件物品，重量分 别为W1，W2，.，Wn。问能否从这n件物品中选择若干件放入背包， 使得放入的重量之和正好是S。设布尔函数Knap（S，n）表示背包问题 的解
8、，Wi（i=1，2，.，n）均为正整数，并已顺序存储地在数组W中。 请在下列算法的下划线处填空，使其正确求解背包问题。 Knap（S，n） 若S=0 则Knap true 否则若（S0且n1） 则Knap false 否则若Knap （1）=true 则print（Wn）；Knap true 否则 Knap Knap （2） 5下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f（abba）返回1，f（abab）返回0； In t f（ （1） In t i=0, j=0； while （sj） （2）； for （j-； ij & si=sj； i+,j-）； return （
9、（3） 6一个有n个顶点的无向图最多有_条边。 7在堆排序和快速排序中，若原始记录接近正序或反序，则选用 _比较好。 三、判断题：（每小题2分，共20分） 1算法的时间复杂度取决于问题的规模_ 2从逻辑上可以把数据结构分为顺序结构、链式结构两大类 _ 3某算法仅含程序段1和程序段2，程序段1的执行次数为3n2，程 序段2的执行次数为0.01n3，则该算法的时间复杂度为O（n2）_ 4对于顺序存储的长度为n的线性表，访问结点和增加、删除结点 的时间复杂度分别为O（n）和O（n） _ 5用链接方式存储的队列（不带头结点），在进行删除运算时仅 修改头指针_ 6线性表L=（a1，a2，an）用数组表示
10、，假定删除表中任一 元素的概率相同，则删除一个元素平均需要移动元素的个数是（n-1）/2 7假设以数组Am存放循环队列的元素,其头尾指针分别为front和 rear，则当前队列中的元素个数为（rear- front +m）%m_ 8设无向图的顶点个数为n，则该图最多有n（n-1）/2条边_ 9一个n个顶点的连通无向图，其边的个数至少为n-1 10要连通具有n个顶点的有向图，至少需要n条边_ 四、简答题：（每小题20分，共40分） 1已知如右图所示的有向图，请给出该图的： 每个顶点的入度、出度； 邻接矩阵； 邻接表； 逆邻接表； 强连通分量。 2设二叉树BTree的存储结构如下： 1234567
11、 left0023758 datajhfdbac right0009400 其中，B Tree为树根结点指针，left、right 分别为结点的左、右孩 子指针域，在这里使用结点编号作为指针域值，0表示指针域值为空； data为结点的数据域。请完成如下问题： 画出二叉树B Tree的逻辑结构； 写出按先序、中序和后序遍历二叉树B Tree所得到的结点序列； 画出二叉树B Tree的后线索化树。 五、编程题：（每小题15分，共30分） 1有线性表（a1, a2, , an），采用单链表存储，头指针为H，每 个结点中存放线性表中一个元素，现查找某个元素值等于X的结点。分 别写出下面三种情况的查找语
12、句。要求时间尽量少。 （1）线性表中元素无序。 （2）线性表中元素按递增有序。 （3）线性表中元素按递减有序。 2设计一个将输入数据建立成链表、输出链表数据、利用原空间 把链表反转的程序。 2013年浙江理工大学信息学院991数据结构 考研真题 浙江理工大学 2013年硕士学位研究生招生入学考试试题 考试科目：数据结构 代码：991 （请考生在答题纸上答题，在此试题纸上答题无效） 一、单选题（在每小题的四个备选答案中选出一个正确答案。每小 题2分，共20分。） 1链表不具备的特点是_。 A可随机访问任一结点 B插入删除不需要移动元素 C不必事先估计存储空间 D所需空间与其长度成正比 2设线性表
13、有n个元素，以下算法中，_在顺序表上实现比在 链表上实现效率更高。 A交换第0个元素与第1个元素的值 B顺序输出这n个元素的值 C输出第i（0in-1）个元素值 D输出与给定值x相等的元素在线性表中的序号 3设输入序列为a、b、c、d，则借助栈所得到的输出序列不可能 是_。 Aa、b、c、d Bd、c、b、a Ca、c、d、b Dd、a、b、c 4为解决计算机主机与打印机之间的速度不匹配问题，通常设计 一个打印数据缓冲区，主机将要输出的数据依次写入到该缓冲区，而打 印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 _。 A栈 B队列 C树 D图 5设哈夫曼树中的叶子结点总数为m，若用二
14、叉链表作为存储结 构，则该哈夫曼树中总共有_个空指针域。 A2m B4m C2m+1 D2m -1 6二叉树若用顺序存储结构表示，则下列四种运算中_最容 易实现。 A先序遍历二叉树 B层次遍历二叉树 C中序遍历二叉树 D后序遍历二叉树 7以下关于有向图的说法正确的是_。 A强连通图是任何顶点到其他所有顶点都有边 B完全有向图一定是强连通图 C有向图中某顶点的入度等于出度 D有向图边集的子集和顶点集的子集可构成原有向图的子图 8若一个有向图中的顶点不能排成一个拓扑结构序列，则可断定 该有向图_。 A含有多个出度为0的顶点 B是个强连通图 C含有多个入度为0的顶点 D含有顶点数目大于1的强连通分量
15、 9顺序查找法适合于存储结构为_的线性表。 A哈希存储 B压缩存储 C顺序存储或链式存储 D索引存储 10在所有排序方法中，关键字比较的次数与记录地初始排列次序 无关的是_。 Ashell排序 B冒泡排序 C直接插入排序 D简单选择排序 二、填空题（每空2分，共30分。） 1下面程序段的时间复杂度是_。 for （i=0；i n ；i+） for （j=0；j=0）的二叉树，至少有_个结点，最多有 _个结点。普里姆（PRIM）算法更适合于求边的网的最小生成 树。 8在无向图G的邻接矩阵A中，若Aij等于1，则Aji等于 _。 9在对一组记录（54，38，96，23，15，72，60，45，83）进行 直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置 需比较_次。 10若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排 序的方法建立的初始堆为_。 11有一个长度为10的有序表，按折半查找法对该表进行查找，在 表内各元素等概率情况下查找成功所需的平均比较次数为_。 12在一棵平衡的二叉树中，每个节点的平衡因子
