菏泽学院数据结构（专升本）复习题

数据结构复习题一.单选题（共182题）1.

(单选题)算法的计算量的大小称为计算的（）A.效率B.复杂性C.现实性D.难度正确答案:

B2.

(单选题)无向图G=（V，E），其中：V={a，b，c，d，e，f}，E={（a，b），（a，e），（a，c），（b，e），（c，f），（f，d），（e，d）}，以顶点a为源点，对该图进行深度优先遍历，得到的顶点序列正确的是（）A.a，b，e，c，d，fB.a，c，f，e，b，dC.a，e，b，c，f，dD.a，e，d，f，c，b正确答案:

D3.

(单选题)设主串的长度为m，子串的长度为n，那么KMP模式匹配算法的时间复杂度为（）A.O（m）B.O（n）C.O（m*n）D.O（m+n）正确答案:

D4.

(单选题)用链接方式存储的队列，假设有头结点，在进行删除运算时（）A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改正确答案:

D5.

(单选题)数据的存储结构是指（）A.数据所占的存储空间B.数据的逻辑结构在计算机中的表示C.数据在计算机中的顺序存储方式D.存储在外存中的数据正确答案:

B6.

(单选题)设有6个值，由它们组成一棵赫夫曼树，则该赫夫曼树中结点个数共有（）A.6B.11C.12D.13正确答案:

B7.

(单选题)下面算法的时间复杂度为（）x=n；//n>1y=0；while（x>=（y+1）*（y+1））y++；A.O（n）B.O（n2）C.O（2n）D.O（n1/2）正确答案:

D8.

