当前位置:首页 >> 其它课程 >>

数据结构3


择的排序方法是( A.快速排序

) C.归并排序 D.直接插入排序

B.堆排序

徐 州 师 范 大 学 试 卷(三)(2007-2008 学年度第一学期)
(考试日期 : 年 月 日) 得分



院系 计算机学院 专业 计算机科学与技术 课程名称 : 算法与数据

结构 成绩
三 12 四 36 五 20 合分人

二、填空题(每空 1 分,共 18 分)
6.根据数据元素之间关系的不同特性,数据结构可分为 、 。 、 、


题 分 得

号 值 分

一 14

二 18

7.循环队列 Q 中,front 和 rear 分别指示队列头元素及队尾元素的位置,则判断对空的条件 是 ,对满的条件是 。 8.假设有二维数组 A6*8,每个元素用相邻的 6 个字节存储,存储器按字节编址。已知 A 的起始 存储位置为 1000,那么按行存储时,元素 a14 的存储地址为 ,a47 的地址为 。 9.若广义表 L=(a ,( b ,c ,d ) ),则 GetHead(L)= ,GetTail(L)= 。 ,

注意:装订线外,勿写答案。

得分

一、单项选择题(每空 2 分,共 14 分) 在下列每小题的备选答案中选出一个正确的答案,并将其字母标号填 入题目的括号内。
1.表长为 n 的顺序存储的线性表,当在任何位置上插入和删除一个元素的概率相等 时,插入一个元素所需移动元素的平均个数为( ) ,删除一个元素需要移动元素 的平均个数为( ) 。 A.(n-1)/2 B.(n+1)/2 C.n/2 D.n E.(n-2)/2 )

10. 具有 n 个结点的完全二叉数的深度为 至多为 。 11.图的遍历方式有 和

。 深度为 k 的二叉数的总结点数至少为

两种。 块

12. 在分块查找中, 若索引表和各块内均用顺序查找, 则有 900 个元素的线性表分成 最好;若分成 25 块,其平均查找长度为 。

学号

13.给出一组关键字 T=(30,8,16,12,2,28) ,写出用希尔排序从小到大排序时第一趟(增 量为 3)结束时的序列 。 得分

2.设栈的输入序列是 1、2、3、4,则不可能出现的出栈序列是( A.3124 B.2134 C.4321 D.1243 )

三、判断题(每题 2 分,共 12 分)
14.顺序存储方式只能用于存储线性结构。 15.数据的基本单位是数据项。 ( ( ) )

3.串是一种特殊的线性表,其特殊性体现在( A.可以顺序存储 C.可以链接存储

B.数据元素是一个字符 D.数据元素可以是多个字符 )条弧。若 G 是强连通图,其弧

班级

