数据结构期末试卷2009A
- 格式：doc
- 大小：53.50 KB
- 文档页数：1
第1页共2页 第2页共2页 安徽工程科技学院2009 ——2010 学年第 1 学期
( 数据结构 )课程考试试卷（ A ）卷
考试时间 120 分钟，满分 100 分
要求：闭卷[√]，开卷[ ]；答题纸上答题[√]，卷面上答题[ ] (填入√)
一、选择题（2分×10＝20分）
1、用链表表示线性表的优点是（ ）。
A．便于随机存取 B．花费的存储空间较顺序存储少
C．便于插入和删除 D．数据元素的物理顺序与逻辑顺序相同
2、带头结点的单链表head为空的判定条件是（ ）。
A．head==NULL B．head->next==NULL
C．head->next==head D．head!=NULL
3、设以abcdef的次序进栈，若在进栈操作时，允许出栈操作，则下面得不到的序列为（ ）。
A．fedcba B．bcafed C．dcefba D．cabdef
4、假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。
A．(rear - front + m)%m B．rear – front +1
C．(front - rear + m)%m; D．(rear - front)%m
5、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数有10个，假定整型数占2个字节，则用三元组表示该矩阵时，所需空间大小为（ ）字节。
A．60 B．66 C．18000 D．33
6、设高度为h的二叉树上只有度为0的度为2的结点，则此类二叉树中所包含的结点数至少为（ ）个。
A．2h B．2h-1 C．2h+1 D．h+1
7、某二叉树的先序遍历序列和后序遍历序列正好相反，则次二叉树一定是（ ）。
A．空或者只有一个结点 B．完全二叉树
C．单支树 D．高度等于结点数
8、G是一个非连通的无向图，共有28条边，则该图至少有（ ）个顶点。
A．6 B．7 C．8 D．9
9、下列排序算法中，其中（ ）是稳定的。
A．堆排序、冒泡排序 B．快速排序、堆排序
C．简单选择排序、归并排序 D．归并排序、冒泡排序
10、高度为4（第4层为叶子）的3阶B-树中，最多有（ ）个关键字。
A．15 B．26 C．27 D．16
二、填空题（1分×10＝10分）
1、数据结构这门课程研究的存储结构主要有（ ）、（ ）、索引存储、（ ）。
2、在n个元素的顺序表中，插入一个元素，平均移动（ ）个元素。 3、栈的特点是（ ）。
4、将整型数组A[1„8,1„8]按行优先次序存储在起始地址为1000的连续的内存单元中，假定整型占2个字节，则元素A[7，3]的地址是（ ）。
5、8层完全二叉树至少有（ ）个结点。
6、关键路径是AOE网络中（ ）。
7、在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要（ ）条弧。
8、求最短路径的Dijkstra算法的时间复杂度为（ ）。
三、应用题（40分）
1、由二叉树的中序序列及前序序列能唯一的建立二叉树，试问中序序列及后序序列是否也能唯一的建立二叉树，不能则说明理由，若能对中序序列DGBEAFHC和后序序列GDEBHFCA构造二叉树。（7分）
2、设输入的关键字序列为：22,41,53,33,46,30,13,01,67, Hash函数为：H（key）=key MOD 11。试用链地址法解决冲突，建立Hash表,并求查找成功时的平均查找长度。（8分）
3、设A、B、C、D、E、F六个字母出现的概率分别为10,4,8,3,2,7。试写出为这六个字母设计的HUFFMAN编码, 并画出对应的HUFFMAN树。（8分）
4、试写出用Prim算法构造下图的一棵最小支撑（或生成）树的每生成一条边的过程。
（7分）
5、已知长度为l2的表{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}
（1） 试按表中元素的次序（字母的ASCII次序，若第一位字母相同，则比较第二位，依次类推）依次插入一棵初始为空的二叉排序树，请画出插入之后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。（5分）
（2） 若对表中元素先进行排序构成有序表，求在等概率的情况下对此表进行折半查找成功的平均查找长度。（5分）
四、算法设计题（30分）
1、若一个字符串正读和反读相同则称为“回文”，请写出判断一个线性表表示的字符串是否为回文。（10分）
2、请写出求将二叉树的左右孩子交换的算法。（10分）
3、请写一个将无序的带头结点的单链表（元素为整型）变成递增有序的算法。（10分） 出卷老师 汪 军 审卷老师
适用专业班级 信息与计算科学0712、信息管理与信息系统0712 姓名 班级 学号
1
2
5
6
4
3
18
4
12
8
10
20
25
15
5
23
7
6
7
