武大计算机考研数据结构部分（2007考研）-A

数据结构部分（共75分）

一. 单项选择题（2×10分，共20分）

1. 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用 d 存储方式最节省运算时间。

A. 单链表 B.循环单链表 C. 双链表 D.仅有尾结点指针的循环单链表 2. 栈和队列的共同点是 c 。 A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点

3．对于含有n个互不相同字符的串，则真子串（不包括串自身）的个数是 c 。 A. n B.n2 C.n(n+1)/2 D.n(n-1)/2

4. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为 2*2+1*1=5。

A. 4 B. 5 C. 6 D. 7

5. 某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 d 。 A. 空或只有一个结点 B. 完全二叉树 C. 二叉排序树 D. 高度等于其结点数

6. 对图1所示的无向图，从顶点1开始进行深度优先遍历；可能得到顶点访问序列是 a 。

A.1 2 4 3 5 7 6 C.1 2 4 5 6 3 7

1 3

2 B.1 2 4 3 5 6 7 D.1 2 3 4 5 7 6

5 4 6 7 图1 一个无向图

7. 对于含有n个顶点的带权无向连通图，它的最小生成树是指该图中任意一个d。 A.由n-1条权值最小的边构成的子图 B.由n-l条权值之和最小的边构成的子图 C.由n条权值之和最小的边构成的连通子图

D.由n个顶点构成的边的权值之和最小的连通子图

8. 有一组数据{15,9,7,8,20,1,7,4}，用堆排序的筛选方法建立的初始小根堆为 c 。 A.{1,4,8,9,20,7,15,7} C.{1,4,7,8,20,15,7,9}

B.{1,7,15,7,4,8,20,9} D.以上都不对

2 2008年攻读硕士学位研究生入学考试试题 9. 在含有27个结点的二叉排序树上，查找关键字为35的结点，则依次比较的关键字有可能是 d 。

A.28,36,18,46,35 B.18,36,28,46,35 C.46,28,18,36,35 D.46,36,18,28,35

10. 采用败者树进行k路平衡归并的外排序算法，其总的归并效率与k b 。 A.有关 B.无关

二. 问答题（共30分）

1.（5分）分析以下算法的时间复杂度（要求给出求解过程）。

void fun(int n) {

int i,s=0; while (s

} }

i++; s+=i;

2.（5分）设b是二叉树（采用二叉链存储结构存储）的根结点指针，给出以下算法的递归模型并说明算法的功能：

int fun(BTNode *b) {

if (b==NULL) return 0;

else if (b->lchild!=NULL && b->rchild!=NULL)

return fun(b->lchild)+fun(b->rchild)+1; else

return fun(b->lchild)+fun(b->rchild);

}

3.（5分）有一个长度为12的有序表R[0..11]，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数是多少？（要求给出求解过程）

4.（8分）一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。

先序序列： B F ICEH G 中序序列：D KFIA EJC 后序序列： K FBHJ G A

5.（4分）对于有n个顶点、e条边的图

（1）若是无向图，采用邻接矩阵存储，其非零的元素有多少？ （2）若是有向图，采用邻接矩阵存储，其非零的元素有多少？

（3）若是无向图，采用邻接表存储，其表头结点和表结点个数是多少？ （3）若是有向图，采用邻接表存储，其表头结点和表结点个数是多少？ 6．（3分）简要说明在执行快速排序算法时，若把栈换为队列会对最终排序结果有什

2008年攻读硕士学位研究生入学考试试题 3 么影响？

三. 算法设计题（共25分）

1. （10分）设有一个带头结点的单链表hc，设计一个算法：

void split(LinkList *hc, LinkList *&ha, LinkList *&hb,ElemType x,ElemType y) 将hc拆分成两个带头结点的单链表ha和hb，其中ha的所有结点值均大于等于x且小于等于y，hb为其他结点。

2．（15分）假设一棵二叉树采用二叉链存储结构进行存储，每个结点的类型如下（每个结点值均为正整数且大小均不同）：

typedef struct node

