2007数据结构试题A(答案)

中国人民公安大学2006~2007学年第二学期

2005级侦查学专业计算机犯罪侦查专业方向 《数据结构》期末考试卷（A卷）参考答案及评分标准

一、判断题（正确的打“V”，错的打“X”。每小题1分，共10分）

1. （v）双向链表中至多只有一个结点的后继指针为空。

2. （x）在循环队列中，front指向队列中第一个元素的前一位置，rear

指向实际的队尾元素，队列为满的条件是front=rear。 3. （v）对链表进行插入和删除操作时，不必移动结点。

4. （v）栈可以作为实现程序设计语言过程调用时的一种数据结构。 5. (x ) 在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图

中必有一条弧。 6. (x ) 对有向图G，如果从任一顶点出发进行一次深度优先或广度

优先搜索就能访问每个顶点，则该图一定是完全图。 7. （x） “顺序查找法”是指在顺序表上进行查找的方法。 8. (v) 向二叉排序树插入一个新结点时，新结点一定成为二叉排序树

的一个叶子结点。 9. （v） 关键字序列{A，C，D，E，F，E，F}是一个堆。 10. （x） 二路归并时，被归并的两个子序列中的关键字个数一定要相

等。

二、填空题：(每小题2分,共 20分)

1．一棵含有101个结点的完全二叉树存储在数组A[1..101]中, 对

1≤k≤101, 若A[k]是非叶结点, 则k的最小值是： 1 。

2．设s=’YOU ARE JUDGING IT RIGHT OR WRONG’，顺序执行下列操作：SubString(sub1,s,1,8); SubString(sub2,s,20,5); StrCat(sub1,sub2); 则最后sub1的值为： ’YOU ARE RIGHT’ 。

3．若一个算法中的语句频度之和为T(n) = 3720n+4nlogn，则算法的时间复杂度为_ O(nlogn) ___ 。

4．广义表((((a),b),c),d)的表头是 (((a),b),c) ，表尾是 (d) 。 5．已知有向图的邻接矩阵，要计算i号结点的入度，计算方法是： 将 i列元素 累加。

6．要在一个单链表中p所指结点之后插入一个子链表，子链表第一个结点的地址为s，子链表最后一个结点的地址为t, 则应执行操作： t->next=p->next 和 p->next=s 。

7．用带头结点的循环链表表示的队列,若只设尾指针rear, 则队空的条件是 rear->next==rear 。 8．已知二维数组A[10][20]采用行序为主方式存储，每个元素占2个存储单元,并且A[0][0]的存储地址是1024, 则A[6][18]的地址是 1300 /1260 。

9．在n个结点的二叉树的二叉链表中,共有 n+1 个空链域。 10．n个顶点的连通无向图至少有 n-1 条边。

三、简答题：（每小题6分，共30分）

1．什么情况下二叉排序树的查找性能较好？什么情况下二叉排序树的查找性能最差？

答：当二叉排序树接**衡二叉树或完全二叉树时查找性能较好，当二叉排序树为单边单枝二叉树时查找性能最差。

2．比较顺序表与单链表的优缺点。

答：顺序表优点：随机查找，存储密度大

顺序表缺点：插入、删除不便，静态分配，表长固定 单链表优点：插入、删除方便，动态分配，表长灵活 单链表缺点：查找不便，存储密度小

3．请写出栈的链式存储结构的类型定义。 答：typedef struct node{

ElemType data; struct node * next; } *LinkStack;

4．队列属于哪种常见的数据结构？说明原因。

答：队列属于线性结构，因为队列中的元素均是按序排列的，除队头外，每个元素均有一个严格的后继；除队尾外，每个元素均有一个严格的前驱。

5．什么叫内部排序？举出4个以上的内部排序方法。

答：内部排序是指待排序记录存放在计算机随机存储器中进行的排序过程。

常见的内部排序有：冒泡法、选择法、堆排序法和桶排序法等。（答案不唯一，答出4种即可）

四、应用题：（每小题10分，共30分）

1．已知二叉树的中序序列为DBGEAFC，后序序列为DGEBFCA，给

出对应的二叉树。

2．已知一个图的顶点为A、B、C、D，其邻接矩阵的上三角元素全为0（包括主对角线元素），其他元素均为1。请画出该图，并给出其邻接表。

3．给定权值{8，12，4，5，26，16，9}，构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。

或者

五、算法设计题：（10分）

已知二叉树T，写算法求该二叉树中叶子结点的个数。 答：

基本思路：可以改造任何对树遍历的算法，计算树中结点的个数。