数据结构学习通超星期末考试答案章节答案2024年

数据结构学习通超星期末考试章节答案2024年在图结构中，数据之间是一对多的关系。

答案:错数据结构研究的是数据的表示和数据之间的关系。

答案:对在线性结构中，数据之间是1对1的关系

答案:对从存储结构上讲，数据有顺序结构、链接结构、索引结构和散列结构四种。

答案:对从逻辑上讲，数据有线性、树和图（非线性）结构。

答案:对在数据结构中，数据的逻辑结构可以分成（）

答案:线性结构和非线性结构数据结构是（）

答案:相互之间存在一种或多种特定关系的数据元素的集合数据元素及其关系在计算机存储器内的表示，称为数据的(

)

答案:存储结构将下列各式按增长率由小至大的顺序正确排列(

)2^100，logn,2^n,n^n

答案:2^100，logn,2^n,n^n若算法中语句的最大频度为T(n)=2006n+6nlogn+29log2n,则其时间复杂度为（）

答案:O(nlogn)以下代码的时间复杂度为（

）#include"stdio.h"voidmain(){

inti;

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

printf("*");}

答案:O(1)以下代码的时间复杂度为（

）For(i=1;i<=n;i++)For(j=1;j<=n;j++)

x=x+1；

答案:O(n²）算法分析的两个主要方面是：

答案:空间复杂性和时间复杂性在长度为n的顺序表上进行插入运算，在第i（假设合法）个位置上插入一个数据元素时，需要向后方向平移（

）个数据元素。

答案:n–i+1在长度为n的顺序表上进行插入运算，有（

）个可插入的位置

答案:n+1顺序表中逻辑上相邻的元素存储位置(

)相邻

答案:一定一个顺序表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是(

)

答案:108

向一个有200个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（

）个元素。

答案:100在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是(

)

答案:p->next=p->next->next;已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为(

)

答案:q->next=s->next；s->next=p；求单链表中当前结点的后继和前驱的时间复杂度分别是（

）

答案:O（1）和O（n）某带头结点的单链表的头指针为head，判定该链表为非空的条件是(

)

答案:head->next!=NULL将长度为n的单链表链接在长度为m的单链表之前的算法的时间复杂度为（

）

答案:O（n）初始化链表的意思是创建一个空链表。如果带头结点，则创建一个头结点，其指针域为空。

答案:对（

）是指向链表中第一个结点或头结点的指针（

）是在链表的第一个结点之前附设的一个结点，数据域不存储数据,指针域存储第一个结点的地址

答案:头指针;头结点在单链表H中查找x的命令如下：voidfindLnode(lnode*H,intx)

//查找数据{inti=0;

//i用来记录查找位置；flag标志用来记录是否找到。lnode*p;if(lnodeEmpty(H)){printf("是空表,没得查");return;}p=H->next;i=1;//p指向第一个结点while(p!=NULL)

{if(p->data==

){printf("%d排在第%d位\n",x,

);return;}p=p->next;i++;}printf("查无此数!");}

答案:x;i查找单链表第i位的结点数据命令如下：lnode*locateLnode(lnode*H,inti)

//查找第i位的结点数据，返回指向该结点的指针{lnode*p;intj;p=H;j=0;//p指向头结点while(p!=NULL){if(

)returnp;p=p->next;j++;}}

答案:j==i初始化单链表的命令如下：lnode*H;

//定义头指针

=(lnode*)malloc(sizeof(lnode));//创建头结点，让头指针指向头结点H->next=

;//链表初始化，头结点的下一个为空H->data=0;//头结点的数据域存放链表的元素个数。}

答案:H;NULL定义单链表的结点命令：typedefstructnode

//定义结点{intdata;

//数据

struct

*next;

//指针,保存下一个结点的地址}lnode;

//取别名

答案:node打印输出单链表的命令如下：voidprintLnode(lnode*H)//打印输出单链表.{lnode*p;if(lnodeEmpty(H))printf("链表为空表");else{

=H->next;

//p指向第一个结点while(

){printf("%d\t",p->

);p=p->

;}}printf("\n");}

答案:p;p!=NULL;data;next/star3/origin/dccdcb8205d688d66be15f04004a3329.png

答案:s->next=q->next;;q->next=s;/star3/origin/c8c5a5a6b1375826c994fc5e40465906.png

