《算法与数据结构》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分)}