2019年上海科技大学数据结构与算法考研真题.doc

2019年上海科技大学数据结构与算法考研真题

1.TrueorFalse（10problems，2pointseach）判断题（10题，每题2分）
Pleaseindicateintheanswersheetwhethereachstatementistrueorfalse.Writedown"T"for
beingtrueand"F"forbeingfalse.
请在答题纸上写明下列每个命题的真假。真则打"√"，假则打"x"。
1.Inacircularlinkedlis,somelinkfieldsmaybenull.()
在循环链表中，某些链接域可能为空。（）
2.Givenanyfunctionsf(n)andg(n),itispossibletohavebothf(n)=Q(g(n))andf(n)=o(g(n)).
给定任意函数f（n）和g（n），f（n）=Q（g（n）和f（n）=o（g（n）可能同时成立。（）
3.Agoodhashfunctionofahashtablesatisfiestheassumptionofsimpleuniformhashing.()
一个好的哈希函数需满足简单均匀。（）
4.Thefollowingtreeisabinarysearchtree.()
下列树是二叉搜索树

5.Thenumberofnodesinatreecanbemorethantwicethenumberofleafnodes.()
一棵树的节点个数有可能大于叶节点个数的两倍。（）
6.Thespacecomplexityofanadjacency-matrixrepresentationofagraphisindependentof
thenumberofedgesinthegraph.()
图的邻接矩阵表示的空间复杂度与图的边数无关。（）
7.Inthebreadth-firstsearchprocedureofgraphs,eachvertexmustbeenqueuedexactlyonce.()
在图的广度遍历算法中，每个节点恰好仅入队一次。（）
8.Givenaweighted,directedgraphwithnodesnumbered1.2..n,findingthelengthofashortestpathfromvertex1tovertexnordeterminingthatnosuchpathexistscanbedone
inpolynomialtime.()
给定一个带权有向图，图的节点为1，2….，n，要计算节点1和n之间的最短路径或判断
这样的路径不存在，这个问题可以在多项式时间内解决。（）
9.Givenagraph,decidingwhetherithasacliqueof100nodesisNP-complete,assumingP=NP.
()
给定一个图，确定图中是否存在一个正好包含100个节点的团是一个NP-complete的问
题，假设P=NP。（）
10.Givenagraph,decidingwhetheritispossibletoremovehalfthenodesinthegraphsothat
theremaininggraphis3-colorableissolvableinpolynomialtime,assumingP=NP.()
给定一个图，确定是否可以去除图中一半的节点后使得该图可以三染色，这可以在多项
式时间内完成，假设P=NP。（）
2.MultipleChoices-SelectOne（10problems，2pointseach）单选题（10题，每
题2分）
Eachquestionhasonlyonecorrectchoice.Pleaseindicatethecorrectchoiceintheanswersheet.
每题只有一个正确选项。请在答题纸上写下正确选项的序号。
1.Inwhatkindofstoragestructureforstringscanoneeasilyinsert,delete,concatenate,andrearrangesubstrings?()
A.Fixedlengthstoragestructure
B.Linkedliststorage
C.Variablelengthstoragewithfixedmaximum
D.Arrayliststorage
E.Noneoftheabove
哪种字符串的存储结构可以方便地进行插入，删除，并联以及重新安排子字符串?（）
A.固定长度的存储结构
B.链表存储结构
C.具有固定最大长度的变长存储结构
D.数组存储结构
E.以上都不是
2.Inwhich