(单选题)设顺序循环队列Q[0..M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素，尾指针R总是指向队尾元素的下一位置，则该循环队列中的元素个数为（）A.R-FB.F-RC.（R-F+M）％MD.（F-R+M）％M正确答案:

C9.

(单选题)下面说法错误的是（）A.算法原地工作的含义是指不需要任何额外的辅助空间B.在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度O（2n）的算法C.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界D.某算法的时间复杂度为O（n2），表明该算法的执行时间与成n2正比正确答案:

A10.

(单选题)下列关于图的叙述中，正确的是（）I.回路是简单路径II.存储稀疏图，用邻接矩阵与邻接表更省空间III.若有向图中存在拓扑序列，则该图不存在回路A.仅IIB.仅I、IIC.仅IIID.仅I、III正确答案:

C11.

(单选题)若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（）A.dcebfaB.cbdaefC.bcaefdD.afedcb正确答案:

D12.

(单选题)栈和队列的共同点是（）A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点正确答案:

C13.

(单选题)算法的计算量的大小称为算法的（）A.效率B.现实性C.难度D.复杂度正确答案:

D14.

(单选题)串的长度是指（）A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数正确答案:

B15.

(单选题)下列排序算法中，（）排序在每趟结束后不一定能选出一个元素放到其排好序的最终位置上。A.归并B.冒泡C.选择D.堆正确答案:

A16.

(单选题)表达式a*（b+c）-d的后缀表达式是（）A.abcd*+-B.abc*+d-C.abc+*d-D.-+*abcd正确答案:

C17.

(单选题)输入序列为A，B，C，输出变为C，B，A时，经过的栈操作为（）A.push，pop，push，pop，push.popB.push，push，push，pop，pop，popC.push，push，pop，pop，push，popD.push，pop，push，push，pop，pop正确答案:

B18.

(单选题)以下（）是一个线性表。A.由n个实数组成的集合B.由100个字符组成的序列C.所有整数组成的序列D.由100个整数组成的集合正确答案:

B19.

(单选题)对n个关键字做快速排序，在最坏的情况下，算法的时间复杂度是（）A.O（n）B.O（n2）C.O（nlog2n）D.O（n3）正确答案:

B20.

(单选题)在常用的描述二叉排序树的存储结构中，关键字值最大的结点（）A.左指针一定为空B.右指针一定为空C.左右指针均为空D.左右指针均不为空正确答案:

B21.

(单选题)某算法的时间复杂度为O（n2），表明该算法的（）A.问题规模是n2B.执行时间等于n2C.执行时间与n2成正比D.问题规模与n2成正比正确答案:

C22.

(单选题)若一棵完全二叉树有768个结点，则该二叉树中的叶子结点的个数是（）A.257B.258C.384D.385正确答案:

C23.

(单选题)串是一种特殊的线性表，其特殊性体现在（）A.可以顺序存储B.每个数据元素是一个字符C.可以链式存储D.每个数据元素是多个字符正确答案:

B24.

(单选题)用链表表示线性表的优点是（）A.便于随机存取B.花费的存储空间较顺序存储少C.便于插入和删除D.数据元素的物理顺序与逻辑顺序相同正确答案:

C25.

(单选题)线性表若采用顺序存储结构时，要求内存中可用存储单元的地址（）A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以正确答案:

A26.

(单选题)下面算法的时间复杂度为（）for（i=0；iA.O（m）B.O（n）C.O（n*m）D.O（n+m）正确答案:

C27.

(单选题)由3个结点可以构造出（）种不同的二叉树。A.2B.3C.4D.5正确答案:

D28.

(单选题)关键路径是事件结点网络中（）A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长回路D.最短回路正确答案:

A29.

(单选题)算法分析的两个主要方面是（）A.数据复杂性和程序复杂性B.正确性和简明性C.空间复杂度和时间复杂度D.可读性和文档性正确答案:

C30.

(单选题)利用二叉链表存储树，则根结点的右指针是（）节。A.指向最左孩子B.指向最右孩子C.空D.非空正确答案:

C31.

(单选题)以下说法正确的是（）A.数据元素是数据的最小单位B.数据项是数据的基本单位C.数据结构是带有结构的各数据项的集合D.一些表面上很不相同的数据可以有相同的逻辑结构正确答案:

D32.

(单选题)用邻接表存储的图的广度优先遍历算法类似于二叉树的（）遍历。A.中序遍历B.先序遍历C.后序遍历D.层序遍历正确答案:

D33.

(单选题)已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（）A.O（n）B.O（m*n）C.O（min（m，n））D.O（max（m，n））正确答案:

D34.

(单选题)线性表（a1，a2，...，an）以链接方式存储时，访问第i位置上元素的时间复杂度为（）A.O（i）B.O（1）C.O（n）D.O（i-1）正确答案:

C35.

(单选题)栈和队列都是（）A.顺序存储的线性结构B.链式存储的非线性结构C.限制存取点的线性结构D.限制存取点的非线性结构正确答案:

C36.

(单选题)已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个存在的元素，则比较次数最多的（）次。A.4B.5C.6D.7正确答案:

B37.

(单选题)n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（）个非零元素。A.nB.2（n-1）C.n/2D.n2正确答案:

B38.

(单选题)从未排序序列中挑选元素，并将其依次放入已排序序列（初始时只有一个元素）的正确位置的方法，称为（）A.归并排序B.冒泡排序C.插入排序D.选择排序正确答案:

C39.

(单选题)将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）A.nB.2n-1C.2nD.n-1正确答案:

A40.

(单选题)在决定选取何种存储结构时，一般不考虑（）A.所用编程语言实现这种结构是否方便B.结点个数的多少C.对数据有哪些运算D.各结点的值如何正确答案:

D41.

(单选题)KMP算法的特点是在模式匹配时指示主串的指针（）A.不会变大B.不会变小C.都有可能D.无法判断正确答案:

B42.

(单选题)算法具有的五个重要特性是：有穷性，（），可行性，输入和输出。A.确定性B.可读性C.健壮性D.可维护性正确答案:

A43.

(单选题)含有n个顶点的连通有向图，其边的个数至多为（）A.nB.n（n+1）C.n（n-1）D.n（n-1）/2正确答案:

C44.

(单选题)设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。A.2nB.n+1C.2n-1D.2n+1正确答案:

C45.

(单选题)堆是一种（）排序。A.插入B.选择C.交换D.归并正确答案:

B46.

(单选题)两个串相等的充分必要条件是（）A.两串长度相等B.两串所包含的字符集合相等C.两串长度相等且对应字符相等D.两串长度相等且所包含的字符集合相等正确答案:

C47.

(单选题)表达式a*（b+c/d）的后缀表达式是（）A.abcd/+*B.abc+*d/C.abc*+d/D./+*abcd正确答案:

A48.

(单选题)链式存储结构中数据元素之间的逻辑关系是由（）表示的。A.线性结构B.非线性结构C.存储位置D.指针正确答案:

D49.

(单选题)对一棵折半查找的判定树进行中序遍历能得到（）A.任意序列B.递增序列C.递减序列D.递增递减交替序列正确答案:

B50.

(单选题)在有向图中每个顶点的度等于该顶点的（）A.入度B.出度C.入度与出度之和D.入度与出度之差正确答案:

C51.

(单选题)设一组初始记录关键字的长度为8，则最多经过（）趟插入排序可以得到有序序列。A.6B.7C.8D.9正确答案:

B52.

(单选题)向一个栈顶指针为top的链栈中插入一个p所指向的结点时，其操作步骤为（）A.top->next=p；B.p->next=top->next；top->next=p；C.p->next=top；top=p；D.p->next=top；top=top->next；正确答案:

C53.

(单选题)n（n>=2）个权值均不相同的字符构成赫夫曼树，关于该树的叙述中，错误的是（）A.该树是一棵完全二叉树B.树中一定没有度为1的结点C.树中两个权值最小的结点一定是兄弟结点D.树中任一非叶子结点的权值一定不小于下一层任一结点的权值正确答案:

A54.

(单选题)数组Q[n]用来表示一个循环队列，f为队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素个数的公式为（）A.r-fB.（n+f-r）%nC.n+r-fD.（n+r-f）%n正确答案:

D55.

(单选题)假定两个集合中的元素个数分别为m和n，用线性表实现求两个集合的交集的运算的时间复杂度为（）A.O（m+n）B.O（m-n）C.O（m*n）D.O（m2）正确答案:

C56.

(单选题)利用栈计算中缀表达式5*（8/2-3）+7时，当扫描到'）'时，OPTR栈中从栈底到栈顶的元素依次是（）A.#*（-B.#*（/-C.#（*/-D.#*/-正确答案:

A57.

(单选题)假设某电文仅有7个字母a，b，c，d，e，f，g组成，各个字母在电文中出现的频率分别为22，5，3，6，10，17，37，该哈夫曼树的带权路径长度为（）A.244B.246C.264D.276正确答案:

B58.

(单选题)一棵二叉树的先序序列和中序序列分别如下，后序序列：DCEBGIJHFA中序序列：CDBEAGFIHJ其先序序列为（）A.ABCDEFGHIJB.ACBDEFGHIJC.ACBDEFHGIJD.ABCEDFGHIJ正确答案:

A59.

(单选题)下列关于AOE网的叙述中，不正确的是（）A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动提前完成，那么整个工程将会提前完成正确答案:

B60.

(单选题)广义表（a，b，（c，d））的表尾是（）A.（c，d）B.（（c，d））C.b，（c，d）D.（b，（c，d））正确答案:

D61.

(单选题)以下算法的时间复杂度为（）voidfun（intn）{inti=1；while（i<=n）i=i*2；}A.O（n）B.O（n2）C.O（nlog2n）D.O（log2n）正确答案:

D62.

(单选题)基数排序的时间复杂度是（）A.O（n）B.O（n2）C.O（nlog2n）D.O（d（n+rd））正确答案:

D63.

(单选题)与单链表相比，双向链表的优点之一是（）A.插入、删除操作更方便B.可以进行随机访问C.可以省略表头指针或表尾指针D.访问前后相邻结点更灵活正确答案:

D64.

(单选题)顺序存储结构中数据元素之间的逻辑关系是由（）表示的。A.线性结构B.非线性结构C.存储位置D.指针正确答案:

C65.

(单选题)对于n阶对称矩阵压缩存储时，需要表长为（）的顺序表。A.n/2B.n*n/2C.n（n+1）/2D.n（n-1）/2正确答案:

C66.

(单选题)在做退栈运算时，应先判断栈是否（）A.空B.满C.上溢D.下溢正确答案:

A67.

(单选题)线性表是（）A.一个有限序列，可以为空B.一个有限序列，不可以为空C.一个无限序列，可以为空D.一个无限序列，不可以为空正确答案:

A68.

(单选题)线性表L=（a1，a2，……an），下列说法正确的是（）A.每个元素都有一个直接前驱和一个直接后继B.线性表中至少有一个元素C.表中诸元素的排列必须是由小到大或由大到小D.除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继正确答案:

D69.

(单选题)要连通具有n个顶点的有向图，至少需要（）条边。A.n-lB.nC.n+lD.2n正确答案:

B70.

(单选题)某算法的语句执行频度为（3n+nlog2n+n2+8），其时间复杂度表示（）A.O（n）B.O（nlog2n）C.O（n2）D.O（log2n）正确答案:

C71.

(单选题)线性表的顺序存储结构是一种（）A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.散列存取的存储结构正确答案:

A72.

(单选题)设有一顺序栈S，元素a，b，c，d，e，f依次进栈，如果6个元素的出栈顺序依次是b，d，c，f，e，a，则栈的容量至少是（）A.2B.3C.5D.6正确答案:

B73.

(单选题)下列程序段的时间复杂度是（）countt=0；for（k=1；k<=n；k*=2）for（j=1；j<=n；j++）count++；A.O（log2n）B.O（n）C.O（nlog2n）D.O（n2）正确答案:

C74.

(单选题)栈在（）中应用。A.递归调用B.子程序调用C.表达式求值D.A，B，C正确答案:

D75.

(单选题)设关键字序列为（Kl，K2，…，Kn），则用筛选法建初始堆必须从第（）个元素开始进行筛选。A.1B.nC.n/2D.n-1正确答案:

C76.

(单选题)在数据结构中，从逻辑上可以把数据结构分成（）A.线性结构和非线性结构B.内部结构和外部结构C.动态结构和静态结构D.紧凑结构和非紧凑结构正确答案:

A77.

(单选题)若串S=“software”，其子串的数目是（）A.8B.37C.36D.9正确答案:

B78.

(单选题)和顺序栈相比，链栈有一个比较明显的优势是（）A.通常不会出现栈满的情况B.通常不会出现栈空的情况C.插入操作更容易实现D.删除操作更容易实现正确答案:

A79.

(单选题)下述几种排序方法中，（）是稳定的排序方法。A.希尔排序B.快速排序C.归并排序D.堆排序正确答案:

C80.

(单选题)链表不具有的特点是（）A.插入、删除不需要移动元素B.所需空间与线性长度成正比C.不必事先估计存储空间D.可随机访问任一元素正确答案:

D81.

(单选题)链栈与顺序栈相比较，明显的优点是（）A.插入操作更加方便B.删除操作更加方便C.通常不会出现栈满的情况D.通常不会出现栈空的情况正确答案:

C82.

(单选题)带头结点的单链表h为空的判断条件是（）A.h==NULLB.h->next==hC.h->next==NULLD.h!=NULL正确答案:

C83.

(单选题)数据结构中评价算法的两个重要指标是（）A.效率、难度B.可行性、确定性C.正确性、稳定性D.时间复杂度、空间复杂度正确答案:

D84.

(单选题)以下数据结构中，（）是非线性结构。A.树B.字符串C.队列D.栈正确答案:

A85.

(单选题)在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入结点s，则执行（）A.s->next=p->next；p->next=s；B.p->next=s->next；s->next=p；C.q->next=s；s->next=p；D.p->next=s；s->next=q；正确答案:

C86.

(单选题)下列各种排序算法中平均时间复杂度为O（n2）是（）A.快速排序B.堆排序C.归并排序D.冒泡排序正确答案:

D87.

(单选题)按（）遍历二叉排序树得到的序列是一个有序序列。A.先序B.中序C.后序D.层次正确答案:

B88.

(单选题)设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）A.空或只有一个结点B.任一结点无左孩子C.任一结点无右孩子D.任一结点都无左孩子或者任一结点都无右孩子正确答案:

D89.

(单选题)连通分量是（）极大连通子图。A.图B.树C.有向图D.无向图正确答案:

D90.

(单选题)具有2017个结点的二叉树，其深度至少为（）A.9B.10C.11D.12正确答案:

C91.

(单选题)对于一个不带头结点的单链表head，判定空表的条件是（）A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL正确答案:

A92.

(单选题)设赫夫曼树中有199个结点，则该赫夫曼树中有（）个叶子结点。A.99B.100C.101D.102正确答案:

B93.

(单选题)设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）A.O（n）B.O（nlogn）C.O（1）D.O（n2）正确答案:

C94.

(单选题)一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用（）方法。A.快速排序B.堆排序C.插入排序D.二路归并排序正确答案:

B95.

(单选题)元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留，可出栈，直到所有的元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（）A.3B.4C.5D.6正确答案:

B96.

(单选题)二维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（）A.数据的元素处在行和列两个关系中B.数组的元素必须从左到右顺序排列C.数组的元素之间存在次序关系D.数组是多维结构，内存是一维结构正确答案:

D97.

(单选题)广义表（a，（b，c），d，e）的表尾为（）A.（b，c），d，eB.（（b，c），d，e）C.eD.（e）正确答案:

B98.

(单选题)算法分析的目的是（）A.分析算法的易懂性和文档性B.找出数据结构的合理性C.研究算法中的输入和输出的关系D.分析算法的效率以求改进正确答案:

D99.

(单选题)关键路径是AOE网中（）A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长回路D.最短回路正确答案:

A100.

(单选题)广义（a，（b，c），d，e）的表头为（）A.aB.bC.dD.e正确答案:

A101.

(单选题)无向图的邻接矩阵（）A.一定是对称的B.一定是不对称的C.不一定是对称的D.不一定是不对称的正确答案:

A102.

(单选题)下列哪一种图的邻接矩阵是对称矩阵（）A.AOV网B.AOE网C.有向图D.无向图正确答案:

D103.

(单选题)已知一棵完全二叉树的第6层（设根为第1层）有8个叶子结点，则该完全二叉树的结点个数最多是（）A.39B.52C.111D.119正确答案:

C104.

(单选题)有两个串p和q，求q在p中首次出现的位置的运算称为（）A.连接B.模式匹配C.求子串D.求串长正确答案:

B105.

(单选题)已知一个二叉树的先序序列是ABCDEFG，中序序列是BDCAFEG，则后序序列是（）A.DCBFGEAB.BCDFGEAC.BCDFEGAD.BDCFEGA正确答案:

A106.

(单选题)下面（）方法可以判定一个有向图是否有环。A.广度优先遍历B.拓扑排序C.求最短路径D.求最小生成树正确答案:

B107.

(单选题)以下算法中加下划线的语句的执行次数为（）intm=0，i，j；for（i=1；i<=n；i++）for（j=1；j<=2*i；j++）（）m++；A.nB.n（n+1）C.n+1D.n2正确答案:

B108.

(单选题)一个栈的输入序列为1，2，3，……，n，若输出序列的第一个元素是n，则输出序列的第i（1<=i<=n）个元素是（）A.不确定B.n-i+1C.iD.n-i正确答案:

B109.

(单选题)链接存储的存储结构所占存储空间（）A.分两部分，一部分存放结点值，另一部分存放表示结点关系的指针B.只有一部分，存放结点值C.只有一部分，存储表示结点间关系的指针D.分两部分，一部分存放结点值，另一部分存放结点所占单元数正确答案:

A110.

(单选题)单链表中，增加一个头结点的目的是为了（）A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储正确答案:

C111.

(单选题)一个顺序表所占用的存储空间大小与（）无关。A.表的长度B.数据元素的存放顺序C.数据元素的类型D.数据元素中各字段的类型正确答案:

B112.

(单选题)广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（）A.cB.b，cC.（b，c）D.（（b，c））正确答案:

D113.

(单选题)堆的形状是一棵（）A.二叉排序树B.满二叉树C.完全二叉树D.平衡二叉树正确答案:

C114.

(单选题)空格串是（①），其长度等于（②），正确选项是（）A.①空串②零B.①由一个或者多个空格组成的字符串②其包含的空格个数C.①空串②未定义D.①由一个或者多个空格组成的字符串②未定义正确答案:

B115.

(单选题)利用二叉链表存储树，则根结点的右指针是（）A.指向最左孩子B.指向最右孩子C.空D.非空正确答案:

C116.

(单选题)已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多的是（）A.4B.5C.6D.7正确答案:

B117.

(单选题)在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（）A.数据的操作方法B.数据元素的类型C.数据元素之间的关系D.数据的存取方法正确答案:

C118.

(单选题)在下列存储形式中，（）不是树的存储形式。A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法正确答案:

D119.

(单选题)下述几种排序方法中，要求辅助存储空间最大的是（）A.希尔排序B.快速排序C.归并排序D.堆排序正确答案:

C120.

(单选题)一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）A.不确定B.iC.n-i+1D.n-i正确答案:

C121.

(单选题)下列叙述中正确的是（）A.一个算法的空间复杂度大，则其时间复杂度也必定大B.一个算法的空间复杂度大，则其时间复杂度必定小C.一个算法的时间复杂度大，则其空间复杂度必定小D.上述三种说法都不对正确答案:

D122.

(单选题)下列说法不正确的是（）A.图的遍历是从给定的顶点出发，每一个顶点仅被访问一次B.图的深度优先遍历不适用于有向图C.遍历的基本方法有两种：深度优先搜索遍历和广度优先搜索遍历D.图的深度优先遍历是一个递归过程正确答案:

B123.

(单选题)下述关于排序的稳定性描述不正确的是（）A.归并排序是稳定的B.简单选择排序是不稳定的C.堆排序是不稳定的D.快速排序是稳定的正确答案:

D124.

(单选题)分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是（）算法。A.堆排序B.快速排序C.冒泡排序D.归并排序正确答案:

C125.

(单选题)若长度为n的线性表采用顺序存储结构，删除第i个数据元素时需要移动的数据元素个数为（）A.iB.n-iC.nD.n-i+1正确答案:

B126.

(单选题)在下列查找方法中，平均查找长度与结点个数n无关的查找方法是（）A.顺序查找B.折半查找C.分块查找D.散列查找正确答案:

D127.

(单选题)广义表（a，（b，c），（d，e））的表头为（）A.aB.（a）C.a，（b，c）D.（a，（b，c））正确答案:

A128.

(单选题)一个链表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则选用（）最节省时间。A.不带头结点的单循环链表B.双链表C.有尾指针的单循环链表D.单链表正确答案:

C129.

(单选题)设哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。A.99B.100C.101D.102正确答案:

B130.

(单选题)判断带头结点的单链表head为空的条件是（）A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL正确答案:

B131.

(单选题)下面关于串的叙述中，（）是不正确的。A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储正确答案:

B132.

(单选题)设主串的长度为m，子串的长度为n，那么简单的模式匹配算法的时间复杂度为（）A.O（m）B.O（n）C.O（m*n）D.O（m+n）正确答案:

C133.

(单选题)抽象数据类型的三个组成部分分别为（）A.数据对象、数据关系和基本操作B.数据元素、逻辑结构和存储结构C.数据项、数据元素和数据类型D.数据元素、数据结构和数据类型正确答案:

A134.

(单选题)下列哪种算法是求单源点最短路径的算法（）A.PrimB.CruscalC.FloydD.Dijkstra正确答案:

D135.

(单选题)从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）A.希尔排序B.冒泡排序C.插入排序D.选择排序正确答案:

C136.

(单选题)下述哪一条是顺序存储结构的优点（）A.存储密度大B.插入运算方便C.删除运算方便D.方便地运用于各种逻辑结构的存储表示正确答案:

A137.

(单选题)若串S="software"，则字符其子串的数目是（），其中空串和S串本身这两个字符串也算作S的子串。A.8B.36C.37D.16正确答案:

C138.

(单选题)与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）A.存储结构B.存储实现C.逻辑结构D.运算实现正确答案:

C139.

(单选题)计算机算法指的是（）A.计算方法B.调度方法C.解决问题的有限运算序列D.排序方法正确答案:

C140.

(单选题)已知一棵二叉树的先序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）A．CBEFDAB．FEDCBAC．CBEDFAD．不定A.CBEFDAB.FEDCBAC.CBEDFAD.不定正确答案:

A141.

(单选题)数据结构在计算机内存中的表示是指（）A.数据的逻辑结构B.数据元素之间的关系C.数据的存储结构D.数据关系正确答案:

C142.

(单选题)下面关于哈希（Hash，杂凑）查找的说法正确的是（）A.哈希函数构造的越复杂越好，因为这样随机性好，冲突小B.除留余数法是所有哈希函数中最好的C.不存在特别好与坏的哈希函数，要视情况而定D.若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可正确答案:

C143.

(单选题)下面说法不正确的是（）A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C.广义表难以用顺序结构存储D.广义表可以是一个多层次的结构正确答案:

A144.

(单选题)已知一个二叉树的先序序列是ABCDEFG，后序序列是DCBFGEA，则中序序列是（）A.BDCAEFGB.BCDAFEGC.BDCAFEGD.BCDAFGE正确答案:

C145.

(单选题)具有2012个结点的二叉树，其深度至少为（）A.9B.10C.11D.12正确答案:

C146.

(单选题)对于单链表表示法，以下说法错误的是（）A.数据域用于存储线性表的一个数据元素B.指针域或链域用于存储一个指向本结点的直接后继结点的指针C.所有数据通过指针的链接而组织成单链表D.NULL称为空指针，它不指向任何结点，只起标志作用正确答案:

C147.

(单选题)在带头结点的循环链表中，将头指针改设为尾指针（rear）后，其首元结点和尾结点的存储位置分别是（）A.rear和rear->next->nextB.rear->next和rearC.rear->next->next和rearD.rear和rear->next正确答案:

C148.

(单选题)关于线性表的下列说法正确的是（）A.每个元素都有一个直接前驱和一个直接后继B.线性表中至少有一个元素C.表中诸元素的排列顺序必须是由小到大或由大到小D.除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前驱和直接后继正确答案:

D149.

(单选题)链式栈结点为（data，next），top指向栈顶，若想删除栈顶结点，并将删除结点的值保存到x中，则应执行的操作（）A.x=top->data；top=top->next；B.top=top->next；x=top->data；C.x=top；top=top->next；D.x=top->data；正确答案:

A150.

(单选题)栈操作数据的原则是（）A.先进先出B.后进先出C.后进后出D.不分顺序正确答案:

B151.

(单选题)若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双向链表D.仅有尾指针的单循环链表正确答案:

D152.

(单选题)设有二维数组A[0..9，0..19]，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6，6]存储地址为（）A.232B.241C.352D.332正确答案:

