复 习 题
一、选择：
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（n2） D、O（nlog2n）
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
