数据结构基础期末试卷13-14 - A

_…__…__…__…__…__…__…__…__…_：…名…姓…… __…__…__…__…__…__…__…_：…号线..学… _…__…__…__…__…__…__ 订.__…__…：…级…班… …__…__装_..__…__…__…__…__…__…__…__…：…业…专… _…__…__…__…__…__…__…：…级…年……诚信应考 考出水平 考出风格

浙江大学城市学院

2013 — 2014 学年第 2 学期期末考试试卷

《 数据结构 》

开课单位： 计算分院 ；考试形式：闭卷；考试时间： 2014 年 06 月 29日； 所需时间： 120 分钟 题序 一 二 三 四 五 六 七 总 分 得分 评卷人 注：试卷答案必须写在答卷上，写在试卷上不得分。

得分 一．判断题(有5条是正确的，将正确的编号写在答卷上，每空 1 分，共 5 分)

1. 数据结构的逻辑结构独立于其存储结构。 2. 某算法的时间复杂度是O（n2），表明该算法的执行时间是问题规模n的平方。 3. 在数据结构中，从逻辑上可以把数据结构分成顺序结构和链式结构。

4. 顺序表可以利用一维数组表示，因此顺序表与一维数组在结构上是一致的，可以通用。 5. 二叉树的叶子结点在先序、中序和后序遍历过程中的相对顺序不变。 6. 二叉树是一棵结点的度最大为二的树。

7. 由树结点的先根序列和后根序列可以唯一地确定一棵树。 8. 广度优先搜索可用于求一个无向图的所有连通分量。

9. 一旦一个图的顶点数组确定后，则该图的邻接矩阵表示是唯一的，但邻接表不唯一。 10. 如果是不连通的无向图，则在相应的邻接矩阵中，一定有全0行和全0列。 得分 二． 选择题 (本大题共 15 题，每题 1 分，共 15 分)

1．下列关于数据的逻辑结构的叙述中， 是正确的。

A．数据的逻辑结构是数据元素间关系的描述

B．数据的逻辑结构反映了数据在计算机中的存储方式 C．数据的逻辑结构分为顺序结构和链式结构 D．数据的逻辑结构分为静态结构和动态结构

第 1 页 共 6 页

2．下列说法中错误的是 。

A．解决同一问题，时间复杂度为O(n)的算法总是优于时间复杂度为O(n2)的算法 B．时间复杂度为O(1)的算法表明该算法的执行时间是不变的 C．时间复杂度是指在最坏情况下估算算法执行时间的一个上限 D．考察算法的时间复杂度与实现的程序语言无关 3．下列函数的时间复杂度为 。

