数据结构学期样卷一

1、学期样卷一单项选择题1有一个带头结点的单链表HEAD,则判断其是否为空链表的条件是（B。A. HEAD=NULLB. HEAD-NEXT=NULLC. HEAD-NEXT=HEADD. HEAD!=NULL注:不带头结点若L为头指针，指向链表的第一个结点_L=NULL,为空表2 .若线性表最常用的操作是存取第i个元素及其前驱的值，可采用（D存储方式最节省时间。A.单向链表B.双向链表C.单向循环链表D.顺序表注:当线性表的长度变化较大、难以估计其存储规模时，采用动态链表存储比较好;当线性表的长度变化不大、易于事先确定其大小时，为了节约存储空间，应采用顺序表作为存储结构；若线性表的操作主要是进行

2、查找，很少做插入或者删除操作，基于时间考虑，宜采用顺序表作为存储结构；对于频繁进行采用链表存储，若表的插入或删除发生在首尾俩端，则采用带尾指针的单循环链表。3 .某个栈的入栈的序列为A,B,C,D,E,则可能的出栈序列是（CA.ADBECB. EBCADC. BCDEAD. EABCD注AA进栈就出栈,B,C,D进栈,D出栈，但B不能在C前面出栈B.A,B,C,D,E进栈,E出栈，但B不能先出栈C. A先进栈,B进栈就出栈,C进栈就出栈，D进出,E进出最后出AD. -8工加建进栈,先出栈,人不能先出4.广义表(a,(b,(c的表尾是(DoA. (cB. (cC. (cD. (b,(c注：(1D

3、二(:空表，其长度为0(2A=(a,(b,c:表长度为2的广义表,其中第一个元素为单个数据a,第二个元素是一个子表(b,c。(3B;(A,A,D:表长度为3,其前俩个元素为表A,第三个元素是空表D。(4C=C:长度为2递归定义的广义表,C相当于无穷表C=(a,(a,(a,(-o(5Head(A=a,即表A的表头是a。（6Tail（A=（b,c,即表A的表尾是（b,c。广义表的表尾一定是一个表6 .一棵深度为h的二叉树，其结点总数最多为（2Ah-lo在二叉树的第i层上至多有2A（i-1个结点对任意一颗二叉树T,若终端结点数为nO,而其度数为2的结点数为n2,则n0=n2+l具有n个结点的完全二叉

4、树的深度为log2An+17 .AVL树是一种平衡的二叉排序树，树中任一结点的（B。A.左右子树的高度均相同8 .左右子树高度差的绝对值不超过1C.左子树的高度大于右子树的高度D.左子树的高度小于右子树的高度注：左右子树也是平衡二叉排序树8 .在关键字随机分布的前提下，用二叉排序树的方法进行查找，其平均长度同（折半查找数量级相同。9 .对于一个有向图，若一个顶点的度为kl,出度为k2,则对应的邻接表中，该结点单链表中的边结点数为（B。A. klB. k2C. kl-k2D.kl+k2注:在无向图的邻接表中，顶点Vi的度恰好就是第i个单链表上结点的个数在有向图中，第i个单链表上结点的个数只是顶点

5、Vi的出度只需通过表头向量表中找到第i个顶点的边链表的头指针。10.下列关键字序列中，（D是堆A. 16,72,31,23,94,53B. 94,23,31,72,16,53C. 16,53,23,94,31,72D. 16,23,53,31,94,72注:堆可以看成一棵完全二叉树：任一根节点二左右孩子（或者白（大的叫大根堆,小的叫小根堆。注意一个堆中的这种性质有一致性，不能既有大于又有小于情况存.填空题1 .如下程序段：for（i=1;iNEXT=Lao注:单链表中判别条件为p!二NULL或p-next!二NULL;而单循环链表的判断条件是p!=La或p-next!=Lao3 .在一棵度为3

6、的树中，其中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个,则度为0的结点数为（6个。注:一个结点的子树个数称为此结点的度；树中所有结点的度的最大值是数的度。树中结点数等于所有结点度数的和加lo所以：2+l+2+X=2*3+l*2+2*l+X*0+l所以X=65 .在待排序的兀素序列基本有序的前提下，效率最高的排序方法是（直接排序或冒泡排序。7 .若用一个大小为6的数组来实现循环队列,且当前的rear和front的值为0和3,当从队列中删除1个元素后，front的值为（4,再加入2个元素后，rear的值为（2o注:front为头指针指示器，出队front+l;rear为尾指针

7、指示器进队,rear+2。Rear-front=Max,队列为满;求元素个数可以用这个公式：（尾指针-头指针队列长度+18 .设有一个二维数组AL.12,1.10,采用以行序为主序存储，每个数据元素占有2个字节,该数组的首元素的地址为1200,则A6,5的地址为（。注:任意兀素Aij的地址计算公式:Loc(Aij=Loc(All+(n*(i-l+j-l*sizeA6,5=1200+(10*(6-1+5-1*2=13089 .设一哈希表表长必为100用除留余数法构造哈希函数，即H(K二K%P,为使函数具有较好性能,P应选(烂100的素数。注:P为小于等于M的最大素数三.构造题1给定权值8,12,4,5,26,16,9,构造一棵带权路径最短的二叉树，并计算其带权路径长度。注：803347161721268991245WPL=(4+5*4+(8+9+12*3+(16+26*2=207WPL二刀Wi*LiWi为第i个叶子结点的权值,Li为第i个叶子结点的路