自学考试数据结构导论试题7套.doc
《自学考试数据结构导论试题7套.doc》由会员分享,可在线阅读,更多相关《自学考试数据结构导论试题7套.doc(43页珍藏版)》请在三一文库上搜索。
1、全国2008年10月高等教育自学考试 数据结构导论试题 课程代码:02142一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.从逻辑上可以把数据结构分为(C) A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构2.关于算法的描述,不正确的是(D) A.算法最终必须由计算机程序实现 B.所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界 C.健壮的算法不会因非法的输入数据而出现莫名其妙的状态 D.算法的优劣与算法描述语言无关
2、3.在单链表中,存储每个结点需要有两个域,一个是数据域,另一个是指针域,指针域指向该结点的(B) A.直接前趋 B.直接后继 C.开始结点 D.终端结点4.将两个各有n个元素的有序表合并成一个有序表,其最少的比较次数为(A) A.n B.2n-1 C.2n D.n25.栈和队列共同具有的特点是(C) A.都是先进后出 B.都是先进先出 C.只允许在端点进行操作运算 D.既能先进先出,也能先进后出6.若用一个有6个单元的数组来实现循环队列,rear和front的初值分别为0和3。则从队列中删除一个元素,再添加两个元素后,rear和front的值分别为(B) A.1和5 B.2和4 C.4和2 D
3、.5和17.数组A0.50.5的每个元素占5个字节,将其以列为主序存储在起始地址为1000的内存单元中,则元素A55的地址是(A) A.1175 B.1180 C.1205 D.12108.含有n个结点的二叉树采用二叉链表存储时,空指针域的个数为(C) A.n-1 B.n C.n+1 D.n+2 9.在一棵深度为H的完全二叉树中,所含结点的个数不少于(B) A.2H-1-1 B.2(H-1) C.2H-1 D.2H10.一个具有n个顶点的无向连通图,它所包含的连通分量数为(D) A.0 B.1 C.n D.不确定11.下列说法中不正确的是(D) A.无向图的极大连通子图称为连通分量 B.连通图
4、的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D.有向图的遍历不可采用广度优先搜索算法12.对一棵二叉排序树采用中根遍历进行输出的数据一定是(A) A.递增或递减序列 B.递减序列 C.无序序列 D.递增序列13.一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100,当二分查找值为82的结点时,查找成功时的比较次数为(C) A.1 B.2 C.4 D.8 14.一组记录的关键字为45,80,55,40,42,85,则利用堆排序的方法建立的初始堆为(B) A.80,45,55,40,42,85 B.
5、85,80,55,40,42,45 C.85,80,55,45,42,40 D.85,55,80,42,45,4015.关于VSAM文件存取操作的说法,正确的是(D) A.不能顺序存取,只能按关键字随机存取 B.不能顺序存取,不能按关键字随机存取 C.只能顺序存取,不能按关键字随机存取 D.既能顺序存取,也能按关键字随机存取二、填空题(本大题共13小题,每小题2分,共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.在任何问题中,数据元素都不是孤立的,它们之间总存在某种关系,通常称这种关系为_逻辑结构_。 17.存储结点之间通常有四种基本存储方式,即顺序存储方式、索引存储方式
6、、_链式存储_和散列存储方式。 18.在一个长度为n的顺序表中第i个元素(1in)之前插入一个元素时,需向后移动_n-i+1_个元素。19.对一棵深度为10的满二叉树按层编号,则编号为51的结点,它的双亲结点编号为_25_。 20.用S表示入栈操作,X表示出栈操作,若元素入栈顺序为1234,为了得到1342的出栈顺序,相应的S和X操作串为_SXSSXSXX_。 21.具有n个叶子结点的哈夫曼树,其结点总数为_2*n-1_。 22.一棵具有n个结点的树,所有非终端结点的度均为k,则该树中叶子结点个数为_1_。 23.在无向图G的邻接矩阵A中,若Aij等于0,则Aji等于_0_。 24.两个串是相
7、等的,当且仅当两个串的长度相等且_对应下标的_的字符都相同。 25.某二叉树的后根遍历序列为abd,中根遍历序列为adb,则它的先根遍历序列为_adb_。 26.先在所有的记录中选出键值最小的记录,将它与第一个记录交换;然后在其余的记录中再选出最小的记录与第二个记录交换,依此类推,直至所有记录排序完成。这种排序方法称为_直接选择排序_。 27.对含有n个结点e条边的无向连通图,利用prim算法生成最小生成树的时间复杂度为_ 0(n2)_。 28.对n个元素进行冒泡排序时,最少的比较次数为_n-1_。 三、应用题(本大题共5小题,每小题6分,共30分) 29.设有编码为A,B,C,D的4列火车,
8、依次进入一个栈式结构的站台,试写出这4列火车开出站台的所有可能的顺序。 (D,C,B,A);(C,B,A,D);(B,A,D,C);(A,D,C,B)30.画出题30图所示的二叉树的二叉链表存储结构。题30图 p8031.对于题31图,试给出:(1)邻接矩阵; p109(M1)(2)邻接表。 p112题31图 32.给定表(39,14,22,8,65,28,88,29,67,13,10),试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树,画出插入完成后的二叉排序树。 33.用插入排序算法对数据序列(47,33,61,82,72,11,25,57)进行排序,写出整个插入排序的每一趟过
9、程。(33,47)61,82,72,11,25,57(33,47,61)82,72,11,25,57(33,47,61,82)72,11,25,57(33,47,61,72,82)11,25,57(11,33,47,61,72,82)25,57(11,25,33,47,61,72,82)57(11,25,33,47,57,61,72,82)四、算法设计题(本大题共2小题,每小题7分,共14分) 34.设两个数据元素均为整型数据的线性表A=(a1,a2,an)和B=(b1,b2,bm)。若n=m且ai=bi(i=1,2,,n)则认为A=B;若ai=bi(i=1,2,,j)且aj+1BJ+1,(J
10、lchild);rh=Depth(t-rchild);retrun lhrh?lh+1:rh+1;全国2009年1月高等教育自学考试 数据结构导论试题 课程代码:02142 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.数据的不可分割的最小标识单位是(A) A.数据项 B.数据记录 C.数据元素 D.数据变量2. for(i=0;im;i+)for(j=0;jt;j+)cij=0;for(i=0;im;i+)for(j=0;jt;j+)for(k=0;knext=pnex
11、tnext B.p=pnext C.p=pnextnext D.pnext=p5.向一个栈顶指针为hs的链栈中插入一个*s结点时,应执行的操作为(D) A.hsnext=s; B.snext=hs;hs=s; C.snext=hsnext;hsnext=s; D.snext=hs;hs=hsnext;6.设循环队列的元素存放在一维数组Q030中,队列非空时,front指示队头元素的前一个位置,rear指示队尾元素。如果队列中元素的个数为11,front的值为25,则rear应指向的元素是(B) A.Q4 B.Q5 C.Q14 D.Q157.定义二维数组A18,010,起始地址为LOC,每个元素
12、占2L个存储单元,在以行序为主序的存储方式下,某数据元素的地址为LOC+50L,则在以列序为主序的存储方式下,该元素的存储地址为(C) A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L8.具有n个结点的二叉树,拥有指向孩子结点的分支数目是(A) A.n-1 B.n C.n+1 D.2n9.对一棵有100个结点的完全二叉树按层序编号,则编号为49的结点,它的左孩子的编号为(B) A.99 B.98 C.97 D.5010.有m个叶子结点的哈夫曼树,其结点总数是(A) A.2m-1 B.2m C.2m+1 D.2(m+1)11.有n个结点的无向图的边数最多为(B) A
13、.n+1 B.n(n-1)/2 C.n(n+1) D.2n(n+1) 12.设图的邻接矩阵为,则该图为(C) A.有向图 B.无向图 C.强连通图 D.完全图13.二分查找算法的时间复杂度是(D) A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n)14.已知8个元素(34,76,45,18,26,54,92,65),按照依次插入结点的方法生成一棵二叉排序树,则该树的深度为(A) A.4 B.5 C.6 D.715.采用排序算法对n个元素进行排序,其排序趟数肯定为n-1趟的排序方法是(C) A.插入和快速 B.冒泡和快速 C.选择和插入 D.选择和冒泡二、填空题(本大题共
14、13小题,每小题2分,共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.在数据结构中,数据的存储结构有顺序存储方式、链式存储方式、_索引_和散列存储方式等四种。17.作为一个算法输入的数据所含数据元素的数目,或与此数目有关的其他参数,称为_计算量_。 18.在双链表中,存储一个结点有三个域,一个是数据域,另两个是指针域,分别指向_前驱结点_和_后继结点_。 19.在有n个元素的链队列中,入队和出队操作的时间复杂度分别为_0(1)_和_0(1)_。 20.在栈结构中,允许插入的一端称为_栈顶_;在队列结构中,允许插入的一端称为_对头_。 21.在循环队列中,存储空间为0n-1
15、。设队头指针front指向队头元素前一个空闲元素,队尾指针指向队尾元素,那么其队空标志为rear=front,队满标志为_front=rear+1_。 22.深度为k的二叉树至多有_2k-1_个结点,最少有_k_个结点。 23.设有一稠密图G,则G采用_索引_存储结构较省空间。设有一稀疏图G,则G采用_链式存储_存储结构较省空间。 24.在一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较_(1+n)/2_个元素结点。 25.假定对线性表R059进行分块检索,共分为10块,每块长度等于6。若检索索引表和块均用顺序检索的方法,则检索每一个元素的平均检索长度为_1_。
16、 26.文件在外存储器上的组织结构主要有三种:顺序文件、散列文件和索引文件,其中_顺序文件_特别适应磁带存储器,也适应磁盘存储器。 27.在插入排序、冒泡排序、快速排序、归并排序等排序算法中,占用辅助空间最多的是_归并排序_。 28.冒泡排序最好的时间复杂度为_0(n-1)_,平均时间复杂度为_0(n2)_,是一种稳定的排序算法。 三、应用题(本大题共5小题,每小题6分,共30分) 29.已知一棵二叉树的前序序列是ABCDEFG,中序序列是CBDAEGF。请构造出该二叉树,并给出该二叉树的后序序列。 30.将题30图所示的由三棵树组成的森林转化为一棵二叉树。(A,B,H,E,C,I,O,F,D
17、,J,P,G,K,Q,C,R,M,N)题30图 31.已知某图的邻接表存储结构如题31图所示:题31图 (1)画出该图。 (2)根据该邻接表从顶点A出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。深度优先搜索法(A,B,C,E,H,G,F,D) 32.假定采用H(k)=kmod7计算散列地址,引用线性探测的开放定址法解决冲突,试在06的散列地址空间中,对关键字序列(38,25,74,63,52,48)构造散列表,并求出等概率情况下查找成功的平均查找长度。 ASL=333.用快速排序法对数据序列(49,38,65,97,16,53,134,27,39)进行排序,写出其第一趟排序
18、的全过程。(39,38,65,97,16,53,134,27,49)(39,38,49,97,16,53,134,27,65)(39,38,27,97,16,53,134,49,65)(39,38,27,49,16,53,134,97,65)(39,38,27,16,49,53,134,97,65)四、算法设计题(本大题共2小题,每小题7分,共14分) 34.完善下列折半插入排序算法。 Voidbinasort(structnoderMAXSIZE,int n) for(i=2;i=n;i+) r0=ri;low=1;high=i-1; while(low=high) mid=(1)_(low
19、+high)/2_; if(r0.key=low;j-) (4)_rmid=rj_; rlow=r0; 35.下列算法的功能是求出指定结点在给定的二叉排序树中所在的层次。请完善该算法。 Void level(BSTree root,p)intlevel=0; if(!root) (1)_return (0)_; else level+; while(rootkey!=pkey) if(rootkey pkey key) (2)_level(root-lchild,p)_; else (3)_ level (root-rchild)_; level+; (4)_return(level)_; 全
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 自学考试 数据结构 导论 试题
链接地址:https://www.31doc.com/p-5189907.html