当前位置:首页 >> 数学 >> 数据结构B卷

数据结构B卷


2010-2011 学年第 2 学期考试试题(B)卷
课程名称 《数据结构》 任课教师签名 审题教师签名 ( 闭)卷 ( 二 120 三 四 适用专业 )分钟 五 六 总分 计算机各专业 出题教师签名 考试方式 考试时间 题号 得分 评卷人
一、填空题(本大题共 15 小题 20 空, 每空 1 分, 共 20 分) 1. _____是对客观事物的符号表示 , 在计算机科学中是指所有能输入到计算机中并 被计算机程序处理的符号的总称。 2. 一个数据元素可由若干个_____组成, 它是数据的不可分割的最小单位。 3. 数据结构是指相互之间存在一种或多种特定关系的 _____的集合, 而这种关系也 称为_____。 4. 数据的逻辑结构可分为集合、线性结构、_____结构和_____结构。 5. 数据元素之间的关系在计算机中有两种不同的表示方法: 顺序映象和_____, 由 此得到两种不同的存储结构: 顺序存储结构和_____。 6. 数据类型是一个值的集合和定义在这个值集上的一组_____的总称。 7. 算法的五个重要特性包括: 有穷性、_____、_____、输入和输出。 8. 下面的算法计算实数 x (x > 0)的非负整数 n (n ? 0)次幂, 其时间复杂度是_____。
double Power(double x, int n) { double y = 1; if (n > 0) { y = Power(x, n / 2); y *= y; if (n % 2 == 1) y *= x; } return y; }



每个元素占用 8 字节内存空间, 若数组起始地址为 0x1000, 则元素 a[3][1] 的地址 为 0x_____。 10. 将 n 阶的上三角矩阵采用压缩方式存储到一维数组中, 则元素 aij (1 ? i ? j ? n) 对 应一维数组元素的下标 k (0 ? k < n(n + 1) / 2)的计算公式为_____。 11. 已知二叉树后根遍历的序列为 “HFADBGEC” , 中根遍历的序列为 “HCAFBDEG” , 则先根遍历的序列为“_____” 。 12. 深度为 10 的完全二叉树至少有_____个结点, 至多有_____个结点。 13. 包含 5 个顶点的有向图, 至多有_____条弧。 14. 包含 10 个顶点的连通图, 其最小生成树拥有_____条边。 15. 某无向图及其邻接表如图 1 所示 , 按广度优先搜索遍历所得到的结点序列为 _____。 B 0 1 A E C 2 3 4 D
图 1 无向图及其邻接表 A B C D E 4 2 3 4 3 3 0 ^ 1 ^ 2 0 ^ 0 ^ 1 ^

9. 在 C 语言中定义下面的二维实型数组: double a[4][5];

二、选择填空题(本大题共 15 小题, 每小题 2 分, 共 30 分) 1. 数据结构被形式地定义为(D, R), D 是_____的有限集, R 是 D 上的关系有限集。 A) 算法 B) 数据元素 C) 数据操作 D) 逻辑结构 2. 算法分析的目的是_____。 A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 3. 下面是 4 种算法的时间复杂度, 其中效率最高的是_____。 A) O(log2n) B) O(2n) C) O(n2) D) O(nlog2n) 4. 在包含 n 个数据元素的顺序表中, 假设在每个位置 i (1 ? i ? n + 1) 处插入元素的 机率相等, 则在位置 i 处插入一个元素平均需要移动_____个元素。 A) 1 B) n / 2 C) (n + 1) / 2 D) n 5. 在无附加头结点的链栈中, 栈顶指针为 top, 指针 s 所指结点入栈执行的操作为 _____。 A) s->next = top; top = top->next; B) top = s; s->next = top; C) s->next = top->next; top->next = s; D) s->next = top; top = s;

6. 在设有头、尾指针的单链表中, _____操作与链表的长度有关。 A) 删除第一个元素 B) 删除最后一个元素 C) 在第一个元素前插入一个元素 D) 在最后一个元素后插入一个元素 7. n 个元素的线性表中, _____操作在顺序表上实现比在链表上实现更快。 A) 输入第 i (1 ? i ? n)个元素的值 B) 交换前两个元素的值 C) 输出线性表全部 n 个元素的值 D) 输出值为 x 的元素的序号 8. 4 个元素 a、b、c、d 依次进栈, 则出栈的序列不可能是_____。 A) abcd B) dcba C) cabd D) acdb 9. "abcd"有_____个子串。 A) 4 B) 5 C) 9 D) 10 10. 在线索二叉树中, 判断指针 p 所指结点没有左子树的条件是_____。 A) p->lch == NULL B) p->ltag == 1 C) p->lch == NULL&& p->ltag == 1 D) 以上都不对 11. 图 2 所示表达式二叉树的后缀表示式为_____。 A) a * b + c - d / e B) + * a b / - c d e C) a b * c d - e / + D) a b * + c d - e / + * a b c
图 2 表达式树

