数据结构选择填空题.docx

数据结构（C语言版）选择、填空题概论选择1、（）是数据的基本单位。A、数据结构B、数据元素C、数据项D、数据类型2、以下说法不正确的是（）。A、数据结构就是数据之间的逻辑结构。B、数据类型可看成是程序设计语言中已实现的数据结构。C、数据项是组成数据元素的最小标识单位。D、数据的抽象运算不依赖具体的存储结构。3、学习数据结构主要目的是（）。A、处理数值计算问题B、研究程序设计技巧C、选取合适数据结构，写出更有效的算法。D、是计算机硬件课程的基础。4、普通而言，最适合描述算法的语言是（）。A、自然语言B、计算机程序语言C、介于自然语言和程序设计语言之间的伪语言D、数学公式5、通常所说的时间复杂度指（）。A、语句的频度和B、算法的时间消耗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、 散列文件的基本存储单位是（）。A、物理记录B、页块C、逻辑记录D、桶填空1、 性质相同的记录的集合称（）。2、 文件的逻辑结构是一种（）结构。3、 文件上的主要操作为（）。4、衡量文件操作质量的重要标志是（）。5、 顺叙文件的的主要优点是（）存取速度快。6、索引文件由（）组成B、线性表中包含的数据元素个数不是任意的。C、线性表中的每一个结点都有且惟独一个直接前趋和直接后继。D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。2、线性表的顺序存储结构是一种（）的存储结构。A、随机存取B、顺序存取C、索引存取D、散列存取3、在顺序表中，只要知道（），就可在相同时间内求出任一结点的存储地址。A、基地址B、结点大小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,则栈的不可能的输出序列是（）。As Edcba B、 decba C、 dceab D、 abode3、在对栈的操作中，能改变栈的结构的是（）。Ax InitStack （S）B、 StackEmpty（S）C StackTop（S）D、 StackFulI（S）4、顺序栈的类型定义如下：typedef maxs i ze 64;typedef struct i nt datamaxs i ze;int top;seqstack;seqstack *s;顺序栈s栈满条件是（）。（A）s->top<>0（B） s->top-maxs i ze（C） s->top-maxs i ze-1（D）S->top!=maxs i ze5、向一个栈顶指针为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中首此浮现的位置的运算称（）。A、连接B、模式匹配C、求子串D、求串长3、 设串s仁'ABCDEFG',s2='PQRST',函数con(x,y)返回x和y串的连接串,subs (s, I, j)返回串 s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度,则 con(subs(s1,2, Ien(s2),subs(s1, 16口化2),2)的结果串是()。 A、BCDEF B、BCDEFG C、 BCPQRST D、 BCDEFEF4、在串的模式匹配中，普通()。A、有效位移的个数大于合法位移的个数B、有效位移的个数等于合法位移的个数C、有效位移的个数小于合法位移的个数D、有效位移和合法位移无关5、顺序串中，根据空间分配方式的不同，可分为()。A、直接分配和间接分配B、静态分配和动态分配C、顺序分配和链式分配D、随机分配和固定分配填空3在空串和空格串中，长度不为0的是()。2、按存储结构不同，串可分为()。3、C语言中，以字符()表示串值的终结。4、在链串中，为了提高存储密度，应该增大().5、假设每一个字符占1个字节，若结点大小为4的链串的存储密度为50%,则其每一个指针占( )个字节。五多维数组和广义表选择1、稀疏矩阵的普通的压缩方法有()。A、二维数组B、广义表C、三元组表D、一维数组2、 设矩阵A是一个对称矩阵，为了节省空间，将其下三角部份按行优先存放在一维数组B中。 对下三角矩阵中任一元素aij (设矩阵A是一个对称矩阵，为了节省空间，将其下三角部份 按行优先存放在一维数组B中，对下三角矩阵中任一元素aij(i>=j),在一维数组B中下标 K的值是()。A、 (i-1)/2+j-1 B、 i (i-1)/2+j Cx i (i+1)/2+j-1 D、 i (i+1)/2+j3、在稀疏矩阵的三元组表表示法中，每一个三元组表示()。(A)矩阵中数据元素的行号、列号和值(B)矩阵中非零元素的值矩阵中非零元素的行号和列号(D)矩阵中非零元素的行号、列号和值4、对稀疏矩阵进行压缩存储是为了()。(A)便于进行矩阵运算(B)便于输入和输出节约存储空间(D)降低运算的时间复杂度5、广义表是线性表的推广，它们之间的区别在于()。A、能否使用子表B、能否使用原子项C、表的长度D、是否能为空6、在广义表中，限制了表中成份递归，但没有限制共享的是（）。A、纯表B、再入表C、递归表D、线性表填空1、 n维数组中的每一个元素都最多有（）个直接前趋。2、对于一个一维数组A12,若一个数据元素占用字节数为S,首地址为1,则Ai（i>=0）的 存储地址为（A ）,若首地址为D,则Ai的存储地址为（B ）o3、 已知二维数组采用行优先顺序存储，每一个元素占k个存储单元，并且第一个元素 的存储地址LOC （A0 0）,则的地址是（）。4、在多维数组中，数据元素的存放地址直接可通过地址计算公式计算出。因此，数组是一种（） 存取结构。5、矩阵的压缩存储就是为多个相同的非零元素分配（）个存储空间，不为零元素分配空间。6、 普通，特殊矩阵按规律压缩存储到一个向量中后，能（）存取。六树选择题1、在树中，互为堂兄弟的结点拥有相同的（）。A双亲B、祖先C、路径D、孩子2、 树最适合用来表示。A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据3、 已知二叉树如下图所示，此二叉树的顺序存储结构是：（）。OA/OCOf OgA、12 3 4D、0 12 3 44、在一棵高度为h的满四叉树中，结点总数为（）oA、4-h-1B、«h-1）/2C、«h-1）/4D、h5、 若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（）。A. 9B. 11C. 12D.不确定6、按二叉树的定义，具有3个结点的二叉树有（）种。 A、3 B、4 C、5 D、6填空1、在树中，度为（）的结点称为叶子。2、在树中，除跟结点外，其他结点都有且惟独一个（）结点。3、 有100个结点的树有（）条边。4、 若将树中的每一个结点的各子树看成从左到右有次序，则该树为（）树。5、 一棵二叉树有67个结点，这些结点的度要末是0,要末是2O这棵二叉树中度为2的结点有 （）个。6、 深度为K的彻底二叉树至少有2XkT）个结点，至多有2Fk7）-2个结点，若按自上而下， 从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是（）。七图选择1、 设G仁（V1,E1）和G2=（V2,E2）为两个图,如果V2包含V1, E2包含E1,则称（）。A、G1是G2的子图B、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+1 C. n-1 D. n+e填空1、 具有n个顶点的有向图最多有（）条边。2、 具有n个顶点的强连通图至少有（）条边。3、 有向图的邻接表表示适于求顶点的（）。4、 有向图的邻接矩阵表示中，第i（）上非零元素的个数为顶点vi的入度。5、对有向图进行深度优先搜索时，若该图不是（），可得到一个深度优先搜索生辰森林。6、 当对用（）表示法表示的图，从某指定顶点作为初始点进行广度优先搜索，得到的广度优先 搜索序列惟一。八排序选择1、内部排序和外部排序的区别不在于（）。A、待排叙文件的大小B、有无内外存的交换C、是否在内存中排序D、可采用的排序策略评价排序算法好坏的标准主要是（）。2、A、执行时间B、辅助空间C、算法本身的复杂度D、执行时间和所需的辅助空间3、 “就地排序”指排序中，需要的辅助空间为（）oA、0（1）B、0C、0（n）D、0（r<2）4、 一个待排叙文件的关键字如下：265 301 751 129 937 863 742 694 076 438经过（）趟直接插入排序后可得到如下序列：129 265 301 751 937 863 742 694 076 438A 1B 2C 3D 4若用冒泡排序对关键字序列18, 16, 14, 12, 10, 8进行从小到大的排序，所要进行的关 5、键字比较总次数为（）。A、10B、15C、21D、346、用某种排序方法对线性表（25, 84, 21, 47, 15, 27, 68, 35, 20）进行排序时，结点序列的变化情况如下：(1) 25 84 21 47 15 27 68 35 20(4)20 15 2115 20 2115 20 2125 47 27 68 35 8425 35 27 47 68 8425 27 35 47 68 84那末，所采用的排序方法是（）。A、直接插入排序B、希尔排序C、冒泡排序D、快速排序填空1、若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变。则这种排序方法是（）的排序方法。2、当增量为1时，该趟希尔排序与（）排序基本一致。3、 最坏情况，在第i趟直接插入排序中，要进行（）次关键字的比较。4、 两个序列如下：L1 = 25, 57, 48, 37, 92, 86, 12, 33L2=25, 37, 33, 12, 48, 57, 86, 92用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列（）。5、在（）堆中，所有双亲结点的关键字的值大于它们孩子的关键字的值。6、直接选择排序的总的关键字比较次数与（）无关。九查找选择1、通常把查找过程中对关键字需要执行的（）作为衡量一个查找算法效率优劣的标准。A、BSTB、WPLC、ASLD、BFS2、用二分法在有序表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）树描述，该树的形态只与有关。A 1-二叉查找树2-表中元素个数B 1-二叉判定树2-表中元素关键字的取值C 1-二叉比较树2-表中元素个数D 1-二叉树2-表中元素关键字的取值5、 长度为12的按关键字有序的查找表采用顺序组织方式，若用二分查找方法，则在等概率情 况下，查找不成功的平均查找长度是（）。A、37/12 B、63/13 C、39/12 D、49/136、在表长是N的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数（）。A、N B、1 C、N+1 D、N-1填空1、若在查找的同时对表作修改，则相应的表称（）。2、对表长为n的链表进行顺序查找，等概率情况下，查找成功的平均查找长度是（）。3、对表长为n的顺序表进行分块查找，若以顺序查找确定块且每块长度为s,则在等概率查找 的情况下，查找成功时的平均查找长度为（）。4、一个线性表中共有625个元素，假定每一个元素的查找概率相同，如果采用分块查找，则对这 些元素共分为（）个索引块为最佳（基本查找方法都采用顺序查找）。5、在分块查找方法中，首先查找索引表,然后再用顺序查找方法查找相应的（）。6、当二叉排序树为（）时，其平均查找长度最好。十文件选择1、通常，磁带只适合用于存储（）文件。A、顺序B、索引C、散列D、多关键字2、对于存储在磁盘上的顺叙文件的记录进行直接存取是根据（）。A、逻辑记录号B、逻辑记录结构C、逻辑记录的内容D、逻辑关键字3、 存储在磁带上的顺叙文件的查找只能用（）。A、顺序查找B、二分查找C、分块查找D、树表查找4、 下面关于B树和B+树的叙述中，不正确的是A. B树和B+树都是平衡的多分树B. B树和B+树都是可用于文件的索引结构C. B树和B+树都能有效地支持顺序检索