计算机系数据结构平时测试试题二

1、临沂大学 2015-2016 学年度第一学期数据结构平时测试试题一一、判断题(共14题，每题 1分，共 14分)1. 线性表的长度是线性表所占用的存储空间的大小。( )2. 顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。( )3. 线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间复杂度都是O(N) ，因而两种存储方式的插入、删除运算所花费的时间相同。()4. 双循环链表中，任一个结点的后继指针均指向其逻辑后继。( )5. 在链队列中，即便不设置尾指针也能进行入队列操作。( )6. 在顺序表中取出第 i 个元素所花费的时间与 i 成正比。 ( )7. 已知指针

2、 P指向链表 L中某结点，执行语句 P=P-next 不会删除该链表中结点。 ( )8. 在带头结点的单循环链表中，任一结点的后继指针均不空。( )9. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。( )10. 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。( )11. 设与一棵树 T 所对应的二叉树为 BT ，则与 T 中的叶子结点所对应的 BT 中的结点也一定 是叶子结点。 ( )12. 当一棵具有 n 个叶子结点的二叉树的 WPL 值为最小时， 称其树为 Huffman 树，且其二叉 树的形状必是唯一的。 ( )13. 二叉树的前序遍历并不能唯一确定这棵树，是因为我们

3、不知道该树的根结点是哪一个。( )14. 对于有 n 个结点的二叉树，其高度为 log 2n。 ()二、选择题(共40题，每题 1分，共 40分)1. 通常从正确性、易读性、健壮性、高效性等四个方面评价算法( 包括程序 )的质量。以下解释错误的是 ( )A 、正确性 算法应能正确地实现预定的功能 (即处理要求 )B、易读性 算法应易于阅读和理解 以便于调试 修改和扩充C、健壮性 当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运 行结果D、高效性 即达到所需要的时间性能2. 数据的存储结构是指( )B、数据的逻辑结构在计算机中的表示C、数据在计算机中的顺序存储方式D、存储在外

4、存中的数据A、数据所占的存储空间量3. 下列属于线性数据结构的是 ( )D.不确定D数据项A. 队列B.树C.图4. 线性表是具有 n 个 ()的有限序列A 表元素B字符C数据元素5. 对于顺序表的优缺点，以下说法错误的是( )A、无需为表示结点间的逻辑关系而增加额外的存储空间B、可以方便地随机存取表中的任一结点C、插入和删除运算较方便D、容易造成一部分空间长期闲置而得不到充分利用6. 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以( )为标准操作A、结点移动B、条件判断C、算术表达式D 、赋值语句7若线性表最常用的操作是存取第i 个元素及其前驱的值，则采用( ) 存储方式节省时间A.

5、 单链表B.双向链表C.单循环链表D. 顺序表8. 单链表的每个结点中包括一个指针 link ，它指向该结点的后继结点。现要将指针 q 指向 的新结点插入到指针 p 指向的结点之后，下面的操作序列中哪一个是正确的？( )A 、 p-link = q-link; q = p-link;B、 p-link = q; q-link = p-link;C、 q-link = p-link; p-link=q;D、q = p-link; p-link = q-link;9在双向循环链表中 ,在 p 指针所指向的结点前插入一个指针q 所指向的新结点 ,其修改指针的操作是 ( )注 :双向链表的结点结构为

6、(prior,data,next) 。 供选择的答案：A.p-prior=q ； q-next=p ； p-prior-next=q ； q-prior=q ；B. p-prior=q ； p-prior-next=q ； q-next=p ； q-prior=p-prior ；C. q-next=p ； q-prior=p-prior ； p-prior-next=q; p-prior=q;D. q-prior=p-prior ； q-next=p ； p-prior=q ； p-prior-next =q ；10. 设有一顺序栈 S，元素 s1,s2,s3,s4,s5,s6 依次进栈，如果

7、 6 个元素出栈的顺序是 s2,s3,s4,s6,s5,s1则, 栈的容量至少应该是 ( )A、2B、3C、5D、611. 设有六列火车，编号为 1，2，3，4，5，6 顺序开进一个栈式结构的站台，问下列输出序 列中，哪个是不可能出现的 ( )A.1,2,3,4,5,6B.6,5,4,3,2,1C.3,1,2,6,5,4D.3,2,1,6,5,412. 一个队列的入队列顺序是 1， 2， 3，4，则队列的输出系列是( )A、4，3，2，1B、1， 2，3，4C、1，4，3，2D、3， 2，4，113. 将一棵有 100 个结点的完全二叉树从根结点这一层开始，每一层上从左到右依次对结点 编号，根

8、结点的编号为 1，则编号为 49 的结点的左孩子编号为 ( )A.98B.99C.50D.4814.二叉树的第I 层上最多含有结点数为 ()IA.2II-1B.2I-1-1I-1C.2I-1ID.2I -115. 设深度为 k 的二叉树上只有度为 0 和度为 2 的结点， 则这类二叉树上所含结点总数最少 ( )A.k+1 B.2k C.2k-1 D.2k+116. 下列有关二叉树的说法正确的是 ( )A. 二叉树的度为 2 B.一棵二叉树度可以小于 2 C.二叉树中至少有一个结点的度为2D.二叉树中任一个结点的度都为 217. 将含有 83个结点的完全二叉树从根结点开始编号，根为1 号，按从上