答案:p->next=q->next;;free(q在单链表中某结点后插入一个新结点，需要修改_______________个结点指针域的值。

答案:2在双向循环链表中插入一个新的结点时，应修改2个指针域的值。

答案:错在单循环链表中插入一个新的结点时，应修改2个指针域的值。

答案:对在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。

答案:对链表的每个结点中都恰好包含一个指针。

答案:错带头结点的单链表为空的条件是：head->next==NULL

答案:对带头结点的循环链表为空的条件是：head->next==head

答案:对/star3/origin/130f9577dd71a38cb2197ee2b2c2cf4d.png

答案:p->prior->next=p->next;;p->next->prior=p->prior;;free(p/star3/origin/34f2097472419cde32e61819d837a15a.png

答案:L->next==L/star3/origin/21a2a3ede6e2e208c8bab5ed7574a760.png

答案:s->prior=p->prior;;s->next=p;;p->prior->next=s;;p->prior=s;/star3/origin/0e667e1861919c1a22603ca83036fab1.png

答案:s->prior=p;;s->next=p->next;;p->next->prior=s;;p->next=s;单链表的插入算法要修改（

）个指针。

答案:2在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（）

答案:４个

假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（）

答案:head–>next==head非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（）

答案:rear->next==head对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为(

)

答案:用尾指针表示的单循环链表对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为()

答案:双向循环链表在带头结点的双向循环链表中删除一个新结点，需要修改的指针域数量是（）

答案:2个在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head,则(

)

答案:*P的直接后继是尾结点栈的存储方式既可是顺序方式，也可是链接方式。

答案:对设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，这四辆列车全进之后再开出车站的情况只有1种：即4，3，2，1。

答案:对栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

答案:对一个栈的输入序列是12345，进栈和出栈可以穿插进行，则栈的输出序列不可能是12345。

答案:错写出下列程序段的输出结果（栈的元素类型e为char）。voidmain(){StackS;charx,y;InitStack(S);x='c’;y='k’;Push(S,x);Push(S,'a’);

Push(S,y);Pop(S,&x);Push(S,'t’);Push(S,x);Pop(S,&x);Push(S,'s’);while(!StackEmpty(S)){

Pop(S,&y);printf(y);

};printf(x);}

答案:stack在做进栈运算时，应先判别栈是否栈(

)；在做退栈运算时，应先判别栈是否栈(

)。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为

(

)。

答案:满;空;n若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是(

)

答案:2，3，5，1，6，4上溢现象通常出现在（）

答案:顺序栈的入栈操作过程中设链式栈(带头结点)中结点的结构为（data,link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行操作（

）。

答案:s->link=top->link;

top->link=s;链栈与顺序栈相比，比较明显的优点是(

)

答案:不会出现上溢的情况栈的插入和删除操作在(

)进行。

答案:栈顶

设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。

答案:栈设链式栈（不带头结点）中结点的结构为（data,link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行操作（

）。

答案:x=top->data;

top=top->link;

/star3/origin/2bb03c3806f2b4e45defca9ac20100db.png

答案:p->next=S;;S=p;设top指向头结点，则（

）表示栈空

答案:top->next==NULL设top指向栈顶元素（无头结点），则（

）表示栈空

答案:top==NULL/star3/origin/b10e9f064763f87eaa3d5642e23a5cba.png

答案:p->data=x1;;p->next=top->next;;top->next=p;假设循环队列的元素存储空间大小为m，队头指针f指向队头元素，队尾指针r指向队尾元素的下一个位置，则在少用一个元素空间的前提下，表示“队满”的条件是(r+1)%m==f。

答案:对队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

答案:错在队列中，允许进行删除操作的一端称为队尾，允许进行插入操作的一端称为队头。

答案:错栈和队列的存储方式既可是顺序方式，也可是链接方式。

答案:对设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有①front=11，rear=19;

②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？

答案:8;32假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为______。

答案:10在具有n个单元的循环队列（牺牲一个存储单元）中，队满时共有（

）个元素。

答案:n-1队列的队尾位置通常是随着_________操作而变化的。

答案:入队假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为(

)

答案:(rear-length+m)％m已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为(

)

答案:16设循环队列的结构是

#defineMaxSize100

typedefintElemType;

typedefstruct{

ElemTypebase[MaxSize];

intfront,rear;

}

Queue;

若有一个Queue类型的队列Q，则判断队列满的条件应是语句（

）。

答案:Q.front==(Q.rear+1)%MaxSize;

写出下列程序段的输出结果（队列中的元素类型QElemType为char）。voidmain(){QueueQ;

InitQueue(Q);Charx=’e’;y=’c’;EnQueue(Q,’h’);

EnQueue(Q,’r’);

EnQueue(Q,y);

DeQueue(Q,&x);EnQueue(Q,x);

DeQueue(Q,&x);

EnQueue(Q,’a’);

while(!QueueEmpty(Q)){

DeQueue(Q,&y);printf(y);

};Printf(x);}

答案:char假设队列q中的元素为{2,4,5,7,8},其中“2”为队头元素。写出执行函数algo(&q)后的队列q={

}。注意大括号内的值使用逗号分隔，如：{2,4,5,7,8}voidalgo(Queue*Q){

StackS;

InitStack(&S);

while(!QueueEmpty(Q))

Push(&S,DeQueue(Q));

while(!StackEmpty(&S))

enQueue(Q,Pop(&S));}

答案:8,7,5,4,2Q、Q1和Q2都是队列结构，设队列Q=（1，0，-5，2，-4，-6，9），其中1为队头元素，写出执行f31(&Q,&Q1,&Q2)之后队列Q、Q1和Q2的状态；（注：lnitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入列、出队和判队空的操作）void

f31(Queue*Q,Queue*Q1,Queue*Q2){int

e;lnitQueue(Q1);lnitQueue(Q2);while(!QueueEmpty(Q)){e=DeQueue(Q);if(e>=0)EnQueue(Q1,e);

//正数和0入Q1elseEnQueue(Q2,e)//负数入Q2}}Q=()，为

队列Q1={

}Q2={

}

答案:空;1,0,2,9;-5,-4,-6假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。设m=40,rear=13,quelen=19,求队头元素的位置；

答案:34阅读算法f31,并回答下列问题：值用逗号分隔开来。（1）设队列Q=（1，3，5，2，4，6）。写出执行算法f31后的队列Q;（2）简述算法f31的功能。void

f31(Queue*Q){

DataType

e;

if(!QueueEmpty(Q)){

e=DeQueue(Q);

f31(Q);

EnQueue(Q,e);

}}(1)Q={

}

答案:6,4,2,5,3,1已知二维数组M5×6的每个元素占4个字节，已知Loc(m00)=2010，M共占（

）个字节？M的最后一个数组元素m[4][5]的存储地址是（

）以行为主和以列为主的顺序存储时，m[2][5]的存储地址分别是（

）和（

）

答案:120;2126;2078;2118二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为(

)

答案:1034二维数组A[20][10]采用列优先的存储方法，若每个元素占2个存储单元，且第1个元素的首地址为200，则元素A[8][9]的存储地址为(

)。

答案:576二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为(

)

答案:429

代码填空。/*顺序栈的创建及操作*/#include"stdio.h"#defineSIZE100typedefstruct{

//定义顺序栈结构intdata[SIZE];

//定义数组用来存放栈中的数据元素。inttop;

//栈顶指针，并不是一个真正的指针，只是一个整数下标，用来保存栈顶元素的下标。}stack;voidprintStack(stack*s)

//输出栈中所有元素。{inti;if(stackEmpty(s)){printf("栈空，没得输出\n");return;}printf("栈中元素有:");for(i=

;i>

;i--){printf("%d\t",s->data[

]);}printf("\n");}

答案:s->top;-1;i#include"stdio.h"#defineSIZE100typedefstruct{

//定义顺序栈结构intdata[SIZE];

//定义数组用来存放栈中的数据元素。inttop;

//栈顶指针，并不是一个真正的指针，只是一个整数下标，用来保存栈顶元素的下标。}stack;voidlengthStack(stack*s)//统计栈中元素个数{if(stackEmpty(s)){printf("栈空，没有元素\n");

;}printf("栈中元素个数为：%d\n",

);}

答案:return;s->top+1设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a68的地址为（

）。

答案:1055已知数组A［10］［10］为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［５］[６］对应的地址是_______

答案:1130假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为________。

答案:56设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a58的地址为（

）。

答案:1055三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的（

）下标

、（

）下标

和

元素（

）。

答案:行;列;值已知二维数组M5×6的每个元素占4个字节，已知Loc(m00)=2010，M共占（

）个字节？M的最后一个数组元素m[4][5]的存储地址是（

）？以行为主和以列为主的顺序存储时，m[2][5]的存储地址分别是（

）和（

）。

答案:120;2126;2078;2118一个20阶的五对角矩阵中，需要（

）个存储单元。

答案:94一个20阶的三对角矩阵中，需要（

）个存储单元。

答案:58所谓稀疏矩阵指的是非零元素很少且分布没有规律的矩阵。

答案:对在n(n>3)阶三对角矩阵中,每一行都有3个非零元素。

答案:错对角矩阵的特点是非零元素只出现在矩阵的两条对角线上。

答案:错二维数组A[4][4](即A[0..3][0..3])的元素起始地址是loc(A[0][0])=1000,元素的长度为2,则LOC(A[2][2])的地址为多少?

答案:1020设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素a[3][5]的存储地址为1000,则a[0][0]的存储地址是______。

答案:860一个n*n的对称矩阵A,采用压缩方式存放到一维数组B中,则B的容量为______.

答案:(n*(n+1))/2广义表L=((a,b),(c,d))

,运算式Tail(L)的操作结果是

。

答案:((c,d广义表A：(()，(a)，((c，d)))的深度为

。

答案:3广义表A=(

a,b,(c,d),(e,(f,g))

),则执行Head(Tail(Head(Tail(Tail(A)))))的值为

。

答案:d已知广义表:A=(a,b),B=(A,A),C=(a,(b,A),B),求下列运算的结果:

tail(head(tail(C)))=

。

答案:(A去除广义表LS=(a1,a2,a3,……，an)中第1个元素，由其余元素构成的广义表称为LS的____________。

答案:表尾已知广义表如下：A=(B,y)B=(x，L)L=(a，b)要求：(1)写出下列操作的结果tail(A)=_______________.head(B)=______________。

答案:(y;x表头和表尾均为空表的广义表是(

)

答案:(())对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是(

)

答案:(b)广义表A=(a,(b),(),(c,d,e))的长度为(

)

答案:4

从广义表L=(((d),c,d))中分解得到(d)的操作为(

)

答案:tail(tail(head(L)))对广义表L=((a,b),((c,d),(e,f)))执行head(tail(head(tail(L))))操作的结果是（）

答案:(e,f)对广义表L=(a，())执行操作tail(L)的结果是（）

答案:(())从广义表LS＝（(p,q),r,s）中分解出原子q的运算是（

）

答案:head(tail(head(LS)))对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是(

)

答案:((e,f))在一棵高度为3的四叉树中,最多含有______结点。假定树根结点的高度为0

答案:85在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为(

)

答案:6/star3/origin/2f38267cb004ab0a96cec105682ccbb9.png

答案:5;3;2;1一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y))),结点f的层数为______。假定根结点的层数为0。

答案:3假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J))),则该树的高度为______。假定根结点的高度为0。

答案:3如果结点A有三个兄弟，而且B是A的双亲，则B的出度是_____。

答案:4已知一棵树的边的集合表示为：(L,N),(G,K),(G,L),(G,M),(B,E),(B,F),(D,G),(D,H),(D,I),(D,J),(A,B),(A,C),(A,D))画出这棵树，并回答下列问题：树的度是多少？树的深度是多少？

答案:4;5对于一棵具有n个结点的树,该树中所有结点度数之和为（

）

答案:n-1已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为(

)

答案:11树最适合用来表示（）

答案:元素之间具有分支层次关系的数据在一棵树中,(

)没有前驱结点。

答案:根结点在一棵二叉树中，若度为2的结点数有5个，度为1的结点数有6个，那么度为0的结点数有

个

答案:6将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子结点编号为（

）

答案:98已知二叉树有31个叶子结点，且仅有一个孩子的结点数为40，则总结点数为（

）。

答案:101假定一棵二叉树的结点数为18个，则它的最小高度_____。

答案:5假设一棵完全二叉树含1000个结点,则其中度为2的结点数为___________。

答案:499结点数为20的二叉树可能达期的最大高度为_________。

答案:20若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（

）

答案:5已知一棵完全二叉树中共有768结点，则该树中共有(

)个叶子结点。

