月自考数据结构试题真题

《月自考数据结构试题真题》由会员分享，可在线阅读，更多相关《月自考数据结构试题真题（8页珍藏版）》请在装配图网上搜索。

1、全国2001年10月高等教育自学考试数据结构试题课程代码：02331第一部分 选择题（30分）、单项选择题（本大题共 15小题，每小题2分，共30分）在每小题列出的四个选项中只有 个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1 算法指的是（）A计算机程序B 解决问题的计算方法C.排序算法D 解决问题的有限运算序列2 线性表采用链式存储时，结点的存储地址（）A 必须是不连续的B 连续与否均可C.必须是连续的D .和头结点的存储地址相连续3 .将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）A . O （1）B. O （n） C. O （m）D. O （ m+

2、n）4 .由两个栈共享一个向量空间的好处是：（）A 减少存取时间，降低下溢发生的机率B 节省存储空间，降低上溢发生的机率C减少存取时间，降低上溢发生的机率D 节省存储空间，降低下溢发生的机率5 .设数组datam作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出B . front=(front+1)%(m-1) D . front=(front+1)%mB .串的长度必须大于零D .空串就是空白串队操作后其头指针front值为（）A. front=front+1C. front=（front-1）%m6. 如下陈述中正确的是（）A .串是一种特殊的线性表C.串中元素

3、只能是字母7. 若目标串的长度为 n,模式串的长度为n/3，则执行模式匹配算法时，在最坏情况下的时间 复杂度是（）nA O( n)B O(n)C. O (n2)D. 0 (n3)B.只能是子表D .可以是子表或原子一个非空广义表的表头（）A .不可能是子表C.只能是原子假设以带行表的三元组表表示稀疏矩阵，则和下列行表02335对应的稀疏矩阵是（）-0-80610-806170007000A.0000B.-5040-504000000000 一Ii0300 一00000000C.0200D.7000-5040-50400000i0300一一00 6 6 |10.在一棵度为3的树中，度为3的结点个

4、数为( )2,度为2的结点个数为1,则度为0的结点个数为C. 611.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）2 2A . eB . 2eC. n eD . n 2e12 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点 w相关的所有弧的时间复杂度是（）用某种排序方法对关键字序列(25,84,21, 47,15, 27, 68, 35,的变化情况如下：20, 15, 21,25,47,27,68,35,8415, 20, 21,25,35,27,47,68,8415, 20, 21,25,27,35,47,68,84则所米用的排序方法是（)A .选择排序B

5、.希尔排序C .归并排序D .快速排序B . 0(e)C . O(n+e)D . O(n*e)C .三叉排序树分块有序表20）进行排序时，序列A . O(n) 13 .14 .适于对动态查找表进行高效率查找的组织结构是（ A .有序表B .）D.线性链表15 .不定长文件是指（）A.文件的长度不固定C.字段的长度不固定B .记录的长度不固定D .关键字项的长度不固定第二部分非选择题（共70分）二、填空题（本大题共 10小题，每小题2分，若有两个空格，每个空格1分，共20分）不写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。16 .数据的逻辑结构是从逻辑关系上描述数据，它与数据的

6、无关，是独立于计算机的。17 .在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=。18 .栈顶的位置是随着操作而变化的。19 .在串S= “structure”中，以t为首字符的子串有 个。20 .假设一个9阶的上三角矩阵 A按列优先顺序压缩存储在一维数组B中，其中B0存储矩阵中第1个元素a“，则B31中存放的元素是 。21.已知一棵完全二叉树中共有768结点，则该树中共有 个叶子结点。22 .已知一个图的广度优先生成树如右图所示，则与此相应的广度优先遍历序列为 。23 .在单链表上难以实现的排序方法有 和24 .在有序表（12, 24 ,

7、 36, 48, 60, 72, 84）中二分查找关键字 72时所需进行的关键字比较次数为。25 .多重表文件和倒排文件都归属于 文件。三、解答题(本大题共 4小题，每小题5分，共20 分)26. 画出下列广义表的共享结构图形表示P= (z) ,(x,y) ,(x,y),x),(z)27. 请画出与下列二叉树对应的森林。28.已知一个无向图的顶点集为a b c d e-0100110010000110110110110a, b, c, d, e,其邻接矩阵如下所示1(1) 画出该图的图形；(2) 根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。29.已知一个散列表如

