数据结构学期样卷一

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

2、应采用顺序表作为存储结构;若线性表的操作主要是进行查找,很少做插入或者删除操作,基于时间考虑,宜采用顺序表作为存储结构;对于频繁进行.采用链表存储,若表的插入或删除发生在首尾俩端,则采用带尾指针的单循环链表。3.某个栈的入栈的序列为A,B,C,D,E,则可能的出栈序列是(C 。A.ADBECB. EBCADC. BCDEAD. EABCD注:A. A进栈就出栈,B,C,D进栈,D出栈,但B不能在C前面出栈B. A,B,C,D,E进栈,E出栈,但B不能先出栈C. A先进栈,B进栈就出栈,C进栈就出栈,D进出,E进出,最后出AD. A,B,C,D,E进栈,E先出栈,A不能先出4.广义表(a,(b,

3、(c的表尾是(D 。A.(cB. (cC. (cD. (b,(c注:(1D = (:空表,其长度为0(2A = (a,(b,c:表长度为2的广义表,其中第一个元素为单个数据a,第二个元素是一个子表(b,c。(3B = (A,A,D:表长度为3,其前俩个元素为表A,第三个元素是空表D。(4C = (a,C:长度为2递归定义的广义表,C相当于无穷表C = (a, (a,(a,(.。(5Head(A= a,即表A的表头是a。(6Tail(A= (b,c,即表A的表尾是(b,c。广义表的表尾一定是一个表。6.一棵深度为h的二叉树,其结点总数最多为(2h -1 。在二叉树的第i层上至多有2(i-1个结点

4、对任意一颗二叉树T,若终端结点数为n0,而其度数为2的结点数为n2,则n0=n2+1具有n个结点的完全二叉树的深度为【log2n】+17.A VL树是一种平衡的二叉排序树,树中任一结点的(B 。A.左右子树的高度均相同B. 左右子树高度差的绝对值不超过1C. 左子树的高度大于右子树的高度D. 左子树的高度小于右子树的高度注:左右子树也是平衡二叉排序树8.在关键字随机分布的前提下,用二叉排序树的方法进行查找,其平均长度同(折半查找数量级相同。9.对于一个有向图,若一个顶点的度为k1,出度为k2,则对应的邻接表中,该结点单链表中的边结点数为( B 。A.k1B. k2C. k1-k2D. k1+k

5、2注:在无向图的邻接表中,顶点Vi的度恰好就是第i个单链表上结点的个数在有向图中,第i个单链表上结点的个数只是顶点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;i<=n-1;i

6、+For(j=i+1;j<=n;j+x=x+1;其中的x=x+1执行的语句频度为(n(n-1/2 。注:第一个for语句执行i=0时第二个for语句要执行n-1 然后再回到第一个语句i=1 。n-2 。i=n-2。 1.。i=n-1。结束2.在循环单链表La(La为头指针中,指针p所指结点为表尾结点的条件是(p->NEXT=La 。注:单链表中判别条件为p!=NULL或p->next!=NULL;而单循环链表的判断条件是p!=La或p->next!=La。3.在一棵度为3的树中,其中度为3的结点数为2个,度为2的结点数为1个,度为1的结点数为2个,则度为0的结点数为(6

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

8、尾指针-头指针%队列长度+18.设有一个二维数组A1.12,1.10,采用以行序为主序存储,每个数据元素占有2个字节,该数组的首元素A11的地址为1200,则A6,5的地址为(。注:任意元素Aij的地址计算公式:Loc(Aij=Loc(A11+(n*(i-1+j-1*size A6,5=1200+(10*(6-1+5-1*2=13089.设一哈希表表长M为100,用除留余数法构造哈希函数,即H(K = K%P,为使函数具有较好性能,P应选(<=100的素数。注:P为小于等于M的最大素数三.构造题1.给定权值8,12,4,5,26,16,9,构造一棵带权路径最短的二叉树,并计算其带权路径长度。注:-80- -33 47-16 17 21 26-8 9 9 12-4 5WPL=(4+5*4+(8+9+12*3+(16+26*2=207WPL = Wi*Li Wi为第i个叶子结点的权值,Li