试卷代号：1010 座位号口 中央广播电视大学2008-2009学年度第一学期“开放本科”期末考试 数据结构 试题 2009年1月 题 号 一 二 三 四 五 六 总 分 分 数 得 分 评卷人 一、单项选择题（在括号内填写所选择的标号。每小题2分，共18 分) 得分 1. 下面算法的时间复杂度为( int f(unsigned int n)( if (n==0 n==1)return 1; else return n f(n-1); } A.O(1) B.O(n) C.O(n2) D.O(n!) 得分 2.在一个长度为的线性表中顺序查找一个值为×的元素时，在等概率的情况下， 查找成功时的平均查找长度为()。 A.n B.n/2 C.(n+1)/2 D.(n-1)/2 得分 3. 已知L为一个单链表的表头指针，在表头插入结点p的操作是()。 A.p=L;p->link=L; B.p->link=L;p=L; C.p->link=L;L=p; D.L=p;p->link=L; 得分 4. 若有一个循环队列Q,队首和队尾指针分别为front的rear,则判断队列满的条件 为()。 A.Q.front==Q.rear; B.Q.front-Q.rear==MaxSize; C.Q.front+Q.rear==MaxSize; D.Q.front==(Q.rear+1)%MaxSize; 得分 5. 在一棵完全二叉树中，若编号为i的结点存在左子女，则左子女结点的编号为()， 假定树根结点的编号为0。 A.2i B.2i-1 C.2i+1 D.2i+2 70试卷代号:1010 座位号口口 中央广播电视大学2008-2009学年度第一学期“开放本科”期末考试 数据结构 试题 2009年 1月 题 号 四 五 六 总 分 分 数 得 分 评卷人 一、单项选择题 (在括号内填写所选择的标号。每小题 2分。共 18 分) F% 3二」1·下面算法的时间复杂度为( int f (unsigned int n) if (n= 二0 else return !! n=“1) return 1; n‘f(n一1); } A. O(1) C. 0(n2) B. O(n) D. O(n!) 0州 】2.在一个长度为 n的线性表中顺序查找一个值为 x的元素时，在等概率的情况下 ， 查找成功时的平均查找长度为( )。 A. n C. (n+ 1)/2 B. n/2 D. (n一i)/2 Fpf -}二]3·已知L为一个单链表的表头指针，在表头插人结点‘p的操作是( p一>link=L; P=L B. D. A. p=L; p一>link=L; L=p; L=p; 卜导州 14. C. p一>link=L; 若有一个循环队列Q，队首和队尾指针分别为 front p一>link=L; 的 rear，则判断队列满的条件 f I}州 卜 为( )。 A. Q. front=“Q. rear; B. Q. front一Q. rear==MaxSize; C. Q. front+Q. rear==MaxSize; D. Q. front二=(Q. rear+1)%MaxSize; 在一棵完全二叉树中，若编号为 i的结点存在左子女，则左子女结点的编号为( )， 假定树根结点的编号为 。。 A. 2i B. 2i一 1 C. 2i+ 1 . D. 21+ 2