数据结构选择填空题

数据结构（语言版）选择、填空题C—概论选择

1、（）是数据的基本单位、数据结构AB、数据元素C、数据项D、数据类型

2、以下说法不正确的是（）A、数据结构就是数据之间的逻辑结构B、数据类型可看成是程序设计语言中已实现的数据结构C、数据项是组成数据元素的最小标识单位D、数据的抽象运算不依赖具体的存储结构

3、学习数据结构主要目的是（）A、处理数值计算问题B、研究程序设计技巧C、选取合适数据结构，写出更有效的算法D、是计算机硬件课程的基础

4、普通而言，最适合描述算法的语言是（）、自然语言AB、计算机程序语言C、介于自然语言和程序设计语言之间的伪语言D、数学公式

5、通常所说的时间复杂度指（）、语句的频度和AB、算法的时间消耗C、渐近时间复杂度D、最坏时间复杂度

6、A算法的时间复杂度为0（rT3）,B算法的时间复杂度为0（2词,则说明（）A、对于任何数据量，A算法的时间开消都比B算法小B、随着问题规模n的增大，A算法比B算法有效C、随着问题规模n的增大，B算法比A算法有效D、对于任何数据量，B算法的时间开消都比A算法小填空

1、数据的（）结构依赖于计算机语言.

2、数据的逻辑结构可分为线性结构和（）结构

3、算法的时间复杂度与问题的规模有关外，还与输入实例的（）有关

4、常用的四种存储方法是什么

5、常见的数据的逻辑结构有哪两种

6、普通，将算法求解问题的输入量称为（）二线性表选择题

1、以下关于线性表的说法不正确的是（）A、线性表中的数据元素可以是数字、字符、记录等不同类型D.B树和B+树都能有效地支持随机检索

5、以下关于ISAM文件的说法中，错误的是（）A、她的中文含义是索引顺序存储方法B、专为磁盘存取文件设计C、采用静态索引结构D、删除记录操作比插入记录操作复杂

6、散列文件的基本存储单位是（）、物理记录AB、页块C、逻辑记录D、桶填空

1、性质相同的记录的集合称（）

2、文件的逻辑结构是一种（）结构

3、文件上的主要操作为（）

4、衡量文件操作质量的重要标志是（）

5、顺叙文件的的主要优点是（）存取速度快

6、索引文件由（）组成B、线性表中包含的数据元素个数不是任意的C、线性表中的每一个结点都有且惟独一个直接前趋和直接后继D、存在这样的线性表表中各结点都没有直接前趋和直接后继

2、线性表的顺序存储结构是一种（）的存储结构、随机存取AB、顺序存取C、索引存取D、散列存取

3、在顺序表中，只要知道（），就可在相同时间内求出任一结点的存储地址、基地址AB、结点大小C、向量大小D、基地址和结点大小

4、在等概率情况下，顺序表的插入操作要挪移（）结点A、全部B、一半C、三分之一D、四分之一

5、在（）运算中，使用顺序表比链表好Av插入B、删除C、根据序号查找D、根据元素值查找

6、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）A、0

（1）B、0（n）C、0（rT2）D、0（Iog2n）填空题

1、线性表是一种典型的（）结构

2、在一个长度为n的顺序表中删除第i个元素，要挪移（）个元素

3、如果要在第i个元素前插入一个元素，要后移（）个元素

4、采用（）存储结构的线性表叫顺序表

5、顺序表中逻辑上相邻的元素的物理位置（）

6、在无头结点的单链表中，第1个结点的地址存放在头指针中，其他结点的存储地址存放在（）结点的next域中三栈和队列选择

1、栈与普通的线性表的区别在于（）A、数据元素的类型不同B、运算是否受限制C、数据元素的个数不同D、逻辑结构不同

2、一个栈的入栈序列是abode,则栈的不可能的输出序列是（）A EdcbaB、decba C、dceab D、abodes

3、在对栈的操作中，能改变栈的结构的是（）Ax InitStack（S）B、StackEmpty（S）C\StackTop（S）D、StackFulI（S）

4、顺序栈的类型定义如下typedef maxs i ze64;typedef struct{i ntdata[maxs ize];int top;}seqstack;seqstack*s;顺序栈s栈满条件是（）（A）s-top0（B）s-top-maxs ize（C）s-top-maxs ize-1（D）S-top!=maxsize

5、向一个栈顶指针为HS的链栈中将一个S指针所指的结点入栈，执行（）oAx HS-next=s;B、S-next=HS-next;HS-next=s;C、S-next=HS-next;HS=s;D、S-next=HS;HS=HS-next;

6、若已知一个栈的入栈序列是1,2,3,n,其输出序列是p1,p2,p3,■■,pn,若p1=n,则pi=（）oA、IB、n-IC\n-i+1D、不确定填空

1、在栈中，可进行插入和删除操作的一端称（）

2、在栈的出栈操作中，要先判断栈是否空，否则会产生（）现象

3、当程序中同时使用（）个栈时，让它们共享同一向量空间可减少上溢的发生

4、栈的特点是（）

5、由于链栈的操作只在链表头部进行，所以没有必要设置（）结点

6、若内存空间充足，（）栈可不定义栈满运算四串选择

1、串是一种特殊的线性表，其特殊性体现在（）A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符

2、有两个串P和Q,求P和Q中首此浮现的位置的运算称（）、连接AB、模式匹配C、求子串D、求串长

3、设串s仁ABCDEFG,s2=PQRST,函数conx,y返回x和y串的连接串,subs s,I,j返回串s的从序号i的字符开始的j个字符组成的子串，lens返回串s的长度,则consubss1,2,Iens2,subss1,16口化2,2的结果串是、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEFA

4、在串的模式匹配中，普通A、有效位移的个数大于合法位移的个数B、有效位移的个数等于合法位移的个数C、有效位移的个数小于合法位移的个数D、有效位移和合法位移无关

5、顺序串中，根据空间分配方式的不同，可分为A、直接分配和间接分配B、静态分配和动态分配C、顺序分配和链式分配D、随机分配和固定分配填空3在空串和空格串中，长度不为0的是

2、按存储结构不同，串可分为

3、C语言中，以字符表示串值的终结

4、在链串中，为了提高存储密度，应该增大.

5、假设每一个字符占1个字节，若结点大小为4的链串的存储密度为50%,则其每一个指针占个字节五多维数组和广义表选择

1、稀疏矩阵的普通的压缩方法有、二维数组B、广义表C、三元组表D、一维数组A

2、设矩阵A是一个对称矩阵，为了节省空间，将其下三角部份按行优先存放在一维数组B中对下三角矩阵中任一元素aij设矩阵A是一个对称矩阵，为了节省空间，将其下三角部份按行优先存放在一维数组B中，对下三角矩阵中任一元素aiji=j,在一维数组B中下标K的值是、\i-1/2+j-1B、i i-1/2+j Cxi i+1/2+j-1D、i i+1/2+jA

3、在稀疏矩阵的三元组表表示法中，每一个三元组表示A矩阵中数据元素的行号、列号和值B矩阵中非零元素的值矩阵中非零元素的行号和列号D矩阵中非零元素的行号、列号和值

4、对稀疏矩阵进行压缩存储是为了A便于进行矩阵运算B便于输入和输出节约存储空间D降低运算的时间复杂度

5、广义表是线性表的推广，它们之间的区别在于、能否使用子表AB、能否使用原子项C、表的长度D、是否能为空

6、在广义表中，限制了表中成份递归，但没有限制共享的是（）A、纯表B、再入表C、递归表D、线性表填空

1、n维数组中的每一个元素都最多有（）个直接前趋

2、对于一个一维数组A

[12],若一个数据元素占用字节数为S,首地址为1,则A[i]（i=0）的存储地址为（A）,若首地址为D,则A[i]的存储地址为（B）o

3、已知二维数组采用行优先顺序存储，每一个元素占k个存储单元，并且第一个元素的存储地址LOC（A

[0]

[0]）,则的地址是（）

4、在多维数组中，数据元素的存放地址直接可通过地址计算公式计算出因此，数组是一种（）存取结构

5、矩阵的压缩存储就是为多个相同的非零元素分配（）个存储空间，不为零元素分配空间

6、普通，特殊矩阵按规律压缩存储到一个向量中后，能（）存取六树选择题

1、在树中，互为堂兄弟的结点拥有相同的（）A\双亲B、祖先C、路径D、孩子

2、树最适合用来表示、有序数据元素AB、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据

3、已知二叉树如下图所示，此二叉树的顺序存储结构是（）OA/OCOF OGA、1234D、

012344、在一棵高度为h的满四叉树中，结点总数为（）o、4-h-1AB、h-1）/2«C、h-1）/4«D、＜h

5、若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（）A.9B.11C.12D.不确定

6、按二叉树的定义，具有3个结点的二叉树有（）种、3B、4C、5D、6A填空

1、在树中，度为（）的结点称为叶子

2、在树中，除跟结点外，其他结点都有且惟独一个（）结点

3、有100个结点的树有（）条边

4、若将树中的每一个结点的各子树看成从左到右有次序，则该树为（）树

5、一棵二叉树有67个结点，这些结点的度要末是0,要末是2这棵二叉树中度为2的结点有（）O个

6、深度为K的彻底二叉树至少有2XkT）个结点，至多有2Fk7）-2个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是（）七图选择

1、设G仁（V1,E1）和G2=（V2,E2）为两个图,如果V2包含V1,E2包含E1,则称（）、G1是G2的子图AB、G1是G2的连通分量C、G2是G1的连通分量D、G2是G1的子图

2、设有6个结点的无向图，该图至少应有（）条边才干确保是一个连通图A、5B、6C、7D、

83、下面关于图的存储的叙述中，哪一个是正确的（）A.用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，与边数无关B.用邻接矩阵法存储图，占用的存储空间数只与图中边数有关，与结点个数无关C.用邻接表存储图，占用的存储空间数只与图中结点个数有关，与边数无关D.用邻接表存储图，占用的存储空间数只与图中边数有关，与结点个数无关

4、在图的表示法中，表示形式惟一的是（）A、邻接矩阵表示法B、邻接表表示法C、逆邻接表表示法D、邻接表和逆邻接表表示法

5、（）适合用邻接表表示A、稠密图B、有向彻底图C、无向彻底图D、稀疏图

6、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（）.

（1）A、N B.n+1C.n-1D.n+e填空

1、具有n个顶点的有向图最多有（）条边

2、具有n个顶点的强连通图至少有（）条边

3、有向图的邻接表表示适于求顶点的（）

4、有向图的邻接矩阵表示中，第i（）上非零元素的个数为顶点vi的入度

5、对有向图进行深度优先搜索时，若该图不是（），可得到一个深度优先搜索生辰森林

6、当对用（）表示法表示的图，从某指定顶点作为初始点进行广度优先搜索，得到的广度优先搜索序列惟一八排序选择

1、内部排序和外部排序的区别不在于（）A、待排叙文件的大小B、有无内外存的交换C、是否在内存中排序D、可采用的排序策略评价排序算法好坏的标准主要是（）

2、、执行时间AB、辅助空间C、算法本身的复杂度D、执行时间和所需的辅助空间

3、“就地排序”指排序中，需要的辅助空间为（）o、0

（1）AB、0C、0（n）D、0（r2）

4、一个待排叙文件的关键字如下265301751129937863742694076438经过（）趟直接插入排序后可得到如下序列129265301751937863742694076438A1B2C3D4若用冒泡排序对关键字序列{18,16,14,12,10,8}进行从小到大的排序，所要进行的关

5、键字比较总次数为（）、10AB、15C、21D、

346、用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，结点序列的变化情况如下20152125472768358415202125352747688441520212527354768841258421471527683520那末，所采用的排序方法是（）、直接插入排序B、希尔排序C、冒泡排序D、快速排序A填空

1、若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变则这种排序方法是（）的排序方法

2、当增量为1时，该趟希尔排序与（）排序基本一致

3、最坏情况，在第i趟直接插入排序中，要进行（）次关键字的比较

4、两个序列如下L1={25,57,48,37,92,86,12,33}L2={25,37,33,12,48,57,86,92}用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列（）

5、在（）堆中，所有双亲结点的关键字的值大于它们孩子的关键字的值

6、直接选择排序的总的关键字比较次数与（）无关九查找选择

1、通常把查找过程中对关键字需要执行的（）作为衡量一个查找算法效率优劣的标准、BSTAB、WPLC、ASLD、BFS

2、用二分法在有序表{3,4,10,13,33,42,46,63,76,78,95,96,120}中查找95时,要进行的比较次数为（）A、2B、3C、4D、

53、线性表必须是（），才干进行二分查找A、用向量存储的线性表B、用链表存储的有序表C、用链表存储的线性表D、用向量存储的有序表

4、二分查找过程可以用

（1）树描述，该树的形态只与⑵有关A1-二叉查找树2-表中元素个数B1-二叉判定树2-表中元素关键字的取值C1-二叉比较树2-表中元素个数D1-二叉树2-表中元素关键字的取值

5、长度为12的按关键字有序的查找表采用顺序组织方式，若用二分查找方法，则在等概率情况下，查找不成功的平均查找长度是（）、37/12B、63/13C、39/12D、49/13A

6、在表长是N的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数（）A、N B、1C、N+1D、N-1填空

1、若在查找的同时对表作修改，则相应的表称（）

2、对表长为n的链表进行顺序查找，等概率情况下，查找成功的平均查找长度是（）

3、对表长为n的顺序表进行分块查找，若以顺序查找确定块且每块长度为s,则在等概率查找的情况下，查找成功时的平均查找长度为（）

4、一个线性表中共有625个元素，假定每一个元素的查找概率相同，如果采用分块查找，则对这些元素共分为（）个索引块为最佳（基本查找方法都采用顺序查找）

5、在分块查找方法中，首先查找索引表,然后再用顺序查找方法查找相应的（）、当二叉排序树为（）时，其平均查找长度最好6十文件选择

1、通常，磁带只适合用于存储（）文件A、顺序B、索引C、散列D、多关键字

2、对于存储在磁盘上的顺叙文件的记录进行直接存取是根据（）、逻辑记录号AB、逻辑记录结构C、逻辑记录的内容D、逻辑关键字

3、存储在磁带上的顺叙文件的查找只能用（）、顺序查找AB、二分查找C、分块查找D、树表查找

4、下面关于B树和B+树的叙述中，不正确的是A.B树和B+树都是平衡的多分树B.B树和B+树都是可用于文件的索引结构C.B树和B+树都能有效地支持顺序检索。