文档介绍：姓名学号学院专业座位号
( 密封线内不答题)
……………………………………………………密………………………………………………封………………………………………线……………………………………线………………………………………
_____________ ________
…

《数据结构》试卷
选择题(从下列答案选项中选出一个正确答案,每小题2分,共22分)
在数据结构中,与所使用的计算机无关的是数据的( )结构。
逻辑
存储
逻辑和存储
物理
若线性表最常用的操作是存取第i个元素及其前驱的值,则采用( )存储方式节省时间。
单链表
双链表
顺序表
单循环链表
已知模式串t=“abcaabbcabcaabdab”,该模式串的next数组值为( )。
-1,0,0,0,1,1,2,3,0,1,2,3,4,5,6,0,1
-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1
-1,1,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1
-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,7,1,
设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一个元素,其存储地址为1,每个元素占1个地址空间,则a85的地址为( )。
13
33
18
40
一棵含有101个结点的完全二叉树存储在数组bt[102]中,其中bt[0]不用,若bt[k]是叶子结点,则k的最小值是( )。
51
50
49
48
稀疏矩阵一般的压缩存储方法有两种,即( )。
二维数组和三维数组
三元组表和散列表
三元组表和十字链表
散列表和十字链表
对顺序存储的18个数据元素(A[1]~A[18])的有序表做二分查找,则查找A[3]的比较序列的下标为( )。
1,2,3
9,5,2,3
9,5,3
9,4,2,3
用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小与图中的结点的个数有关,而与图的边数无关,这种说法( )。
正确
错误
下列排序算法中,某一趟排序结束后未必能选出一个元素放在最终位置上的是( )。
堆排序
冒泡排序
直接插入排序
快速排序
在平衡二叉树中插入一个结点后造成了不平衡,设最小不平衡子树之根为A,并已知A的左孩子的平衡因子为-1,右孩子的平衡因子为0,则应作( )型调整使其平衡。
LL
LR
RL
RR
在解决计算机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机依此从该缓冲区中取出数据打印,该缓冲区应是一个( )结构。
堆栈
队列
顺序表
链表
填空题(每空2分,共18分)
以下程序段的时间复杂度是________________________,其中n为正整数。
int i=1;
while(i<=n)
i=i*2;
对顺序存储结构的线性表,设表长为n;在等概率假设条件下,插入一个数据元素需平均移动表中元素______________个;在最坏情况下需移动表中元素______________个。
设树T的度为4,其中度为1、2、3、4的结点的个数分别为4、3、2、1,则树T的叶子结点的个数是。
判定一个环形