北航数据结构2023期末考题

本文格式为Word版，下载可任意编辑——北航数据结构2023期末考题北京航空航天大学

2023～2023学年第2学期

《软件技术基础》

考试B试卷

班级：__________；学号：______；姓名：__________；成绩：______；

2023年6月16日

1

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

1、若五个元素的出栈序列为1、2、3、4、5，则进栈序列可能是（）A.2,4,3,1,5C.3,1,4,2,5B.2,3,1,5,4D.3,1,2,5,4

1、若从无向图的任意一个顶点出发一次深度优先探寻便可以访问该图的所有顶点，则该图一定是一个（）图。A.非连通C.强联通B.连通D.完全

3、算法分析的目的是（)。

A.研究算法的输入与输出之间的关系C.分析算法的效率，以求改进B.找出数据结构的合理性D.分析算法的可读性

4、下面那个不是数据结构的基本研究内容（）。A.数据的规律结构C.数据的存储结构B.语法D.算法

5、若变量list是带头结点的循环链表的头结点指针，则该链表最终那个链接点的指针域中存放的是（）。

A.变量list的地址C.变量list指的链结点的值

2

B.变量list的内容D.链表第一个链结点的地址6、对于一个不带权的无向图的邻接矩阵而言，（）。A.矩阵中非零元素的数目等于图中边的数目B.矩阵中非全零的行的数目等于图中顶点的数目C.第i行的非零元素的数目与第i列非零元素的数目相等D.第i行与第i列的非零元素的总数等于第i个顶点的度数

7、在循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断循环队列空的条件是（）。A.front==rear+1C.front==rearB.rear==front+1D.front==0

8、在所学过的排序方法中，排序趟数与序列原始状态有关的方法是（）。

A.选择排序法C.冒泡排序法B.谢尔排序法D.快速排序法

9、数据库DBNS能实现对数据库中数据的查询、插入、修改和删除操作，该功能称为（）。

A.数据定义功能C.数据操纵功能B.数据存储功能D.数据控制功能

3

10、程序编译通过表示（）。

A.排除程序中所有错误C.证明程序完全正确B.尽可能排除程序中的错误D.程序中不存在语法错误

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

1、若对线性表的操作主要不是插入与删除，则该线性表宜采用（存储结构；若频繁采用插入与删除操作，则该线性表宜采用（存储结构。

2、下面带#号语句的执行次数是（）。inti=1,j=0;while(i+jj)i++;elsej++;

3、中缀表达式A+(B-C/D)*E(乘)的后缀形式是（

4、已知某二叉树的前序序列为ABDEGCFHIJ,中序序列为

4

。

）））DBGEAHFIJC,请写出后序序列（）。

5、对于关键字值的分布基本连续，或者关键字值有一定规律的状况，适合使用（）来构造散列函数。

6、原始序列为（12,2,16,30,8,28,4,10,20，6,），请写出选择排序法第一趟的排序结果____________________________________。

7、假使程序运行出现错误，常用的调试手段有_________________和_________________________。