C153.

(单选题)下面给出的四种排序方法中，排序过程中的比较次数与初始序列无关的是（）A.简单选择排序法B.插入排序法C.快速排序法D.堆排序法正确答案:

A154.

(单选题)栈在（）中有所应用。A.递归调用B.函数调用C.表达式求值D.前三个选项都有正确答案:

D155.

(单选题)（）不是栈的基本操作。A.判断栈是否为空B.将栈置为空栈C.删除栈顶元素D.删除栈底元素正确答案:

D156.

(单选题)若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A.9B.11C.15D.不确定正确答案:

B157.

(单选题)设栈S和队列Q的初始状态为空，元素1，2，3，4，5和6依次进入栈S，一个元素出栈后立即进入Q，若6个元素的出队序列是2，4，3，6，5，1，则栈S的容量至少应用是（）A.2B.3C.4D.6正确答案:

B158.

(单选题)设栈S元素和队列Q的初始状态均为空，元素abcde依次通过栈S，若每个元素出栈后立即进入队列Q，且5个元素的出队顺序是bdcae，则栈S的容量至少是（）A.6B.4C.3D.2正确答案:

C159.

(单选题)下面关于串的的叙述中，哪一个是不正确的（）A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储正确答案:

B160.

(单选题)下列关于无向连通图特性的叙述中，正确的是（）I.所有顶点的度数之和是偶数II.边数大于顶点个数减1III.至少有一个顶点的度为1A.只有IB.只有IIC.I和IID.I和III正确答案:

