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

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

数据结构试题⼀

⼀、单项选择题（每⼩题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(n2)

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(n2)

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、在单链表、双链表和单循环链表中，若仅知道指