试卷详情
-
数据结构自考题-9
-
[填空题]在线性表的顺序存储中,元素之间的逻辑关系是通过______决定的;在线性表的链接存储中,元素之间的逻辑关系是通过______决定的。
-
[单项选择]采用分治法进行排序的方法是( )
A. 快速排序
B. 插入排序
C. 堆排序
D. 希尔排序
-
[填空题]散列函数的作用是:______。
-
[填空题]对于数组,通常具有的基本操作有______种,它们分别是______。
-
[填空题]如果我们定义一个长度为N的串空间,则它最多能放______个字符。
-
[填空题]已知广义表A=((a,b,c),(d,e,f)),则运算head(head(tail(tail(A))))=______。
-
[单项选择]为便于判别有向图中是否存在回路,可借助于 ( )
A. 广度优先搜索算
B. 最小生成树算法
C. 最短路径算
D. 拓扑排序算法
-
[简答题](1)画出对表长为13的有序顺序表进行二分查找的判定树;
(2)已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99),写出在该序列中二分查找37时所需进行的比较次数。
-
[单项选择]数据结构是 ( )
A. 一种数据类型
B. 数据的存储结构
C. 一组性质相同的数据元素的集合
D. 相互之间存在一种或多种特定关系的数据元素的集合
-
[单项选择]一个具有N个顶点的有向图最多有( )条边。
A. N(N-1)/2
B. N(N-1)
C. N(N+1)
D. N(N+1)/2
-
[单项选择]若有序表的关键字序列为(b,c,d,e,f,g,q,r,s,t),则在二分查找关键字b的过程中,先后进行比较的关键字依次为 ( )
A. f,c,b
B. f,d,b
C. g,c,b
D. g,d,b
-
[填空题]若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为3的希尔排序,则得到的结果为______。
-
[填空题]在按照顺序存储方式存储的数组中,元素aij的存储地址应该是数组的______加上排在aij前面的元素所占用的单元数。
-
[填空题]对于一个二维数组A[m][n],若按行序为主序存储,则任一元素A[i][j]相对于A[0][0]的地址为______。
-
[填空题]若序列中关键字相同的记录在排序前后的相对次序不变,则称该排序算法是______的。
-
[单项选择]两个字符串相等的条件是 ( )
A. 串的长度相等
B. 含有相同的字符集
C. 都是非空串
D. 串的长度相等且对应的字符相同
-
[单项选择]在头指针为head的非空单循环链表中,指针p指向尾结点,下列关系成立的是 ( )
A. p—>next==head
B. p—>next—>Next==head
C. p—>next==NULL
D. p==head
-
[多项选择]对一个有t个非零值元素的m×n矩阵,用B[0..t,1..3]的数组来表示,其中第0行的三个元素分别是m,n,t,从第一行开始到最后一行,每行表示一个非零元素,第一列为矩阵元素行号,第二列为其列号,第三列为其元素量,对这样的表示法,试编写一个算法确定任意一个元素A[i][j]的位置,并考虑若修改其元素值须用多少时间(设B中第1列原行号是递增的)
-
[单项选择]在桶排序中,其平均时间复杂度是( )
A. O(1)
B. O(n)
C. O(n2)
D. O(1gn)
-
[多项选择]对序列(48,37,63,96,22,31,50,55,11)进行升序的堆排序,写出构建的初始(大根)堆及前两趟重建堆之后的序列状态。
初始堆:
第1趟:
第2趟:
-
[单项选择]邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的( )
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历
-
[单项选择]设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图。
A. 5
B. 6
C. 7
D. 8
-
[单项选择]以下有关数据结构的叙述,正确的是 ( )
A. 线性表的线性存储结构优于链式存储结构
B. 二叉树的第i层上有2i-1个结点,深度为K的二叉树上有2k-1个结点
C. 二维数组是其数据元素为线性表的线性表
D. 栈的操作方式是先进先出
-
[单项选择]如果我们采用二分查找法查找一个长度为n的有序表,则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高h≥2)。
A. 大于
B. 小于
C. 等于
D. 无法确定
-
[简答题]利用广义表的head和tail操作,可从广义表
L=((a,b),(c,d))
中分解得到原子c,其操作表达式为
head(head(tail(L)));
分别写出从下列广义表中分解得到b的操作表达式。
(1)L1=(a,b,c,d);
(2)L2=(((a),(b),(c),(d)))。
-
[单项选择]森林T中有4棵树,第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后,其根结点的左孩子上有( )个结点。
A. n1-1
B. n1
C. n1+n2+n3
D. n2+n3+n4
-
[单项选择]设rear是指向非空带头结点的循环单链表的尾指针,则删除起始结点的操作可表示为( )
A. s=rear;
B. rear=rear—>next;
C. rear=rear—>next—>next;
D. s=rear—>next—>next;
-
[填空题]无向图的邻接矩阵是______,并且主对角线上的元素的值为______。
-
[单项选择]对长度为n的关键字序列进行堆排序的空间复杂度为 ( )
A. O(log2n)
B. O(1)
C. O(n)
D. O(n*log2n)