2011-1 2009级数据结构期末考试试卷.doc

西华师范大学学生试卷 年 月 日 学年第 学期 考室 题号 一 二 三 四 五 六 七 八 九 十 总分 阅卷教师 得分 计算机学院计算机科学与技术专业2009级《数据结构》试题 A卷 闭卷考试 时间120分钟 注意事项：1.满分：100 分。保持卷面整洁，否则扣卷面 2分。 2.交卷时请将试题卷与答题卷一起交，否则扣分。 3.学生必须将姓名、班级、学号完整填写在规定的密封栏目内，否则视为废卷。 4.学生必须签到，否则出现遗漏由学生本人负责。 得分 阅卷人 一、选择题（每小题2分，共32分） 1、在线性表的顺序存储结构中，若第1个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。 A、110 B、108 C、100 D、120 2、判定一个循环队列q（最多元素个数为M）为空的条件是（ ）。 A、q.front=q.rear B、q.frontq.rear C、q.front=(q.rear+1) mod M D、q.front(q.rear+1) mod M 3、在循环双链表中P所指结点之后插入S所指结点的操作是（ ）。 p^.next:=s; s^.prior:=p; p^.next^.prior:=s; s^.next:=p^.next; p^.next:=s; p^.next^.prior:=s; s^.prior:=p; s^.next:=p^.next; s^.prior:=p; s^.next:=p^.next; P^.next:=s; p^.next^.prior:=s; s^.prior:=p; s^.next:=p^.next; p^.next^.prior:=s; p^.next:=s; 4、从一个具有n个结点的单链表中查找其值为X的结点时，在查找成功的情况下，需要平均比较（ ）个结点。 A、n B、n/2 C、(n-1)/2 D、(n+1)/2 5、在下列程序段中，其执行的时间复杂度为（ ） Int sum(int n) {int sum=0; Int I,p=1; for I=1 to n do {p=p*I; sum:=sum+p; } return(sum); } A、O（0） B、O（1） C、O（n） D、O（n2） 6、递归函数f(n)=f(n-1)+n(n1)的递归体是（ ） A、f(1)=0 B、f(0)=1 C、f(n)=f(n-1)+n D、f(n)=n 7、有4个叶子结点，分别权值为7、5、2、4，则通过叶子结点所构造的哈夫曼树的带权的路径长度为（ ） A、34 B、35 C、36 D、46 8、在图中，一棵有n个顶点的生成树，有且仅有（ ）条边。 A、n B、n-1 C、2n-1 D、2n 9、树的基本遍历策略可为先根和后根遍历，二叉树基本遍历分为先序、中序、后序，把由树转化得到的二叉树叫这棵树对应的二叉树，则结论（ ）正确。 树的先根遍历序列与对应二叉树先序遍历相同 树的后根遍历序列与对应二叉树后序遍历相同 树的先根遍历序列与对应二叉树中序遍历相同 D、以上均不对。 10、在有向图的邻接表中，第i个链表中的表结点数是（ ） A、顶点Vi的度； B、顶点Vi的出度； C、顶点Vi的入度； D、依附于顶点Vi的弧数。 11、设有一棵三叉树（度为3的树），其叶结点数为n0，度为1的结点数为n1，度为2 的结点数为n2，度为3的结点数为n3，则n0与n1、n2、n3的关系应为（ ） A、n0=n2+1 B、n0=n2+2n3+1 C、n0=n2+n3+1 D、n0=n1+n2+n3 12、设一棵二叉树中只有度为2的结点和叶子结点，已知度为2的结点的数为n，则该二叉树的结点总数为（ ）。 A、2n-1 B、2n C、2n+1 D、2n+2 13、在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。 A、2 B、 1 C、 0 D、–1 14、设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（