您好,欢迎访问三七文档
当前位置:首页 > IT计算机/网络 > 数据挖掘与识别 > 《算法与数据结构》B卷
12011-2012学年第一学期期末考试试题(B)卷课程名称《算法与数据结构》任课教师签名出题教师签名2011计算机合作联盟命题组审题教师签名考试方式(闭)卷适用专业10计科1-2考试时间(110)分钟题号一二三四五六七总分得分评卷人(注:判断题和选择题的答案写在答题纸上)一、单项选择题(每小题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,5B.3,4,2,1,6,5C.1,2,5,3,4,6D.5,6,4,2,3,15.已知循环队列的存储空间为数组data[21],且当前队列的头指针和尾指针的值分别为8和3,则该队列的当前长度为()A.5B.6C.16D.176.二维数组A[8][9]按行优先顺序存储,若数组元素A[2][3]的存储地址为1087,A[4][7]的存储地址为1153,则数组元素A[6][7]的存储地址为()A.1207B.1209C.1211D.12137.广义表A=((x,(a,b)),(x,(a,b),y)),则运算head(head(tail(A)))为()A.xB.(a,b)C.(x,(a,b))D.y8.具有2000个结点的二叉树,其高度至少为()A.9B.10C.11D.129.在任意一棵二叉树的前序序列和后序序列中,各叶子之间的相对次序关系()A.不一定相同B.都相同C.都不相同D.互为逆序10.对下面有向图给出了四种可能的拓扑序列,其中错误..的是()A.1,5,2,6,3,4B.1,5,6,2,3,4C.5,1,6,3,4,2D.5,1,2,6,4,311.图的邻接矩阵表示法适用于表示()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的过程中,先后进行比较的关键字依次为()2A.f,c,bB.f,d,bC.g,c,bD.g,d,b15.下面的序列中,()是堆。A.9,8,7,6,5,4,3,7B.1,5,10,6,7,8,9,2C.9,8,7,6,4,8,2,1D.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为中轴元素,则一趟快速排序后的序列状态是__________。三、解答题(本大题共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的树结构。(4分)4、在地址空间为0~16的散列区中,对以下关键字序列构造哈希表:(Job,Fly,Man,Apple,Max,Key,Kid,Big,Lady,No,Set,Oct,Name)用二次探测再散列开放地址法处理冲突;并求在等概率情况下查找成功时的平均查找长度。设哈希函数为2/)(ixH(例如:35.2),其中i为关键字中第一个字母在字母表中的序号(字母A的序号为)。3四、算法阅读题(本大题共2小题,每小题6分,共12分)1.阅读下列函数algo,并回答问题:(1)假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用algo(&q)后的队列q;(4分)(2)简述算法algo的功能。(2分)voidalgo(Queue*Q){StackS;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分)intf4_2(LinkListha,LinkListhb){//LinkList是带有头结点的单链表//ha和hb分别为指向存储两个有序整数集合的链表的头指针LinkListpa,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)return1;elsereturn0;}五、算法设计题(本题10分)假设以带头结点的单链表表示有序表,单链表的类型定义如下:typedefstructnode{intdata;structnode*next;}LinkNode,*LinkList;编写算法,输入n个整数构造一个元素值互不相同的递增有序链表(即相同的整数只取一个)。算法的函数原型给定为:LinkListf5(intn);42011-2012学年第一学期期末考试试题(B)卷《算法与数据结构》参考答案及评分标准一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。12345678910CBABCAACBC1112131415CDDAD二、填空题(本大题共10小题,每小题2分,若有两个空格,每个空格1分,共20分)请在每个空格中填上正确答案。错填、不填均无分。1.指针2.插入删除3.入队列4.325.16.597.边8.n-1n(n-1)/29.510.28411750789465三、解答题(本大题共4小题,每小题7分,共28分)1.(哈夫曼树5分,对1个结点得1分;编码2分,每对三个结点的编码得1分)约定左分支编码为0,右分支编码为1则:A的编码为:01B的编码为:0001C的编码为:001D的编码为:10E的编码为:11F的编码为:00002.(1)深度优先生成树(4分)(2)邻接矩阵(3分)14914158208791520117113.(1)(3分)8564ADEDCFBEA7362357496618455(2)(4分)或4.(求ASL2分,公式1分,结果1分;哈希表构造5分,每对3个关键字得1分)01234567AppleBigFlyJobKeyMan1211118910111213141516MaxSetKidNoOctLadyName2344466ASL=85.213371362433225四、算法阅读题(本大题共2小题,每小题6分,共12分)1.(1)执行函数调用algo(&q)后的队列q中的元素为(8,7,5,4,2)(4分)(2)将队列q中的元素逆置(2分)2.(1)0(4分)(2)如果两个链表相等(对应元素相同,且长度相等)返回结果为1,否则返回结果为0(2分)五、算法设计题(本题10分)LinkListf5(intn){LinkListL,p,q,s;(初始化2分)inte,i;L=(LinkList)malloc(sizeof(LinkNode));L-next=NULL;for(i=1;i=n;i++){(循环架构1分)scanf(″%d″,&e);(输入及查找准备2分)p=L;q=p-next;while(q&&q-datae){(查找插入位置2分)p=q;q=q-next;}if(!q||q-datae){(插入2分)s=(LinkList)malloc(sizeof(LinkNode));s-data=e;s-next=q;736235766184923757496618366p-next=s;}}returnL;(返回1分)}
本文标题:《算法与数据结构》B卷
链接地址:https://www.777doc.com/doc-3528836 .html