答案:384具有35个结点的完全二叉树的深度为（

）

答案:6一棵含18个结点的二叉树的高度至少为(

)

答案:5已知完全二叉树的第4层有6个结点，则其叶子结点数是（

）。

答案:7已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（

）

答案:49已知一棵二叉树的中序与后序序列如下,求该二叉树的前序序列。中序序列:c,b,d,e,a,g,i,h,j,f后序序列:c,e,d,b,i,j,h,g,f,a前序序列:____________________

答案:a,b,c,d,e,f,g,h,i,j/star3/origin/0f3e5fea643c02565d461a59474c96c9.png

答案:GDBHEFCA已知一棵二叉树的前序与中序序列,求该二叉树的后序序列。前序序列:A,B,C,D,E,F,G,H,I,J中序序列:C,B,A,E,F,D,I,H,J,G后序序列:______________________

答案:C,B,F,E,I,J,H,G,D,A某二叉树的前序和后序序列正好相反，则该二叉树一定是（

）的二叉树。

答案:高度等于其结点数在一非空二叉树的中序遍历序列中，根结点的右边（

）

答案:只有右子树上的所有结点若二叉树的后序遍历序列为dabec，中序遍历序列为debac，则前序序列遍历为（

）。

答案:cedba若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是(

)

答案:树中只有一个根结点某二叉树的先序序列和后序序列正好相同，则该二叉树一定是(

)的二叉树。

答案:空或只有一个结点/star3/origin/a7362b58560feaf39ae55d675b88083a.png

答案:A一棵左右子树均不空的二叉树在中序线索化后，其空指针域数为(

)

答案:2用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为(

)

答案:n+1用二叉链表表示具有n个结点的二叉树时，值为非空的指针域的个数为(

)

答案:n-1

一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为(

)

答案:1已知森林F={T1，T2，T3，T4，T5}，各棵树Ti(i=1，2，3，4，5)中所含结点的个数分别为7，3，5，l，2，则与F对应的二叉树的左子树中的结点个数为（

）。

答案:6一棵树转换成对应的二叉树,则该二叉树中______结点肯定没有右子女。

答案:根树的先根序列等同于与该树对应的二叉树的（

答案:先序序列树的后根序列等同于与该树对应的二叉树的（

）

答案:中序序列已知森林F={T1，T2，T3，T4，T5}，各棵树Ti(i=1，2，3，4，5)中所含结点的个数分别为7，3，5，1，2，则与F对应的二叉树的右子树中的结点个数为（

）

答案:11用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为_________。

答案:219有7个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶结点生成一棵霍夫曼树,求出该树的带权路径长度、高度、度为2的结点个数。带权路径长度:____________高度:___________度为2的结点数:____________

答案:131;5;6利用n个值作为叶结点的权生成的霍夫曼树中共包含有_________个双支结点。

答案:n-1由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为_____。

答案:44利用3,6,8,12这四个值作为叶结点的权值生成一棵霍夫曼树,该树的带权路径长度为(

)。

答案:55已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一个。

答案:错由树转换成二叉树，其根结点的右子树总是空的。

答案:对不管一棵哈夫曼树中有偶数或奇数个叶子结点，则树中总结点的个数必为____________数个。（填：“奇”或“偶”）

答案:奇在二叉树的顺序存储中，对于下标为5的结点，它的双亲结点的下标为__________，若它存在左孩子，则左孩子结点的下标为__________，若它存在右孩子，则右孩子结点的下标为___________。

答案:2;10;11以数据集（4，5，6，7，10，12，18）为结点权值的Huffman树的带权路径长度为（

）。

答案:165已知完全二叉树的第4层有6个结点，则其叶子结点数是（

）。

答案:7由一棵二叉树后序序列和（）序可唯一确定这棵二叉树。

答案:中将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子结点编号为（

）。

答案:98某二叉树的前序和后序序列正好相反，则该二叉树一定是（

）的二叉树。

答案:高度等于其结点数在有8个结点的无向图中，其边数最多为______条边。

答案:28在有向图中，以顶点v为终点的边的数目称为v的____________。

答案:入度n个顶点的连通图中至少含有(

)

答案:n-1条边

n个顶点的强连通图中至少含有(

)

答案:n条有向边n个顶点的有向图中含有向边的数目最多为(

)

答案:n(n-1)n个顶点的无向图中含有向边的数目最多为(

)

答案:n(n-1)/2

无向图中一个顶点的度是指图中(

)

答案:与该顶点相邻接的顶点数若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数即为顶点vi的________________。

答案:出度若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为___________。

答案:2m若用邻接矩阵表示有向图，则顶点i的入度等于矩阵中_________。

答案:第i列的非0元素的个数对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（）。

答案:n邻接表是图的一种（

）。

答案:链式存储结构在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为(

)

答案:n2－2e

