厦门理工学院12级数据结构期末试卷与答案

1、考 生 信 息 栏 系 专业 级 班级 姓名 学号 装 订 线厦门理工学院试卷20122013学年 第 一 学期课程名称数据结构与算法试卷卷别 A B 专业 2011 级 班级 考试方式闭卷 开卷 本试卷共 四 大题(4页)，满分100分，考试时间120分钟。请在答题纸上作答，在试卷上作答无效。 一、选择题：（本题共20小题，每题2分，共40分）1、链式存储的存储结构所占存储空间（ ）。 A 分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针 B 只有一部分，存放结点的值 C 只有一部分，存储表示结点间关系的指针 D 分两部分，一部分存放结点的值，另一部分存放结点所占单元素2、已知

2、一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（ ）。A B+(i-1)*m BB+i*m C B-i*m D B+(i+1)*m3、两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（ ）。AP-next=Q-next BP-next= Q CQ-next= P DP=Q4、下面关于线性表的叙述中，错误的是（ ）关系。A顺序表必须占一片地址连续的存储单元 B顺序表可以随机存取任一元素C链表不必占用一片地址连续的存储单元 D链表可以随机存取任一元素5、等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目

3、为（ ）。AnB(n-1)/2 C n/2 D(n+1)/26、设数组datam作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ）。 Afront=front+1 Bfront=(front+1)%(m-1) Cfront=(front-1)%m Dfront=(front+1)%m7、下列算法的时间复杂度是（ ）。 for (i=0;in;i+) for (j=0;jnext; Btop=top-next; x=top-data; Cx=top-data; Dx=top-data; top=top-next;9、经过下列栈的运算

4、后，x的值是（ ）。 InitStack(s) （初始化栈）;Push(s, a);Push(s, b);ReadTop(s);Pop(s, x);Aa Bb C1 D010、一个栈的入栈次序ABCDE，则栈的不可能的输出序列是 ( )。 AEDCBA BDECBA CDCEAB DABCDE11、设某棵二叉树中有2000个站点，则该二叉树的最小高度为（ ）。 A、9 B、10 C、11 D、1212、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( )。 A5和1 B4和2 C2和4

5、D1和513、根据二叉树的定义，具有3个结点的二叉树有（ ）种树型。 A3 B4 C5 D614、如右图所示的二叉树，后序遍历的序列是（ ）ABADECFGHI A A、B、C、D、E、F、G 、H、I B A、B、D、H、I、E、C、F、G C H、D、I、B、E、A、F、C、G D H、I、D、E、B、F、G、C、A15、下列陈述正确的是（ ）。A二叉树是度为2的有序树B二叉树中结点只有一个孩子时无左右之分C二叉树中必有度为2的结点 D二叉树中最多只有两棵子树，且有左右子树之分16、在有n个叶子结点的哈夫曼树中，非叶子结点的总数是（ ）。n-1 n 2n-1 2n17、对于一个具有n个顶点

6、的有向图的边数最多有（ ）。 An Bn(n-1) Cn(n-1)/2 D2n18、对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（ ）。 An-1Bn+1 Cn Dn+e19、下面关于图的存储结构的叙述中正确的是（ ）。A 用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关B 用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关 C 用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关 D 用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关20、二叉树为二叉排序树的（ ）条件是其任一结点的值均大于其左孩子的值，小于其右孩子的值。

7、A充分不必要 B必要不充分 C充分必要 D既不充分也不必要二、分析运算题（本题共6小题，每题5分，共30分）1、如果输入序列为1 2 3,先进入栈结构后进入队列结构，试写出所有的出队列序列。2、 假设一棵二叉树的前序(先序)遍历序列为ABDECF和中序序列为DBEAFC，画出二叉树并写出后序遍历序列。 图 1 图 2 图33、用二叉树表示算术表达式如图1所示。 按图画出对应的算术表达式 写出后序（后缀）表达式4、请写出有向图2中顶点1-6的入度和出度。5、给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为huffman(赫夫曼) 树。给定项及相应的权如下表：

8、画出相应的huffman树。序号 1 2 3 4 5 6 7 8 9项 A B C D E F G H I权值15 6 71225 4 6 1156、 已经邻接矩阵如图3所示，判断该图是有向图还是无向图，用顶点1-6画出该图。三、程序填空题（本题共5空，每空2分，共10分）1、下面程序段的功能是在单链表中查找元素数据x，若找到，返回指向该结点的指针；否则返回空指针，请在下划线处填上正确的内容。 / 在单链表L中查找元素xtypedef struct LNode DataType data; struct LNode *next; LNode, *LinkList;LinkList Find (

9、 LinkList L, DataType x ) p = L-next; / L为带头节点的单链表 while ( （1） ) if ( p-data = = x ) return p; / 找到x （2） return NULL; / 未找到2、下面程序段的功能实现删除队列中的队头数据（若队列不空），并用x返回其值，要求在下划线处填上正确的语句。typedef struct QNode DataType data; struct QNode *next; QNode, *QueuePtr;typedef struct LQ QueuePtr front; QueuePtr rear;Lin

10、kQueue;int DeQueue ( LinkQueue &Q, DataType &x ) if ( （3） ) return ERROR;p= Q.front-next;x=p-data; （4） if (Q.rear= =p) （5） free(p); return OK;线 订 装考 生 信 息 栏 系 专业 级 班级 姓名 学号 装 订 线四、算法设计题（本题共2小题，共20分）1、（10分）已知一个顺序表，每个元素都是整数，试设计用最少时间把所有值为负数的元素移动到全部正数值元素前面的算法。typedef struct int *elem; int length ; int l

11、istSize; sqlist;2、（10分）以二叉链表为存储结构，编写计算二叉树中叶子结点数目的递归函数。typedef struct BiTNode int data; struct BiTNode *lchild, *rchild;BiTNode,*BiTree;数据结构与算法A卷答案12-13学年第一学期一、选择题：（本题共20小题，每题2分，共40分）1-5：AABDC 6-10：DDDBC 11-15：CBCDD 16-20：ABCAB二、分析运算题（本题共6小题，每题5分，共30 分）(1) 如果输入序列为1 2 3,先进入栈结构后进入队列结构，试写出所有的出队列序列。输出序列1

12、 2 3（1分）输出序列1 3 2（1分）输出序列2 1 3（1分）输出序列2 3 1（1分）输出序列3 2 1（1分）输出序列3 1 2（扣3分）(2) 假设一棵二叉树的前序(先序)遍历序列为ABDECF和中序序列为DBEAFC，画出二叉树并写出后序遍历序列。 （3分）后序遍历：DEBFCA （2分）(3) 用二叉树表示算术表达式如图1所示。 按图画出对应的算术表达式 写出后序（后缀）表达式算术表达式：(a+b+c*(d+e)+f)*(g+h) （2分）后序表达式：ab+cde+*+f+gh+*（3分）(4) 请写出有向图2中顶点1-6的入度和出度1: 入度：3出度：02: 入度：2出度：2

13、3: 入度：1出度：24: 入度：1出度：35: 入度：2出度：16: 入度：2出度：3(入度2.5分，出度2.5分)(5) 给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为huffman(赫夫曼) 树。给定项及相应的权如下表：画出相应的huffman树。(5分)9153382825E15I2315A1312D116G7C6B54F1H(6)已经邻接矩阵如图3所示，判断该图是有向图还是无向图，用顶点1-6画出该图。有向图（2分）（3分）三、程序填空题（本题共5空，每空2分，共10分）(1)：p!=NULL(2)：p = p-next;(3): Q.front= =Q.rear(4): Q.front-next=p-next;(5): Q.rear=Qfront;四、算法设计题（本题共