1、 数据结构常见题型整合1、设栈的输入序列是 1，2，3，4, 则（ ）不可能是其出栈序列。A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， 2、 在 一 个 链 队 列 中 ， 若 f， r 分 别 为 队 首 、 队 尾 指 针 ， 则 插 入 s 所 指 结 点 的 操 作 为 ( )(A) f-next=c； f=s (B) r-next=s； r=s(C) s-next=r； r=s (D) s-next=f； f=s3、顺序存储的栈和队列中已经各有 N 个结点，要删除一个结点分别需要移动数据（ ）次和（ ）次。A. N/2 , N B.
2、N , N/2 C. 0 , N D. N , 04、 设有三个元素 X，Y，Z 顺序进栈（进的过程中允许出栈） ，下列得不到的出栈排列是( )。AXYZ B. YZX C. ZXY D. ZYX5、 一个递归算法必须包括（ ） 。A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分6、如下四个选项中，那个选项是能够正确判断循环队列是否排满元素的操作（其中MAXQSIZE 表示队列的容量） （ ）：Aif (Q.rear = Q.front) Bif (Q.rear = (Q.front + MAXQSIZE)Cif (Q.rear = (Q.front + 1)
3、% MAXQSIZE)Dif (Q.front = (Q.rear + 1) % MAXQSIZE)7、 假设以数组 Am存放循环队列的元素，其头尾指针分别为 front 和 rear，则当前队列中的元素个数为（ ） 。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m8、 若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为多少？( ) A. 1 和 5 B. 2 和 4 C. 4 和 2
4、 D. 5 和 1 9、利用栈进行十进制数1348转换成八进制数，则入栈的数依次是（ ）。A. 1 , 3 , 4 , 8 B. 8 , 4 , 3 , 1 C. 2 , 5 , 0 , 4 D. 4 , 0 , 5 , 2 10、 最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是 （ ） 。A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front11、 栈和队列的共同点是（ ） 。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没
5、有共同点1、 栈是_操作受限（或限定仅在表尾进行插入和删除操作） 的线性表，其运算遵循_后进先出_的原则。2、 队 列 的 插 入 操 作 在 _ 队 尾 _进 行 ， 删 除 操 作 在 队 头 _进 行 ，其特点是_先进先出_。3、 用 S 表示入栈操作， X 表示出栈操作，若元素入栈的顺序为 1234，为了得到 1342 出栈顺序，相应的 S 和 X 的操作串为_SSSS _。4、 表达式求值是_栈_应用的一个典型例子。5、栈和队列在本质上都是同一种基本数据结构的特例，这种基本的数据结构就是 线性表 。6、 在作进栈运算时，应先判别栈是否 . 满 ，在作退栈运算时应先判别栈是否 空 。当
6、栈中元素为 n 个，作进栈运算时发生上溢，则说明该栈的最大容量为 n 。12、在二叉树的第 I 层(I1)上最多含有结点数为（ ） A. 2I B. 2I-1-1 C. 2I-1 D. 2I -113、深度为 6 的二叉树最多有( )个结点 A64 B.63 C.32 D.3114、一棵树高为 K 的完全二叉树至少有 ( )个结点 A.2k 1 B.2k-1 1 C.2k-1 D.2 k 15、有关二叉树下列说法正确的是（ ）A. 二叉树的度为 2 B. 一棵二叉树的度可以小于 2 C. 二叉树中至少有一个结点的度为 2 D. 二叉树中任何一个结点的度都为 216、n 个结点的线索二叉树上含有
7、的线索数为（ ）A. 2n B. nl C. nl D. n 17、线性表和树的结构区别在于（ ）A前驱数量不同，后继数量相同 B前驱数量相同，后继数量不同C前驱和后继的数量都相同 D前驱和后继的数量都不同18、已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为 ABC*+DE/-，则其前缀形式为( )A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE19、设有一表示算术表达式的二叉树（见下图） ，它所表示的算术表达式是（ ）A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*
8、E+（F-G）) D. A*B+C/D*E+F-G20、一棵具有 n 个结点的完全二叉树的树高度（深度）(符号 表示取不大于 x 的最大整x数)是（ ）A. B. C. D.2log1log2)1(log2n1log2n21、利用二叉链表存储树，则根结点的右指针是（ ） 。A指向最左孩子 B指向最右孩子 C空 D非空22、已知一棵二叉树的前序遍历结果为 ABCDEF，中序遍历结果为 CBAEDF，则后序遍历的结果为（ ） 。ACBEFDA B FEDCBA C CBEDFA D不定 23、若前序遍历二叉树的结果为序列 A、B、C，则有_棵不同的二叉树可以得到这一结果。A. 3 B. 4 C.
9、5 D. 624、线索二叉树是一种（ ）结构。A逻辑 B逻辑和存储 C物理 D线性 二、填空题 7、对于任意一棵二叉树，如果其叶子结点数为 N0，度为 1 的结点数为 N1，度为 2 的结点数为 N2，则 N0=_ N2 + 1_。8、具有 256 个结点的完全二叉树的深度为_9_。9、一个深度为 4 的二叉树，其结点至少有 4 个，至多有 15 个：10、深度为 H 的完全二叉树至少有 _ 2H-1_个结点；至多有 2H-1_个结点；H 和结点总数N 之间的关系是 H=log2N+1。11、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，N
10、个结点的二叉树共有_2N_个指针域，其中有_N-1_个指针域是存放了地址，有_N+1_个指针是空指针。12、设一棵赫夫曼树有 6 个叶子结点，权值分别为 3、4、7、14、15、20，则根结点的权值是_63_13、对一棵完全二叉树，设一个结点的编号为 i，若它的左孩子结点存在，则其编号为 2i ；若右孩子结点存在，则其编号为 2i+1 ；而双亲结点的编号为 。 2/i14、赫夫曼树是带权路径长度 最小的 二叉树，又称最优二叉树，路径上权值较大的结点离根较近。15、下 面 程 序 段 的 功 能 是 建 立 二 叉 树 的 算 法 ， 请 在 下 划 线 处 填 上 正 确 的 内 容 。typ
11、edef struct node int data; struct node *lchild;_ struct node *rchild _; BiTNode, *BiTree;void createBitree(BiTree if(ch=#) T=NULL ;else T=( BiTNode *)malloc(sizeof(BiTNode); T-data=ch; createBitree(T-lchild)； _createBitree(T-rchild);16、二叉树由_根结点_，_左子树_，_右子树_三个基本单元组成。17、树的链表存储结构常用的有三种，其中，双亲 表示法 以一组连续空
12、间存储树的结点，在每个结点中设一个指示器指示双亲结点的位置。孩子 表示法 每个结点的孩子以单链表的形式存储，n 个结点有 n 个孩子链表，n 个头指针又组成一个线性表，并以顺序存储结构存储。孩子兄弟 表示法 以二叉链表作为树的存储结构，链表中的结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。/P135-13618、利用树的孩子兄弟表示法存储，可以将一棵树转换为_二叉树_。19、在二叉树中，指针 p 所指结点为叶子结点的条件是_ p-lchild=NULL & p-rchlid=NULL _。20、树的孩子兄弟表示法和二叉树的二叉链表表示法，本质是一样的，只是解释不同，也就是说树（
13、树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。21、树和二叉树逻辑上都是树形结构，但是二叉树不是树的特例，二叉树与树是两个不同的概念。二叉树的度 至多为 2，树无此限制；二叉树有左右子树之分，即使在只有一个分枝的情况下， 也必须指出是 左子树还是右子树，树无此限制。三、简答题 1、已知一棵二叉树的前序遍历的结果是 ABKCDFGHIJ，中序遍历的结果是 KBCDAFHIGJ, 试画出这棵二叉树，并写出后序遍历结果。 答案：当前序序列为 ABKCDFGHIJ，中序序列为 KBCDAFHIGJ 时，逐步形成二叉树的过程如下图所示：
14、这棵二叉树的后序遍历结果是：K D C B I H J G F A2、某通信电文由 A、B、C、 D、E、F 六个字符组成，它们在电文中出现的次数（权值）分别是 16，5，7，3，8，1。试画出其哈夫曼树，确定其对应的哈夫曼编码，并计算其带权路径长度。为使结果唯一，请将权值较小的结点作为其双亲的左孩子，而将权值较大的结点作为其双亲的右孩子。答案：哈夫曼树如下：对应的哈夫曼编码如下：A: 0B: 101C: 110D: 1001E: 111F: 1000带权路径长度为: WPL=(1+3)*4+(5+7+8)*3+16*1=923、对下图所示二叉树分别按前序中序后序遍历，给出相应的结点序列，同时
15、给二叉树加上中序线索。答案：（1）前序序列：ABDEHCFG（2）中序序列：DHEBAFCG（3）后序序列：HEDBFGCA （4）中序线索见图中虚线箭头所示。25、以下数据结构中，哪种具有非线性结构？A栈 B队列 C双向链表 D十字链表 26、下面关于图的存储的叙述中正确的是（ ） 。 A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。 B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。 C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。 D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关AB CD FGEHnul nul
