自考数据结构2008-1-1.doc

全天24小时服务咨询电话 [phone]免费热线 4008135555 自考名师全程视频授课，图像、声音、文字同步传输，享受身临其境的教学效果； 权威专家在线答疑，提交到答疑板的问题在24小时内即可得到满意答复； 课件自报名之日起可反复观看不限时间、地点、次数，直到当期考试结束后一周关闭； 付费学员赠送1G超大容量电子信箱；及时、全面、权威的自考资讯全天24小时滚动更新； 一次性付费满300元，即可享受九折优惠；累计实际交费金额500元或支付80元会员费，可成为银卡会员，购课享受八折优惠；累计实际交费金额1000元或支付200元会员费，可成为金卡会员，购课享受七折优惠（以上须在同一学员代码下）；英语/高等数学预备班：英语从英文字母发音、国际音标、基本语法、常用词汇、阅读、写作等角度开展教学；数学针对有仅有高中入学水平的数学基础的同学开设。通过知识点精讲、经典例题详解、在线模拟测验，有针对性而快速的提高考生数学水平。立即报名！基础学习班：依据全新考试教材和大纲，由辅导老师对教材及考试中所涉及的知识进行全面、系统讲解，使考生从整体上把握该学科的体系，准确把握考试的重点、难点、考点所在，为顺利通过考试做好知识上、技巧上的准备。立即报名！冲刺串讲班：结合历年试题特点及命题趋势，规划考试重点内容，讲解答题思路，传授胜战技巧，为考生指出题眼，提供押题参考。配合高质量全真模拟试题，让学员体验实战，准确地把握考试方向、将已掌握的应试知识融会贯通，并做到举一反三。立即报名！习题班：自考365网校与北大燕园合作推出，共计390门课程，均涵盖该课程全部考点、难点，在线测试系统按照考试难度要求自动组卷、全程在线测试、提交后自动判定成绩。我们相信经过反复练习定能使您迅速提升应试能力，使您考试梦想成真！立即报名！论文答辩与毕业申请指导班：来自主考院校的指导老师全程视频授课，系统阐述申报自考论文的时间、论文的选题、论文的格式及内容、与导师的沟通技巧等，并提供论文范例供学员参考。立即报名！自考实验班：针对高难科目开设，签协议，不及格返还学费。全国限量招生，报名咨询 010-82335555 立即报名！全国2008年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.在数据结构中，数据的基本单位是( )A. 数据项B. 数据元素C. 数据对象D. 数据文件2.k=1; for（i=0；in；i+） for（j=0；jnext-next!=h) p=p-next; p-next=h; 后（其中，p-next为p指向结点的指针域），则( )A. p-next指针指向链尾结点 B. h指向链尾结点 C. 删除链尾前面的结点 D. 删除链尾结点 5.设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( )A.236 B.239 C.242D.2456.一个栈的入栈序列是a，b，c，d，e，则栈的输出序列不可能是( )A. dceabB. decbaC. edcbaD. abcde7.元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为( )A. top=topB. top=n-1C. top=top-1D. top=top+18.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是( )A.高度等于其结点数B.任一结点无左孩子 C.任一结点无右孩子D.空或只有一个结点9.在完全二叉树中，若一个结点是叶结点，则它没有( )A.左孩子结点B.右孩子结点 C.左孩子结点和右孩子结点D.左孩子结点，右孩子结点和兄弟结点10.邻接矩阵为对称矩阵的图是( )A. 有向图B. 带权有向图 C. 有向图或无向图D. 无向图11.在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为( )A.n-1 B.n C.n+1D.12.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不超过( )A. B. nC. D. n+113.闭散列表中由于散列到同一个地址而引起的“堆积”现象，是( )A.由同义词之间发生冲突引起的 B.由非同义词之间发生冲突引起的 C.由同义词之间或非同义词之间发生冲突引起的 D.由散列表“溢出”引起的14.一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用的排序方法是( )A. 快速排序B. 堆排序C. 插入排序D. 二路归并排序15.在排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( )A.希尔排序 B.插入排序C.冒泡排序 D.快速排序得分二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。错填、不填均无分。16.数据的逻辑结构通常包括集合、线性结构、_和图状结构。17.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，指针s指向双链表中的一个结点（该结点既非头结点，也非尾结点），则删除s指针所指向结点的操作为“s-tl-r1=s-r1；”和“_”。18.对稀疏矩阵进行压缩存储的目的是节省_。19.在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则需平均比较的结点数为_。20.深度为15的满二叉树上，第11层有_个结点。21.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为_。22.一个具有4个顶点的无向完全图有_条边。23.一个有向图G中若有孤、和，则在图G的拓扑序列中，顶点Vi，Vj和Vk的相对位置为_。24.在一棵二叉排序树上按_遍历得到的结点序列是一个有序序列。25.实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是_的。26.文件的检索有三种方式，它们是顺序存取、直接存取和_存取。27.在插入排序和选择排序中，若原始记录已基本有序，则较适合选用_。28.对n个元素的序列进行冒泡排序时，最多需进行_趟。三、应用题(本大题共5小题，每小题6分，共30分)29.写出利用直接选择排序方法对一组关键码为（54，38，96，23，15，72，60）的记录进行排序时，每趟排序的结果。30.已知一棵二叉树的中根遍历序列和后根遍历序列分别为BDAFEHGC和DBFHGECA，试画出这棵二叉树。31.设闭散列表容量为7（散列地址空间0.6），给定表（30，36，47，52，34）,散列函数H（K）=K mod 6，采用线性探测法解决冲突，要求：（1）构造散列表；（2）求查找数34需要比较的次数。 32.如题32图所示，在栈的输入端有6个元素，顺序为A，B，C，D，E，F。能否在栈的输出端得到序列DCFEBA及EDBFCA？若能，给出栈操作的过程，若不能，简述其理由。 题32图33.已知无向图G的邻接表如题33图所示，请画出该无向图，并写出其按广度优先搜索时的访问序列。其中nil表示空。题33图四、算法设计题(本大题共2小题，每小题7分，共14分)34.编写一个函数void insert(int *p,int size,int a)，其功能是将a插入指针变量p指向的长度为size的数组中。设数组中的数据已按升序排序。该函数要求实现的功能是：首先采用折半查找的方法，找出要插入数据的位置；然后按升序将数据插入该数组中。35.某带头结点的单链表的结点结构说明如下： typedef struct node1 int data; struct node1 *next node；试设计一个算法int copy(node *head1, node *head2)，将以head1为头指针的单链表复制到一个不带头结点且以head2为头指针的单链表中。 自考365（-）领先的专注于自学考试的网络媒体与服务平台 - 本套试题共分4页，当前页是第4页-