int fun( int n) { int i=1，s=1;

while(s

return i;

B．O(n2)

}

A．O(n) C．O(n/2) D．O()

4．下面关于线性表的叙述中，错误的是 。

A．线性表的顺序存储结构中，元素的逻辑顺序与物理顺序总是一致的

B．线性表的链接存储中，结点除自身信息外还包括指针域，因此空间利用率小于顺序存储 C．顺序存储便于随机存取；而链接存储便于进行插入和删除操作 D．线形表中每个元素都有且只有一个直接前驱和一个直接后继

5．已知L是带表头附加结点的单链表，则删除首元结点的语句是 。

A．L=L->next; B．L->next=L->next->next C．L=L->next->next; D．L->next=NULL;

6．在带表头附加节点且表长大于1的单向循环链表head中，指针p指向表中的某个结点，若p->next->next==head，则 。

A．p指向头结点 B．p指向尾结点 C．*p的直接后继是头结点 D．*p的直接后继是尾结点

7．已知一个栈的进栈序列为1，2，3，…，n，其出栈输出序列是p1，p2，p3，…，pn。若p1=3，则p2的值 。

A．一定是2 B．一定是1 C．可能是1 D．可能是2 8．以1，2，3，…，n的顺序进队列，则可能的出队序列有 种。

A．1 B．n C．n(n+1)/2 D．n!

9. 设栈S和队列Q的初始状态均为空，元素a，b，c，d，e，f，g依次进栈S。如果每个元素出栈后立即进入队列Q，且元素出队的顺序为b，d，c，f，e，a，g，则栈S的容量至少是 。

A．1 B．2 C．3 D．4

10.对二叉树的结点从1开始进行编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用 遍历实现编号。

A．先序 B．中序 C．后序 D．层序 11．先序序列为ABC，后序序列为CBA的二叉树共有 棵不同形态。

A．2 B．3 C．4 D．5

12．一棵深度为k且只有k个结点的二叉树按照完全二叉树顺序存储的方式存放于一个一维数组R[n]中，那么n应至少是 。

A．2k B．2k+1 C．2k-1 D．2k-1 13．G是一个非连通无向图，共有15条边，则该图至少有___________个顶点。

A．5 B．6 C．7 D．8

第 2 页 共 6 页

14．下列关于图的说法中错误的是 。

A．在有向图中，所有顶点的入度之和等于所有顶点的出度之和 B．一个n个顶点有向强连通图至少需要n-1条边

C．存储无向图的邻接矩阵是对称的，因此也可以只存储邻接矩阵的下（或上）三角部分。 D．邻接矩阵法存储图时，在不考虑压缩处理的情况下，所占有的存储空间大小只与图中顶点个数有关，而与图的边数无关。

15．图的广度优先搜索算法的实现中需要使用 作为辅助工具。 A．栈 B．队列 C．线性表 D．链表

得分 三． 填空题 (本大题共 6 题 15 空，每空 1 分，共 15 分)

1．逻辑结构通常用一个二元组B=（K，R）来表示，其中K表示 ⑴ ，R表示 ⑵ 。 2．n个元素的线性表，采用顺序存储结构，插入一个元素要平均移动表中 ⑶ 个元素，删除一个元素要平均移动 ⑷ 个元素。若用此n个元素顺序表构建一个有序的单链表（即n个元素构建有序单链表）的时间复杂度是 ⑸ 。

3．用一维数组a[7]顺序存储一个循环队列，队首和队尾分别用front和rear表示，当前队列中已有5个元素：23，45，67，80，34，若此时rear的值为0，则front的值为 ⑹ ； 此状态下还可以有 ⑺ 个元素进队列。

4．一棵完全二叉树按层序遍历的序列为ABCDEFGHI，若对该二叉树进行先序遍历，则在先序序列中结点E的直接前驱为 ⑻ ；若对该二叉树进行后序遍历，则在后序序列中结点B的直接后继为 ⑼ ；最后一个非终端结点为 ⑽ 。

5．一棵二叉树的中序序列为dbeacf，后序序列为debfca，则此二叉树的先序序列为 ⑾ ，二叉树中共有 ⑿ 个度为1的结点。 6．从邻接矩阵A=

可知，该图共有 ⒀ 个顶点；若该图是有向图，则共有 ⒁ 条边；若该图是无向图，则共有 ⒂ 条边。

得分 四． 解答题 (本大题共 3 题，每题 5 分，共 15 分)

1． 有以下两种带表头附加结点的循环单链表，其中一个设置表头指针，另一个设置表尾指针，

问哪一种设置更好？并说明理由。

L… …

L

第 3 页 共 6 页

2． 一棵二叉树采用顺序存储结构如下图： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 A B D C E H F G I J (1) 画出上述二叉树的二叉链表图示。 (2) 把此二叉树转换成森林。

3． 已知一个图的邻接表存储结构如下所示：

012345ABCDEF∧3∧1402∧325∧∧4∧ (1) 该图是有向图还是无向图？

(2) 根据深度优先遍历算法，写出从顶点A出发所得到的顶点序列。 (3) 根据广度优先遍历算法，写出从顶点A出发所得到的顶点序列。

五． 算法阅读题 (本大题共 3 题，每题 4 分，共 12 分)

1．有下列递归函数，当unknown(5)调用时，写出执行结果。 得分 void unknown ( int w ) {

if ( w ) { unknown ( w-1 ); for ( int i = 1; i <= w; i++ ) cout << w'; cout << endl;

} }

2．已知L是带头结点的非空单链表，且p指针所指结点既不是首元结点（第一个），也不是尾 元结点（最后一个），说明下列算法的功能。

void Ldelete(LNode **L , SLNode *p) {

LNode *q; q=p; p=*L;

while(p->next->next!=q) p=p->next; q=p->next;

p->next=p->next->next; free(q); }

第 4 页 共 6 页

3．设BT为二叉树的根结点指针，p指向二叉树中某一结点，说明下列算法的功能：

BTreeNode* func( BTreeNode *BT, BTreeNode * p) { if( BT==NULL)

return NULL;

if( BT->left==p || BT->right==p )

return BT;

BTreeNode *q = func( BT->left,p ); if( q!=NULL )

return q; else

return func( BT->right,p );

} 得分

六． 算法填空题 (本大题共 2 题 9 空，每空 2 分，共 18 分)

1．有一顺序存储的循环队列Q（Queue Q），下列算法实现元素item入队操作，请在空白处填上合适的语句。 队列存储结构定义为：

struct Queue{

ElemType *queue; // 存储空间基地址 int front,rear; // 队头、队尾指针 int MaxSize; // 数组queue的长度 } ;

void EnQueue (Queue &Q , ElemType item ) {

if ( ⑴ ) //空间不足，扩大2倍

{

int k=sizeof(ElemType);

Q.queue=(ElemType *)realloc(Q.queue,2*Q.MaxSize*k) if(Q.rear!=Q.MaxSize-1) { //移动队列内容，必须要做 for(int i=0; ⑵ ; i++) Q.queue[i+Q.MaxSize]=Q.queue[i]; Q.rear=Q.rear+Q.MaxSize; }

Q.MaxSize=2*Q.MaxSize; //修改队列最大空间 }

⑶ ; //元素入队 Q.queue[Q.rear]=item; }

第 5 页 共 6 页

2．有一个顶点名称为char类型的有向图G，下列算法计算有向图中顶点ch的出度，若无此顶点，显示出错信息。请完成邻接表结构的定义以及算法的实现。 typedef struct EdgeNode{ //边结点

int adjvex; //存放与头结点顶点有关的另一个顶点的下标 ⑷ *next; //指向链表下一个结点 } EdgeNode;

typedef struct VNode{ //顶点 char data; //顶点名称

⑸ *firstarc; //指向边该顶点第一条边 } VNode;

typedef struct{

⑹ vertices[10]; //顶点数组

int vexnum, arcnum; //顶点数和弧数

} ALGraph;

int count(ALGraph G,char ch) { //计算有向图G顶点ch的度

int i , sum=0; EdgeNode *p;

for( i=0; i=G.vexnum ) { cout<<”图中无此顶点！”<

p= ⑻ ; while(p!=NULL){ sum++; ⑼ ; }

return sum; } 得分 七． 算法设计题 (本大题共 2 题，每题 10 分，共 20 分)

1．有一个长度为n的顺序表存储于一维数组a[N]中，其元素均为整形，设计一个算法，将数组a中所有小于表头（a[0]）元素的放在a的前半部分，大于表头元素的放在后半部分，要求时间复杂度为O(n)，空间复杂度为O(1)。函数原型如下：void func(int *a，int n)

2．写一算法求二叉树BT的深度。函数原型如下：int DepthBTree( BTreeNode *BT)

第 6 页 共 6 页

2．有一个顶点名称为char类型的有向图G，下列算法计算有向图中顶点ch的出度，若无此顶点，显示出错信息。请完成邻接表结构的定义以及算法的实现。 typedef struct EdgeNode{ //边结点

int adjvex; //存放与头结点顶点有关的另一个顶点的下标 ⑷ *next; //指向链表下一个结点 } EdgeNode;

typedef struct VNode{ //顶点 char data; //顶点名称

⑸ *firstarc; //指向边该顶点第一条边 } VNode;

typedef struct{

⑹ vertices[10]; //顶点数组

int vexnum, arcnum; //顶点数和弧数

} ALGraph;

int count(ALGraph G,char ch) { //计算有向图G顶点ch的度

int i , sum=0; EdgeNode *p;

for( i=0; i=G.vexnum ) { cout<<”图中无此顶点！”<

p= ⑻ ; while(p!=NULL){ sum++; ⑼ ; }

return sum; } 得分 七． 算法设计题 (本大题共 2 题，每题 10 分，共 20 分)

1．有一个长度为n的顺序表存储于一维数组a[N]中，其元素均为整形，设计一个算法，将数组a中所有小于表头（a[0]）元素的放在a的前半部分，大于表头元素的放在后半部分，要求时间复杂度为O(n)，空间复杂度为O(1)。函数原型如下：void func(int *a，int n)

2．写一算法求二叉树BT的深度。函数原型如下：int DepthBTree( BTreeNode *BT)

第 6 页 共 6 页

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