数据结构复习案例.doc

一、选择题 1、在有N个叶子结点的哈夫曼树中，其结点总数为（ ）。 A、不确定 B、2N C、2N+1 D、2N-1 2、具有2000个结点的二叉树，其高度至少为（ ）。 A、9 B、10 C、11 D、12 3、对于任何一颗二叉树T，设N0、N1、N2分别是度为0、1、2的结点数，则N0=（ ）。 A、N0=N1+1 B、N0=N1+N2 C、N0=N2+1 D、N0=2N1+1 4、深度为K且为（ ）个结点的二叉树称为满二叉树（设根结点处于第1层）。 A、2K-1 B、2K C、2K-1 D、2K-1 5、设一数列的顺序为1，2，3，4，5，6，通过队列操作可以得到（ ）的输出序列。 A、3，2，5，6，4，1 B、1，2，3，4，5，6 C、6，5，4，3，2，1 D、4，5，3，2，6，1 6、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ ）。 A、3 B、4 C、5 D、1 7、下列哪一个程序片段是在链表中间插入一个结点。（假设新结点为NEW，欲插入在Pointer结点之后） A、NEW-next=Pointer B、 NEW-next=Pointer-next Pointer=NEW Pointer-next=NEW C、Pointer-next=NEW-next D、 以上皆非 NEW-next=Pointer 8、线性表的链接实现有利于（ ）运算。 A、插入 B、读表元 C、查找 D、定位 9、线性表采用链式存储时，其地址（ ）。 A、必须是连续的 B、一定是不连续的 C、部分地址必须是连续的 D、连续与否均可以 10、二叉树第I（I≥1）层上至多有（ ）结点。 A、 2I B、 2I C、 2I-1 D、 2I-1 11、线性表是（ ）。 A、一个有限序列，可以为空 B、一个有限序列，不可以为空 C、一个无限序列，可以为空 D、一个无限序列，不可以为空 12、数据结构是研究数据的（ ）以及它们之间的相互关系。 A、理想结构，物理结构 B、理想结构，抽象结构 C、物理结构，逻辑结构 D、抽象结构，逻辑结构 13、若某线性表采用顺序存储结构，每个元素占四个存储单元，首地址为100，则下标为11的元素的存储地址为。替换 ）。 A、 B、 C、 D、1、非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。(?? ) 2数组。(?? ) 3 4、空串与由空格组成的串没有区别。(?? ) 5 6、深度为h的非空二叉树的第i层最多有2h-1 个结点。(?? ) 7完全二叉树就是满二叉树。(?? ) 8一棵二叉树的序序列和中序序列唯一地构造出二叉树。(?? ) 9非空二叉排序树的任意一棵子树也是二叉排序树。(?? ) 10有向图是一种非线性结构。(?? ) 五、算法设计题 1、用递归算法求二叉树的深度，请将下面的算法补充完整。 已知二叉树的链式存储结构为： typedef struct node { char data; struct node *lchild, *rchild; } BTCHINALR; /*已知二叉树bt，求该二叉树的深度，并返回该二叉树的深度 */ Int treehigh ( BTCHINALR *bt ) { int lh, rh, h; //lh、rh分别存放左、右子树的高度 if ______(1)_______ h = 0; else { ______(2)_____________; rh = treehigh ( bt-rchild ); h = ____(3)______________; //二叉树的深度为左、右子树的深度 //的最大值，再加1 } _______(4)_______________ } 一、选择题 1.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素