在期末复习资料中，试题是其中非常重要不可缺少的资料之一，下面是个大家整理的四川广播电视大学《数据结构》试题及答案,供大家复习参考。

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

1. 栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素

B.都是先进后出

C.都是先进先出

D. 没有共同点

2. 用链接方式存储的队列， 在进行插入运算时( ) .

A. 仅修改头指针 B. 头、 尾指针都要修改

C. 仅修改尾指针 D. 头、 尾指针可能都要修改

3. 以下数据结构中哪一个是非线性结构？ ( )

A. 队列 B. 栈 C. 线性表 D. 二叉树

4. 设有一个二维数组 A[m][n]， 假设 A[0][0]存放位置在 644 (10) ， A[2][2]存放位置在

676 (10) ， 每个元素占一个空间， 问 A[3][3] (10) 存放在什么位置？ 脚注 (10) 表示用 10 进制

表示。

A． 688 B． 678 C． 692 D． 696

5. 树最适合用来表示( )。

A.有序数据元素 B.无序数据元素

C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据

6. 二叉树的第 k 层的结点数最多为( ) .

A． 2

k -1 B. 2K+1 C. 2K-1 D. 2 k-1

7. 若有 18 个元素的有序表存放在一维数组 A[19]中， 第一个元素放 A[1]中， 现进行二

分查找， 则查找 A［3］ 的比较序列的下标依次为( )

A. 1， 2， 3       B. 9， 5， 2， 3

C. 9， 5， 3       D. 9， 4， 2， 3

8. 对 n 个记录的文件进行快速排序， 所需要的辅助存储空间大致为

A. O（1） B. O（n） C. O（1og 2 n） D. O（n2）

9. 对于线性表（7， 34， 55， 25， 64， 46， 20， 10） 进行散列存储时， 若选用 H（K）

=K %9 作为散列函数， 则散列地址为 1 的元素有（ ） 个，

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

10. 设有 6 个结点的无向图， 该图至少应有( )条边才能确保是一个连通图。

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

二、 填空题（每空 1 分， 共 26 分）

1.  通常从四个方面评价算法的质量： _________、 _________、 _________和_________。

2.  一个算法的时间复杂度为(n 3 +n 2 log 2 n+14n)/n 2 ， 其数量级表示为________。

3.  假定一棵树的广义表表示为 A（C， D（E， F， G）， H（I， J））， 则树中所含的结点数

为__________个， 树的深度为___________， 树的度为_________。

4.  后缀算式 9 2 3 +- 10 2 / -的值为__________。 中缀算式（3+4X） -2Y/3 对应的后缀算式

为_______________________________。

5.  若用链表存储一棵二叉树时， 每个结点除数据域外， 还有指向左孩子和右孩子的两个指

针。 在这种存储结构中， n 个结点的二叉树共有________个指针域， 其中有________个

指针域是存放了 地址， 有________________个指针是空指针。

6.  对于一个具有 n 个顶点和 e 条边的有向图和无向图， 在其对应的邻接表中， 所含边结点

分别有_______个和________个。

7.  AOV 网是一种___________________的图。

8.  在一个具有 n 个顶点的无向完全图中， 包含有________条边， 在一个具有 n 个顶点的有

向完全图中， 包含有________条边。

9.  假定一个线性表为(12,23,74,55,63,40)， 若按 Key % 4 条件进行划分， 使得同一余数的元

素 成 为 一 个 子 表 ， 则 得 到 的 四 个 子 表 分 别 为 ____________________________、

___________________、 _______________________和__________________________。

-

-

10. 向一棵 B_树插入元素的过程中， 若最终引起树根结点的分裂， 则新树比原树的高度

___________。

11. 在堆排序的过程中， 对任一分支结点进行筛运算的时间复杂度为________， 整个堆排序

过程的时间复杂度为________。

12. 在快速排序、 堆排序、 归并排序中， _________排序是稳定的。

三、 计算题（每题 6 分， 共 24 分）

1.  在如下数组 A 中链接存储了 一个线性表， 表头指针为 A [0].next， 试写出该线性表。

A 0 1 2 3 4 5 6 7

data   60  50  78 90  34   40

next 3  5  7  2 0 4   1

2.  请画出下图的邻接矩阵和邻接表。

3.  已知一个图的顶点集 V 和边集 E 分别为： V={1, 2, 3, 4, 5, 6, 7};

E={(1, 2) 3, (1, 3) 5, (1, 4) 8, (2, 5) 10, (2, 3) 6, (3, 4) 15,

(3, 5)12, (3, 6) 9, (4, 6)4, (4, 7) 20, (5, 6) 18, (6, 7) 25};

用克鲁斯卡尔算法得到最小生成树， 试写出在最小生成树中依次得到的各条边。

4.  画出向小根堆中加入数据 4, 2, 5, 8, 3 时， 每加入一个数据后堆的变化。

四、 阅读算法（每题 7 分， 共 14 分）

1. LinkList mynote(LinkList L)

{//L 是不带头结点的单链表的头指针

if(L&&L->next){

q=L； L=L－>next； p=L；

S1： while(p－>next) p=p－>next；

S2： p－>next=q； q－>next=NULL；

}

return L；

}

请回答下列问题：

（1） 说明语句 S1 的功能；

（2） 说明语句组 S2 的功能；

（3） 设链表表示的线性表为（a 1 ,a 2 , …,a n ） ,写出算法执行后的返回值所表示的线性

表。

2. void ABC(BTNode * BT)

{if BT {

ABC (BT->left);

ABC (BT->right);

cout<<BT->data<<' ';}}

该算法的功能是：五、 算法填空（共 8 分）

二叉搜索树的查找——递归算法:

bool Find(BTreeNode* BST, ElemType& item)

{if (BST==NULL)return false; //查找失败else {if (item==BST->data) {item=BST->data; //查找成功

return ___________; }else if(item<BST->data)return Find(______________, item) ;else return Find(_______________, item) ;}//if}

六、 编写算法（共 8 分）

统计出单链表 HL 中结点的值等于给定值 X 的结点数。

int CountX(LNode* HL, ElemType x)

以上就是四川广播电视大学《数据结构》试题，希望能够帮助大家更好的复习。