数据结构(第二版)复习题及答案
复 习 题
一、选择:
1、数据的基本单位是( B ),在计算机中作为整体进行处理
A 、数据项 B 、数据元素 C 、数据对象 D 、数据结构
2、在一个顺序表中,如果第一个元素的存储地址为100,每个元素的长度为2,则第5个元
素的地址为( B )
计算过程:100+(5-1)*2=108
A 、110 B 、 108 C 、100 D 、120
3、链表不具备的特点是( A )
A 、可以随机访问 B 、插入删除不必移动元素
C 、不必事先估计存储空间 D 、所需空间与其长度成正比
4、在一个长度为n 的顺序表的第i 个元素前插入一个元素时,需要向后移动( A )个
元素
A 、n - i +1 B 、 n – i C 、 n – i – 1 D 、 i
5、在一个单链表中,如果在P 所指的结点后插入S 所指结点,则执行 ( B )
A 、s ->next = p p -> next =s
B 、s ->next =p ->next p ->next = s
C 、s -> next = p -> next p = s
D 、p - >next = s s->next =p
6、删除一个长度为n 的顺序表的第i 个元素,需要向前移动( B )个元素
A 、 n - i +1 B 、 n – i C 、 n – i – 1 D 、 i
7、从一个具有n 个结点的单链表中查找其值为x 的结点,在查找成功的情况下,需要比较
( D )个结点
A 、n B 、 n /2 C 、 (n – 1)/2 D 、(n + 1)/2
8、在一个单链表中,q 是p 所指结点的前趋结点,如果在q 和p 之间插入s 结点,则执行( C )
A 、s->next = p->next p->next =s B 、p->next =s>next s->next = p
C 、q->next =s s->next = p D 、p->next =s s->next = q
9、使带头结点的单链表为空的判定条件是( B )
A 、head = NULL B 、 head -> next = = NULL
C 、head - >next = head D 、 head ! = NULL
10、在一个具有n 个结点的有序链表中插入一个新结点并仍然有序的时间复杂度是(
A 、O (1) B 、O (n ) C 、O (n 2) D 、O (nlog 2n )
11、如果1,2,3依次进栈,则出栈顺序不可能是( C )
A 、3 2 1 B 、 2 1 3 C 、3 1 2 D 、1 3 2
解析:1 2 3分别进栈→3 2 1分别出栈
1进2进→2出1出 3进→ 3出
1进→1出 2进 3进 →3出 2出
12、非空的循环单链表head 的尾结点P 满足( C )
A 、p -> next = = NULL B 、P = = NULL
C 、P - >next = = head D 、p = = head
13、建立有序单链表的时间复杂度为( C )
A 、O (1) B 、O(n) C 、O(n2) D 、O(nlog2n )
14、不带头结点的单链表为空的判定条件是( A )
A 、head = NULL B 、 head -> next = = NULL
C 、head - >next = head D 、 head ! = NULL
B )
15、判断链队为空的条件是( A )
A 、Q->front = = Q->rear B 、Q->front != Q->rear
C 、Q->front = = (Q->rear +1)% n D 、Q->front != (Q->rear +1)% n
16、循环队列的头尾指针分别为front 和rear ,则循环队列为满的条件是( C )
A 、Q->front = = Q->rear B 、Q->front != Q->rear
C 、Q->front = = (Q->rear +1)% n D 、Q->front != (Q->rear +1)% n
17、进队序列为1,2,3,4, 进行1次出队运算后,队头结点为( B )
A 、1 B 、2 C 、3 D 、4
18、在一个单链表中,删除P 所指结点的后继结点,应执行 ( A )
A 、p ->next = p->next ->next
B 、p = p->next; p ->next = p->next ->next
C 、p ->next = p ->next
D 、p = p ->next ->next
19、链表的优点是( C )
A 、便于随机存取 B 、花费的存储空间比顺序表少
C 、便于插入与删除 D 、数据元素的物理顺序与逻辑顺序相同
20、在一个链队中,假设f 和r 分别为队首和队尾指针,则插入s 所指结点的运算是( B )
A 、f->next=s;f=s;
B 、r->next=s;r=s;
C 、s->next=r;r=s;
D 、s->next=f;f=s;
21、设高度为h 的二叉树上只有度为0和度为2的结点,则此二叉树中包含的结点数至少为
( B )个
A 、2h B 、2h-1 C 、2h+1 D 、h+1
22、一个栈的进栈序列是1,2,3,4,则出栈序列不可能是( C )
A 、1 2 3 4 B 、4 3 2 1
C 、4 1 3 2 D 、3 2 4 1
23、采用邻接表存储的图的深度优先搜索遍历类似于二叉树的( A )
A 、先序遍历 B 、中序遍历
C 、后序遍历 D 、层次遍历
24、从一个栈顶指针为HS 的链栈中删除一个结点时,用x 保存被删结点的值,则执行( D )
A 、x=HS; HS= HS->next B 、x=HS->data;
C 、HS= HS->next; x=HS->data D 、x=HS->data; HS= HS->next
25、具有6个结点的无向图至少有( A )条边才能形成连通图
A 、5 B 、6 C 、7 D 、8
26、在链队Q 中,插入S 所指结点需执行的命令是( B )
A 、Q->front ->next =s ; f=s B 、Q->rear->next=s; Q.rear=s
C 、s->next =Q->rear Q->rear=s D 、S->next=Q->front Q->front =s;
27、如果二叉树的先序遍历序列为ABDGCEFH ,中序遍历序列为DGBAECHF, 则后序遍历
序列为( D )
A 、BDGCEFHA B 、GDBECFHA C 、BDGAECHF D 、GDBEHFCA
28、具有5个顶点的无向完全图有( A )条边
A 、10 B 、24 C 、 25 D 、20
29、采用邻接表存储的图的广度优先搜索遍历类似于二叉树的(D )
A 、先序遍历 B 、中序遍历
C 、后序遍历 D 、层次遍历
30、在链队Q 中,删除一个结点需执行的命令是( B )
A 、Q->rear = Q->front->next B 、Q->rear->next= Q->rear->next->next
C 、Q->front->next = Q->front->next->next D 、Q->front= Q->rear->next
31、在解决计算机与打印机之间速度不匹配问题时通常设置一个打印缓冲区,主机将要输出
的数据依次写入缓冲区,打印机则从缓冲区取出数据打印,该缓冲区使用( B )结构
A 、堆栈 B 、队列 C 、数组 D 、树
32、在有向图的邻接表存储结构中,顶点v 在表结点中出现的次数是( B )
A 、顶点v 的度 B 、顶点的出度
C 、顶点v 的入度 D 、依附于顶点V 的边数
33、将一棵有100个结点的完全二叉树从上到下,从左到右依次对结点编号,根结点编号为
1,则编号为49的结点的左孩子为( B )
A 、99 B 、98 C 、50 D 、48
34、二维数组SA 中,每个元素的长度为3个字节,行下标从0到7,列下标从0到9,从
首地址SA 开始连续存放在存储器中,该数组按列存放,元素A[4][7]的地址为( B )
A 、SA +141 B 、SA+180 C 、SA+222 D 、SA+225
35、数组A 中,每个元素的长度是3字节,行下标i 从1到8,列下标j 从1到10,从首地
址开始连续存放在存储器内,存放该数组至少需要的单元数是( B )。
A 、80 B 、100 C 、240 D 、270
36、将一个A[15][15]的下三角矩阵,按行优先存入一维数组B[120]中,A 中元素A[6][5]在
B 数组中的位置K 为( B )
A 、19 B 、26 C 、21 D 、15
37、广义表A = ( a , b, (c,d) ,(e,(f,g))), 则Head(Tail(Head(Tail(Tail(A))))) = ( D )
A 、(g) B 、(d ) C 、c D 、d
38、在一个无向图中,所有顶点的度数之和等于所有边数的( B )
A 、1/2 B 、2 C 、1 D 、4
39、已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac ,则前序遍历序列为
( D )
A 、acbed B 、decab C 、 deabc D 、cedba
40、由权为8,2,5,7的四个叶子结点构造一棵哈夫曼树,该树的带权路径长度为(
A 、23 B 、37 C 、46 D 、43
41、下面结论正确的是( D )
A 、在无向图中,边的条数是结点度数之和
B 、在图结构中,结点可以没有任何前趋和后继
C 、在n 个结点的无向图中,如果边数大于n-1; 则该图必是连通图
D 、图的邻接矩阵必定是对称矩阵
42、由下图得到的拓朴序列,以下选项中合理的为( A )
A 、 V 1 V 4 V 6 V 2 V 5 V 3
B 、 V 1 V 2 V 3 V 4 V 5 V 6
C 、 V 1 V 4 V 2 V 3 V 6 V 5
D 、 V 1 V 2 V 4 V 6 V 3 V 5
D )
二、填空题
1、数据常用的存储表示方法有三种,分别为 、 。
2、算法的时间复杂度取决于
3、线性表的存储方式有二种,分别为
4、线性表的顺序存储结构是一种链式存储结构是一种储结构。
5、为结点p 申请一个存储空间,则使用语句
6、算法的特点包括:输入和输出。
7、双向链表中,每个结点有两个域,一个指向
8、评价算法优劣时需要考虑和高效性。
9、链式存储结构中,指针域只有一个指针的线性表称为
10、串的顺序存储方式分别为 和 单字节储存格式 。
11、链表中的结点包括两个域,数据域存放 结点值 ,指针域存放 结点后续地址
12、如果链表最后一个结点的指针域指向其头结点,则该链表为 循环链表13、线性结构中元素之间存在 关系,图形结构元素之间存在 多对多 关系。
14、栈满时进栈称为,栈空时出栈称为
15、进行串的模式匹配时,BF 算法和KMP 算法的区别在于无回溯
16、为了解决假溢出并使得队列的空间得到充分利用,使用的环形。
17、对于一个单链表,在p 所指的结点后插入S 所指结点, 应执行18、串的赋值使用 算法实现,求子串使用 算法实现
19、算法分析有两个方面,分别为
20、数据元素由组成,是数据的最小单位
21、栈的特点是,队列的特点是栈中元素的插入和删
除在 栈顶 进行,22、队列只能在 队尾 插入元素,在 对头 删除元素。
23、串的模式匹配的算法分别为BF 算法和KMP 算法
24、时间复杂度用25、数据结构指数据之间的关系,包括三方面的内容,分别为
26、一棵深度为5的完全二叉树的第5层有5个叶子结点,则共有个结点
27、矩阵中含有大量零元素的矩阵称为 系数矩阵
28、数据的存储结构包括四种,分别为 和 哈希储存
29、稀疏矩阵使用 进行压缩存储
30、在顶点活动图中,如果从顶点v i 到v j 有一条路径,则顶点v i 必在v j 之前,满足此关系的线性序列称为 拓扑序列
31、树与二叉树的区别为
32、深度优先搜索类似于树的,广度优先搜索类似于树的
33、在二叉树的第i 层至多有
34、构造最小生成树的算法有两种,分别为普利姆和克鲁斯卡尔
35、深度为k 的二叉树至多有个结点。
36、图的遍历方式有两种,分别为深度优先搜索遍及和广度优先搜索遍及37、具有n 个结点的完全二叉树的深度为2。
38、二叉树采用顺序存储结构时,结点间的逻辑关系使用
39、在有向图中,极大的连通子图称为
40、顶点活动图中,顶点表示,顶点活动图中不应该出现 回环
41、有向图的邻接表中第i 个链表中结点的数目取决于
42、二叉树的遍历方式有43、计算最短路径时使用
44、图的存储结构有二种,分别为邻接矩阵 和 邻列表
45、n 个顶点的连通图至少有条边
46、由n 个带权叶子结点构成的所有二叉树中带权路径长度最小的二叉树是47、使用孩子表示法存储树时,除了值域,还包含48、具有n 个结点,
49、无向图使用邻接矩形表示时,其对应的邻接矩阵是
50、网中邻接矩阵中,如果顶点v i 和 v j 存在边,则邻接矩阵中使用 权值 表示,否则使用 (无穷大符号) 表示
51、连通图的极小连通子图称为
52、树的存储结构有三种,分别为双亲表示法、孩子表示法 和 孩子兄弟表示法
53、使用孩子兄弟表示法存储树时,链表中每个结点的链域分别指向第一个孩子 和 下一个兄弟
54、度为k ,且有个结点的二叉树称为满二叉树。
55、散列查找时查找的效率取决于构造散列表时选取的 处理冲突的方法 和 装填因子 。