杭州电子科技大学数据结构数据结构期末考试练习题.docxVIP

杭州电子科技大学数据结构数据结构期末考试练习题

一、选择题

1.数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的关系和运算等的学科。

A.数据元素

B.计算方法

C.逻辑存储

D.数据映像

答案：A

解析：数据结构研究数据元素以及它们之间的关系和运算等。计算方法侧重于算法的设计与分析；逻辑存储是数据存储的一种抽象概念；数据映像是关于数据在不同环境下映射的内容。所以选A。

2.以下属于线性结构的是（）。

A.树

B.图

C.栈

D.二叉树

答案：C

解析：线性结构的特点是数据元素之间存在一对一的线性关系。栈是一种特殊的线性表，遵循后进先出原则，属于线性结构。树和二叉树是树形结构，数据元素之间存在一对多的层次关系；图是一种复杂的非线性结构，数据元素之间存在多对多的关系。所以选C。

3.若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（）。

A.ni

B.ni+1

C.i

D.不确定

答案：B

解析：栈遵循后进先出原则，输入序列是1，2，3，…，n，输出序列第一个元素是n，说明是将所有元素依次入栈后再依次出栈。那么输出序列为n，n1，n2，…，1。所以第i个输出元素是ni+1。选B。

4.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入结点s，则执行（）。

A.snext=pnext;pnext=s;

B.pnext=snext;snext=p;

C.qnext=s;snext=p;

D.pnext=s;snext=q;

答案：C

解析：要在q和p之间插入结点s，需要先让q的后继指向s，即qnext=s，然后让s的后继指向p，即snext=p。A选项是在p之后插入s；B选项逻辑错误；D选项插入顺序错误。所以选C。

5.具有n个结点的完全二叉树的深度为（）。

A.?log?n?+1

B.log?n+1

C.?log?n?

D.log?n

答案：A

解析：对于完全二叉树，设其深度为h，根据完全二叉树的性质，深度为h的满二叉树的结点数为2?1。若2??11n≤2?1，则h=?log?n?+1。所以选A。

二、填空题

1.数据的逻辑结构可以分为线性结构和__________结构。

答案：非线性

解析：数据的逻辑结构主要分为线性结构（如线性表、栈、队列等）和非线性结构（如树、图等）。

2.栈和队列的区别在于__________。

答案：插入和删除操作的限定不同

解析：栈是后进先出（LIFO）的数据结构，插入和删除操作都在栈顶进行；队列是先进先出（FIFO）的数据结构，插入操作在队尾进行，删除操作在队头进行。

3.设循环队列的容量为50（序号从0到49），现经过一系列的入队和出队操作后，有front=16，rear=5，则该循环队列中元素个数为__________。

答案：39

解析：循环队列中元素个数的计算公式为：(rearfront+容量)%容量。将front=16，rear=5，容量=50代入公式，可得(516+50)%50=39。

4.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为__________，邻接表中边结点的个数为__________。

答案：n；2e

解析：邻接表的表头向量是用来存储图的顶点信息的，其大小等于图的顶点数n。对于无向图，每条边在邻接表中会出现两次，所以邻接表中边结点的个数为2e。

5.排序算法中，稳定的排序算法有__________（至少写出一种）。

答案：冒泡排序（答案不唯一，插入排序、归并排序等也是稳定排序算法）

解析：稳定排序算法是指在排序过程中，相等元素的相对顺序不会改变。冒泡排序在比较相邻元素时，如果顺序错误就交换，相等时不交换，所以是稳定的。

三、判断题

1.数据的物理结构是指数据在计算机中的实际存储形式。（）

答案：正确

解析：数据的物理结构也称为存储结构，它描述了数据在计算机中的实际存储方式，如顺序存储、链式存储等。

2.栈和队列都是线性表，只是在插入和删除操作时受到了一些限制。（）

答案：正确

解析：栈和队列本质上都是线性表，栈的插入和删除操作只能在栈顶进行，队列的插入在队尾，删除在队头，它们都对线性表的插入和删除操作进行了限制。

3.有向图的邻接矩阵一定是对称的。（）

答案：错误

解析：有向图的邻接矩阵不一定对称，只有当有向图是有向完全图且每条边都有相反方向的边时，邻接矩阵才对称。一般情况下，有向图邻接矩阵中a[i][j]表示从顶点i到顶点