数据结构试题4

肇庆学院《数据结构》2001级试卷(A)一、单项选择题（2分×10=20分）1．若某线性表中最常用的操作是删除第1个元素，则不宜采用（）存储方式。A.单链表B.双链表C.单向循环链表D.顺序表2．在一棵完全二叉树的顺序存储方式中，若编号i的结点有右孩子1，则其右孩子的编号为（）。A.2iB.2i-1C.2i+1D.i/23.按照二叉树的定义，具有3个结点的二叉树有（）种不同形态。A、3B.4C.5D.64.在长为n的顺序表中，删除第i个元素(1≤i≤n+1)需要向前移动（）个元素。A.n-iB.n-i+1C.n-i-1D.i5.一个队的入队顺序是1、2、3、4、5，则此队的出队顺序为（）。A.5、4、3、2、1B.4、5、3、2、1C.4、3、5、1、2D.1、2、3、4、56.栈是一种特殊的线性表，其特殊性表现在（）。A.可以顺序存储B.只能从端点进行插入和删除C.可以链式存储D.可以在任何位置进行插入和删除7.一棵二叉树中，第k层上最多有（）个结点。A.2kB.2k-1C.2kD.2k-18.一棵有18个结点的二叉树，其高度最小为（）层。A.4B.5C.6D.189.n个顶点的有向图中最多有（）条弧。A.n(n-1)/2B.n(n-1)C.n(n+1)D.n(n+1)/210.有向图中，所有顶点入度和是所有顶点出度和的（）倍。A.0.5B.1C.2D.4二、判断题（1分×10=10分）（F）1.在线性结构的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。（F）2.二叉树就是度为2的树。（T）3.存在这样的二叉树，其后序遍历与中序遍历得到的访问序列相同。（T）4.满二叉树一定是完全二叉树。（F）5.由空格组成的串叫空串。（T）6.在AOE网中，可能有多条关键路径。（T）7.m阶B-树具有k个子树的非叶子结点含有k-1个关键字。（T）8.起泡排序是稳定的。（F）9.链式存储的线性表可以实现随机存取。（F）10.二叉树按某种顺序线索化后，任一结点均有指向其直接前驱和直接后继的线索。三、填空题（2分×8=16分）1．在单链表中，若删除指针p所指结点的直接后继，则需要执行下列三条语句：q=pnext；；free（q）；2．在有头结点的单链表L中，指针p所指结点是最后一个结点的条件是。3．队是一种受限制的线性表，也叫FIFO结构，FIFO的含义是。4.对于栈，只能在插入元素，只能在删除元素。5.数据的基本单位是，在计算机程序中通常作为一个整体进行考虑和处理。6.图的遍历方式通常有遍历和遍历两种。四、简答和应用题（38分）1.（8分）某二叉树后序遍历的结果是ABCDEFG，中序遍历的结果是ADBCGFE.（1）画出此二叉树；（2）写出其先序遍历的结果。2.（9分）已知如图所示有向图，（1）求各点的入度和出度；（2）给出该图的邻接矩阵；（3）给出该图的一个拓扑排序。3.给出下面稀疏矩阵的三元组。（5分）4.（8分）已知序列5，3，4，8，6。（1）以该序列为权构造一棵有5个叶子结点的Huffman树。（2）求上边构造的Huffman树的带权路径长度WPL.5.（8分）已知如图所示的连通网。求其最小生成树（要求画出生成的过程）。五、设计题（16分）1.编写实现“直接插入排序”的子函数，入口参数是整形数组L[]和数组长度n.2.写出统计二叉树叶子结点个数的子函数，入口参数是其根结点指针：BiTree型指针T，其中BiTree定义为：typedefstructBiTNode{chardata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;0090000110001000000010000120000002V1V2V3V4V5V63224313