A161.

(单选题)对于一个带头结点的单循环链表head，判定空表的条件是（）A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL正确答案:

C162.

(单选题)将一棵有200个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为（）A.97B.98C.99D.100正确答案:

C163.

(单选题)从逻辑上可以把数据结构分为（）两大类。A.动态结构、静态结构B.线性结构、非线性结构C.顺序结构、链式结构D.初等结构、构造型结构正确答案:

B164.

(单选题)若森林F有15条边，25个结点，则F包含的树的个数是（）A.8B.9C.10D.11正确答案:

C165.

(单选题)线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以正确答案:

D166.

(单选题)若数据序列{11，12，13，7，8，9，23，4，5}是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（）A.冒泡排序B.插入排序C.选择排序D.归并排序正确答案:

B167.

(单选题)广义表（（a，b），c，（d，e））的表头为（）A.aB.（a，b）C.a，bD.（（a，b），c）正确答案:

B168.

(单选题)基数排序是（）A.利用多逻辑关键字排序的思想对单逻辑关键字进行排序B.利用多逻辑关键字排序的思想对多逻辑关键字进行排序C.利用单逻辑关键字排序的思想对多逻辑关键字进行排序D.利用单逻辑关键字排序的思想对单逻辑关键字进行排序正确答案:

A169.

