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

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


厦门理工学院期末考试卷
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-数据结构与算法_A答案
厦门理工学院12-数据结构与算法_A答案 - 数据结构与算法 A 卷答案 13-14 学年第二学期 一、单项选择题: (本题共 18 小题,每题 2 分,共 36 分。 ) ...
厦门理工学院数据结构实验2
厦门理工学院数据结构实验2_计算机软件及应用_IT/计算机...三、实验内容与步骤 1.设 A、B 均为用数组实现...# define LIST_INIT_SIZE 10 # define LISTINCREMENT...
更多相关标签: