数据结构试题及答案 一、单项选择题
1.一个算法应该是（ ）。
A．程序 B．问题求解步骤的描述
C．要满足五个基本属性 D．A和C. 2.算法指的是（ ）。
A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列。
3.与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ A. 存储结构 B. 逻辑结构 C. 算法 D.操作 4.从逻辑上可以把数据结构分为（ ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 5.线性表采用链式存储时，节点的存储的地址（ ）。 A. 必须是不连续的 B. 连续与否均可
C. 必须是连续的 D. 和头节点的存储地址相连续 6.在下面的程序段中，对x的赋值语句的频度为（ ）。
FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;
A． O(2n) B．O(n) C．O(n2) D．O(log2n) 7.程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1]
THEN A[j]与A[j+1]对换；
其中 n为正整数，则最后一行的语句频度在最坏情况下是（ ）。A. O(n） B. O(nlogn) C. O(n3) D. O(n2) 8. 设有一个递归算法如下：
int fact(int n)
{ /* 大于等于0 */ if ( n<=0 ) return 1 ; else return n*fact (n-1) ; }
则计算fact(n)需要调用该函数的次数为（ ）。
。 ）
A. n B. n+1 C. n+2 D. n-1 9. 若在线性表中采用折半查找法查找元素，该线性表应该( )。 A．元素按值有序 B．采用顺序存储结构
C．元素按值有序，且采用顺序存储结构 D．元素按值有序，且采用链式存储结构 10. 用链表表示线性表的优点是（ ）。
A. 便于随机存取 B．花费的存储空间比顺序表少 C．便于插入与删除
D．数据元素的物理顺序与逻辑顺序相同
11. 链表不具有的特点是（ ） 。
A. 插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 12. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( )。 A. n-i+1 B. i C. i+1 D. n-i
13. 采用顺序搜索方法查找长度为n的顺序表示，搜索成功的平均搜索长度为（ ）。
A. n B. n/2 C. (n-1)/2 D. (n+1)/2 14. 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ）。
A. O(1) B. O(n) C. O(m) D. O(m+n)
15. 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是( )。 A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head
16. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 17. 链式栈与顺序栈相比，一个比较明显的优点是（ ）。
A. 插入操作更加方便 B.通常不会出现栈满的情况 C. 不会出现栈空的情况 D. 删除操作更加方便
18. 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（ ）。
A. 较快 B. 较慢 C. 相同 D. 不定
19. 若已知一个栈的入栈序列是1,2,3,4……n，其输出序列为p1,p2,p3,……pn，
若p1= =n,则pi为（ ）。
A. i B. n= =i C. n-i+1 D. 不确定
20. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是( ) 。
A. edcba B. decba C. dceab D. abcde
21. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( )。
A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4
22. 对于栈操作数据的原则是（ ）。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 23. 栈和队列的共同点是（ ）。
A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 24. 一个队列的入队序列是1，2，3，4，则队列的输出序列是（ ）。 A. 4,3,2,1 B. 1,2,3,4 C.1,4,3,2 D. 3,2,4,1 25. 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front指为（ ）。 A. front=front+1 B. front=(front+1)%(m-1) C. front=(front-1)%m D. front=(front+1)%m 26. 引起循环队列队头位置发生变化的操作是( )。
A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素
27. 设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。
A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m
28. 二维数组A[12][18]采用列优先的存储方法，若每个元素各占3个存储单元，且A[0][0]地址为150，则元素A[9][7]的地址为( )。
A. 429 B. 432 C. 435 D. 438
29. 设有一个10阶的对称矩阵A[10][10]，采用压缩方式按行将矩阵中下三角部分的元素存入一维数组B[]中，A[0][0]存入B[0]中，则A[8][5]在B[]中（ ）位置。
A. 32 B. 33 C. 41 D. 65
30. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i 的位置k的关系为( )。 A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i 31. 对稀疏矩阵进行压缩存储目的是（ ）。 A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度 32. 树中所有结点的度之和等于所有结点数加（ ）。 A. 0 B.1 C. －1 D. 2 33. 在一棵具有n个结点的二叉链表中，所有结点的空域个数等于（ ）。 A. n B. n-1 C. n+1 D. 2*n 34. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 A. 空或只有一个结点 B. 高度等于其节点数 C. 任一结点无左孩子 D. 任一结点无右孩子 35. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ）。 A. 2h B. 2h-1 C. 2h+1 D. h+1 36. 在一棵度为3的树中，度为3的节点个数为2，度为2的节点个数为1，则度为0的节点个数为（ ）。 A. 4 B. 5 C. 6 D. 7 37. 设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n,森林F中第一棵 子树的结点个数是（ ）。 A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 38. 将一株有100个节点的完全二叉树从上到下，从左到右依次进行编号，根节点的编号为1，则编号为49的节点的 左孩子编号为（）。 A. 98 B. 89 C. 50 D. 没有孩子 39. 下列图示的顺序存储结构表示的二叉树是(A ) 40. 树最适合用来表示（ ）。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 41. 在一个非空二叉树的中序遍历序列中，根结点的右边（ ）。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树的上的部分结点 D. 只有左子树上的所有结点 42. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中相对次序（ ）。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 43. 在有n个叶子结点的哈夫曼树中，其结点总数为（ ）。 A. 不确定 B. 2n C. 2n+1 D. 2n-1 44. 权值为{1,2,6,8}的四个结点构成的哈夫曼树的带权路径长度是（ ）。 A. 18 B. 28 C. 19 D. 29 45. 对一个满二叉树，m个树叶，k个分枝结点，n个结点，则（ ）。 A. n=m+1 B. m+1=2n C. m=k-1 D. n=2k+1 46. 在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ ）。 A. e B. 2e C. n2-e D. n2-2e 47. 若采用邻接矩阵存储一个n个顶点的无向图，则该邻接矩阵是一个（ ）。 A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵 48. 在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。 A. 1/2 B. 1 C. 2 D. 4 49. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A. 1/2 B. 1 C. 2 D. 4 50. n个顶点的连通图至少中含有( )。 A. n-1 B. n C. n+1 D. 0 51. n个顶点的完全有向图中含有( )。 A. n-1条有向边 B. n条有向边 C. n(n-1)/2条有向边 D. n(n-1)条有向边 52. 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除预某个顶点vi相关的所有弧的时间复杂度是（ ）。 A. O(n) B. O(e) C. O(n+e) D.O(n*e) 53. 在无向图中定义顶点Vi域Vj之间的路径为从Vi到达Vj的一个（ ）。 A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条 数 54. 由同一组关键字集合构造的各棵二叉排序树( )。 A. 其形态不一定相同，但平均查找长度相同 B. 其形态不一定相同，平均查找长度也不一定相同 C. 其形态均相同，但平均查找长度不一定相同 D. 其形态均相同，平均查找长度也都相同