三、画图题(本大题共 3 小题, 每小题 5 分, 共 15 分) 1. 将图 3 所示的树转换成二叉树, 请画出对应的二叉树。 A B D E H
图 3 树的转换

A C B D E G
图 4 线索二叉树

C F

F

G

2. 将图 4 所示的二叉树按先根遍历的次序线索化, 请画出对应的先根线索二叉树。 3. 按图 5 所示无向图, 请画出 Kruskal 算法求最小生成树的过程。 2 2 1 3 1 4 3 6 3 5 1 7 6 2 6 1 2 5 3 8

/ d e

1

图 5 最小生成树

12. 下面关于树和二叉树的说法中, _____是正确的。 A) 度为 m 的树第 i 层至多有 mi - 1 个结点 B) 二叉树只能采用链式存储结构 C) 二叉树就是度为 2 的树 D) 度为 2 的树转换为二叉树后, 形态完全一样 13. n 个叶子结点的哈夫曼树, 结点总数为_____。 A) 不确定 B) 2n - 1 C) 2n D) 2n + 1 14. 无向图的邻接矩阵一定是_____。 A) 对角矩阵 B) 上三角矩阵 C) 下三角矩阵 D) 对称矩阵 15. 采用邻接矩阵存储的图的广度优先遍历算法类似于二叉树的_____算法。 A) 先根遍历 B) 中根遍历 C) 后根遍历 D) 按层遍历

四、分析题(本大题共 4 小题, 每小题 5 分, 共 20 分) 1. 若线性表 L = {2, 9, 3, 0, 5, 1, 7, 6, 8, 4}, 请写出用冒泡排序法按升序排序时, 线性 表变化过程的前 5 步。

2. 按图 6 所示有向图, 请写出 Dijkstra 算法求从顶点 A 出发到其余顶点的最短路径 的计算过程。 A 1 F 1 E 3 1 3 1 4 4 G 1 D 2 1 7 8
图 7 拓扑排序

设集合: x = {1, 2, 4, 6}, y = {2, 3, 4, 5, 7}, 则它们的交集为: z = {2, 4} 如下图所示:
1 2 4 ^

B 1 C

1

2

3

4

5

6

9

图 6 最短路径

3. 对图 7 所示的有向无环图进行拓扑排序, 请写出至少 5 种排序结果。 4. 已知散列表表长为 12, 地址计算公式为 H(k) = k mod 11 冲突处理方式为线性探测再散列, 将关键字 2、16、5、14、27、3、25、24 依次 插入到散列中, 请写出散列表的状态。 0 1 2 3 4 5 6 7 8 9 10 11 五、算法设计题(本大题共 2 小题, 第 1 小题 9 分, 第 2 小题 6 分, 共 15 分) 1. 集合的交集(9 分) 采用链式存储结构来表示集合。其中结点的存储结构如下图所示: data next 结点的结构类型定义如下:
struct NODE { double data; struct NODE *next; }; // 数据域 // 指针域

集合的存储结构如下图所示: head cardinal 集合的结构类型定义如下:
struct SET { struct NODE *head; int cardinal; }; // 头指针 // 集合基数(即集合元素的个数)

集合采用带头结点、按元素值递增有序的单链表来表示。