{ int data;

struct node *lchild,*rchild; /*左、右孩子结点指针*/

} BSTNode; （1）（10分）设计一个算法int isBST(BSTNode *bt)，判断二叉树bt是否是一棵二叉排序树；

（2）（5分）说明你的算法的正确性。

数据结构部分参考答案

一. 单项选择题（2×10分，共20分）

1.D

2.C

3.C

4.B

5.D 6.A 7.D

8.C

9.D

10.B

二. 问答题（共30分）

1. 算法中的基本操作为while语句，设while循环语句执行T(n)次，有： s=1+2+3+…+T(n)

(1+T(n))*T(n)

2n?O(n)

所以算法时间复杂度为O(n)。

评分标准：只有正确结果给2分，推导过程为3分。 2. 答：

对应的递归模型如下： f(b)=0 b=NULL

f(b)=f(b->lchild)+f(b->rchild)+1 若*b为双分支结点 f(b)=f(b->lchild)+f(b->rchild) 其他情况 该算法用于计算b二叉树中双分支结点的个数。 评分标准：递归模型占3分，功能占2分。

3. 构造相应的判定树如图2所示(图中结点的值对应元素的序号)，第一层1个结点，

4 2008年攻读硕士学位研究生入学考试试题 第二层2个结点，第三层个4结点，第四层5个结点，则：ASL=

评分标准：只有正确结果给2分，推导过程为3分。 0～11 0～4 2 0～1 0 1 1～1 3～4 6～7 3 4 4～4 6 7 5 1*1?2*2?3*4?4*537=。

12126～11 8 9～11 10 9 11 11～11 0～4 9～9 图2 一棵判定树

4. 由这些显示部分推出二叉树如图3所示。则先序序列为：ABDFKICEHJG；中序序列为：DBKFIAHEJCG；后序序列为：DKIFBHJEGCA。

评分标准：二叉树、先序序列、中序序列和后序序列各占2分。

B D K F I H E J A C G

图3 一棵二叉树

5. 对于有n个顶点、e条边的图 （4分） （1）2e （2）e（3）n+2e （3） n+e 评分标准：每小题1分 6．在执行快速排序算法时，用栈保存每趟快速排序划分后左、右子区段的首、尾地址，其目的是为了在处理子区段未排序子序列时能够知道其范围，这样才能对该子序列进行排序(排序过程中可能产生新的左、右区段)，但这与处理子序列的先后顺序没什么关系，而仅仅起存储作用。因此，用队列同样可以存储子区段的首、尾地址，即可以取代栈的作用。在执行快速排序算法时，把栈换为队列对最终排序结果不会产生任何影响。

评分标准：答没有影响的给1分，说明原因的给2分。

三. 算法设计题（共25分）

1.（10分）

void split(LinkList *hc,LinkList*&ha, LinkList *&hb,

ElemType x,ElemType y)

{

2008年攻读硕士学位研究生入学考试试题 5 LinkList *p=hc->next,*ra,*rb; ha=hc; ra=ha;

hb=( LinkList *)malloc(sizeof(LinkList)); rb=hb;

while (p!=NULL) {

if (p->data>=x && p->data<=y) {

ra->next=p; ra=p; } else {

rb->next=p; rb=p; }

p=p->next; }

R1->next=r2->next=NULL; }

评分标准：有多种解法，以上是采用尾插法建表，也可以从hc中删除满足条件的结点另建表等，根据情况判分。

2．解：（1）

int d=0;

int isBST(BSTNode *bt) {

int b1,b2; if (bt==NULL)

return 1; else {

b1=isBST(bt->lchild);

if (b1==0 || bt->data>d) return 0; d=bt->data;

b2=isBST(bt->rchild); return b2; } }

评分标准：不能只判断左孩子小于根结点，右孩子大于根结点，即以堆来判断，这样扣6分，另根据算法情况适当判分。

（2）如果一棵二叉树的中序序列是一个递增的有序序列，则它是一棵二叉排序树。

6 2008年攻读硕士学位研究生入学考试试题 评分标准：若只给出二叉排序的定义给3分。

本文来源：https://www.bwwdw.com/article/aw4w.html