20230506数据结构（本）试卷-04
关注公众号【飞鸟搜题】，回复【试题】获取试卷答案
文档说明:本人针对该科精心汇总了历年题库及答案，形成一个完整的题库，并且每年都在更新。该题库对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。做考题时，利用本文档中的查找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。本文库还有期末考核试题、其他网核及教学考一体化、一网一平台复习试题与答案，敬请查看。
课程题目试题是随机的，请按题目关键词查找（或按Ctrl+F输入题目中的关键词，尽量不要输入整个题目，不要复制空格，连续的几个字就行）
本文由【飞鸟搜题】微信公众号提供，禁止复制盗取，违者必究
本文由【飞鸟搜题】微信公众号提供，禁止复制盗取，违者必究
本文由【飞鸟搜题】微信公众号提供，禁止复制盗取，违者必究
一 、单选题
1. 以下数据结构中（ ）是线性结构。
A. 有向图
B. 堆
C. 完全二叉树
D. 栈
答案：D
- 关注公众号【飞鸟搜题】查看答案
2. 下面关于串的叙述中，正确的是（ ）。
A. 串其实是字母序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串只能采用顺序存储
答案：C
- 关注公众号【飞鸟搜题】查看答案
3. 稀疏矩阵采用压缩存储的目的主要是（ ）。
A. 表达变得简单
B. 对矩阵元素的存取变得简单
C. 去掉矩阵中的多余元素
D. 减少不必要的存储空间的开销
答案：D
- 关注公众号【飞鸟搜题】查看答案
4. 链表不具有的特点是（ ）。
A. 不必事先估计存储空间
B. 可随机访问任一元素
C. 逻辑上相邻的元素在物理位置上不一定相邻
D. 插入删除不需要移动元素
答案：B
- 关注公众号【飞鸟搜题】查看答案
5. 一个具有n个顶点的有向完全图包含（ ）条边。
A. n（n-1）
B. n（n+1）
C. n（n-1）/2
D. n（n+1）/2
答案：关注公众号【飞鸟搜题】查看答案
6. 下面程序段的时间复杂度是（ ）。 for(i=1;i<=n;i++) for(j=1;j<=n;j++){ c[i][j]=0; for(k=1;k<=n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; }
A. O(1)
B. O(log2n)
C. O(n)
D. O(n3)
答案：关注公众号【飞鸟搜题】查看答案
7. 已知某二叉树的后续遍历序列是dabec，中序遍历是debac，则它的先序遍历序列是（ ）。
A. acbed
B. decab
C. deabc
D. cedba
答案：关注公众号【飞鸟搜题】查看答案
8. 以下四个串中最小的是（ ）。
A. ”ABADF”
B. ”ABAFD”
C. ”ABADFA”
D. ”ABAF”
答案：关注公众号【飞鸟搜题】查看答案
9. （）不属于线性表的基本操作。
A. 插入
B. 求子表
C. 存取
D. 求表长
答案：关注公众号【飞鸟搜题】查看答案
10. 对具有n个元素的任意序列采用插入排序法进行排序，排序趟数为（ ）。
A. n-1
B. n
C. n+1
D. log2n
答案：关注公众号【飞鸟搜题】查看答案
11. 假定一棵二叉树中，叶子结点数为10，单分支结点数为30，则双分支结点数为（ ）。
A. 7
B. 8
C. 9
D. 19
答案：关注公众号【飞鸟搜题】查看答案
12. （ ）的一个重要应用是解决主机和打印机之间速度不匹配的问题。
A. 双向链表
B. 循环链表
C. 栈
D. 队列
答案：关注公众号【飞鸟搜题】查看答案
13. 有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。
A. 29/10
B. 31/10
C. 26/10
D. 29/9
答案：关注公众号【飞鸟搜题】查看答案
14. 下面关于栈的基本运算算法中，复杂度最高的是（）。
A. 链栈清空运算
B. 顺序栈判空运算
C. 读取栈顶运算
D. 入栈运算
答案：关注公众号【飞鸟搜题】查看答案
15. 非空的单向循环链表的尾结点满足（ ）（设头指针为head，指针p指向尾结点）。
A. p->next==head
B. p==NULL
C. p== head
D. p->next==NULL
答案：关注公众号【飞鸟搜题】查看答案
二 、判断题
1. 采用顺序查找法对长度为n（n为偶数）的线性表进行查找，采用从前向后的方向查找。在等概率条件下成功查找到前n/2个元素的平均查找长度为(n+2)/4。
A. √
B. ×
答案：关注公众号【飞鸟搜题】查看答案
2. 如果一个叶子结点是某二叉树中序遍历序列的最后一个结点，那么它也是该二叉树的先序遍历序列的最后一个结点。
A. √
B. ×
答案：关注公众号【飞鸟搜题】查看答案
3. 设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为33。
A. √
B. ×
答案：关注公众号【飞鸟搜题】查看答案
4. 若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。
A. √
B. ×
答案：关注公众号【飞鸟搜题】查看答案
5. 在双向循环链表上，删除最后一个结点，其算法的时间复杂度为0(1)。
A. √
B. ×
答案：关注公众号【飞鸟搜题】查看答案
6. 完全二叉树中没有度为1的结点。
A. √
B. ×
答案：关注公众号【飞鸟搜题】查看答案
7. 字符串a1=〝heijing〞, a2 =〝hen〞 , a3= 〝heifang〞, a4=“heni〞，其中最小的是a2。
A. √
B. ×
答案：关注公众号【飞鸟搜题】查看答案
8. 数据的物理结构是指数据在计算机内的实际存储形式。
A. √
B. ×
答案：关注公众号【飞鸟搜题】查看答案
9. 若一个强连通图有n个顶点，则该强连通图中至少含有n条有向边。
A. √
B. ×
答案：关注公众号【飞鸟搜题】查看答案
10. 在归并排序中，在第3趟归并中，是把长度为4的有序表归并为长度为8的有序表。
A. √
B. ×
答案：关注公众号【飞鸟搜题】查看答案
11. 在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针后移，当删除一个元素队列时，头指针后移。
A. √
B. ×
答案：关注公众号【飞鸟搜题】查看答案
12. 一个广义表的表头总是一个广义表。
A. √
B. ×
答案：关注公众号【飞鸟搜题】查看答案
13. 顺序查找是一种最简单的查找方法。
A. √
B. ×
答案：关注公众号【飞鸟搜题】查看答案
14. 具有n个结点的二叉树，采用二叉链表存储，共有n-1个空链域。
A. √
B. ×
答案：关注公众号【飞鸟搜题】查看答案
15. 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。
A. √
B. ×
答案：关注公众号【飞鸟搜题】查看答案
三 、综合题
1. 以下是直接插入排序算法对存放在a[0],a[1],……,a[n-1]中，长度为n的记录序列按关键字key由小到大排序，完成程序中空格部分。 void disort (NODE a[ ], int n) { int i,j; NODE temp; for (i=1;i<n;i++) { temp=a[i]; j=i-1; while ( j>=0&&temp.key<a[j].key) { a[j+1]=a[j]; _______; } a[j+1]=temp; } }
A. j++
B. i++
C. j--
D. i--
答案：关注公众号【飞鸟搜题】查看答案
2. 以1，2，3 ，6，7，8作为叶结点的权，构造一棵哈夫曼树是如下哪个图？（ ）
A.
B.
C.
D.
答案：关注公众号【飞鸟搜题】查看答案
3. 在下面空格处填写一条语句，以使下面的顺序队列入队算法完整。 void InQueue(struct SeqQueue *sq, int x) { if (sq->rear==MaxSize) { printf(“队列已满！ ”); exit(1); } ______________ sq->rear++; }
A. x=sq->data[sq->rear];
B. x=sq->rear[sq->data];
C. sq->rear[sq->data]=x;
D. sq->data[sq->rear]=x;
答案：关注公众号【飞鸟搜题】查看答案
4. 设查找表为： 用折半查找在该查找表成功查找到元素55需要经过（ ）次比较。
A. 1
B. 2
C. 3
D. 4
答案：关注公众号【飞鸟搜题】查看答案
5. 设有一个头指针为head的单向链表中（结点类型为NODE），p为指向该链表中某个结点的指针。以下程序段为插入一个指针为s的结点，使它成为p结点的直接前驱，请选择其中空格的选项。 NODE *q; q=head; while(q->next!=p) ________; s->next=p; q->next=s;
A. p=p->next
B. q=q->next
C. s=s->next
D. head=head->next
答案：关注公众号【飞鸟搜题】查看答案
关注公众号【飞鸟搜题】，回复【试题】获取试卷答案
微信扫码添加好友
如二维码无法识别，可拨打 13662661040 咨询。