知道智慧树数据结构（山东联盟-临沂大学）满分测试答案

第一章测试1【单选题】(2分)下列叙述中正确的是（）A.算法设计只需考虑得到计算结果B.所谓算法就是计算方法C.程序可以作为算法的一种描述方法D.算法设计可以忽略算法的运算时间2【判断题】(1分)数据的最小单位是数据项（）A.对B.错3【单选题】(2分)在数据结构中，从逻辑上可以把数据结构分成（）A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4【单选题】(2分)与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）A.存储结构B.存储实现C.运算实现D.逻辑结构5【单选题】(2分)以下说法正确的是（）A.一些表面上很不相同的数据可以有相同的逻辑结构B.数据项是数据的基本单位C.数据结构是带有结构的各数据项的集合D.数据元素是数据的最小单位6【单选题】(2分)下面代码段的时间复杂度是（）。

s=0;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

s+=B[i][j];

sum=s;A.O(logn)B.O(n)C.O(n²)D.O(1)7【单选题】(2分)下面代码段的时间复杂度是（）。

x=0;

for(i=1;i<n;i++)

for(j=1;j<=n-i;j++)

x++;A.O(n²)B.O(n)C.O(logn)D.O(n³)8【判断题】(1分)NlogN²和NlogN具有相同的增长速度。（）A.错B.对9【判断题】(1分)N²logN²和NlogN²具有相同的增长速度。（）A.对B.错10【判断题】(1分)斐波那契数列FN的定义为：F0=0，F1=1，FN=FN−1+FN−2，N=2,3,...。用递归函数计算FN的时间复杂度是O(N!)。A.对B.错第二章测试1【单选题】(2分)下面关于线性表的叙述中，的是哪一个（）A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用链接存储，便于插入和删除操作C.线性表采用链接存储，不必占用一片连续的存储单元D.线性表采用顺序存储，便于进行插入和删除操作2【单选题】(2分)在具有n个结点的单链表中，实现下列哪个操作，其算法的时间复杂度是O(n)？A.删除开始结点B.遍历链表和求链表的第i个结点C.在地址为p的结点之后插入一个结点D.删除地址为p的结点的后继结点3【单选题】(2分)链表不具有的特点是（）A.所需空间与线性表长度成正比B.插入删除不需要移动元素C.可随机访问任一个元素D.不必事先估计存储空间4【单选题】(2分)带头结点的单链表L为空的条件是（）A.L==NULL;B.L->next->next==NULL;C.L->next==L;D.L->next==NULL;5【单选题】(2分)在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（）A.s->next=p->next;

p->next=s;B.p->next=s->next;

p->next=s;C.p->next=s;

s->next=p->next;D.p->next=s;

p->next=s->next;6【单选题】(2分)在长度为n的顺序表的表尾插入一个新元素的时间复杂度为（）A.O(n²)B.O(n)C.O(1)D.O(logn)7【单选题】(2分)单链表中，增加头结点的目的是为了()A.说明单链表是线性表的链式存储实现B.使单链表至少有一个结点C.标示表结点中首结点的位置D.方便运算的实现8【判断题】(1分)线性表的逻辑顺序与物理顺序总是一致的（）A.对B.错9【判断题】(1分)取线性表的第i个元素的时间同i的大小有关()A.错B.对10【判断题】(1分)线性表的长度是线性表所占用的存储空间的大小（）A.对B.错第三章测试1【单选题】(2分)设有六列火车，编号为1，2，3，4，5，6，顺序开进一个栈式结构的站台，问下列输出序列中，哪个是不可能出现的（）。A.3,1,2,6,5,4B.1,2,3,4,5,6C.3,2,1,6,5,4D.6,5,4,3,2,12【判断题】(1分)栈和队列都是运算受限的线性表。（）A.错B.对3【判断题】(1分)当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是top==1。（）A.对B.错4【单选题】(2分)元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（）。A.4B.5C.6D.35【单选题】(2分)已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（）。A.0,0B.n-1,n-1C.0,n-1D.n-1,06【单选题】(2分)数组Q[n]用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素个数的公式为（）。A.(n+r-f)%nB.n+r-fC.r-fD.(n+f-r)%n7【单选题】(2分)若一个栈以向量V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是（）。A.top++;V[top]=x;B.V[top]=x;top++;C.V[top]=x;top--;D.top--;V[top]=x;8【单选题】(2分)设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。A.6B.2C.4D.39【单选题】(2分)循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（）。A.队空：end1==(end2+1)；队满：end2==(end1+1)mod(M-1)B.队空：end1==end2；队满：end2==(end1+1)mod(M-1)C.队空：end2==(end1+1)modM；队满：end1==(end2+1)modMD.队空：end1==end2；队满：end1==(end2+1)modM10【单选题】(2分)用链接方式存储的队列，在进行删除运算时（）。A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改第四章测试1【单选题】(2分)由3个结点可以构造出多少种不同的树（）A.2B.3C.4D.52【单选题】(2分)一棵树高为K的完全二叉树至少有()个结点A.B.C.D.3【单选题】(2分)将含有83个结点的完全二叉树从根结点开始编号，根为1号，按从上到下、从左到右顺序结点编号，那么编号为41的双亲结点编号为（）A.20B.40C.42D.214【单选题】(2分)对于有n个结点的二叉树,其高度为（）A.B.不确定C.D.5【单选题】(2分)给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3、1、7、5、6、2、4，则其遍历方式是（）A.NRLB.LRNC.RNLD.RLN6【单选题】(2分)如果T2是由有序树T转化而来的二叉树，那么T中结点的先序就是T2中结点的（）A.后序B.中序C.层次D.先序7【单选题】(2分)下面几个符号串编码集合中，不是前缀编码的是（）A.{00,010,0110,1000}B.{11,10,001,101,0001}C.{0,10,110,1111}D.{b,c,aa,ac,aba,abb,abc}8【单选题】(2分)二叉树先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是（）A.HB.FC.ED.G9【单选题】(2分)以下说法的是（）A.若初始森林中共有N棵二叉树，最终求得的哈夫曼树中共有2N-1个结点B.一般在哈夫曼树中，权值越大的叶子离根结点越近C.若初始森林中共有N棵二叉树，进行2N-1次合并后才能剩下最终的哈夫曼树D.哈夫曼树中没有度数为1的分支结点10【判断题】(1分)若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树（）A.对B.错11【判断题】(1分)若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反（）A.对B.错12【判断题】(1分)完全二叉树中，若一个结点没有左孩子，则它必是树叶。（）A.错B.对13【单选题】(2分)利用二叉链表存储树，则根结点的右指针是（）A.非空B.指向最左孩子C.指向最右孩子D.空第五章测试1【判断题】(1分)用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。（）A.对B.错2【判断题】(1分)有向图的邻接矩阵是对称的。（）A.错B.对3【单选题】(2分)设无向图的顶点个数为n，则该图最多有（）条边。A.n-1B.n(n+1)/2C.n(n-1)/2D.04【单选题】(2分)下列关于无向连通图特征的叙述中，正确的是：（）

