2004年上半年软件设计师（高级程序员）上午试题(1)

●在面向对象技术中，类属是一种__(1)__机制。一个类　属类是关于一组类的一个特性抽象，它强调的是这些类的成员特征中与__(2)__的那些部分，而用变元来表示与__(3)__的那些部分。
　　(1)a．包含多态　　　b．参数多态　　　c．过载多态　　　d．强制多态
　　(2)a．具体对象无关　b．具体类型无关　c．具体对象相关　d．具体类型相关
　　(3)a．具体对象无关　b．具体类型无关　c．具体对象相 关　d．具体类型相关

　　●__(4)__的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。
　　(4)a．树形存储结构　b．链式存储结构　c．索引存储结构　d．散列存储结构

　　●若循环队列以数组 q[o..m-1] 作为其存储结构叭变量 rear 表示循环队列中队尾元素的实际位置，其移动按 rear=(rear+1) mod m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是__(5)__。
　　(5)a．rear-length　　　　　　　　b．(rear-length+m) mod m
　　　 c．(1+rear+m-length) mod m　　d．m-length

　　●一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有__(6)__个零元素。
　　(6)a．e　　　b．2e　　　c．n²-e　　d．n²-2e

　　●若一棵哈夫曼(huffman)树共有9个顶点，则其叶子结点的个数为__(7)__。
　　(7)a．4　　　b．5　　　 c．6　　　 d．7

　　●若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于该矩阵__(8)__。
　　(8)a．第i行中值为1的元素个数　　　　　 b．所有值为1的元素总数
　　　 c．第i行及第i列中值为1的元素总个数　d．第i列中值为1的元素个数

　　●在—棵度为3的树中，若有2个度为3的结点，有1个度为2的结点，则有__(9)__个度为0的结点。
　　(9)a．4　　　b．5　　　　c．6　　　d．7

　　●设结点x和y是二叉树中任意的两个结点，在该二叉树的先根遍历序列中x在y之前，而在其后根遍历序列中x在y之后，则x和y的关系是__(10)__。
　　(10)a．x是y的左兄弟　　　b．x是y的右兄弟　　　c．x是y的祖先　　d．x是y的后裔

　　●设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均查找长度为__(11)__。 
　　(11)a．21　　b．23　　　c．41　　　d．62
　　●下图为一确定有限自动机(dfa)的状态转换图，与该自动机等价的正规表达式是__(12)__，图中的__(13)__是可以合并的状态· 

　　(12)a．(a|b)^*bb(a^*b^*)^* 　　b．(a|b)^*bba^*|b^*
　　　　c．(a^*b^*)bb(a|b)^* 　　 d．(a|b)^*bb(a^*|b^*)^* 
　　(13)a．0和1　 b．2和3　 c．1和2　　d．0和3

　　●已知有一维数组a[0..m*n-1]，若要对应为 m 行、n 列的矩阵，则下面的对应关系__(14)__可将元素a[k](0≤k　　(14)a．i=k/n,j=k％m　　　b．i=k/m,j=k％m　　c．i=k/n,j=％n　　d．i=k/m,j=k％n

　　●编译的优化工作对于下面程序段构造的控制流程图有__(15)__个基本块。