《自学考试-数据结构自考题模拟13》由会员分享，可在线阅读，更多相关《自学考试-数据结构自考题模拟13（7页珍藏版）》请在金锄头文库上搜索。
1、数据结构自考题模拟13一、单项选择题K为便于判别有向图中是否存在回路，可借助于（）A. 广度优先搜索算B.最小生成树算法C.最短路径算D.拓扑排序算法2、在头指针为head的非空单循坏链表中，指针p指向尾结点，下列关系成立的是（）A- pnext=headB- pnextNext =headC- pnext = =NULLD. p=head3、设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。A. 5 B. 6C7 D84、若有序表的关键字序列为（b,c,d,6f,g，dr,s,t）,则在二分查找关键字b的过程小，先后进行比较的关键字依次为（）A f , c, b B f z d
2、, b C. gz c z bD gz d, b5、以下有关数据结构的叙述，正确的是（）A. 线性表的线性存储结构优于链式存储结构B. 二叉树的第i层上有2“个结点，深度为K的二叉树上有2个结点C. 二维数组是其数据元索为线性表的线性表D. 栈的操作方式是先进先出6、设rear是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为（）A. s = rear；B. rear=rearnext；rear=rearnext；free （rear）；free （s）；C. rear=rearnextnext ；D. s = rearnextnext ；free （rear） ；rearn
3、extnext = snext ；free （s）；7、采用分治法进行排序的方法是（）A.快速排序B.插入排序C.堆排序 D.希尔排序8、对长度为n的关键字序列进行堆排序的空间复杂度为（）A Odogn B. 0（1）C 0（n） D 0（n*log2n）9、在桶排序中，其平均时间复杂度是（）A. 0（1） B 0（n） C 0（r?） D. 0 （lgn）10森林T中有4棵树，第一、二、三、四棵树的结点个数分别是i, n2, n3, n4,那么当把森林T转 换成一棵二叉树后，其根结点的左孩了上有（）个结点。A nrl B. n1 C. n1+n2+n3 D n2+n3+n4、数据结构是（）A
4、一种数据类型B. 数据的存储结构C. 一组性质相同的数据元素的集合D. 相互之间存在一种或多种特定关系的数据元素的集合12两个字符串相等的条件是()A.串的长度相等B.含冇相同的字符集C.都是非空串D.串的长度相等且对应的字符相同13. 邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的()A.先序遍历B.中序遍历 C.后序遍历 D.按层遍历14. 如果我们采用二分查找法查找一个长度为n的有序表，则查找每个元素的平均比较次数()对应的判定树的高度(假设树高h$2)。A.大于 B.小于 C.等于 D.无法确定15. 一个具有N个顶点的冇向图最多冇()条边。A N(N：L)/2 B. N(N-
5、l) C N(N+1) D N(N+l)/2填空题丄6、在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线性表的链接存储中，元素Z间的逻辑关系是通过决定的。17. 对于一个二维数组Am n,若按行序为主序存储，则任一元索Ai j相对于A0 0的地址为O18、若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是的。丄9、对于数组，通常具有的基本操作有种，它们分别是。20、如果我们定义一个长度为N的串空间，则它最多能放个字符。21、己知广义表人=(az b, c) , (d, e, f),贝ll运算head (head (tail (tailA.) ) ) =。22若对关键字
6、序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为3的希尔排序, 则得到的结果为。23、无向图的邻接矩阵是,并且主对角线上的元素的值为。24、散列函数的作用是：。25、在按照顺序存储方式存储的数组中，元索的存储地址应该是数组的加上排在丟，前面的元素所占用的单元数。三、解答题26、对序列(48,37,63,96,22,31,50,55,11)进行升序的堆排序,写出构建的初始(大根)堆及 前两趟重建堆之后的序列状态。初始堆：第1趟：第2趟：利用广义表的head和tai.操作，可从广义表 L=(a,b), (cz d)中分解得到原子C,其操作表达式为head(he
7、ad(tail(L)；分别写出从下列广义表中分解得到b的操作表达式。27L1=(a,b,c,d)；28L2=(a),(b)z (c),(d)。29画出对表长为13的冇序顺序表进行二分查找的判定树；3 0已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99),写出在该序列中 二分查找37时所需进行的比较次数。四、算法阅读题假设学生成绩按学号增序存储在带头结点的单链农中，类型定义如下: typedef struct Nodeint id； /*学号*/int score；/*成绩*/srruct Node*next；LNode,*LinkList;阅读算法
8、f31,并回答问题：31设结点结构为idscorenext成绩链表A和B如图所示，画出执行算法f31 (A,B.T 1170| zUgTX4|4刑 4H 5156INT 2|38| 4嗣二H 5 75|32简述算法f31的功能。void f31(LinkList A,LinkList B LinkList p,q；p=Anext ；q=Bnext ；while(p&q) if (pidp=pnext;else if (pidqid) q=qnext;else if (pscorescorescore=q score ； else pscore=60;p=pnext ；q=qnext;阅读下列算
9、法，并回答问题：33无向图G如图所示，写出算法f30(&G的返回值；34简述算法f30的功能。#define MaxNum 20int visitedMaxNum；void DFS(Graph*gz int i);/*从顶点vi出发进行深度优先搜索，访问顶点匕时置visitedj为/ int f30(Graph*g) int i z k；for (i = 0 ; iN；工+ + )visitedi=0；if(visitedi=0) k+；DFS(g,i);return k；五、法设计题35、对一个有七个非零值元素的mxn矩阵，用B0.tz1.3的数组來表示，其中第0行的三个元素 分别是mznz
10、t，从第一行开始到最后一行，每行表示一个非零元素，第一列为矩阵元素行号，第二列 为其列号，第三列为其元索量，对这样的表示法，试编写一个算法确定任意一个元索Ai j的位 置，并考虑若修改其元素值须用多少时间？（设B中第1列原行号是递增的）答案：一、单项选择题1 D2 A解析在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点，就得到了单链形式的 循环链表，并简单称为单循环链表。故由题目中此单循环锚表的头指针为head,指针p指向尾结点， 可得pfnext=head。3、A4、A5、C6、D7 A8、B解析由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地
11、 排序，辅助空间为0（丄），但它是不稳定的。9、B10 A11、D12 D13、A14、 B15 B二、填空题16. 相邻位置 链接指针17、ixj+i全元素位置18、稳定19、两 查找和修改20、N-l21、22 15 z 02 Z21 z24 z26z57 z 43,66,80,48,7323、对称零24、压缩待处理的下标范围，待处理的|u|个值减少到m个值，从而降低空间开销25基地址三、解答题27 head(tail(LI)28、head(head(tail(head(L2)29、30、26、初始堆：(96,55,63,48,22,31,50,37,11) 第1 趟：(63,55,50,
12、48,22,31,11,37,96) 第2趟：(55,4 8,50,3 7,22,31,11,63,96)四.算法阅读题31、32、对于表A中成绩低于60的学生，如果在表B中也有成绩记录，则将表A中的成绩修改为其 在表B中的成绩；但若其在表B中的成绩高于60分，则只改为60分。33、34、返冋无向图g中连通分量的个数。五. 算法设计题3 5、分析题意可得其算法思想为：首先可在数组B中找到相应的行，然后找到相应的列，即可修改其元素值，可假定要修改的 Ai j,原先就具冇非零值。从而可将算法苦述为：lorte (Bz t, i, j z v) /*确定任意一个元素Ai j的位置*/ datatyp
13、e B ; /*B 的杆标为 0.t 和 1.3*/ int tz i,j ；float v； datatype A ；/*A的下彳示为 1 .mfll. .n, A表示mxn矩卩车*/int p ；P= 1 7while ( (B p 1 ! =1) &； &； (pt)printf Chasn11 element foundnn)；else while ( (B p 1 = = i) * (p=t) &(B p i !=j ) P+;if ( (Bp l=i)&(Bp 2 !=j)B p 3 =v；else printf (no element foundn)； /*lorte*|显然，在本算法中可能出现的最坏情况：一是需要修改的元素位于B中最后一行；二是Bi j 先的元素值为零，而无法在B中查找到相应的位置。所以，在这两种情况下的时间复杂度为0代)。
