天津师范大学2020-2021学年第1学期《数据结构》期末考试试卷（B卷）含标准答案.docxVIP

天津师范大学2020-2021学年第1学期《数据结构》期末考试试卷（B卷）含标准答案

一、单项选择题（共20题，每题2分，共40分）

D

C

B

A

B

C

A

D

B

A

B

C

A

D

B

C

D

A

B

C

二、多项选择题（共10题，每题2分，共20分）

BC

ACD

BCD

AD

ABC

ABC

BCD

ABC

ACD

ABD

三、填空题（共10题，每题2分，共20分）

List

Queue

Hard

Linked

Binary

AVL

Union

Bubble

Dijkstra

Hash

四、简答题（共5题，每题4分，共20分）

线性表是由一组具有直接前驱和直接后继关系的数据元素组成的数据结构。线性表可以分为顺序表和链表两种存储结构。顺序表采用连续的存储空间存储数据元素，而链表则采用离散的存储空间。在顺序表中，数据元素之间的关系通过元素在存储空间中的相对位置来表示；而在链表中，数据元素之间的关系通过指针来表示。因此，顺序表的插入和删除操作需要移动其他元素，而链表的插入和删除操作仅需要修改指针，效率相对较高。但是，顺序表可以通过下标访问元素，而链表需要遍历，访问元素的效率较低。

栈是一种只能在表尾进行插入和删除操作的线性表，即遵循后进先出（LIFO）的原则。栈可以使用顺序存储结构或链式存储结构来实现。在顺序存储结构中，栈的数据元素依次存储在一片连续的存储空间中，通过一个栈顶指针来指示栈顶的位置。向栈中插入元素时，栈顶指针增加；删除元素时，栈顶指针减少。在链式存储结构中，栈的数据元素存储在链表的结点中，通过指向链表头部的指针来表示栈顶。向栈中插入元素时，新的结点插入链表头部；删除元素时，从链表头部删除结点。栈的应用包括函数调用、表达式求值、递归算法等。

树是一种非线性的数据结构，由n（n=0）个结点的有限集合组成。树的特点是每个结点至多有一个父结点，且每个结点可以有多个子结点。树的结构可以用链表或数组进行存储。二叉树是特殊的树结构，其中每个结点最多有两个子结点，分别称为左子结点和右子结点。二叉树的存储可以使用链表或数组，链表存储结构包括指针域和数据域，数组存储结构则根据结点的位置和序号进行存储。二叉树的应用包括排序、搜索、霍夫曼编码等。

图是由结点和边组成的集合，结点表示实体，边表示实体之间的关系。图可以分为有向图和无向图。有向图中，边具有方向，从一个结点指向另一个结点；无向图中，边没有方向，从一个结点可以到达另一个结点。图的存储可以采用邻接矩阵或邻接表的方式。邻接矩阵使用二维数组来表示结点之间的关系，数组元素的值表示相连的边的权重；邻接表使用链表或向量来表示结点之间的关系，链表中存储相邻的结点。

查找是一种常用的操作，用于在数据集合中寻找特定的元素。常见的查找算法包括顺序查找、折半查找和哈希查找。顺序查找的步骤是从头到尾依次遍历数据集合，直到找到目标元素或遍历完所有元素；折半查找的前提是数据集合已经排好序，通过不断缩小查找范围来快速定位目标元素；哈希查找利用哈希函数将数据元素映射到一个唯一的位置，通过计算该位置来查找目标元素。这些查找算法的时间复杂度各不相同，需要根据具体的应用场景选择合适的算法。

五、编程题（共5题，每题8分，共40分）

#includestdio.h

voidreverseArray(intarr[],intlen){

inttemp;

for(inti=0;ilen/2;i++){

temp=arr[i];

arr[i]=arr[len-1-i];

arr[len-1-i]=temp;

}

}

intmain(){

intarr[]={1,2,3,4,5};

intlen=sizeof(arr)/sizeof(arr[0]);

reverseArray(arr,len);

for(inti=0;ilen;i++){

printf(%d,arr[i]);

}

return0;

}

#includestdio.h

typedefstructNode{

intdata;

structNode*next;

}Node;

Node*createLinkedList(intarr[],intlen){

Node*head=NULL;

Node*tail=NULL;

for(inti=0;ilen;i++){

Node*newNode