雨课堂学堂在线学堂云《数据结构（江西师范大学）》单元测试考核答案

数据结构第1题计算机算法指的是（）A计算机程序B解决问题的有限运算序列C排序方法D检索方法第2题下面程序段的算法复杂度是（）123min=A[0];for(i=1;i<n;i++)if(min>A[i])min=A[i];其中n为正整数A𝑂(𝑛2)B𝑂(𝑛)C𝑂(𝑙𝑜𝑔2𝑛)D𝑂(𝑛3)第3题在数据结构中，数据的（）的结构是与计算机无关的。A物理B存储C逻辑D逻辑和存储第4题数据的最小单位是（）A数据项B数据元素C结点D记录第5题若某算法的时间复杂度为O(n^2)，则表明该算法的（）。A执行时间与n^2成正比B问题规模是n^2C问题规模与n^2成正比D执行时间等于n^2第6题下列函数中时间复杂度是O(n)的是（）。A𝑇(𝑛)=8000𝑙𝑜𝑔2𝑛B𝑇(𝑛)=500𝑛C𝑇(𝑛)=𝑛𝑙𝑜𝑔2𝑛+500𝑛D𝑇(𝑛)=15𝑛2第7题下面代码段的时间复杂度为（）。1234{inti=1;while(i<=n)i=i*2;}A𝑂(𝑛)B𝑂(𝑙𝑜𝑔2𝑛)C𝑂(√𝑛)D𝑂(𝑛2)第8题下面代码段的时间复杂度为（）。1234567{inti=0,s=0;while(i<n){s=s+a[i];i=i+3;}}A𝑂(𝑛)B𝑂(𝑛3)C𝑂(𝑙𝑜𝑔2𝑛)D𝑂(1)第9题算法的时间复杂度取决于（）。A问题的规模B待处理数据的初态C实现算法所使用的的语言D数据采用的存储结构第10题下面代码段的时间复杂度为（）。123456x=100;y=100;while(y>0)if(x>100){x=x-10;y--;}elsex++;A𝑂(𝑛)B𝑂(1)C𝑂(√𝑛)D𝑂(𝑛2)第11题如下程序段中，语句x=x+1执行的语句频度为（）。12for(i=1;i<=n-1;i++)for(j=i+1;j<=n;j++)x=x+1;A𝑛×𝑛B𝑛×(𝑛−1)C𝑛×(𝑛−1)2D𝑛×(𝑛+1)2第1题对于线性表，下列说法正确的是（）A除第一个元素与最后一个元素，其他每个元素有且仅有一个直接前驱和一个直接后继B每个元素有且仅有一个直接前驱和一个直接后继C线性表不允许为空D表中元素必须是有序的第2题线性表的顺序存储最适合于实现（）运算。A将x插入第i个位置B删除第i个位置元素C取第i个位置元素D查找值为x第3题在长度为n的顺序表中，查找第i个位置的数据元素的时间复杂度为（）A𝑂(𝑛2)B𝑂(𝑛)C𝑂(1)D𝑂(𝑙𝑜𝑔2𝑛)第4题在长度为n的顺序表的运算中，算法的时间复杂度是O(1)的操作是（）。A求第i个位置的元素的直接前驱（1≤i<n）B删除第i个位置上的元素（0≤i<n）C在第i个位置上插入一个新元素（0≤i≤n）D以上都不对第5题将长度为m的单链表（A）链接在长度为n的单链表（B）之后的算法时间复杂度为（）。A𝑂(1)B𝑂(𝑚+𝑛)C𝑂(𝑚)D𝑂(𝑛)第6题在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）。A𝑂(1)B𝑂(𝑛)C𝑂(𝑛2)D𝑂(𝑙𝑜𝑔2)第7题线性表采用顺序存储结构进行存储，取第i个位置元素的时间与i值的大小有关。第8题顺序表的插入、删除总是伴随着大量数据的移动。第9题对于使用带头结点的单链表，若头指针为head，判定该表为空的条件是（）。Ahead!=NULLBhead->next==NULLChead->next==headDhead==NULL第10题已知指针p指向在一个单链表中的某个结点，若在该结点之后插入指针s指向的结点，则需执行（）。As->next=p->next;p->next=s;Bp->next=s;s->next=p;Cs->next=p->next;s=p;Ds->next=p->next;s=p->next;第11题在单链表head中，指针p所指结点是线性表中最后一个元素的条件是（）。Ap==NULLBp->next==NULLCp!=NULLDp->next!=NULL第12题在循环单链表head中，指针p所指结点是线性表中最后一个元素的条件是（）Ap==headBp->next==NULLCp->next==headDp==NULL第13题与单链表相比，双链表的优点之一是()。A更节约存储空间B能够方便的访问某结点的前驱结点C可以进行随机访问D插入、删除操作更简单章节测试第1题若元素A、B、C、D、E依次进栈后，栈顶元素是（）。AEBDCBDC第2题元素A、B、C依次进栈，中间允许出栈，若出栈序列为BCA，经过栈的操作是（）。ApushpushpushpoppoppopBpushpushpoppushpoppopCpushpoppushpoppushpopDpushpoppushpushpoppop第3题元素A、B、C依次进栈，中间允许出栈，则不可能的出栈序列是（）。ACABBBCACBACDABC第4题表达式5*6-7*8的后缀表达式是（）。A5678**-B56*78*-C-**5678D5678*-*第5题若一个栈用数组data[0..n-1]存储，初始栈顶指针top为-1，则以下元素x进入栈的正确操作是()。Adata[top]=x;top++;Bdata[top]=x;top--;Ctop--;data[top]=x;Dtop++;data[top]=x;第6题若一个栈用数组data[0..n-1]存储，初始栈顶指针top为0，则以下元素x进入栈的正确操作是()。Atop++;data[top]=x;Btop--;data[top]=x;Cdata[top]=x;top++;Ddata[top]=x;top--;第7题判定一个顺序栈st（数组大小为MaxSize，初始st.top==0）栈满的条件是（）。Ast.top==MaxSizeBst.top==0Cst.top==-1Dst.top==MaxSize-1第8题若不带头结点的链栈其栈顶指针为top，则插入一个s指针所指向的结点时，应进行如下（）操作。As->next=top;top=s;Bs->next=top->next;top->next=s;Cs->next=top;top->next=s;Dtop>next=s;第9题顺序循环队列qu的队满条件（front队首指针指向队首元素，rear队尾指针指向队尾元素的后一个位置，采用浪费一个空间的方式进行存储，队列元素最大个数为MaxSize）是（）。Aqu.rear==qu.frontB(qu.rear+1)%MaxSize==qu.front+1C(qu.rear+1)%MaxSize==qu.frontD(qu.rear+1)%MaxSize==(qu.front+1)%Maxsize第10题假设用不带头结点的单链表表示队列，front和rear分别指向队头和队尾，则判断队空的条件是（）。Afront!==NULLBfront==NULLCrear!==NULLDfront==rear第11题为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中读取数据。该缓冲区最适合采用的逻辑结构是（）。A顺序表B栈C链式表D队列第12题循环队列解决了溢出问题，不会出现溢出现象。第13题在具有n个元素的非空顺序队列中，插入或者删除一个元素的操作时间复杂度是O(n)。章节测试第1题两个字符串相等的充分必要条件是（）。A两个字符串的长度相等且对应位置上的字符也相等B两个字符串中对应位置上的字符相等C两个字符串的长度相等D以上说法都不对第2题设有两个串S和T，其中T是S的子串，求T在S中首次出现的位置的算法称为（）A取子串B串连接C串的模式匹配D串插入第3题下面关于串的叙述中，不正确的是（）。A串是一种特殊的线性表B串中元素只能是字母C空串就是空白串D串的长度必须大于零第4题以下是采用压缩存储的一个链串的节点类型定义：#defineNodeSize8typedefstructnode{chardata[NodeSize];structnode*next;}LinkStrNode;如果每个字符占1个字节，指针占2个字节，该链串的存储密度为（）。A1/4B1/3C2/3D4/5第5题串只可以采用顺序存储，不可以采用链式存储。第6题若串S=“software”，其子串个数为（）。A9B8C37D36第7题串是一种特殊的线性表，其特殊性体现在（）A可以顺序存储B可以链式存储C数据元素可以是多个字符D数据元素是一个字符第8题空串是任意字符串的子串。第9题空串就是空白串。第10题空串是不含字符的串，长度为0。第11题在字符{A,C,G,T}组成的DNA序列中，A和T、C和G是互补对。判断一个DNA序列中是否存在互补回文串（例如，ATCATGAT的补串是TAGTACTA，与原串形成互补回文串）。则下面DNA序列中存在互补回文串的是（）AGTACGTACBAGCTAGCTCAATTAATTDCTGATCAG第12题intf(chars[])函数判断字符串s是否是回文，是回文则返回1，否则返回0；如f("abba")返回1，f("abcba")返回1f("abab")返回0；对于（1），下列选项正确的是（）intf(chars[]){inti=0,j=0;while(s[j])j++;for(j--;i<j&&s[i]==s[j];i++,j--);return_______(1)_______;}Ai>jBi==jCs[i]==s[j]Ds[i]=s[j]章节测试第1题设有10×5的数组A，其每个元素占2个字节，按行优先顺序存储，若已知A[3][4]在内存中的地址是1038，则A[6][0]的地址是（）。A1060B1030C1098D1068第2题设有10×6的数组A，数组下标从0,0开始，其每个元素占2个字节，按列优先顺序存储，若已知A[3][4]在内存中的地址是1086，则A[4][5]的地址是（）A1296B1140C1108D1054第3题将10×5的二维数组A按照行优先顺序存储到一维数组B中，则B[35]中存储的二维数组元素是()。AA[6][0]BA[7][0]CA[7][1]DA[6][1]第4题对特殊矩阵采用压缩存储的目的主要是（）。A对矩阵元素的存储变得简单B表达变得简单C减少不必要的存储空间D去掉矩阵中的多余元素第5题N*N的三对角矩阵，需要保存的数据元素的个数是()。A3n-2B3n-1C3nD3n+1第6题某稀疏矩阵A采用三元组顺序表作为存储结构，对于矩阵元素的赋值运算A[i][j]=x，不可能的操作是（）。A修改某个三元组的元素值B插入一个新的三元组C删除一个三元组D修改某个三元组的行号或列号第7题使用三元组来保存稀疏矩阵中的非零元素，三元组不包括非零元素的()A行号B元素值C列号D个数第8题以下物理结构中，不能够对数据元素进行随机访问的是（）A三对角矩阵的压缩存储B三元组顺序表C数组的顺序存储D对称矩阵的压缩存储第9题对稀疏矩阵进行压缩存储方法一般有两种，分别为三元组顺序表和十字链表第10题数组是一种定长的线性表，数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作。第11题数组是一种非线性结构，除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等操作。第12题使用三元组顺序表或十字链表作为稀疏矩阵中的物理结构，对元素可以进行随机访问。章节测试第1题一棵深度为6的满二叉树有（）个分支结点。A31B32C63D64第2题在一棵二叉树中，度为零的结点的个数为N0，度为2的结点的个数为N2,则有N0等于（）A无法确定BN2+1CN2-1DN2第3题若在一棵度为3的树中，有3个度为3的结点，2个度为2的结点，2个度为1的结点，该树中叶子结点的个数为（）A6B7C9D16第4题若某棵二叉树的后序遍历序列为ABCDEFG，则其根结点值是（）AABGCBD不能确定第5题若某棵二叉树的中序根遍历序列为ABCDEFG，则其根结点值是（）AABGCBD无法确定第6题若知道一棵二叉树的先序和中序遍历序列，便可以唯一确定该二叉树。第7题给定权值总数有n个，其哈夫曼树的结点总数是2n-1个。第8题设有一棵哈夫曼树的结点总数为41，则该哈夫曼树共有（）个叶子结点。A20B21C22D30第9题树中某结点的第3个孩子，转换成二叉树后，应该是（）A该结点的右孩子B该结点的左孩子的右孩子C该结点的左孩子的右孩子的右孩子D该结点的右孩子的右孩子的右孩子第10题引入线索二叉树的目的是（）A为了能在二叉树中方便的进行插入与删除B加快查找结点的前驱或后继的速度C为了能方便的找到双亲D使二叉树的遍历结果唯一第11题若结点A是中序线索二叉树中一个有右孩子的结点，则A的后继为()AA的左子树中最右的结点BA的左子树中最右的叶结点CA的右子树中最左的结点DA的右子树中最右的结点第12题根据使用频率为4个字符设计的哈夫曼编码不可能是（）A00,10,01,11B111,110,10,0C11,10,1,0D001,000,01,1第13题对应于一组权值构造出的哈夫曼树可能不是唯一的。章节测试第1题图的深度优先遍历类似于二叉树的（）A先序遍历B中序遍历C后序遍历D层次遍历第2题如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所有顶点，则该图一定是()A完全图B有回路C连通图D有回路的连通图第3题在图的广度优先遍历算法中用到一个队列，每个顶点最多进队（）次A1B2C0D不确定第4题关于图的邻接矩阵，下列哪个结论是正确的（）A有向图的邻接矩阵一定是不对称的B有向图的邻接矩阵可以是对称的，也可以是不对称的C无向图的邻接矩阵一定不是对称的。D无向图的邻接矩阵可以是不对称的，也可以是对称的。第5题对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，所有顶点邻接表的边结点总数为（）Ae/2BeC2eDn+e第6题在图的表示法中，表示形式唯一的是邻接矩阵。第7题迪杰斯特拉算法求最短路径时，是按照路径长度递增的顺序求解的。第8题用Kruskal算法，求下图的最小生成树时，依次得到的树边为（）ABE1、ED3、BA4、AF2、AC6BBE1、AF2、ED3、BA4、AC6CAB4、BE1、ED3、AF2、AC6DBE1、AF2、BA4、ED3、AC6第9题从B点出发用prim算法，求下图的最小生成树时，依次得到的树边为（）。ABE1、AF2、ED3、BA4、AC6BBE1、ED3、BA4、AF2、AC6CAB4、BE1、ED3、AF2、AC6DBE1、AF2、BA4、ED3、AC6第10题设无向图G=(V,E)和G'=(V',E')，如果G'是G的生成树，则下面的说法中错误的是（）AG'为G的子图BG'为G的连通分量CG'为G的极小连通子图且V=V'DG'是G的一个无环子图第11题在用Kruskal算法求解带权连通图的最小生成树时，选择权值最小的边的原则是该边不能在图中构成回路。第12题在一个带权连通图G中，权值最小的边一定包含在G的（）生成树中。章节测试第1题采用顺序查找法查找一个长度为n的线性表，则查找成功（假设查找概率相等）时，平均比较次数为（）。An/2B(n-1)/2C(n+1)/2Dn第2题对线性表进行二分检索时，线性表必须采用（）A链式存储B链式存储，且结点之间是有序排列的C顺序存储，不要求结点之间可是有序排列的D顺序存储，且结点之间是有序排列的。第3题有序数组a[11]，下标从0开始，使用二分检索进行查找，则查找到a[7]的查找路径（下标序列）为（）A5，7B5，8，7C5，8，6，7D1，4，7第4题设有一组关键字为{29，40，23，1，92，21，88，14，55，11}的记录，若用拉链地址法构造散列表，散列函数为H（key）=keyMOD13，散列地址为1的链中有（）个记录。A2B3C4D4第5题顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为（）次AnBn-1Cn/2D(n+1)/2第6题用二分（对半）检索法，查找表的元素的速度一定比用顺序法快。第7题若将100个元素散列到100000个单元的哈希表中，则一定不会产生冲突。第8题顺序查找n个元素的顺序表，当使用监视哨时，若查找失败，则比较关键字的次数为n次。第9题对二叉排序树进行中序遍历，得到的序列一定是有序的。第10题在二叉排序树中插入一个结点，该结点一定在叶子上。第11题设散列表长为13，哈希函数是H(key)=key%11，表中已有数据的关键字为26，5，17，20共4个，现要将关键字为60的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()A9B8C7D1第12题设散列表长为13，哈希函数是H(key)=key%11，表中已有数据的关键字为26，5，17，20共4个，现要将关键字为60的结点加到表中，用线性探测再散列法解决冲突，则放入的位置是()A2B3C7D8章节测试第1题假定在待排序的数据表中，存在多个具有相同键值的记录，若经过排序后，这些记录的相对次序仍然保持不变。则该排序算法是稳定的第2题冒泡排序算法的排序趟数与序列的初始状态有关。第3题使用冒泡排序方法对关键字序列（25，54，47，27，68，20）