资源描述：
《数据结构2009学年第1学期试卷(A卷).doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、华南农业大学期末考试试卷（A卷）2009学年第一学期考试科目：数据结构考试类型：（闭卷） 考试时间： 120分钟学号姓名年级专业题号一二三四总分得分评阅人考生须知：1．答案必须写在“答卷”上，写在试卷上不得分。2．考试结束时，只回收答题卡，不回收试卷。3.必须在答题卡上正确填写班级、学号、姓名等内容，否则没有考试成绩一、选择题（每小题2分，共20分）1、如果最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。A．单链表B．双链表C．单循环链表D．顺序表2、经过以下栈运算后，x的值是（）。InitStack(s);Push(s,a);
2、Push(s,b);Pop(s,x);GetTop(s,x);A．aB．bC．1D．03、一个队列的入队序列为1234，则队列可能的输出序列是（）。A.4321B.1234C.1432D.32414、已知模式串的next数组，使用KMP算法进行串匹配，以下空格应填入的语句是（）。intIndex_KMP(SStringS,SStringT,intpos){//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的//KMP算法。其中，T非空，1≤pos≤StrLength(S)。intnext[255];inti=pos;intj=1;g
3、et_next(T,next);while(i<=S[0]&&j<=T[0]){if(j==0
4、
5、S[i]==T[j]){//继续比较后继字符++i;++j;}else;//模式串向右移动}if(j>T[0])returni-T[0];//匹配成功elsereturn0;}//Index_KMPA．j=next[j]B．i=next[j]C．j=i+1D．i=j+15、深度为5的二叉树至多有（）个结点。A．16B．32C．31D．106、根据使用频率为5个字符设计的哈夫曼编码不可能是（）。A．000，001，010，011，1B．0000，0001，
6、001，01，1C．000，001，01，10，11D．00，100，101，110，1117、如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所有顶点，则该图一定是（）。A.完全图B.连通图C.有回路D.一棵树8、任何一个无向连通图（）最小生成树。A．只有一棵B．有一棵或多棵C．一定有多棵D．可能不存在9、有一个有序表位{1,3,9,12,32,41,45,62,75,77,82,95,99}，当采用二分查找法查找关键字为82的元素时，（）次比较后查找成功。A．1B．2C．4D．810、在以下排序算法中，关键字比较的次数与记录的初始排列次序无
7、关的是（D）。A.希尔排序B.冒泡排序C.插入排序D.直接选择排序二、应用题（共30分，每题6分）1、依次把结点{16,3,7,11,9,26,18,14,15}插入到初始状态为空的平衡二叉排序树中，使得在每次插入后保持该树仍然是平衡二叉排序树。要求画出每次插入后所形成的平衡二叉排序树。2、在学生的课程安排中,有些课程必须在学完其先修课程才能开始。如软件工程专业的学生必须学习的课程之间的一个关系如下表所示：课程编号课程名称先修课程C1程序设计基础无C2离散数学C1C3数据结构C1,C2C4汇编语言C1C5语言的设计和分析C3,C4C6计算机原理C11
8、C7编译原理C3.C5C8操作系统C3,C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C1,C9,C10（1）要求用AOV网将上表中课程以及课程之间的优先关系表示出来；（2）假设每次只安排一门课程，请给出一个包含所有课程的合理安排序列，使到在开始任一门课程之前其先修课程已经完成。1、二叉树可采用静态链表的形式表示，即用游标指示器指示其后继结点在结构数组中的相对位置(即数组下标)，游标为0相当于NULL指针。设二叉树BT的存储结构如下：其中BT为树根结点的指针，其游标值为6，Lchild,Rchild分别为结点的左、右孩子的游标域
9、，data为结点的数据域。完成下列各题：（l）画出该二叉树BT；（2）写出按先序、中序、后序遍历该二叉树所得到的结点序列。2、关键字序列为{19,14,23,1,68,20,84,27,55,11,10,79}，哈希函数为H(key)=keymod13，采用链地址法处理冲突，给定哈希表的长度为13（0-12），要求画出关键字序列在哈希表中的存储状态，并计算在等概率情况下，查找成功的平均查找长度。3、已知序列{503,87,512,61,908,170,897}，用二叉树的形式画出采用堆排序算法对该序列作升序排列时的每一趟结果（包括所建立的初始堆）。三
10、、程序填空题（共30分，每空2分，注意：每空只填一个语句）1、归并过程：已知两个有序的顺序表La和Lb，将其
