中级软件设计师单项选择试卷（中级软件设计师）_8.docVIP

试卷第 PAGE 10 页共 NUMPAGES 14 页 中级软件设计师单项选择试卷（中级软件设计师） 姓名:_____________ 年级:____________ 学号:______________ 题型 选择题 填空题 解答题 判断题 计算题 附加题 总分 得分 评卷人 得分 1、循环链表的主要优点是（ ）。 A.不再需要头指针了 B.已知某个节点的位置后，能很容易找到它的直接前驱节点 C.在进行删除操作后，能保证链表不断开 从表中任一节点出发都能遍历整个链表2、若循环队列以数组Q[O..m-1]作为其存储结构，变量rear表示循环队列中队尾元素的实际位置，其移动按rear=（rear+1）modm进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是（ ）。 A.rear-length B.(rear-length+m) mod m C.(1+rear+m-length) mod m m-length3、若广义表L（（1，2，3）），则L的长度和深度分别为（ ）。 A.1和1 B.1和2 C.1和3 2和24、已知有一维数组A（0..m*n-1]，若要对应为m行、n列的矩阵，则下面的对应关系（ ）可将元素A[k]（0≤k＜m*n）表示成矩阵的第i行、第j列的元素（0≤i＜m，0≤j＜n）。 A.i=k,j=k%m B.i=k/m,j=K%m C.i=k,j=k%n i=k/m,j=k%n5、为便于存储和处理一般树结构形式的信息，常采用孩子-兄弟表示法将其转换成二叉树（左子关系表示父子、右子关系表示兄弟），与图8-2所示的树对应的二叉树是（ ）。 A.A B.B C.C D6、在平衡二叉树中，（ ）。 A.任意节点的左、右子树节点数目相同 B.任意节点的左、右子树高度相同 C.任意节点的左、右子树高度之差的绝对值不大于1 不存在度为1的节点7、已知某二叉树的中序、层序序列分别为DBAFCE，FDEBCA，则该二叉树的后序序列为（ ）。 A.BCDEAF B.ABDCEF C.DBACEF DABECF8、在二叉树的顺序存储中，每个节点的存储位置与其父节点、左右子树节点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个节点，采l B.38 C.51 7510、表达式a*（b+c）-d的后缀表达形式为（ ）。 A.abcd*+- B.abc+*d- C.abc*+d- -+*abcd11、若二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则其后序遍历序列为（ ）。 A.DEBAFC B.DEFBCA C.DEBCFA DEBFCA12、在常用的描述二叉排序树的存储结构中，关键字值最大的节点（ ）。 A.左指针一定为空 B.右指针一定为空 C.左右指针均为空 左右指针均不为空13、由权值为9，2，5，7的四个叶子构造一棵哈夫曼树，该树的带权路径长度为（ ）。 A.23 B.37 C.44 4614、在一棵完全二叉树中，其根的序号为1，（ ）可判定序号为p和q的两个节点是否在同一层。 A.[logp]=[log2q) B.log2 p=log2 q C.[log2 p]+1=[log2q) [log2 p]=[log2 q)+115、若一棵哈夫曼(Huffman)树共有9个顶点，则其叶子节点的个数为（ ）。 A.4 B.5 C.6 716、在一棵度为3的树中，若有2个度为3的节点，有1个度为2的节点，则有（ ）个度为0的节点。 A.4 B.5 C.6 717、设节点x和y是二叉树中任意的两个节点，在该二叉树的先根遍历序列中x在y之前，而在其后根遍历序列中x在y之后，则x和y的关系是（ ）。 A.x是y的左兄弟 B.x是y的右兄弟 C.x是y的祖先 x是y的后裔18、一个具有767个节点的完全二叉树，其叶子节点个数为（ ）。 A.383 B.384 C.385 38619、若一个具有n个节点、k条边的非连通无向图是一个森林（n＞k），则该森林中必有（ ）棵树。 A.k B.n C.n-k n+k20