上海科技大学计算机考研真题.docx
- 文档编号:16871880
- 上传时间:2023-07-19
- 格式:DOCX
- 页数:8
- 大小:18.93KB
上海科技大学计算机考研真题.docx
《上海科技大学计算机考研真题.docx》由会员分享,可在线阅读,更多相关《上海科技大学计算机考研真题.docx(8页珍藏版)》请在冰点文库上搜索。
上海科技大学计算机考研真题
上海科技大学计算机考研真题
考生须知:
1.本试卷满分为150分,全部考试时间总计180分钟。
2.所有答案必须写在答题纸上,写在试题纸上或草稿纸上一律无效。
3.每道题的英文部分均已翻译为中文,考生可在中英文中任选一种语言作答。
1.TrueorFalse(10problems,2pointseach)判断题(10题,每题2分)
Pleaseindicateintheanswersheetwhethereachstatementistrueorfalse.Writedown“T”forbeingtrueand“F”forbeingfalse.请在答题纸上写明下列每个命题的真假。
真则打“”,假则打“”。
1.Inacircularlinkedlist,somelinkfieldsmaybenull.()在循环链表中,某些链接域可能为空。
()
2.Givenanyfunctionsf(n)andg(n),itispossibletohavebothf(n)=Ω(g(n))andf(n)=o(g(n)).()
给定任意函数f(n)和g(n),f(n)=Ω(g(n))和f(n)=o(g(n))可能同时成立。
()
3.Agoodhashfunctionofahashtablesatisfiestheassumptionofsimpleuniformhashing.()一个好的哈希函数需满足简单均匀。
()
4.Thefollowingtreeisabinarysearchtree.()
下列树是二叉搜索树。
()
5.Thenumberofnodesinatreecanbemorethantwicethenumberofleafnodes.()
一棵树的节点个数有可能大于叶节点个数的两倍。
()
6.Thespacecomplexityofanadjacency-matrixrepresentationofagraphisindependentofthenumberofedgesinthegraph.()
图的邻接矩阵表示的空间复杂度与图的边数无关。
()
7.Inthebreadth-firstsearchprocedureofgraphs,eachvertexmustbeenqueuedexactlyonce.()
在图的广度遍历算法中,每个节点恰好仅入队一次。
()
8.Givenaweighted,directedgraphwithnodesnumbered1,2,……,n,findingthelengthofashortestpathfromvertex1tovertexnordeterminingthatnosuchpathexistscanbedoneinpolynomialtime.()
给定一个带权有向图,图的节点为1,2,……,n,要计算节点1和n之间的最短路径或判断这样的路径不存在,这个问题可以在多项式时间内解决。
()
9.Givenagraph,decidingwhetherithasacliqueof100nodesisNP-complete,assumingPNP.()
给定一个图,确定图中是否存在一个正好包含100个节点的团是一个NP-complete的问题,假设PNP。
()
10.Givenagraph,decidingwhetheritispossibletoremovehalfthenodesinthegraphsothattheremaininggraphis3-colorableissolvableinpolynomialtime,assumingPNP.()
给定一个图,确定是否可以去除图中一半的节点后使得该图可以三染色,这可以在多项式时间内完成,假设PNP。
()
2.MultipleChoices–SelectOne(10problems,2pointseach)单选题(10题,每题2分)Eachquestionhasonlyonecorrectchoice.Pleaseindicatethecorrectchoiceintheanswersheet.每题只有一个正确选项。
请在答题纸上写下正确选项的序号。
rearrangesubstrings?
()A.FixedlengthstoragestructureB.LinkedliststorageC.VariablelengthstoragewithfixedmaximumD.ArrayliststorageE.Noneoftheabove哪种字符串的存储结构可以方便地进行插入,删除,并联以及重新安排子字符串?
()
A.固定长度的存储结构
B.链表存储结构
C.具有固定最大长度的变长存储结构
D.数组存储结构E.以上都不是
2.Inwhichofthefollowingarethefunctionslistedinorderofincreasingasymptoticsize?
()
下面哪个选项中的函数是按照渐进大小的增序排列?
()
A.2n,n+(logn)2,n3,10n2,nlogn
B.n+(logn)2,n3,10n2,nlogn,2n
C.n+(logn)2,nlogn,10n2,n3,2n
D.n+(logn)2,10n2,nlogn,n3,2nE.2n,n3,10n2,nlogn,n+(logn)2
3.Westore10elementswithkeys{5,28,19,15,20,12,33,17,10,18}intoahashtablewithcollisionsresolvedbychaining(withlinkedlist).Thehashtablehas9slotsandthehashfunctionisdefinedash(k)=kmod9.Whatisthemaximumlengthofthelinkedlistsinthehashtable?
()
存储10个元素到一个哈希表,这10个元素的key是{5,28,19,15,20,12,33,17,10,18}。
哈希表总共有9个slots,哈希函数是h(k)=kmod9,并用链表解决冲突。
哈希表中最长的链表长度是?
()
A.1
B.2
C.3
D.44.Afullbinarytreeisarootedtreeinwhicheveryinternalnodehasexactlytwochildren.manyinternalnodesarethereinafullbinarytreewith500leaves?
()
满二叉树的所有中间节点都有两个孩子节点。
一个有500个叶子节点的满二叉树有多少个中间节点?
()
A.250
B.499
C.500
D.501
E.1,000
5.Whichofthefollowingstatementsabouttreesisfalse?
()
A.Aninternalnodemayhavenochild
B.Addinganedgetoatreecreatesacycle
C.Noteverynodehasaparentnodeinatree
D.Theheightofatreewithonenodeis0
以下哪一个关于树的描述是错误的?
()
A.非叶节点有可能没有孩子
B.在一棵树中加一条边会形成一个环
C.一棵树中并非每个节点都有父亲节点
D.一棵包含一个节点的树高度为0
6.Whatisthein-ordertraversalofthefollowingbinarytree?
()
下面二叉树的中序遍历是什么?
()
A.DFBEAC
B.ABDFEC
C.FDEBCA
D.FDEBAC
Prim’salgorithmisonealgorithmforfindingaminimumspanningtreeinagraphandtheFloyd-Warshallalgorithmcanbeusedtosolvetheall-pairsshortest-pathsproblemonadirectedgraph.Whichofthefollowingmustbetrue?
()
Prim’salgorithmisagreedyalgorithm.ii.Prim’salgorithmisadynamicprogrammingalgorithm.iii.Floyd-Warshallalgorithmisagreedyalgorithm.iv.Floyd-Warshallalgorithmisadynamicprogrammingalgorithm.Prim算法是一种计算图的最小生成树算法,Floyd-Warshall算法可用于计算有向图中所有节点对之间的最短路径。
以下哪些表述肯定是正确的?
()
IPrim算法是一种贪心算法。
ii.Prim算法是一种动态规划算法。
iii.Floyd-Warshall算法是一种贪心算法。
iv.Floyd-Warshall算法是一种动态规划算法。
A.I和iiiB.I和ivC.ii和iiiD.ii和iv8.AmongthefollowingproblemsconcerningagivengraphG,whichiscurrentlyknowntobesolvableinlineartime?
()
A.Findingalongestsimplecycleinanundirectedgraph
B.Computingthestronglyconnectedcomponentsofadirectedgraph
C.Solvingthesingle-sourceshortest-pathsproblemofaweighted,directedgraphG
D.FindingalargestcliqueinanundirectedgraphG
以下哪一个图的问题可以在线性时间内解决?
()
A.找到一个无向图中的最长简单环
B.计算有向图的强连通分量
C.解决带权有向图的单源最短路径问题
D.找到一个无向图的最大团
9.Whichofthefollowingistrueofmergesortandquicksort?
()
A.Botharedivideandconqueralgorithms
B.Bothtake(n)timeineachdividestep,givenaninputarrayofsizen
C.Bothhavethesameworst-casetimecomplexity
D.Alloftheabovearetrue
下列关于归并排序和快速排序的陈述哪一项是对的?
()
A.都是用分治法
B.给定一个长度为n的输入数组,都是需要(n)的时间进行每一次切分
C.都有相同的最坏时间复杂度
D.以上都对
10.Whichofthefollowingistheclosesttotheminimumnumberofcomparisonsbetweenarrayelementsthatanycomparison-basedalgorithmneedstoperformtofindboththeminimumandmaximumvaluesinaninputarrayofsizen?
()
任何一个基于比较的算法在一个长度为n的数组中同时找出最大和最小值,至少需要数组元素之间的比较的次数与下列哪个最接近?
()
A.n
B.1.5n
C.2n
D.n23.
MultipleChoices–SelectOneorMore(5problems,2pointseach)多选题(5题,每题2分)Eachquestionmayhaveoneormorecorrectchoices.Pleaseindicateallthecorrectchoice(s)intheanswersheet.每题有一个或多个正确选项。
请在答题纸上写下所有正确选项。
1.Considerusingalinkedlisttorepresentasparsematrix.Onlynon-zeroelementsarestoredinthelist.Whatinformationshouldbestoredinthenodesofthelinkedlist?
()
A.Rownumber
B.Columnnumber
C.Valueofthematrixelement
D.Numberofnon-zeroelementsE.Numberofzeroelements
假设使用一个链表来表示一个稀疏矩阵,其中只存储非零元素。
在链表的节点中需要存科目代码:
991科目名称:
数据结构与算法第7页共12页储什么信息?
()
A.行号
B.列号
C.矩阵元素的值
D.非零元素的个数
E.零元素的个数
2.Inacharacter-codingproblem,ifafilecontainsonlycharacters‘a’,‘b’,and‘c’withfrequencies45,13,and12respectively,whichofthefollowingcodewordsisanoptimalcharactercodeforthefile?
()
在一个字符编码问题中,如果一个文件只由a,b,c组成,它们出现的频率分别是45,13,12,以下哪些编码是最优的?
()
A.a:
000,b:
010,c:
101
B.a:
000,b:
010,c:
100
C.a:
00,b:
01,c:
10
D.a:
1,b:
01,c:
003.
Givenanundirectedgraphwithnnodesandmedges,selectthecorrectstatement(s)below.()
A.m=n-1ifthegraphisatree
B.n=m-1ifthegraphisatree
C.m D.n 给定一个具有n个节点和m条边的无向图,选择下列正确的称述? () A.如果该图是一棵树,那么m=n-1 B.如果该图是一棵树,那么n=m-1 C.如果该图是一个森林,那么m D.如果该图是一个森林,那么n E.以上都不正确 4.Considerthefollowingweighed,undirectedgraph.Whichofthefollowingmustbetrue? () 12345678925515759478491063A.Theabovegraphhasfourminimumspanningtrees.B.Thereisatleastoneminimumspanningtreecontainingtheedge(6,8)C.Thereisatleastoneminimumspanningtreecontainingtheedge(5,6)D.Alltheminimumspanningtreescontaintheedge(2,9)E.Alltheminimumspanningtreescontaintheedge(4,7)考虑以下带权无向图,以下哪一个或哪些表述是正确的? () A.上图有四个最小生成树 B.存在一个包含边(6,8)的最小生成树 C.存在一个包含边(5,6)的最小生成树 D.所有最小生成树都包含边(2,9) E.所有最小生成树都包含边(4,7) 5.WriteXpYtomeanthataproblemXispolynomial-timereducibletoproblemY.SupposethataproblemXisinP,aproblemYisinNP,andXpY.Whichofthefollowingmustbetrue? () A.XisinNP B.XisNP-complete C.YisNP-complete D.IfaproblemZisinP thenZpX用XpY表示问题X可以多项式时间规约到问题Y。 假设问题X属于P,问题Y属于NP,同时XpY。 下列哪些项一定为真? () A.X属于NP B.X是NP-complete C.Y是NP-complete D.假定Z属于P,那么Zp
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 上海 科技大学 计算机 考研
![提示](https://static.bingdoc.com/images/bang_tan.gif)