全国高等教育自学考试数据结构试题及解析.docx
- 文档编号:18503429
- 上传时间:2023-08-18
- 格式:DOCX
- 页数:21
- 大小:91.65KB
全国高等教育自学考试数据结构试题及解析.docx
《全国高等教育自学考试数据结构试题及解析.docx》由会员分享,可在线阅读,更多相关《全国高等教育自学考试数据结构试题及解析.docx(21页珍藏版)》请在冰点文库上搜索。
全国高等教育自学考试数据结构试题及解析
全国2008年10月高等教育自学考试
数据结构试题
(课程代码:
02331)
一、单项选择题(本大题共15小题,每小题2分,共30分)
在每小题列出的四个备选项中只有一个是最符合题目要求的,请将其代码填写在题后的括号内。
错选、多选或未选均无分。
1.如果在数据结构中每个数据元素只可能有一个直接前驱,但可以有多个直接后继,则该结构是()
A.栈B.队列
C.树D.图
2.下面程序段的时间复杂度为()
for(i=0;i for(j=0;j A[i][j]=i*j; A.O(m2)B.O(n2) C.O(m*n)D.O(m+n) 3.在头指针为head的非空单循环链表中,指针p指向尾结点,下列关系成立的是() A.p->next==headB.p->next->next==head C.p->next==NULLD.p==head 4.若以S和X分别表示进栈和退栈操作,则对初始状态为空的栈可以进行的栈操作系列是 () A.SXSSXXXXB.SXXSXSSX C.SXSXXSSXD.SSSXXSXX 5.两个字符串相等的条件是() A.串的长度相等B.含有相同的字符集 C.都是非空串D.串的长度相等且对应的字符相同 6.如果将矩阵An×n的每一列看成一个子表,整个矩阵看成是一个广义表L,即 L=((a11,a21,…,an1),(a12,a22,…,an2),…,(a1n,a2n,…,ann)),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素,则求得a21的运算是() A.head(tail(head(L)))B.head(head(head(L))) C.tail(head(tail(L)))D.head(head(tail(L))) 7.已知一棵含50个结点的二叉树中只有一个叶子结点,则该树中度为1的结点个数为 () A.0B.1 C.48D.49 8.在一个具有n个顶点的有向图中,所有顶点的出度之和为Dout,则所有顶点的入度之和为() A.DoutB.Dout-1 C.Dout+1D.n 9.如图所示的有向无环图可以得到的拓扑序列的个数是() A.3B.4 C.5D.6 10.如图所示的带权无向图的最小生成树的权为() A.51B.52 C.54D.56 11.对长度为n的关键字序列进行堆排序的空间复杂度为() A.O(log2n)B.O (1) C.O(n)D.O(n*log2n) 12.已知用某种排序方法对关键字序列(51,35,93,24,13,68,56,42,77)进行排时,前两趟排序的结果为 (35,51,24,13,68,56,42,77,93) (35,24,13,51,56,42,68,77,93) 所采用的排序方法是() A.插入排序B.冒泡排序 C.快速排序D.归并排序 13.已知散列表的存储空间为T[0..18],散列函数H(key)=key%17,并用二次探测法处理冲突。 散列表中已插入下列关键字: T[5]=39,T[6]=57和T[7]=7,则下一个关键字23插入的位置是() A.T[2]B.T[4] C.T[8]D.T[10] 14.适宜进行批量处理的文件类型是() A.顺序文件B.索引顺序文件 C.散列文件D.多关键字文件 15.VSAM文件的索引结构为() A.B+树B.二叉排序树 C.B-树D.最优二叉树 二、填空题(本大题共10小题,每小题2分,共20分) 请在每小题的空格中填上正确答案。 错填、不填均无分。 16.如果某算法对于规模为n的问题的时间耗费为T(n)=3n3,在一台计算机上运行时间为t秒,则在另一台运行速度是其64倍的机器上,用同样的时间能解决的问题规模是原问题规模的倍。 17.将两个长度分别为m和n的递增有序单链表,归并成一个按元素递减有序的单链表,可能达到的最好的时间复杂度是。 18.已知循环队列的存储空间大小为m,队头指针front指向队头元素,队尾指针rear指向队尾元素的下一个位置,则在队列不满的情况下,队列的长度是。 19.字符串“sgabacbadfgbacst”中存在有个与字符串“ba”相同的子串。 20.假设以列优先顺序存储二维数组A[5][8],其中元素A[0][0]的存储地址为LOC(a00),且每个元素占4个存储单元,则数组元素A[i][j]的存储地址为。 21.假设用 22.n个顶点且含有环路的无向连通图中,至少含有条边。 23.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中,所需记录交换次数最少的是。 24.和二分查找相比,顺序查找的优点是除了不要求表中数据元素有序之外,对结构也无特殊要求。 25.顺序文件中记录存放的物理顺序和顺序一致。 三、解答题(本大题共4小题,每小题5分,共20分) 26.由森林转换得到的对应二叉树如图所示,写出原森林中第三棵树的前序序列和后序序列。 前序序列: 后序序列: 27.图的邻接表的类型定义如下所示: #defineMaxVertexNum50 typedefstructnode{ intadjvex; structnode*next; }EdgeNode; typedefstruct{ VertexTypevertex; EdgeNode*firstedge; }VertexNode; typedefVertexNodeAdjList[MaxVertexNum]; typedefstruct{ AdjListadjlist; intn,e; }ALGraph; 为便于删除和插入图的顶点的操作,可将邻接表的表头向量定义为链式结构,两种定义的存储表示实例如下图所示,请写出重新定义的类型说明。 28.某类物品的编号由一个大写英文字母及2位数字(0..9)组成,形如E32。 运用基数排序对下列物品编号序列进行按字典序的排序,写出每一趟(分配和收集)后的结果。 E13,A37,F43,B32,B47,E12,F37,B12 第一趟: 第二趟: 第三趟: 29. (1)画出对表长为13的有序顺序表进行二分查找的判定树; (2)已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99),写出在该序列中二分查找37时所需进行的比较次数。 (1) (2) 四、算法阅读题(本大题共4小题,每小题5分,共20分) 30.已知线性表的存储结构为顺序表,阅读下列算法,并回答问题: (1)设线性表L=(21,-7,-8,19,0,-11,34,30,-10),写出执行f30(&L)后的L状态; (2)简述算法f30的功能。 voidf30(SeqList*L){ inti,j; for(i=j=0;i if(L->data[i]>=0) { if(i! =j) L->data[j]=L->data[i]; j++; } L->length=j; } (1) (2) 31.阅读下列算法,并回答问题: (1)Q、Q1和Q2都是队列结构,设队列Q=(1,0,-5,2,-4,-6,9),其中1为队头元素,写出执行f31(&Q,&Q1,&Q2)之后队列Q、Q1和Q2的状态; (2)简述算法f31的功能。 (注: lnitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入列出队和判队空的操作) voidf31(Queue*Q,Queue*Q1,Queue*Q2) { inte; lnitQueue(Q1); lnitQueue(Q2); while(! QueueEmpty(Q)) { e=DeQueue(Q); if(e>=0)EnQueue(Q1,e); elseEnQueue(Q2,e) } } (1) (2) 32.阅读下列算法,并回答问题: (1)假设串由合法的英文字母和空格组成,并以’\0’作结束符。 设串s=”⊔⊔|⊔am ⊔a⊔⊔⊔student”(⊔表示空格符),写出f32(s)的返回值; (2)简述算法f32的功能。 intf32(char*s) { inti,n,inword; n=inword=0; for(i=0;s[i]! =’\0’;i++) if(s[i]! =’⊔’&&inword==0) { inword=1; n++; } elseif(s[i]==’⊔’&&inword==1) inword=0; returnn; } (1) (2) 33.阅读下列对正整数关键字序列L操作的算法,并回答问题: (1)设L=(28,19,27,49,56,12,10,25,20,50),写出f33(L,4)的返回值; (2)简述函数f33的功能。 intPartition(SeqList*L,intlow,inthigh); ∥对L[low..high]做划分,返回基准记录的位置,并使左部的关键字 ∥都小于或等于基准记录的关键字,右部的关键字都大于基准记录的关键字 intf33(SeqListL,intk) { intlow,high,pivotpos; low=1; high=L.length; if(k return-1; do { pivotpos=Partition(&L,low,high);∥调用快速排序的划分算法 if(pivotpos low=pivotpos+1; elseif(pivotpos>k) high=pivotpos-1; }while(pivotpos! =k); returnL.data[pivotpos]; } (1) (2) 五、算法设计题(本题10分) 34.二叉排序树的类型定义如下: typedefstructBSTNode{∥二叉排序树的结点结构 intdata;∥数据域 structBSTNode*lchild,*rchild;∥左、右孩子指针 }BSTNode,*BSTree; 设计递归算法,统计一棵二叉排序树T中值小于a的结点个数。 全国2008年10月高等教育自学考试 数据结构试题解析 (课程代码: 02331) 一、单项选择题(本大题共15小题,每小题2分,共30分)。 1.CP69 【解析】在树中,除了根结点和叶子结点外,其余结点都只有一个直接前趋而有一个或多个直接后驱续,而根结点没有直接前趋而有直接后续,叶子结点没有直接后续而有直接前趋。 【点评】本题考查考生对各种数据结构定义的识记程度。 2.CP8 【解析】此程序的时间复杂度即为程序中循环次数的时间耗费,由程序的嵌套循环,外循环的时间复杂度为T(n1)=m,内程序的时间复杂度为T(n2)=n,此程序的时间复杂度为T(n)=m*n。 即为O(m*n) 【点评】属必考题。 本题的特点是给出一个小程序段,求其时间复杂度,此题一定含一个或两个循环,看的是最内层语句的执行次数。 3.AP25 【解析】在单链表中,将终端结点的指针域NULL改为指向表头头结点或开始结点,就得到了单链形式的循环链表,简称为单链表。 题中单链表的头指针为head,指针p指向尾节点,尾节点的指针域指头结点,所以p->next指向head。 【点评】属必考题。 特点是用指针操作链表,考生在遇到此类型题目时应注意链表是单链表还是单循环链表,或是双链表,有无表头或表尾。 并且操作的顺序不能乱。 4.DP32 【解析】可以按以下两个原则来判断出正确的栈操作序列: (1)操作序列中进栈次数和出栈次数相等。 (2)操作系列中的任意操作之前进栈次数大于等于出栈次数。 【点评】属必考题,考查考生对栈的操作规则是否熟练,即“后进先出”规则。 并且,栈满再进栈发生“上溢”,栈空再出栈发生“下溢”。 “溢出”都被视为错误。 5.DP51 【解析】字符串相等的条件有: 字符串的长度相等,字符串中字母相等。 【点评】识记性内容,仅一句话,但考的频率却不低,多会以填空题形式来考 6.AP66 【解析】若广义表LS非空(n≥1),则a1是LS的表头,其余元素组成的表(a2,a3………a6)称为LS的表尾,则此题目要求a21,则需先要进行取表头运算head(L)的子表1(a11,a22,……n1),在对子表1进行取表尾运算tail(head(L)),得带子表2(a21……an1)在对表2进行取表头运算head(tail(head(L)))可的元素a21. 【点评】属必考题。 本题考查了广义表的两个特殊的基本运算: 即取表头head(LS)和取表尾tail(LS)。 7.DP71 【解析】有此二叉树仅有一个叶子结点,及仅有一个结点的度为零。 在二叉树中,n0表示度为零的结点数,n2表示度为二的结点数,n1表示度为1的结点数,n0=n2+1,n0=1,则n2=0,又有n=n0+n1+n2,则n=n0+n1=1+n1=50,则n1=49。 【点评】属常考题。 考查二叉树的概念,从叶子结点只有一个就可看出这棵树没有分支。 因此除了叶子结点没有度,其余50-1个结点的度都为1。 所以答案为: 49。 8.AP101 【解析】在一个有向图中,所有顶点的出度之和等于所有顶点的入度之和。 【点评】本题考查了对有向图出入度关系的掌握程度。 9.CP127 【解析】拓扑排序算法思想: 选择有向图中入度为0的顶点输出,并从图中删去该点相邻弧;重复上述操作,直到图中全部顶点均被输出或图中已不存在入度为0的顶点(有回路)。 按此排序可得到: 2,6,5,3,4 2,6,3,5,4 6,2,5,3,4 6,2,3,5,4 6,5,2,3,4 【点评】属常考题。 拓扑排序的方法要重点掌握。 10.CP115 【解析】连通网G=(V,E),边是带权的,因而G的生成树的各边也是带权的。 将生成树的各边的权值总和称为生成树的权,并把权最小的生成树称为G的最小生成树。 按此规则选择权的先后顺序为10,14,12,18,他们的和为54 【点评】属必考题。 要重点掌握最小生成树的概念。 11.BP156 【点评】A选项是堆排序的最坏时间复杂度。 由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序,辅助空间为O (1),但它是不稳定的。 【点评】各种排序的时间复杂度和空间复杂度是重点内容。 12.BP142 【解析】相邻元素依次进行比较,小的前移,大的后移,第一趟结束后,最大元素放在了最后;再进行第二趟,使次大元放在最大元素之前;继续,直到在一趟排序中没有交换发生,排序结束。 由题中第一趟排序的结果是把所有关键字中最大的关键字(93)放入序列最后,第二趟排序的结果是把除93以外的所有节点中的最大关键字(77)放在了序列的倒数第二个位置。 可知排序方法是冒泡排序。 【点评】本题考查对几种排序方法的掌握。 是必考内容。 13.DP197 【解析】23%17结果为6,因此关键字23是要插入到T[6]位置的,但T[6],T[7]都已提前被占用了,此时采用二次探测法,di=(d+i2)modm,当i=1时,di=(23+12)mod17=7,冲突仍存在,当i=2时,di=(23+22)mod17=10,T[10]空闲,所以插入到T[10]了。 【点评】本题考查了利用二次探测解决冲突的方法,是重点掌握内容。 14.AP209 【解析】顺序文件采用顺序查找法对于少量的检索是不经济的,但适合于批量检索,即把用户的检索要求先进性积累,一旦待查记录聚集到一定量之后,便把这些记录按照主关键字排序,然后,通过一卒顺序扫描文件来定这一批检索要求。 【点评】本题考查了几种检索方法的特点,是重点掌握内容。 15.AP214 【解析】VSAM是VirtualStorageAccessMethod(虚拟存储存取方法)的缩写,它也是一种索引顺序文件的组织方式,采用B+树作为动态索引结构。 【点评】本题考查VAAM文件的索引结构,是重点掌握内容。 二、填空题(本大题共10小题,每小题2分,共20分)。 16.4P8 【解析】设在速度快的机器上运行此算法的规模为n,则时间耗费为T1=(n1)=3n13,则由速度快机器是眼来机器的64倍,即T1/T=(n1)=3n13/3n3,则n1/n=4,即在同样的时间内速度快的机器解决问题规模是原来机器解决问题规模的4倍。 【点评】本题考查了时间复杂度的概念,是重点考查内容。 17.O(m+nP18 【解析】将两个递增有序单链表合并成一个递减有序的单链表,则将这两个单链表都从最后一个元素开始,按照由后至前的顺序,将两单链表中元素进行比较,从而选择较大的元素依次组成的单链表。 【点评】本题考查了时间复杂度的问题,是重点掌握内容。 18.(rear-front+m)%mP38 【解析】循环队列的结构可以知道队列长度可以表示为(队尾指针-对头指针加队长)模队长。 【点评】属必考题。 循环队列的考题每次考试都会有,应注意存储空间m,求队列的长度时不忘与m求一次余。 19.3P51 【解析】子串的定位操作通常称为串的模式匹配或串匹配,是各种串处理系统中重要的操作之一。 早串匹配中,一般将主串成为目标(串),字串称为模式串,在主串中有3个字串。 【点评】考查最基本的串的模式匹配,属送分题。 20.Loc(a00)+(i+j*5)*4P60 【解析】在二维数组中,假设首个元素为a00,每行元素为i,每列元素为j,每个元素占n个字节,则按列优先顺序可表示为Loc(aij)=(a00)+(i+j*i)*n 【点评】属必考题。 特点是已知数组首地址,已知每个元素占用的存储空间大小,求某个元素的地址。 这里应注意是按行排列还是按列排列。 本题有一定难度,应细心求解。 21.3P70 【解析】根据题目说明可得出如上草图,一个结点拥有的子树数称为该结点的度。 一棵树的度是指该树中结点的最大度数。 【点评】本题考查了树的度,是重点掌握内容。 22.n-1P102 【解析】n个顶点的无向连通图有环回路且边最少时,此图仅有一个环路且所有顶点均在此环路中,此时边数为n。 【点评】本题考查了有向回路环的特点。 23.选择排序P150 【解析】选择排序是每一趟(例如第i趟,i=1,…,n-1)在后面的n-i+1个待排序对象中选出关键字最小的对象,作为有序对象序列的第i个对象。 待到第n-1趟作完,直至全部排序完毕,最好情况下对象的比较次数为0. 【点评】本题考查了几种排序的特点,是重点掌握内容。 24.存储P170 【解析】顺序查找的优点是算法简单,且对表的结构无任何要求,无论是用向量还是用链表来存放结点,也无论结点之间是否按关键字有序,它都同样适用。 顺序查找的缺点是查找效率低,因此,当n较大时不宜采用顺序查找。 而二分查找时静态查找表必须按关键字有序(用向量作为存储结构)。 【点评】本题考查了二分查找和顺序查找的区别,是重点掌握内容。 25.逻辑P208 【解析】顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。 【点评】本题考查了书序存储的特点,是重点掌握内容。 三、解答题。 (本大题共4小题,每小题5分,共20分) 26.(P76)第三棵树是: 前序序列是: GHIJ 后序序列是: HJIG 【解析】二叉树转换为森林的方法为: 若结点x是其父结点y的左孩子,则把结点x的右孩子、右孩子的右孩子、……,都与该结点的父结点y用线线连;去掉树中所有父结点到其右孩子的连线,生成森林。 则题中二叉树得到的三棵树分别为 第三棵树的前序遍历和后序遍历分别为GHIJ和HJIG 【点评】常考题型,考法有且仅有2种: (1)题目给出一棵二叉树,求其前序序列和后序序列; (2)给出前序、中序、后序序列中的任2个,要求画出与其所对应的二叉树。 27.(P105) typedefstructArcNode{ VNode*adjvex;//该弧所指向的顶点位置 structArcNode*nextarc//指向下一条弧的指针 }ArcNode; typedefstructVNode{ VertexTypedata;//顶点信息 structVNode*nextVertex;//指向下一顶点的指针 ArcNode*firstarc;//指向第一条依附该节点的弧 }VNodeAdjList typedefstruct{ adjListadjlist; intn,e; }ALGraph; 【解析】本题一定要有指向下一顶点和弧的指针以及指向第一条依附给结点的弧。 【点评】设计算法重新设计数据是本门课的难点,我们需多下功夫。 28.(P161) 【解析】基数排序是采用“分配”与“收集”的办法,用对多关键字进行排序的思想实现对单关键字进行排序的方法,排序中不需要进行比较。 本题是先按最低位排序,再按次低位排序,最后按最高位排序。 【点评】排序算法是必考内容,考的几率比较大的有: 归并排序、冒泡排序、快速排序、直接插入排序;比较难的是希尔排序,快速排序,堆排序。 因此,要熟练掌握和运用排序算法,不论从考试还是实用性来看,排序算法都有其重要意义。 29. (1)(P170) (2) 【解析】二分查找首先要确定该区间中点位置mid=(low+high)/2,然后将待查的K值与R[mid].key比较,若相等,则查找成功并返回此位置,否则重新确定查找位置,若R[mid].keyK,则由表的有序性可知R[mid……n].key均大于K因此若表中存在关键字等于K的节点,则该结点必定在mind的左表中,在上题中,我们首先我们首先确定中间节点是(1+13)/2=7,按此方法求出每个中结结点,他们就是二分查找判定树的结点。 在实际序列中,确定35为中间结点,37大于35,就和第8~13之间的中间结点67比较,37小于67,于是37又和43~52之间的中间结点42比较,比较之后没有找到,不再进行比较。 【点评】二分查找法应该说是在查找这一章中占有最重要的地位(考试几率高),其次是二叉排序树和散列表。 四、算法阅读题。 (本大题共4小题,每小题5分,共20分) 30.(P13) (1)L=(21,19,0,34,30) (2)删除表中所有小于0的值,并依次移动其后的数来填补空缺,以形成新表。 【解析】线性表中的元素如果是正数的话,则执行L->data[j]=L->data[i]语句,然后i,j分别加1,如果是负数,不执行L->data[j]=L->data[
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国 高等教育 自学考试 数据结构 试题 解析