数据结构判断题

习题一三．判断题。数据元素是数据的最小单位。（错误）数据的逻辑结构是指数据的各数据项之间的逻辑关系。（错误）算法的优劣与算法描述语言无关，但与所用计算机有关。（错误）程序一定是算法。（错误）数据的物理结构是指数据在计算机内的实际存储形式。（正确）数据的抽象操作的定义与具体实现有关。（错误）数据的逻辑结构表达了数据元素之间的关系，它依赖于计算机的存储结构。（正确）习题二三．判断题。链表中的头结点仅起到标识作用。（错误）顺序存储的线性表可以按序号随机存取。（正确）线性表采用链表存储时，存储空间可以是不连续的。（正确）静态链表中地址相邻的元素具有前驱后继的关系。（错误）对任何数据结构，链式存储结构一定优于顺序存储结构。（错误）在线性表的顺序存储结构中，逻辑上相邻的两个元素在无力位置上不一定紧邻。（错误）循环链表可以在尾部设置头指针。（正确）为了方便插入和删除，可以使用双向链表存放数据。（正确）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（错误）取顺序表的第i个元素的时间与i的大小有关。（错误）习题三消除递归一定要使用桟。（错误）桟是实现过程和函数调用所必须的结构。（正确）两个桟共享一片连续内存空间时，为提高内存利用率、减少溢出机会，应把两个桟的栈底分别设在这片内存空间的两端。（正确）用递归方法设计的算法效率高。（错误）栈与队列是一种特殊的线性表。（正确）队列逻辑上是一端既能增加又能减少的线性表。（错误）循环队列通常浪费一个存储空间。（正确）循环队列也存在空间溢出问题。（正确）栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（正确）任何一个递归过程都可以转换成非递归过程。（正确）习题四KMP算法的特点是在模式匹配时指示主串的指针不会变小。（正确）只要串采用定长顺序存储，串的长度就可以立即获得，不需要用函数求。（错误）next函数值序列的产生仅与模式串有关。（错误）空格串就是由零个字符组成的字符序列。（错误）从串中取若干个字符组成的字符序列称为串的字串。（错误）串名的存储映像就是按串名访问串值的一种方法。（正确）两个串含有相等的字符，它们一定相等。（错误）在插入和删除操作中，链式串一定比顺序串方便。（正确）串的存储密度与结点大小无关。（错误）在串的顺序存储中，通常将“\0”作为串结束的标记。（正确）习题五数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。（错误）二维以上的数组其实是一种特殊的广义表。（正确）稀疏矩阵压缩存储后，必会失去随机存储功能。（正确）一个稀疏矩阵Amvn采用三元组形式表示，若把三元组中有关下标与列下标的值互换，并把m和n的值互换，则就完成了A转置运算。（错误）mXn线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。（正确）一个广义表可以为其他广义表所共享。（正确）广义表中原子个数即为广义表的长度。（错误）所谓取广义表的表尾就是返回广义表中最后一个元素。（错误）广义表是由零或多个原子或子表所组成的有限序列，所以广义表可能为空表。（正确）任何一个非空广义表，其表头可能是单个元素或广义表，其表尾必定是广义表。（正确）习题六哈夫曼树的结点个数不可能是偶数。（正确）二叉树中序线索化后，不存在空指针域。（错误）二叉树线索化后，任意一个结点均有指向其前驱和后继的线索。（错误）哈弗曼编码是前缀编码。（错误）非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子。（正确）必须把一般树转换成二叉树后才能进行存储。（错误）由先序和后序遍历序列不能唯一确定一棵二叉树。（正确）一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（错误）一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（正确）在哈夫曼树中，权值相同的叶结点都在同一层上。（错误）习题七当改编AOE网上某一关键路径上任一关键活动后，必将产生不同的关键路径。在n个结点的无向图中，若边数大于n-1,则该图必是连通图。在AOE网中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。一个有向图的邻接表和逆邻接表中结点的个数可能不相等。强连通图的各顶点间均可达。带权的连通无向图的最小代价生成树是唯一的。广度遍历生成树描述了从起点到各顶点的最短路径。邻接多重表是无向图和有向图的链式存储结构。连通图上各边权值均不相同，则该图的最小生成树是唯一的。习题八折半查找法的查找速度一定比顺序查找快。（错误）就平均查找长度而言，分块查找最小、折半查找次之，顺序查找最大。（错误）对一棵二叉树排序树线序遍历得出的结点序列是从小到大的序列。（错误）哈希查找不需要任何比较。（错误）将线性表中的信息组织成平衡二叉树，其优点之一是无论线性表中数据如何排列，总能保证平均查找长度均为log屮量级（n为线性表中的结点数目）。（争取）在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（错误）有序的线性表不论如何存储，都能采用折半查找。（错误）B+树既能索引查找也能顺序查找。（正确）Hash表的平均查找长度与处理冲突的方法无关。（错误）装填因子是哈希表的一个重要参数，它反映了哈希表的装满程度。（正确）习题九快速排序在所有排序方法中最快，而且所需附加空间也最少。（错误）在大根堆中，最大元素在根的位置，最小元素在某个叶结点处。（正确）用Shell方法排序时，若关键字的初始排序越杂乱无序，则排序效率就越低。（错误）对n个记录进行堆排序，在最坏的情况下的时间复杂度是0（"2）。（错误）

