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

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

1、这真题是假的啊！被验证过了！被一些赚黑心钱的卖家拿来卖！拿假的来骗钱的！谁要谁就去下载吧！武汉理工大学2013年研究生入学考试试题课程：数据结构一、单选题(每题2分，共20分)1.不带头结点的单链表simpleList为空的判定条件是。A.simpleList==nullB.simpleList->next==nullC.simpleList->next=simpleListD.simpleList!=null2.某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用_______________存储方

2、式最节省运算时间。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.两者

3、长度均可变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.如

4、果Tree2是由有序树Tree1转换而来的二叉树，那么Tree1中结点的后序就是Tree2中结点的____________________。A.先序B.中序C.后序D.层次序8.判定一个有向图上是否存在回路除了可以利用拓扑排序方法外，还可以用_____________。A.求关键路径的方法B.求最短路径的Dijkstra方法第1页，共5页C.广度优先遍历算法D.深度优先遍历算法9.采用邻接表存储的图的深度优先遍历算法类似于二叉树的____________________。A.先序遍历B.中序遍历C.后序遍历D.按层遍历10.

5、采用折半查找法查找长度为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个元素()之前插入一个元素时，需向

6、后移动_____________个元素。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])；Kn

7、ap←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

8、GJK；中序遍历：HFIEJKG。该二叉树根的右子树的根是__________________。9．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,,,,