《数据结构》02级（计算机）期末考试A卷

《算法与数据结构》期末考试A卷

姓名： 班别： 得分：

一、填空题（每小题2分，共16分）

1、堆栈是操作受限的线性结构，只能在 栈顶 插入和删除元素；不能进行插入和删除元素的一端称为 栈底 。

2、 稀疏矩阵的存储结构主要有 三元组 和 邻接链表 两种。

3、有一个10阶对称矩阵A，采用压缩存储方式（以行为主存储），A[0][0]的地址是100（每个元素占一个基本存储单元），则A[8][5]的地址是 185 。

4、设有一棵深度为n的二叉树，它至少有 2^(n-1) 个结点，至多 2^n-1 有 个结点。

5、序列ABC依次进栈，则最多有__4____种出栈序列。

6、 动态存储管理主要是解决系统如何_______________、_____________的两大问题。 7、 对于内部排序，有多种排序方法。按排序基本思想（策略），可分为 、 、 和基数排序。

8、 对于文件，按其记录的类型可将文件分为 文件、 文件；而按物理结构划分，可分为顺序文件、 文件、 文件和多关键字文件。

二、单项选择题（请将您的选择写在题目后的括号中。每题2分，共16分）

1、线性表若采用链式存储结构时，要求内存中可用存储单元的地址是（ D ）。

（A） 必须是连续的 （B） 部分地址必须是连续的 （C） 一定是不连续的 （D） 是否连续没有要求 2、下面程序段的时间复杂度是（ D ）。 Int i=2;

While ((n%i)!=0&&i*1.0

（A） O(n) （B） O(n2) （C） O(㏒2n) （D） O(√ n ) 3、向一个栈顶指针为top的链栈中压入一个P所指向的结点，执行的操作是（ B ）。 （A） top→next=p；p→next=top； （B） p→next=top；top=p；

1

（C） p→next=top→next； （D） p→next=top；

top→next=p→next； top=top→next；

4、一般树的存储结构主要有（ B ）。 （A） 双亲表示法，孩子表示法，链表表示法 （B） 双亲表示法，孩子表示法，孩子—兄弟表示法 （C） 双亲表示法，孩子—兄弟表示法，链表表示法 （D） 双亲表示法，孩子—兄弟表示法，链表表示法

5、设有一棵二叉树，其先序遍历序列是abdgcef，中序遍历的序列是dgbaecf，则其后序遍历序列是（ D ）。

（A） bdgcefa （B） gbdecfa （C） bdgacef （D） gdbefca 6、 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍， 所有顶点的度之和等于所有顶点的入度之和的 倍。（ B ） （A） 1/2，1 （B） 1，2 （C） 2，1 （D） 1，4

7、 设有一个长度为n的线性表，当采用顺序查找方法时，每个元素的平均查找长度是

(n+1)/2 ；而采用二分查找方法时，其平均查找长度是 。（ ） （A）n/2 ,O(n) （B）(n+1)/2, O(n㏒2n) （C）(n+1)/2, O(㏒2n) （D）n/2,O(㏒2n) 8、设有一组记录的关键字是（37，28，56，80，60，14，25，50），用快速排序法以第一个记录为基准得到的一次划分结果是（ ）。

（A） 25，28，37，14，56，80，60，50 （B） 25，28，37，14，60，80，56，50 （C） 25，28，14，37，60，56，80，50 （D） 25，28，14，37，60，80，56，50

三、分析题（前6题7分，第7题8分，共50分）

1、若以{4，5，7，9，12，15}作为叶子结点的权值构造Huffman树，请画出所构造的Huffman树，并计算其带权路径。 51 21

31

9 12 15 16 4 5 7 9

WL=(12+15)*2+(4+5+7+9)*3=129

2

2、假设使用下述两种结点的链表作广义表的存储结构：

rlink 表结点： Tag=1 dlink 元素结点： Tag=0 data 请画出广义表（（a，b），(a，(b))，c，(d，(e，f))）的存储结构。

3、 设有一棵树如下图，请先将此树转换为二叉树，然后给出对图的中序线索树。

4、 对于下图中的网，写出该网的邻接链表，然后写出其深度优先搜索生成树（假设从顶点V1出发）。

2

a b c d e f g h i 8 13 1 7 6 4 5 10 3 3

3 3 4

5、 将关键字序列（10，3，18，7，8，13，25，14，2）依此插入到初态为空的二叉排序树中，请画出所得到的树T；然后画出删除13之后的二叉排序树T1；最后再后画出插入13之后的二叉排序树T2。

6、线性表的关键字集合{87，25，310，8，27，132，68，95，187，123，70，63，47}，共有13个元素，已知散列函数为：H（k） = k % 13，采用链地址处理冲突，设计出这种链表结构。

7、已知序列{500，90，520，60，900，160，800，270}，对其实现大顶堆排序，请列出初始堆、建堆及前两趟输出并筛选调整后的结果。

4

四、算法填空（8分）

请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。

2、有向图的正邻接链表的建立。 #define Max_Vex_Num 30

typedef struct LinkNode typedef struct VexNode /*链表中结点类型定义*/ /*向量中分量的*结点类型定义/ { int adjvex ; { VexType data;

struct LinkNode *nextarc ; LinkNode *firstarc; } LinkNode ; } VexNode ; typedef struct ALGraph /*图的数据结构类型定义*/ { int vexnum ;

VexNode Adjlist[Max_Vex_Num] ; } ALGraph ;

Void Create_Graph_Adjlist(ALGraph *G, int num,int eds) /*形参num,eds分别表示图的顶点数和边数*/

{ int i ,bvex,evex; // bvex,evex分别保存有向边的起点和终点 LinkNode p,pre;

For (i=0;i

{ G→adjlist[i].data=i; G→adjlist[i].firstarc=NULL ; } For (i=1;i<=eds;i++)

{ printf(“ 请输入边的起点和终点编号: ”) ; scanf(“%d,%d”,&bvex,&evex) ;

p=( LinkNode *)malloc(sizeof(LinkNode)); p→adjvex=evex; p→nextarc=NULL; if (G→adjlist[bvex].firstarc==NULL) G→adjlist[bvex].firstarc=p ; else { pre= G→adjlist[bvex].firstarc ;

while (pre→nextarc!=NULL) pre=pre→nextarc ;

5

pre→nextarc=p ;

}

}

_____ G→vexnum=num______;

}

五、编写算法（要求给出相应的类型说明， 10分）

1、以二叉链表为存储结构，统计二叉树中度为2的结点个数。 #typedef char Elem_Type #typedef BT

{ Elem_Type data;

Struct BT *Lchild,*Rchild; }

Int Two_Tree(BT *T) {int num1,num2;

If(T==NULL)return 0;

Else { num1= Two_Tree(T->Lchild); Num2= Two_Tree(T->Rchild);

If(T->Lchild!=NULL&& T->Rchild!=NULL) return num1+num2+1; Else return num1+num2;

} }

6

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