考 生 信 息 栏 系 专业 10 级 班级 姓名 学号 装 订 线 厦门理工学院期末考试卷 2011－2012 学年 第一学期 课程名称 数据结构与算法 试卷 卷别 A √ B □ 专业 10级 班级 考试 闭卷 √ 方式 开卷 □ 本试卷共 四 大题( 4 页)，满分100分，考试时间120分钟。 请在答题纸上作答，在试卷上作答无效。 一、选择题：（本题共20小题，每题2分，共40分） (1) 对数据结构，下列结论中不正确的是（ ） A．相同的逻辑结构，对应的存储结构也必相同 B. 数据结构由逻辑结构、存储结构和基本操作3个方面组成 C. 数据存储结构就是数据逻辑结构的机内的实现 D. 对数据基本操作的实现与存储结构有关 (2) 下面程序的时间复杂度为（ ） for(int i=0;inext==NULL B. p->next->next==H C. p->data==0 D. p->next==H (5) 若要在O(1)的时间复杂度上实现两个循环链表表头尾相接，则对应两个循环链表各设置一个指针，分别指向（ ） A.各自的头节点 B.各自的尾节点 C.各自的第一个元素节点 D.一个表的头节点，另一个表的尾节点 (6) 一个链队列中，假设f和分别为队首和队尾指针，则插入s所指节点的运算是（ ） A. f->next=s;f=s; B. r->next=s;r=s; C. s->next=r;r=s; D. s->next=f;f=s (7) 在双向链表中删除指针p所指的节点时需要修改指针（ ） A. p->llink->rlink=p->rlink;p->rlink->llink=p->llink; B. p->llink=p->llink->llink;p->llink->rlink=p C. p->rlink->llink=p;p->rlink=p->rlink->rlink; D. p->rlink=p_>llink->llink;p->llink=p->rlink->rlink (8) 设栈s和队列q的初始状态为空，6个元素入栈的顺序为：a1,a2,a3,a4,a5,a6，一个元素出栈之后立即入队列q，若6个元素出对的顺序是：a2,a4,a3,a6,a5,a1，则栈s的容量至少应该是（ ）。 A. 2 B. 3 C. 4 D. 6 (9) 向一个栈顶指针为top的链栈中插入一个s节点，则执行（ ） A. top->next=s; B. s->next=top->next;top-next=s; C. s->next=top;top=s; D. s->next=top;top=top->next; (10) 循环队列用数组V[0..m-1]存放其元素值，已知其头、尾指针分别是f和r，则当前队列中的元素个数是（ A ） A. (r-f+m)%m B. (r-f+1) C. (r-f+m+1)%m D. (r-f+m-1)%m (11) 单循环链表表示的队列长度为n，若只设头指针，则进队的时间复杂度为（ ） A. O(n) B. O(1) C. O(n2) D. O(nlogn) (12) 已知循环队列的存储空间为数组a[21]，且当前队列的头指针和尾指针的值分别是8和3，则该队列的当前长度为（ ）。 A. 5 B. 6 C. 16 D. 17 (13) 一棵树共有n个节点的数，其中所有分支节点的度均为k，则该数中叶子节点的个数为（ ）。 A. n(k-1)/k B. n-k C. (n+1)/k D. (nk-n+1)/k (14) 若一棵二叉树有1001个节点，且无度为1的节点，则叶子节点的个数为（ ） A. 498 B. 499 C. 500 D. 501 (15) 树中所有节点的度等于所有节点数加（ ） A．0 B. 1 C. -1 D. 2 (16) 设高度为h的二叉树只有度为0和度为2的节点，则此类二叉树中所包含的节点数至少为（ ） A. 2h B. 2h+1 C. 2h-1 D. h-1 (17) 设某二叉树的前序序列为abdcef，中序为dbaecf，则此二叉树的后序为（ ） A. dbefca B. debfca C. dfebca D. dbfeca (18) 线索二叉树中的线索是指（ ） A. 左孩子 B. 右孩子 C. 遍历 D. 指针 (19) 具有10个顶点的无向图最多有（ ）条边。 A. 0 B. 9 C. 10 D. 45 (20) 对AOE网的关键路径，下面的说法（ ）是正确的 A．提高关键路径上的一个关键活动的速度，必然使得整个工期缩短； B．完成工程的最短时间是从始点到终点的最短路径的长度 C．一个AOE网的关键路径只有一条，但关键路径活动可有多个 D．任何一项活动持续时间的改变都可能会影响关键路径的改变 考 生 信 息 栏 系 专业 10 级 班级 姓名 学号 二、分析运算题（本题共6小题，每题6分，共36分） (1) 如果输入序列为6 5 4 3 2 1,试问能否通过栈结构得到以下两个序列3 4 6 5 2 1和2 3 4 1 5 6;请说明为什么不能或如何才能得到。 (2) 请写出图 1中二叉树的前序(先序)和中序遍历序列。 装 订 线 图 1 图 2 (3) 算术表达式如下：a*(b+c)-d。 ① 用二叉树表示算术表达式 ② 写出后序（后缀）表达式 (4) 请写出无向图图2中顶点a-f的度。 (5) 给定元素序列：（50，25，80，20，76，93），画出按照该序列构造的二叉排序树(必须画出二叉排序树的建树过程)。 (6) 下面的邻接表表示一个给定的无向图 ① 请根据邻接表画出无向图 ② 给出从顶点v1开始, 根据邻接表对图用深度优先搜索法进行遍历时的顶点序列； ③ 给出从顶点v1开始, 根据邻接表对图用广度优先搜索法进行遍历时的顶点序列。