在任何情况下，快速排序方法的时间性能总是最优的。（错误）堆是满二叉树。（错误）快速排序和归并排序在最坏的情况下的比较次数都是O（nlog2n）。（错误）只有在初始数据表为逆序是，直接插入排序所执行的次数最多。（正确）简单选择排序算法的时间复杂性不受数据的初始状态映像，为0（"2）.（正确）10.11.12.《数据结构》第1教学单元测试练习题、选择1、通常从正确性、易读性、健壮性、高效性等四个方面评价算法（包括程序）的质量。以下解释错误的是（）A、正确性算法应能正确地实现预定的功能（即处理要求）B、易读性算法应易于阅读和理解以便于调试修改和扩充C、健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果D、高效性即达到所需要的时间性能B2、以下说法正确的是（）B、数据项是数据的基本单位DB、数据项是数据的基本单位D、数据结构是带有结构的数据元素的集合C、数据结构是带有结构的各数据项的集合3、对于顺序表，以下说法错误的是（）A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B、 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C、 顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中数组的下标可以看成是元素的相对地址B4、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作D、赋值语句）B、可以方便地随机存取表中的任一结点D、容易造成一部分空间长期闲置而得不AD、赋值语句）B、可以方便地随机存取表中的任一结点D、容易造成一部分空间长期闲置而得不B5、对于顺序表的优缺点，以下说法错误的是 （A、无需为表示结点间的逻辑关系而增加额外的存储空间C、插入和删除运算较方便到充分利用C6、链表不具有的特点是:A、可随机访问任一个元素 B、插入删除不需要移动元素C、不必事先估计存储空间 D、所需空间与线性表长度成正比C7、若线性表最常用的操作是存取第i个元素及其前驱的值，则采用()存储方式节省时间A、单链表B、双向链表C、单循环链表 D、顺序表顺序表可以随机存取8、 设指针P指向双链表的某一结点，贝y双链表结构的对称性可用()式来刻画A、p->prior->next->==p->next->next B、p->prior->prior->==p->next->priorC、p—〉prior—〉next—〉==p—〉next-〉prior D、p-〉next_〉next二二p_〉prior_〉pri0r9、 以下说错误的是()A、 对循环来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表B、 对单链表来说，只有从头结点开始才能扫描表中全部结点C、 双链表的特点是找结点的前趋和后继都很容易D、 对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。10、 在带头结点的循环链表中，将头指针改设为尾指针(rear)后，其头结点和尾结点的存储位置分别是()A、 rear和rear-〉next-〉next B、rear-〉next和rearC、rear-〉next-〉next和rear D、rear和rear-〉next11、 以下说错误的是()A、 对于线性表来说，查找定位运算在顺序表和单链表上的量级均为0(n)B、 读表元运算在顺序表上只需常数时间0(1)便可实现，因此顺序表是一种随机存取结构C、 在链表上实现读表元运算的平均时间复杂性为0(1)D、 插入、删除操作在链表上的实现可在0(n)时间内完成12、 循环链表主要优点是()A、不再需要头指针了 B、已知某个结点的位置后，能够容易找到它的直接前趋C、从表中任一结点出发都能扫描到整个链表D、在进行插入、删除运算时，能更好地保证链表不断开13、 以下说法错误的是 ()A、 数据的物理结构是指数据在计算机内实际的存储形式B、 算法和稈序没有区别，所以在数据结构中二者是通用的C、 对链表进行插人和删除操作时，不必移动结点D、 双链表中至多只有一个结点的后继指针为空14、 以下说法正确的是A、 线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继B、 线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低C、 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素位置有关D、 顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动15、 以下说法错误的是 ()A、 求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B、 顺序存储的线性表可以随机存取C、 由于顺序存储要求连续约存储区域所以在存储管理上不够灵活D、 线性表的链式存储结构优于顺序存储结构16、 以下说法错误的是 ()A、 线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻B、 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻C、 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻D、 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素17、 以下说法正确的是()

