一 选择题
1．算法的计算量的大小称为计算的（ ）。
A．效率 B. 复杂性 C. 现实性 D. 难度 2．下面说法错误的是（ ）
(1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 3. 连续存储设计时，存储单元的地址（ ）。
A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 4. 下述哪一条是顺序存储结构的优点？（）
A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
5．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 6．下面的叙述不正确的是（ ）
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 7．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2)
8．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（ ） (^.相当于—>) A. p＾.llink:=q; q＾.rlink:=p; p＾.llink＾.rlink:=q; q^.llink:=p^.llink;
B. q＾.llink:=p^.llink; p＾.llink^.rlink:=q; q＾.rlink:=p; p^.llink:=q^.rlink; C. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^.rlink:=p;
D. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^.llink; p^.llink:=q; 9．下列排序算法中，其中（ ）是稳定的。
A) 堆排序，冒泡排序 B) 快速排序，堆排序 C) 直接选择排序，希尔排序 D) 归并排序，冒泡排序
10．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 (4） 15 21 25 47 84 则采用的排序是 ( )。
A) 选择 B) 冒泡 C) 快速 D) 插入
11．双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（ ）（链中结点数大于2，p不是第一个结点） A．p^.llink^.rlink:=p^.llink; p^.llink^.rlink:=p^.rlink; dispose(p); B．dispose(p); p^.llink^.rlink:=p^.llink; p^.llink^,rlink:=p^.rlink; C．p^.llink^.rlink:=p^.llink; dispose(p); p^.llink^.rlink:=p^.rlink; D．以上A，B，C都不对。
12.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ） A)CABDEFG B) BCDAEFG C) DACEFBG D) ADBCFEG
13. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ ）。 A) 5 1 2 3 4 B) 4 5 1 3 2 C) 4 3 1 2 5 D) 3 2 1 5 4
14. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。
A. i-j-1 B. i-j C. j-i+1 D. 不确定的 15. 一个递归算法必须包括（ ）。
A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分
16. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。 A) 快速排序 B) 堆排序 C) 归并排序 D) 直接插入排序 17．下面关于串的的叙述中，哪一个是不正确的？（ ）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 18．稳定的排序方法是（ ）
A)直接插入排序和快速排序 B)折半插入排序和起泡排序 C)简单选择排序和四路归并排序 D)树形选择排序和shell排序 19．已知串S=‘aaab’,其Next数组值为（ ）。
A．0123 B．1123 C．1231 D．1211 20．串的长度是指（ ）
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
21. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ ）。 A) a，c，b，d B) b, c，d，a C) c, d，b, a D) d, c，a，b
22．数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。
A. 1175 B. 1180 C. 1205 D. 1210
23．A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组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+1
24. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。 A. head(tail(LS)) B. tail(head(LS)) C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 25．下面说法不正确的是( )。
A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 26．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。
A)(38,40,46,56,79,84) B) (40,38,46,79,56,84) C)(40,38,46,56,79,84) D) (40,38,46,84,56,79)
27. 已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( ) A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE
28. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A．9 B．11 C．15 D．不确定
29. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用()遍历方法最合适。 A．前序 B．中序 C．后序 D．按层次
30. 将一个长度为n的向量的第i 个元素删除时，需要前移( )个元素。 A) i B) n-i C) n+1 D) n-i+1
31. 某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2，… ，n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按( )编号的。
A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次顺序 32. 线索二叉树是一种（ ）结构。
A． 逻辑 B． 逻辑和存储 C． 物理 D．线性
33. 非空循环链表head 的尾结点 *p 满足下列( )条件
A)head->next==p; B)head==p; C)p->next==head; D)p->next==0 34. 一个栈的输入序列是a,b,c,d,e ，则可能的出栈序列是( )。 A) ecdab B)cebda C)daecb D)abcde
35. 设栈s的类型为sqstack ，判定栈空的条件是( )。 A) s==NULL B)s->top==0 C)s.top==0 D) s.top==NULL 36. 深度为5 的二叉树至多有个( )结点。 A) 12 B) 31 C) 14 D) 15
37. 已知二叉树的后、中根序列分别是bedfca 和 badecf，则该二叉树的前根遍历序列是( )。 A)defbca B)fedbca C) abcdef D)fedcba 38. 一个有n个顶点的有向图最多有( )弧 。
A) n(n+1) B) n(n-1) C) n(n+1)/2 D) n(n-1)/2
39. 具有n个顶点的无向图至少要有( )条边才有可能是一个连通图。 A) n(n+1) B) n-1 C) n+1 D) n(n-1) 40. 图中有关路径的定义是（ ）。
A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是
41. 一个向量的第一个元素的地址是100，每个元素的长度是2 ，则第五个元素的地址是( ) A) 102 B) 110 C) 108 D) 120
42. 一个循环顺序队列 ,队头、尾指针的值分别为front,rear，则队列中元素个数为( )。（maxlen为循环顺序表的长度）
A) (rear-front+maxlen) % maxlen B) (rear-front) % maxlen C) rear-front+1 D) front-rear+1
43. 一个有n个顶点的图最少有( )条边。
A) n(n+1) B) n(n-1) C) n(n+1)/2 D) 0
44. 具有5个顶点的无向图至少要有( )条边才能确保是一个连通图。 A) 4 B) 5 C) 6 D) 7
45. 设栈s的类型为sqstack ，最多可容纳maxlen个元素，则判定栈满的条件是( )。 A) s==maxlen-1 B) s.top==maxlen-1 C) s->top==maxlen-1 D) s.top==0
46. 一个顺序队列q的类型为sqqueue,队头、尾指针分别为front,rear，最多可容纳maxlen个元素，则队空的条件是( )。
A) front==rear B) rear==0 C) q.front==q.rear D) rear==maxlen-1
47. 下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（1 ），下面步骤重复n-1次: a：（ 2 ）；b：（ 3 ）；最后：（ 4 ）。 （1）．A．VT，ET为空 B．VT为所有顶点，ET为空
C．VT为网中任意一点，ET为空 D．VT为空，ET为网中所有边 （2）．A. 选i属于VT，j不属于VT，且（i，j）上的权最小
B．选i属于VT，j不属于VT，且（i，j）上的权最大 C．选i不属于VT，j不属于VT，且（i，j）上的权最小 D．选i不属于VT，j不属于VT，且（i，j）上的权最大 （3）．A．顶点i加入VT，（i,j）加入ET B. 顶点j加入VT，（i,j）加入ET C. 顶点j加入VT，（i,j）从ET中删去 D．顶点i,j加入VT，（i,j）加入ET （4）．A．ET 中为最小生成树 B．不在ET中的边构成最小生成树
C．ET中有n-1条边时为生成树，否则无解 D．ET中无回路时，为生成树，否则无解 48. 链栈与顺序栈相比，比较明显的优点是( )
A)插入操作更加方便 B)删除操作更加方便
C)不会出现下溢的情况 D)不会出现上溢的情况 49. 下面关于二分查找的叙述正确的是 ( )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列 B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储 50. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 51. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ ） A)深度优先搜索算法 B)广度优先搜索算法 C)求最小生成树的prim算法 D)拓扑排序算法 52. 既希望较快的查找又便于线性表动态变化的查找方法是 )
A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找
53. 对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( ) A) (n-1)/2 B) n/2 C) (n+1)/2 D) n
54. 对于哈希函数H(key)=key%13,被称为同义词的关键字是( ) A)35和41 B)23和39 C)15和44 D)25和51 55. 某内排序方法的稳定性是指( )。
A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录
C．平均时间为0（n log n）的排序方法 D．以上都不对
56. 下列内部排序算法中：
A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序 （1） 其比较次数与序列初态无关的算法是（ ） （2）不稳定的排序算法是（ ）
（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k< A)限制存取位置的线性结构 B)链式存储的非线性结构 C)顺序存储的线性结构 D)限制存取位置的非线性结构 59. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。 A. (2,5,12,16)28(60,32,72) B. (5,16,2,12)28(60,32,72) C. (2,16,12,5)28(60,32,72) D. (5,16,2,12)28(32,60,72) 60. 一棵含有n个节点的k叉树，可能达到的最小深度为多少？（ ） A) n-k B) n-k+1 C) |logkn|+1 D) |logkn| 其中|k|表示下取整 61. 下列序列中( )不是堆。 A) 12 36 53 68 48 60 75 B) 12 48 53 68 36 60 75 C) 12 48 36 60 75 68 53 D) 12 36 60 53 48 68 75 62. 在下列内排序方法中，( )的平均时间复杂性是O(nlogn)。 A) 直接插入排序 B) 简单选择排序 C) 快速排序 D) 希尔排序 63. 设顺序栈s非空，则语句段( )可实现栈s的出栈操作，其中s.top为栈顶指针，s.elem为栈空间，出栈的元素存放在x中。 A) s.top:=s.top+1; B) x:=s.elem[s.top]; x:=s.elem[s.top]; s.top:=s.top+1; C) s.top:=s.top-1; D) x:=s.elem[s.top]; x:=s.elem[s.top]; s.top:=s.top-1; 64. 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ ） A．-1，4，8，9，20，7，15，7 B．-1，7，15，7，4，8，20，9 C．-1，4，7，8，20，15，7，9 D．A，B，C均不对。 65. 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ D ）。 A)二叉排序树 B)哈夫曼树 C)AVL树 D)堆 66. 下面给出的四种排序法中( )排序法是不稳定性排序法。 A) 插入 B) 冒泡 C) 二路归并 D) 快速排序 67. 算法的时间复杂度取决于（ ） A．问题的规模 B. 待处理数据的初态 C. A和B D. 计算机cpu 68. 有关静态链表的叙述：(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（ ） A．（1），（2） B．（1） C．（1），（2）,(3) D.（2） 69．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。 A. 不确定 B. n-i+1 C. i D. n-i 70．下面关于串的的叙述中，哪一个是不正确的？（ ） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 71. 关于二叉树的叙述：①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。正确的是（ ） A．①②③ B．②③④ C．②④ D．①④ 72．用DFS（深度）遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。 A．逆拓扑有序 B．拓扑有序 C．无序的 73. 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为( ) A.O(1) B.O(logn) C.O(n) D.O(n logn) 因篇幅问题不能全部显示，请点此查看更多更全内容