数据结构练习题.doc

一、 单项选择题1 关键路径是指AOE(Activity On Edge)网中_。 (a). 最长的回路 (b). 最短的回路(c) 从源点到汇点(结束顶点)的最长路径 (d). 从源点到汇点(结束顶点)的最短路径2 以下序列中不符合堆定义的是_。 (a)(102，87，100，79，82，62，84，42，22，12，68) (b)(102，100，87，84，82，79，68，62，42，22，12) (c)(12，22，42，62，68，79，82，84，87，100，102) (d)(102，87，42，79，82，62，68，100，84，12，22)3 一个具有767个结点的完全二叉树，其叶子结点个数为_。 (a). 383 (b). 384 (c). 385 (d). 3864. 一个二叉树的前序遍历序列为ABCDEFG，它的对称序遍历序列可能是（ ）(a). CABDEFG (b). ABCDEFG (c). DACEFBG (d). EABCDFG5. 高度为h的完全二叉树（仅含根结点的二叉树高度为零）的结点最少是多少（ ）(a). h1 (b). 2h1 (c). 2h+11 (d). 2h6. 对包含n个关键码的散列表进行检索，平均检索长度是（ ）(a). O( log2n ) (b). O( n ) (c). O(n log2n ) (d). 不直接依赖于n7. 设有关键码初始序列 Q,H,C,Y,P,A,M,S,R,D,F,X，新序列F,H,C,D,P,A,M,Q,R,S,Y,X是采用下列哪种排序方法对初始序列进行第一趟扫描的结果？(a). 直接插入排序 (b). 二路归并排序 (c). 以第一元素为枢轴（或分界）元素的快速排序 (c). 基数排序8. 下列说法中错误的是 (a). n个结点的树的各结点度数之和为n-1 (b). n个结点的无向图最多有n*(n-1)条边(c). 用相邻矩阵存储图时所需存储空间大小与图的结点数有关，而与边数无关(d). 散列表中碰撞的可能性大小与负载因子有关9.堆是一种特殊的数据结构，下面哪一个是堆： (a)19,75,34,26,97,56；(b)97,26,34,75,19,56；(c)19,56,26,97,34,75；(d)19,34,26,97,56,75；10.下面关于B树和B+树的叙述中，不正确的是 (a) B树和B+树都是平衡的多分树； （b）B树和B+树都是可用于文件的索引结构； (c) B树和B+树都能有效地支持顺序检索；(d) B树和B+树都能有效地支持随机检索；11.在数据结构中，从逻辑上可以把数据结构分成：(a)动态结构和静态结构；(b)紧凑结构和非紧凑结构；(c)线性结构和非线性结构；(d)内部结构和外部结构；12.若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn, 那么p1=n；pi为：(a)i；(b)n=i；(c)n-i+1；(d)不确定；13.判断一个循环队列QU（最多元素m0）为空的条件是：(a)QU-front = = QU-rear；(b) QU-front! = QU-rear；(c) QU-front = = (QU-rear+1)%m0；(d) QU-front ! = (QU-rear+1)%m0；14.表达式a*(b+c)-d的后缀表达式是(a)abcd*+-；(b)abc+*d-；(c)abc*+d-；(d)*-a+bc；15.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行：(a)s-next = p-next; p-next = s；(b)p -next = s-next; s-next = p；(c) q-next =s; s-next = p； (d) p-next =s; s-next = q；16.在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算是：(a) f-next = s；f=s；(b) f-next = s；r=s；(c) s-next = r；r=s；(d) s-next = f；f=s；17.将递归算法转换成对应的非递归算法时，通常需要使用 (a) 栈 (b) 队列(c) 链表 (d) 树18.树最适合用来表示 (a) 有序数据元素 (b) 无序数据元素(c) 元素之间具有分支层次关系的数据(d) 元素之间相关联的数据19.要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的查找方法是：(a) 分块查找(b) 顺序查找(c) 二分查找(d) 散列查找20.A node in a tree that does not have any children is called (a) a leaf； (b) an internal node； (c) a root； (d) an empty node； 21.对于一棵深度为2（仅含根结点的二叉树高度为零）的二叉树，它的总节点数：(a) 至多7个 (b)至多2个 (c) 节点数不限 (d) 至多4个 22.下面的伪码是对二叉树操作算法的片段： print( node ) if( there is a left child ) print( left child ); print data; if( there is a right child ) print( right child ); 这个算法是：（a）折半查找；（b）前序遍历；（c）中序遍历；（d）后序遍历；23.下面哪个序列不是折半查找（二分查找）所访问的数值序列(a) 10, 20, 30, 40, 50； (b) 50, 40, 30, 20, 10； (c) 10, 20, 30, 15, 18； (d) 30, 35, 40, 45, 4224.递归函数可以调用自身多少次?(a) 至多1次; (b) 任意次数; (c) 0 次; (d) 至多2次;25.分析下面函数：int f( int n ) if( n = = 0 ) return 0; if( (n & 1) = = 0 ) return f(n/2); return f(n/2) + 1; 调用函数f(10)的返回值是：(a) 1； (b) 3； (c) 5； (d) 2；26.假如n,m=0，那么下面函数的功能是： int ff( int n, int m ) if( n = 0 ) return m; return ff( n-1, m*n ); (a) 计算m * (n!)； (b) 计算最大公约数； (c)计算最小公倍数； (d) 计算(m + n)!；27.总的来说，哈希方法（hashing，也称散列方法）的主要问题在于：(a)哈希函数难以计算；(b)哈希表的存取速度慢；(c)会发生冲突；(d)哈希表占很多内存；28.对于一个大小为m含有n项的哈希表，它的负载(load)因子是：(a) m - n； (b) n + m； (c) m/n； (d) n/m ；29.下面对p的声明，那一个是指向整数的指针：(a) int *p； (b) int p； (c) int &p； (d) int *p；30.假设Thing是一个用户定义的类，B是Thing的一个实例，对于下面的代码段Thing A = B用到了类Thing中的哪一个成分：(a)赋值操作符；(b)析构函数；(c)构造函数；(d)复制构造函数；31.下面对类的部分描述用于说明一种用户定义的实数实现： class RealNumber . RealNumber( float x ); RealNumber( float x, float y=0 ); ;这段代码可能错在哪里?(a)在构造函数中不允许时有缺省值；(b)没有错误；(c)第二个构造函数与第一个不一致；(d)用两个实数参数无法创建一个实数；32.面向对象的程序设计最适合下面哪一种开发要求:(a)程序是一个完整的程序模块；(b)提供完善的代码复用；(c)获得高效率；(d)对封装的需求；33.对于有n个节点e条边的图，如果用邻接表表示，则计算全部入度的时间复杂度是:(a) O(n + e)； (b) O(n2)； (c) O(n3)； (d) O(n * e) ；34.结定结点的关键字序列（、），对它按字母的字典顺序进行排列， 快速排序的第一趟结果是：(a)（C、B、D、A、F、E、I、J、G、H）(b)（C、B、D、A、E、F、I、G、J、H） (c)（B、A、D、E、F、G、I、J、H、C）(d)（B、C、D、A、E、F、I、J、G、H）35.计算机算法是指(a) 数值计算方法(b) 对抽象数据结构的操作方法(c) 非数值计算方法(d) 解决问题的有限运算序列36、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为.( ) (a) R-F (b).n+R-F (c).(R-F+1)mod n (d).(n+R-F)mod n37、链表不具备的特点是( )。 A可随机访问任何一个元素 B插入、删除操作不需要移动元素 C无需事先估计存储空间大小 D所需存储空间与线性表长度成正比 38、对矩阵压缩存储的主要目的是( )。 A方便运算 B节省存储空间 C 降低计算复杂度 D提高运算速度 39、判断“链式队列为空 ”的条件是 ( )（front为头 指针，rear为尾指针）。Afront=NULL Brear=NULL Cfront=rear Dfront!=rear 40、关于字符串的判定语句中正确的是( )。 A字符串是一种特殊的线性表B串的长度必须大于零 C字符串不属于线性表的一种 C空格字符组成的串就是空串 41、有100个结点的树中，其边的数目为( )。 A101 B100 C99 D98 42、在程序的执行过程中，用 ( )结构可实现嵌套调用函数的正确返回。 A队列 B栈 C树 D图 43、已知递归函数f(n)的功能是计算1+ 2+n，且n1，应采用的代码段是( )。Aif n=l then return 1 else return n+f(n-1) Bif n=l then return 1 else return n+f(n+1) Cif n=l then return 0 else return n+f(n-1) Dif n=l then return 0 else return n+f(n+1)44、将一个三对角矩阵A l.100，1.100中的元素按行存储在一维数组Bl.298中，矩阵A中的元素A66，65在数组B中的下标为 ( )。 A195 B196 C197 D198 45、给定一个有n个元素的线性表。若采用顺序存储结构，则在等概率前提下，向其插入一个元素需要移动的元素个数平均为 ( )。An+l Bn/2 C(n+l)/2 D.n 46、( )是线性结构的数据结构。 A广义表 B高维数组 C双端队列 D二叉树 47、结论“( )”是正确的。 A二叉树的度为2 B树中结点的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2 48、某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新元素。删除运算是指删除表头第一个元素，那么采用( )存储方式最节省运算时间。 A仅有尾指针的单向循环链表 B仅有头指针的单向循环链表 C单向链表 D双向链表 49、表达式采用逆波兰式表示时可以不用括号，而且可以用基于( 1 )的求值过程进行计算。与逆波兰式ab+cd+*对应的中缀表达式是( 2 )。(1)A栈 B队列 C符号表 D散列表 (2)Aa+b+c*d B(a +b)*c+d C.(a+b)*(c+d) Da+b *c+d50、设数组a3.16，5.20的元素以列为主序存放，每个元素占用两个存储单元，则数组元素ai,j(3i16，5j20)的地址计算公式为( )。Aa-118+2i+28j Ba-116+2i+28j Ca-144+2i +28j Da-146+2i+28j51.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（ ） A. 1，3，2，4 B. 2，3，4，1 C. 4，3，1，2 D. 3，4，2，152.下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关？（ ） A. 直接插入排序 B. 起泡排序 C. 快速排序 D. 直接选择排序53.对n个记录的文件进行二路归并排序，总的时间代价为 A. O（nlog2n） B. O（n2） C. O（log2n） D. O（n）54.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（ ） A. 9 B. 11 C. 12 D. 不确定55.下面关于B树和B+树的叙述中，不正确的是 A. B树和B+树都是平衡的多分树 B. B树和B+树都是可用于文件的索引结构C. B树和B+树都能有效地支持顺序检索 D. B树和B+树都能有效地支持随机检索56在一棵m阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是 。Am Bm 1 Cml Dm257.如果具有n个顶点的图是一个环，则它有( )棵生成树。 An Bn +l Cn-l D2n 58一棵前序序列为1，2，3，4的二叉树，其中序序列不可能是 。 A4,1,2,3 B.4,3,2,1 C.2,4,3,1 D.3,4,2,159具有n个顶点和e条边的图的深度优先搜索算法的时间复杂度为 AO(n) BO(n3) CO(n2) DO(n*e) 60堆排序算法在平均情况下的时间复杂度为 A O(n) BO(nlogn) CO(n2) DO(logn) 61在待排序数据已基本有序的前提下，下述排序方法中效率最高的是 A 直接插入排序 B直接选择排序 C快速排序 D归并排序 62在理想情况下，散列表中查找元素所需的比较次数为 。An BO Cn2 D163. 在数据结构中数据项是有意义的数据的（）单位。基本最小最大特殊64. 在一个以 h为头指针的双向循环链表中，指针p所指的元素是尾元素的条件是（ ）。A. p=h B. h-rlink=p C. p-llink=h D. p-rlink=h65. 假设循环队列的最大容量为m的，队尾指针是rear，队头指针是front，则队列为满的条件是（ ）。A.(rear+1) % m=front B. rear=front Crear+1=front D. (rear-l) % m=front66. 深度为d(d1)的完全二叉树至少有 ( )个结点。A2d-1+1 B2d-1 C2d-1 D 2d-1-167. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ ）。Ap-next=s;s-next=p-next; B s-next=p-next;p-next=s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s;68. 对一个表长为12的有序顺序表进行二分查找，假定对表中每个记录的查找概率相等,则查找成功的平均查找长度为( )。A. 4 B. 3.1 C. 2.8 D. 1.269. An，n是对称矩阵，将下三角（包括对角线）以行序存储到一维数组Tn （n+1）/2中， 则对任一上三角元素aij对应Tk的下标k是（ ）。A. i（i-1）/2+j B. j（j-1）/2+i C. i（i-1）/2+j-1 D. j（j-1）/2+i-1 70. 一个有两个以上结点的二叉树的前序遍历序列与中序遍历序列正好相反，则该二叉树（ ）。A. 任一结点没有左子树 B. 任一结点没有右子树C. 任一结点不能同时有左子树和右子树 D. 不存在71. 计算机算法是指数值计算方法对抽象数据结构的操作方法非数值计算方法解决问题的有限运算序列72. 串的长度是（）。串中不同字符的个数 串中不同字母的个数串中所含字符的个数且字符个数大于0 串中所含字符的个数73. 将递归算法转换成对应的非递归算法时，通常需要使用（）。栈对列链表树74. 判断一个循环队列QU（最多元素m0）为空的条件是（）。QU-front = = QU-rearQU-front! = QU-rearQU-front = = (QU-rear+1)%m0QU-front ! = (QU-rear+1)%m075. 将一个对称矩阵Al.50，1. .50中的元素按行压缩存储在一维数组B中，数组B的元素总个数为（ ）。A2500 B1275 C1225 D150076. 在具有100个结点的树中，其边的数目为（）。 10110099D9877. 在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算是：f-next = s；f=s；f-next = s；r=s；s-next = r；r=s；s-next = f；f=s；78. 某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新元素。删除运算是指删除表头第一个元素，那么采用（ ）存储方式最节省运算时间。仅有尾指针的单向循环链表 仅有头指针的单向循环链表单向链表 双向链表79. 如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的（）。前序中序后序层中序80. 下面关于B树和B+树的叙述中，不正确的是（）。B树和B+树都是平衡的多分树 B树和B+树都是可用于文件的索引结构B树和B+树都能有效地支持顺序检索 B树和B+树都能有效地支持随机检索81. 当序列中的记录基本有序或n值较小时，最佳的排序方法( )。交换排序 堆排序 插入排序 基数排序82. 深度为5的二叉树至多有个结点（）。1632311083. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（ ）。s-next = p-next; p-next = sp -next = s-next; s-next = pq-next =s; s-next = pp-next =s; s-next = q84. 在单向链表的第i个结点前插入新结点时，需预先保留的结点指针是 （ ）。指向i结点的指针指向i结点的前趋结点的指针指向i结点的后继结点的指针无需保留85. 在数据结构中为了叙述的方便和避免产生混淆，通常把数据的物理结构统称为（）。存储结构逻辑结构线性结构非线性结构86. 下列属于随机存取结构的是（）。线性链表顺序表循环链表双向链表87. 下面程序段的时间复杂度为（ ）。for（i=0；i=n;+i）for（j=0；j1)个结点构成的完全二叉树，其深度为（ ）。 Log2n +1 Log2n -1 log2n+1 Log2n-191. 对于一棵深度为2的二叉树，它的总结点数：A至多7个 B.至多2个 C. 结点数不限 D. 至多4个 92. 有n个结点的完全二叉树,其最后一个非终端节点为（ ）。 n/2 n/2 2n 2n93. 对于有n个结点e条边的图，如果用邻接表表示，则计算全部结点入度的时间复杂度是:A.O(n + e) B. O(n2) C. O(n3) D. O(n * e) 94. 下面哪个序列不是折半查找（二分查找）所访问的数值序列( )A.10, 20, 30, 40, 50 B. 50, 40, 30, 20, 10 C.13, 26, 30, 45, 68 D. 30, 50, 40, 45, 4295. 给定结点的关键字序列（、），对它按字母的字典顺序进行排列（选F为枢轴），快速排序的第一趟结果是( )A.（C、B、D、A、F、E、I、J、G、H）B.（C、B、D、A、E、F、I、G、J、H）C.（B、A、D、E、F、G、I、J、H、C）D.（B、C、D、A、E、F、I、J、G、H）96. 总的来说，散列方法（hashing，也称哈希方法）的主要问题在于( )A.哈希函数难以计算B.哈希表的存取速度慢C.会发生冲突 D.哈希表占很多内存97. 堆是一种特殊的数据结构，下面哪一个是堆( )A.19,75,34,26,97,56 B.97,26,34,75,19,56 C.19,56,26,97,34,75 D.19,34,26,97,56,7598. 一棵具有n个叶子结点的哈夫曼树的总结点数为（ ）。Anl Bn C2n-l D2n 99. 用循环链表表示队列，设队列的长度为n，若只设尾指针，则出队和入队的时间复杂度分别为( )。AO(1)，O(1) B. O(1)，O(n) C. O(n)，O(1) D. O(n)，O(n)100. 设某数据结构的二元组形式表示为A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=，则数据结构A是（ ）。 A.线性结构 B. 树型结构 C.物理结构 D.图型结构101. 设有n个待排序的记录关键字，则在堆排序中需要（ ）个辅助记录单元。 A.1B.nC.nlog2nD.n2102. 设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。 A.n，e B.e，n C.2n，e D.n，2e103. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则不可得到的序列是（ ）。A. cbafed B. abcdef C. cabdef D. fedcba104. 链表不具有的特点是 （ ）。 A.随机访问 B.不必事先估计存储空间 C.插入删除不需要移动元素 D.所需空间与线性表成正比 105. 设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ ）。A.head=0 B.head-next=0 C.head-next=head D.head!=0106. 对矩阵压缩存储的主要目的是( )。 A方便运算B节省存储空间C降低计算复杂度D提高运算速度 107. 在长度为n(n0)的顺序表中插入一个元素时（假设在任何位置上插入或删除元素概率相等）,平均要移动的元素个数是( )。n 2n/3 n/2 n/3108. 对于只在首、尾进行插入操作的线性表，宜采用的存储结构为（ ）。A.顺序表 B. 用头指针表示的单循环链表C.用尾指针表示的单循环链表 D. 单链表109. 计算机算法是指（ ）。A.数值计算方法B.对抽象数据结构的操作方法C.非数值计算方法D.解决问题的有限运算序列110. 以下关于广义表的叙述中,正确的是（ ）。A.广义表是由0个或多个单元素或子表构成的有限序列B.广义表至少有一个元素是子表C.广义表不能递归定义 D.广义表不能为空表111. 一棵含18个结点的二叉树的高度至少为（ ）(设根结点所在的二叉树高度为1)。A.3 B.4 C.5 D.6112. 设只含根结点的二叉树的高度为1，则高度为n的二叉树中所含叶子结点的个数最多为（ ）个。A.2n B.n C.2n -1 D.2n-1113. 任何一个无向连通网的最小生成树（ ）。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在114. 对一棵二叉搜索树进行（ ）得到的结点序列是一个有序序列。A前序遍历 B. 中序遍历 C.后序遍历 D. 层次遍历115. 在含n个顶点和e条边的有向图的邻接矩阵中，零元素的个数为（ ）。 A.e B.2e C.n2-e D.n2-2e 116. 对矩阵压缩存储的主要目的是( )。 A方便运算B节省存储空间C降低计算复杂度D提高运算速度 117. 在具有100个结点的树中，其边的数目为（ ）。 101 100 99 D98118. 下列属于随机存取结构的是（ ）。A线性链表 .顺序表 .循环链表 .双向链表119. 所有的操作只能在一端进行的数据结构是（ ）。 A队列 .栈 .栈和队列 .循环队列120. 由n(1)个结点构成的完全二叉树，其深度为（ ）。 A Log2 (n+1) Log2 (n-1) .log2n+1 .Log2n-1121. 在树表示中,双亲表示法可以在常量时间内实现的操作（ ）。A.Parent(T,ax) B.Leftchild(T,x) C.Rightsibling(T,x) D.Deletechild(&T,&p,I)122. 具有n个顶点的无向完全图应具有的边数为（ ）。 A.n .n2-1 .n（n-1）/2 .n（n+1）/2123. （ ）是稳定的内排序方法。 A.快速排序 .堆排序 .希尔排序 .基数排序124. 总的来说，哈希方法（hashing，也称散列方法）的主要问题在于( )。A.哈希函数难以计算B.哈希表的存取速度慢C.会发生冲突 D.哈希表占很多内存125. 堆是一种特殊的数据结构，下面（ ）是堆。A.19,75,34,26,97,56 B.97,26,34,75,19,56 C.19,56,26,97,34,75 D.19,34,26,97,56,75126. 下面关于B树和B+树的叙述中，不正确的是（ ）。 A.B树和B+树都是平衡的多分树 B.B树和B+树都是可用于文件的索引结构C.B树和B+树都能有效地支持顺序检索 D.B树和B+树都能有效地支持随机检索127. 以下关于字符串的判定语句中正确的是( )。 A字符串是一种特殊的线性表 B串的长度必须大于零 C字符串不属于线性表的一种 D空格字符组成的串就是空串128. 如果具有n个顶点的图是一个环，则它有( )棵生成树。 An Bn +l Cn-l D2n 129. 一棵前序序列为1，2，3，4的二叉树，其中序序列不可能是 。 A4,1,2,3 B.4,3,2,1 C.2,4,3,1 D.3,4,2,1130. 具有n个顶点和e条边的图的深度优先搜索算法的时间复杂度为 AO(n) BO(n3) CO(n2) DO(n*e) 131. 堆排序算法在平均情况下的时间复杂度为 B O(n) BO(nlogn) CO(n2) DO(logn) 132. 在待排序数据已基本有序的前提下，下述排序方法中效率最高的是 B 直接插入排序 B直接选择排序 C快速排序 D归并排序 133. 在理想情况下，散列表中查找元素所需的比较次数为 。An BO Cn2 D1134. ( )是线性结构的数据结构。 A广义表 B高维数组 C双端队列 D二叉树 135. 结论“( )”是正确的。 A二叉树的度为2 B树中结点的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2 136. 某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新元素。删除运算是指删除表头第一个元素，那么采用( )存储方式最节省运算时间。 A仅有尾指针的单向循环链表 B仅有头指针的单向循环链表 C单向链表 D双向链表 137. 表达式采用逆波兰式表示时可以不用括号，而且可以用基于( 1 )的求值过程进行计算。与逆波兰式ab+cd+*对应的中缀表达式是( 2 )。(1)A栈 B队列 C符号表 D散列表 (2)Aa+b+c*d B(a +b)*c+d C.(a+b)*(c+d) Da+b *c+d138. 设数组a3.16，5.20的元素以列为主序存放，每个元素占用两个存储单元，则数组元素ai,j(3i16，5j20)的地址计算公式为( )。Aa-118+2i+28j Ba-116+2i+28j Ca-144+2i +28j Da-146+2i+28j139. 一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（ ） A. 1，3，2，4 B. 2，3，4，1 C. 4，3，1，2 D. 3，4，2，1140. 下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关？（ ） A. 直接插入排序 B. 起泡排序 C. 快速排序 D. 直接选择排序141. 对n个记录的文件进行二路归并排序，总的时间代价为 A. O（nlog2n） B. O（n2） C. O（log2n） D. O（n）142. 若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（ ） A. 9 B. 11 C. 12 D. 不确定143. 对于一个大小为m含有n项的哈希表，它的负载(load)因子是：(a) m - n； (b) n + m； (c) m/n； (d) n/m ；144. 下面对p的声明，那一个是指向整数的指针：(a) int *p； (b) int p； (c) int &p； (d) int *p；145. 假设Thing是一个用户定义的类，B是Thing的一个实例，对于下面的代码段Thing A = B用到了类Thing中的哪一个成分：(a)赋值操作符；(b)析构函数；(c)构造函数；(d)复制构造函数；146. 下面对类的部分描述用于说明一种用户定义的实数实现： class RealNumber . RealNumber( float x ); RealNumber( float x, float y=0 ); ;这段代码可能错在哪里?(a)在构造函数中不允许时有缺省值；(b)没有错误；(c)第二个构造函数与第一个不一致；(d)用两个实数参数无法创建一个实数；147. 面向对象的程序设计最适合下面哪一种开发要求:(a)程序是一个完整的程序模块；(b)提供完善的代码复用；(c)获得高效率；(d)对封装的需求；148. 对于有n个节点e条边的图，如果用邻接表表示，则计算全部入度的时间复杂度是:(a) O(n + e)； (b) O(n2)； (c) O(n3)； (d) O(n * e) ；二、填空题1若一个具有n个结点、k条边的非连通无向图是一个森林(nk)，则该森林中必有（ n - m ）棵树。 2. 含有3个2度结点和4个叶结点的二叉树可含（ 无穷 ）个1度结点。3. 含有2的n次方个结点的二叉树高度至少是（ n ），至多是（ 2n - 1 ）（仅含根结点的二叉树高度为零）。4. 用起泡法对n个关键码排序，在最好情况下，只需做（ n-1 ）次比较和（ 0 ）次移动；在最坏的情况下要做（ n(n-1)/2 ）次比较。5.在用于表示有向图的邻接矩阵中, 对第i行的元素进行累加, 可得到第i 个顶点的（ 出/入 ）度, 而对第j列的元素进行累加, 可得到第j个顶点的（ 入/出 ）度。 6.一个连通图的生成树是该图的（ 极小 ）连通子图。若这个连通图有n个顶点, 则它的生成树有（ n-1 ）条边。 7.给定序列100, 86, 48, 73, 35, 39, 42, 57, 66, 21, 按堆结构的定义, 则它一定（ 大顶 ）堆。 8.在进行直接插入排序时, 其数据比较次数与数据的初始排列（ 有 ）关；而在进行直接选择排序时，其数据比较次数与数据的初始排列（ 无 ）关。 9.利用关键码分别为10, 20, 30, 40的四个结点，能构造出（ 48 ）种不同的二叉排序树。 10在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个（ 前驱 ）,且存在一条从根到该结点的（ 路径 ）。11、评价数据结构的两条基本标准是：（unkown ）和（ unkown ）。12、对于顺序存储的栈，因为栈的空间是有限的，在进行（ 进栈 ）运算时，可能发生栈的上溢，在进行（ 出栈 ）运算时，可能发生栈的下溢。13、对于单链表形式的队列，其空队列的F指针和R指针都等于（ NULL ）。14、若S1=linkedst,S2=ring,则S1/S2=（ unkown ）。15、设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1。则高度为k的二叉树具有的结点数目，最少为（ k+1 ）,最多为（ 2(k+1) - 1 ）。16.从逻辑结构看，线性表是典型的（ 线性结构 ），树是典型的（ 非线性结构 ） 。17.设有二维数组A0.9,0.19，其每个元素占两