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

《算法与数据结构》B卷


2011-2012 学年第一学期期末考试试题 (B)卷
课程名称 《算法与数据结构》 任课教师签名 出题教师签名 2011 计算机合作联盟命题组 审题教师签名 考试方式 考试时间 ( 闭 )卷 ( 110 )分钟 适用专业 10 计科 1-2

题号 得分 评卷人






>








总分

(注:判断题和选择题的答案写在答题纸上) 一、单项选择题(每小题 2 分,共 30 分) 1. 数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之
为( ) A. 存储结构 B. 逻辑结构 C. 顺序存储结构 D. 链式存储结构 2.算法分析的目的是( ) A.辨别数据结构的合理性 B.评价算法的效率 C.研究算法中输入与输出的关系 D.鉴别算法的可读性 3. 若要在单链表中的结点*p之后插入一个结点*s,则应执行的语句是( ) A. s->next=p->next;p->next=s; B. p->next=s;s->next=p->next; C. p->next=s->next;s->next=p; D. s->next=p;p->next=s->next; 4.若进栈序列为 1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的 出栈序列为( ) A.3,2,6,1,4,5 B.3,4,2,1,6,5 C.1,2,5,3,4,6 D.5,6,4,2,3,1 5. 已知循环队列的存储空间为数组data[21],且当前队列的头指针和尾指针的值 分别为8和3,则该队列的当前长度为( )
1

A. 5 B. 6 C. 16 D. 17 6.二维数组 A[8][9]按行优先顺序存储,若数组元素 A[2][3]的存储地址为 1087, A[4][7]的存储地址为 1153,则数组元素 A[6][7]的存储地址为( ) A.1207 B.1209 C.1211 D.1213 7. 广义表A=((x,(a,b)),(x,(a,b),y)),则运算head(head(tail(A)))为( ) A. x B. (a,b) C. (x,(a,b)) D. y 8. 具有2000个结点的二叉树,其高度至少为( ) A. 9 B. 10 C. 11 D. 12 9 .在任意一棵二叉树的前序序列和后序序列中,各叶子之间的相对次序关系 ( ) A.不一定相同 B.都相同 C.都不相同 D.互为逆序 10.对下面有向图给出了四种可能的拓扑序列,其中错误 的是( ) ..

A.1,5,2,6,3,4 B.1,5,6,2,3,4 C.5,1,6,3,4,2 D.5,1,2,6,4,3 11.图的邻接矩阵表示法适用于表示( ) A.无向图 B.有向图 C.稠密图 D.稀疏图 12.连通网的最小生成树是其所有生成树中( ) A. 顶点集最小的生成树 B. 边集最小的生成树 C. 顶点权值之和最小的生成树 D. 边的权值之和最小的生成树 13.下列排序算法中不稳定 的是( ) ... A.直接插入排序 B.归并排序 C.冒泡排序 D.快速排序 14.若有序表的关键字序列为(b,c,d,e,f,g,q,r,s,t) ,则在二分查找关键字 b 的 过程中,先后进行比较的关键字依次为( )

A.f,c,b B.f,d,b C.g,c,b D.g,d,b 15. 下面的序列中,( )是堆。 A. 9,8,7,6,5,4,3,7 B. 1,5,10,6,7,8,9,2 C. 9,8,7,6,4,8,2,1 D. 1,2,8,4,3,9,10,5

二、填空题(本大题共 10 小题,每小题 2 分,若有两个空格,每个空格 1 分,共 20 分)请在每个空格中填上正确答案。错填、不填均无分。
1. 数据的链式存储结构的特点是借助________表示数据元素之间的逻辑关系。 2. 如果需要对线性表频繁进行____________或____________操作,则不宜采用顺 序存储结构。 3. 队列的队尾位置通常是随着________操作而变化的。 4. 广义表L=(a,(b,( )))的深度为________,长度为________。 5. 任意一棵完全二叉树中,度为1的结点数最多为________。 6. 已知一棵哈夫曼树含有60个叶子结点,则该树中共有________个非叶子结点。 7. 求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中________的数目 正相关。 8. 有 n 个顶点的无向连通图 中最少有_________条边,最多有_________条边。 ..... 9. 对长度为 20 的有序表进行二分查找的判定树的高度为__________。 10. 若对关键字序列(50,41,65,94,78,17,28)进行快速升序排序,以 50 为中轴元素,则一趟快速排序后的序列状态是__________。

