数据结构课程（本科）期末针对性训练（4份含答案）(g)

数据结构课程（本科）期末针对性训练

训练第一套

一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分） 1. 若需要利用形参直接访问实参，则应把形参变量说明为( )参数。 A. 指针 B. 引用 C. 传值 D. 常值

2. 在二维数组中，每个数组元素同时处于（ ）个向量中。 A. 0 B. 1 C. 2 D. n

3. 已知单链表A长度为m，单链表B长度为n，它们分别由表头指针所指向，若将B整体连接到A的末尾，其时间复杂度应为（ ）。 A. O(1) B. O(m) C. O(n) D. O(m+n)

4. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。

A. front == rear B. front != NULL C. rear != NULL D. front == NULL

4. 若让元素1,2,3依次进栈，则出栈次序不可能出现( )种情况。 A. 3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,2

6. 在一棵高度为5(假定树根结点的高度为0)的完全二叉树中，所含结点个数至少等于( )。

A. 16 B. 64 C. 31 D. 32

7. 向具有n个结点的二叉搜索树中插入一个结点的时间复杂度大致为( )。 A. O(1) B. O(log2n ) C. O(n) D. O(nlog2n)

8. 具有n个顶点的有向图最多可包含有( )条有向边。 A．n-1 B．n C．n(n-1)/2 D．n(n-1)

9. 图的广度优先搜索类似于树的（ ）遍历。

A. 先根 B. 中根 C. 后根 D. 层次

二、填空题，在横线处填写合适的内容（每小题2分，共14分） 1. 链表只适用于____________查找。

2. 设双向循环链表中每个结点的结构为(data,llink,rlink),则结点*p的前驱结点的地址为__________。

3. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有________

1

个结点。

4. 假定一棵树的广义表表示为a(b,c,d(e,f),g(h))，则结点f的层数为_________。假定树根结点的层数为0。

5. 从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向根的________继续搜索。

6. 每次从第i至第n个元素中顺序挑选出一个最小元素，把它交换到第i个位置，此种排序方法叫做_____________排序。

7. 快速排序在最坏情况下的时间复杂度为____________。

三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题2分，共14分） 1. 数据的逻辑结构与数据元素本身的内容和形式无关。

2. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。

3. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，则对它分别进行前序遍历和按层遍历时具有相同的结果。

4. 能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。

5. 邻接表表示只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。

6. 在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。

7. 向一棵B树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少1。

四、运算题（每小题6分，共30分）

1. 假定一棵二叉树广义表表示为a(b(c(,g)),d(e,f))，分别写出对它进行先序、中序和后序遍历的结果。

先序： 中序： 后序：

2. 有7个带权结点，其权值分别为3,7,8,2,6,10,14，试以它们为叶子结点生成一棵霍夫曼树，求出该树的带权路径长度。

带权路径长度：

2

3. 已知图G=(V,E)，其中 V={a,b,c,d,e}，

E={,,,,,,}

在该图的邻接表表示中，每个顶点单链表各有多少个边结点。

顶点： a b c d e 边结点数：

4. 已知一个AOV网的顶点集V和边集G分别为： V={0,1,2,3,4,5,6,7};

E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<5,7>,<6,7>}; 若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列。

拓扑序列：

5. 已知有一个数据表为{30,16,20,15,38,12,44,53,46,18,26,86}，给出进行归并排序的过程中每一趟排序后的数据表变化。

(0) [30 16 20 15 38 12 44 53 46 18 26 86]

(1) (2) (3) (4)

五、算法分析题（每小题6分，共12分）

1. 该算法功能为：从表头指针为la的、按值从小到大排列的有序链表中删除所有值相同的多余元素，并释放被删结点的动态存储空间。阅读算法，在划有横线的上面填写合适的内容。

void purge_linkst(ListNode *& la) {

ListNode *p,*q; if(la==NULL) return; q=la; p=la->link; while(p) {

if(p->data>q->data) {q=p; p=p->link;} else {

q->link= ____________; delete(p);

p=____________;

3

}

} }

2. 已知二叉树中的结点类型BinTreeNode定义为:

struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是从二叉树BT中查找值为X的结点，若查找成功则返回结点地址，否则返回空。阅读算法，在划有横线的上面填写合适的内容。

BinTreeNode* BTF(BinTreeNode* BT, ElemType x) {

if(BT==NULL) NULL;

else {

if(BT->data==x) ____________; else {

BinTreeNode* t;

if(t=BTF(BT->left, x)) return t;

if(t=____________________ ) return t; return NULL; } }

}

六、算法设计题（每小题6分，共12分）

1. Q 是一个由其队尾指针和队列长度标识的循环队列，请写出插入一个元素的算法。 struct CyclicQueue // 循环队列定义 {

ElemType elem[M]; //M为已定义过的整型常量

int rear; // rear指向队尾元素的后一个位置 int length; // length 指示队列中元素个数 };

bool EnCQueue(CyclicQueue& Q, ElemType x);

//Q是一个循环队列，若队列不满，则将x插入并返回true；否则返回false。 //在下面写出该函数的函数体

4

2. 已知二叉搜索树中的结点类型BinTreeNode定义为:

struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数BST指向一棵二叉搜索树的根结点。试根据下面的函数声明编写一个递归算法，向BST树中插入值为item的结点，要求若树中不存在item结点则进行插入并返回1表示插入成功，若树中已存在item结点则不插入并返回0表示插入失败。

int Insert(BinTreeNode*& BST, const ElemType& item);

5

答案供参考

一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分） 1. B 2. C 3. B 4. D 5. C 6. D 7. B 8. D 9. D

二、填空题，在横线处填写合适内容（每小题2分，共14分） 1. 顺序 2. p->llink 3. 1 4.2 5. 右子树 6. 直接选择 7. O(n)

三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题2分，共14分） 1. 对 2. 对 3. 对 4. 错 5. 错 6. 对 7. 错

四、运算题（每小题6分，共30分） 1. 先序：a,b,c,g,d,e,f //2分 中序：c,g,b,a,e,d,f //2分 后序：g,c,b,e,f,d,a //2分

2. 带权路径长度：131

3. 评分标准：每个数据对给1分，全对给6分。 顶点： a b c d e 边结点数： 1 1 2 1 2

4. 评分标准：若与答案完全相同得6分，若仍为一种拓扑序列则得3分，其他则酌情处理。

拓扑序列：1,3,6,0,2,5,4,7

5. 分步给分

(0) [30 16 20 15 38 12 44 53 46 18 26 86]

(1) [16 30][15 20][12 38][44 53][18 46][26 86] //1分 (2) [15 16 20 30][12 38 44 53][18 26 46 86] //1分 (3) [12 15 16 20 30 38 44 53][18 26 46 86] //2分 (4) [12 15 16 18 20 26 30 38 44 46 53 86] //2分

五、算法分析题（每小题6分，共12分）

1. p->link、q->link //每空3分 2. return BT、BTF(BT->right, x) //每空3分

六、算法设计题（每小题6分，共12分） 评分标准：根据编程完整程度酌情给分。

1. bool EnCQueue(CyclicQueue& Q, ElemType x);

2

6

