数据结构与程序设计知到智慧树期末考试答案题库2025年北京航空航天大学

数据结构与程序设计知到智慧树期末考试答案题库2025年北京航空航天大学非空线性链表中，若要在由p所指的链结点后面插入新结点q，则应执行语句（）。结点结构为structNode{intvalue;structNode*link;};

答案:q->link=p->link;p->link=q;阅读程序，程序的运行结果为（）。#includeinttry(int);intmain(){intx;x=try(5);printf("%d\n",x);return0;}inttry(intn){if(n>0)return(n*try(n-2));elsereturn(1);}

答案:15递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。

答案:栈选择：对有8个元素的序列（49，38，65，97，76，13，27，50）按从小到大顺序进行排序，（）是选择排序法的第一趟的结果。

答案:13,38,65,97,76,49,27,50说法正确的是：（）。

答案:OLD是一个结构类型设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是（）。

答案:3设有以下说明语句：structstrutype{inta;floatb;}var;则下面叙述中错误的是（）。

答案:var是用户定义的结构类型名设有一顺序栈S，元素a,b,c,d,e,f,g,h依次进栈，如果8个元素出栈的顺序是d,f,e,c,h,g,b,a，则栈的容量至少应该是（）。

答案:5设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD13,散列地址为1的链中有（）个记录。

答案:4设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）

答案:32154设n是描述问题规模的非负整数，下列程序片段的时间复杂度是（）x=2；while(x答案:O(1og2n)若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。

答案:O(n)若要进行从小到大排序，数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（）。

答案:插入排序若栈和队都采用顺序存储结构，则下述说法正确的是（）。

答案:队不为空时可以进行出队操作。若某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为100，则第10个元素的存储地址为（）。

答案:136若某栈初始为空，PUSH与POP分别表示对栈进行一次进栈与出栈操作，那么对于进栈序列a,b,c,d,e,经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH以后，得到的出栈序列是（）。

答案:b,c若有说明:char*language[]={"FORTRAN","BASIC","PASCAL","JAVA","C"};则以下不正确的叙述是（）。

答案:language包含5个相同长度的数组若有以下说明和语句:structstudent{intage;intnum;;}std,*p;p=&std;则以下对结构变量std中成员age的引用方式不正确的是（）。

答案:*p.age若有以下程序段structdent{intn;int*m;};inta=1,b=2,c=3;structdents[3]={{101,&a},{102,&b},{103,&c}};structdent*p=s;则以下表达式值为2的是（）。

答案:*(++p)->m若有以下定义,则数值不为3的表达式是（）。intx[10]={0,1,2,3,4,5,6,7,8,9},*p1;

答案:p1=x+2,*(p1++)若已知一个栈的入栈序列是1,2,3…，30，其输出序列是p1,p2,p3,…pn,若p1=30,则p10为（）。

答案:21若利用快速排序算法进行从小到大排序，下列选项中，不可能是经过两次选择分界元素并确定其最终位置后的排序结果的是（）。

答案:3,2,5,4,7,6,9若具有n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵一定为一个（）。

答案:对称矩阵若具有n个结点的二叉树采用二叉链表存储结构，则该链表中有（）个指针域。

答案:2*n若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是（）。

答案:69若二叉树的前序序列与后序序列的次序正好相反，则该二叉树一定是（）的二叉树。

答案:其分支结点的度都为1若一个非连通的无向图最多有28条边，则该无向图至少有（）个顶点。

答案:9给出一组关键字序列{12,2,16,30,8,28,4,10,20,6,18}，当用快速排序（选第一个记录为基准点进行划分，采用课堂中描述的“快速排序”算法）从小到大进行排序第一趟结束时的序列为（）。

答案:4，2，6，10，8，12，28，30，20，16，18线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O(n)（）

答案:对线性表中的插入、删除操作，在链式存储方式下，若要在某个结点后插入和删除一个结点，其时间复杂度都是O(1)。（）

答案:对线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（）。

答案:(n-1)/2用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法。

答案:队列用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为（）。

答案:SXSSXSXX栈和队都是（）

答案:限制存取点的线性结构栈R,从顶到底:{2,4,6,8,10},逐个取出放入队列Q中，再从Q中逐个取出放入R中，问现在栈R中从顶到底的顺序为（）。

答案:{10,8,6,4,2}某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

答案:仅有尾指针的单循环链表有向图G用邻接矩阵存储，其第i行的所有非无穷大元素个数等于顶点i的出度（）。

答案:对有下面的程序段：chara[3],b[]="China";a=b;printf("%s",a);则（）。

答案:编译出错有8个顶点的无向图最多有（）条边。

答案:28有11个叶结点的哈夫曼树共有（）个结点。

答案:21数据的存储结构通常有（）。

答案:顺序存储结构、链式存储结构、索引结构和散列结构折半查找过程可以利用一棵称之为“判定树”的二叉树来描述。在长度为12的序列中（假如第一个元素在序列中的位置为0）进行折半查找，对应判定树的根结点右孩子的值（即：某元素在序列中的位置）是（）。

答案:8快速排序在平均情况下的时间复杂度为（）。

答案:.O(nlogn)当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]中时，数组中第i个结点的左孩子为（）。

答案:无法确定度为k的树中，第i层最多有（）个结点（i≥1）。（2的幂指数可表示为形如2^(n+1)形式）

