圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台第3部分模拟试题全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合模拟试题及详解（一）一、单项选择题（1～40小题，每小题2分，共80分。）1．以下算法的时间复杂度为（）。A．O（n）B．O（nlog2n）C．O（n2log2n）D．O（n2）【答案】C【解析】基本运算语句是k＝5×k，设其执行时间为T（n）。对于j每循环一次，该语句的执行次数为m，有：m≤n，即m≤log5n。所以：T(n)=??m?m??1?mn2?n2log5n?O(n2log5n)
i?1j?1
i?1j?1
1/62nnnn
圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台算法的时间复杂度也可表示为O（n2log2n）。2．链表不具有的特点是（）。A．插入、删除不需要移动元素B．可随机访问任意元素C．不必事先估计存储空间D．所需空间与线性长度成正比【答案】B【解析】本题考查顺序表和链表的比较。显然随机存储是顺序表的特性，而不是链表的特性；A项是链表结构所具有的特性；C项，因为链表在使用时可以动态分配，可以不必事先估计存储空间的大小；D项明显正确，一个数据元素对应一个空间。3．表达式a*（b＋c）－d的后缀表达式是（A．abcd*＋－B．abc＋*d－C．abc*＋d－D．－＋*abcd【答案】B【解析】本题转化过程图1所示：）。2/62圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台图1表达式转化过程由图1可以写出以下转化过程：①b＋c->bc＋（假设x＝“bc＋”）；②a*x->ax*（假设y＝“ax*”）；③y－d->yd－；④将xy还原后得到：abc＋*d－。4．一个具有767个结点的完全二叉树，其叶子结点个数为（A．383B．384C．385D．386【答案】B）。【解析】根据二叉树性质可推导，对于一棵非空的二叉树，如果叶子结点数为n0，度数为1的结点数为n1，度数为2的结点数为n2，则有n0＝n2＋1。即结点总数，n＝n0＋n1＋n2＝2n0＋n1－1。由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到：n0＝（n＋1）/2或n0＝n/2。5．在一棵完全二叉树中，其根的序号为1，（）可判定序号为p和q的两个结点3/62圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台是否在同一层。A．?log2p?＝?log2q?B．log2p＝log2qC．?log2p?＋1＝?log2q?D．?log2p?＝?log2q?＋1【答案】A【解析】由完全二叉树的性质可知，在一棵完全二叉树第h（h≥1）层上的结点p和q，它们序号范围应是2k—1≤p,q≤2k—1，因此有?log2p?＝?log2q?成立。6．在具有n个顶点的无向完全图中删去（A．n（n－1）/2B．（n－1）（n－2）/2C．（n－2）（n－3）/2D．（n＋1）（n－2）/2【答案】B）条边才可能得到一棵树。【解析】由于具有n个顶点的无向完全图中共有n（n－1）/2条边，n个顶点的树应有n－1条边，于是删去的边有：n（n－1）/2－（n－1）＝（n－1）（n－2）/2。7．设哈夫曼编码的长度不超过4，若已对两个字符编码为1和01，则最多还可以对（）个字符编码。A．2B．34/62圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台C．4D．5【答案】C【解析】本题主要考查哈夫曼编码的概念和性质。哈夫曼编码是一种前缀编码，满足任意一个字符的编码都不是另一个字符编码的前缀。除1和01外，长度不超过4的其余所有编码为1，00，10，11，000，001，010，011，100，101，110，111，0000，0001，0010，0011，0100，0101，0110，0111，1000，1001，1010，1011，1100，1101，1110，1111。因为已有编码1和01，根据前缀编码的要求，则1和01开头的编码都不可考虑，剩余0，00，000，001，0000，0001，0010，0011。若再选择0为一个字符的编码，则剩余的编码都不能使用，只能再为一个字符编码，同理选择00也是如此。若再选择000为一个字符编码，则还能再选择001，能再为2个字符编码。若再选择0000为一个字符编码，则还能选择0001，0010，0011，能再为4个字符编码。8．在含有27个结点的二叉排序树上，查找关键字为35的结点，则依次比较的关键字有可能是（）。A．28，36，18，46，35B．18，36，28，46，35C．46，28，18，36，35D．46，36，18，28，35【答案】D【解析】各选项对应的查找过程如图2所示，从中看到只有选项D对应的查找树是一5/62
考研计算机联考辅导系列-模拟试题【圣才出品】
