一、单项选择题
1.对一个算法的评价，不包括如下(）方面的内容。
A．健壮性和可读性
B．并行性
c．正确性
D．时空复杂度
答案:B
2．在带有头结点的单链表H比L中，要向表头插入一个由指针p 指向的结点，则执行()。
A. p->next=HL->next;HL->next=p;
B. p->next=HL; HL=p;
C.p->next=HL; p=HL;
D.HL=p; p->next=HL;
答案:A
3.对线性表，在下列哪种情况下应当采用链表表示?()
A.经常需要随机地存取元素
B.经常需要进行插入和删除操作
c.表中元素需要占据一片连续的存储空间
D.表中元素的个数不变
答案:B
4.一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是()
A.2 31
B.3 2 1
C.312
D.12 3
答案:C
5. AOV网是一种().
A．有向图
B．无向图
c．无向无环图
D．有向无环图
答案:D
6.采用开放定址法处理散列表的冲突时，其平均查找长度()。
A．低于链接法处理冲突
B.高于链接法处理冲突
c.与链接法处理冲突相同
D．高于二分查找
答案:B
7．若需要利用形参直接访问实参时，应将形参变量说明为()参数。
A.值
B．函数
c.指针
D．引用
答案:D
8．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（)。
A．行号
B．列号
c.元素值
D．非零元素个数
答案:A
9.快速排序在最坏情况下的时间复杂度为()。
A. O(log2n)
B. O(nlog2n)
c. o(n)
D. 0(n2)
答案:D
10.从二叉搜索树中查找一个元素时，其时间复杂度大致为()。
A.O(n)B.O(1)
C. O(log2n)
D.O(n2)
答案:C
11.栈和队列的共同特点是().
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
答案:A
12.用链接方式存储的队列，在进行插入运算时().
A．仅修改头指针
B.头、尾指针都要修改
c.仅修改尾指针
D.头、尾指针可能都要修改
答案:D
13.以下数据结构中哪一个是非线性结构?()
A．队列
B.栈
c.线性表
D.二叉树
答案:D
14．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(1o)’A[2][2]存放位置在676(1o)，每个元素占一个空间，问A[3][3](o)存放在什么位置﹖脚注(1o)表示用10进制表示。
A. 688
B.678
C. 692
D.696
答案:C
15．树最适合用来表示()。
A.有序数据元素
B.无序数据元素
c.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
答案:C
16.二叉树的第k 层的结点数最多为().
A. 2k-1
B.2K+1
C.2K-1
D.2k-1
答案:D
17．若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为()
A.1，2，3
B.9，5，2，3
C.9，5，3
D.9，4，2，3
答案:D
18.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为
()
A.O (1)
B.O (n)
C.o ( 1og2n）
D.O (n2)
答案:C
19.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H(K） -=K%9作为散列函数，则散列地址为1的元素有(）个，
A.1
B.2
c.3
D.4
答案:D
20.设有6个结点的无向图，该图至少应有()条边才能确保是一个
连通图。
A.5
B.6
C.7
D.8
答案:A
21、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为()。
A.n
B.n/2
C.(n+1)/2
D.(n-1)/2
答案:C
22、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s 所指的结点,则执行()。
A.s→link=p→link; p一link=s;
B.p→link=s; s→link=q;
C.p→link=s→link; s→link=p;
D.q →link=s; s→link =p;
答案:D
23、栈的插入和删除操作在(）进行。
A.栈顶
B.栈底
C.任意位置
D.指定位置
答案:A
24、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为()
A.24
B.71
c.48
D.53
答案:B
25．算法指的是（)
A．计算机程序
B．解决问题的计算方法
c．排序算法
D.解决问题的有限运算序列
答案:D
26．线性表采用链式存储时，结点的存储地址（)
A．必须是不连续的
B．连续与否均可
c．必须是连续的
D．和头结点的存储地址相连续
答案:B
27．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为()
A. O (1）
B.o (n）
c. o (m）
D. O (m+n)
答案:C
28．由两个栈共享一个向量空间的好处是:()
A．减少存取时间，降低下溢发生的机率
B．节省存储空间，降低上溢发生的机率
c．减少存取时间，降低上溢发生的机率
D．节省存储空间，降低下溢发生的机率
答案:B
29．设数组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
答案:D
30．如下陈述中正确的是（）
A.串是一种特殊的线性表
B．串的长度必须大于零
c.串中元素只能是字母
D.空串就是空白串
答案:A
31．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（)
A. o ( 3 )
B. O (n)
c. 
D. 
答案:C
32.一个非空广义表的表头()
A．不可能是子表
B．只能是子表
c．只能是原子
D．可以是子表或原子
答案:D
33．在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为
0的结点个数为()
A.4
B. 5
C. 6
D.7
答案:C
34．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为()
A. e
B. 2e
c. 
D. 
答案:D
35．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点 
相关的所有弧的时间复杂度是()
A. O(n)
B. o(e)
c. O(n+e)
D. O(n*e)
答案:C
36．用某种排序方法对关键字序列(25，84，21，47，15，27，68，35，20)进行排序时，序列的变化情况如下:
则所采用的排序方法是（)
A．选择排序
B．希尔排序
c.归并排序
D．快速排序
答案:D
37．适于对动态查找表进行高效率查找的组织结构是()
A.有序表
B．分块有序表
c.三叉排序树
D．线性链表
答案:C
38．不定长文件是指()
A．文件的长度不固定
B.记录的长度不固定
c．字段的长度不固定
D．关键字项的长度不固定
答案:B
39.组成数据的基本单位是()。
A.数据项
B．数据类型
c.数据元素
D.数据变量
答案:C
40．设数据结构A=(D，R)，其中 D={1，2，3，4}，R=[r}，r=(<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是()。
A．线性结构
B.树型结构
c.图型结构
D.集合
答案:c
41．数组的逻辑结构不同于下列(）的逻辑结构。
A．线性表
B.栈
c.队列
D.树
答案:D
42.二叉树中第i(i≥1)层上的结点数最多有（）个。
A.2i
B. 
C. 
D.2i-1
答案:C
43．设指针变量p 指向单链表结点A则删除结点A的后继结点B需要的操作为()。
A. p->next=p->next->next
B.p=p->next
C.p=p->next->next
D. p->next=p
答案:A
44．设栈s和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（)。
A.6
B.4
C.3
D.2
答案:C
45.将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为()。
A.100
B.40
C.55
D.80
答案:c
46．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为()。
A.3
B.4
C.5
D.1
答案:B
47．根据二叉树的定义可知二叉树共有(）种不同的形态。
A.4
B.5
C.6
D.7
答案:B
48.设有以下四种排序方法，则(）的空间复杂度最大。
A．冒泡排序
B.快速排序
c.堆排序
D.希尔排序
答案:B
49、在一棵具有n个结点的二叉链表中，所有结点的空域个数等于（)。
A.n
B.n-1
C.n+1
D.2*n
答案:C
50、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是(）的二叉树。
A.空或只有一个结点
B.高度等于其节点数
c.任一结点无左孩子
D.任一结点无右孩子
答案:B
51、引起循环队列队头位置发生变化的操作是()。
A．出队
B.入队
C.取队头元素
D.取队尾元素
答案:A
52、设以数组A[m]存放循环队列的元素，其头尾指针分别为front和 rear，则当前队列中的元素个数为()。
A.(rear-front+m)%m
B.rear-front+1
C.( front-rear+m)%m
D.(rear-front)%m
答案:A
53、二维数组A[12][18]采用列优先的存储方法，若每个元素各占3个存储单元，且A[0][0]地址为150，则元素A[9][7]的地址为()。
A.429
B.432
C.435
D.438
答案:A
54、设有一个10阶的对称矩阵A[10][10]，采用压缩方式按行将矩阵中下三角部分的元素存入一维数组B[]中，A[0][0]存入B[0]中，则 A[8][5]在B[]中()位置。
A.32
B.33
C.41
D.65
答案:C
55、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B [1..(n(n+1))/2]中，则在B中确定aij (i＜j)的位置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
答案:A
56、在一棵度为3的树中，度为3的节点个数为2，度为2的节点个数为1，则度为0的节点个数为()。
A.4
B.5
C.6
D.7
答案:C
57、设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵子树的结点个数是（)。
A.m-n
B.m-n-1
C.n+1
D.条件不足，无法确定
答案:A
58、将一株有100个节点的完全二叉树从上到下，从左到右依次进行编号，根节点的编号为1，则编号为49的节点的左孩子编号为()。
A.98
B.89
C.50
D.没有孩子
答案:A
59、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（)。
A.存储结构
B.逻辑结构
C.算法
D.操作
答案:B
60、树最适合用来表示()。
A.有序数据元素
B.无序数据元素
c.元素之间具有分支层关系的数据
D.元素之间无联系的数据
答案:C
61、在一个非空二叉树的中序遍历序列中，根结点的右边()。
A.只有右子树上的所有结点
B.只有右子树上的部分结点
c.只有左子树的上的部分结点
D.只有左子树上的所有结点
答案:A
62、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中相对次序()。
A.不发生改变
B.发生改变
c.不能确定
D.以上都不对
答案:D
63、在有n个叶子结点的哈夫曼树中，其结点总数为()。
A．不确定
B.2n
C.2n+1
D.2n-1
答案:D
64、权值为{1,2,6,8}的四个结点构成的哈夫曼树的带权路径长度是()。
A.18
B.28
C.19
D.29
答案:D
65、对一个满二叉树，m个树叶，k 个分枝结点，n个结点，则()。
A.n=m+1
B.m+1=2n
C.m=k-1
D.n=2k+1
答案:D
66、设有一个递归算法如下:int fact(int n)
则计算fact(n)需要调用该函数的次数为()。
A. n
B.n+1
C.n+2
D.n-1
答案:B
67、若采用邻接矩阵翻存储一个n个顶点的无向图,则该邻接矩阵是一个()。
A.上三角矩阵
B.稀疏矩阵
C.对角矩阵
D.对称矩阵
答案:D
68、在一个图中，所有顶点的度数之和等于所有边数的(）倍。
A.1/2
B.1
C.2
D.4
答案:c
69、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。
A.1/2
B.1
C. 2
D.4
答案:B
70、非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是()。
A.rear->next= =head
B.rear->next->next= =head
C.head->next= =rear
D.head->next->next= =rear
答案:A
71、从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（)。
A.n-i
B.n-i+1
C.n-i-1
D.i
答案:A
72、n个顶点的连通图至少中含有()。
A.n-1
B.n
C.n+1
D.0
答案:A
73、n个顶点的完全有向图中含有()。
A.n-1条有向边
B.n条有向边
C. n(n-1)/2条有向边
D. n(n-1)条有向边
答案:D
74、假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除预某个顶点vi相关的所有弧的时间复杂度是（)。
A.O(n)
B.O(e)
c.O(n+e)
D.O(n*e)
答案:C
75、在无向图中定义顶点Vi域Vj之间的路径为从Vi到达Vj的一个()。
A.顶点序列
B.边序列
C.权值总和
D.边的条数
答案:A
76、无向图G=(V,E),其中: V={a,b,c,d,e,f},E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优先遍历，得到的顶点序列正确的是()。
A.abecdf
B.acfebd
C.aebcfd
D.aedfcb
答案:D
77、下面哪一方法可以判断出一个有向图是否有环（回路)。()
A.求节点的度
B.拓扑排序
c.求最短路径
D.求关键路径
答案:B
78、图的广度优先搜索类似于树的(）次序遍历。
A．先根
B.中根
c.后根
D.层次
答案:B
79、在图采用邻接表存储时，求最小生成树的 Prim算法的时间复杂度为()。A.O(n)
B.O(n+e)
c.O(n2)
D.O(n3)
答案:B
80 、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7} ，E={<V1,V2>,<V1,V3>,<V1,V4>,
<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是()。
A.V1,V3,04,V6,V2,V5,V7
B.V1,13,V2,v6,V4,V5,V7
C.V1,V3,V4,V5,V2,06,V7
D.V1,v2,15,V3,V4,v6,V7
答案:A
81、关键路径是事件结点网络中()。
A.从源点到汇点的最长路径
B.从源点到汇点的最短路径
c.最长回路
D.最短回路
答案:A
82、有n个结点的有向完全图的弧数是（)。
A.n2
B.2n
C.n(n-1)
D.2n(n+1)
答案:C
83、设图的邻接链表如题12图所示，则该图的边的数目是（)。
A.4
B.5
C.10
D.20
答案:B
- 在一个图中，所有顶点的度数之和等于图的边数的(）倍。
A.1/2
B.1
C.2
D.4
答案:A
85、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（)倍。
A.1/2
B.1
C.2
D.4
答案:B
86、有8个结点的无向图最多有()条边。
A.14
B.28
C.56
D.112
答案:B
87、有8个结点的无向连通图最少有(）条边。
A.5
B.6
C.7
D.8
答案:c
88、有8个结点的有向完全图有（）条边。
A.14
B.28
C.56
D.112
答案:C
89、用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的。A.栈
B.队列
C.树
D.图
答案:B
90、用邻接表表示图进行深度优先遍历时，通常是采用(）来实现算法的。
A.栈
B.队列
c.树
D.图
答案:A
91、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是()。
A.02 4 3156
B.0 13654 2
C.0 423165
D.036154
2
建议:0134256
答案:c
92、已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是()。
A. 0243156
B.013564 2
C.0423165
D.0134256
答案:D
93、已知图的邻接矩阵同上题8，根据算法，则从顶点О出发，按广度优先遍历的结点序列是（)。
A. 0243651
B. 0136425
C. 0423156
D. 0134256
答案:B
- 在下面的程序段中，对x的赋值语句的频度为()。
A. O(2n)
B.o(n)
c. 
D.O(log2n)
答案:C
95、 己知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是()。
A) 132
B)0231
c)0321
D) 0123
答案:D
- 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是()。
A.0 321
B.0 123
C.0 132
D.0312
答案:A
97、深度优先遍历类似于二叉树的(） 。
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
答案:A
98、广度优先遍历类似于二叉树的(） 。
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
答案:D
99、任何一个无向连通图的最小生成树(） 。
A.只有一棵
B.一棵或多棵
C.一定有多棵
D．可能不存在
答案:A
100、在分析折半查找的性能时常常加入失败节点，即外节点，从而形成扩充的二叉树。若设失败节点i所在层次为Li，那么查找失败到达失败点时所做的数据比较次数是()。
A.Li+1
B.Li+2
C.Li-1
D. Li
答案:D
评论0