9 8 2 3 4 5 7 ^ y 5 7 6 2 4 ^ z 5 2 4 图 8 集合的交集 3 请编写算法, 完成集合的交集运算。函数原型如下: 2 void Intersection(struct SET *z, const struct SET *x, const struct SET *y); 1 函数的参数都是指向集合的指针, 没有函数值。x 和 y 指向两个相交的集合, z 指 1 向准备保存结果的集合。 3 要求: 用文字描述算法思想, 并估算时间复杂度, 然后用 C/C++语言编码。 5 2. 求二叉树的叶子结点数(6 分) 2 二叉树采用链式存储结构, 结点的存储结构如下图所示: 1 lch data rch 1 6 结点的结构类型定义如下 : struct NODE 2 { 4 double data; // 数据域 struct NODE 9 *lch, *rch; // 指针域 }; 5 请用递归方法编写算法求二叉树的叶子结点数。 1 int Nol(NODE *root); 3 函数的参数是根指针, 函数值是二叉树的叶子结点数。如: 3 printf("%d\n", Nol(root)); 6 要求: 用文字描述算法思想, 并估算时间复杂度, 然后用 C/C++语言编码。 2 1 6 1 3 2 1 2 8

数据结构课程考试参考答案和评分标准
六、填空题(本大题共 15 小题 20 空, 每空 1 分, 共 20 分) 9. 0x1080 1. 数据 (2n ? i ? 2)( i ? 1) 2. 数据项 ? j ?i 10. k ? 3. 数据元素、结构 2 4. 树形、图状(网状) 11. CHEBAFDG 5. 非顺序映象、链式存储结构 12. 512、1023 13. 20 6. 操作 14. 9 7. 确定性、可行性 15. AEDBC 8. O(log2n) 七、选择填空题(本大题共 15 小题, 每小题 2 分, 共 30 分) 1 2 3 4 5 6 7 8 9 10 11 12 B C A B D B A C D B C A 13 B 14 D 15 D 1 1

2

5 1

5

3

6

8

1 1

3

6

8

4 2 1 1 1 4 2 3 1

7 5

4 2 1

7 5

6

8

1 1

3 1 4 2 2 1 3 1 1 4 2

6

1

8

八、画图题(本大题共 3 小题, 每小题 5 分, 共 15 分) 1. 树的转换 2. 先根线索二叉树 A B D E H F 1 1 G C D B E G F A C NULL 1 1 2

7 5 1

7 5

3 1 4 2 2 3 1 4 3 1 2

6

1

8

1

6

1

8

7 5

7

3. 最小生成树(Kruskal)

6

1

8

7

九、分析题(本大题共 4 小题, 每小题 5 分, 共 20 分) 1. 冒泡排序 L = (2, 9, 3, 0, 5, 1, 7, 6, 8, 4) L = (2, 3, 0, 5, 1, 7, 6, 8, 4, 9) L = (2, 0, 3, 1, 5, 6, 7, 4, 8, 9) L = (0, 2, 1, 3, 5, 6, 4, 7, 8, 9) L = (0, 1, 2, 3, 5, 4, 6, 7, 8, 9) L = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) L = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) 2. 最短路径(Dijkstra)
步骤 顶点 0 1 2 3 4 5 6 A B C D G E F A 0 0 0 0 0 0 0 B 1 1 1 1 1 1 1 C ∞ 2 2 2 2 2 2 长度 D ∞ ∞ 3 3 3 3 3 E ∞ ∞ ∞ 6 5 5 5 F ∞ ∞ ∞ ∞ 7 6 6 G ∞ 5 5 4 4 4 4 A B A A A A A A A C B B B B B B 路径 D C C C C C E D G G G F G E E G B D D D D

// 首先将集合 z 清为空集 while ((s = z->head->next) != NULL) { z->head->next = s->next; delete s; } z->cardinal = 0; // 集合的交集 p = x->head->next; q = y->head->next; r = z->head; while (p != NULL && q != NULL) { if (p->data < q->data) { p = p->next; } else if (p->data > q->data) { q = q->next; } else // p->data == q->data { s = (struct NODE*)malloc(sizeof(struct NODE)); s->data = p->data; r->next = s; r = s; z->cardinal ++; p = p->next; q = q->next; } } // 处理尾结点 r->next = NULL; }

路径 A→B A→C A→D A→E A→F A→G

长度 1 2 3 5 6 4

最短路径 A→B A→B→C A→B→C→D A→B→C→D→G→E A→B→C→D→G→E→F A→B→C→D→G

3. 拓扑排序 1, 2, 3, 4, 5, 6, 7, 8, 9 1, 2, 3, 4, 5, 7, 6, 8, 9 1, 2, 3, 4, 5, 7, 8, 6, 9 4. 散列表 0 1 2 3 4 2 14 3

1, 2, 4, 3, 5, 6, 7, 8, 9 1, 2, 4, 3, 5, 7, 6, 8, 9 1, 2, 4, 3, 5, 7, 8, 6, 9 5 16 6 5 7 27 8 25 9 24

1, 4, 2, 3, 5, 6, 7, 8, 9 1, 4, 2, 3, 5, 7, 6, 8, 9 1, 4, 2, 3, 5, 7, 8, 6, 9 10 11 12 13 14