(单选题)设赫夫曼编码的长度不超过4，若已对两个字符编码为1和01，则还最多可对（）个字符编码。A.2B.3C.4D.5正确答案:

C170.

(单选题)顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）A.O（n）B.O（n2）C.O（n1/2）D.O（1og2n）正确答案:

A171.

(单选题)一个广义表为（a，（a，b），d，e，（（i，j），k）），则该广义表的长度为（）A.不确定B.8C.5D.6正确答案:

C172.

(单选题)设计一个判别表达式中左、右括号是否配对出现的算法，采用（）数据结构最佳。A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈正确答案:

D173.

(单选题)有向图的邻接矩阵（）A.一定是对称的B.一定是不对称的C.有可能是对称的D.以上答案都不对正确答案:

C174.

(单选题)在下述结论中，正确的是（）①只有一个结点的二叉树的度为0；②二叉树的度为2；③二叉树的左右子树可任意交换；④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.②③④C.②④D.①④正确答案:

D175.

(单选题)以下数据结构中，（）是非线性数据结构。A.字符串B.队列C.树D.栈正确答案:

C176.

(单选题)设哈希表长为14，哈希函数是H（key）=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）A.8B.3C.5D.9正确答案:

D177.

(单选题)线性表L在（）情况下适用于链式结构实现。A.需经常修改L中的结点值B.需不断对L进行删除插入C.L中含有大量的结点D.L中结点结构复杂正确答案:

B178.

(单选题)用邻接表存储的图的深度优先遍历算法类似于二叉树的（）遍历。A.中序遍历B.先序遍历C.后序遍历D.层序遍历正确答案:

B179.

(单选题)当栈中元素为n个，做进栈运算时发生溢出，则说明栈的最大容量为（）A.nB.n-1C.n+1D.n/2正确答案:

A180.

(单选题)某内排序方法的稳定性是指（）A.该排序算法不允许有相同的关键字记录B.该排序算法允许有相同的关键字记录C.平均时间为0（nlogn）的排序方法D.以上都不对正确答案:

D181.

(单选题)线性表是具有n个（）的有限序列。A.表元素B.字符C.数据元素D.数据项正确答案:

C182.

(单选题)链式栈结点为（data，link），top指向栈顶，若想摘除栈顶结点，并将删除的结点的值保存到x中，则应执行操作（）A.x=top->data；top=top->link；B.top=top->link；x=top->link；C.x=top；top=top->link；D.x=top->link；正确答案:

A二.多选题（共23题）1.

(多选题)以下哪些是图的分类A.无向图B.有向图C.加权图D.无权图正确答案:

ABCD2.

(多选题)从逻辑上可以把数据结构分为（）A.动态结构B.线性结构C.链式结构D.非线性结构正确答案:

