2004年上半年软件设计师上午试题.doc

2004年上半年软件设计师(高级程序员)上午试题
●在面向对象技术中,类属是一种__(1)__机制。一个类属类是关于一组类的一个特性抽象,它强调的是这些类的成员特征中与__(2)__的那些部分,而用变元来表示与__(3)__的那些部分。(此括号内不是试题部分。欢迎访问软件考试网)
(1)
(2)
(3)
●__(4)__的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。
(4)
●若循环队列以数组 Q[O..m-1] 作为其存储结构叭变量 rear 表示循环队列中队尾元素的实际位置,其移动按 rear=(rear+1) mod m 进行,变量 length 表示当前循环队列中的元素个数,则循环队列的队首元素的实际位置是__(5)__。
(5)-length B.(rear-length+m) mod m
C.(1+rear+m-length) mod m -length
●一个含有n个顶点和e条边的简单无向图,在其邻接矩阵存储结构中共有__(6)__个零元素。
(6) -e -2e
●若一棵哈夫曼(Huffman)树共有9个顶点,则其叶子结点的个数为__(7)__。
(7)
●若采用邻接矩阵来存储简单有向图,则其某一个顶点i的入度等于该矩阵__(8)__。
(8)

●在—棵度为3的树中,若有2个度为3的结点,有1个度为2的结点,则有__(9)__个度为0的结点。
(9)
●设结点x和y是二叉树中任意的两个结点,在该二叉树的先根遍历序列中x在y之前,而在其后根遍历序列中x在y之后,则x和y的关系是__(10)__。
(10)
●设顺序存储的某线性表共有123个元素,按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块,且在确定的子块中也采用顺序查找方法,则在等概率的情况下,分块查找成功的平均查找长度为__(11)__。 
(11)
●下图为一确定有限自动机(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..m*n-1],若要对应为 m 行、n 列的矩阵,则下面的对应关系__(14)__可将元素A[k](0≤k<m*n)表示成矩阵的第