考查点主要有: 1) 是否注意到要先清除原链表中的所有结点 2) 合并过程按元素 值众小到大进行, 指针移动是否正确 3) 当值相同时才创建新结点加入的结果集中 4) 是否对尾结点进行处理。具体分值请阅卷教师酌情处理。 2. 求二叉树的叶子结点数(6 分) 参考代码如下, 时间复杂度为 O(n):
int Nol(NODE *root) { int n = 0; if (root != NULL) { if (root->lch == NULL && root->rch == NULL) { n = 1; } else {

十、算法设计题(本大题共 2 小题, 第 1 小题 9 分, 第 2 小题 6 分, 共 15 分) 1. 集合的交集(9 分) 参考代码如下, 时间复杂度为 O(m+n):
void Intersection(struct SET *z, const struct SET *x, const struct SET *y) { struct NODE *s, *p, *q, *r;

n = Nol(root->lch) + Nol(root->rch); } } return n; }

考查点主要有: 1) 是否考虑到空二叉树的情况 2) 是否正确调用递归函数 3) 判 断叶子结点的条件是否正确。具体分值请阅卷教师酌情处理。


更多相关文档:

数据结构II试卷B(孟凡荣)20).doc

数据结构II试卷B(孟凡荣)20) - 东北大学继续教育学院 数据结构 II 学习中心: 试卷(作业考核 线上) 院校学号: 姓名 B 卷 (共 总分 题号 得分 一...

《数据结构》( B 卷).doc

数据结构》( B 卷) - 《数据结构》模拟卷 一、单项选择题 1.以下与数据

数据结构B卷.doc

数据结构B卷 - 2010-2011 学年第 2 学期考试试题(B)卷 课程名称

数据结构B卷_图文.doc

数据结构B卷 - 中 ???装???订???线??? 原 工 学 院 2 学期

数据结构试卷B试卷及答案.doc

计算机学院 2010-2011 学年第一学期 《数据结构》试卷(B 卷) (考试

2010-2011(2)数据结构B卷及答案.doc

数据结构 》考试试卷(B 卷) (闭卷 时间 120 分钟) 考场登记表序号

数据结构B卷.doc

数据结构B卷 - 2011-2012 学年第二学期期末考试试题 (B)卷 课程名

2011《数据结构》期末试卷_B卷.doc

2011《数据结构》期末试卷_B卷 - 厦门大学《_数据结构_》课程期末试卷 信

《算法与数据结构》B卷.doc

《算法与数据结构B卷 - 2011-2012 学年第一学期期末考试试题 (B)卷 课程名称 《算法与数据结构》 任课教师签名 出题教师签名 2011 计算机合作联盟命题组 ...

数据结构B卷.doc

数据结构B卷 - 试卷 B 一、单项选择题 1.计算机算法指的是( C ) ,它

数据结构B卷_图文.doc

数据结构B卷 - 一、单项选择题 本题得分 评阅人 1、设一个栈的输入序列是 1

数据结构试卷B.doc

数据结构试卷B - 数据结构导论模拟试卷(二) 一、单项选择题(在每小题的 4

数据结构期末复习B卷.doc

试卷编号: (B)卷 数据结构 课程 课程类别:必 闭卷 考试日期: 总分 累分

2013-2014第二学期数据结构期末考试试卷B卷.doc

2013-2014第二学期数据结构期末考试试卷B卷_理学_高等教育_教育专区。合肥学院数据结构期末考试试卷 合肥学院 20 13 至 20 14 学年第 2 学期数据结构与算法设计...

数据结构试卷B.doc

数据结构试卷B - 承诺:我将严格遵守考场纪律,知道考试违纪、作弊的严重性,还知

东大数据结构II试卷B(孟凡荣)20).doc

东大数据结构II试卷B(孟凡荣)20) - 东北大学继续教育学院 数据结构 II 学习中心: 试卷(作业考核 线上) 院校学号: 姓名 B 卷 (共 总分 题号 得分...

海南大学2010 2011数据结构B期末试卷.pdf

海南大学 2010-2011 学年度第 1 学期试卷 科目: 《数据结构》试题

数据结构B卷及答案.doc

数据结构B卷及答案 - 题号 得分 一 二 三 四 五 总分 复查人 注意:在填

数据结构试卷B及答案__黄河科技学院.doc

数据结构试卷B及答案__黄河科技学院_工学_高等教育_教育专区。数据结构 试卷B 答案 黄河科技学院 《数据结构》课程试题(B 卷)一、单选题(每小题1分,共20分)...

2009下数据结构试卷B.doc

武汉大学测绘学院 2009-2010 学年度第一学期期末考试 《数据结构与数据库》课程试卷( B 卷) 出题者虞晖 刘进 班级 学号 姓名 审核人 成绩 一、选择题:(以下...

更多相关标签:
网站地图

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