数据结构C++考试题及答案.pdf资源-CSDN文库

版权申诉

5星 · 超过95%的资源 32 浏览量 2023-04-01 19:22:33 上传评论 1 收藏 952KB PDF 举报

资源推荐

资源详情

资源评论

数据结构试题一

一、单项选择题（每小题 3 分，共 30 分）

1、在有 n 个叶子结点的哈夫曼树中，其结点总数为（）。

A、不确定 B、2n C、2n+1 D、2n-1

2、下列序列中，（）是执行第一趟快速排序得到的序列（排序的关键字类型是

字符串）。

A、[da，ax，eb，de，bb]ff[ha，gc] B、[cd，eb，ax，da]ff[ha，

gc，bb] C、[gc，ax，eb，cd，bb]ff[da，ha] D、[ax，bb，

cd，da]ff[eb，gc，ha]

3、若线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用（）存储

方式节省时间。

A、单链表 B、双链表 C、单循环链表 D、顺序表

4、下列排序算法中，时间复杂度不受数据初始状态影响，恒为 O(nlogn)的是（）。

A、堆排序 B、冒泡排序 C、直接选择排序 D、快序排序

5、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉

树。

A、空或只有一个结点 B、高度等于其结点数

C、任意结点无左孩子 D、任意结点无右孩子

6、下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是

（）。

A、堆排序 B、冒泡排序 C、直接选择排序 D、快序排

序

7、快速排序算法在最好情况下的时间复杂度为（）。

A、O(n) B、O(n 2 ) C、O(nlogn) D、O(logn)

8、已知数据表 A 中每个元素距其最终位置不远，则采用（）排序算法最省时

间。

A、堆排序 B、插入排序 C、直接选择排序 D、快序排

序

9、带权有向图 G 用邻接矩阵 A 存储，则顶点 i 的入度为 A 中（）。

A、第 i 行非∞的元素之和 B、第 i 列非∞的元素之和

C、第 i 行非∞且非 0 的元素之和 D、第 i 列非∞且非 0 的元素之和

10、在有 n 个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较

次数的数量级为（）。

A、O(n) B、O(n 2 ) C、O(nlogn) D、O(logn)

二、判断题（认为对的在题后的括号内打“√”，错的打“ⅹ”，每小题１分，

共 10 分）

1.对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可

访问该图的每个顶点。 ( )

2. 在索引顺序表上实现分快查找，在等概率查找情况下，其平均查找长度不仅

与表的个数有关，而且与每一块中的元素个数有关。 ( )

3、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。 ( )

4、图 G 的最小生成树的代价一定小于其他生成树的代价。 ( )

5、已知一棵树的先序序列和后序序列，一定能构造出该树。 ( )

6、对一个堆按层次遍历，不一定能得到一个有序序列。 ( )

7、设与一棵树 T 所对应的二叉树为 BT，则与 T 中的叶子结点所对应的 BT

中的结点也一定是叶子结点。 ( )

8、不管 ADT 栈是用数组实现，还是用链表的指针实现，POP(S)与 Push(x,S) 的

耗时均为 O(n)。 ( )

9、如果删除二叉排序树中一个结点，再按照二叉排序树的构造原则重新插入上

去，一定能得到原来的二叉排序树。 ( )

10、快速排序是排序算法中最快的一种。 ( )

三、填空题（每小题 2 分，共 20 分）

1、在双向循环表中，在 p 所指的结点之后插入指针 f 所指的结点，其操作为：

___ ______=p;f→next=p→next;_____=f; p→next=f。

2、在有序表 A[1…20]中，采用二分查找算法查找元素值等于 A[12]的元素，所

比较过的元素的下标依次为__________。

3、若某串的长度小于一个常数，则采用_________存储方式最节省空间。

4、在有 n 个顶点的有向图中，每个顶点的度最大可达_________。

5、已知二叉树中叶子数为 50，仅有一个孩子的结点数为 30，则总结点数为

__________。

6、设键值序列为{K1，K2，…，Kn},用筛选法建堆则必须从第_______个元素

开始筛选。

7、在二叉链表中判断某指针 p 所指结点为叶子结点的条件是_________。

8、直接选择排序算法在最好情况下所作的交换元素的次数为___ _____。

9、有 n 个球队参加的足球联赛按主客场制进行比赛，共需进行_______比赛。

10、下列排序算法中，占用辅助空间最多的是_________( 堆排序，希尔排序，

快速排序，归并排序)。

四、简答题（每题 10 分，共 60 分）

1、在单链表、双链表和单循环链表中，若仅知道指针 p 指向某结点，不知道头

指针，能否将结点 p 从相应的链表中删去？若可以，其时间复杂度各为多少？

2、设有一组关键字（17，13，14，153，29，35）需插入到表长为 12 的散列表

中，请回答以下问题：

（1）设计一个适合该散列表的散列函数。

（2）用设计的散列函数将上述关键字插入到散列表中，并用线性探测法解决

冲突，画出其结构；并指出用线性探测法解决冲突时构造散列表的装填因子为多

少？

3、对 n 个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下

列有关问

（1）图中有多少条边？

（2）任意两个顶点 i 和 j 是否有边相连？

（3）任意一个顶点的度是多少？

4、已知下面二叉排序树的各结点的值依次为 1…9，请标出各结点的值。

