安徽大学期末考试数据结构试卷.pdf

安徽大学

《数据结构》考试试卷（A卷）

一、填空题

1、在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结

点；最后一个结点后续结点，其余每个结点有且只有个后续结点。

2、下面程序段的时间复杂度是。

for(i=0;in;i++)

for(j=0;jm;j++)

A[i][j]=0;

3、在具有n个单元的循环队列中，队满时共有个元素。

4、假定一棵二叉树的结点数为18，则它的最小深度为，最大深度为。

5、在一个单链表中p所指结点之后插入一个s所指结点时，应执行下面的操作：

s—＞next=____;

p—＞next=___;

6、从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查

找长度分别为和。

7、.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的

结点有___________________个。

8、在堆排序和快速排序中，若原始记录接近正序或反序，则选用____。

9、若采用邻接表的存储结构，则图的广度优先有哪些信誉好的足球投注网站类似于二叉树的________遍历。

二、单向选择题（每小题1.5分，共15分）

1、n个顶点的强连通图中至少含有()。

A、n—l条有向边B、n条有向边

C、n(n—1)／2条有向边D、n(n一1)条有向边

2、在一个不带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，

执行()。

A、HL＝p;p一next＝HL;B、p一next＝HL；HL＝p;

C、p一next＝HL;p＝HL;D、p一next＝HL一next;HL一next＝p;

3、采用线性链表表示一个向量时，要求占用的存储空间地址（）。

A:必须是连续的B部分地址必须是连续的

C:一定是不连续的D:可连续可不连续

4、如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。

A:起泡排序B:堆排序C:锦标赛排序D:快速排序

5、在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为front和rear，

则当前队列中的元素个数是（）。

A:(front-rear+1)%mB:(rear-front+1)%m

C:(front-rear+m)%mD:(rear-front+m)%m

6、数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的

内存单元中，则元素A[5，5]的地址是()。

第1页共7页

A:1175B:1180C:1205D:1210

7、已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是()

A:head(tail(LS))B:tail(head(LS