A、在单链表中，仟何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行杳找仟何一个元素B、 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构C、 顺序存储方式只能用于存储线性结构D、 顺序存储方式的优点是存储密度大、且插入、删除运算效率高A18、线性表L=（al,a2,...,ai,...,an）,下列说法正确的是（）A、 每个元素都有一个直接前驱和直接后继B、 线性表中至少要有一个元素C、 表中诸元素的排列顺序必须是由小到大或由大到小的D、 除第一个元素和最后一个元素外其余每个元素都有一个数且仅有一个直接前驱和直接后继A19、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（）A、必需是联系的 B、部分地址必须是连续的 C、一定是不连续的D、连续不连续都可以20.设REAR是指向非空带头结点的循环单链表的尾指针，则删除表首结点的操作可表示为（）A、p=rear;rear=rear->next;free（p） B、rear=rear->next;free（rear）;C、 rear=rear->next->next;free（rear）;D、 p二rear-〉next-〉next;rear-〉next-〉next二p-〉nextfree（p）:C21、单链表中，增加头结点的目的是为了（）A、使单链表至少有一个结点 B、标示表结点中首结点的位置C、方便运算的实现 D、说明单链表是线性表的链式存储实现22、带头结点的单链表Head为空的判定条件是A、Head==NullA、Head==NullB、Head-〉next==NULLC、Head-〉next==HeadCC、 P->next==L D、P==LB、算法执行过程中所需要的基本运算次数D、 算法程序中的指令条数B、算法程序中的指令条数D、算法执行过程中所需要的存储空间B、栈和队列是非线性结构D、二叉树是线性结构B、数据的逻辑结构在计算机中的表示D、存储在外存中的数据D、不确定23、 空的单循环链表L的尾结点*P,满足A、P-〉next==NULLB、P==NULLTOC\o"1-5"\h\z24、 算法的时间复杂度是指（ ）A、执行算法程序所需要的时间C、算法程序的长度25、算法的空间复杂度是指（ ）A、执行算法程序所占的存储空间C、算法程序的长度26、 下列叙述中正确的是（ ）A、线性表是线性结构C、线性链表是非线性结构C27、数据的存储结构是指（ ）A、数据所占的存储空间量C、数据在计算机中的顺序存储方式28、下列属于线性数据结构的是（）A、队列 B、树 C、图A29、单链表的每个结点中包括一个指针next，它指向该结点的后继结点。现要将指针q指向的新结点插入到指针P指向的单链表结点之后，下面的操作序列中哪一个是正确的？（）A、P-〉next=q-〉next;q=p-〉next; B、P-〉next=q;q-〉next=p-〉next;C、q-〉next二p-〉next;p-〉next二a; D、q=p-〉next：p-〉next=q-〉next：C30、在一个单链表中，若删除p所指结点的后续结点，则执行（）A、p-〉next二p-〉next-〉next; B、p二p-〉next：p—〉next二p—〉next-〉next：C、p-〉next=p-〉next; D、p=p-〉next-〉next;31、循环链表指（）A、最后一个节点的指针域总是指向链表头 B、可以自由膨胀的链表C、链表含有指向上一级节点的指针域D、C、链表含有指向上一级节点的指针域32、循环队列的出队操作为（）A、sa.front二（sa.ftont+1）%maxsize B、sq.front二sqfront+1C、sq.rear=（sq.rear+）%maxsize D、sq.rear二sq.rear+1B33、循环队列的队满条件为（）A、（sq.rear+1）%mazsize==（sq.front+1）%maxsize; B、（sq.rear+1%maxsize==sq.front+1TOC\o"1-5"\h\zC、 D、34、 循环队列的队空条件为（）A、（sq.rear+1）%maxsize==（sq.front+1）%maxsize B、（sq.rear+）%maxsize==sq.front+1C、 D、sa.rear==sa.front35、 如果以链表作为栈的存储结构,则退栈操作时 （）A、必须判别栈是否满 B、判别栈元素的类型C、必须判别栈是否空 D、队栈不做任何判别B36、设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是（ ） A、2B、3 C、5 D、637、设有一顺序栈已含3个元素，如下图所示，元素a4正等待进栈。那么下列4个序列中不可能出现的出栈序列是（ ）ala3TOC\o"1-5"\h\zA、a3.a1.a4.a2 B、a3,a2,a4,a1 C、a3,a4,a2,a1 D、a4,a3,a2,a138、 在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（ ）A、f-〉next=c;f=s B、r—〉next=s:r=sC、s-〉next=r;r=s D、s-〉next=f;f=s39、 链栈与顺序栈相比，有一个比较明显的优点即 （ ）A、插入操作更方便 B、通常不会出现栈满的情况C、不会出现栈空的情况D、删除操作更方便A40、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 （ ）A、edcba B、decba C、dceab D、abcde41、 一个队列的入队列顺序是1,2，3，4，贝9队列的输出系列是 （ ）A、4，3，2，1 B、1,2,3,4 C、1，4，3，2D、3，2，4，142、 设计一个判别表达式中左、右括号是否配对出线的算法，采用（）数据结构最佳。A、线性标的顺序存储结构B、栈C、队列 D、线性表的链式存储结构43、 设循环队列中数组的下标范围是0—n-1,其头尾指针分别为f和r,则其元素的个数为（）A、r—fB、r—f+1C、（r—f）%n+1D、（r-f+n）%nB44、若一个栈的输入序列是1、2……N,输出序列的第一个元素是N,则第I个输出元素为（）D、N-I-1C、只能进行插入 D、只能进行删除B、一个有限序列，不能为空；D、 D、N-I-1C、只能进行插入 D、只能进行删除B、一个有限序列，不能为空；D、 一个无序序列，不能为空。45、 队列操作的原则是（）A、先进先出 B、后进先出46、 线性表是（）。A、一个有限序列，可以为空；C、一个无限序列，可以为空；二、填空题47、 下面程序段的时间复杂度是—O（n*m）_for（i=0;ivn;i++）for（j=0;jvm;j++）Array[i][j]=0;48、 下面程序段的时间复杂度是死循环i=0;while(iv=n)i=i*3;49、在下面程序段中，s=s+p语句的执行次数为_n ,p*=j语句的执行次数为—n(n+l)/2 ，该程序段的时间复杂度为 O(n2)。inti=0,s=0;while(++i<=n){intp=l;for(intj=l;j<=i;j++)p*=j;s=s+p}50、 以下为求单链表表长的运算，分析算法，请在 处填上正确的语句。intlength_lklist(linklisthead)/*求表head的长度*/{__p=head ;j=0;while(p->next!=NULL){__p=p->next ;j++;}return(j);}51、以下为单链表的定位运算，分析算法，请在 处填上正确的语句。intlocate_lklist(lklisthead,datatypex)/*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/{p=head;j=0;while( p->next!=NULL&&p->data!=x__){p=p->next;j++;}if(p-〉data=x_)return(j_);elsereturn(0);}52、以下为单链表按序号查找的运算，分析算法，请在 处填上正确的语句。Pointerfind_lklist(lklisthead,inti){p=head;j=0;while(__p-〉next!=NULL&&j<i__){p=p-〉next;j++;}if(i==j)return(p);elsereturn(NULL);}53、以下为单链表的删除运算，分析算法，请在 处填上正确的语句。voiddelete_lklist(lklisthead,inti){p=find_lklist(head,i-1);/*find_lklist见73题*/if(__p-〉next!=NULL___){q=__p-〉next ;p-〉next=q-〉next;free(q);elseerror(“不存在第i个结点〃)54、以下为单链表的插入运算，分析算法，请在 处填上正确的语句。voidinsert_lklist(lklisthead,datatypex,inti)/*在表head的第I个位置上插入一个以x为值的新结点*/{p=find_lklist(head,i-1);/*find_lklist见73题*/if(p==NULL)error(“不存在第i个位置〃)；else{s=___malloc(size)__;s->data=x;s->next=__p->next__;p->next=s;}}55、 以下为单链表的建表算法，分析算法，请在 处填上正确的语句。lklistcreate_lklist()/*直接实现的建表算法。*/{head=malloc(size);p=head;scanf(“%f”,&x);while(x!='$'){q=malloc(size);q->data=x;p->next=q;_p=q ;scanf(“%f”,&x);}___q->next=NULL___;return(head);}56、 循环链表与单链表的区别仅仅在于其尾结点的链域值不是_空(NULL) 而是一个指向—头指针—的指针。57、 在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点,这样构成的链表中有两个方向不同的链,称为___双向链表___。58、 一个好的算法应当具有下列好的特性：正确性、(可读性)、(健壮性)和效率和低存储需求。59、 采用顺序存储结构的线性表，其每个元素占用L个单元。第一个元素的地址为N,则第i个元素的存储位置为(N+(i-l)*L )。60、 数据元素之间的关系在计算机中的表示有两种不同的表示方法，即(顺序映像)和(非顺序映像)，从而得到两种不同的存储结构(顺序存储结构)和(链式存储结构)。61、 带头结点的单链表H为空的条件是_H->next=NULL_。不带头结点的单链表H为空的条件是H=NULL62、非空单