山开数据结构期末复习题.docx
2023学年数据结构复习题一、单选题1、组记录的关键字序列为（25,48,16,35,79,82,23,40,36,72）,其中,含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（）A、16,25,35, 48, 23, 40, 79, 82, 36, 72B、工6,25, 35, 48,79, 82, 23, 36, 40, 72C、16,25, 48, 35, 79, 82, 23, 36, 4072D、 16, 25,35,48,79,23,36,40,82,72正确答案：A2、顺序查找法与二分查找法对存储结构的要求是（）。A、顺序查找与二分查找均只是适用于顺序表B、顺序查找与二分查找均既适用于顺序表，也适用于链表C、顺序查找只是适用于顺序表D、二分查找适用于顺序表正确答案：D3、已知下图所示的一个图，若从顶点Vl出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A、V1V2V4V8V3V5V6V7B、V1V2V4V5V8V3V6V7C、V1V2V4V8V5V3V6V7D、V1V3V6V7V2V4V5V8正确答案：C4、设某一二叉树先序遍历为abdec.中序遍历为dbeac,则该二叉树后序遍历的顺序是（）。A、abdecB、debacC、debcaD、abedc正确答案：C5、在图的存储结构表示中，表示形式唯一的是（）。A、nB%n+1C、n-1D、n/2正确答案：C6、在正常情况下，直接插入排序的时间复杂度为（）.A、O（log2n）B、0（n）C、0（nIog2n）D、0（n2）正确答案：D7、将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号,根结点的编号为1,则编号为69的结点的双亲结点的编号为（）。A,33B,34C、35D,36正确答案：B8,以下陈述中正确的是（）.A、串是一种特殊的线性表B、串的长度必须大于零C,串中元素只能是字母D、空串就是空白串正确答案：A9、设一棵哈夫曼树共有n个叶结点，则该树有（）个非叶结点。A、nB、n-1Csn+1D、2n正确答案：B10、利用n个值作为叶结点的权生成的哈夫曼树中共包含有（）个结点。A、nB、n+1C,2*nD、2*n-l正确答案：D11、数据结构中，与所使用的计算机无关的是数据的（）.A、存储结构B,物理结构C、逻辑结构D、物理和存储结构正确答案：C12、下列的叙述中，不属于算法特性的是（）.A、有穷性B、输入性C、可行性D、可读性正确答案：D13、设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）。A.n-i+1B、nTC,n-i-1D、i正确答案：B14、在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是P所指结点的直接后继，现要删除q所指结点，可用语句（）.A、p=q->ne×tBp->next=qC、p->next=qnextDq->next=NULL正确答案：C15、链表不具有的特点是（）.A、可随机访问任一元素B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表长度成正比正确答案：A16、在一个链队中，假设f和I分别为队头和队尾指针，则插入S所指结点的运算为（A、f->next=s;f=s;Br->next=s;r=s;C、s->next=r;r=s;Ds->next=fjf=s;正确答案：B17、一个队列的入队序列是1,2,3,4。则队列的输出序列是（）。A、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,21正确答案：B18、在一个栈顶指针为top的链栈中，将一个P指针所指的结点入栈，应执行（MA、top->next=p;B、p->next=top->next;top->next=p;C、p->next=top;top=p;D、p->ne×t=top->ne×t;top=top->ne×t;正确答案：C19、判断一个循环队列Q（最多元素为m0）为空的条件是（）。A、Q->front=Q->rearB、Q->front!=Q->rearC、Q->front=（Q->rear+l）%mD、Q->frontl=（Q->rear+l）%mO正确答案：A20,一个递归算法必须包括（）。A、递归部分B、终止条件和递归部分C、迭代部分D、终止条件和迭代部分正确答案：B21、设有两个串P和q,其中q是P的子串，q在P中首次出现的位置的算法称为（A.求子串B、连接C,匹配D、求串长正确答案：C22、在一棵度为3的树中，度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为（）.A,4B、SC、6D,7正确答案：C23、利用n个值作为叶结点的权生成的哈夫曼树中共包含有（）个结点。A、nB、n+1C,2*nD、2*n-l正确答案：D24、二叉树的深度为k,则二叉树最多有（）个结点。A,2kB,2k-lC、D,-1正确答案：D25、无向图的邻接矩阵是一个（）.A、对称矩阵B、零矩阵C、上三角矩阵Ds对角矩阵正确答案：A26、己知下图所示的一个图，若从顶点VI出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）.A.V1V2V4V8V3V5V6V7B、V1V2V4V5V8V3V6V7C、V1V2V4V8V5V3V6V7D、V1V3V6V7V2V4V5V8正确答案：C27、当两个元素出现逆序的时候就交换位置，这种排序方法称为（）.A.插入排序B、交换排序C、选择排序D、归并排序正确答案：B28、在正常情况下，直接插入排序的时间复杂度为（）。A、O（log2n）B、0（n）C、0(nIog2n)D、0(n2)正确答案：D29、己知10个数据元素为(54,28,16,34,73,62,95,60,26,43),对该数列从小到到大排序，经过一趟冒泡排序后的序列为A、16,B、28,C、28,D、16,28,16,16,28,34,34,34,34,54, 73,54, 62,54, 62,5% 62,62,73,60,60,60,60,73,73,26,26,26,26,43,43,43,43,(M95959595正确答案：B二、填空题30、树的带权路径长度为树中所有叶子结点的o正确答案：第1空：带权路径长度之和31、为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为。正确答案：第1空：栈32、在一个带权图中，两顶点之间的最段路径最多经过条边。正确答案：第1空：n-133、结点的度是指结点所拥有的。正确答案：第1空：子树数目或后继结点数34、中缀表达式(a+b)/c，(f-d/c)所对应的后缀表达式是。正确答案：第1空：ab+cfde-或35、树中度等于0的结点称作正确答案：第1空：叶子结点第2空：终端结点36、数据结构中的数据元素存在一对多的关系称为结构。正确答案：第1空：树形结构;树结构结构。37、数据结构中的数据元素存在一对一的关系称为正确答案：第1空：线性结构38、每个结点只包含一个指的域的线性表叫。正确答案：第1空：单链表39、线性表具有和两种存储结构。正确答案：第1空：顺序存储第2空：链式存储;链接存储40、在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针，当删除一个元素队列时，头指针。正确答案：第1空：l/.1第2空：增141、栈是限定在表的一端进行插入和删除操作的线性表，又称为。正确答案：第1空：后进先出表42、串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是。正确答案：第1空：字符43、8.设广义表L=(),(),则L的长度是。正确答案：第1空:244、若以4,5,6,7,8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是.正确答案：第1空：6945、在有n个顶点的有向图中，每个顶点的度最大可达。正确答案：第1空：211-1)三、简答题46、写出如下图所示的二叉树的先序、中序和后序遍历序列。正确答案：(1)先序为"根左右",先序序列为：fdbacegihl(2)中序为"左根右"，中序序列为：abcdefghij(3)后序为"左右根",后序序列为：acbedhjigf47、头指针、头结点、第一个结点(或称首元结点)的区别是什么？正确答案：头结点是在链表的开始结点之前附加的一个结点；第一个结点(或称首元结点)是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针.48、简述栈和一般线性表的区别正确答案：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。49、简述广义表和线性表的区别和联系。正确答案：广义表是线性表的的推广,它也是n(n>O)个元素al,a2aian的有限序列,其中ai或者是原子或者是一个广义表.所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当ai都是原子时，广义表退化成线性表。四、资料题50、己知序列(10,18,4,3,6.12,1,9,15.8),请写出对此序列采用归并排序法进行升序排序时各趟的结果。正确答案：第1空：答：原始序列：10,18.4.3,6,12,1,9,15,8第1趟：10,183,46,121,9118,15第2趟：3.4,10,18,1,6,9,128,15第3趟：3,4,10,18.1,6,8,9,12,15第4趟：1,3,4,6,8,9.10,12,15,1851、intwrite(LinkQueue*q)QueueNode*p;if(q->front=q->rear)/*队空*/printf(wunderflow,);exit(O);while(q->front->nextI=NULL)p=q->front->ne×t;(1)printf(“4d”，p>data);(3);/*队空时，头尾指针指向头结点*/正确答案：第1空：q->front->next=p->next;第2空：free(p);第3空：q->rear=q->front52、下列是在具有头结点单向列表中删除第i个结点，请在空格内填上适当的语句。intdelete(NODE*head,inti)NODE*p,*q;intj;
