数据结构（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算法的时间复杂度为O(n^3)，B算法的时间复杂度为O(2^n)，则说明( )。

A、对于任何数据量，A算法的时间开销都比B算法小B、随着问题规模n的增大，A算法比B算法有效C、随着问题规模n的增大，B算法比A算法有效D、对于任何数据量，B算法的时间开销都比A算法小填空1、数据的( )结构依赖于计算机语言.2、数据的逻辑结构可分为线性结构和( )结构。

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

4、常用的四种存储方法是什么5、常见的数据的逻辑结构有哪两种6、一般，将算法求解问题的输入量称为( )。

二线性表选择题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、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。

A、 O(1)B、 O(n)C、 O(n^2)D、 O(log2n)填空题1、线性表是一种典型的( )结构。

2、在一个长度为n的顺序表中删除第i个元素，要移动( )个元素3、如果要在第i个元素前插入一个元素，要后移( )个元素。

4、采用( )存储结构的线性表叫顺序表。

5、顺序表中逻辑上相邻的元素的物理位置( )。

6、在无头结点的单链表中，第1个结点的地址存放在头指针中，其他结点的存储地址存放在( )结点的next域中。

三栈和队列选择1、栈与一般的线性表的区别在于( )。

A、数据元素的类型不同B、运算是否受限制C、数据元素的个数不同D、逻辑结构不同2、一个栈的入栈序列是abcde，则栈的不可能的输出序列是( )。

A、EdcbaB、 decbaC、 dceabD、 abcde3、在对栈的操作中，能改变栈的结构的是( )。

A、InitStack(S)B、StackEmpty(S)C、StackTop(S)D、StackFull(S)4、顺序栈的类型定义如下：typedef maxsize 64;typedef struct {int data[maxsize];int top;}seqstack;seqstack *s;顺序栈s栈满条件是( )。

(A)s->top<>0(B)s->top==maxsize(C)s->top==maxsize-1(D)S->top!=maxsize5、向一个栈顶指针为HS的链栈中将一个S指针所指的结点入栈，执行( )。

A、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=( )。

A、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、设串s1='ABCDEFG',s2='PQRST',函数con(x,y)返回x和y串的连接串，subs(s,I,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2)))的结果串是( )。

A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF4、在串的模式匹配中，一般( )。

A、有效位移的个数大于合法位移的个数B、有效位移的个数等于合法位移的个数C、有效位移的个数小于合法位移的个数D、有效位移和合法位移无关5、顺序串中，根据空间分配方式的不同，可分为( )。

A、直接分配和间接分配B、静态分配和动态分配C、顺序分配和链式分配D、随机分配和固定分配填空1、在空串和空格串中，长度不为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(i-1)/2+j-1B、i(i-1)/2+jC、i(i+1)/2+j-1D、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、对于一个一维数组A[12]，若一个数据元素占用字节数为S，首地址为1，则A[i](i>=0)的存储地址为( A )，若首地址为D，则A[i]的存储地址为( B )。

3、已知二维数组A[m][n]采用行优先顺序存储，每个元素占k个存储单元，并且第一个元素的存储地址LOC（A[0][0]），则A[i][j]的地址是( )。

4、在多维数组中，数据元素的存放地址直接可通过地址计算公式计算出。

因此，数组是一种( )存取结构。

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

6、一般，特殊矩阵按规律压缩存储到一个向量中后，能( )存取。

六树选择题1、在树中，互为堂兄弟的结点拥有相同的( )。

A、双亲B、祖先C、路径D、孩子2、树最适合用来表示。

A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据3、已知二叉树如下图所示，此二叉树的顺序存储结构是：( )。

○A/○C/ \○F ○GA、 1 2 3 4┌─┬─┬─┬─┐│ A│ C│ F│ G│└─┴─┴─┴─┘B、 1 2 3 4 5┌─┬─┬─┬─┬─┐│ 4│ A│ C│ F│ G│└─┴─┴─┴─┴─┘C、 0 1 2 3 4 5┌─┬─┬─┬─┬─┬─┐│ 4│ A│ C│ │ F│ G│└─┴─┴─┴─┴─┴─┘D、 0 1 2 3 4┌─┬─┬─┬─┬─┐│ A│ C│ │ F│ G│└─┴─┴─┴─┴─┘4、在一棵高度为h的满四叉树中，结点总数为( )。

A、4^h-1B、(4^h-1)/2C、(4^h-1)/4D、4^h5、若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是( )。

A. 9B. 11C. 12D. 不确定6、按二叉树的定义，具有3个结点的二叉树有( ) 种。

A、3B、4C、5D、6填空1、在树中，度为( )的结点称为叶子。

2、在树中，除跟结点外，其他结点都有且只有一个( )结点。

3、有100个结点的树有( )条边。

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

5、一棵二叉树有67个结点，这些结点的度要么是0，要么是2。

这棵二叉树中度为2的结点有( )个。

6、深度为K的完全二叉树至少有2^(k-1)个结点，至多有2^(k-1)-2个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是( )。

七图选择1、设G1=(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、在图的表示法中，表示形式唯一的是( )。