若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（）

答案:图中每个顶点的入度无向图的邻接矩阵是一个_______

答案:对称矩阵假设有向图含n个顶点及e条弧，则表示该图的邻接表中，包含的结点个数为（

）

答案:e图的广度优先搜索序列是惟一的。

答案:错/star3/origin/964b6e5fc7cf8326240447319ce3d1bc.png

答案:对/star3/origin/4c290eb1aa2e388b3b0a971b76da2bce.png

答案:acefdh/star3/origin/e93617cbdaa5418f72d9059c6790cecf.png

答案:acdbfeh/star3/origin/ad16c8a1d5aa99684cf51e67d17c8f80.png

答案:gaedfcb如果从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是

（

）

答案:连通图/star3/origin/e55fc6ef39623eccf8393cb6e7076d5e.png

答案:55/star3/origin/d0e2a8614de649473d61a593f977de4f.png

答案:35在图G中求两个结点之间的最短路径可以采用的算法是(

)

答案:迪杰斯特拉（Dijkstra）算法在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。

答案:对/star3/origin/98427f9d90188d7aaf63c85feaea8ccf.png

答案:3.5分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(

)

答案:（100，60，80，90，120，110，130）

堆是完全⼆叉树，完全⼆叉树不⼀定是堆。

答案:对（101,88,46,70,34,39,45,58,66,10）是堆。

答案:对利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为(________)。

答案:75,66,48,29,31,37下列关键字序列中，构成小根堆的是(

)

答案:{15，28，46，37，84，58，62，41}堆是一种（

）排序。

答案:选择下列关键字序列中（

）是堆

答案:16，23，53，31，94，72一组记录的关键字为｛25,50,15,35,80,85,20,40,36,70}，其中已经含有5个长度为2的有序表，即：｛【25,50】,【15,35】,【80,85】,【20,40】,【36,70】｝用归并排序方法对该序列进行一趟归并后的结果为

答案:15,25,35,50,20,40,80,85,36,70一组记录为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一次归并后的结果为（

）

答案:16，25，35，48，23，40，79，82，36，72对关键字序列(50，34，92，19，11，68，56，41，79)进行直接插入排序，当将第7个关键字56插入到当前的有序子表中时，为寻找插入位置需进行_____次关键字之间的比较。

答案:5已知关键字序列为(51，22，83，46，75，18，68，30)，对其进行快速排序，第一趟划分完成后的关键字序列是（

）

答案:(30,22,18,46,51,75,68,83)设待排序关键码序列为(25，18，9，33，67，82，53，95，12，70)，要按关键码值递增的顺序进行排序，采取以第一个关键码为分界元素的快速排序法，第一趟完成后关键码95被放到了第几个位置?______。

答案:8快速排序在（

）情况下最易发挥其长处。

答案:被排序的数据完全无序用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84则采用的排序方法是（

）

答案:快速排序广义表的元素可以是子表，也可以是单元素。（）

答案:对广义表的表尾一定是一个广义表。（）

答案:对矩阵中的行列数往往是不相等的。（）

答案:错矩阵不仅是表示多维数组，而且是表示图的重要工具。（）

答案:对在一般情况下，采用压缩存储之后，对称矩阵是所有特殊矩阵中存储空间节约最多的。（）

答案:错采用压缩存储之后，下三角矩阵的存储空间可以节约一半。（）

答案:错对于不同的特殊矩阵应该采用不同的存储方式。（）

答案:对以行为主序或以列为主序对于多维数组的存储没有影响。（）

答案:对多维数组可以看作数据元素也是基本线性表的基本线性表。（）

答案:对数组可看作基本线性表的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。（）

答案:错/star3/origin/ded454a77ee99615b94ff0de96a75547.png

答案:（（0，2，2），（1，0，3），（2，2，-1），（2，3，5））；对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为______________。

答案:i×n+j个元素位置一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。

答案:线性结构;顺序结构;以行为主序;以列为主序串是指___________________。

答案:含n个字符的有限序列（n≥0空串是指___________________，空格串是指___________________。

答案:不含任何字符的串;仅含空格字符的字符串一个广义表的表头总是一个（）。

答案:元素或广义表若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（）。

答案:不正确数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（）。

答案:SA+222通常对数组进行的两种基本操作是（）。

答案:查找和修改广义表A=((x,(a,B)),(x,(a,B),y))，则运算head(head(tail(A)))的结果为（）。

答案:x广义表A=（a），则表尾为（）。

答案:空表设有广义表D=(a,b,D)，其长度为（），深度为（）。

答案:3若下三角矩阵An×n，按列顺序压缩存储在数组Sa[0…(n+1)n/2]中，则非零元素aij的地址为（）。（设每个元素占d个字节）

答案:[(j-1)*n-+i]*d若数组A[0…m][0…n]按列优先顺序存储，则aij地址为（）。