数据结构试题 2

一、单项选择题（每小题 3 分，共 30 分）

1、下列排序算法中，（）排序在每趟结束后，不一定能选出一个元素放到其排好序的最终

位置上。

A、选择 B、冒泡 C、归并 D、堆

2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则

采用（）存储方式最节省运算时间。

A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表

3、串的长度是（）。

A、串中不同字符的个数 B、串中不同字母的个数

C、串中所含字符的个数且字符个数大于 0 D、串中所含字符的个数

4、有一个散列表，表长度 m 为 100，采用除余法构造散列函数，即 H(k)=k%P,(P 小于等

于 m)，为使散列函数有较好的性能，P 的选择应是（）。

A、99 B、97 C、91 D、93

5、在包括 n 个键值的二叉排序树中查找一个键值，其平均比较的量级为（）。

A、O(n) B、O(logn) C、O(nlogn) D、O(n)

6、对有 14 个元素的有序表 A[1…14]作二分查找，查找 A[4]时的被比较元素依次为（）。

A、A[1]，A[2]，A[3]，A[4] B、A[1]，A[14]，A[7]，A[4]

C、A[7]，A[3]，A[5]，A[4] D、A[7]，A[5]，A[3]，A[4]

7、具有 65 个结点的完全二叉树其深度为（）。

A、8 B、7 C、6 D、5

8、带权有向图 G 用邻接矩阵 A 存储，则顶点 i 的入度等于 A 中（）。

A、第 i 行非无穷元素之和 B、第 i 列非无穷元素之和

C、第 i 行非零且非无穷元素个数 D、第 i 列非零且非无穷元素个数

9、队列操作的原则是（）。

A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除

10、若表 R 在排列前已按元素键值递增顺序排序，采用（）的比较次数少。

A、直接插入排序 B、快速排序 C、归并排序 D、选择排序

二、判断题（认为对的，在题后的括号内打“√”，错的打“ⅹ”，每小题１分，共１０分）

1、在栈空的情况下，不能做退栈运算，否则产生下溢。（）

2、在快速排序算法中，取待排序的 n 个记录中的第一个的键值为基准，将所有记录分为

两组，读记录就排在这两组的中间，这也是该记录的最终位置。（）

3、在索引顺序表查找方法中，对索引顺序表可以使用顺序表查找方法，也可以使用二分查

找方法。（）

4、设有键值序列（k1，k2，…，kn），当 i>n/2 时，任何一个序列（k1，k2，…，kn）一定

是堆。（）

5、在向二叉排序树中插入一个新结点时，需要比较结点的次数可能大于此二叉树的高度h。

（）

6、在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为

零。（）

7、双循环链表中，任一结点的前驱指针均为不空。（）

8、线性表采用链式存储方式和顺序存储方式，执行插入、删除运算的算法时间复杂度都是

O(n),因而两种存储方式的插入、删除运算所花费的时间相同。（）

9、如果有向图 G=(V，E)的拓扑序列不唯一，则图中必有两条弧<vi,vj>和<vj,vi> 存在。（）

剩余20页未读，继续阅读

评论收藏

内容反馈

版权申诉

Allbule8352

2024-01-09

资源很实用，对我启发很大，有很好的参考价值，内容详细。
2201_75761617

2023-06-13

资源太好了，解决了我当下遇到的难题，抱紧大佬的大腿~

若♡

粉丝: 6210
资源: 1万+

数据结构C++考试题及答案.pdf

C++面试题笔试题C++ 数据结构算法笔试题资料合集.zip

数据结构C++考试题及答案汇编.pdf

数据结构C++考试题及答案终稿.pdf

数据结构C++版试题.docx.pdf

数据结构C++考试题及答案 (2).pdf

2010西藏自治区数据结构(C++)试题及答案.pdf

2019年10月自考数据结构02331真题及参考答案.pdf

哈工大2009秋《C++与数据结构》考试题-B.pdf

数据结构与算法C++版_模拟试题.pdf

数据结构(C++)模拟试题.pdf

数据结构考试题(英文版)C++.pdf

数据结构考试题(英文版)C++分享.pdf

相关实用应用程序（Windows可用）

李飞飞自传 我看见的世界 The World I see

ChatGPT使用总结：150个ChatGPT提示词模板（完整版）

chromedriver-win64.zip

全国计算机二级WPSoffice精选350道选择题题库（含答案）.pdf

哈尔滨工业大学-ChatGPT调研报告-2023.3.6-94页.pdf

智联招聘：2024年大学生就业力调研报告.pdf

第十九届研电赛-技术论文模板

4个亲测好用的ChatGPT4渠道

学术海报模板+论文科研+研究生

北森能力测评题库.zip

车载毫米波雷达DOA估计综述博文仿真代码

农村公交与异构无人机协同配送优化

ST-LINK Utility 4.6.0

认知智能技术与产业研究报告2023

python大作业 含爬虫、数据可视化、地图、报告、及源码（2016-2021全国各地区粮食产量）.rar

2023泛娱乐社交出海手册-ZEGO即构科技

最新资源

李飞飞自传我看见的世界 The World I see

python大作业含爬虫、数据可视化、地图、报告、及源码（2016-2021全国各地区粮食产量）.rar