1.下面程序段的时间复杂度为( C )。
for(int i=0;inext=q->next; B、 p=q->next;q->next=p;
C、 p=q->next;p->next=q; D、 q->next=q->next->next;
6.设一个广义表的A=(a,()),其表尾为( B )。
A、a B、(( )) C、( ) D、(a)
7.在一个链队中,假设f和r分别为队首和队尾指针,删除一个结点的运算是( C )。
A、r = f —>next B、r = r —>next C、f = f —>next D、f = r —>next
8.若用数组S[1..n]作为两个栈S1和S2的共同存储结构,对任何一个栈,只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是( C )。
A、S1的栈底位置为0,S2的栈底位置为n+1 B、S1的栈底位置为0,S2的栈底位置为n/2
C、S1的栈底位置为1,S2的栈底位置为n D、S1的栈底位置为1,S2的栈底位置为n/2
9.在有n个结点的二叉链表中,值为空的链域的个数为( C )。
A、n-1 B、2n-1 C、n+1 D、2n+1
10.设有13个值,用它们组成一棵哈夫曼树,则该哈无曼树的共有( D )个结点.
A、13 B、12 C、26 D、25
11.对于具有e条边的无向图,它的邻接表中有( D )边结点
A、 e-1 B、 e C、 2(e-1) D、 2e
12.用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为( B )。
A、O(n) B、O(log2n) C、O(n2) D、O(1)
13.在一个长度为n的线性表中顺序查找值为x的元素时,查找成功的平均查找长度(即x同元素的平均比较次数,假定查找每个元素的概率都相等)为 ( C ) 。
A、 n B、 n/2 C、 (n+1)/2 D、 (n-1)/2
14.如果想在4092个数据中只需要选择其中的最小的10个,采用( B )方法最好。
A、起泡法 B、堆排序 C、直接选择法 D、快速排序
15.若串S=“software”,其真子串的个数是( C )。
A.8 B.37 C.36 D.9
16.执行下面程序段时,执行T语句的次数为( A )。
for(int i=1;inext==first D、first!=NULL
20.栈的插入与删除操作在( A )进行。
A、 栈顶 B 、栈底 C、 任意位置 D、 指定位置
21.设一个广义表的A=(a),其表尾为( C )。
A、a B、(( )) C、( ) D、(a)
22.二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范
围从0到4,列下标j的范围从0到5,M按行存储时元素M[3][5]的起始地址与M按列存储时元素( B )的起始地址相同。
A、M[2][4] B、M[3][4] C、M[3][5] D、M[4][4]
23.树中所有结点的度之和等于所有结点数加( C )。
A、 0 B 、 1 C、 -1 D、 2
24.设有13个值,用它们组成一棵哈夫曼树,则该哈无曼树的共有( D )个结点.
A、13 B、12 C、26 D、25
25.对于一个具有N个顶点的图,如果我们采用邻接矩阵法表示,则此矩阵的维数应该是( B )。 A、(N-1)×(N-1) B、N×N C、(N+1)×(N+1) D、不确定
26.对于一个有向图,其邻接矩阵表示比邻接表表示更易于( A )
A、求一个顶点的入度 B、求一个顶点的出边邻接点
C、进行图的浓度优先遍历 D、进行图的广度优先遍历
27.向一棵AVL树插入元素,可能引起最小不平衡子树的调整过程,此调整分为( C )种。
A、2 B、3 C、4 D、5
28.折半查找要求查找表中各元素的关键字值必须是( A )排列。
A、 递增或递减 B、递增 C、递减 D、无序
29. 以下序列不是堆的是( D )
A、{100,85,98,77,80,60,82,40,20,10,66}
B、{100,98,85,82,80,77,66,60,40,20,10}
C、{10,20,40,60,66,77,80,82,85,98,100}
D、{100,85,40,77,80,60,66,98,82,10,20}
30.若串S=“software”,其子串的个数是( C )。
A.8 B.37 C.36 D.9
31.数据的最小单位是( A )。
A、 数据项 B、 数据类型 C、 数据元素 D、 数据变量
32. 一个栈的输入序列为1,2,3,4,下面哪一个序列不可能是这个栈的输出序列( C )。
A、 1,3,2,4 B、2,3,4,1 C、 4,3,1,2 D、3,4,2,1
33. 对顺序存储的线性表,设其长度为n,在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的( A )个元素。
A、 n/2 B、(n+1)/2 C、(n -1)/2 D、 n
34. 某算法的时间代价为T(n)=100n+10nLog2n+n2+10,其时间复杂度为( C)。
A、O(n) B、O(nlog2n) C、 O(n2) D 、O(1)
35.设一组初始记录关键字序列为(50,40,95,20,15,70,60,45),则以增量d=4的一趟希尔排序结束后前4条记录关键字为( B )。
A、 40,50,20,95 B、 15,40,60,20
C、 15,20,40,45 D、 45,40,15,20
36.设一组初始记录关键字序列为(25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序子表,则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为( A )。
A、 15,25,35,50,20,40,80,85,36,70
B、15,25,35,50,80,20,85,40,70,36
C、15,25,35,50,80,85,20,36,40,70
D、15,25,35,50,80,20,36,40,70,85
37.函数substr(“DATASTRUCTURE”,5,9)的返回值为( A )。
A、 “STRUCTURE” B、 “DATA”
C、 “ASTRUCTUR” D、 “DATASTRUCTURE”
38.设一个有序的单链表中有n个结点,现要求插入一个新结点后使得单链表仍然保持有序,则该操作的时间复杂度为( D )。
A、 O(log2n) B、 O(1) C、 O(n2) D、 O(n)
39.在有n个结点的二叉链表中,值为非空的链域的个数为( A )。
A、n-1 B、2n-1C、n+1D、2n+1
40.设有序表中有1000个元素,则用二分查找查找元素X最多需要比较( B )次。
A、 25 B、 10 C、 7 D、 1
41.设连通图G中的边集E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发可以得到一种深度优先遍历的顶点序列为( A )。
A、 abedfc B、 acfebd C、 aebdfc D、 aedfcb
42.设输入序列是1、2、3、……、n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素是( C )。
A、 n-i B、 n-1-i C、 n+1-i D、不能确定
43. 设一组初始记录关键字序列为(45,80,55,40,42,85),则以第一个记录关键字45为基准而得到一趟快速排序的结果是( C )。
A、 40,42,45,55,80,83 B、 42,40,45,80,85,88
C、 42,40,45,55,80,85 D、 42,40,45,85,55,80
44. 利用n个权值作为叶子结点的生成的哈夫曼树中共包含( D )个结点
A、n B、n+1 C、2*n D、2*n-1
45. 向一棵AVL树插入元素,可能引起最小不平衡子树的调整过程,此调整分为( C )种。
A、2 B、3 C、4 D、5
46.数据的基本单位是( B )。
A. 数据结构 B. 数据元素 C. 数据项 D. 文件
47. 以下算法的时间复杂度为( D )。
s=0;
for (i=0;i