数据结构-题库附有答案

数据结构-题库[复制]

下列选项中，不属于线性结构的是[单选题]*A、线性表B、双向链表C、循环队列D、二叉树(正确答案)

某线性表L含有n个元素，采用单循环链表保存，仅有尾指针指向链表的终端结点。在最后一个结点之后插入一个结点及删除第一个结点的时间复杂度分别是[单选题]*A、

0(1)和0(1）(正确答案)B、O(1)和O(n)C、O(n)和O(1)D、O(n)和

O(n)下列应用中会用到栈[单选题]*A、计算后缀表达式的值(正确答案)B、图的广度优先遍历C、对数组进行希尔排序D、对散列表进行查找

设栈初始为空，入栈序列为1，2，3，4，5，下列选项中，不可能得到的出栈序列[单选题]*A、

1，2，3，4，5B、

3，1，4，2，5(正确答案)C、4，3，2，5，1D、5，4，3，2，1

己知广义表LS=(((c，((d))，(e，(（f))，(g，h)，((m，n)))，head(LS)[单选题]*A、cB、（c）C、（c，（d））D、((c，(d))，(e，(f)))(正确答案)

设线性表采用顺序存储方式保存，每个元素占8个存储单元。第1个元素的存储地址为200，则第5个元素占用的最后一个存储单元的地址[单选题]*A、

239(正确答案)B、240C、247D、248

—棵完全二叉树T的全部k个叶结点都在同一层中，每个分支结点都有两个孩子结点。T中包含的结点数是[单选题]*A、k(正确答案)B、2k-1C、k2D、2k-l[填空题]_________________________________答案:B[单选题]*解析:(正确答案)

设字符集中有n个字符，对其进行哈夫曼编码，得到的哈夫曼树的结点总数[单选题]*A、

2n_1(正确答案)B、2nC、2n+lD、不确定

设图G的邻接矩阵A如下所示。G的各顶点的度依次是[单选题]*A、1，2，1，2B、2，2，1，1C、3，4，2，3(正确答案)D、4，4，2，2.对题10-11图进行深度优先遍历，下列选项中，正确的遍历序列是[单选题]*A、1，2，3，4，5(正确答案)B、2，3，5，4，1C、3，5，

1，2，4D、4，3，5，

1，2对题10-11图进行拓扑排序，下列选项中，正确的拓扑序列是[单选题]*A、1，2，3，4，5B、2，3，

1，4，5C、3，5，1，2，4D、

5，3，1，2，4(正确答案)下列排序方法中，不是稳定排序方法的是[单选题]*A、直接插入排序B、冒泡排序C、归并排序D、快速排序(正确答案)

已知数据序列（18，19，20，4，51，6，30，1，2）是某种排序算法第二趟排序后得到的结果，则该算法可能是[单选题]*A、选择排序B、冒泡排序C、直接插入排序(正确答案)D、快速排序对有序表（1，3，9，12，32，41，45，62，75，77）进行二分查找，查找关键字9时，进行比较的关键字依次是[单选题]*A、1，3，9B、32，3，9(正确答案)C、32，

12，9D、41，12，9分别使用下列数据序列建立二叉排序树，能得到高度最高的二叉树的是[单选题]*A、10，8，9，6，12，11，

13B、10，6，8，9，

12，11，13(正确答案)C、10，12，

11，13，8，6，D、10，8，6，9，12，13，11.

数据的运算，即对数据元素施加的操作，是定义在数据的_______结构上的。[单选题]*答案:(正确答案)逻辑;

在顺序表中，因为访问任一结点的方式是_______，所以访问每个结点的时间复杂度均为0（1）[单选题]*答案:随机访问(正确答案);.

带头结点的链队列可以由一个头指针和一个尾指针唯一确定。当头指针和尾指针相等时，表示队列_______。[单选题]*答案:为空(正确答案);

稀疏矩阵采用压缩存储，只保存非零元素，得到的顺序存储结构称为________。[单选题]*答案:三元组表(正确答案);

广义表（（a），（b，c），（d，e，（f，g，h）））的表尾是_______。[单选题]*答案:((b,c),(d,e,(f,g,h)))(正确答案);中序线索化二叉树的过程，是在中序遍历过程中用线索取代_______。[单选题]*答案:空指针(正确答案);

在有n个顶点、e条边的无向连通图中，e的取值范围是_______。[单选题]*答案:((b,c),(d,e,(f,g,h)))(正确答案);

中序线索化二叉树的过程，是在中序遍历过程中用线索取代_______。[单选题]*答案:空指针(正确答案);在有n个顶点、e条边的无向连通图中，e的取值范围是_______。[单选题]*答案:n-l≤e≤n(n-l)/2(正确答案);

对数据序列进行升序排序。采用堆排序算法时，首先应对初始数据建立_______堆[单选题]*答案:大根(正确答案);.

在无序数组中进行查找操作，应使用的查找方法是_______。[单选题]*答案:顺序查找（或线性查找）(正确答案);

—棵高度为2的4阶B树中能够保存的关键字个数最多是_______。[单选题]*答案:15(正确答案);数据结构研宄的基本内容是[单选题]*A、数据的逻辑结构、存储结构和对数据元素施加的操作(正确答案)B、数据的类型、数据的定义、算法描述和各种操作实现C、数据的线性结构、树型结构、图型结构及相关的算法D、数据元素之间的逻辑关系、物理存储和相关程序实现数据结构中，评价算法好坏的重要指标之一是[单选题]*A、程序的执行时间B、源程序的代码长度C、程序采用的语言D、算法的时间复杂度(正确答案)等概率情况下，在长度为《的顺序表中插入1个元素需要移动元素的平均次数是[单选题]*A、1B、n/2(正确答案)C、nD、n＋1己知head为指向带头结点的单链表的头指针，指针变量p指向一个新结点，next[单选题]*是结点的指针域，若要将p所指结点插入到单链表的表头，则正确的语句序列是A、head->next=p;p->next=head;B、p->next=head->next;head=p;C、head=p;p->next=head->head;D、p->next=head->next;head->next=p;(正确答案)后缀表达式求值的过程中要用到的数据结构是[单选题]*A、—个保存各种操作符的栈B、—个保存操作数及运算结果的栈(正确答案)C、两个分别保存操作符和操作数的D、两个分别保存操作数和运算结果的栈广义表1^=(((3)，b)),((c，（d)),(e，(f)),(g，h))的表尾是[单选题]*A、(g,h)B、(c,(d))，（e，（f))),(g，h)C、((g，h))D、(((c,(d)),(e,(f))),(g,h))(正确答案)用》(«>2)个带权值的结点作为叶结点构造一棵哈夫曼树，下列选项中正确的是[单选题]*A、哈夫曼树是叶结点权值之和最小的二叉树B、哈夫曼树是带权路径长度WPL最小的二叉树(正确答案)C、n个带有权值的结点可以构造出唯一一棵哈夫曼树D、哈夫曼树是有《个叶结点的二叉树中高度最低的二叉树将一棵树T转换为等价的二叉树T1,与T的后序遍历序列相同的是T1的[单选题]*A、前序遍历序列B、中序遍历序列(正确答案)C、后序遍历序列D、按层遍历序列要在带权图（权值>0)中求从某一顶点到其余各顶点的最短路径，应采用的算法是[单选题]*A、哈夫曼算法B、普里姆算法C、克鲁斯卡尔算法D、迪杰斯特拉算法(正确答案)设图G存在拓扑序列，则下列结论中正碌的是[单选题]*A、图G是一个有向图B、图G的拓扑序列唯一C、图G是一个无向图D、图G是一个有向无环图(正确答案)内排序过程中，待排序数据保存在[单选题]*A、CPU中B、内存储器中(正确答案)C、外存储器中D、计算机中下列排序方法中，关键字总的比较次数与记录的初始排列次序无关的是[单选题]*A、冒泡排序B、希尔排序C、直接插入排序D、直接选择排序(正确答案)散列查找方法可以达到的最好时间复杂度是[单选题]*A、0(1)(正确答案)B、〇(n)C、O(log«)D、O(nm)下列关于二分查找判定树T的叙述中，正确的是[单选题]*A、T是一棵二叉树(正确答案)B、T是一棵满二叉树C、T是一棵完全二叉树D、T的叶结点在同一层算法必须满足的五个准则是:输入、输出、有穷性、确定性和____________。[单选题]*答案:可行性(正确答案);答案:[单选题]*1396(正确答案);广义表（（））的长度是____________[单选题]*答案:1(正确答案);具有n个结点的完全二叉树的深度为_____________。[单选题]*答案:[logn]+l（或[log（n+1）1）(正确答案);图G的邻接矩阵不是一个对称矩阵，则图G—定是____________图。[单选题]*答案:有向(正确答案);顶点表示活动、边表示活动间先后关系的有向无环图称为____________网。[单选题]*答案:(正确答案)顶点活动（或AOV）;对二叉排序树BT进行____________遍历可以得到BT中所有结点的有序序列。[单选题]*答案:中序(正确答案);在一棵25阶的B树中，非根结点内所包含的关键字个数至少是____________个。[单选题]*答案:12(正确答案);若某线性表中最常用的操作是删除最后一个元素和找第i个元素的前趋元素，则采用（）存贮方式最节省运算时间[单选题]*A、单链表B、双链表(正确答案)C、单循环链表D、顺序（数组）有一散列表，表长度M为100，采用除余数法构造散列函数即H（K）=KmodP(p<M)，为使该函数具有较好的性能，P的选择是（）:[单选题]*A、99(正确答案)B、93C、97D、91答案:B二叉排序树查找时，当二叉排序树是（），效率最优。[单选题]*A、线索树B、平衡二叉树(正确答案)C、Huffman树D、最小生成树按照二叉树的定义，具有3个结点的二叉树有（）种。[单选题]*A、5(正确答案)B、.4C、3D、6数据表中有10000个元素，如果仅要求求出其中最大的100个元素，则采用（）排序算法最节省时间。[单选题]*A、直接选择排序B、希尔排序C、快速排序D、堆排序(正确答案)一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）:[单选题]*A、edcbaB、dceab(正确答案)C、decbaD、abcde设有两个串p和q，求q在p中首次出现的位置的运算称作（）:[单选题]*A、模式匹配(正确答案)B、.连接C、求子串D、求串长循环队列sq队空的条件（）[单选题]*A、（sq.rear+1）%maxsize==(sq.front+1)%maxsizeB、（sq.rear+1）%maxsize==sq.front+1;C、（sq.rear+1）%maxsize==sq.front;D、sq.rear==sq.front;(正确答案)一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）:[单选题]*A、110B、100C、108(正确答案)D、120若待排序列已基本有序，要使它完全有序，从关键字比较次数和移动次数考虑，应当使用的排序方法是（）。[单选题]*A、归并排序(正确答案)B、直接插入排序C、直接选择排序D、快速排序有12个节点的平衡二叉树的最大深度是（）。[单选题]*A、4B、3C、6D、5(正确答案)某二叉树的前序遍历结点顺序为:ABCDEFG，中序遍历结点顺序为:CBDAFGE，则后续遍历结点的顺序为:（）。[单选题]*A、CDBGFEA(正确答案)B、CDGFEABC、CDBAGFED、CDBFAGE设树T的度为4，其中度为1、2、3和4的结点的个数分别为4、2、1、1，则T中叶子结点的个数是（）。[单选题]*A、5B、6C、7D、8(正确答案)设只包含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为（）。[单选题]*答案:(2^k)-1;(正确答案)对于给出的一组权W={10，12，16，21，30}，通过哈夫曼算法求出的哈夫曼树的带权路径长度为（）。[单选题]*答案:200;(正确答案)在有5个选手参加的单循环乒乓球赛中，总共将进行（）场比赛。[单选题]*答案:10场;(正确答案)有向图中的极大连通子图称为该图的（）。[单选题]*答案:有向图的强连通分量;(正确答案)用一维数组设计栈，初态是栈空。现有输入序列是a、b、c、d，经过push、push、push、pop、pop、push操作后，输出序列是（）。[单选题]*答案:cb;(正确答案)中缀表达式(A—B×C/D＋E)/F的后缀表达式是（）[单选题]*答案:ab-c*d+e/f-;(正确答案)设哈夫曼树中共有n个结点，则该哈夫曼树中有（）个度数为1的结点。[单选题]*答案:0;(正确答案)设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为（）。[单选题]*答案:e=d;(正确答案)下列排序算法中()不能保证每趟排序至少能将一个元素放到其最终的位置上。[单选题]*A、快速排序B、shell排序(正确答案)C、堆排序D、冒泡排序下面关于哈希(Hash，杂凑)查找的说法正确的是()[单选题]*A、哈希函数构造的越复杂越好，因为这样随机性好，冲突小B、除留余数法是所有哈希函数中最好的C、不存在特别好与坏的哈希函数，要视情况而定(正确答案)D、若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）:[单选题]*A、edcbaB、cdbaeC、abcdeD、dbace(正确答案)链表不具有的特点是（）[单选题]*A、可随机访问任一元素(正确答案)B、插入、删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性长度成正比设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。[单选题]*A、栈(正确答案)B、队列C、线性表的链式存储结构D、线性表的顺序存储结构下面给出的四种排序法中()排序法是不稳定性排序法。[单选题]*A、插入B、冒泡C、二路归并D、堆积(正确答案)对于有n个结点的二叉树,其高度为（）[单选题]*A、不确定(正确答案)B、log2nC、ëlog2nû|+1D、nlog2n下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。[单选题]*A、冒泡B、希尔C、快速(正确答案)D、堆设无向图的顶点个数为n，则该图最多有（）条边。[单选题]*A、n-1(正确答案)B、n(n-1)/2C、n(n+1)/2D、0数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用()算法最节省时间。[单选题]*A、堆排序(正确答案)B、希尔排序C、快速排序D、直接插入排序在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。[单选题]*A、2021-01-02B、2C、1(正确答案)D、4在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。[单选题]*A、G中有弧B、G中有一条从Vi到Vj的路径C、G中没有弧D、G中有一条从Vj到Vi的路径(正确答案)关键路径是事件结点网络中（）。[单选题]*A、从源点到汇点的最长路径(正确答案)B、从源点到汇点的最短路径C、最长回路D、最短回路适用于折半查找的表的存储方式及元素排列要求为()[单选题]*A、链接方式存储，元素无序B、链接方式存储，元素有序C、顺序方式存储，元素无序D、顺序方式存储，元素有序(正确答案)当采用分快查找时，数据的组织方式为()[单选题]*A、数据分成若干块，每块内数据有序B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块(正确答案)C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D、数据分成若干块，每块（除最后一块外）中数据个数需相同设树T的度为4，其中度为1，2，3、4、5的结点个数分别为2，4，3，4，2则T中的叶子数为[单选题]*答案:30;(正确答案)如果要将序列{50，16，23，68，94，70，73}建成堆，则只需把16与相互交换。[单选题]*答案:50;(正确答案)下面程序段中带下划线的语句的执行次数的数量级是:。i=1;WHILE（i[单选题]*答案:O(log2n);(正确答案)广义表（a，（a，b），d，e，（（i，j），k））的长度是。[单选题]*答案:5;(正确答案)设有一个中缀表达式（（E-F）*G+A/（B-C））*D，其等价的后缀表达式是。[单选题]*答案:ABCD/+E*-;(正确答案)设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）[单选题]*A、5B、6C、7D、8(正确答案)设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。[单选题]*A、M1B、M1+M2C、M3D、M2+M3(正确答案)设给定权值总数有n个，其哈夫曼树的结点总数为()[单选题]*A、不确定B、2nC、2n+1D、2n-1(正确答案)一个具有1025个结点的二叉树的高h为（）[单选题]*A、11B、10C、11至1025之间(正确答案)D、10至1024之间在一个具有n个顶点的有向完全图中，所含的边数为()。[单选题]*A、nB、n(n-1)(正确答案)C、n(n-1)/2D、n(n+1)/2在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为()。[单选题]*A、kB、k+1(正确答案)C、k+2D、2k已知一个有向图的边集为{<a，b>，<a，c>，<a，d>，<b，d>，<b，e>，<d，e>}，则由该图产生的一种可能的拓扑序列为()。[单选题]*A、a，b，c，d，e(正确答案)B、a，b，d，e，bC、a，c，b，e，dD、a，c，d，b，e在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是()。[单选题]*A、-1~1(正确答案)B、-2~2C、1~2D、0~1若根据查找表(23，44，36，48，52，73，64，58)建立哈希表，采用h(K)=K%13计算哈希地址，则元素64的哈希地址为()。[单选题]*A、4(正确答案)B、8C、12D、13答案:C下述几种排序方法中，（）是稳定的排序方法。[单选题]*A、希尔排序B、快速排序C、归并排序(正确答案)D、堆排序下面（）算法适合构造一个稠密图G的最小生成树。[单选题]*A、Prim算法(正确答案)B、Kruskal算法C、Floyd算法D、Dijkstra算法若一组记录的排序码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。[单选题]*A、38,40,46,56,79,84B、40,38,46,79,56,84C、40,38，46,56,79,84(正确答案)D、40,38,46,84,56,79设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（）。[单选题]*A、8B、3C、5D、9(正确答案)A、[单选题]*B、(正确答案)C、D、答案:D150、假定一组记录为(46，79，56，64，38，40，84，43)，在冒泡排序的过程中进行第一趟排序时，元素79将最终下沉到其后第_______个元素的位置。答案:4;在一棵65阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是___个。[单选题]*答案:64;(正确答案)顺序查找n个元素的顺序表，;当使用监视哨时，若查找失败，则比较关键字的次数为____次。[单选题]*答案:n+1;(正确答案)在有序表A[1..12]中，采用折半查找算法查等于A[2]的元素，所比较的元素下标依次为。[单选题]*答案:6、3、1、2;(正确答案)若某线性表中最常用的操作是删除最后一个元素和找第i个元素的前趋元素，则采用（）存贮方式最节省运算时间[单选题]*A、单链表B、双链表C、单循环链表D、顺序（数组）(正确答案)有一散列表，表长度M为100，采用除余数法构造散列函数即H（K）=KmodP(p[单选题]*A、99(正确答案)B、93C、97D、91答案:A二叉排序树查找时，当二叉排序树是（），效率最优。[单选题]*A、线索树B、平衡二叉树(正确答案)C、Huffman树D、最小生成树按照二叉树的定义，具有3个结点的二叉树有（）种。[单选题]*A、5(正确答案)B、4C、3D、6数据表中有10000个元素，如果仅要求求出其中最大的100个元素，则采用（）排序算法最节省时间。[单选题]*A、直接选择排序B、希尔排序C、快速排序D、堆排序(正确答案)下面程序段中state语句的执行次数为（）:for(i=0;ii;j--)state;[单选题]*A、n(n+2)/2B、(n-1)(n+2)C、n(n+1)/2(正确答案)D、(n-1)(n+2)/2一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）:[单选题]*A、edcbaB、dceab(正确答案)C、decbaD、abcde设有两个串p和q，求q在p中首次出现的位置的运算称作（）:[单选题]*A、模式匹配(正确答案)B、连接C、求子串D、求串长循环队列sq队空的条件（）[单选题]*A、（sq.rear+1）%maxsize==(sq.front+1)%maxsizeB、（sq.rear+1）%maxsize==sq.front+1;(正确答案)C、（sq.rear+1）%maxsize==sq.front;D、sq.rear==sq.front;一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）:[单选题]*A、110B、100C、108(正确答案)D、120数据的最小单位是（）。[单选题]*A、数据项(正确答案)B、数据类型C、数据元素D、数据变量函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。[单选题]*A、“STRUCTURE”(正确答案)B、“DATA”C、“ASTRUCTUR”D、“DATASTRUCTURE”设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。[单选题]*A、O(log2n)B、O(1)C、O(n2)D、O(n)(正确答案)设只包含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为（）。[单选题]*答案:2k-1;(正确答案)对于给出的一组权W={10，12，16，21，30}，通过哈夫曼算法求出的哈夫曼树的带权路径长度为（）。[单选题]*答案:200;(正确答案)在有5个选手参加的单循环乒乓球赛中，总共将进行（）场比赛。[单选题]*答案:10;(正确答案)有向图中的极大连通子图称为该图的（）。[单选题]*答案:连通分量;(正确答案)用一维数组设计栈，初态是栈空。现有输入序列是a、b、c、d，经过push、push、push、pop、pop、push操作后，输出序列是（）。[单选题]*答案:cb;(正确答案)已知广义表L=((A)，(B,c，d))，设取表头和表尾的运算分别为H(L)，T(L)，则取得原子d的运算是（）。[单选题]*答案:T(T(L));(正确答案)在一棵m阶B树中，若在某结点中删除一个关键字而引起该结点和兄弟节点的合并，则此结点中原有的关键字的个数是（）个。[单选题]*答案:m-1;(正确答案)设有一个顺序共享栈S[0:n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是（）。[单选题]*答案:top2-top1=1;(正确答案)在图的邻接表中用顺序存储结构存储表头结点的优点是（）。[单选题]*答案:可以随机访问到任一个定点的简单链表;(正确答案){[填空题]_________________________________若某线性表中最常用的操作是删除最后一个元素和找第i个元素的前趋元素，则采用（）存贮方式最节省运算时间[单选题]*A、单链表B、双链表C、单循环链表(正确答案)D、顺序（数组）二叉排序树查找时，当二叉排序树是（），效率最优。[单选题]*A、线索树B、Huffman树C、平衡二叉树(正确答案)D、最小生成树下列排序算法中，时间复杂度不受数据初始状态影响，恒为O（nlog2n）的是()。[单选题]*A、堆排序(正确答案)B、冒泡排序C、快速排序D、希尔排序按照二叉树的定义，具有3个结点的二叉树有（）种。[单选题]*A、3B、5(正确答案)C、4D、6数据表中有10000个元素，如果仅要求求出其中最大的100个元素，则采用（）排序算法最节省时间。[单选题]*A、直接选择排序B、希尔排序C、快速排序D、堆排序(正确答案)已知二叉树叶子数为50，仅有一个孩子的结点数为30，则总结点数为()。[单选题]*A、130B、131C、129(正确答案)D、不确定下述二叉树中，那一种满足性质:从任意结点出发到根的路径上所经过的结点序列按其关键字有序:[单选题]*A、堆(正确答案)B、哈夫曼树C、线索二叉树D、二叉排序树下面程序段中state语句的执行次数为（）:for(i=0;ii;j--)state;[单选题]*A、n(n+2)/2B、(n-1)(n+2)/2C、n(n+1)/2(正确答案)D、(n-1)(n+2)一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）:[单选题]*A、110B、100(正确答案)C、108D、120设有两个串p和q，求q在p中首次出现的位置的运算称作:[单选题]*A、连接B、模式匹配(正确答案)C、求子串D、求串长数据结构在内存中的表示是指（）。[单选题]*A、数据的存储结构(正确答案)B、数据结构C、数据的逻辑结构D、数据元素之间的关系计算机中，算法指的是解决某一问题的有限运算序列，它必须具备输入、输出、（）。[单选题]*A、可行性、可移植性和可扩充性B、可行性、有穷性和确定性(正确答案)C、确定性、有穷性和稳定性D、易读性、稳定性和确定性下面程序段的时间复杂度为（）。for(i=1;i<=n;i*=2){j=0;while(j[单选题]*A、O(n)B、O(n2)C、O(nlog2n)(正确答案)D、O(n3)链表不具有的特点是（）。[单选题]*A、可随机访问任一元素(正确答案)B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表长度成正比两个字符串S1和S2相等的条件是（）:[单选题]*A、S1和S2长度相等B、S1和S2对应位置的字符相等(正确答案)C、S1是S2的子串D、A并且B设只包含要根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为。[单选题]*答案:2k-1;(正确答案)在有n个选手参加的单循环乒乓球赛中，总共将进行场比赛。[单选题]*答案:10;(正确答案)有n个叶子的哈夫曼树，其总结点数为。[单选题]*答案:2n-1;(正确答案)用一维数组设计栈，初态是栈空，top=0。现有输入序列是a、b、c、d，经过push、push、pop、push、pop、push操作后，输出序列是。[单选题]*答案:bc;(正确答案)对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为个。[单选题]*答案:2n;(正确答案)广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为。Head(Tail(Head(Tail(Tail(A)))))[单选题]*答案:d;(正确答案)对于有200个结点的完全二叉树,其高度是。[单选题]*答案:8;(正确答案)中缀表达式(A-B*(C+D))/(E+F)的后缀表达式是:。[单选题]*答案:ABC+*DE-F+/;(正确答案)若一棵二叉树具有7个度为2的结点，5个度为1的结点，则总的结点数有个。[单选题]*答案:20;(正确答案)一棵完全二叉树有101个结点，其中叶子结点有个。[单选题]*答案:36;(正确答案)答案:[单选题]*1-3-2-4-8-5-7-6

1-3-2-7-4-6-8-5(正确答案)栈和队列的相同之处是()。[单选题]*A、元素的进出满足先进后出B、元素的进出满足后进先出C、只允许在端点进行插入和删除操作(正确答案)D、无共同点m阶B-树是一棵()。[单选题]*A、m叉排序树B、m叉平衡排序树(正确答案)C、m-1叉平衡排序树D、m+1叉平衡排序树AVL树是一种平衡的二叉排序树，树中任一结点的()。[单选题]*A、左、右子树的高度均相同B、左、右子树的高差的绝对值不超过1(正确答案)C、左、右子树的高度均大于右子树的高度D、左子树的高度均小于右子树的高度要进行二分查找，则线性表（）。[单选题]*A、必须以顺序方式存储B、必须以顺序方式存储，且数据元素按键值有序(正确答案)C、既可用顺序方式存储，也可用链式方式存储D、必须以链式方式存储，且数据元素按键值有序已知一哈希表，采用链地址法处理冲突，在这种表上查找某一键值，可能要查找多次，所有被查找的键值（）。[单选题]*A、一定都是同义词(正确答案)B、均不是同义词C、不一定都是同义词D、都相同若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。[单选题]*A、顺序表(正确答案)B、双链表C、带头结点的双循环链表D、单循环链表用二分法在有序表{3，4，10，13，33，42，46，63，76，78，95，96，120}中查找95时，需要比较次数为（）。[单选题]*A、2B、3(正确答案)C、4D、5下列关键字序列中，()是堆。[单选题]*A、16，72，31，23，94，53B、94，23，31，72，16，53C、16，53，23，94，31，72D、16，23，53，31，94，72(正确答案)如果将所有中国人按照生日（不考虑年，只考虑月、日）来排序，那么使用下列排序算法中最快的是（）。[单选题]*A、基数排序(正确答案)B、归并排序C、堆排序D、快速排序二叉树的先序遍历和中序遍历如下:先序遍历:EFHIGJK;中序遍历:HFIEJKG。该二叉树根的右子树的根是:()[单选题]*A、EB、FC、G(正确答案)D、H适用于折半查找的表的存储方式及元素排列要求为（）。[单选题]*A、链接方式存储，元素无序B、链接方式存储，元素有序C、顺序方式存储，元素无序D、D.顺序方式存储，元素有序(正确答案)在一棵具有n个结点的二叉链表中，所有结点的空域个数等于（）。[单选题]*A、nB、n-1C、n+1(正确答案)D、2*n对于一个有向图，若一个顶点的度为k1，入度为k2，则对应的邻接表中，该结点后的单链表中的结点数为（）。[单选题]*A、k1B、k2C、k1-k2(正确答案)D、k1+k214.图的广度优先遍历类似于二叉树的（）。[单选题]*A、先序遍历B、中序遍历C、后序遍历D、层次遍历(正确答案)答案:D251、15.具有n个顶点的有向图最多有（）条边。A、nB、n(n-1)C、n(n+1)D、n*n对100个记录进行折半查找，最多比较次数和最少比较次数分别是（）。[单选题]*答案:7和1;(正确答案)查找表分为静态查找表和动态查找表两种，二叉排序树属于（）。[单选题]*答案:动态查找表;(正确答案)设有满足二分查找法要求的查找表R（键值按递增顺序排列），查找区间为[l，h],要查找的键值为K，首先被比较元素的位置为mid=(l+h)DIV2，若R[MID].key>K，则h改为（）;二分查找的结束条件是l>h。[单选题]*答案:MID-1;(正确答案)无向图中的极大连通子图称为该无向图的（）。[单选题]*答案:连通分量;(正确答案)若一个具有n个顶点、e条边的无向图是一个森林，则该森林中必有多少棵树?（）。[单选题]*答案:n-e;(正确答案)在一个无环路有向图G中，若存在一条从顶点i到j的边，则在顶点的拓扑序列中，顶点i与顶点j的先后次序是（）。[单选题]*答案:i在前j在后;(正确答案)采用堆排序、快速排序、冒泡排序，对初态有序的表，最省时间的是（）。[单选题]*答案:冒泡排序;(正确答案)已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有（）个叶子结点。[单选题]*答案:12;(正确答案)设有向图G有n个顶点v1，v2，v3，…，vn，它的邻接矩阵为A，顶点vi的出度OD（vi）为()。[单选题]*答案:第I行非零元素之和（∑aij）;(正确答案)二叉排序树中的查找，在最优时，可以达到折半查找的效率O（log2n），但是最坏情况下只能达到（）效率。[单选题]*答案:O(n);(正确答案)}VNode,AdjList[MAXSIZE];[单选题]*typedefstruct(正确答案){AdjListvertex;intvexnum,arcnum;GraphKindkind;}AdjGraph;intLocateVertex(AdjGraphG,VertexTypev);voidCreateGraph(AdjGraph*G);voidDisplayGraph(AdjGraphG);voidDestroyGraph(AdjGraph*G);voidDFSTraverse(AdjGraphG);intLocateVertex(AdjGraphG,VertexTypev){inti;for(i=0;i<G.vexnum;i++){if(strcmp(G.vertex[i].data,v)==0){returni;}}return-1;}voidCreateGraph(AdjGraph*G){inti,j,k;VertexTypev1,v2;ArcNode*p;cout<<"请输入图的定点数和边数:";cin>>(*G).vexnum>>(*G).arcnum;cout<<"请输入"<<G->vexnum<<"个顶点的值:"<<endl;for(i=0;i<G->vexnum;i++){cin>>G->vertex[i].data;G->vertex[i].firstarc=NULL;}cout<<"请输入弧尾弧头:"<<endl;for(k=0;k<G->arcnum;k++){cin>>v1>>v2;i=LocateVertex(*G,v1);j=LocateVertex(*G,v2);p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->info=NULL;p->nextarc=G->vertex[i].firstarc;G->vertex[i].firstarc=p;}(*G).kind=DG;}voidDestroyGraph(AdjGraph*G){inti;ArcNode*p,*q;for(i=0;i<(*G).vexnum;++i){p=G->vertex[i].firstarc;if(p!=NULL){q=p->nextarc;free(p);p=q;}}(*G).vexnum=0;(*G).arcnum=0;}voidDisplayGraph(AdjGraphG){inti;ArcNode*p;cout<<G.vexnum<<"个顶点:"<<endl;for(i=0;i<G.vexnum;i++){cout<<G.vertex[i].data<<"";}cout<<G.arcnum<<"条边:"<<endl;for(i=0;i<G.vexnum;i++){p=G.vertex[i].firstarc;while(p){cout<<G.vertex[i].data<<"->"<<G.vertex[p->adjvex].data<<"";cout<<endl;p=p->nextarc;}}}voidvisitvex(AdjGraphG,inti){cout<<G.vertex[i].data<<"";}voidDFS(AdjGraphG,inti,intvisited[],int*n){ArcNode*p;visited[i]=1;(*n)++;visitvex(G,i);p=G.vertex[i].firstarc;while(p!=NULL){if(!visited[p->adjvex]){DFS(G,p->adjvex,visited,n);}p=p->nextarc;}}voidDFSTraverse(AdjGraphG){intv,u,n,visited[MAXSIZE];for(v=0;v<G.vexnum;v++){cout<<"从"<<G.vertex[v].data<<"开始搜索:";for(u=0;u<G.vexnum;u++){visited[u]=0;}n=0;DFS(G,v,visited,&n);if(n==G.vexnum){cout<<"."<<G.vertex[v].data<<"是根顶点"<<endl;利用二叉链表存储树时，则根结点的右指针是（）。[单选题]*A、指向最左孩子B、指向最右孩子C、非空D、空(正确答案)若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的中序前驱为()[单选题]*A、X的双亲B、X的左子树中最右下结点(正确答案)C、X的右子树中最左下的结点D、X的左子树中最右叶结点下述编码中哪一个不是前缀码（）。[单选题]*A、（00，01，10，11）B、（0，10，110，111）C、（0，1，00，11）(正确答案)D、（1，01，000，001）适用于折半查找的表的存储方式及元素排列要求为()[单选题]*A、链接方式存储，元素无序B、链接方式存储，元素有序C、顺序方式存储，元素无序D、顺序方式存储，元素有序(正确答案)下列排序算法中()不能保证每趟排序至少能将一个元素放到其最终的位置上。[单选题]*A、快速排序B、shell排序(正确答案)C、堆排序D、冒泡排序下面关于哈希(Hash，杂凑)查找的说法正确的是()[单选题]*A、哈希函数构造的越复杂越好，因为这样随机性好，冲突小B、除留余数法是所有哈希函数中最好的C、不存在特别好与坏的哈希函数，要视情况而定(正确答案)D、若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可当采用分快查找时，数据的组织方式为()[单选题]*A、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块(正确答案)B、数据分成若干块，每块中数据个数可以不相同C、数据分成若干块，每块内数据不必有序，每块内最大（或最小）的数据组成索引块D、数据分成若干块，每块内数据必须有序下面给出的四种排序法中()排序法是稳定性排序法。[单选题]*A、shell排序B、冒泡排序(正确答案)C、堆排序D、快速排序下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。[单选题]*A、堆(正确答案)B、希尔C、快速D、冒泡设无向图的顶点个数为n，则该图最多有（）条边。[单选题]*A、n-1B、n(n+1)/2C、0D、n(n-1)/2(正确答案)下列程序段的时间复杂度为（）。i=0，s=0;while(s[单选题]*A、O(n1/2)(正确答案)B、O(n1/3)C、O(n)D、O(n2)设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（）存储方式最节省运算时间。[单选题]*A、单向链表B、单向循环链表C、双向链表D、双向循环链表(正确答案)设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（）。[单选题]*A、s->next=p->next;p->next=-s;(正确答案)B、q->next=s;s->next=p;C、p->next=s->next;s->next=p;D、p->next=s;s->next=q;设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。[单选题]*A、5，3，4，6，1，2B、3，2，5，6，4，1(正确答案)C、3，1，2，5，4，6D、1，5，4，6，2，3设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（）。[单选题]*A、10B、19(正确答案)C、28D、55与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。[单选题]*A、存储结构B、存储实现C、逻辑结构(正确答案)D、运算实现下述几种排序方法中，（）是稳定的排序方法。[单选题]*A、希尔排序B、快速排序C、归并排序(正确答案)D、堆排序线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。[单选题]*A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以(正确答案)在双向链表存储结构中，删除p所指的结点时须修改指针（）。[单选题]*A、p->next->prior=p->prior;p->prior->next=p->next;(正确答案)B、p->next=p->next->next;p->next->prior=p;C、p->prior->next=p;p->prior=p->prior->prior;D、p->prior=p->next->next;p->next=p->prior->prior;一个栈的入栈序列为A,B,C,D,E，则栈的不可能出栈序列是()。[单选题]*A、ABCDEB、EDCBAC、DECBAD、DCEAB(正确答案)用链接方式存储的队列，在进行删除运算时（）。[单选题]*A、仅修改头指针B、仅修改尾指针C、头、尾指针都要修改D、头、尾指针可能都要修改(正确答案)把一棵树转换为二叉树后，这棵二叉树的形态是（）。[单选题]*A、唯一的(正确答案)B、有多种C、有多种，但根结点都没有左孩子D、有多种，但根结点都没有右孩子最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。[单选题]*A、(rear+1)%n==frontB、rear==front(正确答案)C、rear+1==frontD、(rear-l)%n==front已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）。[单选题]*A、CBEFDA(正确答案)B、FEDCBAC、CBEDFAD、不确定下面（）方法可以判断出一个有向图是否有环。[单选题]*A、深度优先遍历B、拓扑排序(正确答案)C、求最短路径D、求关键路径分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）。[单选题]*A、（100，80，90，60，120，110，130）B、（100，120，110，130，80，60，90）C、（100，60，80，90，120，110，130）(正确答案)D、(100，80，60，90，120，130，110)从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（）。[单选题]*A、归并排序B、冒泡排序C、插入排序(正确答案)D、选择排序栈是一种操作受限的线性表，它只能在线性表的一端进行插入和删除操作，对栈的访问是按照的原则进行的。[单选题]*答案:后进先出;(正确答案)在循环队列中，队列长度为m，存储位置从0到m-1编号，以rear表示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是。[单选题]*答案:（rear+1）%n;(正确答案)对n个元素的表做顺序查找时，若查找成功，则比较关键字的次数最多为。[单选题]*答案:n;(正确答案)在哈希造表中，不同的关键字产生同一哈希地址的现象，称为。[单选题]*答案:冲突;(正确答案)在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动个元素。[单选题]*答案:n-i+1;(正确答案)若S表示入栈操作，X表示出栈操作，若元素入栈顺序为1，2，3，4，为了得到1，3，4，2的出栈顺序，相应的S和X的操作串为。[单选题]*答案:SXSSXSXXX(正确答案)深度为h的满m叉树的第k层有个结点。(1=<k=<h)[单选题]*答案:m^(k-1);(正确答案)n个顶点的连通图至少有条边。[单选题]*答案:n-1;(正确答案)

请回答下列问题:[单选题]*（1）说明语句S1的功能;（2）说明语句组S2的功能;(正确答案)答案:（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点写出该算法的功能:[单选题]*答案:递归地后序遍历链式存储的二叉树。(正确答案)程序填空:二叉搜索树的查找——递归算法:[单选题]*答案:BST;BST->lchild;BST->rchild(正确答案)由3个结点可以构造出多少种不同的二叉树?（）[单选题]*A、5(正确答案)B、3C、4D、2设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。[单选题]*A、M1B、M1+M2C、M3D、M2+M3(正确答案)设给定权值总数有n个，其哈夫曼树的结点总数为()[单选题]*A、不确定B、2nC、2n+1D、2n-1(正确答案)一个具有1025个结点的二叉树的高h为（）[单选题]*A、11B、10C、11至1025之间(正确答案)D、10至1024之间在一个具有n个顶点的有向完全图中，所含的边数为()。[单选题]*A、nB、n(n-1)C、n(n-1)/2(正确答案)D、n(n+1)/2用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。[单选题]*A、栈B、队列(正确答案)C、树D、图已知一个有向图的边集为{<a，b>，<a，c>，<a，d>，<b，d>，<b，e>，<d，e>}，则由该图产生的一种可能的拓扑序列为()。[单选题]*A、a，b，c，d，e(正确答案)B、a，b，c，e，dC、a，c，b，e，dD、a，c，d，e，b在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是()。[单选题]*A、-1~1(正确答案)B、-2~2C、1~2D、0~1若根据查找表(23，44，36，48，52，73，64，58)建立哈希表，采用h(K)=K%13计算哈希地址，则元素64的哈希地址为()。[单选题]*A、4(正确答案)B、8C、12D、13答案:C关键路径是事件结点网络中（）。[单选题]*A、从源点到汇点的最长路径(正确答案)B、从源点到汇点的最短路径C、最长回路D、最短回路数据表中有10000个元素，如果仅要求求出其中最大的5个元素，则采用()算法最节省时间。[单选题]*A、快速排序B、希尔排序C、直接插入排序D、堆排序(正确答案)对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为()。[单选题]*A、2B、3C、4(正确答案)D、5在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（）型调整以使其平衡。[单选题]*A、LLB、LRC、RL(正确答案)D、RR若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）。[单选题]*A、79，46，56，38，