9、到下、从左到右顺序结点编号，那么编号为 41的双亲结点编号为 ()A.42B.40C.21D.2018.一棵具有n 个结点的完全二叉树的深度是 ()A. log2n +1B.log 2n+1C. log2nD.log 2n-119. 设树 T的度为 4，其中度为 1，2，3和 4的结点个数分别为 4，2，1，1 则 T中的叶子 数为 ( )A.5 B.6 C.7 D.820. 设有 13个值 ,用它们组成一棵哈夫曼树 ,则该哈夫曼树共有 ( )个结点.A.13B.12C.26D.2521树的后根遍历序列等同于该树对应的二叉树的A. 先序序列 B.中序序列C.后序序列 D. 层次序列22. 为解

10、决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将 要输出的数据依次写入该缓冲区， 而打印机则依次从该缓冲区中取出数据。 该缓冲区的逻辑 结构应该是 ( )A. 栈 B. 队列 C. 树 D. 图23. 设栈 S和队列 Q 的初始状态均为空，元素abcdefg 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是 ( )A1B. 2C. 3D. 424. 给定二叉树图所示。设 N 代表二叉树的根， L 代表根结点的左子树， R 代 表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历 方

11、式是 ( )ALRNB. NRLC. RLN D. RNL25. 已知一棵完全二叉树的第 6层(设根为第 1层)有 8 个叶结点，则完全二叉树的结点个 数最多是 ( )A39B. 52 C. 111D. 11926. 将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则 在原来的森林中， u 和 v 可能具有的关系是 I父子关系II.兄弟关系 III. u 的父结点与 v的父结点是兄弟关系 ( )A. 只有 II B.I 和 II C.I 和 IIID.I 、 II 和 III27、若元素 a,b,c,d,e,f 依次进栈，允许进栈、退栈操作交替进行。但不允许连续

12、 三次进行退栈工作，则不可能得到的出栈序列是( )A：dcebfa B： cbdaefC：dbcaef D：afedcb28、某队列允许在其两端进行入队操作， 但仅允许在一端进行出队操作， 则不可 能得到的顺序是( )A：bacdeB：dbaceC：dbcaeD： ecbad29、下列线索二叉树中(用虚线表示线索) ，符合后序线索树定义的是( )30、在下列所示的平衡二叉树中插入关键字 48 后得到一棵新平衡二叉树，在新 平衡二叉树中，关键字 37 所在结点的左、右子结点中保存的关键字分别是（）A：13，48B： 24，48C：24， 53D： 24，9031、在一棵度为 4 的树 T中，若有

13、 20 个度为 4 的结点， 10 个度为 3 的结点， 1 个度为 2 的结点， 10个度为 1 的结点，则树 T的叶节点个数是（）A：41B： 82C：113D：12232、对 n（n 大于等于 2）个权值均不相同的字符构成哈夫曼树， 关于该树的叙述中， 错误的是（）A：该树一定是一棵完全二叉树B：树中一定没有度为 1 的结点C：树中两个权值最小的结点一定是兄弟结点 D：树中任一非叶结点的权值一定不小于下一任一结点的权值33、求整数 n（n0）阶乘的算法如下，其时问复杂度是 （ ）int fact（int n）if （n一 1）return 1;return n*fact（n 一 1）;A

14、. O(logzn)B. 0(n)C. (nlogzn)D. 0(n2)34、已知操作符包括 +、一、*、/、(和 )。将中缀表达式 a+b-a* (c+d)/e-f)+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+时，用栈来存放暂时还不 能确定运算次序的操 作符，若栈初始时为空， 则转换过程中同时保存栈中的 操作符的最大个数是 ( )A. 5B. 7C. 8D. 1135、若一颗二叉树的前序遍历序列为 a, e, b, d, c，后续遍历序列为 b, c, d, e, a， 则根节点的孩子节点 ( )A. 只有 e B. 有 e、bC. 有 e、cD. 无法确定36. 已知两个长

15、度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是A. O ( n )B. O( m *n)C. O( min( m, n) )D. O( max( m, n)37. 一个栈的入栈序列为 1, 2, 3, ,n ，其出栈序列是 P1 ,P2, P3, ,Pn, 。若 P2= 3， 则 P3 可能取值的个数是A. n-3B. n- 2 C. n -1D . 无法确定38. 若将关键字 1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树 T 中， 则 T 中平衡因子为 0 的分支结点的个数是A. 0B. 1C. 2D. 339. 已知

16、三叉树 T 中 6 个叶结点的权分别是 2，3，4，5，6，7，T 的带权(外 部)路径长度最小是A. 27B. 46C. 54D. 5640. 若 X 是后序线索二叉树中的叶结点，且 X 存在左兄弟结点 Y，则 X 的右 线索指向的是A. X 的父结点B. 以 Y 为根的子树的最左下结点C. X 的左兄弟结点 YD. 以 Y 为根的子树的最右下结点三、构造题 (共 2 题，每题 10 分，共 20 分)1. 已知某二叉树的先序遍历序列为： ABDGCEFH ；中序遍历序列为： DGBAECHF 。 (1)试画出该二叉树。 ( 4 分)2）求二叉树的后序遍历序列（ 2 分） （3）试画出该二叉树对应的森林。 （2 分）2.已知字符 A-F 的出现频率依次为 2， 3，5，6，11，9，（1） 给出上述字符最优编码对应的 Huffman 树，并在叶子旁标注相应字符； （3 分 ）（2）计算上述 Huffman 树的带权路径长度。 （2 分）四、算法设计 （26 分）1. 带头结点的单链表，其长度存放在头结点的数据域中，设计一算法求 倒数 第 k 个结点的 值，并且删除该结点。要求：（