《算法与数据结构》B卷

1、2011-2012 学年第一学期期末考试试题 （B）卷 课程名称 算法与数据结构 任课教师签名 出题教师签名 2011 计算机合作联盟命题组 审题教师签名 考试方式 （ 闭 ）卷 适用专业 10 计科 1-2 考试时间 （ 110 ）分钟 题号一二三四五六七总分 得分 评卷人 （注：判断题和选择题的答案写在答题纸上）（注：判断题和选择题的答案写在答题纸上） 一、单项选择题（每小题 2 分，共 30 分） 1.数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之 为( ) A. 存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构 2算法分析的目的是( ) A辨别数据结构的

2、合理性 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，且进栈和出栈可以穿插进行，则可能出现的 出栈序列为( ) A3，2，6，1，4，5B3，4，2，1，6，5 C1，2，5，3，4，6D5，6，4，2，3，1 5. 已知循环队列的存储空间为数组da

3、ta21，且当前队列的头指针和尾指针的值 分别为8和3，则该队列的当前长度为( ) A. 5 B.6 C.16 D.17 6二维数组 A89按行优先顺序存储，若数组元素 A23的存储地址为 1087，A47的存储地址为 1153，则数组元素 A67的存储地址为( ) A1207B1209 C1211D1213 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在任意一棵二叉树的前

4、序序列和后序序列中，各叶子之间的相对次序关系( ) A不一定相同B都相同 C都不相同D互为逆序 10对下面有向图给出了四种可能的拓扑序列，其中错误的是( ) A1，5，2，6，3，4B1，5，6，2，3，4 C5，1，6，3，4，2D5，1，2，6，4，3 11图的邻接矩阵表示法适用于表示( ) A无向图B有向图 C稠密图D稀疏图 12.连通网的最小生成树是其所有生成树中( ) A. 顶点集最小的生成树 B.边集最小的生成树 C. 顶点权值之和最小的生成树 D. 边的权值之和最小的生成树 13下列排序算法中不稳定的是( ) A直接插入排序 B归并排序 C冒泡排序 D快速排序 14若有序表的关键

5、字序列为（b,c,d,e,f,g,q,r,s,t） ，则在二分查找关键字 b 的 过程中，先后进行比较的关键字依次为( ) Af,c,bBf,d,b Cg,c,bDg,d,b 15.下面的序列中，( )是堆。 A. 9，8，7，6，5，4，3，7B. 1，5，10，6，7，8，9，2 C. 9，8，7，6，4，8，2，1D. 1，2，8，4，3，9，10，5 二、填空题（本大题共 10 小题，每小题 2 分，若有两个空格，每个空格 1 分，共 20 分）请在每个空格中填上正确答案。错填、不填均无分。 1.数据的链式存储结构的特点是借助_表示数据元素之间的逻辑关系。 2.如果需要对线性表频繁进行

6、_或_操作，则不宜采用顺 序存储结构。 3.队列的队尾位置通常是随着_操作而变化的。 4.广义表L=（a，（b，( )）的深度为_，长度为_。 5.任意一棵完全二叉树中，度为1的结点数最多为_。 6.已知一棵哈夫曼树含有60个叶子结点，则该树中共有_个非叶子结点。 7.求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中_的数目 正相关。 8.有 n 个顶点的无向连通图中最少有_条边，最多有_条边。 9.对长度为 20 的有序表进行二分查找的判定树的高度为_。 10. 若对关键字序列（50，41，65，94，78，17，28）进行快速升序排序，以 50 为中轴元素，则一趟快速排序后的

7、序列状态是_。 三、解答题（本大题共 4 小题，每小题 7 分，共 28 分） 1、假设用于通讯的电文仅由 6 个字母 A,B,C,D,E,F 组成，其权值分别为 8,2,4,5,6,1，试为这 6 个字母设计哈夫曼编码。 2已知带权图的邻接表如下所示，其中边表结点的结构为： 请回答下述问题： （1）画出由此邻接表从顶点 C 出发进行深度优先遍历得到的深度优先生成树； （4 分）分） （2）写出上述带权图的邻接矩阵。 （3 分）分） 3已知一棵二叉排序树如图所示。 请回答下列问题： (1)画出插入元素 23 后的树结构；（3 分）分） (2)请画出在插入 23 后删除元素 45 的树结构。 （

