当前位置:首页 >> 理学 >> 《数据结构》期末考试试题及答案

《数据结构》期末考试试题及答案


《数据结构》期末考试试题及答案
(2003-2004 学年第 2 学期)

贵州大学理学院数学系信息与计算科学专业

一、

单项选择题

1.对于一个算法,当输入非法数据时,也要能作出相应的处理,这种要求称为 ( ) 。 (A)、正确性 (B). 可行性 (C). 健壮性 (D). 输入性 2.设 S 为 C 语言的语句,计算机执行下面算法时,算法的时间复杂度为( for(i=n-1;i>=0;i--) for(j=0;j<i;j++) S; (A)、n2 (B). O(nlgn) (C). O(n) ) 。 (B) 、有序单链表 ) 。 (D). O(n2) 3.折半查找法适用于( (A) 、有序顺序表 ) 。

(C) 、有序顺序表和有序单链表都可以 (D) 、无限制 4.顺序存储结构的优势是( (A) 、利于插入操作 (B) 、利于删除操作 (C) 、利于顺序访问 (D) 、利于随机访问 5.深度为 k 的完全二叉树,其叶子结点必在第( )层上。 (A) 、k-1 (B) 、k (C) 、k-1 和 k (D) 、1 至 k 6. 具有 60 个结点的二叉树, 其叶子结点有 12 个, 则度过 1 的结点数为 ( ) (A) 、11 (B) 、13 (C) 、48 (D) 、37 7.图的 Depth-First Search(DFS)遍历思想实际上是二叉树( )遍历方法 的推广。 (A) 、先序 (B) 、中序 (C) 、后序 (D) 、层序 8.在下列链队列 Q 中,元素 a 出队的操作序列为(
front



a

b

c

d ∧

Q rear (A) 、p=Q.front->next; p->next= Q.front->next; (B) 、p=Q.front->next; Q.front->next=p->next; (C) 、p=Q.rear->next; p->next= Q.rear->next; (D) 、p=Q->next; Q->next=p->next; 9. Huffman 树的带权路径长度 WPL 等于( (A) 、除根结点之外的所有结点权值之和 (C) 、各叶子结点的带权路径长度之和 10.线索二叉链表是利用( ) (B) 、所有结点权值之和 (D) 、根结点的值

)域存储后继结点的地址。
第 1 页 共 7 页

(A) 、lchild

(B) 、data

(C) 、rchild

(D) 、root

二、填空题
1. 逻 辑 结 构 决 定 了 算 法 的 的 。 的线性表, 栈的插入和删除只能在 进行。 2. 栈和队列都是一种 的存储地址 LOC(ai)为 4. 已知一双向链表如下(指针域名为 next 和 prior): ,而存储结构决定了算法

3. 线性表(a1,a2,…,an)的顺序存储结构中,设每个单元的长度为 L,元素 ai

x
q p
e

y

现将 p 所指的结点插入到 x 和 y 结点之间,其操作步骤 为: ; ; ; ; 5.n 个结点无向完全图的的边数为 n 个结点的生成树的边数为 6.已知一有向无环图如下:
B A C D E F G

, 。

任意写出二种拓扑排序序列: 遍历序列为

、 ,层序遍历序列为 。



7.已知二叉树的中序遍历序列为 BCA,后序遍历序列为 CBA,则该二叉树的先序

三、应用题
1. 设散列函数 H(k)=k % 13,设关键字系列为{22,12,24,6,45,7,8,13,21},要 求用线性探测法处理冲突。(6 分) (1) 构造 HASH 表。 (2) 分别求查找成功和不成功时的平均查找长度。 2. 给定表(19,14,22,15,20,21,56,10).(8 分) (1) 按元素在表中的次序,建立一棵二叉排序树
第 2 页 共 7 页

(2) 对(1)中所建立的二叉排序树进行中序遍历,写出遍历序列。 (3) 画出对(2)中的遍历序列进行折半查找过程的判定树。 3. 已知二个稀疏矩阵 A 和 B 的压缩存储三元组表如下: A
i 1 2 2 4 5 j 3 4 5 2 2 V -5 6 2 -1 9 i 2 3 4 5 5

B
j 5 3 1 2 5 V 2 7 3 -9 8

写出 A-B 压缩存储的三元组表。 (5 分) 4. 已知一维数组中的数据为(18,12,25,53,18), 试写出插入排序(升序)过 程。并指出具有 n 个元素的插入排序的时间复杂度是多少?(5 分) 5. 已知一网络的邻接矩阵如下,求从顶点 A 开始的最小生成树。(8 分,要有 过程) A B C D E F

A ?? 6 5 1 ? ? ? ? B? ? 6 ? ? 5 3 ?? C ?5 ? ? 7 ? 2? ? ? D ?1 5 7 ? 6 4? E ?? 3 ? 6 ? 6 ? ? ? F? ?? ? 2 4 6 ? ? ?
(1)求从顶点 A 开始的最小生成树。 (2)分别画出以 A 为起点的 DFS 生成树和 BFS 生成树。 6.已知数据六个字母及在通信中出现频率如下表: A 0.15 B 0.15 C 0.1 D 0.1 E 0.2 F 0.3

把这些字母和频率作为叶子结点及权值,完成如下工作(7 分,要有过程)。 (1) 画出对应的 Huffman 树。 (2) 计算带权路径长度 WPL。 (3) 求 A、B、C、D、E、F 的 Huffman 编码。
第 3 页 共 7 页

7. 已知有如下的有向网: A 2 B 3 6 4 10 C
2

5 E

6

D

1

2

求顶点 A 到其它各顶点的最短路径(采用 Dijkstra 算法,要有过程) 。 (6 分)

三、 设计题(30 分,每题 10 分,用 C 语言写出算法,做在答题纸 上)
1. 已知线性表(a1,a2,…,an)以顺序存储结构为存储结构,其类型定义如下: #define LIST_INIT_SIZE 100 //顺序表初始分配容量 typedef struct { Elemtype *elem; //顺序存储空间基址 int length; //当前长度(存储元素个数) }SqList; 设计一个算法,删除其元素值为 x 的结点(假若 x 是唯一的) 。并求出其算法的 平均时间复杂度。其算法函数头部如下: Status ListDelete(Sqlist &L,Elemtype x) { …… } 2.设顺序栈如左图所示。 其中结点定义如下: typedef struct { Elemtype *base; //栈底指针 Elemtype *top; //栈顶指针 }Stack; 设计算法,将栈顶元素出栈并存入 e 中. 3.设二叉链树的类型定义如下: typedef int Elemtype; typedef struct node{ Elemtype data; struct node *lchild, *rchild; }BinNode, *BinTree; 试写出求该二叉树叶子结点数的算法:
第 4 页 共 7 页

top

an … a2 a1

base

Status CountLeaves(BinTree &root,int &n) {//n is the number of leaves …… }

答案:
选择题(每题 1 分) 1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、填空题 1.设计、实现 2.特殊、栈顶 3.LOC(a1)+(i-1)*L 4.p->next=q->next;q->next->prior=p; q->next=p;p->prior=q; 5.n(n-1)/2、n-1 6.ADCBFEG、ABCDEFFG 7.ABC、ABC 二、应用题 1 (1)Hash 表(4 分) 0 1 2 3 4 5 6 7 8 9 地址 13 21 6 45 7 22 关键安 1 7 1 2 3 1 探测次数 (2)查找成功的平均查找长度: (1 分) (5*1+1*2+2*3+1*7)/9=20/9 查找不成功的平均查找长度: (1 分) (2+1+9+8+7+6+5+4+3+2+1)/13= 2(1) 、构造(3 分) 19 14 10 15 22 20 21 (2)、10 14 15 19 20 21 22 56(2 分) (3) 、 (3 分) 56

10 8 3

11 24 1

12 12 1

第 5 页 共 7 页

3、(5 分,每行 0.5) j 3 4 3 1 2 2 5 4、 初始关键字: [18] 第 一 趟:[12 第 二 趟:[12 第 三 趟:[12 第 四 趟:[12 2 O(n ) (1 分) 。 5、7 分 (1)4 分 A B 3 5 D4 E (2)4 分 F 1 2 C i 1 2 3 4 4 5 5 v -5 6 7 3 -1 18 8 12 25 18] 25 18 25] 18 25 18 18

53 53 53 53] 25

18 18 18 18 53]

(4 分)

6、(1) 3 分

E A B

F C D

第 6 页 共 7 页

(2)WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21= (1 分) (3)A:010 B:011 C:110 D:111 E:00 F;10 (3 分) 12、A-B: (A、B) 1分 A-C: (A、D、C) 2 分 A-D: (A、D) 1分 A-E: (A、D、E) 2 分 三,设计题(20 分) 1、(10 分) Status ListDelete(Sqlist &L,ElemType x) { int i,j; for(i=0;i<L->length;i++) if(L->elem[i]==x) break; if(i=L->length) return ERROR; for(j=i;j<L->lengthi-1;j++) L->elem[j]=L->elem[j+1]; L->length--; } (8 分) 平均时间复杂度: (2 分) 设元素个数记为 n,则平均时间复杂度为:

E?

1 n n ?1 (n ? i ) ? ? n i ?1 2

2(10 分) void pop(Stack &S,Elemtype &e) { if(S.top==S.base) return ERROR; S.top--; e=*s.top; } 2、 (10 分) voidCountLeaves(BinTree T,int &n) { if(T) { if((!(T->lchild)&&!( T->rchild)) n++; CountLeaves (T->lchild,n); CountLeaves (T->rchild,n); } }

第 7 页 共 7 页


更多相关文档:

《数据结构》期末考试试题及答案

《数据结构》期末考试试题及答案 (2003-2004 学年第 2 学期) 贵州大学理学院数学系信息与计算科学专业 一、 单项选择题 1.对于一个算法,当输入非法数据时,也...

《数据结构》期末考试试题及答案

《数据结构》期末考试试题及答案 (2003-2004 学年第 2 学期) 贵州大学理学院数学系信息与计算科学专业 一、 单项选择题 1.对于一个算法,当输入非法数据时,也...

《数据结构》期末考试试题及答案

《数据结构》期末考试试题及答案 (2003-2004 学年第 2 学期) 单项选择题 1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、 1.对于...

大学数据结构期末考试试题(有答案)

大学数据结构期末考试试题(有答案)_计算机软件及应用_IT/计算机_专业资料。大学...顺序 B.二分法 C.顺序,也能二分法 D.随机 《数据结构与算法》复习题 一、...

2015年数据结构期末考试题及答案

2012 年数据结构期末考试题及答案 一、选择题 1.在数据结构中,从逻辑上可以把数据结构分为 C 。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和...

数据结构期末考试题

数据结构期末考试题_从业资格考试_资格考试/认证_...分)不写解答过程,将正确的答案写在每小题的空格内...数据结构期末考试题及答... 16页 5下载券 2015...

数据结构期末试题与答案

仲恺农业工程学院试卷 (答案及评分标准)《数据结构与算法》 2011 至 2012 学年度第 2 学期期 末(A)卷 专业班级 题号一得分 评卷人 (考生注意:考试时间为 ...

2017《数据结构》期末考试试题及答案

2017《数据结构》期末考试试题及答案_理学_高等教育_教育专区 暂无评价|0人阅读|0次下载2017《数据结构》期末考试试题及答案_理学_高等教育_教育专区。2017《数据...

2011《数据结构》期末试卷_B卷(答案)

厦门大学《_数据结构_课程期末试卷信息科学与技术学院计算机科学系 2009 年级___专业 主考教师:陈怡疆 庄朝晖 试卷类型: (B 卷) 一、 (本题 10 分)请...

数据结构C语言版期末考试试题(附带复习资料)

EIemType MaxValue(LNOde*HL); “数据结构期末考试试题答案 一、单选题(每...共 16 分) 评分标准:每小题正确得 8 分,出现一处错误扣 4 分,两处及...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com