武汉理工大学2013数据结构考研真题

《武汉理工大学2013数据结构考研真题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

这真题是假的啊！被验证过了！被一些赚黑心钱的卖家拿来卖！拿假的来骗钱的！谁要谁就去下载吧！武汉理工大学2013年研究生入学考试试题课程：数据结构一、单选题(每题2分，共20分)1.不带头结点的单链表simpleList为空的判定条件是。A.simpleList==nullB.simpleList->next==nullC.simpleList->next=simpleListD.simpleList!=null2.某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用_______________存储方式最节省运算时间。A.单链表B.仅有头结点的单循环链表C.双链表D.仅有尾指针的单循环链表3.向一个栈顶指针为top的链栈中插入一个S所指结点时，则执行_______________________。A.top->next=S;B.S->next=top->next;top->next=S;C.S->next=top;top=S;D.S->next=top;top=top->next;4.一维数组和线性表的区别是_____________。A.前者长度固定，后者长度可变B.后者长度固定，前者长度可变C.两者长度均固定D.两者长度均可变5.设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对任一下三角部分中任一元素aij(),在一组数组B的下标位置K的值是______。A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j6.在线索化二叉树中，P所指的结点没有左子树的充要条件是_______________________。A.P->left==nullB.P->ltag=1C.P->ltag==1且P->left==nullD.以上都不对7.如果Tree2是由有序树Tree1转换而来的二叉树，那么Tree1中结点的后序就是Tree2中结点的____________________。A.先序B.中序C.后序D.层次序8.判定一个有向图上是否存在回路除了可以利用拓扑排序方法外，还可以用_____________。A.求关键路径的方法B.求最短路径的Dijkstra方法第1页，共5页 C.广度优先遍历算法D.深度优先遍历算法9.采用邻接表存储的图的深度优先遍历算法类似于二叉树的____________________。A.先序遍历B.中序遍历C.后序遍历D.按层遍历10.采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为____________。A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)二、填空题(每空2分，共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)表示背包问题的解，Wi(i=1，2，...，n)均为正整数，并已顺序存储地在数组W中。请在下列算法的下划线处填空，使其正确求解背包问题。Knap(S，n)若S=0则Knap←true;否则若（S<0）或(S>0且n<1)则Knap←false;否则若Knap(1)=true则print(W[n])；Knap←true;否则Knap←Knap(2);5．下列程序判断字符串s是否对称，对称则返回1，否则返回0；如f("abba")返回1，f("abab")返回0；intf((1))第2页，共5页 {inti=0,j=0;while(s[j])(2);for(j--;i,,,,,,,,},G的一种拓扑序列是__________________。10．采用邻接表存储的图的广度优先遍历算法类似于二叉树的__________________。11．设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD13，散列地址为1的链中有__________________个记录。12．对数列{25，84，21，47，15，27，68，35，20}进行排序，元素序列的变化情况如下：(1)25，84，21，47，15，27，68，35，20(2)20，15，21，25，47，27，68，35，84(3)15，20，21，25，35，27，47，68，84(4)15，20，21，25，27，35，47，68，84，则采用的排序方法是__________________。三、判断题(每题2分，共20分)1.数据的逻辑结构是指数据元素之间的逻辑关系。（）2.一个数据结构在计算机中的映像称为存储结构。（）3.数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。（）4.引入二叉线索树的目的是加快查找结点的前驱或后继的速度。（）5.直接定址法得到的哈希函数肯定不会发生冲突。（）6.在分块查找中，首先查找块表，然后再查找相应的索引表。（）7.查找效率最高的二叉树是所有结点的右子树都为空的二叉树。（）第3页，共5页 8.具有n个顶点的无向连通图中至少有n-2条边。（）9.一个图的邻接表表示法是唯一的，而邻接矩阵表示法是不唯一的。（）10.如果含有n个顶点的图G形成一个环，则G有n-1棵生成树。（）四、应用题(共50分)1.已知如图所示的有向图，请给出该图的：(25分)（1）每个顶点的入度、出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表；（5）强连通分量。2.设二叉树BTree的存储结构如下：(15分)12345678910left00237580101datajhfdbacegiright0009400000其中，BTree为树根结点指针，left、right分别为结点的左、右孩子指针域，在这里使用结点编号作为指针域值，0表示指针域值为空；data为结点的数据域。请完成如下问题：(1)画出二叉树BTree的逻辑结构；(2)写出按先序、中序和后序遍历二叉树BTree所得到的结点序列；(3)画出二叉树BTree的后线索化树。3.假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10请为这8个字母设计哈夫曼编码。要求写出相应的思路和过程。(5分)4.给出一棵树最少的关键字序列(4、5、7、2、1、3、6)，使AVL树的4种调整平衡操作各至少一次，并画出其构造过程。(5分)五、编程题(每小题15分，共30分)第4页，共5页 1．有线性表(a1，a2，…，an)，采用单链表存储，头指针为H，每个结点中存放线性表中一个元素，现查找某个元素值等于X的结点。分别写出下面三种情况的查找语句：(1)线性表中元素无序。(2)线性表中元素按递增有序。(3)线性表中元素按递减有序。要求用尽量少时间查找相应的结点。2.设计一个将输入数据建立成链表、输出链表数据、利用原空间把链表反转的程序。第5页，共5页