手机扫描二维码答题
00:00:00
第3章-线性表（常规课）
录音中...
*
您的姓名：
*
签名：
请在以下矩形区域内绘制
清空
撤销
橡皮擦
确定并上传
*
1.
在长度为n的线性表中查找值为x的数据元素的时间复杂度为O(n)。（）
对
错
需要遍历整个线性表，最坏O(n)。
*
2.
线性表的逻辑顺序与物理顺序总是一致的。（）
对
错
顺序存储时一致，链式存储时不一定一致。
*
3.
顺序表中逻辑上相邻的元素，物理位置（）相邻，单链表中逻辑上相邻的元素，物理位置（）相邻。
顺序表物理连续，链表物理地址不一定连续。
*
4.
从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（）个元素结点。
A、n/2
B、n
C、(n+1)/2
D、(n-1)/2
平均情况下，目标元素在链表中间，需比较n/2次。
*
5.
在含有127个元素的顺序表中插入一个新元素，平均移动元素的次数是（）?
A、8
B、63.5
C、63
D、7
顺序表插入时，平均需要移动一半的元素。127/2=63.5，插入位置随机分布时，平均移动次数为63.5。
*
6.
顺序表具有随机存取特性，指的是（）。
A、查找序号为i的元素的时间与顺序表中元素个数n无关
B、查找序号为i的元素的时间与顺序表中元素个数n有关
C、查找值为x的元素的时间与顺序表中元素个数n无关
D、查找值为x的元素的时间与顺序表中元素个数n有关
顺序表（数组）可以通过下标直接访问任意元素，时间复杂度为O(1)。
*
7.
在顺序表中，只要知道（），就可在相同时间内求出任一结点的存储地址。
A、基地址
B、结点大小
C、向量大小
D、基地址和结点大小
顺序表的地址计算公式只需基地址和下标。
*
8.
在（）运算中，使用顺序表比链表好。
A、插入
B、删除
C、根据序号查找
D、根据元素值查找
顺序表支持O(1)的随机访问。
*
9.
根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为（）链表和（）链表。
单链表每结点一个指针，双链表两个。
*
10.
在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（）。
A、s->next=p->next; p->next=s
B、q->next=s; s->next=p
C、p->next=s->next; s->next=p
D、p->next=s; s->next=q
插入s结点时，先让q的next指向s，再让s的next指向p。
*
11.
单链表从任何一个结点出发，都能访问到所有结点。（）
错
对
只能从头结点出发遍历。
*
12.
设计一个判别表达式中左右括号是否配对的算法，采用（）数据结构最佳。
A、顺序表
B、栈
C、队列
D、链表
括号匹配问题用栈可以实现先进后出，适合嵌套结构。
*
13.
在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是（）。
A、O(1)
B、O(n)
C、O(n^2)
D、O(log2n)
需要遍历链表找到插入位置。
*
14.
算法设计题:在顺序存储的有序表L中，查找关键字与key相同的记录，如果找到则返回该元素的下标，如果没有找到，返回0。补全下列折半查找算法。
int Bin_search(SqLlist L,int key){
int low,high,mid;
low=1;high=L.length;
while(_______){ //第①空
mid=________; //第②空
if (L.r[mid].key>key)_______; //第③空
else if ( L.r[mid].key<key)__________; //第④空
else return mid;
}
________
; //第⑤空
}
折半查找通过不断缩小查找区间，效率高于顺序查找。
*
15.
在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是O(n)。（）
对
错
需要遍历查找插入位置，O(n)。
*
16.
在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（）。
A、rear%n==front
B、(front+1)%n==rear
C、rear%n-1==front
D、(rear+1)%n==front
队满时rear的下一个位置是front。
*
17.
栈是一种特殊的线性表，它所有的插入和删除都限制在表的同一端进行。（）
对
错
栈的特性是后进先出。
*
18.
在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是（）。
A、p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
B、s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
C、p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
D、s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
插入操作需先让新结点s的prior指向p，next指向p的next，再让p的next的prior指向s，最后p的next指向s，顺序不能错。
*
19.
线性表中的每个结点最多只有一个前驱和一个后继。（）
对
错
线性表的定义。
*
20.
若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（）存储方法最合理。
A、单链表
B、带头指针的循环单链表
C、双链表
D、带尾指针的循环单链表
带尾指针的循环单链表可以在O(1)时间内在表尾插入结点，同时删除表头结点也很方便，效率最高。
*
21.
线性表是（）。
A、一个有限序列，可以为空
B、一个有限序列，不可以为空
C、一个无限序列，可以为空
D、一个无限序列，不可以为空
线性表的定义是零个或多个数据元素的有限序列。
*
22.
若一个栈用数组data[1..n]存储，初始栈顶指针top为0，则以下元素x进栈的正确操作是（）。
A、top++;data[top]=x;
B、data[top]=x;top++;
C、top--;data[top]=x;
D、data[top]=x;top--;
栈顶指针先加一再赋值。
*
23.
在双向链表中，每个结点含有两个指针域，一个指向（）结点，另一个指向（）结点。
双向链表每个结点有两个指针，分别指向前驱和后继。
*
24.
在一个具有n个单元的顺序栈中，假定以地址低端(即0单元)作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（）。
A、top不变
B、top=0
C、top--
D、top++
出栈时栈顶指针减一。
*
25.
设单链表中指针p指向结点m，若要删除m之后的结点(若存在)，则需修改指针的操作为（）。
A、p->next=p->next->next;
B、p=p->next;
C、p=p->next->next;
D、p->next=p;
删除m后结点时，p的next应指向m后结点的next。
*
26.
在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为（）。
A、rear%n==front
B、front+1=rear
C、rear==front
D、(rear+1)%n=front
循环队列判空时front和rear相等。
*
27.
以下关于线性表的说法不正确的是（）。
A、线性表中的数据元素可以是数字、字符、记录等不同类型。
B、线性表中包含的数据元素个数不是任意的。
C、线性表中的每个结点都有且只有一个直接前趋和直接后继。
D、存在这样的线性表:表中各结点都没有直接前趋和直接后继。
线性表中除第一个和最后一个结点外，每个结点都有且只有一个直接前驱和直接后继。
*
28.
在一个带头结点的循环单链表L中，删除元素值为x的结点，算法的时间复杂度为（）。
A、O(n)
B、O(1)
C、O(nlog2n)
D、O(n^2)
需要遍历链表查找值为x的结点，最坏情况下需要遍历所有结点。
*
29.
在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（）。
A、front=front->next
B、rear=rear->next
C、rear=front->next
D、front=rear->next
链队列删除操作只需移动front指针。
*
30.
与非循环单链表相比，循环单链表的主要优点是（）。
A、不再需要头指针
B、已知某个结点的位置后，能够容易地找到它的前驱结点
C、在进行插入、删除操作时，能更好地保证链表不断开
D、从表中任意结点出发都能扫描到整个链表
循环单链表的最大特点是最后一个结点的指针指向头结点，形成一个环，因此可以从任意结点出发遍历整个链表。
*
31.
当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用（）存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用（）存储结构为宜。
顺序存储适合查找，链式存储适合频繁插入删除。
*
32.
设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列（）。
A、A, B, C, D, E
B、B, C, D, E, A
C、E, A, B, C, D
D、E, D, C, B, A
栈的出栈序列必须满足后进先出，E出栈后A不能再出栈。
*
33.
在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（）?
A、直接前趋
B、直接后继
C、开始结点
D、终端结点
单链表的每个结点包含数据域和指针域，指针域用于指向下一个结点（即直接后继），这样才能实现链表的顺序连接。
*
34.
线性表、栈和队列都是（）结构，可以在线性表的（）位置插入和删除元素;对于栈只能在（）位置插入和删除元素;对于队列只能在（）位置插入元素和在（）位置删除元素。
三种结构的操作位置不同。
*
35.
线性表采用链式存储时，其地址（）。
A、必须是连续的
B、一定是不连续的
C、部分地址必须是连续的
D、连续与否均可以
链式存储结构对物理地址没有要求，可以连续也可以不连续。
*
36.
在n个元素的顺序表中，算法的时间复杂度是O(1)的操作是（）。
A、访问第i个元素(2≤i≤n)及其前驱元素
B、删除第i个元素(1≤i≤n)
C、在第(1≤i≤n)个元素后插入一个新元素
D、将n个元素从小到大排序
顺序表支持O(1)的随机访问。
*
37.
对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为（），在给定值为x的结点后插入一个新结点的时间复杂度为（）。
已知位置插入O(1)，查找O(n)。
*
38.
向一个栈顶指针为hs的链栈中插入一个s结点时，应执行（）。
A、hs->next=s;
B、s->next=hs; hs=s;
C、s->next=hs->next; hs->next=s;
D、s->next=hs; hs=hs->next;
链栈插入时新结点s指向原栈顶，栈顶指针指向s。
*
39.
在长度为n(n≥1)的双链表中插入一个结点(非尾结点)要修改（）个指针域。
A、1
B、2
C、3
D、4
插入一个结点需要修改前驱结点的next、后继结点的prior、新结点的next和prior，共4个指针域。
*
40.
线性表的顺序存储结构是一种（）的存储结构。
A、随机存取
B、顺序存取
C、索引存取
D、散列存取
顺序存储结构的元素在物理上是连续存放的。
*
41.
长度为20的有序表采用折半查找，共有（）个元素的查找长度为3。
A、2
B、3
C、4
D、5
折半查找时，查找长度为3的元素有4个。
*
42.
线性表采用链式存储结构时，要求内存中可用存储单元的地址（）?
A、必须是连续的
B、必须是部分连续的
C、一定是不连续的
D、连续和不连续都可以
链式存储结构的优点之一就是对物理地址没有连续性的要求，可以充分利用内存的零散空间。
评价对象得分
字体大小
第3章-线性表（常规课）
复制