答案:LOC(a00)+[j*m+i]设二维数组A[0…m-1][0…n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（）。

答案:p+[i*n+j-1]*k字符串采用结点大小为1的链表作为其存储结构，是指（）。

答案:链表的每个链结点的数据域中只存放了一个字符在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（）。

答案:1≤i≤n若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（）。

答案:“Shanghai＆Nanjing”若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（）。

答案:4若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（）。

答案:“jing＆”两个字符串相等的条件是（）。

答案:两串的长度相等，并且对应位置上的字符相同一个子串在包含它的主串中的位置是指（）。

答案:子串的第一个字符在主串中首次出现的位置广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（）。

答案:d数组A[0..4,-1..-3,5..7]中含有元素的个数（）。

答案:45设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（）。

答案:(i-1)*n+j若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij（iA.i*(i-1)/2+jB.j*(j-1)/2+iC.i*(i+1)/2+jD.j*(j+1)/2+i我的答案：B正确答案：B

答案:j*(j-1)/2+i设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（）。

答案:BA+180假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（）。

答案:818串“ababaaababaa”的next数组为（）。

答案:011234223456串是一种特殊的线性表，其特殊性体现在（）。

答案:数据元素是一个字符顺序队列中有多少元素，可以根据队首指针和队尾指针的值来计算。

答案:对N个元素进队列的顺序和出队列的操作顺序总是一致的

答案:对队列是一种对进队、出队操作的次序做了限制的线性表。

答案:错栈和队列都是限制存取端的线性表。

答案:对空栈没有栈顶指针。

答案:错对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。

答案:对栈是一种对进栈、出栈操作总次数做了限制的线性表。

答案:错若用s[0..m-1]表示顺序栈的存储空间，则对栈的进栈、出栈操作最多只能进m次。

答案:错栈顶元素和栈底元素有可能是同一个元素。

答案:对在n个元素进栈后，它们的出栈顺序和进栈顺序一定正好相反。

答案:错顺序栈中元素值的大小是有序的。

答案:错栈底元素是不能删除的元素。

答案:错/star3/origin/6933ca3ac985d4c76888d6954b4fa9c4.png

答案:BCD;CBD用一维数组设计栈，初态是栈空，top=0。现有输入序列是a、b、c、d，经过push、push、pop、push、pop、push操作后，输出序列是（

），栈顶指针是（

）

答案:b,c;2数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（

）。

答案:（n+r-f)%n一个递归算法必须包括（）。

答案:终止条件和递归部分栈和队列的共同点是（）。

答案:只允许在端点处插入和删除元素最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。

答案:rear==front循环队列存储在数组A[0..m]中，则入队时的操作为（）。

答案:rear=(rear+1)%(m+1)用链接方式存储的队列，在进行删除运算时（）。

答案:头、尾指针可能都要修改设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。

答案:栈若一个栈以向量V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是()。

答案:top--;V[top]=x;设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。

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

答案:队列栈在

（）中有所应用。

答案:前三个选项都有设有一个递归算法如下

答案:

intfact(intn){

//n大于等于0链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。

答案:x=top->data;top=top->link；若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

答案:4，3，1，2，5在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。

答案:n-i设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。

答案:p->next=p->next->next;在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。

答案:s->next=p->next;p->next=s;在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_______。

答案:O(n)线性表L=(a₁，a₂,……an)，下列说法正确的是（）。

答案:除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。线性表Ｌ在（）情况下适用于使用链式结构实现。

答案:需不断对Ｌ进行删除插入链表不具有的特点是___________________

答案:可随机访问任一元素在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（）个元素。

答案:n-i+1循环链表的主要优点是(

)。

答案:从表中的任意结点出发都能扫描到整个链表线性表是________。

答案:一个有限序列，可以为空线性表采用链式存储时，其地址________。

答案:连续与否均可以创建一个包括n个结点的有序单链表的时间复杂度是（）。

答案:O(n²)在双向链表存储结构中，删除p所指的结点时须修改指针（）。

答案:p->next->prior=p->prior;p->prior->next=p->next;顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

答案:108线性表若采用顺序存储结构时，要求内存中可用存储单元的地址（

）。

答案:必须是连续的在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。

答案:s->prior=p;

s->next=p->next;p->next->prior=s;

p->next=s;在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行

答案:q->next=s;s->next=p以下关于线性表的说法不正确的是______。

答案:线性表中的每个结点都有且只有一个直接前趋和直接后继。将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。

答案:n在顺序表中，只要知道_______，就可在相同时间内求出任一结点的存储地址。

答案:基地址和结点大小链接存储的存储结构所占存储空间（）。

答案:分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针每种数据结构的逻辑结构与物理结构总是一致的。

答案:错数据项是具有独立含义的数据最小单位。

答案:对数据结构就是指数据在计算机中的存储结构。

答案:错数据元素是数据的最小单位。

答案:错每个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是()存储方式。

答案:链接以下算法的时间复杂度为（

）。

void

fun(int

n)

{

inti=l;

while(i<=n)

i=i*2;

}

答案:O(log2n)以下与数据的存储结构无关的术语是（）。

答案:有序表一个存储结点存储一个()。

答案:数据元素通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。

答案:不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致求整数n(n>=0)阶乘的算法如下，其时间复杂度是(

)。

int

fact(int

n){

if(n<=l)return1;

returnn*fact(n-1);}

答案:

O(n)以下算法中m++;语句的执行次数为（

）。intm=0,i,j;for(i=l;i<=n;i++)

for(j=1;j<=2*i;j++)

m++;

答案:n(n+1)与数据元素本身的形式、内容、相对位置、个数无关的是数据的（

）。

答案:逻辑结构以下算法的时间复杂度为(

)

x=0;for(i=1;i答案:O(n2)算法分析的目的是()。

答案:分析算法的效率以求改进有声明双链表结点typedefstructnode{

datatypedata;

________

*front;

_________*next;}ND;请问front和next前应填入（

）？

答案:structnode判断带表头附加结点循环双链表为空在条件是？

答案:head->next==head&&head->front==head有单链表head，在p结点后增加一个元素q，则进行（

）操作。

答案:q->next=p->next;p->next=q;顺序表的优点是（

）。

答案:读得快有带表头附加结点的单链表head，则以下语句可以完成对该单链表的初始化

答案:head->next=NULL;声明顺序表如下：typedefstructsqList{

datatypedata[10];

intlast;}SQ;如果对该顺序表进行初始化，则应该将last赋值为（

）。

答案:-1在长度为n的单链表中，删除第i个元素，则需要移动（

）个元素？

答案:0在顺序表中有n个元素，删除第i个元素，则需要移动（

）个元素？

答案:n-i在长度为n的顺序表中，在第i个位置（假设i位置是符合插入条件的）插入元素，则需要移动（

）个元素？

答案:n-i+1从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为()。

答案:O(log2n)对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为()。

答案:4若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%7计算哈希地址，则哈希地址等于3的元素个数()。

答案:2对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为()的9分之一。

答案:20采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字()。

答案:不一定都是同义词设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（）。

答案:9下面关于哈希查找的说法，正确的是（）。

答案:不存在特别好与坏的哈希函数，要视情况而定分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）。

答案:（100，60，80，90，120，110，130）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。

答案:20，70，30，50如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用()查找法。

答案:分块查找适用于折半查找的表的存储方式及元素排列要求为（）。

答案:顺序方式存储，元素有序对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（

）。

答案:(n+1)/2在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为()。

答案:2e在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为()。

答案:2e在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为()。

答案:2e/star3/origin/72640dd44d919ab194817dc1bf6bec6f.png

答案:0

1

2

3深度优先遍历类似于二叉树的（）。

答案:先序遍历用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。

答案:队列下面（）算法适合构造一个稠密图G的最小生成树。

答案:Prim算法G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。

答案:9具有n个顶点的有向图最多有（）条边。

答案:n(n-1)在一个图中，所有顶点的度数之和等于图的边数的（

）倍。

答案:210.树的子树是无序的。（）

答案:错9.哈夫曼树一定是完全二叉树。（）

答案:错7.根据任意一种遍历序列即可唯一确定对应的二叉树。（）

答案:对8.满二叉树也是完全二叉树。（）

答案:对3.线索二叉树是一种逻辑结构。（）

答案:错2.二叉树的前序遍历中，任意结点均处在其子女结点之前。（）

答案:对根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树（）。

答案:是完全二叉树把一棵树转换为二叉树后，这棵二叉树的形态是（

）。

答案:唯一的若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）。

答案:X的左子树中最右结点设哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

答案:100一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。

答案:只有一个叶子结点在下列存储形式中，（）不是树的存储形式？

答案:顺序存储表示法若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。

答案:后序一个具有1025个结点的二叉树的高h为（）。

答案:11至1025之间一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。

答案:501由3个结点可以构造出多少种不同的二叉树？（

）

答案:5设二维数组A[0…m-1][0…n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（

）。

答案:p+[i*n+j]*k若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij（i答案:j*(j-1)/2+i设有一个递归算法如下

intfact(intn){

//n大于等于0

if(n<=0)return1;

elsereturnn*fact(n-1);

}计算fact(n)需要调用该函数的次数为（

）。

答案:

n+1

若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。

答案:n-i+1在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动______个元素。

答案:n-i在等概率情况下，顺序表的插入操作要移动______结点。

答案:一半向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。

答案:63.5从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。

答案:（n+1）/2在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。

答案:访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）在______运算中，使用顺序表比链表好。

答案:根据序号查找单链表的存储密度（）。

答案:小于1将两个各有n个元素的有序表归并成一个有序表，在最好的情况下的比较次数是（

）。

答案:n链接存储的存储结构所占存储空间（

）。

答案:分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针以下数据结构中，（）是非线性数据结构

答案:树程序段for(i=n-l;i>l;i--)

for(j=1;jA[j+l])

A[j]与A[j+1]对换;其中n为正整数，则最后一行的语句频度在最坏情况下是（

）。

答案:O(n2)在用数组表示的循环队列中，front值一定小于等于rear值。

答案:错线索二叉树是一种逻辑结构。

答案:错栈和队列的存储方式,既可以是顺序方式,也可以是链式方式。

答案:对线性表的逻辑顺序与存储顺序总是一致的。

答案:错排序算法中的比较次数与初始元素序列的排列无关。

答案:错树的子树是无序的。（）

答案:错一个栈的输入序列是12345，则栈的输出序列不可能是12345。

答案:错具有10个叶结点的二叉树中,有9个度为2的结点。

答案:对距阵中的数据元素可以是不同的数据类型。（）

答案:错在对链队列做出队操作时，不会改变front指针的值。

答案:错n个元素进队的顺序和出队的顺序总是一致的。

答案:对在对n个元素进行堆排序的过程中，空间复杂度为（）。

答案:O(1)带权有向图G用邻接矩阵存储，则Vi的入度等于邻接矩阵中（

）

答案:第i列非∞且非0的元素个数与数据元素本身的形式、内容、相对位置、个数无关的是数据的（

）。

答案:逻辑结构对5个不同的数据元素进行直接插入排序，最多需要进行的比较次数是（

）

答案:10设F是一个森林，B是由F变换来的二叉树，若F中有n个非终端结点，则B中右指针域为空的结点有（

）个

答案:n+1广义表((a,b,c,d))的表头是（

）

答案:(a,b,c,d)对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（

）遍历实现编号。

答案:后序若一个元素序列基本有序，则选用（）方法较快。

答案:直接插入排序若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为()。

答案:(n+1)/2若要从1000个元素中得到10个最小值元素，最好采用（）方法。

答案:简单选择排序下面（）方法可以判断出一个有向图是否有环。

答案:拓扑排序采用线性探测法处理冲突,可能要探测多个位置,在查找成功的情况下,所探测的这些位置上的关键字()。

答案:不一定都是同义词线性表Ｌ在（

）情况下适用于使用链式结构实现。

答案:需不断对Ｌ进行删除插入若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为()。

答案:(d+1)%m线性表的链式存储结构优于顺序存储。

答案:错数据的逻辑结构是依赖于计算机的。

答案:错数据的物理结构是指数据在计算机内实际的存储形式。

答案:对数据的存储结构是数据的逻辑结构的存储映像。

答案:对从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。

答案:对程序和算法原则上没有区别，所以在讨论数据结构时可以通用。

答案:错数据的逻辑结构和数据的存储结构是相同的。

答案:错一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。

答案:对数据的逻辑结构与数据元素本身的内容和形式无关。

答案:对数据结构是数据的组织形式包括哪些方面（）

答案:数据元素间的逻辑关系，即数据的逻辑结构;;数据元素及其关系在计算机存储内的表示，即数据的存储表示;;数据的运算，即对数据元素施加的操作。数据结构不是（）的组织形式

答案:字母;数字;英文()不属于信息的载体

答案:字母;数字;英文8.下面()方法可以判断出一个有向图是否有环(回路)。

答案:深度优先遍历;拓扑排序7.在一个无向图中,所有顶点的度数之和等于所有边数()倍,在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的()倍。

答案:2;16.一个有n个顶点的图,最少有()个连通分量,最多有()个连通分量。

答案:0;n一个循环队列一旦说明，其占用空间的大小（

）。

答案:已固定当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为（

）。

答案:n-1队列是一个(

)线性表结构。

答案:加了限制的同一队列内各元素的类型(

)。

答案:必须一致队列中的元素个数是(

)。

答案:可变的队列是限定在（

）进行操作的线性表。

答案:端点9.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear,则当前队列中的元素个数为()。

答案:(rear-front+m)%m线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。

答案:对顺序存储方式的优点是存储密度大，插入、删除效率高。

答案:错在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

答案:对顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

答案:错队尾没有在（）

答案:链头;链中;链末队头没有在（）

答案:链尾;链中;链末数据元素又称为（）。

答案:元素;结点;记录只允许在一端插入和删除的线性表允许插入和删除的一端不能称为（）

答案:栈底;栈中;栈末循环队列占用的空间(

)。

答案:必须连续若进队的序列为：A，B，C，D，则出队的序列是（

）。

答案:A，B，C，D四个元素按：A，B，C，D顺序连续进队Q，执行一次OutQueue(Q)操作后，队头元素是（

）。

答案:B存放循环队列元素的数组Data有10个元素，则Data数组的下标范围是(

)。

答案:0..9四个元素按：A，B，C，D顺序连续进队Q，则队尾元素是（

）。

答案:D队列Q，经过下列运算后：itQueue(Q)(初始化队列);InQueue(Q,a);InQueue(Q,b);OutQueue(Q,x);x的值是（

）

答案:0循环队列SQ队满的条件是(

)。

答案:(SQ->rear+1)%

MAXLEN

==SQ->front四个元素按：A，B，C，D顺序连续进队Q，执行四次OutQueue(Q)操作后，再执行QEmpty(Q);后的值是（

）。

答案:1“数据结构”的本质目的是？

答案:通过寻找恰当的数据组织形式从而获得对数据时间或空间上更有效的存取算法通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（

）。

答案:不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致在数据结构中，从逻辑上可以把数据结构分成（

）。

答案:线性结构和非线性结构/star3/origin/d1faece7c3ccf7f0f1684fc0404cb2ed.png

答案:（1）T(n)=O(1)解释：程序的执行次数为常数阶。（2）T(n)=O(m*n)解释：语句a[i][j]=0;的执行次数为m*n。（3）答案：T(n)=O()解释：语句s+=B[i][j];的执行次数为。（4）答案：T(n)=O()

解释：设语句i=i*3;的执行次数为f(n)，那么n，即f

。（5）答案：O()解释：语句x++;的执行次数为n-1+n-2+……＋1=n(n-1)/2。（6）答案：O()解释：设语句y++;的执行次数为f(n)，那（f(n)+1)(f(n)+1)n，近似于，即在用链表实现堆栈时，选用单向链表还是双向链表？

答案:单向链表，因为它实现的堆栈操作可以达到O(1)，同时消耗的存储空间小于双向链表假设用单向链表实现堆栈，堆栈顶端应该选在什么位置？

答案:单向链表的头节点用数组实现堆栈的基本方法是？

答案:数组中当前存放数据下标最大处作为栈顶设计一个判别表达式中左，右括号是否配对出现的算法，采用()数据结构最佳。

答案:栈链式栈结点为:(data,link)，top指向栈顶，若想摘除栈顶结点,并将删除结点的值保存到x中，则应执行操作(

)。

答案:x=top->data;top=top->link;为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（

）。

答案:队列单向链表实现队列的基本方法是？

答案:头节点作为出队端，尾节点作为入队端用数组实现队列的基本方法是？

答案:需要通过求模运算控制队列两端的下标一个具有1025个结点的二叉树的高h为（

）。

答案:11至1025之间一棵完全二叉树共有20个结点，那这棵树的深度是（

）。