4.设有向图 G 的顶点个数为 n,则该图最多有( 的个数至少为( ) A.n(n+1)/2 B.n(n-1) C.n(n-1)/2

16.在单链表中,任何两个元素的存储位置之间都有固定的联系,因为可以从头结点进行查找 任何一个元素。 ( ) 17.完全二叉树的某结点若无左孩子,则它必是叶子结点。 ( ) 18.数组可看成线性结构的一种推广,因此与线性表一样,可以对它进行插入、删除等操作。 ( ) 19.在 n 个结点的无向图中,如边数大于 n-1,则该图必存在回路。 ( )

D.n

5.若需在 O(nlogn)的时间内完成对一组纪录的排序,且要求排序是稳定的,则可选

1

得分

四、应用题(共 36 分)
20.假设一棵二叉树的中序序列为 DCBGEAHFIJK 和后序序列为 DCEGBFHKJIA.请画出该二叉树。 (4 分)

23.如图所示的 AOE 网络中,计算各顶点的 ve(i)和 vl(i)函数值及各活动的 e(i)和 l(i)函数 值,并求出关键活动和关键路径。 (10 分) 其中:a1=6,a2=4,a3=4,a4=6,a5=8,a6=6,a7=4,a8=2

21.下图为一以邻接矩阵存储的图,试分别画出自顶点 V1 出发进行遍历所得的深度优先生成树 和广度优先生成树。 分) (6

24.使用哈希函数 H(key)=x MOD 11,把一个整数值转换成哈希表(表长为 11) ,先要把数据 1、 13、12、34、38、33、27、22 插入到哈希表中。 (10) a.使用线性探测再散列发来构造哈希表。 (5’) 22.已知长度为 10 的表(48,65,32,81,12,25,50,04,98,56) ,若按表中元素的顺序 依次插入到一棵初始为空的二叉排序树中: 分) (6 a.请画出此二叉排序树; b.若在表中再插入 76 和 18,请画出新的二叉排序树。 b.计算(a)中查找成功时的平均查找长度(设查找概率相等) 。(5’)

2

得分

(2)请补充图的广度优先非递归遍历图 G 的算法。 void BFSTraverse(Graph G,Status (*visit)(int v)) {

五、算法设计题(每空 2 分,共 20 分)
25.函数 reverse()实现将已知不带头结点的单链表的链接顺序颠倒的功能, 即第一表元变为最 后表元,第二表元变为倒数第二表元,……,最后表元变为第一表元。函数中 h 为链表的头指 针,q2 为第一个尚未颠倒的链表表元,q1 为已颠倒链表的第一个链表表元。 Typedef int struct data; *next; node {

for (v=0;v<G.vexnum;++v) InitQueue(Q); for (v=0;v<G.vexnum;++v) if (!visited[v]) {

;

visited[v]=TRUE; Visit(v); ; while (!Q.ueueEmpty(Q)) { ; for (w=FirstAdjVex(G,u));w>=0;w= if (!visited[w]) { )

struct node

}node; //链表的形式说明 void reverse(node h) { node *q1, *q2; ; q1=NULL; while (q2!=NULL) { ; ; h=q2; ; } =q1; } } } } }

visited[w]=TRUE; Visit(w); ;

3

徐 州 师 范 大 学 试 卷(三)(2007-2008 学年度第一学期)
参考答案及评分标准
院系 计算机学院 专业 计算机科学与技术 课程名称 :算法与数据结构
一、选择题(每空 2 分,共 14 分) 9.c,a 10.a 11.b 12.b,d 13.c 二、填空题(每空 1 分,共 18 分) 1. 集合、线性、树型、图状(网状) 2. Q.rear=Q.front,(Q.rear+1)%maxqsize=Q.front 3. 1072,1234 4. a,(b,c,d) ( ) k 5. |_log2n_|+1,k,2 -1 6. 深度优先,广度优先 7. 30,31.5 8. 12,2,16,30,8,28 三、 判断题(每题 2 分,共 12 分) 14.× 15. × 16. × 17.√ 18.× 19.√ 四、 应用题(共 40 分) 20.二叉树为 (4’)

a(3’) 23. 顶点 V1 V2 V3 V4 V5 V6 ve 0 6 4 12 12 16 vl 0 8 4 12 14 16 活动 a1 a2 a3 a4 a5 a6 a7 a8 e 0 0 6 6 4 4 12 12

b(3’) l 2 0 8 8 4 10 12 14

所以关键活动为 a2,a5,a7。 (2’) 关键路径为(v1,v3,v4,v6) 。(2’) 其中求出顶点的 ve、vl 得 3 分,求出活 动的 e、l 得 3 分

24. a)(5’) 33 1

13

12

34

38

27

22 10

21.深度(3’)和广度(3’)生成树为:

0 1 2 3 4 5 6 7 8 9 b)的平均查找长度为:1/8(1*4+2*1+3*1+4*1+8*1)=21/8(5’)或 7/3 五、算法填空(每空 2 分,共 20 分) 25. q2=h->next; h->next=q1; q1=h; q2=q2->next; h->next 26. visited[v]=FALSE; enquue(Q,v); dequeue(Q,u); nextadjvex(G,u,w); enqueue(Q,w);

22.

4


相关文章:
数据结构(第3版)习题答案
【答】:数据结构涉及三个方面的内容,即数据的逻辑结构、数据的存储结构和数据的运算集 合。 1.3 两个数据结构的逻辑结构和存储结构都相同,但是它们的运算集合中...
数据结构3
数据结构 3 总分:100 考试时间:100 分钟 一、单项选择题 1、数组的存储结构采用()存储方式(正确答案:A) A、顺序 B、链式 C、链表 D、线性表 2、设二维...
数据结构3
数据结构3_计算机软件及应用_IT/计算机_专业资料。实验三 栈和队列 一、实验目的 掌握线性表的两个典型应用——栈和队列的基本操作 二、实验内容 1.尝试接触 ...
数据结构 3
数据结构 3_理学_高等教育_教育专区。数据结构 洛阳理工学院实验报告系部 计算机系 班级 Z130553 数据结构 二叉树遍历 学号 Z13055317 姓名 李胜杰 2014.4.14 ...
数据结构3
数据结构3_天文/地理_自然科学_专业资料。数据结构实验报告 HUNAN UNIVERSITY 课程实习报告 题 目: 四则运算表达式求值 王操 201308020314 学生姓名 学生学号 专业班...
数据结构报告3
45 第 2 页共 45 页 数据结构实验报告_信安 1302_0906130212_彭澍 数据结构实验报告 3 1.实验内容图的操作算法 实现图的常用操作算法:包括建立图的存储结构、...
数据结构3
数据结构3_理学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档数据结构3_理学_高等教育_教育专区。 文档贡献者 水随汉落梅花开 贡献于2015-07-11 ...
数据结构课后习题3
数据结构课后习题3_理学_高等教育_教育专区。3.1 有 5 个元素,其进栈次序为:A、B、C、D、E,在各种可能的出栈次序中,以元素 C、 D 最先出栈(即 C 第一...
数据结构3
数据结构单元3 39页 2财富值 数据结构3_队列 13页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
数据结构报告3
数据结构报告3_工学_高等教育_教育专区。数据结构实验报告 计算机科学与工程系 天津理工大学计算机与通信工程学院 实验报告 2014 至 2015 学年 第二 学期 课程名称...
更多相关标签:
数据结构实验3 | discuz3.2数据库结构 | 数据结构实验报告3 | 严蔚敏数据结构视频3 | python3 数据结构 | 数据结构教程 第3版 | 数据结构c语言 视频3 | 数据结构 |