文档介绍:广东工业大学考试试卷( A )
课程名称: 数据结构(C语言) 试卷满分 100 分
考试时间: 2008 年 6 月25日(第 18 周星期 3 )
题号
一
二
三
四
五
六
七
八
九
十
总分
评卷得分
评卷签名
复核得分
复核签名
一、选择题(每项选择2分,共36分)
1、下面程序段的时间复杂度为( )。
i=1;
while (i<n)
i*=2;
A、O(n) B、O(n2) C、O(log2n) D、O(nlog2n)
2、线性表的顺序存储结构是一种( ①)的存储结构,线性表的链式存储结构是一种( ②)的存储结构。
①②:A、随机存取 B、顺序存取 C、索引存取 D、散列存储
3、若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为( )。(1≤i≤n+1)
(0) (1) (n) (n2)
4、对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为( )。
A、顺序表 B、带头指针的单循环链表
C、带尾指针的单循环链表 D、单链表
学院: 专业: 学号: 姓名:
装订线
5、数组A中,每个数据元素的长度为4个字节,行下标从3到8,列下标从2到10,存放该数组至少需要的字节数是( )。
A、54 B、108 C、216 D、270
6、若一棵完全二叉树中某结点无左孩子,则该结点一定是( )。
A、度为1的结点 B、度为2的结点
C、分支结点 D、叶子结点
7、某二叉树只有度为0和度为2的结点,如果该二叉树只有19个结点,则叶子结点数为( )。
A、9 B、10 C、11 D、12
8已知二叉树的前序序列为DABCEFG,中序序列为BACDFGE则该二叉树的后序序列为( ①),层次序列为( ②)。
①、②: A、BCAGFED B、DAEBCFG
C、ABCDEFG D、BCAEFGD
9、将一棵树转换成二叉树,树的前根序列与其对应的二叉树的( ①)相同。树的后根序列与其对应的二叉树的( ②)相同。
①、②:A、前序序列 B、中序序列
C、后序序列 D、层序序列
10、具有8个顶点的无向图最多可以有( )条边。
A、8 B、28 C、56 D、72
11、下面关于图的操作的说法不正确的是( )。
A、寻找关键路径是关于带权有向图的操作。
B、拓扑排序是关于有向图的操作。
C、连通图的生成树不一定是唯一的。
D、带权连通图的最小生成树是唯一的。
12、下面的各种图中,哪个图的邻接矩阵是一定对称的( )。
A、AOE网 B、AOV网 C、无向图 D、有向图
13、对线性表用折半查找时要求线性表必须是( )。
A、顺序表 B、单链表 C、顺序存储的有序表 D、散列表
14、若一组记录的排序码序列为{60,40,10,90,80,20},利用快速排序方法,以60为基准,升序排列,得到第一趟快速排序的结果为( )。
A、10,40,20,60,90,80 B、20,40,10,60,80,90
C、40,10,20,60,90,80 D、20,10,40,60,80,90
15、下列几种排序方法中要求辅助存储空间最大的是( )。
A