一、单选题
1.数据结构中，与所使用的计算机无关的是数据的（D）。
A.存储结构
B.物理和存储结构
C.物理结构
D.逻辑结构
2.在数据结构中，从逻辑上可以把数据结构分为（D）。
A.动态结构和静态结构
B.紧凑结构和非紧凑结构
C.内部结构和外部结构
D.线性结构和非线性结构
3.线性结构中数据元素之间的关系是（A）
A.一对一
B.一对多
C.多对一
D.多对多
4.树形结构中数据元素之间的关系是（B）
A.一对一
B.一对多
C.多对一
D.多对多
5.数据的存储结构包括数据元素的表示和（D）。
A.数据处理的方法
B.相关算法
C.数据元素的类型
D.数据元素间的关系的表示
6.每个存储结点只存储一个数据元素，各结点存储在连续的存储空间，该存储方式是（A）存储方式。
A.顺序
B.链接
C.索引
D.散列
7.线性表中（C）称为线性表的长度。
A.数据最大值
B.数据最小值
C.数据元素个数
D.表的行数
8.设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（C）。
A.n-i
B.n-i-1
C.n-i+1
D.i
9.设有一个长度为n的顺序表，要删除第i个元素,则需移动元素的个数为（C）。
A.i
B.n-i-1
C.n-i
D.n-i+1
10.有关线性表的正确说法是（D）。
A.线性表至少要求一个元素
B.每个元素都有一个直接前驱和一个直接后继
C.表中的元素必须按由小到大或由大到下排序
D.除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继
11.在线性表的顺序结构中，以下说法正确的是（D）。
A.逻辑上相邻的元素在物理位置上不一定相邻
B.数据元素是不能随机访问的
C.进行数据元素的插入、删除效率较高
D.逻辑上相邻的元素在物理位置上也相邻
12.在非空双向循环链表的*p结点之前插入*q结点的操作是（D）。
A.p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;
B.p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior;
C.q->next=p;q->prior=p->prior;p->prior=q;p->prior->next=q;
D.q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;
13.对链表, 以下叙述中正确的是（A）。
A.不能随机访问任一结点
B.插入删除元素的操作一定要要移动结点
C.结点占用的存储空间是连续的
D.可以通过下标对链表进行直接访问
14.非空的单向循环链表的尾结点满足（A）（设头指针为head，指针p指向尾结点）。
A.p->next==head
B.p==NULL
C.p== head
D.p->next==NULL
15.设头指针为head的非空的单向链表，指针p指向尾结点,则通过以下操作（ D )可使其成为单向循环链表。
A.head = p;
B.p=head;
C. p->next = NULL;
D.p->next=head;
16.链表不具有的特点是（B）。
A.不必事先估计存储空间
B.可随机访问任一元素
C.逻辑上相邻的元素在物理位置上不一定相邻
D.插入删除不需要移动元素
17.在一个单链表Head中，若要向表头插入一个由指针p指向的结点，则执行（B）。
A.Head=p;p->next=Head;
B.p->next=Head;Head=p;
C.p->next=Head;p=Head;
D.p->next=Head->next;Head->next=p;
18.在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（D）。
A.p->next=s;s->next=p->next;
B.p->next=s->next;
C.p=s->next;
D.s->next=p->next;p->next=s;
19.对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该（B）。
A.以顺序存储方式
B.以链接存储方式
C.以索引存储方式
D.以散列存储方式
20.若Head为一个带表头结点的单链表的表头指针，则该表为空表的条件是（B）。
A.Head==NULL
B.Head->next==NULL
C.Head->next==Head
D.Head!=NULL
21.每个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（B）存储方式。
A.顺序
B.链接
C.索引
D.散列
22.非空的单向循环链表L的尾结点（由p所指向）满足（D）。
A.p==NULL
B.p->next==NULL
C.p==L
D.p->next==L
23.在双向循环双链表中，删除*p结点需要（B）。
A.p->next->prior=p->prior;p->prior->next=p->next;
B.p->prior->next=p->next;p->next->prior=p->prior;
C.p->prior->next=p;p->prior=p->prior->prior;
D.p->prior=p->next->next;p->next=p->prior->prior;
24.链表所具备的特点是（C）。
A.可以随机访问任一结点
B.占用连续的存储空间
C.插入删除元素的操作不需要移动元素结点
D.可以通过下标对链表进行直接访问
25.带头结点的双向循环链表L为空表的条件是（C）。
A.L==NULL
B.L->next->prior=NULL
C.L->next==L
D.L->prior==NULL
解析：
带头结点的双向循环链表（空表）的判定条件是：头结点的前驱和后继都指向头结点自身。
L 指向头结点（不存储数据）
空表时：L->next == L 且 L->prior == L
26.在一个带头结点的单向链表中，若要在指针q所指结点后插入p指针所指结点，则执行（A）。
A.p->next=q->next; q->next=p;
B.q->next=p->next; p=q;
C.p->next=q->next; p->next=q;
D.q->next=p->next; p->next=q;
27.若某表最常用的操作是在最后一个结点之后插入一个结点，则采用__D___最节省运算时间。
A.单链表
B.给出表头指针的单向循环链表
C.双链表
D.带头结点的双向循环链表
解析：
A. 单链表：只知道表头，找尾需要 O(n) 时间。
B. 给出表头指针的单向循环链表：可通过表头找到尾（尾的 next 是头），但找尾仍需 O(n)（需循环一圈）。
C. 双链表：同样只给头指针，找尾需要 O(n) 遍历。
D. 带头结点的双向循环链表：头结点的 prior 指向尾结点，直接获取尾结点位置，O(1)，在尾后插入新结点只需修改几个指针即可完成。
28.设有两个长度为n的单向链表，结点类型相同，分别是循环链表和非循环链表，则（B）。
A.对于两个链表来说，删除第一个结点的操作，其时间复杂度都是O(1)
B.对于两个链表来说，删除最后一个结点的操作，其时间复杂度都是O(n)
C.循环链表要比非循环链表占用更多的内存空间
D.循环链表与非循环链表占用相同的内存空间
解析：
A. 非循环链表：直接 head = head->next（有头结点时 head->next = head->next->next），O(1)。
单向循环链表删除第一个结点时,需要遍历出尾结点，让它指向新的第一个结点。
B. 非循环链表：需要遍历到最后一个结点的前一个结点（倒数第二个），才能把它的 next 置空，时间复杂度 O(n)
循环链表：同样需要遍历到倒数第二个结点，才能使其 next 指向头结点（单向，不能直接知道前驱）。
→ 时间复杂度也是 O(n)
C. 结点类型相同，存储内容一样（数据域+next指针），区别只是尾结点的 next 指向 NULL 还是指向头。不增加额外内存
D.为什么错？应该是把“相同内存空间”理解成内存单元的重叠或共享，不是指大小一样。
29.单向线性链表的结点包含data域和（A）域。
A.next
B.right
C.left
D.head
30.带头结点的单向链表为空的判断条件是（D）（设头指针为head）。
A.head = =NULL
B.head!=NULL
C.head->next= =head
D.head->next= =NULL
31.当利用大小为N的数组顺序存储一个栈时，假定用top==-1表示栈空，则入栈应该执行（A）语句修改top指针。
A.top++
B.top–
C.top=0
D.！top
32.从顺序栈中删除新元素时，应当（B）。
A.先移动栈顶指针，再存入元素
B.先读取元素，再移动栈顶指针
C.先后次序无关紧要
D.同时进行
33.（C）的一个重要应用是在程序设计中实现递归调用。
A.双向链表
B.循环链表
C.栈
D.队列
34.栈是一种操作受限的线性表，其限制是（A）。
A.仅允许在表的一端进行插入和删除操作
B.仅允许进行插入操作
C.仅允许进行删除操作
D.仅允许在表的一端进行插入，而在另一端进行删除操作
35.表达式3*(x+y)/(2-x)的后缀表达式是（D）。
A.3 x y + 2 * 2 x – /
B.3 x * y + 2 x – /
C.3 x y 2 x * + / –
D.3 x y + * 2 x – /
解析：在后缀表达式中，操作数总在运算符之前，且表达式中无括号和优先级的约束，运算符在表达式中出现的顺序即为表达式的运算顺序，每个运算符和在它之前出现且紧靠它的两个操作数进行运算。
36.当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则入栈应该执行（B）语句修改top指针。
A.top++
B.top–
C.top=0
D.！top
37.在一个栈顶指针为top的链栈中删除一个结点时，用 x保存被删结点的值，则执行（）。
A.x=top;top=top->next;
B.x=top->data;
C.top=top->next; x=top->data;
D.x=top->data; top=top->next;
38.关于单链表实现的链栈，下面说法正确的是（A）。
A.表头为栈顶效率高
B.表尾为栈顶效率高
C.表中为栈顶效率高
D.以上答案均不对
39.表达式8/5+4的后缀表达式是（D）。
A.8 5 4 / +
B.8 5 / + 4
C.8 4 + 5 /
D.8 5 / 4 +
40.栈顶指针通常命名为（B）
A.next
B.top
C.rear
D.front
41.元素4，6，8，10按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的可能输出序列是（D）（进栈出栈可以交替进行）。
A.10，8，4，6
B.10，6，4，8
C.8，4，6，10
D.10，8，6，4
42.一般情况下，将递归算法转换成等价的非递归算法应该设置（A）。
A.栈
B.队列
C.堆栈或队列
D.数组
43.栈的基本运算包括（D）
A.求栈长
B.修改栈元素
C.取栈底元素
D.取栈顶元素
44.若让元素a，b，c依次进栈，则出栈顺序不可能为（C）。
A.c，b，a
B.b，a，c
C.c，a，b
D.a，c，b
45.通常的使用顺序栈或者链栈实现递归算法，下面哪个说法正确（C）。
A.顺序栈效率高
B.链栈效率高
C.顺序栈和链栈性能基本相同
D.视情况而定
解析:
递归算法在非递归实现时，需要自己模拟系统栈，用顺序栈或链栈两种方式都可以。
时间上
顺序栈：数组，随机存取，移动栈顶指针 O(1)
链栈：指针访问，入栈出栈也是 O(1)
指令执行上顺序栈略快一点点（连续内存，cache友好，指针少）
差距很小，尤其在递归深度大的时候顺序栈有时更好。
空间上
顺序栈大小固定（可能溢出或浪费）
链栈动态分配，更灵活
但递归深度已知或可控时顺序栈足够。
常见结论
计算机教材和考题里，当不强调栈空间溢出的极端情况时，认为顺序栈和链栈在实现递归算法时的性能（速度）基本差不多，差异主要在空间管理上。
46.一个栈的进栈序列是10，20，30，40，50，则栈的不可能输出序列是（B）（进栈出栈可以交替进行）。
A.10,20,30,40,50
B.40,30,50,10,20
C.40,50,30,20,10
D.50,40,30,20,10
47.向顺序栈中压入新元素时，应当（A）。
A.先移动栈顶指针，再存入元素
B.先存入元素，再移动栈顶指针
C.先后次序无关紧要
D.同时进行
48.链栈和顺序栈相比，有一个比较明显的优点，即（B）。
A.插入操作更加方便
B.通常不会出现栈满的情况
C.不会出现栈空的情况
D.删除操作更加方便
49.以下数据结构中（D）是线性结构。
A.有向图
B.堆
C.完全二叉树
D.栈
50.表达式a*(b+c)-d的后缀表达式是（B）。
A.abcd*+-
B.abc+*d-
C.abc*++d-
D.-+*abcd
51.在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（C）。
A.top->next=p;
B.p->next=top->next; top->next=p;
C.p->next=top; top=p;
D.p->next=top->next; top=top->next
52.一个队列的入队序列是1，2，3，4。则队列的输出序列是（B）。
A.4，3，2，1
B.1，2，3，4
C.1，4，3，2
D.3，2，4，1
53.判断一个顺序队列sq（最多元素为m）为空的条件是（C）。
A.sq->rear-sq->front==m
B.sq->rear-sq->front-1==m
C.sq->front==sq->rear
D.sq->front==sq->rear+1
54.以下（C）不是队列的基本运算。
A.向队尾插入一个新元素
B.判断一个队列是否为空
C.从队列中删除第i个元素
D.读取队首元素的值
55.假设链队的队首和队尾指针是F和R，那么队空的条件是（）。
A.F==R
B.F！=NULL
C.R=NULL
D.F！=R
【答案】 C 答案应该是A才对（AI的回答也是选A）
56.队列是一种操作受限的线性表，其限制是（D）。
A.仅允许在表的一端进行插入和删除操作
B.仅允许进行插入操作
C.仅允许进行删除操作
D.仅允许在表的一端进行插入，而在另一端进行删除操作
57.顺序队列中，队首元素位置为5，则队首指针位置为（）。
A.3
B.4
C.5
D.6
【答案】 B 答案应该是C对（AI的回答也是选C）
58.（D）的一个重要应用是解决主机和打印机之间速度不匹配的问题。
A.双向链表
B.循环链表
C.栈
D.队列
59.下面关于串的叙述中，正确的是（C）。
A.串其实是字母序列
B.空串是由空格构成的串
C.模式匹配是串的一种重要运算
D.串只能采用顺序存储
解析：
A. 串其实是字母序列 ❌
串是字符序列，不限于字母（可以是数字、符号等），表述片面。
B. 空串是由空格构成的串 ❌
空串长度为 0，不含任何字符（包括空格）。由一个或多个空格字符构成的串是“空格串”，不是空串。
C. 模式匹配是串的一种重要运算 ✅
模式匹配（子串定位）是串处理的核心运算之一，如 Index(S, T)、KMP 算法等。
D. 串只能采用顺序存储 ❌
串既可以顺序存储（定长数组），也可以链式存储（链串），还可以采用堆分配存储。
60.空串与空格串（B）。
A.相同
B.不相同
C.可能相同
D.无法确定
61.下列是”abcd321ABCD”的子串的选项是（A）。
A.”21ABC”
B.”abcABCD”
C.“abcD”
D.“321a”
62.串是什么？（C）。
A.多个字母的序列
B.任意个字母的序列
C.有限个字符的序列
D.无数个字符的序列
63.以下陈述中正确的是（A）。
A.串是一种特殊的线性表
B.串的长度必须大于零
C.串中元素只能是字母
D.空串就是空白串
64.下列说法不正确的是（A）。
A.串不是线性结构
B.串中元素可能是字母、数字或其他字符
C.空串和空白串不一样
D.串的长度可能等于零
65.两个字符串相等的条件是（D）。
A.串的长度相等
B.含有相同的字符集
C.都是非空串
D.两个串的长度相等且对应位置的字符相同
66.以下四个串中最小的是（A）。
A.”ABADF”
B.”ABAFD”
C.”ABADFA”
D.”ABAF”
67.串函数Strcat（a,b）的功能是进行串（D）。
A.比较
B.复制
C.赋值
D.连接
68.字符串处理函数Strcmp（a,b）的功能是进行串（B）。
A.连接
B.比较
C.复制
D.模式匹配
69.设有两个串p和q，其中q是p的子串，q在p中首次出现的位置的算法称为（C）。
A.求子串
B.连接
C.模式匹配
D.求串长
解析：
A. 求子串：是从一个串中提取连续字符组成新串，不涉及查找位置。
B. 连接：是将两个串拼接成一个新串。
C. 模式匹配：是在主串中查找子串首次出现的位置，与题干描述完全一致。
D. 求串长：是返回串中字符的个数。
70.两个字符串相等的条件是（D）。
A.两串的长度相等
B.两串包含的字符相同
C.两串的长度相等，并且两串包含的字符相同
D.两串的长度相等，并且对应位置上的字符相同
71.某串的长度小于一个常数，则采用（B）存储方式最节省空间。
A.链式
B.顺序
C.堆结构
D.无法确定
72.如果进行串的比较，下列哪个串最大？（A）
A.“BEIJING”
B.“BEI”
C.“BEFANG”
D.“BEFI”
73.广义表( f , h , (a ,b, d, c) , d , e ,( (i ,j ) ,k ) )的长度是( A )。
A.6
B.10
C.8
D.4
74.一个非空广义表的表头（D）。
A.不可能是原子
B.只能是子表
C.只能是原子
D.可以是子表或原子
75.下列广义表中的线性表是（C）。
A.E(a,(b,c))
B.E(a,E)
C.E(a,b)
D.E(a,L( ))
解析：线性表的元素必须是同类型且平坦的，不允许嵌套子表。
76.广义表(a,(d,a,b),h,(e,((i,j),k)))深度是( D )。
A.6
B.10
C.8
D.4
77.广义表（a，a，b，d，e，（（i，j），k））的表头是（B）。
A.（a）
B.a
C.a,（a，b）
D.（a，a，b）
78.设有一个广义表A (a)，其表尾为（C）。
A.a
B.(( ))
C.( )
D.(a)
79.深度为5的二叉树至多有（C）个结点。
A.16
B.32
C.31
D.10
80.在一棵二叉树中，若编号为8的结点存在右孩子，则右孩子的顺序编号为（D）。
A.18
B.16
C.15
D.17
81.在二叉树的第4层最多含有（A）个结点。
A.8
B.15
C.16
D.17
82.假定一棵二叉树中，叶子结点数为10，单分支结点数为30，则双分支结点数为（C）。
A.7
B.8
C.9
D.19
解析：叶子结点比双分支结点多一个
83.在一棵二叉树上，第5层的结点数最多为（C）。
A.8
B.15
C.16
D.32
84.一棵高度为4的二叉树，最多含有（B）个结点。
A.8
B.15
C.16
D.17
85.在一棵树中，度为0的结点称作（A）。
A.叶子结点
B.分支结点
C.孩子结点
D.双亲结点
86.树中所有结点的度等于所有结点数加（D）。
A.1
B.0
C.2
D.-1
87.在一棵度具有5层的满二叉树中结点总数为（A）。
A.31
B.32
C.33
D.16
88.二叉树的按层遍历算法需要使用（A）
A.队列
B.栈
C.广义表
D.二维数组
解析：
二叉树的按层遍历（又称广度优先遍历）的基本思想是：
从上到下、从左到右依次访问每个结点。
访问一个结点后，将其左右孩子（如果存在）依次放入等待队列中。
这种“先访问的结点，其孩子也较早被访问”的规律，符合先进先出（FIFO）的原则。
89.对一棵二叉树中顺序编号为i的结点，若它存在左孩子，则左孩子结点的编号为（A）。
A.2i
B.2i+1
C.2i-1
D.i/2
90.权值为{1，2，6，8}的四个结点构成的哈夫曼树的带权路径长度是（D）。
A.18
B.28
C.19
D.29
解析：
带权路径长度=1*3+2*3+6*2+8*1=29
91.利用2、4、5、10这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为（C）。
A.18
B.16
C.38
D.30
解析：
带权路径长度=2*3+4*3+5*2+10*1=38
92.哈夫曼树只有（C ）的结点的二叉树。
A.度为0
B.度为2
C.度为2和度为0
D.度为2或度为0
93.设a，b为一棵二叉树的两个结点，在后续遍历中，a在b前的条件是（）。
A.a在b上方
B.a在b下方
C.a在b左方
D.a在b右方
【答案】 B 答案应该是先C才对（AI的回答也是选C）
94.由六个叶子结点a、b、c、d、e、f构造的哈夫曼树（B）。
A.唯一
B.不唯一
C.不确定
D.以上都不对
解析
哈夫曼树（Huffman Tree）的构造算法，在给定一组权值（叶子结点）后，编码结果（带权路径长度）唯一，但树的结构不一定唯一。
造成不唯一的原因主要有：
权值重复
当存在权值相等的叶子时，合并哪两个结点的选择不唯一，可能导致不同的树形结构。
合并顺序
即使权值都不相等，在构造过程中选择哪两个最小权值结点合并的结果是唯一的，但如果权值有相等情况，合并顺序可调整，树形结构就可能不同。
新结点权值与原有结点权值相等的处理
当新生成的父结点权值与某个叶子结点权值相等时，可以按不同次序合并，也会影响形状。
因此，哈夫曼树的形状不一定唯一，但最小带权路径长度（WPL）是唯一确定的。
95.设一棵哈夫曼树有20个叶子结点，该树共有（A）个非叶子结点。
A.19
B.20
C.39
D.40
96.无向图的邻接矩阵是一个（A）。
A.对称矩阵
B.零矩阵
C.上三角矩阵
D.对角矩阵
解析：
无向图的邻接矩阵表示顶点之间的相邻关系。
如果图中存在从顶点 i 到 j 的边，那么必然也存在从 j 到 i 的边，因为边是无向的。
因此，矩阵中满足 A[i][j] = A[j][i]（对于无权图，值为 1 或 0；对于有权图，值为权值或 0/∞）。
所以，无向图的邻接矩阵必定是 对称矩阵。
97.在无向图中定义顶点vi与vj之间的路径为从vi到vj的一个（A）。
A.顶点序列
B.边序列
C.权值总和
D.边的条数
解析
在图论中，路径（path）的定义为：
从顶点 vivi 到顶点 vjvj 的顶点序列 (vi,vi1,vi2,…,vj)(vi,vi1,vi2,…,vj)，其中序列中相邻的两个顶点之间有边相连。
因此：
路径的核心是顶点依次经过的顺序（顶点序列）。
边序列也可以表示路径，但严格定义更常使用顶点序列。
98.在一个图G中，所有顶点的度数之和等于所有边数之和的（C）倍。
A.1/2
B.1
C.2
D.4
解析：想象一个三角形，顶点度数之和为6（每个顶点度数为2），所有边数之和为3，6是3的2倍。
99.一个具有n个顶点的有向完全图包含（A）条边。
A.n（n-1）
B.n（n+1）
C.n（n-1）/2
D.n（n+1）/2
解析:
有向完全图的定义：任意两个顶点之间都有两条方向相反的有向边。
对于 n 个顶点的有向完全图：
从任意一个顶点出发，可以指向其余 n-1 个顶点，所以每个顶点有 n-1 条出边。
这样的出边总数为：n × (n-1)
由于每条有向边都是独立的，不需要除以 2。
因此，边数为：n(n−1)
另：无向完全图的定义：在一个无向图中，如果任意两个不同的顶点之间都有且仅有一条边，则称该图为无向完全图
100.在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为（B）。
A.k
B.k+1
C.k+2
D.2k
解析
在无向图中：
路径长度 k 通常定义为路径上 边的数目。
一条由 k 条边组成的路径，经过的顶点数为 k+1（包括起点和终点）。
101.邻接表是图的一种（B）。
A.顺序存储结构
B.链式存储结构
C.索引存储结构
D.散列存储结构
解析:
邻接表（Adjacency List） 是图的一种链式存储结构。
它结合了顺序存储（顶点表用数组存储）和链式存储（每个顶点的邻接点用链表存储）的特点，但从整体结构分类上，属于链式存储结构。
存储方式说明
顶点表：使用一维数组顺序存储所有顶点，便于快速访问。
边表（邻接表）：每个顶点对应一个单链表，存储与该顶点相邻的所有顶点（及其相关信息，如权值等）。
这种结构有利于稀疏图的存储，可以避免邻接矩阵中大量零元素的浪费。
102.在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。
A.入边
B.出边
C.入边和出边
D.不是入边也不是出边
解析
在有向图的邻接表中，对于每个顶点 vv：
它的邻接表（边表）中存放的是以 vv 为起点的所有弧（有向边），即 出边 所指向的邻接点。
因此，每个顶点邻接表链接着该顶点所有出边的邻接点。
如果需要记录入边，通常使用逆邻接表，或在十字链表、邻接多重表等更复杂的结构中同时存储入边和出边。
103.对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标可能为（D）。
A.1、2、3
B.9、5、2、3
C.9、5、3
D.9、4、2、3
解析：
如果下标从0到17，则第一个中间位置的下标为(0+17)/2=8,选项中无，所以下标应从1到18.
第一步：mid=(1+18)/2=9, A[3]在A[9]左侧。
第二步：high=mid-1=9-1=8，所以，mid=(1+8)/2=4，A[3]在A[4]左侧。
第三步：high=mid-1=4-1=3，所以，mid=(1+3)/2=2，A[3]在A[2]右侧。
第四步：low=mid+1=2+1=3，所以，mid=(3+3)/2=3，正是A[3]所在位置。
104.已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（C）次。
A.3
B.4
C.5
D.6
105.有一个长度为12的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。
A.37/12
B.39/12
C.41/12
D.35/12
【答案】 A
解析：画出折半查找的判定树如下（序号从1到12）：
平均比较次数为：(1*1+2*2+4*3+5*4)/12=37/12
106.有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（A）。
A.29/10
B.31/10
C.26/10
D.29/9
解析：画出折半查找的判定树如下（序号从1到10）：
平均比较次数为：(1*1+2*2+4*3+3*4)/10=29/10
107.对线性表进行二分查找时，要求线性表必须（C）。
A.以顺序存储方式
B.以链接存储方式
C.以顺序存储方式，且数据元素有序
D.以链接存储方式，且数据元素有序
108.对于顺序存储的有序表{5，12，20，26，37，42，46，50，64}，若采用折半查找，则查找元素26的比较次数是（）。
A.2
B.3
C.4
D.5
【答案】 B 答案应该是选C才对
解析：用不画判定树的形式分析，设下标为从1到9，26为第4号元素。
第一步：mid=(1+9)/2=5,4在5左边
第二步：high=mid-1=5-1=4，mid=(1+4)/2=2,4在2右边
第三步：low=mid+1=2+1=3，mid=(3+4)/2=3, 4在3右边
第四步：low=mid+1=3+1=4，mid=(4+4)/2=4,4正好是26所在位置。
二叉判定树如下：
109.一组记录的关键字序列为（80，57，41，39，46，47），利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（C）。
A.39，47，46，80，41，57
B.41，39，46，47，57，80
C.39，46，41，57，80，47
D.39，80，46，47，41，57
解析：初始堆如下：
110.每次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（B）。
A.插入排序
B.快速排序
C.堆排序
D.归并排序
111.设有2000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（D）排序法。
A.快速排序
B.基数排序
C.冒泡排序
D.堆排序
解析：
A. 快速排序
需要完全排序整个序列，平均时间复杂度 O(n log n) ≈ 2000 × 11 ≈ 22000 次比较，且做完才能得到前 10 个，效率不高（做了很多无用功）。
B. 基数排序
适用于整数且需要完全排序，对于取前 10 大仍需全排（或至少进行若干趟，但未必能提前得到前 10 个），空间开销大，不如堆直接高效。
C. 冒泡排序
做 10 趟冒泡，每趟比较 n-1, n-2, …, n-10 次，比较总数 ≈ 10 × 2000 = 20000 次，比堆排序 O(n + k log n) 差。
D. 堆排序（部分堆排序，取 Top K）
方法一：建一个大根堆（O(n) ≈ 2000），然后取出堆顶（最大），重新调整，重复 10 次（每次调整 O(log n) ≈ 11）。
112.一组记录的关键字序列为（26，59，36，18，20，25），利用堆排序的方法建立的初始小根堆为（B）。
A.18，20，36，59，26，25
B.18，20，25，59，26，36
C.26，18，59，20，36，25
D.26，59，36，18，20，25
解析：
18比其左右孩子20、25都小；
20比其左右孩子59、26都小；
25比其右孩子36小；
113.对数据元素序列（49，72，68，13，38，50，97，27）进行排序，前三趟排序结果时的结果依次为第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38，50，97，27；第三趟：13，49，68，72，38，50，97，27。该排序采用的方法是（A）。
A.插入排序法
B.选择排序法
C.冒泡排序法
D.堆排序法
解析：
A. 插入排序 ：符合“依次将元素插入已排序部分”的过程。
114.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是（B）。
A.堆排序> 快速排序> 归并排序
B.堆排序< 快速排序< 归并排序
C.堆排序< 归并排序< 快速排序
D.堆排序> 归并排序> 快速排序
解析
题干比较的是辅助空间（额外内存）的大小，不是时间复杂度。
堆排序
原地排序，只需要 O(1) 的辅助空间（用于交换、存储临时变量）。
快速排序
虽然是在原数组上操作，但递归调用需要栈空间。
平均情况下递归深度 O(log n)，因此辅助空间为 O(log n)；最坏情况可能 O(n)，但平均一般按 O(log n) 比较。
归并排序
非原地排序，合并时需要额外的数组存放归并结果，无论递归还是迭代实现，典型辅助空间为 O(n)。
115.从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（A）。
A.插入排序
B.交换排序
C.选择排序
D.归并排序
116.依次将每两个相邻的有序表合并成一个有序表的排序方法称为（D）。
A.插入排序
B.交换排序
C.选择排序
D.归并排序
117.一组记录的关键字序列为（60，47，80，57，39，41，46，30），利用归并排序的方法,第一趟归并后的结果为（D）。
A.47，57，60，80，30，39，41，46
B.30，39，41，46，47，57，60，80
C.30，47，80，57，39，41，46，60
D.47，60，57，80，39，41，30，46
118.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（D）。
A.2n-1
B.n-1
C.2n
D.n
解析：
两个各有 n 个元素的有序表归并，最少比较次数出现在最好情况下：
其中一个表中的所有元素都小于另一个表中的第一个元素。
举例（n=3）
A = [1, 2, 3]，B = [4, 5, 6]
归并过程：
1. 比较 1 与 4 → 取 1（1 次比较）
2. 比较 2 与 4 → 取 2（2 次比较）
3. 比较 3 与 4 → 取 3（3 次比较）
此时 A 空，B 剩余元素 [4, 5, 6] 直接复制，无需再比较。
总比较次数 = n=3
公式：最少比较次数 = n
因为需要将第一个表的 n 个元素逐一与第二个表的第一个元素比较，才能取出第一个表的所有元素（并使该表先空）。
119.已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列从小到大排序，经过一趟冒泡排序后的序列为（B）。
A.16，28，34，54，73，62，60，26，43，95
B.28，16，34，54，62，73，60，26，43，95
C.16，28，34，54，62，60，73，26，43，95
D.28，16，34，54，62，60，73，26，43，95
