山东开放大学数据结构期末复习题.docx

2022学年9月份考试数据结构复习题一、单选题1、数据结构中，与所使用的计算机无关的是数据的（）。A、存储结构B、物理结构C、逻辑结构D、物理和存储结构正确答案：C2、在下列排序方法中，关键字比较的次数与记录的初始排列秩序无关的是（）。A、希尔排序B、冒泡排序C、插入排序D、选择排序正确答案：D3、在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是P所指结点的直接后继，现要删除q所指结点，可用语句（）。A、 p=q->ne×tB、 p->next=qC、 p->next=q->nextD、q->next=NULL正确答案：C4、已知一个有序表为11,22,33,44,55,66,77,88,99,则顺序查找元素55需要比较（）次。A、3B、4C、5D、6正确答案：C5、从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（）A、插入排序B、选择排序C、交换排序D、归并排序正确答案：A6、图的深度优先遍历算法类似于二叉树的（）遍历。A、先序B、中序C、后序D、层次正确答案：A7、二叉树第k层上最多有（）个结点。A、 2kB、C、-1D、2正确答案：B8、常对数组进行的两种基本操作是（）。A、建立与删除B、索引和修改C、查找和修改D、查找与索引正确答案：C9、若串S="English”，其子串的个数是（）oA、 9B、16C、36D、28正确答案：D10、一个队列的入队顺序是a,b,c,d,则离队的顺序是（）。A、a,d,c,bB、 a,b,c,dC、 d,c,b,aD、 c,b,d,a正确答案：B11、设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）oA、 n-i+1B、 n-iC、 n-i-1D、i正确答案：B12、顺序查找方法适合于存储结构为（）的线性表。A、散列存储B、索引存储C、散列存储或索引存储D、顺序存储或链接存储正确答案：D13、利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为（）。A、 18B、16C、12D、30正确答案：A14、设某一二叉树先序遍历为abdec,中序遍历为dbeac,则该二叉树后序遍历的顺序是（）。A、abdecB、 debacC、 debcaD、 abedc正确答案：C15、下列有关二叉树的说法正确的是（）。A、二叉树中度为O的结点的个数等于度为2的结点的个数加1B、二叉树中结点个数必大于OC、完全二叉树中，任何一个结点的度，或者为O或者为2D、二叉树的度是2正确答案：A16、算法的时间复杂度与（）有关。A、所使用的计算机B、计算机的操作系统C、算法本身D、数据结构正确答案：C17、算法分析的目的是（）。A、找出数据结构的合理性B、研窕算法中的输入和输出的关系C、分析算法的效率以求改进分析算法的易懂性和文档性D、分析算法的易懂性和文档性正确答案：C18、链表不具有的特点是（）。A、可随机访问任一元素B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表长度成正比正确答案：A19、在图的存储结构表示中，表示形式唯一的是（）。A、nB、n+1C、n-1D、n/2正确答案：C20、对于顺序存储的有序表5,12,20,26,37,42,46,50,64）,若采用折半查找，则查找元素26的比较次数是（）oA、2B、3C、4D、5正确答案：C21、以下陈述中正确的是（）oA、串是一种特殊的线性表B、串的长度必须大于零C、串中元素只能是字母D、空串就是空白串答案：A22、设有两个串P和q,其中q是P的子串，q在P中首次出现的位置的算法称为（）,A、求子串B、连接C、匹配D、求串长答案：C23、串是（）。A、不少于一个字母的序列B、任意个字母的序列C、不少于一个字符的序列D、有限个字符的序列答案：D解析：24、串的长度是指（）。A、串中所含不同字母的个数B、串中所含字符的个数C、串中所含不同字符的个数D、串中所含非空格字符的个数答案：B25、两个字符串相等的条件是（）oA、两串的长度相等B、两串包含的字符相同C、两串的长度相等，并且两串包含的字符相同D、两串的长度相等，并且对应位置上的字符相同答案：D二、填空题1、树中度大于。的结点称作或。正确答案：第1空：分支结点第2空：非终端结点2、哈夫曼树又称为正确答案：第1空：最优二叉树3、在一棵树中，每个结点的子树的根或者说每个结点的称为该结点的孩子结点，简称为孩子。正确答案：第1空：后继结点4、树中度等于。的结点称作或。正确答案：第1空：叶子结点第2空：终端结点5、图常用的两种存储结构是和。正确答案：第1空：邻接矩阵第2空：邻接表6、在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针，当删除一个元素队列时，头指针。正确答案：第1空：增1第2空：增17、在对一组记录(50,40,95,20,15,70,60,45,80)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需要比较次。正确答案：第1空：38、关键字是记录某个，用它可以识别、确定一个记录。正确答案：第1空：数据项的值9、具有m个叶子结点的哈夫曼树共有结点。正确答案：第1空：2m-l10、串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是。正确答案：第1空：字符11、在一个单向链表中，要删除P所指结点，已知q指向P所指结点的前驱结点。则可以用操作正确答案：第1空：q->next=p->next12、冒泡排序是一种比较简单的方法。正确答案：第1空：交换排序13、单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向。正确答案：第1空：头结点的指针第2空：指向第一个结点的指针14、在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种的关系正确答案：第1空：多对多15、数据结构中的数据元素存在多对多的关系称为结构。正确答案：第1空：图状结构;图结构16、分块查找又称为，它是一种介于顺序查找和折半查找之间的查找方法。正确答案：第一空：索引顺序查找17、在有序表A口.18中，采用二分查找算法查找元素值等于A17的元素，所比较过的元素的下标依次是。正确答案：第一空：9,14,16，1718、栈是限定在表的一端进行插入和删除操作的线性表，又称为。正确答案：第一空：后进先出表19、在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针，当删除一个元素队列时，头指针。正确答案：第一空：增1第二空：增120、广义表A(a,b,c),(d,e,f)的表尾为。正确答案：第一空：(d,e,f)三、简答题1、编写顺序查找算法。顺序查找算法如下：intsearch(NODEa,intn,intk)/*在a0an-l中顺序查找关键字等于k的记录。查找成功时返PI该记录的下标，失败时返回)正确答案：顺序查找算法如下：intsearch(NODEa,intn,intk)/*在aOan-l中顺序查找关键字等于k的记录。查找成功时返PI该记录的下标，失败时返回L*/(inti=0;while(i<n&&ai.key!=k)/*没有查到同时查找过程没有结束，则继续查找*/i+；if(ai.key=k)/*查找成功*/returni;elsereturn-1;/*查找失败*/)2、简述栈和一般线性表的区别正确答案：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。3、简述队列和一般线性表的区别。正确答案：队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行,而一般的线性表可以在线性表的任何位置进行插入和删除操作。4、(1)设有查找表8,17,5,9,21,10,7,19,6,依次取表中数据，构造一棵二叉排序树.(2)说明如何通过序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果.正确答案：1 .2 .中序遍历：2,3,4,5,6,7,14,16,18四、资料题1、下面函数的功能是返回二叉树BT中值为X的结点所在的层号，请在划有横线的地方填写合适内容。intNodeLevel(structBinTreeNode*B'charX)(If(BT=NULL)return0;/*空树的层号为0*/elseif(BT->data=X)return1;/*根结点的层号为1*/*向子树中查找X结点*/elseintcl=NodeLevel(BT->left,X);if(cl>=l)；intc2=(2);if一(3)；若树中不存在X结点则返回OelsereturnO;)正确答案：第一空：returncl+1第二空：NodeLevel(BT->rightzX)第三空：(c2>=l)returnc2+l2、阅读下面算法，在划线处填入正确的代码内容intwrite(LinkQueue*q)QueueNode*p;if(q->front=q->rear)/*队空*/printf("underflow”);exit(O);)while(q->front->next!=NULL)p=q->front->next;(1)Printf("%4d"p>data);(2)(3) ；*队空时，头尾指针指向头结点*/)正确答案：第一空：q->front->next=p->ne×t;第二空：free(p);第三空：q->rear=q->front