8、4 分）分） 4、在地址空间为 016 的散列区中，对以下关键字序列构造哈希表： （Job,Fly,Man,Apple,Max,Key,Kid,Big,Lady,No,Set,Oct,Name） 用二次探测再散列开放地址法处理冲突；并求在等概率情况下查找成功时的平均查 找长度。设哈希函数为（例如：）,其中 i 为关键字中 2/)(ixH 35 . 2 第一个字母在字母表中的序号(字母 A 的序号为)。 四、算法阅读题（本大题共 2 小题，每小题 6 分，共 12 分） 1.阅读下列函数 algo,并回答问题： (1)假设队列 q 中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行

9、函数调用 algo( InitStack( while (!QueueEmpty(Q) Push( while (! StackEmpty( 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 分别为指向存储两个有序整数集合的链表的头指针 L

10、inkList pa,pb; pa=ha-next; pb=hb-next; while(pa pb=pb-next; if(pa=NULL else return 0; 五、算法设计题（本题 10 分） 假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node int data； struct node *next； LinkNode，*LinkList； 编写算法，输入n个整数构造一个元素值互不相同的递增有序链表(即相同的整数只 取一个)。算法的函数原型给定为:LinkList f5(int n)； 2011-2012 学年第一学期期末考试试题 （B

11、）卷 算法与数据结构算法与数据结构参考答案参考答案及评分标准 一、单项选择题（本大题共一、单项选择题（本大题共1515小题，每小题小题，每小题2 2分，共分，共3030分）在每小题列出分）在每小题列出 的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的 括号内。错选、多选或未选均无分。括号内。错选、多选或未选均无分。 12345678910 CBABCAACBC 1112131415 CDDAD 二、填空题（本大题共二、填空题（本大题共1010小题，每小题小题，每小题2 2分，若有两个空格，每个空格分，若有两个空格，每个

12、空格1 1 分，共分，共2020分）请在每个空格中填上正确答案。错填、不填均无分。分）请在每个空格中填上正确答案。错填、不填均无分。 1 指针2 插入 删除 3. 入队列43 2 5. 16. 59 7. 边 8. n-1 n(n-1)/2 9. 510. 28 41 17 50 78 94 65 三、解答题（本大题共三、解答题（本大题共4 4小题，每小题小题，每小题7 7分，共分，共2828分）分） 1.1.（哈夫曼树（哈夫曼树 5 5 分，对分，对 1 1 个结点得个结点得 1 1 分；编码分；编码 2 2 分，每对三个结点的编分，每对三个结点的编 码得码得 1 1 分）分） 约定左分支编

13、码为 0，右分支编码为 1 则： A 的编码为：01 B 的编码为：0001 C 的编码为：001 D 的编码为：10 E 的编码为：11 F的编码为：0000 2.（1）深度优先生成树（4 4分）分） （2）邻接矩阵（3 3分）分） 149 1415 820 87 9152011 711 3.(1)(3(3分分) ) （2） （4 4分）分） 或 4.（求（求 ASLASL 2 2 分，公式分，公式 1 1 分，结果分，结果 1 1 分；哈希表构造分；哈希表构造 5 5 分，每对分，每对 3 3 个关个关 键字得键字得 1 1 分）分） 01234567 8 12 56 4 B F A C D E D C F B E A 736 23 57 4966 18 45 736 23 57 66 18 49 237 57 4966 18 36 AppleBigFlyJobKeyMan 121111 8910111213141516 MaxSetKidNoOctLadyName 2344466 ASL=85 . 2 13 37 13 62433225 四、算法阅读题（本大题共四、算法阅读题（本大题共2 2小题，每小题小题，每小题6 6分，共分，共1212分）分） 1