长安大学成教期末考试题及答案.docVIP

长安大学成教期末考试题及答案

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

1.以下哪种数据结构是线性结构（）

A.树B.图C.栈D.集合

2.若某算法的时间复杂度用T(n)表示，其中n是问题规模，则T(n)=O(2^n)表示该算法（）

A.是多项式时间算法B.是指数时间算法

C.时间复杂度与n无关D.是常数时间算法

3.下列排序算法中，平均时间复杂度最小的是（）

A.冒泡排序B.选择排序C.插入排序D.快速排序

4.链表不具有的特点是（）

A.可随机访问任一元素B.插入删除不需要移动元素

C.不必事先估计存储空间D.所需空间与线性表长度成正比

5.栈和队列的共同点是（）

A.都是先进先出B.都是先进后出

C.只允许在端点处插入和删除元素D.没有共同点

6.一棵完全二叉树共有360个结点，则在该二叉树中度为1的结点个数为（）

A.0B.1C.180D.181

7.具有3个结点的二叉树有（）种不同形态。

A.3B.4C.5D.6

8.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（）

A.log?nB.n/2C.nD.n+1

9.哈希表的平均查找长度与（）有关。

A.哈希函数B.装填因子C.处理冲突的方法D.以上都是

10.下列关于图的说法正确的是（）

A.有向图一定有环B.无向图一定连通

C.图的邻接矩阵表示法适用于稠密图D.图的邻接表表示法适用于稀疏图

答案

1.C2.B3.D4.A5.C6.B7.C8.C9.D10.D

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

1.以下属于数据结构中逻辑结构的有（）

A.线性结构B.树形结构C.图形结构D.顺序结构

2.以下哪些算法属于贪心算法的应用（）

A.迪杰斯特拉（Dijkstra）算法B.普里姆（Prim）算法

C.克鲁斯卡尔（Kruskal）算法D.哈夫曼编码

3.以下关于栈的描述正确的有（）

A.栈是一种先进后出的数据结构B.栈可以用来实现表达式求值

C.栈在递归调用中起重要作用D.栈的插入和删除操作只能在栈顶进行

4.以下属于二叉树遍历方式的有（）

A.前序遍历B.中序遍历C.后序遍历D.层次遍历

5.以下排序算法中，稳定的排序算法有（）

A.冒泡排序B.归并排序C.基数排序D.选择排序

6.关于图的存储结构，下列说法正确的是（）

A.邻接矩阵适合存储稠密图B.邻接表适合存储稀疏图

C.十字链表是有向图的一种存储结构D.邻接多重表是无向图的一种存储结构

7.以下哪些数据结构可以用来实现优先队列（）

A.堆B.栈C.队列D.二叉排序树

8.下列关于算法的特性描述正确的有（）

A.有穷性B.确定性C.可行性D.输入输出

9.以下属于线性表的存储结构的有（）

A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构

10.以下关于哈希表的说法正确的有（）

A.哈希表的查找效率取决于哈希函数的设计

B.处理哈希冲突的方法有开放定址法和链地址法等

C.哈希表中装填因子越大，查找效率越高

D.哈希表可以用于快速查找和数据存储

答案

1.ABC2.ABCD3.ABCD4.ABCD5.ABC6.ABCD7.A8.ABCD9.AB10.ABD

三、判断题（每题2分，共10题，20分）

1.数据的逻辑结构与存储结构是一一对应的。（）

2.算法的时间复杂度是指执行算法所需要的计算工作量。（）

3.栈和队列都是特殊的线性表。（）

4.完全二叉树的叶子结点只可能在最后两层。（）

5.排序算法中的稳定性是指排序前后相同元素的相对位置不变。（）

6.图的广度优先有哪些信誉好的足球投注网站类似于树的层次遍历。（）

7.顺序存储结构的优点是存储密度大，且插入、删除操作效率高。（）

8.哈希表中，装填因子越大，发生冲突的可能性越小。（）

9.二叉排序树的中序遍历序列是一个有序序列。（）

10.任何一个递归算法都可以转换为对应的非递归算法。（）

答案

1.×2.√3.√4.√