请回答下述问题: (1)画出由此邻接表从顶点 C 出发进行深度优先遍历得到的深度优先生成树; (4 分) (2)写出上述带权图的邻接矩阵。 (3 分) 3.已知一棵二叉排序树如图所示。 请回答下列问题: (1)画出插入元素 23 后的树结构; (3 分) (2)请画出在插入 23 后删除元素 45 的树结构。 (4 分)

三、解答题(本大题共 4 小题,每小题 7 分,共 28 分)
1 、 假 设 用 于 通 讯 的 电 文 仅 由 6 个 字 母 A,B,C,D,E,F 组 成 , 其 权 值 分 别 为 8,2,4,5,6,1,试为这 6 个字母设计哈夫曼编码。 2.已知带权图的邻接表如下所示,其中边表结点的结构为:

4、在地址空间为 0~16 的散列区中,对以下关键字序列构造哈希表: (Job,Fly,Man,Apple,Max,Key,Kid,Big,Lady,No,Set,Oct,Name) 用二次探测再散列开放地址法处理冲突;并求在等概率情况下查找成功时的平均查 找长度。设哈希函数为

H ( x) ? ?i / 2? (例如: ?2.5? ? 3 ),其中 i 为关键字中

第一个字母在字母表中的序号(字母 A 的序号为)。
2

四、算法阅读题(本大题共 2 小题,每小题 6 分,共 12 分)
1.阅读下列函数 algo,并回答问题: (1)假设队列 q 中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用 algo(&q)后的队列 q;(4 分) (2)简述算法 algo 的功能。(2 分) void algo(Queue *Q) { Stack S; InitStack(&S); while (!QueueEmpty(Q)) Push(&S, DeQueue(Q)); while (! StackEmpty(&S)) EnQueue(Q,Pop(&S)); } 2.已知用有序链表存储整数集合的元素。阅读算法 f4_2,并回答下列问题: (1)写出执行 f4_2(a,b)的返回值,其中 a 和 b 分别为指向存储集合{2,4,5, 7,9,12}和{2,4,5,7,9}的链表的头指针; (4 分) (2)简述算法 f4_2 的功能; (2 分) int f4_2(LinkList ha,LinkList hb) { //LinkList 是带有头结点的单链表 //ha 和 hb 分别为指向存储两个有序整数集合的链表的头指针 LinkList pa,pb; pa=ha->next; pb=hb->next; while(pa && pb && pa->data==pb->data) { pa=pa->next; pb=pb->next; } if(pa==NULL && pb==NULL) return 1; else return 0;
3

}

五、算法设计题(本题 10 分)
假设以带头结点的单链表表示有序表,单链表的类型定义如下: typedef struct node { int data; struct node *next; } LinkNode,*LinkList; 编写算法,输入n个整数构造一个元素值互不相同的递增有序链表(即相同的整数只 取一个)。算法的函数原型给定为:LinkList f5(int n);

2011-2012 学年第一学期期末考试试题 (B)卷 《算法与数据结构》参考答案及评分标准
一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出 的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的 括号内。错选、多选或未选均无分。 1 C 11 C 2 3 4 5 B A B C 12 13 14 15 D D A D 6 A 7 A 8 C 9 B 10 C

A 的编码为:01 B 的编码为:0001 C 的编码为:001 D 的编码为:10 E 的编码为:11 F的编码为:0000

2.(1)深度优先生成树(4分) 二、填空题(本大题共10小题,每小题2分,若有两个空格,每个空格1 分,共20分)请在每个空格中填上正确答案。错填、不填均无分。 1. 指针 3. 入队列 5. 1 7. 边 9. 5 2. 插入 4.3 6. 59 8. n-1 n(n-1)/2 10. 28 41 17 50 78 94 65
E D B A F C

(2)邻接矩阵(3分)
?? ? ?11 ? ? ?7 ? ?? ? ?? ? ? ? ? ? ? ? ? ? ? 20 15 9 ? ? ? ? ? 8 ? ? ? ? 20 8 ? ? ? ? ? 15 ? ? ? 14? ? ? 9 ? ? 14 ? ? ? 11 7 ? ?

删除

2

三、解答题(本大题共4小题,每小题7分,共28分) 1.(哈夫曼树 5 分,对 1 个结点得 1 分;编码 2 分,每对三个结点的编 码得 1 分) 约定左分支编码为 0,右分支编码为 1 则:
4