BD3.

(多选题)以下关于指针变量的叙述中，正确的有（）A.指针变量可赋值为0B.指针变量中存放的是地址值C.指针可以进行加、减等算术运算D.指针变量不占用存储空间正确答案:

ABC4.

(多选题)线索二叉树的作用包括（）A.方便遍历B.节省存储空间C.加快查找速度D.便于插入和删除操作正确答案:

AC5.

(多选题)下面说法正确的是（）A.算法原地工作的含义是指不需要任何辅助空间B.在相同的规模n下，时间复杂度为O（n）的算法在执行时间上一定比时间复杂度为O（nlogn）的算法快C.最坏时间复杂度是指算法在最坏情况下执行时间的上界D.可读性好的算法有助于人们对算法的理解和交流正确答案:

CD6.

(多选题)对于哈夫曼编码，以下说法正确的是（）A.哈夫曼编码是一种不等长编码B.哈夫曼编码是前缀编码C.出现频率高的字符编码短D.可以通过构建哈夫曼树来生成编码正确答案:

ABCD7.

(多选题)线索二叉树的线索化过程主要包括（）A.先序线索化B.中序线索化C.后序线索化D.层次线索化正确答案:

ABC8.

(多选题)关于二叉树的说法，正确的是（）A.二叉树可以为空树。B.二叉树中结点的度都为2C.二叉树中结点的度可以为0，1，2D.二叉树的高度是指二叉树中结点的个数正确答案:

