数据结构问题

Question

.设用于通信的电文仅由A，B，C，D，E，F这6个字母组成，字母在电文中出现的次数分别为7、9、2、6、3、5，试为这6个字母设计哈夫曼编码，要求画出哈夫曼树。

Answer 1

第1题 (2.0) 分 某二叉树的先根遍历序列和后根遍历序列相同，则该二叉树的特征是( )。A、高度等于其结点数B、任一结点无左孩子C、任一结点无右孩子D、空或只有一个结点第2题 (2.0) 分 关于哈夫曼树，下列叙述正确的是( )。A、可能有度为1的结点B、总是完全二叉树C、有可能是满二叉树D、WPL是深度最大叶子的带权路径长度第3题 (2.0) 分 给定整数集合{3,5,6,9,12}，与之对应的哈夫曼树是( )。第4题 (2.0) 分 在n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素个数为( )。A、nB、n*eC、eD、2*e第5题 (2.0) 分 对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为( )。A、求顶点的邻接点B、求顶点的度C、深度优先遍历D、广度优先遍历第6题 (2.0) 分 为便于判别有向图中是否存在回路，可借助于( )。A、广度优先搜索算法B、最小生成树算法C、最短路径算法D、拓扑排序算法第7题 (2.0) 分 在待排关键字序列基本有序的前提下，效率最高的排序方法是( )。A、直接插入排序B、快速排序C、直接选择排序D、归并排序第8题 (2.0) 分 对n个元素进行冒泡排序，最好情况下的只需进行( )对相邻元素之间的比较。A、nB、n-1C、n+1D、n/2第9题 (2.0) 分 对包含n个关键字的散列表进行检索，平均检索长度是( )。A)O(log2n)B)O(n)C)不直接依赖于nD)O(nlog2n)A、AB、BC、CD、D第10题 (2.0) 分 下列查找方法中，不属于动态的查找方法是( )。A、二叉排序树法B、平衡树法C、散列法D、二分查找法第11题 (2.0) 分 ( )存储方式适用于折半查找。A、键值有序的单链表B、键值有序的顺序表C、键值有序的双链表D、键值无序的顺序表第12题 (2.0) 分 在顺序表中，数据元素之间的逻辑关系用( )。A、数据元素的相邻地址表示B、数据元素在表中的序号表示C、指向后继元素的指针表示D、数据元素的值表示第13题 (2.0) 分 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用( )存储方式最节省运算时间( )。A、单链表B、顺序表C、双链表D、单循环链表第14题 (2.0) 分 若只在线性表的首、尾两端进行插入操作，宜采用的存储结构为( )。A、顺序表B、用头指针表示的单循环链表C、用尾指针表示的单循环链表D、单链表第15题 (2.0) 分 算法分析是指( )。A、分析算法的正确性B、分析算法的可读性C、分析算法的健壮性D、分析算法的时空性能第16题 (2.0) 分 算法的时间复杂度取决于( )。A、问题的规模B、数据的初始状态C、A和BD、以上都不是第17题 (2.0) 分 若进栈序列为a,b,c，则通过入出栈操作能得到的a,b,c的不同排列个数为( )。A、4B、5C、6D、7第18题 (2.0) 分 下列关于串的叙述中，正确的是( )。A、一个串的字符个数即该串的长度B、一个串的长度至少是1C、空串是由空格字符组成的串D、两个串若长度相同，则它们相等第19题 (2.0) 分 下列叙述错误的是( )。A、多维数组是向量的推广。B、多维数组是非线性结构。C、如果将二维数组看成由若干个行向量组成的一维数组，则为线性结构。D、对矩阵进行压缩存储的目的是为了数据加密。第20题 (2.0) 分 若下图表示某广义表，则它是一种( )。A、线性表B、纯表C、再入表D、递归表第21题 (2.0) 分某完全二叉树有7个叶子，则其结点总数为( )。A、14B、13C、13或14D、以上都不是第22题 (2.0) 分 在二叉链表上交换所有分支结点左右子树的位置，则利用( )遍历方法最合适。A、前序B、中序C、后序D、按层次第23题 (2.0) 分 线索二叉树中某结点为叶子的条件是( )。A、p-> lchild!=NULL || p-> rchild!=NULLB、p-> ltag==0 || p-> rtag==0C、p-> lchild!=NULL & & p-> rchild!=NULLD、p-> ltag==1 & & p-> rtag==1第24题 (2.0) 分 连通图是指图中任意两个顶点之间( )。A、都连通的无向图B、都不连通的无向图C、都连通的有向图D、都不连通的有向图第25题 (2.0) 分 在n个顶点和e条边的无向图的邻接表中，边结点的个数为( )。A、nB、n*eC、eD、2*e第26题 (2.0) 分 图的深度遍历必须借助( )作为辅助空间。A、栈B、队列C、查找表D、数组第27题 (2.0) 分 下列排序方法中，稳定的是( )。A、直接选择排序B、冒泡排序C、快速排序D、希尔排序第28题 (2.0) 分 在不完全排序的情况下，就可以找出前几个最大值的方法是( )。A、快速排序B、直接插入排序C、堆排序D、归并排序第29题 (2.0) 分 n个记录直接选择排序时所需的记录最多交换次数是( )。A、n-1B、nC、n(n-1)/2D、n(n+1)/2第30题 (2.0) 分 从理论上讲，将数据以( )结构存放，查找一个数据的时间不依赖于数据的个数n。A、二叉查找树B、链表C、散列表D、顺序表第31题 (2.0) 分 静态查找表与动态查找表二者的根本差别在于( )。A、它们的逻辑结构不一样B、施加在其上的操作不同C、所包含的数据元素的类型不一样D、存储实现不一样第32题 (2.0) 分 单链表中增加头结点的目的是为了( )。A、使单链表至少有一个结点B、标识表结点中首结点的位置C、方便运算的实现D、说明单链表是线性表的链式存储第33题 (2.0) 分 设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是( )。s->next=p->next;p->next=s;t=p->data;p->data=s->data;s->data=t;A、结点*p与结点*s的数据域互换B、在p所指结点的元素之前插入元素C、在p所指结点的元素之后插入元素D、在结点*p之前插入结点*s第34题 (2.0) 分 若结点的存储地址与结点内容有某种确定的关系，则相应的存储结构应为( )。A、顺序存储结构B、链式存储结构C、索引存储结构D、散列存储结构第35题 (2.0) 分 下列各式中，按增长率由小至大的顺序正确排列的是( )。A．n1/2，n!，2n，n3/2B．n3/2，2n，nlogn，2100C．2n，logn，nlogn，n3/2D．2100，logn, 2n, nn第36题 (2.0) 分 栈和队列的共同特点是( )。A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点第37题 (2.0) 分 引起循环队列队头位置发生变化的操作是( )。A、入队B、出队C、取队头元素D、取队尾元素第38题 (2.0) 分 设S=”abc”;T=”xyz”，则strcmp(S,T)的值为( )。A、正数B、负数C、零D、不确定第39题 (2.0) 分 关于十字链表中的叙述，错误的是( )。A、便于查找每一行或列的非零元素B、每行、每列的非零元素分别组成行链表、列链表C、C．十字链表是一种多重链表D、行链表、列链表的头结点不能共用第40题 (2.0) 分若下图表示某广义表，则它是一种( )。A、线性表ì再入表ì纯表ì递归表B、线性表ì纯表ì递归表ì再入表C、纯表ì线性表ì再入表ì递归表D、线性表ì纯表ì再入表ì递归表第41题 (1.0) 分 在数据结构中，算法的空间耗费包括代码和数据两部分。对错第42题 (1.0) 分顺序表不需存放指针，链表要存放指针，故链表的存储空间要求总是比顺序表大。对错第43题 (1.0) 分 开散列表和闭散列表的装填因子都可大于、等于或小于1对错第44题 (1.0) 分 任何树或林都可转化为二叉树，反之，二叉树可转化为任何树或林。对错第45题 (1.0) 分 在线索二叉树上，求结点的(遍历)前趋和后继时可利用线索得到，即不必进行遍历了。对错第46题 (1.0) 分 无向图中边数等于邻接矩阵中1的个数的一半；也等于邻接表中的边表结点数的一半对错第47题 (1.0) 分 直接插入排序是稳定的，而Shell排序就是调用若干趟直接插入排序，故也是稳定的。对错第48题 (1.0) 分 图G的生成树T是G的子图。对错第49题 (1.0) 分 设串的长度为n，则其子串个数为n(n+1)/2。对错第50题 (1.0) 分 广义表不仅是线性表的推广，也是树的推广。对错第51题 (1.0) 分 数组各元素在内存中连续存放，故前后相邻的两元素物理地址相差为1或-1。对错第52题 (1.0) 分 算法的时间复杂性是指在计算机上的实际运行时间。对错第53题 (1.0) 分 单链表中取第i个元素的时间与i成正比。对错第54题 (1.0) 分 在二叉排序树中，即使删除一个结点后马上再插入该结点，该二叉排序树的形态也可能不同。对错第55题 (1.0) 分 不可能有二叉树的任何遍历次序是相同的。对错第56题 (1.0) 分 不管树的深度和形态如何，也不可能构造出一棵有100个结点的哈夫曼树。对错第57题 (1.0) 分 如果n个顶点的无向图有n条边，则图中肯定有回路。对错第58题 (1.0) 分 有向图中顶点i的出度等于邻接矩阵中第i行中1的个数；入度等于第i列中1的个数。对错第59题 (1.0) 分 堆排序是一种巧妙的树型选择排序。对错