Question

求解数据结构导论题目

.在表长为n的顺序表上做插入运算，平均要移动的结点数为（ ）
A.n/4 B.n/3
C.n/2 D.n
2.在线性表的下列存储结构中进行插入、删除运算，花费时间最多的是（ ）
A.单链表 B.双链表
C.顺序表 D.单循环链表

3.用n个值构造一棵二叉排序树，它的最大高度为（ ）
A.n/2 B. n
C. D.log2n

4.带表头结点链队列的队头和队尾指针分别为front和rear，则判断队空的条件为
（ ）
A.front==rear B.front!=NULL
C.rear!=NULL D.front==NULL

5.下列程序段的时间复杂度为________。
　　　　i=0；s=0；
　　　　while（i<n）
　　　　　　{ i++；
　　　　　　　s=s+i；
　　　　　　}

6.向一个栈顶指针为top的链栈中插入一个新结点*p时，应执行________和top=p操作。
7.有向图G的邻接矩阵为A，如果图中存在弧<Vi，Vj>，则A［i］［j］的值为________。
8.顺序查找算法的平均查找长度为________。
9.二路归并排序的平均时间复杂度为________。

10.下列程序段的时间复杂度为____________。
　　　for(i=1；i<=n；i++)
　　　　for(j=1；j<=n；j++)
　　　　　for(k=1；k<=n；k++)
　　　　　　s=i+j+k；
11.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。
12.循环队列被定义为结构类型，含有三个域：data、front和rear，则循环队列sq为空的条件是____________。
13.含有n个顶点和n-1条边的连通图G采用____________存储结构较省空间。
14.在图中，第一个顶点和最后一个顶点相同的路径称为____________。
15.动态查找中两个元素X，Y存入同一个散列表时，X、Y键值相同，则这种情况称为____________。

1堆排序需____________个记录大小的辅助存储空间。
2.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( )
A.O(1) B.O(1og2n)
C.O(n) D.O(n2)
3.下述几种排序方法中，要求内存量最大的是( )
A.插入排序 B.快速排序
C.归并排序 D.选择排序
4.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( )
A.n-1 B.n
C.n+1 D.n(n-1)／2
5.在表长为n的顺序表上做删除运算，其平均时间复杂度为( )
A.O(1) B.O(n)
C.O(nlog2n) D.O(n2)
6.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( )
A.n-2 B.n-1
C.n D.n+1
7.有关插入排序的叙述，错误的是( )
A.插入排序在最坏情况下需要O(n2)时间
B.插入排序在最佳情况可在O(n)时间内完成
C.插入排序平均需要O(nlog2n)时间
D.插入排序的空间复杂度为O(1)
8.有关树的叙述正确的是( )
A.每一个内部结点至少有一个兄弟
B.每一个叶结点均有父结点
C.有的树没有子树
D.每个树至少有一个根结点与一个叶结点。
9.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为( )
A.rear=rear+1 B.rear=(rear+1)％(m-1)
C.rear=(rear+1)％m D.rear=(rear+1)％(m+1)
10.关于串的的叙述，不正确的是( )
A.串是字符的有限序列
B.空串是由空格构成的串
C.替换是串的一种重要运算
D.串既可以采用顺序存储，也可以采用链式存储
11.对称矩阵A[N][N]，A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)／2]中，则任一上三角元素A[i][j]存于T[k]中，下标k为( )
A.i(i-1)／2+j B.j(j-1)／2+i
C.i(j-i)／2+1 D.j(i-1)／2+l

Answer 1

1-5 CBDA o(n)