8、下图所示:35203348590123456789101112其散列函数为h(key)=key%13,处理冲突的方法为双重散列法，探查序列为： hi=(h(key)+ i *h1(key)%m i =0,1,，m 1其中h1(key)=key%11+1回答下列问题：(1) 对表中关键字35 , 20, 33和48进行查找时，所需进行的比较次数各为多少?(2) 该散列表在等概率查找时查找成功的平均查找长度为多少？四、算法阅读题(本大题共 4小题，每小题5分，共20分)30. 下列算法的功能是比较两个链串的大小，其返回值为：-1 当 ss2comstr(S1,S2)= 0当 s1 = q1当 S1

9、 A S2请在空白处填入适当的内容。int comstr(LinkString s1,LinkString s2)/s1和s2为两个链串的头指针while(s1 &s2)if(s1 datedate)retur n 1 ；if(s1 dates2 date)retur n1 ； ；if()return 1 ；if()return1 ；31 阅读下面的算法Lin kList myno te(L in kList L)/L是不带头结点的单链表的头指针if(L&L- next)q=L ； L=L next; p=L ;S1:while(p n ext) p=p n ext;S2：p next=q ;

10、 q next=NULL ; return L;请回答下列问题：(1 )说明语句S1的功能；(2) 说明语句组S2的功能；(3) 设链表表示的线性表为(a1,a2,an),写出算法执行后的返回值所表示的线性表。32 假设两个队列共享一个循环向量空间(参见右下图)，.其类型Queue2定义如下：typedef structDateType dataMaxSize;.冷int front2,rear2;Queue2 ;对于i=0或1, fronti和reari分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。int En Queue (Queue2*Q,i nt i,D

11、ateType x)/若第i个队列不满，则元素 x入队列，并返回1 ;否则返回0 if(i1)return 0 ;if(Q reari=Q front return0 ;Q data =x;Q reari= ;return1 ;33. 已知二叉树的存储结构为二叉链表，阅读下面算法。typedef struct node DateType data;Struct node * next;ListNode ;typedef ListNode * Li nkList Lin kList Leafhead=NULL ; Void Ino rder (Bin Tree T)LinkList s ;lf(

12、T)Inorder(T lchild);If (!T lchild)&(!T rchild) s=(ListNode*)malloc(sizeof(ListNode); s data=T data;s next=Leafhead ； Leafhead=s;Inorder(T rchild);对于如下所示的二叉树(1) 画出执行上述算法后所建立的结构；(2) 说明该算法的功能。五、算法设计题(本题共10分)34. 阅读下列函数arrange()int arran ge(i nt a,i nt 1,i nt h,i nt x)/1和h分别为数据区的下界和上界int i,j,t ;i=1 ； j=h

13、 ； while(ij) while(i=x)j-； while(i=x)i+；if(ij) t=aj ； aj=ai ； ai=t ； if(ai next n ext18.进栈和退栈19. 1220.a4,821 . 38422 .abefcdg23.快速排序、堆排序、希尔排序24.225 .多关键字三、解答题（本大题共 4小题，每小题5分，共20分）26.图127.28 .该图的图形为:深度优先遍历序列为：abdce 广度优先遍历序列为：abedc29. （ 1）对关键字 35、20、33和48进行查找的比较次数为3、2、1、1;（2）平均查找长度AS3 2 112955四、算法阅读题（

14、本大题共4小题，每小题5分，共20分）30. S1=S1- next s2=s2- n ext s2（或 s2!=NULL 或 s2&!s1） si(或 s1!=NULL 或 s1&!s2) return 031. (1)查询链表的尾结点(2)将第一个结点链接到链表的尾部，作为新的尾结点3)返回的线性表为(出,an,ai)32. (i + 1)%2(或 1 i) Q reari(Q reari + )%Maxsize33.(1)LeafheadDALeafhead为头指针。(2 )中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以的逆序单链表(或按二叉树中叶子结点数据自右至左链接成一个链表)五、算法设计题(本题共10分)34. (1)该函数的功能是：调整整数数组a中的元素并返回分界值i，使所有v x的元素均落在a1.i上，使所有x的元素均落在ai + 1.h上。(2) int f(int b,int n)或int f(int b,int n)int p,q ;int p,q ;p=arra nge(b, 0,n 1,0);p=arra nge(b, 0,n 1,1);q= arran ge(b,p+1, n 1,1); q= arran ge(b,0,p,0);return q p;return p q;