【填空题】考研数据结构填空题整理
数据结构填空题
题源来⾃《算法与数据结构考研试题精析》
⼀、概论
1. 在数据结构中，数据的逻辑结构分线性结构和线性结构。
2. 链接存储的特点是利⽤指针来表⽰数据元之间的逻辑关系。
3. 数据的物理结构包括数据元素的表⽰和数据元素间关系的表⽰。
4. 对于给定的n个元素，可以构造出的逻辑结构有集合、线性结构、树形结构、图结构四种。
5. 数据结构由数据的逻辑结构、存储结构和运算三部分组成。
完全二叉树算法
6. ⼀个数据结构在计算机中的表⽰称为存储结构。
7. 数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。
8. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互关系，并对与这种结构定义相应的操作，设计出相应的算法。
9. 抽象数据类型的定义仅取决于它的⼀组逻辑特性，⽽与在计算机内部如若表⽰和实现⽆关，即不论其内部结构如何变化，只要它的
数学特性不变，都不影响其外部使⽤。
⼆、线性表
1. 在单链表中设置头结点的作⽤是有头结点后，插⼊元素和删除元素的算法统⼀了，不再需要判断是否在第⼀个元素之前插⼊和删除第
⼀个元素。
2. 根据线性表的链式存储结构中每⼀个结点包含的指针个数，将线性链表分成单链表和双链表；⽽⼜根据指针的连接⽅式，链表⼜可
分成链表和静态链表。
3. 链接存储的特点是利⽤指针来表⽰数据元素之间的逻辑关系。
4. 顺序存储结构是通过结点物理上相邻表⽰元素之间的关系的；链式存储结构是通过结点指针表⽰元素之间的关系的。
5. 循环单链表的最⼤优点是：从任⼀结点出发都可访问到链表中每⼀个元素。
6. 指针p指向单链表的某个结点，在指针p所指结点之前插⼊s所指结点。操作序列： s->next=p->next;p->next=s;p->data<-->s->data 。这
⾥⽤交换两结点数据的办法达到在结点前插⼊结点的⽬的。
7. 判断带头结点的双循环链表L仅有⼀个元素结点的条件是 L->next->next=L&&L->prior->prior==L&&L->next!=L 。
8. 带头结点的双循环链表L为空表的条件是： L->next==L&&L->prior=L 。
9. 判断带头结点的单循环链表L仅有⼀个元素结点的条件是 L->next->next=L&& L-next!=L 。
三、栈和队列
1. 在栈的ADT定义中，除初始化操作外，其他基本操作的初始条件都要求栈已存在。
2. 栈是操作受限的线性表，其运算遵循的原则后进先出。
3. 堆栈是⼀种操作受限的线性表，它只能在线性表的⼀端进⾏插⼊和删除操作，对栈的访问是按照后进先出的原则进⾏的。
4. 向栈中压⼊元素的操作是先进栈，后退栈。
5. 当两个栈共享⼀存储区时，栈利⽤⼀维数组stack（1，n）表⽰，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为 0 ，栈2空
时，top[2]为 n+1 ，栈满时为 top[1]+1=top[2] 。
6. 顺序栈S的GetTop(s,e)操作是⽤e返回s的栈顶元素。则操作正确的是 e = *(s.top)。
7. 栈是⼀种操作受限的线性表，它只能在线性表的栈顶进⾏操作和删除。
8. 判断顺序栈是否为空的条件是 s->top == -1 ；判断顺序栈是否为满的条件是 s.top == maxsize -1 。
9. 两个栈共享空间时栈满的条件两栈顶指针相邻。
10. 为了增加内存空间的利⽤率和减少溢出的可能性，由两个栈共享⼀⽚连续的空间时，应将两栈的栈
底分别设在内存空间的两端，这样
只有当两栈顶指针相邻时才产⽣溢出。
11. 多个栈共存时，最好⽤链式存储结构作为存储结构。
12. 队列只允许在表的⼀端插⼊，插⼊的⼀端叫队尾，删除的⼀端叫队头。
13. 顺序栈⽤]存储数据，栈顶指针是top，则值为x的元素⼊栈的操作是 if(top!=n) data[++top]=x;
14. 在按算符优先法求解表达式3-1+5x2时，最先执⾏的运算是减法运算，最后执⾏的运算是加法运算
15. 循环队列是队列的⼀种顺序存储结构。
16. 循环队列的引⼊，⽬的是为了克服假溢出时⼤量移动数据元素。
17. 在循环队列中，队列长度为n，存储位置从0到n-1编号，以rear指⽰实际的队尾元素，现要在此队列中插⼊⼀个新元素，新元素的位置
是 rear=(rear+1)%n 。
18. 已知链队列的头尾指针分别是f和r，则将值x⼊队的操作序列是 new(s);s->data=x;s->next=r->next;r->next=s;r=s;
19. 区分循环队列的满与空，只有两种⽅法，它们是牺牲⼀个存储单元和设标记。
20. 循环队列⽤数组-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是 (rear-front+m)%m 。
21. ⽤循环链表表⽰的队列长度为n，若只设头指针，则出队和⼊队的时间复杂度分别是 O(1) 和 O(n) ；若只设尾指针，则出队和⼊队的时
间复杂度分别是 O(1) 和 O(1) 。
22. 设循环队列容量为Q，当rear<front时，队列长度为 (rear-front+Q)%Q 。
23. 已知⼀循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是 front==(rear+1)%(n-
m+1) 。
四、树和⼆叉树
1. 树在计算机内的表⽰⽅式有双亲链表表⽰法，孩⼦链表表⽰法，孩⼦兄弟表⽰法。
2. 在⼆叉树中，指针p所指结点为叶⼦结点的条件是 p->lchild==null && p->rchlid=-null 。
3. 已知完全⼆⼜树的第8层（根结点的层次为0）有240个结点，则整个完全⼆叉树的叶⼦结点数是 248 。
4. ⼀个⽆序的元素序列可以通过构造⼀棵⼆叉排序树⽽变成⼀个有序的元素序列 (√)
5. 在顺序存储的⼆⼜树中，编号为 i 和 j 的两个结点处在同⼀层的条件是⽤顺序存储结构存储⼆叉树时，要按完全⼆⼜树的形式存储，⾮
完全⼆叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s和t，则结点i和j在同⼀层上的条件是log2sHlogzt]。。
6. 若按层次顺序将⼀棵有n个结点的完全⼆叉树的所有结点从1到n编号，那么结点 i 没有右兄弟的条件为 2*i+1>n 。
7. 对于⼀个具有n个结点的⼆叉树，当它为⼀棵完全⼆叉树时具有最⼩⾼度，当它为⼀棵只有⼀个叶⼦结点的⼆叉树时，具有最⼤⾼
度。
8. 先序遍历森林时，⾸先访问森林中第⼀棵树的根结点。
9. 前序遍历树林正好等同于按前序遍历对应的⼆叉树，后序遍历树林正好等同于按中序遍历对应的⼆叉树。
10. ⼆⼜树的先序序列和中序序列相同的条件是任何结点⾄多只有右⼦⼥的⼆叉树。
11. 在⼀棵存储结构为三叉链表的⼆叉树中，若有⼀个结点是它的双亲的左⼦⼥，且它的双亲有右⼦⼥，则这个结点在后序遍历中的后继
结点是双亲的右⼦树中最左下的叶⼦结点。
12. 线索⼆元树的左线索指向其前驱，右线索指向其后继。
13. 在线索⼆叉树中，T所指结点没有左⼦树的充要条件是 T->ltag =1 。
14. 哈夫曼树是带权路径长度最⼩的⼆叉树，⼜称最优⼆叉树。
15. 中缀式a+b3+4（c-d）对应的前缀式为++a b34-cd ，若a=1，b=2，c=3d-4，则后缀式 db/cc a-b+
的运算结果为18 。
16. 已知完全⼆⼜树的第8层（根结点的层次为0）有240个结点，则整个完全⼆⼜树的叶⼦结点数是 248 。
17. 深度为H的完全⼆叉树⾄少有 2^(H-1) 个结点；⾄多有 2^H-1 个结点；H和结点总数N之间的关系是 H=[log2N]+1 。
18. 完全⼆叉树结点的平衡因⼦取值只可能为 1，0，-1 。
19. 完全⼆叉树的存储结构通常采⽤顺序存储结构。(T)
20. 在有N个元素的最⼤堆中，随机访问任意键值的操作可以在O(logN)时间完成。(F)
21. 哈夫曼编码是⼀种最优的前缀码。对⼀个给定的字符集及其字符频率，其哈夫曼编码不⼀定是唯⼀的，但是每个字符的哈夫曼码的长
度⼀定是唯⼀的。(F)
五、图
1. 若⼀个具有n个顶点、e条边的⽆向图是⼀个森林，则该森林中必有 n-e 棵树。
2. 完全图是任意两个顶点之间存在边；连通图是任意两个顶点之间都有路径。
3. 有向树定义：⼀个顶点的⼊度为0，其余顶点的⼊度均为 1 的有向图。
4. 在数据结构中，线性结构、树形结构和图形结构数据元素之间分别存在⼀对⼀、⼀对多和多对多的联系。
5. n个顶点的连通图⾄少有 n-1 条边。n个顶点的强连通图最少有 n 条边。
6. 在⽆向图中，调⽤遍历函数(BFS 或 DFS)的次数为连通分量的个数。
7. A^3【m】[n]表⽰从顶点 m 到顶点 n 长度为 3 的路径⼀共有 A^3【m】[n]条
8. 有向图G的强连通分量是指有向图的极⼤强连通⼦图。
9. n个顶点的⽆向连通图的连通分量个数为 1 个。
10. n个顶点的连通⽆向图，其边的条数⾄少为 n-1 。
11. 对于⼀个具有n个顶点的⽆向连通图，它包含的连通分量的个数为 1 个。
12. 如果具有n个顶点的图是⼀个环，则它有 n 棵⽣成树。
13. 最⼩⽣成树不唯⼀。当带权⽆向连通图G 的各边权值不等时或 G只有结点数减1条边时，MST唯⼀。
14. Prim算法求最⼩⽣成树的时间复杂度是 O(V^2) 。
15. Kruskal算法求最⼩⽣成树的时间复杂度是 O(E*logE) ，所以更适合⽤于稀疏图。
16. 若⽆向图满⾜ n个顶点n-1条边的⽆向连通图，则该图是树。
17. n个顶点的⽆向图的邻接矩阵⾄少有 0 个⾮零元素；n个顶点的有向图是强连通图⾄少有 n 条边。
18. N个顶点的连通图⽤邻接矩阵表⽰时，该矩阵⾄少有 2(N-1) 个⾮零元素。
19. 邻接矩阵法的⼴度优先⽣成树及深度优先⽣成树唯⼀，邻接表法的不唯⼀。
20. ⽆向图G有16条边，有3个4度顶点，4个3度顶点，其余顶点的度均⼩于3，则图G⾄少有 11 个顶点。
21. 已知⼀个图的邻接矩阵表⽰，删除所有从第i个结点出发的边的⽅法是将第i个⾮零元素都变为零元素。。
22. 在⼀个⽆向图的的邻接表中，若表结点的个数是m，则图中边的条数是 m/2 条。
23. 图的多重邻接表表⽰法中，表中结点的数⽬是图中边的边数。 (√)
24. 遍历图的过程实质上是查顶点的邻接点的过程，breath-first search遍历图的时间复杂度 O(n+e) ；depth-first search遍历图的时间复
杂度 O(n+e) ，两者不同之处在于访问顶点的顺序不同，反映在数据结构上的差别是队列和栈。
25. 为了实现图的⼴度优先搜索，除了⼀个标志数组标志已访问的图的结点外，还需队列以存放被访问的结点以实现遍历。
26.
27. Dikstar算法是按距离源点路径的长度⼩的次序产⽣⼀点到其余各定点最短路径的算法。
28. 在拓扑分类中，拓扑序列的最后⼀个顶点必定是的顶点出度为0
29. 拓扑排序是按AOE⽹中每个结点事件的最早事件对结点的进⾏排序。(×)
30. 若⽹中有⼏条关键路径，提⾼⼀条关键路径上的活动速度，不能导致整个⼯程缩短⼯期。(×)
31. AOV⽹中，结点表⽰活动，边表⽰活动间的优先关系。AOE⽹中，结点表⽰事件，边表⽰活动。
32. AOE⽹中，完成⼯程的最短时间是从源点到汇点的最短路径的长度。
33. 在AOE（Activity On Edge）⽹中，从源点到汇点路径上各个活动的时间总和最长路径称为关键路径。
34. AOE-⽹⼯程⼯期为关键活动上的权之和。(T) ⼯期为起点到终点的最⼤路径长度。
35. 在AOV⽹中，存在环意味着某项活动以⾃⼰为先决条件，这是荒谬的；对程序的数据流图来说，它表明存在死循环。
36. 当⼀个AOV⽹⽤邻接表表⽰时，可按下列⽅法进⾏拓扑排序。
（1）查邻接表中⼊度为零的顶点，并进；
（2）若栈不空，则①输出栈顶元素巧，并退栈；②查i的直接后继k，对以⼊度处理，处理⽅法是 Vk⼊度减1，，若⼊度为零，则进栈；
（3）若栈空时，输出顶点数⼩于图的顶点数，说明有环，否则拓扑排序完成。
六、数组
1. 对特殊矩阵压缩可以降低运算的复杂度。 (√)
2. 稀疏矩阵⼀般的压缩存储⽅法主要有两种，即三元组存储和⼗字链表。
七、查
1. 散列法存储的思想是由关键字值决定数据的存储地址。(×)
2. 在哈希查⽅法中，要解决两⽅⾯的问题，它们分别是哈希函数的选择及冲突的解决。
3. 在散列表中，评判⼀个散列函数优劣的两个主要条件是计算简单和散列之后得到的元素分布均匀。
4. ⼀般线性表顺序查，查成功的平均查长度为 (n+1)/2 ，查失败的平均查长度为 n+1 。
5. 有序线性表顺序查，查失败时不⼀定要遍历整个线性表，查成功的平均查长度也为 (n+1)/2 ，但查失败的平均查长度为
n/2+n/n+(n+1) 。
6. 采⽤分块查时，数组的组织⽅式为数据分成若⼲块，每块内数据不必有序，但块间必须有序，每块内最⼤的数据组成索引块。
7. 对有65025个元素的有序顺序表建⽴索引顺序结构，在最好情况下查到表中已有元素最多需要执⾏ (16) 次关键字⽐较。解析：每个
索引块⼤⼩为 (根号下65025) = 255，块间与块内均使⽤折半查 log255+1 = 16次，⽐较次数=块间+块内。若使⽤顺序查，则进⾏255+1 = 256次。
⼋、算法填空
斐波那契数列递归与⾮递归实现
//递归实现
int Fib(int n){
if(n==0)
return 0;
else if(n==1)
return 1;
else
return Fib(n-1) + Fib(n-2);
}
//⾮递归实现
int Fib(int n){
if(n==0)
return 0;
else if(n==1)
return 1;
int a = 0;
int b = 1;
for (int i = 1; i < n; i++){
int temp = a;
a = b;
b = temp + a;
}
return b;
}
中序遍历⾮递归算法
void InOrder2(BiTree T){
InitStack(S);
BiTree p = T;
while(p ||!isEmpty(S)){
if(p){
Push(S,p);
p = p->lchild;
}
else
{
Pop(S,p);
visit(p);
p=p->rchild;
}
}
}
层次遍历
void levelOrder(BiTree T){
InitQueue(Q);
BiTree p;
EnQueue(Q,T);
while(!isEmpty(Q)){
DeQueue(Q,p);
visit(p);
if(p->lchild != NULL)
EnQueue(Q,P->lchild);
if(p->rchild!=NULL)
EnQueue(Q,p->rchild);
}
}
线索⼆叉树
线索⼆叉树结点结构
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild.*rchild;
int ltag,rtag;
}ThreadNode,*ThreadTree;
中序线索⼆叉树线索化
void InThread(ThreadTree &p,ThreadTree &pre){    if(p!=NULL){
InThread(p->lchild,pre);
if(p->lchild == NULL){
p->lchild = pre;
p->ltag = 1;
}
if(pre!=NULL && p->rchild == NULL){
p->rchild = p;
p->rtag = 1;
}
pre = p;
InThread(p->rchild,pre);
}
}
折半查
int Binary_Search(SeqList L, ElemType key){    int low = 0, high = L.TableLen-1,mid;
while(low<=high){
mid = (low+high)/2;
if(L.elel[mid] == key)
return mid;
else if(L.elem[mid]>key)
high = mid-1;
else
low = mid+1;
}
return -1;
}
⼴度优先搜索
bool visited[MAX_TREE_SIZE];
void BFSTraverse(Graph G){
for(int i=0;i<G.vexnum;i++)
visited[i] = FALSE;
InitQueue(Q);
for(int i;i<G.vexnum;i++)
BFS(G,i);

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。