当前位置:首页 >> 数学 >>

厦门理工学院10级数据结构期末试卷


厦门理工学院期末考试卷
2011-2012 学年 第一学期 课程名称

数据结构与算法
专业 10 级 班级

试卷 卷别

A B
闭卷






考试 方式

学号

开卷 □

本试卷共 四 大题( 4 页),满分 100 分,考试时间 120 分钟。 请在答题纸上作答,在试卷上作答无效。



线

姓名

一、选择题: (本题共 20 小题,每题 2 分,共 40 分)
(1) 对数据结构,下列结论中不正确的是( ) A.相同的逻辑结构,对应的存储结构也必相同 B. 数据结构由逻辑结构、存储结构和基本操作 3 个方面组成 C. 数据存储结构就是数据逻辑结构的机内的实现 D. 对数据基本操作的实现与存储结构有关 (2) 下面程序的时间复杂度为( ) for(int i=0;i<m;i++) for(int j=0;j<n;j++) a[i][j]=i*j; A.O(n2) B.O(nm) C.O(m2)







10

级 班级



专业



D.O(n+m)

(3) 若一个栈的输入序列为 1、2、3、……n,输出序列的第一个元素为 i,则第 j 个输出元素为( ) A.i-j-1 B.i-j C.j-i+1 D.不确定 (4) 设 H 是带头节点的单循环链表的头指针,节点的指针域为 next,数据域为 data,则指针 p 是指向链表尾的条件是( ) A.p->next==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
第 1 页 共 4 页

