991数据结构真题2013

《991数据结构真题2013》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浙江理工大学2013年硕士学位研究生招生入学考试试题考试科目：数据结构代码：991（请考生在答题纸上答题，在此试题纸上答题无效）一、单选题（在每小题的四个备选答案中选出一个正确答案。每小题2分，共20分。）1.链表不具备的特点是______。A.可随机访问任一结点B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与其长度成正比2.设线性表有n个元素，以下算法中，在顺序表上实现比在链表上实现效率更高。A.交换第0个元素与第1个元素的值B.顺序输出这n个元素的值C.输出第i(0≤i≤n-1)个元素值D.输出与给定值x相等的元素在线性表中的序号3.设输

2、入序列为a、b、c、d，则借助栈所得到的输出序列不可能是_________。A.a、b、c、dB.d、c、b、aC.a、c、d、bD.d、a、b、c4.为解决计算机主机与打印机之间的速度不匹配问题，通常设计一个打印数据缓冲区，主机将要输出的数据依次写入到该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是。A.栈B.队列C.树D.图5.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有个空指针域。A.2mB.4mC.2m+1D.2m-16.二叉树若用顺序存储结构表示，则下列四种运算中最容易实现。A.先序遍历二叉树

3、B.层次遍历二叉树C.中序遍历二叉树D.后序遍历二叉树7.以下关于有向图的说法正确的是。A.强连通图是任何顶点到其他所有顶点都有边B.完全有向图一定是强连通图C.有向图中某顶点的入度等于出度D.有向图边集的子集和顶点集的子集可构成原有向图的子图8.若一个有向图中的顶点不能排成一个拓扑结构序列，则可断定该有向图____________。A.含有多个出度为0的顶点B.是个强连通图C.含有多个入度为0的顶点D.含有顶点数目大于1的强连通分量9.顺序查找法适合于存储结构为的线性表。A.哈希存储B.压缩存储C.顺序存储或链式存储D.索引存储10.在所有排序方法中，关键

4、字比较的次数与记录地初始排列次序无关的是。A.shell排序B.冒泡排序C.直接插入排序D.简单选择排序第2页，共2页二、填空题（每空2分，共30分。）1．下面程序段的时间复杂度是。for(i=0;i

5、储方式（以行序为主存储，且A[0][0]=1），则A[8][5]的地址是。7．高度为h(>=0)的二叉树，至少有个结点，最多有个结点。8．普里姆（PRIM）算法更适合于求边的网的最小生成树。9．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于。10．在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较次。11．若一组记录的排序码为（46,79,56,38,40,84），则利用堆排序的方法建立的初始堆为。12．有一个长度为10的有序表，按折半查找法对

6、该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为。13．在一棵平衡的二叉树中，每个节点的平衡因子B的取值范围是三、判断题（每小题2分，共20分。）1.对于数据结构，相同的逻辑结构，对应的存储结构也必相同。（）2.哈夫曼树中没有度数为1的结点。（）3.线性表中的所有元素都有一个前驱元素和后继元素。（）4.除了删除和插入操作外，数组的主要操作还有存取、修改、检索和排序。（）5.链表的每一个结点都恰好包含一个指针。（）6.无向图的邻接矩阵一定是对称矩阵，且有向图的邻接矩阵一定是非对称矩阵。（）7.若有一个结点是某二叉树子树的中序遍历序列中的最后一

7、个结点，则它必是该子树的前序遍历序列中的最后一个结点。（）8.冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）9.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（）10.快速排序是排序算法中平均性能最好的一种排序。（）四、应用题（共50分。）fabcedg1．（14分）已知一棵二叉树如右图所示：(1)中序全线索化二叉树；(2)写出对该二叉树进行先序遍历和后序遍历的结果；(3)试画出其相应的树。第2页，共2页