3.(1)(3分)
18 7 6 E 36

45

57 49 66

D A 8 5

23

(2)将队列q中的元素逆置(2分)

49

2.(1)0(4分) (2)如果两个链表相等(对应元素相同,且长度相等)返回结果为1,

(2) (4分)
18 7 23

36 18 57 7 49 66 36

57 否则返回结果为 0(2分)


23

66 五、算法设计题(本题 10分)

LinkList f5(int n) {LinkList L,p,q,s;(初始化2分) int e,i; L=(LinkList)malloc(sizeof(LinkNode)); L->next=NULL; for(i=1;i<=n;i++) {(循环架构1分) scanf(″%d″,&e);(输入及查找准备2分) p=L;

4.(求 ASL 2 分,公式 1 分,结果 1 分;哈希表构造 5 分,每对 3 个关 键字得 1 分) 0 1 Apple 1 2 Big 2 3 Fly 1 4 5 Job 1 6 Key 1 7 Man 1

8 Max 2

9 Set 3

10 Kid 4

11 No 4

12 Oct 4

13

14

15 Lady 6

16 Name 6

q=p->next; while(q&&q->data<e) {(查找插入位置2分) p=q; q=q->next; } if(!q||q->data>e){(插入2分) s=(LinkList)malloc(sizeof(LinkNode)); s->data=e; s->next=q;
5

5 ? 2 ? 2 ? 3 ? 3 ? 4 ? 2 ? 6 37 ? ? 2.85 ASL= 13 13

四、算法阅读题(本大题共2小题,每小题6分,共12分) 1.(1)执行函数调用algo(&q)后的队列q中的元素为(8,7,5,4,2) (4分)

p->next=s; } } return L;(返回1分) }

6


相关文章:
《算法与数据结构》B卷
算法的函数原型给定为:LinkList f5(int n); 2011-2012 学年第一学期期末考试试题 (B)卷 《算法与数据结构》参考答案及评分标准一、单项选择题(本大题共15小...
《算法与数据结构》A卷
算法的函数原型 给定为: void f5(LinkList A,LinkList B); 2011-2012 学年第一学期期末考试试题 (A)卷 《算法与数据结构》参考答案及评分标准一、单项选择题...
《算法与数据结构》练习一(答案)
《算法与数据结构》练习一(答案)_教育学_高等教育_教育专区。习题一 一、选择题 1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的(B)...
算法与数据结构试题及答案
2. 设有两个集合 A 集合 B,要求设计生成集合 C=A∩B算法,其中集合 A、B C 用链 式存储结构表示。 5 数据结构试卷(三)一、选择题(每题 1 ...
算法与数据结构C卷答案
算法与数据结构C卷答案_理学_高等教育_教育专区。赣南师范学院………密………...A.该排序算法不允许有相同的关键字记录 B.该排序算法允许有相同的关键字记录 ...
算法与数据结构B卷
课程名称:算法与数据结构 三四五 考试形式:闭卷 所需时间:120 分钟 六七八总分 一 二 选课班级: A.该排序算法不允许有相同的关键字记录 B.该排序算法允许有...
算法与数据结构期末考试试卷[
算法与数据结构期末考试试卷[_教育学_高等教育_教育...6. 广义表 A= (a,(a,b),((a,b),c)), ...《算法与数据结构 》课程... 4页 免费 算法与...
《算法与数据结构》-期中试卷
B. 2m-1 C. 2m+1 。 D. m+1 2014-2015 下 计算机学院《算法与数据结构》期中试卷 第 9 页,共 17 页 15. 若采用孩子兄弟链表作为树的存储结构,则树...
算法与数据结构试卷
算法与数据结构试卷_电脑基础知识_IT/计算机_专业资料。赣南师范学院………密…...A、v1 v4 v6 v2 v5 v3 B、v1 v2 v3 v4 v5 v6 C、v1 v4 v2 v3 ...
《算法与数据结构 》课程模拟考试试卷
《算法与数据结构 》课程模拟考试试卷_财会/金融考试_资格考试/认证_教育专区。...( i=1;k=0; while(i<n) {k=k+10;i++;} A.0(1) B.O(n) C....
更多相关标签:
数据结构与算法 | 数据结构与算法分析 | java数据结构和算法 | 数据结构与算法 pdf | c 数据结构与算法 | 数据结构和算法 | 数据结构与算法 视频 | 数据结构与算法 java |