专栏文章

【笔记】一些数据结构基础习题

断断清秋
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min8otd7
此快照首次捕获于
2025/12/01 22:23
3 个月前
此快照最后确认于
2025/12/01 22:23
3 个月前
查看原文
1、数据结构中有顺序存储结构、链式存储结构、索引存储结构、哈希存储结构这四种常用的存储结构类型。
Hint
代表数据结构依次为数组、链表、B+ 树、哈希表。
2、在一个长度为 n 的带头结点的单链表 L 中，设有尾指针 r，则执行（C）操作与链表的表长有关。
A. 删除第一个元素
B. 在第一个元素前插入新元素
C. 删除最后一个元素
D. 在最后一个元素后插入新元素
Hint
C 操作意味着需要找到 r 的前驱结点，对于单链表需要从表头开始遍历，复杂度 O(n)O(n)。
3、已知循环队列存储在一维数组 a[0..n-1] 中，且队列非空时，front 和 rear 分别指向队头元素和队尾元素。若初始时队列为空，且要求第一个进入队列的元素存放在 a[0] 中，则初始时 front 和 rear 的值分别为（B）。
A. 0,00,0
B. 0,n−10,n-1
C. n−1,0n-1,0
D. n−1,n−1n-1,n-1
Hint
每次入队时，尾指针先向后移动一位，然后将元素入队。本题中第一个元素入队时，尾指针先从 n−1n-1 移动到 00，然后元素入队，此时头尾指针都指向 00，符合题意。
4、判断一个顺序栈 st（元素个数最多为 MaxSize）为空的条件可设置为（D）。
A. st->top==MaxSize/2
B. st->top!=MaxSize/2
C. st->top!=MaxSize-1
D. st->top==MaxSize-1
Hint
这是一个向下生长的栈，栈底在地址最高处，入栈操作是地址向下移动，故栈空时 top 指针位于最高处，选 D。
5、若一个栈用数组 data[1..n] 存储，初始栈顶指针 top 为 n，则以下元素 x 进栈的操作正确的是（D）。
A. top++; data[top]=x;
B. data[top]=x;top++;
C. top--; data[top]=x
D. data[top]=x; top--;
Hint
初始时栈为空，元素进栈存在 n 位，栈顶指针向下一位，选 D。
6、若栈 S1 中保存整数，栈 S2 中保存运算符，函数 F() 依次执行下述各步操作：
1、从 S1 中依次弹出两个操作数a和b。
2、从 S2 中弹出一个运算符op。
3、执行相应的运算b op a。
4、将运算结构压入栈S1中。
假设 S1 中的操作数依次是 5、8、3、2，其中，2 在栈顶。S2 中的运算符依次是 *、-、+，其中+位于栈顶。调用 3 次 F() 后，S1 栈顶保存的值是（C）。
A. 20
B. -15
C. 15
D. -20
Hint
注意操作顺序是 b op a。
7、设循环队列的存储空间为 a[0..20]，且当前队头指针 f（f 指向队首元素前一个位置）和队尾指针 r（r 指向队尾元素）分别为 8 和 3，则该队列中元素个数为（B）。
A. 17
B. 16
C. 6
D. 5
Hint
设环形队列中数组的下标是 0∼n−10 \sim n-1，其队头指针为 ff（指向队头元素的前一个位置），队尾指针为 rr（指向队尾元素），则其元素个数为 (r−f+n)mod  n(r-f+n) \mod n。
对于本题，元素数量为 (3−8+21)mod  21=16(3-8+21) \mod 21 = 16。
直接数也行。
8、用循环单链表表示队列，下列说法中正确的是（B）。
A. 无论如何只能使入队方便，无法实现出队方便
B. 可设一个尾指针使入队、出队都方便
C. 必须设头尾指针才能使入队、出队都方便
D. 可设一个头指针使入队、出队都方便
Hint
入队操作：只需在尾指针之后添加新节点，并更新尾指针。
出队操作：头节点是尾指针的 next 节点，因此可以通过尾指针直接访问头节点并进行出队操作。
9、设目标串 ss 为 "abcaabbcaaabababaabca"，模式串 tt 为 "babab"，则该模式串的 nextval 数组为（[−1,0,−1,0,−1][-1,0,-1,0,-1]）；第一趟匹配从 i=0,j=0i=0,j=0 开始，第二趟匹配从 i=0,j=−1i=0,j=−1 开始，则第 5 趟匹配从 i=(2)，j=(0)i=(2)，j=(0) 开始。
Hint
先计算 next 数组。next[j]next[j] 表示第 0…j−10 \ldots j-1 个字符中前缀和后缀的最长公共长度。
可以求出 next[0…4]=[−1,0,0,1,2]next[0\ldots4]=[-1,0,0,1,2]。
再求 nextval 数组。当 tj=tnext[j]t_j=t_{next[j]} 时，nextval[j]=nextval[next[j]]nextval[j]=nextval[next[j]]；反之，则 nextval[j]=next[j]nextval[j]=next[j]。
可以求出 nextval[0…4]=[−1,0,−1,0,−1]nextval[0\ldots4]=[-1,0,-1,0,-1]。
然后模拟 KMP 过程。若 j=−1j=-1 或 si=tjs_i=t_j，则 i←i+1,j←j+1i \leftarrow i+1,j \leftarrow j+1；否则 j←nextval[j]j \leftarrow nextval[j]。
前 5 次匹配依次是 i=0,j=0⇒i=0,j=−1⇒i=1,j=0⇒i=2,j=1⇒i=2,j=0i=0,j=0 \Rightarrow i=0,j=-1 \Rightarrow i=1,j=0 \Rightarrow i=2,j=1 \Rightarrow i=2,j=0。
10、假设 L=(a1,a2,...,an)L=(a_1,a_2,...,a_n) 是一个线性表，若采用顺序存储结构，则在等概率的前提下，插入一个元素需要平均移动的元素个数是（n2\dfrac{n}{2}）；若元素插在 aia_i 与 ai+1a_{i+1} 之间 (0≤i≤n−1)(0≤i≤n−1) 的概率为 2(n−i)n(n+1)\frac{2(n−i)}{n(n+1)}，则插入一个元素需要移动元素的个数是（2n+13\dfrac{2n+1}{3}）
Hint
nn 个元素的线性表有 n+1n+1 个插入位置，插在 aia_i 和 ai+1a_{i+1} 之间要移动 n−in-i 个元素。
11、高度为 h(h>0)h(h>0) 的满二叉树对应的森林由（D）棵树构成。
A. 11
B. log⁡2h\log_2 h
C. h2\dfrac{h}{2}
D. hh
Hint
森林转二叉树的规则：森林中第一棵树的根作为二叉树的根，第二棵树的根作为第一棵树根的“右孩子”，第三棵树的根作为第二棵树根的“右孩子”，依此类推。
逆向思考（二叉树转森林）：二叉树的根结点是森林中第一棵树的根；二叉树根结点的右指针链（一直往右走的路径）上的每一个结点，依次是森林中后续每一棵树的根。
12、有一棵 3 次树，其中 n3=2,n2=2,n1=1n_3=2,n_2=2,n_1=1，当该树采用孩子兄弟链存储结构时，其中非空指针域数占总指针域数的比例约为（B）。
A. 10%
B. 45%
C. 70%
D. 90%
Hint
孩子兄弟链存储结构：每个节点记录它的孩子和旁边的一个兄弟。（本质上是把树转化为二叉树）
本题中，可以求出 n0=7n_0=7，共有 12 个节点，11 条边，故所求值等于 1124\dfrac{11}{24}。
13、按照二叉树的定义，具有 4 个结点的二叉树，有（A）种形态。
A. 14
B. 12
C. 10
D. 16
Hint
就是 Catlan 数 C4=14C_4=14。
14、一棵 124 个叶子结点的完全二叉树，最多有（B）个结点。
A. 247
B. 248
C. 249
D. 250
Hint
二叉树中有 n0=n2+1n_0=n_2+1，故 n2=123n_2=123。
又 n1=0n_1=0 或 11，取 n1=1n_1=1，则总结点数最大，为 248248。
15、如果一棵有序树 TT 转换为二叉树 BB，那么 TT 中结点的先根遍历序列就是 BB 中结点的（先序）序列，TT 中结点的后根遍历序列就是 B 中结点的（中序）序列，TT 中结点的层次遍历序列就是 BB 中结点的（无法确定）序列。
Hint
把有序树 TT 转换为二叉树 BB 的方法：BB 中的每个结点的左孩子是 TT 中该结点的第一个孩子，右孩子是 TT 中该结点的第一个兄弟。
TT 的先根遍历为：根 → \rightarrow 子树 1 →\rightarrow 子树 2 …\ldots
转换为 BB 就是：根 → \rightarrow 左孩子 →\rightarrow 右孩子 …\ldots，即先序遍历。
TT 的后根遍历为：子树 1 → \rightarrow 子树 2 →\rightarrow 根 …\ldots
转换为 BB 就是：左孩子 → \rightarrow 根，即中序遍历。（注意，BB 中根没有右孩子）
16、一棵含有 nn 个结点的 k(k≥2)k(k≥2) 次树，可能达到的最大高度为 n−1n-1，最小高度为 log⁡k(n(k−1)+1)\log_k (n(k-1)+1)。
Hint
树退化成链的时候有最大高度。
17、线索二叉树中，先序/中序/后序线索树指：对于树中的每个结点，若其左孩子为空则令其指向树的先序/中序/后序遍历序列中该结点的前驱，若其右孩子为空则令其指向树的先序/中序/后序遍历序列中该结点的后继。
Hint
nn 个点的线索二叉树有 2n2n 条边（可以指向 NULL）。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...