|
|
西南大学网络与继续教育学院课程考试试题卷
类别： 网教 专业： 软件工程 2016 年 6 月
课程名称【编号】： 数据结构 【0012】 A卷
大作业 满分：100 分
________________________________________
一、大作业题目
（一）选择题
1. 在一个单链表中，如果删除P结点所指向的后续结点，以下语句正确的是（ C ）
A. P=P->next B. p=p->next->next
C. p-next=p->next->next D. p=p-next, p-next=p->next->next
2. 栈和队列的共同特点是( C )。
A.只允许在端点处插入和删除元素 B.都是先进后出
C.都是先进先出 D.没有共同点
3. 以下数据结构中哪一个是非线性结构？( )
A. 队列 B. 栈 C. 线性表 D. 二叉树
4. 在软件开发中，下面任务不属于设计阶段的是__D____。
A.数据结构设计 B.给出系统模块结构
C.定义模块算法 D.定义需求并建立系统模型
5. 在一棵二叉树上第5层的结点数最多是__B___。
A．8 B.16 C.32 D.15
6. 下列程序段的时间复杂度为（ ）。
i=0，s=0； while (s<n) {s=s+i；i++；}
(A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)
7.设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（ ）存储方式最节省运算时间。
(A) 单向链表 (B) 单向循环链表
(C) 双向链表 (D) 双向循环链表
8.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ ）。
(A) O(1) (B) O(log2n) (C) (D) O(n2)
9. 设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。
(A) 2k-1 (B) 2k (C) 2k-1 (D) 2k-1
10.下列四种排序中（ A ）的空间复杂度最大。
(A) 快速排序 (B) 冒泡排序 (C) 希尔排序 (D) 堆
（二）填空题
1. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为____ O(n)
____。
2. 快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。
3.设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。
4.根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为_____ 2k-1_______。
5. 散列表中解决冲突的两种方法是_____________和_____________。
6. 在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。
7. 设一棵二叉树的前序序列为ABC，则有______________种不同的二叉树可以得到这种序列。
8. 设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为__________。
9. 设某棵完全二叉树中有100个结点，则该二叉树中有______________个叶子结点。
10. 数据结构从逻辑上划分为三种基本类型：___________、__________和___________。
（三）应用题
1. 设无向图G（如图所示），给出该图的最小生成树上边的集合，并计算最小生成树各边上的权值之和。
2. 请画出下图的邻接矩阵和邻接表。
二、大作业要求
大作业共需要完成三道大题：
第（一）题必做，满分30分；
第（二）题必做，满分30分；
第（三）题必做，满分40分。
|
|
