长沙理工大学计算机与通信工程学院

2013-2014学年二学期数据结构期末考试试卷(B卷)

班级:___________学号:___________姓名:___________得分:___________

题目部分，(卷面共有31题,100分,各大题标有题量和总分)一、应用题(1小题,共8分)

1．已知无向图G的邻接表如图所示，分别写出从顶点1出发的深度遍历和广度遍历序列。

二、判断正误(7小题,共14分)

1．串中任意个字符组成的子序列称为该串的子串。 2．带权无向图的最小生成树是唯一的。（ ）

3．如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（ ） 4．无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的。（ ） 5．向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（ ） 6．堆是完全二叉树，完全二叉树不一定是堆。（ ） 7．数据的逻辑结构和数据的存储结构是相同的。（ ）

三、单项选择题(10小题,共20分) 1．在顺序表中，只要知道（ ），就可以求出任一结点的存储地址。

A．基地址 B．结点大小 C． 向量大小 D．基地址和结点大小

2．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。

A q=p->next；p->data=q->data；p->next=q->next；free(q)； B q=p->next；q->data=p->data；p->next=q->next；free(q)； C q=p->next；p->next=q->next；free(q)； D q=p->next；p->data=q->data；free(q)； 3．循环队列占用的空间( )。

A．必须连续 B．不必连续 C．不能连续 D．可以不连续

4．若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( )。 A．5和1 B．4和2 C．2和4 D．1和5 5．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ ）。 A 20 B 256 C 512 D 1024

6．设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（ ）。

A 4 B 5 C 6 D 7