AC9.

(多选题)二叉树的性质包括（）A.第i层最多有2^(i-1)个结点（i≥1）B.深度为k的二叉树最多有2^k-1个结点（k≥1）C.对于任何一棵二叉树，如果其叶结点数为n₀，度为2的结点数为n₂，则n₀=n₂+1D.具有n个结点的完全二叉树的深度为⌈log₂(n+1)⌉正确答案:

ABCD10.

(多选题)数据之间的运算包括（）A.插入B.删除C.查找D.更新和排序正确答案:

ABCD11.

(多选题)如何将字符串转换为数值A.先用数值的valueOf函数将字符串转换为数值类对象，再利用该对象的intValue或doubleValue等函数将数值类对象转换为数值B.利用数值类的parseInt，parseDouble等函数将字符串直接转换为数值C.利用数值类的静态函数valueOf将字符串转换为数值D.利用数值类的静态函数intValue将字符串转换为数值正确答案:

AB12.

(多选题)以下有关结构体数组的说法中，正确的有（）A.结构体数组中的每个元素都是结构体类型B.结构体数组也可初始化C.指针可以指向结构体变量,但不可以指向结构体数组D.结构体数组在内存中是连续存放的正确答案:

ABD13.

(多选题)二叉树的遍历方式有（）A.先序遍历B.中序遍历C.后序遍历D.层次遍历正确答案:

ABCD14.

(多选题)算法的特征包括（）A.无穷性B.确定性C.有效性D.有零个或多个输入正确答案:

BCD15.

(多选题)（）属于特殊矩阵A.对角矩阵B.上三角矩阵C.下三角矩阵D.稀疏矩阵正确答案:

ABC16.

(多选题)算法的基本特征有（）A.有穷性B.确定性C.可行性D.输入和输出正确答案:

ABCD17.

(多选题)算法的时间复杂度取决于（）A.问题的规模B.待处理数据的初始状态C.内存的大小D.操作系统的选择正确答案:

AB18.

(多选题)以下哪些属于索引顺序文件可能出现的问题A.索引需要占用额外的存储空间B.数据更新时维护索引的开销较大C.索引结构若不合理可能导致查找效率降低D.完全杜绝了数据丢失风险正确答案:

ABC19.

(多选题)下面不可以声明字符串类型的是()A.boolB.floatC.stringD.int正确答案:

ABD20.

(多选题)非空二叉树的基本组成单元包括（）A.根结点B.左子树C.右子树D.空指针正确答案:

ABC21.

(多选题)树的存储结构可以有（）A.双亲表示法B.孩子表示法C.孩子兄弟表示法D.顺序存储结构正确答案:

ABC22.

(多选题)以下数据结构中，（）是线性结构。A.树B.字符串C.线性表D.栈正确答案:

BCD23.

(多选题)数据元素也称为（）A.元素B.结点C.顶点D.记录正确答案:

ABCD三.填空题（共15题）1.

(填空题)设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[]中，A[0][0]存入B[0]中，则A[8][5]在B[]中的下标为（）正确答案:

(1)412.

(填空题)数据结构从逻辑上划分为四种基本类型：线性结构、树形结构、图状结构和（）正确答案:

(1)集合3.

(填空题)一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。这个数组的体积是（）个字节。正确答案:

(1)2884.

(填空题)平衡二叉树上所有结点的平衡因子只可能是0，1和（）正确答案:

(1)-15.

(填空题)串‘science’的非空子串有（）个。正确答案:

(1)266.

(填空题)设某棵完全二叉树中有100个结点，则该二叉树中有（）个叶子结点。正确答案:

(1)507.

(填空题)已知一个长度为13的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多的是（）正确答案:

(1)48.

(填空题)设线性表中有n个数据元素，则在在链式存储结构上实现顺序查找的平均时间复杂度为（）正确答案:

(1)O（n）9.

(填空题)设数组a[0..10，1..8]的基地址为2000，每个元素占4个字节，若以行序为主序顺序存储，则元素a[4，6]的存储地址为（）正确答案:

(1)214810.

(填空题)设有二维数组A[0..9，0..19]，其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6，6]存储地址为（）正确答案:

(1)23211.

(填空题