1.所有顶点的度之和为偶数

2.边数大于顶点个数减1

3.至少有一个顶点的度为1A.1和3B.1和2C.只有1D.只有25【单选题】(2分)对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，所有顶点邻接表的边结点总数为（）。A.e/2B.n+eC.eD.2e6【单选题】(2分)给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的顶点序列为()。A.V1,V5,V4,V7,V6,V3,V2B.V1,V5,V6,V4,V7,V2,V3C.V1,V5,V4,V7,V6,V2,V3D.V1,V2,V3,V4,V7,V6,V57【单选题】(2分)在图中自a点开始进行广度优先搜索算法可能得到的结果为（）。A.a,e,d,f,c,bB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,b,e,c,d,f8【单选题】(2分)任何一个带权无向连通图的最小生成树（）。A.是不唯一的B.是唯一的C.有可能不存在D.有可能不唯一9【单选题】(2分)对于下列的网，使用克鲁斯卡尔算法求最小生成树，依次得到的边集是（）。A.{（A，D），（B，C），（E，A），（C，E）}B.{（A，D），（A，B），（A，E），（E，C）}C.{（A，D），（D，E），（E，C），（C，B）}D.{（A，D），（D，E），（B，C），（C，E）}10【单选题】(2分)使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其它各顶点的最短路径，依次得到的各最短路径的目标顶点是（）。A.5,2,6,3,4B.5,2,4,3,6C.5,2,3,6,4D.5,2,3,4,6第六章测试1【判断题】(1分)二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值。（）A.错B.对2【判断题】(1分)查找相同结点的效率折半查找总比顺序查找高。（）A.错B.对3【判断题】(1分)在查找树（二叉排序树）中插入一个新结点，总是插入到叶结点下面。（）A.对B.错4【判断题】(1分)采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（）A.对B.错5【判断题】(1分)对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。（）A.对B.错6【单选题】(2分)已知一个长度为16的顺序表L,其元素按关键字有序排列,若采用折半查找法查找一个不存在的元素,则比较次数最多的是（）。A.5B.4C.7D.67【单选题】(2分)对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是(）。A.12,25,71,68,33,34B.95,22,91,24,94,71C.92,20,91,34,88,35D.21,89,77,29,36,388【单选题】(2分)在任意一棵非空二叉排序树T1中，删除某结点v之后形成二叉排序树T2，再将v插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是（）。

I.若v是T1的叶结点，则T1与T3不同

II.若v是T1的叶结点，则T1与T3相同

III.若v不是T1的叶结点，则T1与T3不同

IV.若v不是T1的叶结点，则T1与T3相同A.仅I、IIIB.仅I、IVC.仅II、IIID.仅II、IV9【单选题】(2分)对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则哈希地址为0的元素有（）个A.1B.4C.3D.210【单选题】(2分)适用于折半查找的查找表存储方式及元素排列要求为()A.链接方式存储，元素无序B.顺序方式存储，元素无序C.链接方式存储，元素有序D.顺序方式存储，元素有序11【单选题】(2分)有一个有序表为｛1,3,9,12,32,41,45,62,75,77,82,95,100｝，当用折半查找方法查找值82的结点时，（）次比较后查找成功。A.2B.4C.8D.112【单选题】(2分)将{5,2,7,3,4,1,6}依次插入初始为空的二叉排序树。则该树的后序遍历结果是:（）A.1,4,2,6,3,7,5B.1,2,3,4,6,7,5C.1,4,3,2,6,7,5D.5,4,3,7,6,2,113【单选题】(2分)有数据{53，30，37，12，45，24，96}，从空二叉树开始逐步插入数据形成二叉排序树，若希望高度最小，应选择下列（）的序列输入。A.12，24，30，37，45，53，96B.37，24，12，30，53，45，96C.30，24，12，37，45，96，53D.45，24，53，12，37，96，3014【单选题】(2分)下面关于哈希查找的说法，不正确的是（）A.用链地址法处理冲突，不会引起二次聚集现象B.采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的C.用链地址法处理冲突，适合表长不确定的情况D.采用链地址法处理冲突时，查找每个元素的时间是相同的第七章测试1【判断题】(1分)快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。A.错B.对2【判断题】(1分)堆排序是稳定的排序方法。A.错B.对3【判断题】(1分)在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n)。A.对B.错4【判断题】(1分)在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。A.对B.错5【单选题】(2分)比较次数与排序的初始状态