答案:k^(i-1)已知某有向图G=(V,E)，其中V={v1,v2,v3,v4,v5,v6}，E={,,,,,,,}，G的拓扑序列是（）。

答案:v3v1v4v5v2v6已知序列25,13,10,12,9是大顶堆，在序列尾部插入新元素18，将其再调整为大顶堆。调整过程中元素之间进行的比较次数是（）。

答案:2已知二叉树的前序遍历序列为ABDCEFG,中序遍历序列是DBCAFEG,则其后序遍历序列为（）。

答案:DCBFGEA已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（）。

答案:-+A*BC/DE已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素，则关键字比较次数最多为（）。

答案:5己知循环队列存储在一维数组A[0-n-1]中，且队列非空时front和rear分别指向队头元素和队尾元索。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（）。

答案:0,n-1将森林F转换为对应的二叉树T，F中叶结点的个数等于（）。

答案:T中左孩子指针为空的结点个数将数据元素2,4,6,8,10,12,14,16,18,20依次存放于一个一维数组中，然后采用折半查找方法查找元素12，被比较过的数组元素的下标依次为（）。

答案:4,7,5对序列(49,38,65,97,76,13,47,50)采用折半插入排序法进行排序，若把第7个元素47插入到已排序序列中，为寻找插入的合适位置需要进行（）次元素间的比较。

答案:3对含有n条边的无向图而言，其邻接表中边数为（）。

答案:2n对具有n个结点的完全二叉树按照层次从上到下，每一层从左到右的次序对所有结点进行编号，编号为i的结点的双亲结点的编号为（）。（从1开始编号，用[x]表示对x向下取整）

答案:[i/2]对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。

答案:25对于含有n个顶点e条边的无向连通图，利用Kruskal算法生成最小生成树，其时间复杂度为（）。

答案:O(elog2e)对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）8447251521（2）1547258421（3）1521258447（4）1521254784则采用的排序是（）。

答案:选择对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。

答案:（N+1）/2如果n个顶点的图是一个环，则它有（）棵生成树。

答案:n在非空双向循环链表中由q所指的那个链结点前面插入一个由p所指的链结点的动作所对应的语句依次为：p->rlink=q;p->llink=q->llink;q->llink=p;（）。(此处为一条赋值语句)

答案:p->llink->rlink=p;在有序表(k1,k2,...,k99)中采用折半查找方法查找99次，其中至少有一个元素被比较了99次，该元素是（）。

答案:k50在二叉查找树中进行查找的效率与（）有关。

答案:二叉查找树的深度在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是（）。

答案:82在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动（）个元素。

答案:n-i+1在一个图中，所有顶点的度数之和等于图的边数的（）倍。

答案:2在一个单向循环链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（）个指针域的值。

答案:2在一个具有n个链结点的线性链表中查找某一个链结点，若查找成功，需要平均比较（）个链结点。

答案:(n+1)/2在一个以h为头节点的单循环链表中，p指针指向链尾节点的条件是（）。

答案:p->next==h图的深度优先遍历类似于二叉树的（）。

答案:前序遍历图中顶点的度是指依附于该顶点的边的数目，有向图中的顶点还有出度和入度之分。在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的度（）。

答案:对函数squeez(chars[],charc)的功能是删除字符串s中所出现的与变量c相同的字符。补全下面程序，请选择（）。voidsqueez(chars[],charc){inti,j;for(i=j=0;s[i]!=‘\0’;i++)if(s[i]!=c)______;s[j]=‘\0’;}

答案:s[j++]=s[i]函数index(chars[],chart[])检查字符串s中是否包含字符串t，若包含，则返回t在s中的开始位置(下标值)，否则返回-1。补全下面程序请选择（）。intindex(chars[],chart[]){inti,j,k;for(i=0;s[i]!=‘\0’;i++){for(j=i,k=0;t[k]!=‘\0’&&s[j]==t[k];j++,k++);if(_______)returni;}return-1;}

答案:t[k]==‘\0’任何一个无向连通图的最小生成树（）。

答案:一棵或多棵以下给字符数组str定义和赋值正确的是（）。

答案:charstr[]="China";以下正确的说明语句是（）。

答案:inta[5],*num[5]={&a[0],&a[1],&a[2],&a[3],&a[4]};以下与int*q[5];等价的定义语句是（）。

答案:int*(q[5]);为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。

答案:队列为实现快速排序算法，待排序序列宜采用的存储方式是（）。

答案:顺序存储中缀表达式A-(B+C/D)×E的后缀形式是（）。

答案:ABCD/+E×-中缀表达式3+x*(2.4/5-6)所对应的后缀表达式为（）。

答案:3x2.45/6-*+下面能正确进行字符串赋值，并且能确保字符串以’\0’结尾的操作是（）。

答案:char*s;s="ABCDE";下面程序段的运行结果是（B）。charc[]="\t\v\\\0will\n";printf("%d",strlen（）);

答案:9下面的函数invert的功能是将一个字符串的内容颠倒过来。补全下面函数请选择（）。voidinvert(charstr[]){inti,j,k;for(i=0,j=strlen(str)-1;i答案:i++,j—下面有关本节图的遍历算法的描述中，正确的是（）。

答案:广度优先遍历算法要利用一个队列数据结构来保证顶点的访问顺序下面有关本节图的遍历算法应用的描述中，正确的是（）。

答案:应用代码实现中采用是邻接表来存储图数据的下面关于线性