厦门理工学院c语言数据结构级数据结构期末试卷A

1、考 生 信 息 栏 系 专业 10 级 班级 姓名 学号 装 订 线厦门理工学院期末考试卷20112012 学年 第一学期课程名称数据结构与算法试卷卷别A B 专业 10级 班级 考试方式闭卷 开卷 本试卷共 四 大题( 4 页)，满分100分，考试时间120分钟。请在答题纸上作答，在试卷上作答无效。一、选择题：（本题共20小题，每题2分，共40分）(1) 对数据结构，下列结论中不正确的是（ ）A相同的逻辑结构，对应的存储结构也必相同B. 数据结构由逻辑结构、存储结构和基本操作3个方面组成C. 数据存储结构就是数据逻辑结构的机内的实现D. 对数据基本操作的实现与存储结构有关(2) 下面程序的时

2、间复杂度为（ ） for(int i=0;i<m;i+) for(int j=0;j<n;j+) aij=i*j;AO(n2) B.O(nm) C.O(m2) D.O(n+m)(3) 若一个栈的输入序列为1、2、3、n，输出序列的第一个元素为i，则第j个输出元素为（ ）Ai-j-1 B.i-j C.j-i+1 D.不确定(4) 设H是带头节点的单循环链表的头指针，节点的指针域为next，数据域为data，则指针p是指向链表尾的条件是（ ）Ap->next=NULL B. p->next->next=H C. p->data=0 D. p->next=H

3、(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->

4、;rlink->llink=p->llink;B. p->llink=p->llink->llink;p->llink->rlink=pC. 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

5、,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) 循环队列用数组V0.m-1存放其元素值，已知其头、尾指针分别是f和r，则当前队列中的元素个数是（ A ）A. (r-f+m)%m B. (r-f+1) C. (r-f+m+1)%m D. (r-

6、f+m-1)%m(11) 单循环链表表示的队列长度为n，若只设头指针，则进队的时间复杂度为（ ）A. O(n) B. O(1) C. O(n2) D. O(nlogn)(12) 已知循环队列的存储空间为数组a21，且当前队列的头指针和尾指针的值分别是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. 49

7、8 B. 499 C. 500 D. 501(15) 树中所有节点的度等于所有节点数加（ ）A0 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.

8、 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) 请写出图

9、 1中二叉树的前序(先序)和中序遍历序列。 图 1 图 2(3) 算术表达式如下：a*(b+c)-d。 用二叉树表示算术表达式 写出后序（后缀）表达式(4) 请写出无向图图2中顶点a-f的度。(5) 给定元素序列：（50，25，80，20，76，93），画出按照该序列构造的二叉排序树(必须画出二叉排序树的建树过程)。(6) 下面的邻接表表示一个给定的无向图 请根据邻接表画出无向图 给出从顶点v1开始, 根据邻接表对图用深度优先搜索法进行遍历时的顶点序列； 给出从顶点v1开始, 根据邻接表对图用广度优先搜索法进行遍历时的顶点序列。三、程序填空题（本题共5空，每空2分，共10分）链式表表示和实现线

10、性表的部分程序如下，请在程序空白处填上适当的语句：/线性表的单链表存储结构typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;/带头结点的单链表L中第 i 个位置之前插入元素 eint ListInsert_L ( LinkList &L, int i, int e ) LinkList p,s; int j; /j为计数器p = L; /p指向L的头节点j = 0; while ( p && j<i-1 ) /顺指针向后查，直到p指向第i个元素之前 p = _; +j; i

11、f ( ! p | j >i-1 ) return ERROR; s = ( LinkList ) _ ( sizeof ( LNode ) ); / 生成新结点s->_ = e; / 使新结点数据域的值为 e_; / 将新结点插入到单链表 L 中_; / 修改第 i-1 个结点指针return OK;四、算法设计题（本题共1小题，每题14分，共14分）1. 如果通讯字符a，b，c，d出现频度分别为7，5，2，4某同学设计了如下程序，请根据程序画出对应的二叉树，计算所画出的二叉树的带权路径长度（必须写出计算过程，否则不给分）；if(input=c) printf("%c&

12、quot;,c); else if(input=d) printf("%c",d); else if(input=a) printf("%c",a); elseprintf("%c",b); 请画出赫夫曼（哈弗曼）树(必须画出赫夫曼树的建树过程)；计算赫夫曼树的带权路径长度（必须写出计算过程，否则不给分）；根据赫夫曼树，用if-else语句修改中的程序，写出最佳判定算法。数据结构与算法A卷答案一、 选择题（本题共20小题，每题2分，共40分）1 A2 B3 D4 D5 B6 B7 A8 B9 C10 A11 A12 C13 D14 D

13、15 C16 C17 A18 D19 D20 D二、分析运算题（本题共6小题，每题6分，共36分）(1) 如果输入序列为6 5 4 3 2 1,试问能否通过栈结构得到以下两个序列3 4 6 5 2 1和2 3 4 1 5 6;请说明为什么不能或如何才能得到输出序列2 3 4 1 5 6可以得到（2分）输出序列3 4 6 5 2 1不能得到（2分），其理由是，输出序列中间两元素是6 5，前面2个元素（3 4）得到后，栈中元素剩6 5，且5在栈顶，不可能栈底元素6在栈顶元素5之前出栈(2分)。(2) 请写出图中二叉树的前序(先序)和中序遍历序列。前序(先序)：ABDCEF （3分）中序：DBAEC

14、F （3分）(3) 算术表达式如下：a*(b+c)-d 用二叉树表示算术表达式 写出后序（后缀）表达式 +d-abc* （3分）后序（后缀）表达式：abc+*d-（3分）(4) 请写出无向图中顶点a-f的度a:3（1分）b:2（1分）c:1（1分）d:2（1分）e:4（1分）f:2（1分）(5) 给定元素序列：（50，25，80，20，76，93），画出按照该序列构造的二叉排序树(必须画出二叉排序树的建树过程)。502580769320每个结点1分(6) 下面的邻接表表示一个给定的无向图 请根据邻接表画出无向图 给出从顶点v1开始, 根据邻接表对图用深度优先搜索法进行遍历时的顶点序列； 给出从

15、顶点v1开始, 根据邻接表对图用广度优先搜索法进行遍历时的顶点序列。V5V3V1V4V6V2（2分）深度序列：V1 V2 V5 V3 V4 V6 （2分）广度序列：V1 V2 V3 V4 V5 V6 （2分）三、程序填空题（本题共5空，每空2分，共10分）p->next（2分）malloc（2分）data（2分）s->next = p->next（2分）p->next = s（2分）四、算法设计题（本题共1小题，每题14分，共14分）1. 如果通讯字符a，b，c，d出现频度分别为7，5，2，4某同学设计了如下程序，请根据程序画出对应的二叉树，计算所画出的二叉树的带权路径长度（必须写出计算过程，否则不给分）；请画出赫夫曼（哈弗曼）树(必须画出赫夫曼树的建树过程)；计算它的带权路径长度（必须写出计算过程，否则不给分）根据赫夫曼树，用if-else语句修改中的程序，写出最佳判定算法。1641275218abdc（2分）WPL = 7*3 + 5*3 + 4*