班 级 学 号 姓 名
密封装订线 密封装订线 密封装订线
西南交通大学2009-2010 学年第(2)学期考试试卷
课程代码 3232100 课程名称 数据结构A 考试时间 120分钟
题号
一
二
三
四
五
六
七
八
九
十
总成绩
得分
阅卷教师签字:
注意:全部答案写在答题卷上才视为有效试卷!
试题
中考模拟试题doc幼小衔接 数学试题 下载云南高中历年会考数学试题下载N4真题下载党史题库下载
卷A
一、填空题(前17空每1分,后面4空每空2分,共25分)
1. 根据数据元素之间关系的不同特性,通常有四类基本结构,即:集合、线性结构、树形结构和 (1) 结构。
2. 数据类型是一个值的集合和定义在这个值集上的一组 (2) 的总称。
3. 算法的性能主要由时间复杂度和 (3) 复杂度表示。
4. 队列的操作特点是“先进先出”,堆栈的操作特点是 (4) 。
5. m个元素的C语言数组实现循环队列,若f, r分别表示队头和队尾下标, 其中队尾下标指向队尾元素后面的一个空闲位置,则在少用一个元素空间的前提下,队满的判断条件是 (5) 。
6. 7层满二叉树中,最后一层的结点数是 (6) 。
7. n个结点e条边的无向图邻接表中,有 (7) 个头结点和 (8) 个表结点。
8. 快速排序的平均时间复杂度是 (9) ;当待排序关键字基本正序时,快速排序将蜕化为起泡排序,其时间复杂度为 (10) 。
9. 已知两个带附加头结点的单链表,每个链表的数据结点按升序连接,下面的函数不另辟存储空间,实现将两个升序单链表归并为一个升序单链表,请填空。
已知结点结构定义为 typedef struct node { int data; struct node *next; } LNode;
LNode *merge(LNode *h1, LNode *h2) // h1, h2传入两个升序链表的附加头结点的指针
{ p1=h1->next; p2=h2->next;
last=h1; delete h2; //附加头结点*h1作为归并后的链表附加头结点
while( (11) )
{ if(p1->data (12) p2->data)
{ last->next=p1; p1=p1->next; }
else
{ last->next=p2; p2=p2->next; }
last= (13) ;
}
if(p1) last->next=p1;
if(p2) last->next= (14) ;
return h1;
}
10. 若二叉树结点指针类型定义如下:
typedef struct bt_node { char data; struct bt_node *left, *right; } *BT;
下面的C++函数用先根遍历算法将所有叶子结点按right指针域从左向右串接成单链表,请填空。
void f(BT root, BT &p, BT &h) //h返回最左边的叶子(单链表头)结点的指针
{ if(root)
{ if( (15) )
{ if(h==NULL) { h= (16) ; p=h; /*处理最左边的叶子*/ }
p->right=root; p= (17) ;
}
f(root->left, p, root, h);
f(root->right, p, root, h);
}
}
已知主程序中,上述函数的调用方式为:
h=NULL; f(bt, p, h); /* bt为二叉树根结点指针 */
(以下各小题每空2分)
11. 若有C语言二维数组定义double a[4][5]; 已知sizeof(double)=8, 数组按行优先存储,若数组首地址为0,则元素a[3][2]的首地址是 (18) 。
12. 拥有100个结点的完全二叉树中,叶子结点的数目是 (19) 。
13. 考虑KMP算法,子串为 "aaaaa",则下标从0开始的next数组元素值是 (20) 。
14. 对数组存储线性表(18, 32, 15, 10, 9, 30)用快速排序方法进行由小到大排序,若排序下标范围为0~5,选择元素18作为支点,调用一趟快速排序算法后,元素18在数组中的下标位置是 (21) 。
二、单项选择题(10小题,每小题2分,共20分)
1. 逻辑上可以将数据结构分为 (1) 。
(A) 动态结构和静态结构
(B) 线性结构和非线性结构
(C) 顺序结构和链式结构
(D) 初等结构和组合结构
2. 以下对顺序表进行的操作中,时间复杂度一定为O(1)的是 (2) 。
(A) 访问第i个元素的前驱
(B) 插入一个元素到第i个元素之前
(C) 删除第i个元素
(D) 对元素进行排序
3. 若栈的容量为3,已知入栈序列为1, 2, 3, 4, 5且栈满时不会进行入栈操作,则以下出栈序列正确的是 (3) 。
(A) 5, 4, 3, 2, 1 (B) 1, 3, 5, 2, 4 (C) 3, 5, 4, 2, 1 (D) 2, 3, 5, 4, 1
4. 若10个结点的完全二叉树采用顺序表存储,下标范围0~9, 根结点下标为0,则下标为3的结点的的左孩子的下标是 (4) 。
(A) 5 (B) 6 (C) 7 (D) 8
5. 若某二叉树的结点按其关键字中序遍历有序,则该二叉树是 (5) 。
(A) 最小生成树 (B) 完全二叉树 (C) 哈夫曼树 (D) 二叉排序树
6. 以下关于哈希表的说法中正确的是 (6) 。
(A) 哈希表中访问数据元素的平均时间复杂度为O(1)
(B) 装填因子越大,说明哈希表的存储空间利用率越高
(C) 哈希表的查找效率仅与冲突的处理方法有关
(D) 通过精心设计哈希(散列)函数,冲突总可以避免
7. 8个元素组成的有序顺序表(a0, a1, a2, a3, a4, a5, a6, a7)采用折半查找,经过2次关键字比较后,可能找到的元素有 (7) 。
(A) a1, a5 (A) a2, a6 (A) a3, a4 (A) a0, a7
8. 以下内部排序方法中,最坏情况下时间复杂度也为O(nlog2n)的是 (8) 。
(A) 快速排序 (B) 堆排序 (C) 希尔排序 (D) 基数排序
9. n个结点的有向图,至少需要 (9) 条有向边(弧)才能构成强连通图。
(A) 2n (B) n (C) n(n-1) (D) n-1
10. 为判别有向图是否存在回路,可利用 (10) 算法。
(A) 最短路径 (B) 深度优先遍历
(C) 拓扑排序 (D) 最小生成树
三、 简答题(共35分)
1. 已知二叉树的先序和中序遍历结点访问次序如下:
先序遍历:ACDEFBGH
中序遍历:CEDFABHG
试画出该二叉树。(此题5分)
2. 请将序列28, 15, 72, 40, 30, 20, 6, 65, 9, 76初始筛选构建为一个小根堆,写出构建后的序列并画出对应的完全二叉树。(此题5分)
3. 已知输入序列同本大题第2小题,即28, 15, 72, 40, 30, 20, 6, 65, 9, 76。
(1) 画出由该输入序列构成的二叉排序树;
(2) 若每个元素按等概率查找,试计算成功查找时的平均查找长度。
(此题共6分)
4. 已知有向图的邻接表如下图所示。
(1) 写出从顶点A出发,深度优先遍历结点访问次序(用字母表示)。
(2) 写出从顶点A出发,广度优先遍历结点访问次序(用字母表示)。
(3) 画出该有向图的逆邻接表。 (此题共7分)
5. 一个赋权网络如下图所示。从顶点a开始,用Prim算法求出一棵最小生成树。此题要求在答题卷上画出原图,然后用波浪线标出最小生成树的各条边,并用<>括起来的数字标号反映最小生成树中各条边的求取次序。(此题6分)
6. 已知用4进制表示的三位整数序列201, 102, 133, 012, 301, 001, 101, 212。用基数排序方法实现由小到大排序,则必须进行3趟分配和收集操作, 请画(写)出每趟分配和收集的结果。(6分)
四、算法设计题(2小题,每小题10分,共20分)
1. 已知带附加头结点单链表结点结构如本试卷第一大题第8小题。
写一个算法,形参传入附加头结点指针,然后删除所有data域值小于0的所有结点。
2. 编写算法,利用队列实现二叉树按层次遍历。
队列可直接使用,无需给出其实现细节(即假设队列已有正确定义,所用操作请加适当注释即可);