首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 计算机考试 > 软件考试 > 考试试题 >

软件设计师第1部分计算机科学基础三(1)

2010-11-15 来源:读书人 
读书人为您总结软件设计师第1部分计算机科学基础,希望对您的考试有所帮助
编辑推荐:
软件设计师第1部分计算机科学基础一
软件设计师第1部分计算机科学基础二

  ●将两个长度为n的递减有序表归并成一个长度为2n的递减有序表,最少需要进行关键字比较(67)次。

  (67)A.1

  B.n-1

  C.n

  D.2n

  答案:(67)C

  解析:当一个有序表中的最小关键字比另一个表的最大关键字还大时,则最少比较关键字n次。

  ●设集合N={0,1,2,…},f为从N到N的函数,且当0≤x≤90时f(x)=f(f(x+11)),当X>90时f(X)=X-10。经计算f(90)=81,f(89)=81,f(49)=(68)。

  (68)A.39

  B.49

  C.81

  D.92答案:(68)C

  解析:当80<=90时,易得f(x)=f(f(x+11))=f(x+11-10)=f(x+1),于是当80<=90时,f(x)恒等于f(89)即81。递推f(49)得f(49)=f(f(f(f(82))))=f(f(f(81)))=f(f(81))=f(81)=81。

  ●集合A={1.2.3}上的二元关系R为:R={<1,1>,<3,3>,<1,2>)},则二元关系R是(69)。

  (69)A.自反的

  B.反自反的

  C.对称的

  D.传递的

  答案:(69)C

  解析:由<2,2>不属于R知R不是自反的;由<1,1>属于R知R不是反自反的;由<1,2>属于R而<2,1>不属于R知R不是对称的。

  ●快速排序最坏情况下的时间复杂度为(70)。

  (70)A.0(log2n)

  B.O(n)

  C.O(nlog2n)

  D.O(n2)

  答案:(70)D

  解析:对n个元素进行快速排序时,最坏情况下的时间复杂度为O(n2)。

  ●任何一个基于“比较”的内部排序的算法,若对5个元素进行排序,则在最坏情况下所需的比较次数至少为(71)。

  (71)A.7

  B.8

  C.21

  D.120

  答案:(71)A

  解析:对于5个记录的集合任何一个基于“比较”的内部排序的算法的判定树的叶子结点数目为5!,此判定树的树高至少为log25!。由5!=120,27=128,26=64可得6<7。因此在最坏情况下所需的比较次数至少为7。

  ●元素的存储地址与其关键字之间存在某种映射关系的存储结构是(72)。

  (72)A.树形存储结构

  B.线性存储结构

  C.索引存储结构

  D.散列存储结构

  答案:(72)D

  解析:散列存储结构中将结点按其关键值的散列地址存储到散列表中,其关键字与其存储地址之间按照某种关系进行映射。

  ●若循环队列存储在数组Q[0,m-1]中,变量r表示循环队列中队尾元素的实际位置,其移动按r=(r+1)mod m进行,变量l表示当前循环队列中的元素个数,则循环队列的队首元素的实际位置是(73)。

  (73)A.r-1

  B.(r-1+m)mod m

  C.m-1

  D.(1+r+m-1)mod m

  答案:(73)D

  解析:按照循环队列的定义,因为元素移动按照r=(r+1)mod m进行。当数组Q[m-1]存放了元素之后,下一个入队的元素将存放在Q[0],因此。循环队列的队首元素的实际位置是(1+r+m-1)mod m。

  ●一个简单无向图含有n个顶点和e条边,则在其邻接矩阵存储结构中,零元素个数为(74)。

  (74)A.e

  B.2e

  C.n2-e

  D.n2-2e

  答案:(74)D

  解析:无向图的邻接矩阵是对称的,图中的一条边对应邻接矩阵中两个非零元素。因此该图的邻接矩阵存储结构中。零元素个数为n2-2e。

  ●一棵9个顶点的哈夫曼(Huffman)树共有(75)个叶子结点。

  (75)A.7

  B.6

  C.5

  D.4

  答案:(75)C

  解析:哈夫曼(Huffman)树是严格的二叉树。没有度为1的分支结点。n个叶子经过n-1次合并,产生n-1个新结点。于是得到关系式n+n-1=9,推出n=5。本题也可以直接画出哈夫曼树而得到结果。

  ●采用邻接矩阵来存储简单有向图时,则其某一个顶点i的出度等于该矩阵(76)。

  (76)A.所有值为1的元素总数

  B.第i行中值为1的元素个数

  C.第i行中值为1的元素个数n2-2e

  D.第i行及第i列中值为1的元素总个数

  答案:(76)B

  解析:采用邻接矩阵存储简单有向图时,其邻接矩阵第i行元素的和即为顶点i的出度,第i列元素的和即为顶点i的入度。

  ●在一棵度为4的树中,若有3个度为4的结点,有1个度为2的结点,没有度为1的结点,则有(77)个度为0的结点。

  (77)A.9

  B.10

  C.11

  D.12

  答案:(77)C

  解析i每个度为4的结点衍生出4个子结点,每个度为3的结点衍生出3个子结点,每个度为2的结点衍生出2个子结点,再加上根结点,于是结点总数为3*4+2+1=15。减去度非零的4个结点,得到度为0的结点数为11个。

  ●某二叉树的先根遍历序列中x结点在Y结点之前,而在其后根遍历序列中X结点在y结点之后,则x结点和Y结点的关系是(78)。

  (78)A.X是Y的左兄弟

  B.X是Y的祖先

  C.X是Y的右兄弟

  D.X是y的后裔

  答案:(78)B

  解析:二叉树的先根遍历序列中,根结点总是出现在其子树结点之前;二叉树的后根遍历序列中,根结点总是出现在其子树结点之后。因此。x结点是Y结点的祖先。


(作者:读书人网友 编辑:kind887)
热点排行