(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. (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.任何一项活动持续时间的改变都可能会影响关键路径的改变
第 2 页 共 4 页

二、分析运算题(本题共 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 开始, 根据邻接表对图用广度优先搜索法进行遍历时的顶 点序列。



专业 系 装

10

级 班级





第 3 页 共 4 页

三、程序填空题(本题共 5 空,每空 2 分, 共 10 分)
链式表表示和实现线性表的部分程序如下,请在 程序空白处填上适当的语句: //线性表的单链表存储结构 typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList; } 中

_____ ④ _____; // 将新结点插入到单链表 L

_____⑤_____; // 修改第 i-1 个结点指针 return OK;

四、算法设计题(本题共 1 小题,每题 14 分,共 14 分)
1. 如果通讯字符 a,b,c,d 出现频度分别为 7, 5,2,4 ①某同学设计了如下程序,请根据程序画出对应

//带头结点的单链表 L 中第 i 个位置之前插入元 素 e int 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; } if ( ! p || j >i-1 ) return ERROR; s = ( LinkList ) _____ ② _____ ( sizeof ( LNode ) ); // 生成新结点 s->_____ ③ _____ = e; // 使新结点数据域的 值为 e

的二叉树,计算所画出的二叉树的带权路径长度 (必须写出计算过程,否则不给分) ; if(input==’c’) printf("%c",’c’); else if(input==’d’) printf("%c",’d’); else if(input==’a’) printf("%c",’a’); else printf("%c",’b’); ②请画出赫夫曼(哈弗曼)树(必须画出赫夫曼树 的建树过程); ③计算赫夫曼树的带权路径长度(必须写出计算 过程,否则不给分) ; ④根据赫夫曼树, 用 if-else 语句修改①中的程序, 写出最佳判定算法。

第 4 页 共 4 页


相关文章:
厦门理工学院12级数据结构期末试卷与答案_图文.doc
厦门理工学院12级数据结构期末试卷与答案 - 厦门理工学院试卷 2012-201
厦门理工学院10级数据结构期末试卷_A_图文.pdf
厦门理工学院10级数据结构期末试卷_A - 厦门理工学院期末考试卷 2011-2
厦门理工 10级 数据结构期末试卷_A_图文.doc
厦门理工 10级 数据结构期末试卷_A - 厦门理工学院期末考试卷 2011-2
厦门理工学院 c语言数据结构 级数据结构期末试卷_A_图文.doc
厦门理工学院期末考试卷 2011-2012 学年 第一学期 课程名称 数据结构与算法专业 10 级 班级 试卷 卷别 A B 闭卷 √ □√ 考试 方式 学号 开卷 □ 本试卷...
厦门理工学院数据结构期末考试试题.doc
厦门理工学院数据结构期末考试试题 - 厦门理工学院试卷 20 课程名称 -20
10级数据结构期末试卷_A_图文.doc
10级数据结构期末试卷_A - 厦门理工学院期末考试卷 2011-2012 学年
10级数据结构期末试卷_A_图文.doc
10级数据结构期末试卷_A - 厦门理工学院期末考试卷 2011-2012 学年
数据结构期末试卷_A卷_图文.doc
数据结构期末试卷_A卷_工学_高等教育_教育专区。2012年厦门理工学院数据结构期末...2002级数据结构期末试卷... 4页 免费 2010数据结构期末试卷A 7页 免费 2012...
厦门理工学院12-数据结构与算法+试卷A(双面).pdf
厦门理工学院12-数据结构与算法+试卷A(双面) - 考生信息栏系 专业 级班级 姓名 学号 装订线 厦门理工学院试卷 2013-2014学年 第二 学期 课程名称 数...
数据结构期末试卷_A卷_图文.doc
数据结构期末试卷_A卷 - 厦门理工学院试卷 2012-2013 学年 第二 学
12级数据结构期末试卷_A(双面)_图文.doc
12级数据结构期末试卷_A(双面) - 厦门理工学院试卷 2012-2013 学
厦门理工学院12-数据结构与算法+试卷A(双面).doc
厦门理工学院12-数据结构与算法+试卷A(双面) - 厦门理工学院试卷 2013-2014 学年 第二 学期 课程名称 数据结构与算法 专业 级 班级 试卷 卷别 A ■ B □...
厦门理工学院uml考试试卷A卷.doc
注释、关系和结构 4.在 UML 中,有四种关系,下面...uml期末考试题A卷 2页 1下载券 UML基础与应用...厦门理工学院10级数据结... 4页 5下载券 喜欢...
厦门理工学院高等数学期末考试试卷(大题部分).doc
厦门理工学院高等数学期末考试试卷(大题部分)_理学_高等教育_教育专区。 ...厦门理工学院12级数据结... 8页 1下载券 厦门理工学院高数下册考... 暂无...
厦门理工学院马哲期末考试题目(题目和页数).doc
厦门理工学院马哲期末考试题目(题目和页数)_哲学_高等教育_教育专区。1、马克思
厦门理工数字图像处理_A卷答案-2014.doc
厦门理工数字图像期末考试啊卷 厦门理工学院试卷 2014-2015 学年 第一 学期 ...9. 图像中有一种与像素相关性直接联系着的数据冗余称为 像素间冗余 。 10. ...
厦门理工学院算法期末复习.pdf
厦门理工学院算法期末复习_工学_高等教育_教育专区。...矩阵连乘算法的数据结构形参表中应有n和P[n+1]。...[5] 10 10 10 10 10 maxint 30 60 50 50 ...
厦门理工学院数据结构实验4.doc
厦门理工学院数据结构实验4_计算机软件及应用_IT/计算机...(i=1;i<10;++i) { Push(st,i); printf("...2014小学教师资格考试《... 2014年幼儿园教师资格考...
厦门理工学院 数字电路 期末A卷答案.pdf
厦门理工学院 数字电路 期末A卷答案 - 厦门理工学院试卷答题纸 学年学期: 2012-2013 学年第 1 学期 考试课程: 考试地点: 二栏三 姓名 四五六七八九考 专业...
厦门理工操作系统_试卷(含答案)_图文.doc
A.为内外存容量之和 B.由计算机的地址结构决定 C.是任意的 D.由作业的地址...厦门理工操作系统期末复... 4页 2下载券 厦门理工学院12级数据结... 8...
更多相关标签: