电大数据结构复习题(选择题).doc

电大数据结构复核习题（选择题）一、 单项选择题。1、 在数据结构中，从逻辑上可以把数据结构分为（ C ）。A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部机构2、 下列说法中，不正确的是（ D ）。A数据元素是数据的基本单位 B数据项是数据中不可分割的最小可标识单位 C数据可有若干个数据元素构成 D数据项可由若干个数据元素构成3、 一个存储结点存储一个（ B ）。A数据项 B数据元素 C数据结构 D数据类型4、 每个存储结点只存储一个数据元素，各结点存储在连续的存储空间，该存储方式是（ A ）存储方式。A顺序 B链接 C索引 D散列5、 每个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（ B ）存储方式。A顺序 B链接 C索引 D散列6、 数据结构中，与所使用的计算机无关的是数据的（ C ）。A存储结构 B物理结构 C逻辑结构 D物理和存储结构7、 下列的叙述中，不属于算法特性的是（ D ）。A有穷性 B输入性 C可行性 D可读性8、 算法分析的目的是（ C ）。 A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性9、 数据结构是一门研究计算机中（B ）对象及其关系的科学。A数值运算 B非数值运算 C集合 D非集合 10、 算法的时间复杂度与（ C ）有关。 A所使用的计算机 B与计算机的操作系统 C与算法本身 D与数据结构11、 把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（ B ）。 A逻辑结构 B物理结构 C算法的具体实现 D给相关变量分配存储单元12、 设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（ A ）。 An-i+1 Bn-i Cn-i-1 Di13、 设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（ B ）。 An-i+1 Bn-i Cn-i-1 Di14、 在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（ C ）。 Ap=q-next Bp-next=q Cp-next=qnext Dq-next=NULL15、 在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（ D ）。 Ap-next= s; snext= pnext Bp-next=snext; Cp=s-next Ds-next=p-next; p-next=s;16、 非空的单向循环链表的尾结点满足（C ）（设头指针为head，指针p指向尾结点）。 A.P-next= =NULL BP= =NULL CP-next= =head DP= = head 17、 链表不具有的特点是（ A ）。 A可随机访问任一元素 B插入删除不需要移动元素 C不必事先估计存储空间 D所需空间与线性表长度成正比18、 带头结点的链表为空的判断条件是（B ）（设头指针为head）。Ahead = =NULLBhead-next= =NULL Chead-next= =headDhead!=NULL19、 在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（C ）。Ap=q-nextBp-next=qCp-next=q-nextDq-next=NULL20、 下面关于线性表的叙述错误的是( B )。 A.线性表采用顺序存储,必须占用一片地址连续的单元 B线性表采用顺序存储,便于进行插入和删除操作 C线性表采用链式存储,不必占用一片地址连续的单元 D线性表采用链式存储,便于进行插入和删除操作21、 在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（ C ）。 Ar=f-next; Br=r-next; Cf=f-next; Df=r-next;22、 在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（ B ）。 Af-next=s; f=s; Br-next=s;r=s; Cs-next=r;r=s; Ds-next=f;f=s;23、 一个顺序表第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的地址是（ B ）。A98 B100 C102 D10624、 用链表表示线性表的优点是（ C ）。A便于随机存取 B花费的存储空间较顺序存储少C便于插入和删除 D数据元素的物理顺序和逻辑顺序相同25、 有关线性表的正确说法是（ D ）。A每个元素都有一个直接前驱和一个直接后继 B线性表至少要求一个元素C表中的元素必须按由小到大或由大到下排序 D除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继26、 若让元素1，2，3依次进栈，则出栈顺序不可能为（ C ）。A3，2，1 B2，1，3 C3，1，2 D1，3，227、 一个队列的入队序列是1，2，3，4。则队列的输出序列是（ B ）。A4，3，2，1 B1，2，3，4 C1，4，3，2 D3，2，4，128、 向顺序栈中压入新元素时，应当（ A ）。A先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针 C先后次序无关紧要 D同时进行29、 在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（ C ）。Atop-next=p; Bp-next=top-next; top-next=p;Cp-next=top; top=p; Dp-next=top-next; top=top-next;30、 在一个栈顶指针为top的链栈中删除一个结点时，用 x保存被删结点的值，则执行（ A ）。Ax=top;top=top-next; Bx=top-data;Ctop=top-next; x=top-data; Dx=top-data; top=top-next;31、 一般情况下，将递归算法转换成等价的非递归算法应该设置（ B ）。A栈 B队列 C堆栈或队列 D数组32、 表达式a*(b+c)-d的后缀表达式是（ C ）。 Aabcd*+- Babc+*d- Cabc*+d- D-+*abcd33、 判断一个顺序队列sq（最多元素为m0）为空的条件是（ A ）。 Asq-rear-sq-front= m0 Bsq-rear-sq-front-1= = m0Csq-front=sq-rear Dsq-front=sq-rear+134、 判断一个循环队列Q（最多元素为m0）为空的条件是（ C ）。 AQ-front=Q-rear BQ-front!=Q-rear CQ-front=(Q-rear+1)% m0 DQ-front!= (Q-rear+1)%m0 35、 判断一个循环队列Q（最多元素为m0）为空的条件是（ C ）。 AQ-front=Q-rear BQ-front!=Q-rear CQ-front=(Q-rear+1)% m0 DQ-front!= (Q-rear+1)% m0 36、 判断栈S满（元素个数最多n个）的条件是（ B ）。 As-top=0 Bs-top!=0 Cs-top=n-1 Ds-top!=n-1 37、 一个队列的入队顺序是a,b,c,d，则离队的顺序是（ C ）。 Aa,d,cb Ba,b,c,d Cd,c,b,a Dc,b,d,a38、 如果以链表作为栈的存储结构，则退栈操作时（ B ）。 A必须判断栈是否满 B判断栈元素类型 C必须判断栈是否空 D对栈不作任何判断39、 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（ B ）结构。A堆栈 B队列 C数组 D先性表40、 一个递归算法必须包括（ A ）。A递归部分 B终止条件和递归部分 C迭代部分 D终止条件和迭代部分41、 从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（ C ）。 Ax=top-data; top=top-next; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data;42、 在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（ B ）。 Ar=f-next; Br=r-next; Cf=f-next; Df=r-next;43、 在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（ A ）。 Af-next=s; f=s; Br-next=s;r=s; Cs-next=r;r=s; Ds-next=f;f=s;44、 以下陈述中正确的是（ C ）。A串是一种特殊的线性表 B串的长度必须大于零 C串中元素只能是字母 D空串就是空白串45、 设有两个串p和q，其中q是p的子串，q在p中首次出现的位置的算法称为（ D ）。A求子串 B连接 C匹配 D求串长 46、 串是（ B ）。 A不少于一个字母的序列 B任意个字母的序列 C不少于一个字符的序列 D有限个字符的序列 47、 串的长度是指（ D ）。A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数48、 若串S=“English”，其子串的个数是（ B ）。 A9 B16 C 36 D2849、 下面关于串的叙述中，不正确的是（ C ）。A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串即可以采用顺序存储，也可以采用链式存储50、 串与普通的线性表相比较，它的特殊性体现在（ B ）。A顺序的存储结构 B链接的存储结构 C数据元素是一个字符 D数据元素可以任意51、 空串与空格串（ D ）。A相同 B不相同 C可能相同 D无法确定52、 两个字符串相等的条件是（ A ）。 A两串的长度相等 B两串包含的字符相同 C两串的长度相等，并且两串包含的字符相同 D两串的长度相等，并且对应位置上的字符相同53、 在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（ C ）存储比较合适。A链式 B 顺序 C堆结构 D无法确定54、 一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（ D ）。A64 B28 C70 D9055、 稀疏矩阵采用压缩存储的目的主要是（ D ）。A表达变得简单 B对矩阵元素的存取变得简单 C去掉矩阵中的多余元素 D减少不必要的存储空间的开销56、 一个非空广义表的表头（ C ）。 A不可能是原子 B只能是子表 C只能是原子 D可以是子表或原子 57、 常对数组进行的两种基本操作是（ A ）。A建立与删除 B索引与、和修改 C查找和修改 D查找与索引58、 设二维数组A56按行优先顺序存储在内存中，已知A00 起始地址为1000，每个数组元素占用5个存储单元，则元素A44的地址为（ D ）。 A1140 B1145 C 1120 D112559、 设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（ ）。A41 B32 C18 D3860、 假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ B ）。A15 B16 C17 D4761、 二叉树第k层上最多有（ B ）个结点。 A2k B2k-1 C2k-1 D2k-1 62、 二叉树的深度为k,则二叉树最多有（ D ）个结点。A2k B2k-1 C2k-1 D2k-163、 设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（ C ）。 Aabdec Bdebac Cdebca Dabedc64、 树最适合于用来表示（ D ）。A线性结构的数据 B顺序结构的数据 C元素之间无前驱和后继关系的数据 D元素之间有包含和层次关系的数据 65、 设a,b为一棵二叉树的两个结点，在后续遍历中，a在b前的条件是（ C ）。Aa在b上方 Ba在b下方 Ca在b左方 Da在b右方66、 权值为1，2，6，8的四个结点构成的哈夫曼树的带权路径长度是（ D ）。A18 B28 C19 D2967、 将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（ B ）。A33 B34 C35 D3668、 如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（ A ）。A哈夫曼树 B平衡二叉树 C二叉树 D完全二叉树69、 下列有关二叉树的说法正确的是（ A ）。A二叉树中度为0的结点的个数等于度为2的结点的个数加1B二叉树中结点个数必大于0C完全二叉树中，任何一个结点的度，或者为0或者为2 D二叉树的度是270、 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。A4 B5 C6 D771、 在一棵度具有5层的满二叉树中结点总数为（ A ）。A31 B32 C33 D1672、 利用n个值作为叶结点的权生成的哈夫曼树中共包含有( D )个结点。 A. n B. n+1 C. 2*n D. 2*n-173、 利用n个值作为叶结点的权生成的哈夫曼树中共包含有( B )个双支结点。 A. n B. n-1 C. n+1 D. 2*n-174、 利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为( A )。 A. 18 B. 16 C. 12 D. 3075、 在一棵树中，（ C ）没有前驱结点。A分支结点 B叶结点 C树根结点 D空结点76、 在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ C ）。 A2i B2i-1 D2i+1 C2i+2 77、 设一棵哈夫曼树共有n个叶结点，则该树有（ B ）个非叶结点。 An Bn-1 Cn+1 D2n78、 设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（ B ）个结点。 A2n B2n-1 C2n+1 D2n+2 79、 一棵完全二叉树共有5层，且第5层上有六个结点，该树共有（ B ）个结点。 A20 B21 C23 D3080、 在一个图G中，所有顶点的度数之和等于所有边数之和的（ C ）倍。 A1/2 B1 C2 D4 81、 在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。 A邻接矩阵表示法 B邻接表表示法 C逆邻接表表示法 D邻接表和逆邻接表82、 在图的存储结构表示中，表示形式唯一的是（ A ）。 An Bn+1 Cn-1 Dn/283、 一个具有n个顶点的无向完全图包含（ C ）条边。 An（n-1） Bn（n+1） C n（n-1）/2 D n（n+1）/284、 一个具有n个顶点的有向完全图包含（ A ）条边。 An（n-1） Bn（n+1） C n（n-1）/2 D n（n+1）/285、 对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ B ）。 An Bn2 Cn-1 D（n-1）286、 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（ A ）。 An Be C2n D2e87、 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ D ）。 An Be C2n D2e88、 在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（ B ）邻接点。 A入边 B出边 C入边和出边 D不是入边也不是出边89、 在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（ A ）邻接点。 A入边 B出边 C入边和出边 D不是入边也不是出边90、 邻接表是图的一种（ B ）。 A顺序存储结构 B链式存储结构 C索引存储结构 D散列存储结构91、 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ B ）。 A完全图 B连通图 C有回路 D一棵树92、 下列有关图遍历的说法不正确的是（ C ）。A连通图的深度优先搜索是一个递归过程B图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C非连通图不能用深度优先搜索法D图的遍历要求每一顶点仅被访问一次93、 无向图的邻接矩阵是一个（ A ）。 A对称矩阵 B 零矩阵 C上三角矩阵 D对角矩阵94、 图的深度优先遍历算法类似于二叉树的（ A ）遍历。A先序 B 中序 C后序 D层次95、 已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ C ）。 AV1V2V4V8V3V5V6V7 BV1V2V4V5V8V3V6V7 CV1V2V4V8V5V3V6V7 DV1V3V6V7V2V4V5V8V6V7V1V2V3V8V4V596、 顺序查找方法适合于存储结构为（ D ）的线性表。A散列存储 B索引存储 C散列存储或索引存储 D顺序存储或链接存储97、 对线性表进行二分查找时，要求线性表必须（ C ）。 A以顺序存储方式 B以链接存储方式 C以顺序存储方式 ，且数据元素有序 D以链接存储方式，且数据元素有序 98、 如果要求一个线性表既能较快地查找，又能动态适应变化要求，可以采用（ B ）查找方法。A顺序 B分块 C折半 D散列99、 对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该（ B ）。 A以顺序存储方式 B以链接存储方式 C以索引存储方式 D以散列存储方式100、 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ C ）。An Bn/2 C(n+1)/2 D(n-1)/2 101、 采用折半查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ D ）。AO(n*n) BO(nlog2n) CO(n) Ds(log2n)102、 哈希函数有一个共同的性质，即函数值应当以（ D ）取其值域的每个值。A最大概率 B最小概率 C平均概率 D同等概率103、 有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ A ）。A29/10 B31/10 C26/10 D29/9104、 已知一个有序表为11,22,33,44,55,66,77,88,99，则顺序查找元素55需要比较（ C ）次。A3 B4 C5 D6105、 顺序查找法与二分查找法对存储结构的要求是（ D ）。A顺序查找与二分查找均只是适用于顺序表B顺序查找与二分查找均既适用于顺序表，也适用于链表C顺序查找只是适用于顺序表 D二分查找适用于顺序表106、 有数据53,30,37,12,45,24,96，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（ B ）。A45,24,53,12,37,96,30 B37,24,12,30,53,45,96 C12,24,30,37,45,53,96 D30,24,12,37,45,96,53107、 对有18个元素的有序表作二分（折半）查找，则查找A3的比较序列的下标可能为（ D ）。A1、2、3 B9、5、2、3 C9、5、3 D9、4、2、3108、 对于顺序存储的有序表5，12，20，26，37，42，46，50，64，若采用折半查找，则查找元素26的比较次数是（ C ）。 A.3 B. 3 C. 4 D.5109、 关于哈希查找的说法正确的是（ B ）。 A.除留余数法是最好的 B. 哈希函数的好坏要根据具体情况而定 C.删除一个元素后，不管用哪种方法处理冲突，都只需简单地把该元素删除掉 D.因为冲突是不可避免的，所以装填因子越小越好110、 在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（ C ）。 A. 冒泡排序 B. 希尔排序 C. 直接选择排序 D. 直接插入排序111、 从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（ A ） A. 插入排序 B. 选择排序 C. 交换排序 D. 归并排序112、 从未排序序列中挑选元素，并将其放入已排序序列的一端，此方法称为（ C ）。 A. 插入排序 B. 交换排序 C. 选择排序 D. 归并排序113、 依次将每两个相邻的有序表合并成一个有序表的排序方法称为（ D ）。 A. 插入排序 B. 交换排序 C. 选择排序 D. 归并排序114、 当两个元素出现逆序的时候就交换位置，这种排序方法称为（ B ）。 A. 插入排序 B. 交换排序 C. 选择排序 D. 归并排序115、 每次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（ B ）。 A. 插入排序 B. 快速排序 C. 堆排序 D. 归并排序116、 在正常情况下，直接插入排序的时间复杂度为（ D ）。 A. O(log2n) B. O(n) C. O(n log2n) D. O(n2)117、 在正常情况下，冒泡排序的时间复杂度为（ D ）。 A. O(log2n) B. O(n) C. O(n log2n) D. O(n2)118、 在归并排序中，归并趟数的数量级为（ A ）。 A. O(log2n) B. O(n) C. O(n log2n) D. O(n2)119、 在待排序元素基本有序的情况下，效率最高的排序方法是（ A ）。 A. 插入排序 B. 快速排序 C. 堆排序 D. 归并排序120、 下面几种排序方法中，要求内存量最大的是（ D ）。A. 插入排序 B. 交换排序 C. 选择排序 D. 归并排序121、 在下列排序方法中，关键字比较的次数与记录的初始排列秩序无关的是（ D ）。 A. 希尔排序 B. 冒泡排序 C. 插入排序 D. 选择排序122、 快速排序方法在（ C ）情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数123、 下述几种排序方法中，平均情况下占用内存量最大的是（ D ）方法。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序124、 若构造一棵具有n个结点的二叉树排序，在最坏的情况下，其深度不会超过（ B ）。A. n/2 B. n C. (n+1)/2 D. n+1125、 对数据元素序列（49，72，68，13，38，50，97，27）进行排序，前三趟排序结果时的结果依次为第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38，50，97，27；第三趟：13，49，68，72，38，50，97，27。该排序采用的方法是（ A ）。A. 插入排序法 B. 选择排序法 C. 冒泡排序法 D.堆积排序法126、 对具有n个元素的任意序列采用插入排序法进行排序，排序趟数为（A）。A. n-1 B. n C. n+1 D. log2n127、 对序列（49，38，65，