{

if(Q.length==M) return false; //1分 Q.elem[Q.rear]=x; //2分 Q.rear=(Q.rear+1)%M; //4分 Q.length++; //5分 return true; //6分 }

2. int Insert(BinTreeNode*& BST, const ElemType& item) {

if(BST==NULL){

BinTreeNode* p=new BinTreeNode; p->data=item;

p->left=p->right=NULL; BST=p; return 1;

} //3 else if(item==BST->data) return 0; //4 else if(itemdata)

return Insert(BST->left, item); //5 else

return Insert(BST->right, item); //6 }

说明：函数体中的三个else保留字均可以被省略。

分 分 分 分 7

训练第二套

一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分） 1. 下面程序段的时间复杂度为( )。

for(int i=0; i

for(int j=0; j

A. O(m) B. O(n) C. O(m*n) D. O(m+n)

2. 在二维数组中，每个数组元素同时处于（ ）个向量中。 A. 0 B. 1 C. 2 D. n

3. 设有两个串t和p，求p在t中首次出现的位置的运算叫做（ ）。 A. 求子串 B. 模式匹配 C. 串替换 D. 串连接

4. 利用双向链表作线性表的存储结构的优点是（ ）。

A. 便于单向进行插入和删除的操作 B. 便于双向进行插入和删除的操作 C. 节省空间 D. 便于销毁结构释放空间

5. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行( )操作。

A. top->link=s; B. s->link=top->link; top->link=s; C. s->link=top; top=s; D. s->link=top; top=top->link;

6. 一棵具有35个结点的完全二叉树的高度为( )。假定空树的高度为-1。 A. 5 B. 6 C. 7 D. 8

7. 向具有n个结点的堆中插入一个新元素的时间复杂度为( )。 A. O(1) B. O(n) C. O(log2n) D. O(nlog2n)

8. 在一棵AVL树中，每个结点的平衡因子的取值范围是( )。 A. -1?1 B. -2?2 C. 1?2 D. 0?1

9. 一个有n个顶点和n条边的无向图一定是( ) 的。 A．连通 B．不连通 C．无回路 D．有回路

二、填空题，在横线处填写合适的内容（每小题2分，共14分） 1. 数据结构包括__________、存储结构和对数据的运算这三个方面。

2. 一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的_________存取的。

3. 将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则该一维数组需要至少具有_________个元素。

2

2

8

4. 对于一棵具有n个结点的树，该树中所有结点的度数之和为__________。

5. 在一棵高度为3的理想平衡二叉树中，最少含有________个结点，假定树根结点的高度为0。

6. 假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底层的结点数为______个。

7. 用邻接矩阵存储图，占用的存储空间与图中的________数有关。

三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题2分，共14分） 1. 算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。

2. 用字符数组存储长度为n的字符串，数组长度至少为n+1。

3. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

4. 邻接矩阵适用于稀疏图的表示，邻接表适用于稠密图的表示。

5. 对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。

6. 在索引顺序结构的搜索中，对索引表只可以采取顺序搜索，不可以采用折半搜索。

7. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。

四、运算题（每小题6分，共30分）

1. 假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行中序、后序、按层遍历的结果。

中序： 后序： 按层：

2. 一个一维数组a[12]中存储着有序表(15,26,34,39,45,56,58,63,74,76,80,86)，根据折半搜索所对应的判定树，写出该判定树中度为1的结点个数，并求出在等概率情况下进行成功搜索时的平均搜索长度。

度为1的结点个数： 平均搜索长度：

3. 假定一个线性序列为(38,42,55,15,23,44,30,74,48,26)，根据此线性序列中元素的排列次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点、右子树为空的所有单支结点和所有叶子结点，请按照结点值从小到大的次序写出。

9

左子树为空的所有单支结点： 右子树为空的所有单支结点： 所有叶子结点：

4. 已知一个图的顶点集V和边集G分别为： V={1,2,3,4,5,6};

E={<1,2>,<1,3>,<2,4>,<2,5>,<3,4>,<4,5>,<4,6>,<5,1>,<5,3>,<6,5>}; 假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：

(1) 从顶点1出发进行深度优先搜索所得到的顶点序列； (2) 从顶点1出发进行广度优先搜索所得到的顶点序列。

(1)： (2)：

5. 已知一个数据序列为{16,45,27,23,41,15,56,64}，请把它调整为一个最大堆。

最大堆：

五、算法分析题（每小题6分，共12分）

1. 下面算法的功能为：将两个有序单链表合并成一个有序单链表并返回其表头指针。阅读算法，在划有横线的上面填写合适的内容。

ListNode* Merge1(ListNode*& p1, ListNode*& p2) {

ListNode* p=new ListNode, *f=p; while(p1!=NULL && p2!=NULL)

{

if(p1->data<=p2->data) {

p->link=p1; ______________; }

else {p->link=p2; p2=p2->link;} ______________; }

if(p1!=NULL) p->link=p1; else p->link=p2; p1=p2=NULL; return f->link; }

2. 已知二叉树中的结点类型BinTreeNode定义为:

struct BinTreeNode {ElemType data; BinTreeNode *left, *right;}; 其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面算法的定义指出其功能。算法中参数BT指向一棵二叉树。 BinTreeNode* BTreeSwopX(BinTreeNode* BT)

10

{

if(BT==NULL) return NULL; else {

BinTreeNode* pt=new BinTreeNode; pt->data=BT->data;

pt->right=BTreeSwopX(BT->left); pt->left=BTreeSwopX(BT->right); return pt; } }

算法功能：

六、算法设计题（每小题6分，共12分）

1. 已知f为单链表的表头指针, 单链表中的结点结构为(data,link），并假定每个结点的值均为大于0的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最大值，若单链表为空则返回数值0。 int Max(LinkNode *f);

2. 设Q是一个由其队尾指针和队列长度标识的循环队列，按照下面队列定义和函数声明写出从此队列中删除一个元素的算法。 // 循环队列定义 struct CyclicQueue {

ElemType elem[M]; //M为已定义过的整型常量 int rear; //rear指向队尾元素的后一个位置 int length; //length 指示队列中元素个数 };

//若队列非空则删除队头元素并由引用参数x带回，同时返回true；否则若队列为空则返回false。

bool DelCQueue(CyclicQueue& Q, ElemType& x);

11

12

答案供参考

一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分） 1. C 2. C 3. B 4. B 5. C 6. A 7. C 8. A 9. D

二、填空题，在横线处填写合适的内容（每小题2分，共14分）

1. 逻辑结构 2. 下标（或顺序号） 3. n(n+1)/2 4. n-1 5. 8 6. 19 7. 顶点

三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题2分，共14分） 1. 错 2. 对 3. 对 4. 错 5. 对 6. 错 7. 对

四、运算题（每小题6分，共30分） 1. 中序：c,b,a,e,d,f //2分 后序：c,b,e,f,d,a //2分 按层：a,b,d,c,e,f //2分

2. 度为1的结点个数：5 //3分 平均搜索长度：37/12 //3分

3. 左子树为空的所有单支结点：15,23,42,44 //2分 右子树为空的所有单支结点：30 //2分 所有叶子结点：26,48,74 //2分

4. (1) 1,2,4,5,3,6 //3分 (2) 1,2,3,4,5,6 //3分

5. 最大堆： {64,45,56,23,41,15,27,16}

五、算法分析题（每小题6分，共12分）

1. p1=p1->link、p=p->link //每空3分 2. 生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右子树（或左、右孩子的值）交换的结果。

六、算法设计题（每小题6分，共12分） 1. 评分标准：按注释酌情给分。 int Max(LinkNode *f)

{

if(f==NULL) return 0; //1分 if(f->link==NULL) return f->data; //2分 int temp=Max(f->link); //4分 if(f->data>temp) return f->data; //5分

13

else return temp; //6分 }

2. 评分标准：按注释酌情给分。

bool DelCQueue(CyclicQueue& Q, ElemType& x) {

if(Q.length==0) return false; //1分 x=Q.elem[(Q.rear-Q.length+M)%M]; //4分 Q.length--; //5分 return true; //6 }

分 14

训练第三套

一、单项选择题，在括号内填写所选择的标号（9小题，每小题2分，共18分） 1. 当一个作为实际参数传递的对象占用的存储空间较大并且需要修改时，则对应的形参应说明为( )。

A. 基本类型 B. 引用型 C. 指针型 D. 常值引用型

2. 在一个长度为n的顺序表的任一位置插入一个新元素的时间复杂度为（ ）。 A. O(n) B. O(n/2) C. O(1) D. O(n2)

3. 栈的插入和删除操作在( )进行。

A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置

4. 已知广义表为A((a,b,c),(d,e,f))，从A中取出原子e的运算是（ ）。 A．Tail(Head(A)) B．Head(Tail(A))

C．Head(Tail(Head(Tail(A)))) D．Head(Head(Tail(Tail(A))))

5. 在一棵树的静态双亲表示中，每个存储结点包含( )个域。 A 1 B 2 C 3 D 4

6. 有向图中的一个顶点的度数等于该顶点的( )。 A．入度 B．出度

C．入度与出度之和 D．(入度+出度)/２

7. 与邻接矩阵相比，邻接表更适合于存储( )。

A．无向图 B．连通图 C．稀疏图 D．稠密图

8. 较快的数据搜索方法是（ ）搜索方法。 A. 顺序 B. 折半 C. 单链 D. 散列

9. 在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（ ）引起的。 A. 同义词之间发生冲突 B. 非同义词之间发生冲突 C. 同义词之间或非同义词之间发生冲突 D. 散列表“溢出”

二、填空题，在横线处填写合适内容（12小题，每小题1分，共12分） 1. 算法的一个特性是________，即算法必须在执行有限步之内结束。

2. 属性与操作相同的对象构成类，类中的每个对象称为该类的________。

3. 在单链表中, 除了表头结点外, 任意结点的存储位置由其直接________结点的指针域的值所指示。

4. 队列的删除操作在________进行。

15

5. 在一个非空广义表中，除第一个元素之外，由其他所有元素组成的表称为该广义表的________。

6. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有________个。

7. 在一个最小堆中，堆顶结点的值是所有结点中的________。

8. 在一棵具有n个结点的AVL树上进行插入或删除元素的时间复杂度大致为_________。

9. 在对n个元素进行直接选择排序的算法中，记录比较总次数的时间复杂度为________。

10. 在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用_________次调整算法。

11. 在索引表中，每个索引项至少包含有__________域和地址域这两项。

12. 在一棵m阶的B树上，除树根结点外，每个结点的子树数至少为________棵。

三、判断题，在每小题前面打对号表示正确或打叉号表示失败（10小题，每小题1分，共10分）

1. 线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。

2. 在线性链表中删除结点时，只需要将被删结点释放，不需要修改任何指针。

3. 在用单链表表示的链式队列Q中，假定队头指针为Q->front，队尾指针为Q->rear，则链队为空的条件为Q->front==Q->rear。

4. 一棵AVL树的所有叶结点不一定在同一层次上，同样，平衡的m路搜索树的叶结点也不一定在同一层次上。

5. 一个广义表((a),((b),c),(d))的表尾是“((b),c),(d)”。

6. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，若对它分别进行中序遍历和后序遍历，则具有相同的结果。

7. 折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。

8. 对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。

9. 如果有向图中各个顶点的度都大于2，则该图中必有回路。

16

10. 堆排序是一种稳定的排序方法。

四、运算题（5小题，每小题6分，共30分）

1. 假定一棵二叉树的广义表表示为A(B(,D(G)),C(E,F))，分别写出对它进行先序、中序、按层遍历的结果。

先序： 中序： 按层：

2. 已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。

元素

34 56 58 63 94 比较次数

3. 假定一个线性序列为(56,27,34,95,73,16,50,62,65)，根据此线性序列中元素的排列次序生成一棵二叉搜索树，求出该二叉搜索树的高度（假定树根结点的高度为0）、度为2的结点个数、单支结点数和叶子结点个数。

高度：

度为2的结点个数： 单支结点数： 叶子结点数：

4. 已知一个带权图的顶点集V和边集G分别为： V={0,1,2,3,4,5};

E={(0,1)19,(0,2)21,(0,3)14,(1,2)16,(1,5)5,(2,3)26,(2,4)11,(3,4)18,(4,5)6};

试根据普里姆算法从顶点0出发得到最小生成树，在下面填写依次得到的各条边。

________, ________, ________, ________, ________。

5. 设散列表的长度m=13；散列函数为H (K)=K mod m，给定的关键码序列为{19,14,23,40,68,20,84,27,55,11}，并假定采用的闭散列表为HT[m]，采用的解决冲突的方法为线性探查法，求出在最后得到的散列表中，关键码19,40,84和55的存储位置和对应的查找长度。

19,40,84,55的存储位置依次为： 19,40,84,55的查找长度依次为：

17

五、算法分析题（3小题，每小题6分，共18分）

1. 设单链表的存储结构为ListNode=(data,link)，表头指针为LH，所存线性表L=(’a’,’b’,’c’,’d’,’e’,’f’,’g’)，若执行unknown(LH)调用下面算法，则写出执行结束后的输出结果。

void unknown（LinkNode *Ha） { //Ha为指向单链表的头指针 if(Ha){

unknown(Ha->link); cout<data; } }

输出结果：

2. 下面算法的功能为：将两个有序单链表合并成一个有序单链表并返回其表头指针。阅读下列算法, 按标号填写空缺的内容，要求统一填写在算法后面的标记处。 ListNode* Merge1(ListNode*& p1, ListNode*& p2) {

ListNode* p=new ListNode, *f=p; while(p1!=NULL && p2!=NULL) {

if(p1->datadata) {

___(1)___; p1=p1->link; }

if(p1->data>p2->data) { p->link=p2; p2=p2->link; }

else {

p->link=p1; p1=p1->link; p=p->link; p->link=p2; p2=p2->link; }

___(2)___;

}

if(p1!=NULL) p->link=p1; else ___(3)___; p1=p2=NULL; return f->link; }

(1) (2) (3)

3. 已知二叉树中的结点类型BinTreeNode定义为:

struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面

18

算法的定义指出其功能。算法中参数BT指向一棵二叉树。 BinTreeNode* BTreeSwopX(BinTreeNode* BT) {

if(BT==NULL) return NULL; else {

BinTreeNode* pt=new BinTreeNode; pt->data=BT->data;

pt->right=BTreeSwopX(BT->left); pt->left=BTreeSwopX(BT->right); return pt; } }

算法功能：

六、算法设计题（2小题，每小题6分，共12分）

1. Q 是一个由其队尾指针和队列长度标识的循环队列，请写出插入一个元素的算法。 struct CyclicQueue // 循环队列定义 {

ElemType elem[M]; //M为已定义过的整型常量

int rear; // rear指向队尾元素的后一个位置 int length; // length 指示队列中元素个数 };

bool EnCQueue(CyclicQueue& Q, ElemType x);

//Q是一个循环队列，若队列不满，则将x插入并返回true；否则返回false。 //在下面写出该函数的函数体

2. 已知二叉搜索树中的结点类型BinTreeNode定义为:

struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数BST指向一棵二叉搜索树的根结点。试根据下面的函数声明编写一个递归算法，向BST树中插入值为item的结点，要求若树中不存在item结点则进行插入并返回1表示插入成功，若树中已存在item结点则不插入并返回0表示插入失败。

int Insert(BinTreeNode*& BST, const ElemType& item);

19

答案供参考

一、单项选择题，在括号内填写所选择的标号（9小题，每小题2分，共18分） 1. B 2. A 3. A 4. C 5. B 6. C 7. C 8. D 9. C

二、填空题，在横线处填写合适内容（12小题，每小题1分，共12分） 1. 有穷性 2. 实例 3. 前驱 4. 队头（或队首） 5. 表尾 6. 6 7. 最小值 8. O(log2n)

2

9. O(n) 10. n-1 11. 关键码（或索引值） 12. ?m/2?

三、判断题，在每小题前面打对号表示正确或打叉号表示错误（10小题，每小题1分，共10分）

1. 对 2. 错 3. 错 4. 对 5. 错 6. 对 7. 对 8. 错 9. 错 10. 错

四、运算题（5小题，每小题6分，共30分） 1. 先序：A,B,D,G,C,E,F //2分 中序：B,G,D,A,E,C,F //2分 按层：A,B,C,D,E,F,G //2分

2. 评分标准：对1个数据给1分，全对给6分 元素 34 56 58 63 94 比较次数 2 1 3 4 4

3. 高度：4 //2分 度为2的结点个数：2 //2分 单支结点数：4 //1分 叶子结点数：3 //1分

4. (0,3)14,(3,4)18,(4,5)6,(5,1)5,(4,2)11

5. 19,40,84,55的存储位置依次为：6,2,8,5 //4分，每个数据1分 19,40,84,55的查找长度依次为：1,2,3,3 //2分，每两数据1分

五、算法分析题（3小题，每小题6分，共18分） 1. gfedcba

2. (1) p->link=p1 //2分 (2) p=p->link //2分 (3) p->link=p2 //2分

3. 生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右子树（或左、右孩子的值）交换的结果。

20

六、算法设计题（2小题，每小题6分，共12分） 评分标准：根据编程完整程度酌情给分。 1. if(Q.length==M) return false; Q.elem[Q.rear]=x; Q.rear=(Q.rear+1)%M; Q.length++; return true;

2. int Insert(BinTreeNode*& BST, const ElemType& item) {

if(BST==NULL){

BinTreeNode* p=new BinTreeNode; p->data=item;

p->left=p->right=NULL; BST=p; return 1;

}

else if(item==BST->data) return 0; else if(itemdata)

return Insert(BST->left, item); else

return Insert(BST->right, item); }

说明：函数体中的三个else保留字均可以被省略。

21

训练第四套

一、单项选择题，在括号内填写所选择的标号（9小题，每小题2分，共18分） 1. 一个数组元素a[i]与( )的表示等价。

A. *(a+i) B. a+i C. *a+i D. &a+i

2. 设有一个n?n的对称矩阵A，将其下三角部分按行为主序存放在一个一维数组B中，A[0][0]存放于B[0]中，则A[i][i]存放于（ ）中。

A. B(i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2

3. 根据n个元素建立一个有序单链表的时间复杂度为（ ）。 A. O(1) B. O(n) C. O(n) D. O(nlog2n)

4. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。

A. front+1==rear B. rear+1==front C. front==0 D. front==rear

5. 如果一个递归函数过程中只有一个递归语句，而且它是过程体的最后可执行语句，则称这种递归为（ ），它很容易被改写为非递归过程。 A. 单向递归 B. 回溯递归 C. 间接递归 D. 尾递归

6. 假定一棵二叉树的第i层上有3i个结点，则第i+1层上最多有( )个结点。 A. 3i B. 6i C. 9i D. 2i

7. 从具有n个结点的AVL树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为( )。

2

A. O(n) B. O(1) C. O(log2n) D. O(n)

8. 对于具有e条边的无向图，它的邻接表中共有( )个边结点。 A．e-1 B．e+1 C．2e D．3e

9. 图的深度优先搜索遍历类似于树的（ ）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次

二、填空题，在横线处填写合适内容（每小题1分，共12分） 1. 数据结构的存储结构包括顺序、________、索引和散列四种。

2. 在程序运行过程中进行存储空间分配的数组是__________分配的数组。这种数组在声明它时需要使用数组指针。

3. 在链表中进行插入和 操作的效率比在顺序存储结构中进行相同操作的效率高。

2

22

4. 栈是一种限定在表的一端进行插入和删除操作的线性表，又称它为___________表。

5. 如果一个对象部分地包含自己，或自己定义自己，则称这个对象是_________的对象。

6. 假定一棵树的广义表表示为a(b,c,d(e,f),g(h))，则结点f的层数为_________。假定树根结点的层数为0。

7. 若把一棵树按照左子女-右兄弟表示法转换成一棵对应的二叉树，则该二叉树的树根结点肯定没有________子女。

8. 向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的________上。

9. 设图G=(V,E)，V={1,2,3,4}, E={<1,2>,<1,3>,<2,4>,<3,4>}，从顶点1出发，对图G进行广度优先搜索的序列有________种。

10. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做__________类排序。

11. 快速排序在平均情况下的空间复杂度为____________。

12. 若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为________。

三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题1分，共10分） 1. 算法和程序的概念完全相同，在讨论数据结构时二者是通用的。

2. 插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常被使用。

3. 栈和队列都是顺序存取的线性表, 但它们对存取位置的限制不同。

4. 将f=1+1/2+1/3+?+1/n转化为递归函数时，递归部分为f(n)=f(n-1)+1/n，递归结束条件为f(1)=1。

5. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中序遍历时具有相同的结果。

6. 进行折半搜索的表必须是顺序存储的有序表。

7. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。

23

8. 对于AOE网络，任一关键活动延迟都将导致整个工程的延迟完成。

9. 将一批杂乱无章的数据按小根堆结构组织起来并存储到一维数组中, 则堆中的数据必然按从小到大的线性顺序排列。

10. 一棵m阶B树中每个结点都最多有m-1个关键码，最少有?m/2?-1个关键码。

四、运算题（每小题6分，共30分）

提示：在进行每题运算时，若需要最好先在草稿纸上根据题意画出对应的图形，这样会更直观和简便。

1. 设有一个10?10的矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。

A[8][5]在B中的存放位置（即下标位置）为：

2. 已知一棵树的静态双亲表示如下，其中用-1表示空指针，树根结点存于0号单元，分别求出该树的叶子结点数、单分支结点数、两分支结点数和三分支结点数。

序号： 0 1 2 3 4 5 6 7 8 9 10 data: a b c d e f g h i j k parent: -1 0 1 1 3 0 5

叶子结点数： 单分支结点数：

两分支结点数： 三分支结点数：

3. 已知图G=(V,E)，其中 V={a,b,c,d,e}

E={，，，，，，} 请写出各结点的出度和入度。

结点 出度 入度

4. 已知一个AOV网络的顶点集V和边集G分别为：

V={0,1,2,3,4,5,6,7};

E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<5,7>,<6,7>}; 若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号(即dest域的值)从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列。

a b c d e 6 6 0 9 24

拓扑序列：

5. 已知有一个数据表为{30,18,20,15,38,12,44,53,46,18*,26,86}，给出进行归并排序的过程中每一趟排序后的数据表变化。

(0) [30 18 20 15 38 12 44 53 46 18* 26 86] (1) (2) (3) (4)

五、算法分析题（3小题，每小题6分，共18分）

1. 该算法功能为：从表头指针为la的、按值从小到大排列的有序链表中删除所有值相同的多余元素，并释放被删结点的动态存储空间。阅读算法，按标号填写空缺的内容，要求统一填写在算法后面的标记处。

void purge_linkst(ListNode*& la) {

ListNode *p,*q;

if(la==NULL) return; q=la; p=la->link; while (p) {

if(___(1)___) {q=p; p=p->link;} else {

q->link= ___(2)___; delete(p); p=___(3)___; } } }

(1) (2) (3)

2. 请写出下面算法的功能，其中Stack表示栈类，Queue表示队列类。 void unknown(Queue &Q) {

Stack S; int d;

S.InitStack( ); //初始化S为空栈

while(!Q.IsEmpty( )) { //队列Q不为空则循环

Q.DeQueue(d); //出队列元素的值由变量d带回

25

S.Push(d); //d的值压入S栈

}

while(!S.IsEmpty( )) { //栈S不为空则循环

S.Pop(d); //出栈元素的值由变量d带回 Q.EnQueue(d); //d的值插入队列Q中 } }

算法功能：

3. 已知二叉树中的结点类型BinTreeNode定义为:

struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面算法的定义指出其功能。算法中参数BT指向一棵二叉树。 BinTreeNode* BTreeSwopX(BinTreeNode* BT) {

if(BT==NULL) return NULL; else {

BinTreeNode* pt=new BinTreeNode; pt->data=BT->data;

pt->right=BTreeSwopX(BT->left); pt->left=BTreeSwopX(BT->right); return pt; } }

算法功能：

六、算法设计题（2小题，每小题6分，共12分）

1. 已知f为单链表的表头指针, 单链表中的结点结构为(data,link），并假定每个结点的值均为大于0的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最大值，若单链表为空则返回数值0。 int Max(LinkNode *f);

26

2. 设Q是一个由其队尾指针和队列长度标识的循环队列，按照下面队列定义和函数声明写出从此队列中删除一个元素的算法。 // 循环队列定义 struct CyclicQueue {

ElemType elem[M]; //M为已定义过的整型常量 int rear; //rear指向队尾元素的后一个位置 int length; //length 指示队列中元素个数 };

//若队列非空则删除队头元素并由引用参数x带回，同时返回true；否则若队列为空则返回false。

bool DelCQueue(CyclicQueue& Q, ElemType& x);

27

答案供参考

一、单项选择题，在括号内填写所选择的标号（9小题，每小题2分，共18分） 1. A 2. A 3. C 4. D 5. D 6. B 7. C 8. C 9. A

二、填空题，在横线处填写合适内容（每小题1分，共12分） 1. 链接 2. 动态 3. 删除 4. 后出先进 5. 递归 6. 2 7. 右 8. 左子树 9. 2 10. 交换 11. O(log2n) 12. 500

三、判断题，在每小题前面打对号或打叉号（每小题1分，共10分） 1. 错 2. 错 3. 对 4. 对 5. 错 6. 对 7. 对 8. 对 9. 错 10. 错

四、运算题（每小题6分，共30分） 1. 41

答案说明：根据题意，矩阵A中当元素下标I与J满足I≥J时，任意元素A[I][J]在一维数组B中的存放位置为I*(I+1)/2+J，因此，A[8][5]在数组B中位置为： 8*(8+1)/2+5=41

2.

叶子结点数： 5 //2分 单分支结点数：3 //2分 两分支结点数：2 //1分 三分支结点数：1 //1分

3. 评分标准：每个结点的出度和入度值正确得1分，全对得6分。

a B c d e 结点 出度 入度

1 2 1 2 2 1 1 1 2 1 4. 评分标准：若与答案完全相同得6分，若仍为一种拓扑序列则得3分，其他则酌情处理。

拓扑序列：1,3,6,0,2,5,4,7

5. 分步给分

(0) [30 18 20 15 38 12 44 53 46 18* 26 86]

(1) [18 30][15 20][12 38][44 53][18* 46][26 86] //1分 (2) [15 18 20 30][12 38 44 53][18* 26 46 86] //1分 (3) [12 15 18 20 30 38 44 53][18* 26 46 86] //2分 (4) [12 15 18 18* 20 26 30 38 44 46 53 86] //2分

28

五、算法分析题（3小题，每小题6分，共18分）

1. (1) p->data>q->data（或p->data!=q->data） //2分 (2) p->link //2分 (3) q->link //2分

2. 利用\栈\作为辅助数据结构,将队列Q中的元素逆置（即按相反次序放置）。

3. 生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右子树（或左、右孩子的值）交换的结果。

六、算法设计题（2小题，每小题6分，共12分） 1. 评分标准：按注释酌情给分。 int Max(LinkNode *f)

{

if(f==NULL) return 0; //1分 if(f->link==NULL) return f->data; //1分 int temp=Max(f->link); //2分 if(f->data>temp) return f->data; //1分 else return temp; //1分 }

2. 评分标准：按注释酌情给分。

bool DelCQueue(CyclicQueue& Q, ElemType& x) {

if(Q.length==0) return false; //1分 x=Q.elem[(Q.rear-Q.length+M)%M]; //2分 Q.length--; //1分 return true; //2分 }

29

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