《自考数据结构2007-10-1.doc》由会员分享，可在线阅读，更多相关《自考数据结构2007-10-1.doc（6页珍藏版）》请在金锄头文库上搜索。
1、 全天24小时服务咨询电话 010-82335555免费热线 4008135555 自考名师全程视频授课，图像、声音、文字同步传输，享受身临其境的教学效果； 权威专家在线答疑，提交到答疑板的问题在24小时内即可得到满意答复； 课件自报名之日起可反复观看不限时间、地点、次数，直到当期考试结束后一周关闭； 付费学员赠送1G超大容量电子信箱；及时、全面、权威的自考资讯全天24小时滚动更新； 一次性付费满300元，即可享受九折优惠；累计实际交费金额500元或支付80元会员费，可成为银卡会员，购课享受八折优惠；累计实际交费金额1000元或支付200元会员费，可成为金卡会员，购课享受七折优惠（以上须在同一
2、学员代码下）；英语/高等数学预备班：英语从英文字母发音、国际音标、基本语法、常用词汇、阅读、写作等角度开展教学；数学针对有仅有高中入学水平的数学基础的同学开设。通过知识点精讲、经典例题详解、在线模拟测验，有针对性而快速的提高考生数学水平。立即报名！基础学习班：依据全新考试教材和大纲，由辅导老师对教材及考试中所涉及的知识进行全面、系统讲解，使考生从整体上把握该学科的体系，准确把握考试的重点、难点、考点所在，为顺利通过考试做好知识上、技巧上的准备。立即报名！冲刺串讲班：结合历年试题特点及命题趋势，规划考试重点内容，讲解答题思路，传授胜战技巧，为考生指出题眼，提供押题参考。配合高质量全真模拟试题，让
3、学员体验实战，准确地把握考试方向、将已掌握的应试知识融会贯通，并做到举一反三。立即报名！习题班：自考365网校与北大燕园合作推出，共计390门课程，均涵盖该课程全部考点、难点，在线测试系统按照考试难度要求自动组卷、全程在线测试、提交后自动判定成绩。我们相信经过反复练习定能使您迅速提升应试能力，使您考试梦想成真！立即报名！论文答辩与毕业申请指导班：来自主考院校的指导老师全程视频授课，系统阐述申报自考论文的时间、论文的选题、论文的格式及内容、与导师的沟通技巧等，并提供论文范例供学员参考。立即报名！自考实验班：针对高难科目开设，签协议，不及格返还学费。全国限量招生，报名咨询 010-82335555
4、 立即报名！ 全国2007年10月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.在数据结构中，从逻辑上可以把数据结构分成( )A.线性结构和非线性结构B.紧凑结构和非紧凑结构C.动态结构和静态结构D.内部结构和外部结构2.for（i=0；im；i+）for（j=0；jn；j+）Aij=i*j；上面算法的时间复杂度为( )A.O(m2)B.O(n2)C.O(mn)D.O(m+n）3.设顺序表有9个元素，则在第3个元素前插入一个
5、元素所需移动元素的个数为( )A.5B.6C.7D.94.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用pllink和prlink表示，则同样表示p指针所指向结点的表达式是( )A.pllink B.prlinkC.pllinkllinkD.pllinkrlink5.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是( )A. 110B. 108C. 100D. 1206.设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是( )A.DCBAB.CDABC.DBAC D.DCAB7.在一个具有n个单元的顺序栈中，假定以地址低端（即
6、0单元）作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为( )A.top+ B.top- C.top不变 D.top=08.除根结点外，树上每个结点( )A.可有任意多个孩子、一个双亲B.可有任意多个孩子、任意多个双亲C.可有一个孩子、任意多个双亲D.只有一个孩子、一个双亲9.题9图中树的度为( ) A.2 B.3C.5D.8 题9图10.有4个顶点的无向完全图的边数为( )A.6B.12C.16 D.2011.设图的邻接矩阵为，则该图为( )A.有向图B.无向图 C.强连通图D.完全图12.在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要
7、适合于( )A.静态查找表B.动态查找表C.静态查找表与动态查找表D.静态查找表或动态查找表13.用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得到相同散列函数值的冲突现象。可用于解决上述问题的是( )A.线性探测法B.除留余数法C.平方取中法D.折叠法14.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是( )A.选择排序B.插入排序C.冒泡排序 D.快速排序15.在排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为( )A.希尔排序B.归并排序 C.插入排序D.选择排序二、填空题(本大题共13小题，每小题2分，共26分
8、)请在每小题的空格中填上正确答案。错填、不填均无分。16.如果操作不改变原逻辑结构的“值”，而只是从中提取某些信息作为运算结果，则称该类运算为_型运算。 17.设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“pnext=head；”和“_”。18.单链表中逻辑上相邻的两个元素在物理位置上_相邻。19.在一个长度为n的数组中删除第i个元素（1in）时，需要向前移动的元素的个数是_。20.设F、C是二叉树中的两个结点，若F是C的祖先结点，则在采用后根遍历方法遍历该二
9、叉树时，F和C的位置关系为：F必定在C的_。21.若用后根遍历法遍历题21图所示的二叉树，其输出序列为_。 题21图22.具有n个顶点的连通图至少需有_条边。23.在无向图G的邻接矩阵A中，若Aij等于1，则Aji等于_。24.设顺序表的表长为n，且查找每个元素的概率相等，则采用顺序查找法查找表中任一元素，在查找成功时的平均查找长度为_。25.在索引顺序表上的查找分两个阶段：一是查找_，二是查找块。26.文件的基本运算有检索和修改两类。而检索又有三种方式，它们是_存取、直接存取和按关键字存取。27.在对一组关键字为（54，38，96，23，15，72，60，45，83）的记录采用直接选择排序法
10、进行排序时，整个排序过程需进行_趟才能够完成。28.冒泡排序是一种稳定排序方法。该排序方法的时间复杂度为_。三、应用题(本大题共5小题，每小题6分，共30分)29.分别写出题29图中二叉树的先根、中根、后根遍历序列。题29图30.设要将序列（Q，H，C，Y，P，A，M，S，R）按字母升序排序，请分别画出采用堆排序方法时建立的初始堆，以及第一次输出堆顶元素后经过筛选调整的堆的完全二叉树形态。 31.如题31图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，试写出在栈的输入端三个可能的输入序列。 题31图32.已知无向图G的邻接矩阵如题32图所示。请画出该无向图，并写出按深度优先搜
11、索时的访问序列。题32图33.对长度为20的有序表进行二分查找，试画出它的一棵判定树。四、算法设计题(本大题共2小题，每小题7分，共14分)34.下面程序段为删除循环链表中第一个info域值等于x的结点，请填上程序中缺少的部分。循环链表的结构如题34图所示：题34图struct node int info;struct node *link; int Delete (struct node *head, int x) struct node *p, *q; /*p:当前处理的结点；q：p的前驱结点*/ if (! head ) return (0); if (headlink =head) i
12、f (headinfo=x) free (head);head=NULL；return (x) return (0); p=head; q=head; while (qlink!=head) q=(1) ; while (plink!=head) if (pinfo=x) (2) ; if (p=head) head=(3) ; free (p);return (x); else q=p ;（4） ; return (0); 35.设以二叉链表为二叉树的存储结构，结点的结构如下：lchilddatarchild其中data域为整数，试设计一个算法void change(bitreptr r): 若结点左孩子的data域的值大于右孩子的data域的值，则交换其左、右子树。 自考365（--）领先的专注于自学考试的网络媒体与服务平台 - 本套试题共分6页，当前页是第6页-
