数据结构期末总复习题

1 套题1

一、选择题（每题2 分，共15题，总计30 分） 1 以下叙述中正确的是_____。 A 数组是数据的最小单位

B 数据对象就是一组数据元素的集合 C 顺序存储方式只能用于存储线形结构

D 树对应到的二叉树其根结点的右子树总是空的

2 一个数组的第一个元素的存储地址是100，每个元素长度为2，则第5个元素的存储地址是_____。 A 110 B 108 C 100 D 120 3 一个栈的入栈顺序是a,b,c,d,e，则其出栈顺序不可能是_____。 A a,b,c,d,e B e,d,c,b,a C d,c,e,a,b D d,e,c,b,a 4栈的特点是_____。

A 先进先出 B 先进后出 C 随即存取 D 链式实现 5 一个队列的入队顺序是1，2，3，4，5，那么出队顺序是_____。 A 5，4，3，2，1 B 1，2，3，5，4 C 1，2，3，4，5 D 1，3，2，4，5

6 向一个长度为10的数组的第5个元素之前插入一个元素时，需向后移动_____个元素。 A 3B 5C 6 D7

7若一棵二叉树有101个结点，且无度为1的结点，则叶结点的个数为_____。 A 48 B 49 C 50 D 51 8 高度为6的完全二叉树中第4层结点的个数为_____。 A 2 B 4 C 8 D 16 9具有n个顶点的无向完全图，其边数为_____。

A n B n(n-1) C n(n-1)/2 D n 10具有n个顶点的有向完全图，其边数为_____。

A n B n(n-1) C n(n-1)/2 D n 11在有7个顶点的无向图中至少有_____条边才能确保该图连通。 A 1 B 6 C 7 D 21

12对于一个有n个顶点的无向图，若采用邻接矩阵表示法，则该矩阵的大小是_____。 A n-1 B n C (n-1) D n

13在序列1，10，12，15，23，40，66，77，85中利用直接查找，查找15所需的比较次数为_____。 A 2 B 3 C 4 D 6

14 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为_____。 AO( n) B O(nlogn) C O(n) D O(logn) 15 在待排序元素基本有序的前提下，效率最高的排序方法是_____。 A 插入排序 B 选择排序 C 快速排序 D 归并排序

二、填空题（每空2 分，共20空，总计40 分）

1 判定下列程序段的时间复杂度为_________________，其中语句A[i][j]频度为___________________ for(i=0;i

for(j=0;j<=n;j++)

22

222

2

A[i][j]=0; B[j][i]=1; }

2对线性表进行二分查找时，要求线性表必须_______________且______________。

3 对于一个头指针为head的带头结点的单链表，判定该链表为空的条件是__________________，对于一个不带头指针的单链表，判定该链表为空的条件是__________________。

4 在循环单链表中，头指针用head表示，队尾结点用p指向，那么p→next等于__________________。 5 在选择数据结构的存储结构时，为了方便地定位和读取某特定元素，数据结构宜采用__________形式，为了方便地进行数据元素的插入删除操作，数据结构宜采用__________形式。 6深度为5的二叉树，最多有___________个结点，最少有___________个结点。

7若深度为5的二叉树中仅有度为0的结点和度为2的结点，那么这棵二叉树最多有___________个结点，最少有___________个结点。

8 在线索二叉树中，若以ltag表示某结点的左标志域，以lch表示某结点的左孩子域，则结点t没有左子树的条件是。

9在含有个8结点的二叉链表中有_______个空链域。 10有_______个结点的二叉树将会呈现5种不同的表现形式。

11在无向图的邻接矩阵中，若A[i][j]=1,A[j][i]= _______________。 12如下图所示的有向图，顶点D的入度为，出度为，顶点D的度为。

A B C D E F

三、操作题（共4题，总计20分） 1已知一棵二叉树如下图所示：

A B

①写出该二叉树的先根遍历序列(2分) ②写出该二叉树的中根遍历序列(2分)

③判断正误：这棵二叉树的先根、中根、后根遍历序列中，叶子结点的相对次序保 持不变，其实，任意一棵二叉树，其叶子结点在先根、中根、后根遍历序列中的相 对次序都保持不变。（2分）

C D E F 2 下面的程序段是一个在单链表表示的有序序列a,b,d,e中插入新值c并保持有序的算法，已知插入位置的前驱用p指向，请将程序段补充完整。(6分)

p

3

Status ListInsert_L(LinkList &L, char c) {

s=(LinkList)malloc(sizeof(LNode)); ; s→next=; p→next=; return OK; }//ListInsert_L

3下图为一个无向图G，请给出该图从A出发的两个可能的广度优先遍历序列

①(2分) ②(2分)

③ 画出该图的邻接矩阵表示（4分）

四、算法设计题（共1题，总计10分）

设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。

套题2

一、选择题（每题2 分，共10题，总计20 分）

1 一个数组的第一个元素的存储地址是1000，每个元素长度为4，则第4个元素的存储地址是_____。 A 1004 B 1008 C 1012 D 1016 2 一个栈的入栈顺序是a,b,c,d,e，则其出栈顺序不可能是_____。 A a,b,c,d,e B e,d,c,b,a C d,c,e,a,b D d,e,c,b,a

3从一个具有n个结点的单链表中查找值等于x的结点，在查找成功的前提下，其平均比较次数为_____。 A n B n/2 C (n-1)/2 D (n+1)/2

4 在序列1，10，12，15，23，40，66，77，85中利用直接查找，查找15所需的比较次数为_____。 A 2 B 3 C 4 D 6 5 下列排序算法中不稳定的是_____。

head a b d e ∧ A B D F C E 4

A 堆排序 B 折半插入排序 C 直接插入排序 D 链式基数排序

6 向一个长度为100的数组的第45个元素之前插入一个元素时，需向后移动_____个元素。 A 45B 46C 55 D56

7若一棵二叉树有101个结点，且无度为1的结点，则叶结点的个数为_____。 A 48 B 49 C 50 D 51 8具有n个顶点的无向完全图，其边数为_____。

A n B n(n-1) C n(n-1)/2 D n 9 下列关于图的描述，错误的是_____。

A 无向图中所有顶点的度数之和为边数之和的2倍 B 有向图中所有顶点的度数之和为边数之和的2倍 C 有向图中所有顶点的入度之和等于出度之和 D 具有n个顶点，n-1条边的无向图是连通图 10有关二叉树下列说法正确的是_____。 A 二叉树是度为2的树 B 一棵二叉树的度可以小于2 C 二叉树中至少有一个结点的度为2 D 二叉树中所有结点的度都为2

二、填空题（每空2 分，共12题，总计40 分）

1 判定下列程序段的时间复杂度为___________________，其语句频度为___________________ for(i=0;i

for(j=0;j<=n;j++) A[i][j]=0; B[j][i]=1; }

2 在一个单链表中的p所指的结点之前插入一个s所指的结点的操作可以描述为： s->next=____________________; p->next=s; t=p->data;

p->data=____________________; s->data=____________________;

3 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的

排序是____________________，需要内存容量最多的排序是____________________。 4 对线性表进行二分查找时，要求线性表必须___________________________。

5 对于一个头指针为head的带头结点的单链表，判定该链表为空的条件是__________________，对于一个不带头指针的单链表，判定该链表为空的条件是__________________。

6 数据的存储结构是指，设有一批数据元素，为了方便地定位和读取某特定元素，数据结构宜采用__________形式，为了方便地进行数据元素的插入删除操作，数据结构宜采用__________形式。 7 已知一棵二叉树，其先序序列为ABCDE，中序序列为CDBEA，则其后序序列为_。 8高度为6的二叉树，其结点个数最多为_____个，最少为_____个。

9在线索二叉树中，若以ltag表示某结点的左标志域，以lch表示某结点的左孩子域，则结点t没有左子树的条件是。

2

5

10在含有个20结点的二叉链表中有_______个空链域。 11 有_______个结点的二叉树将会呈现5种不同的表现形式。 12如下图所示的AOE－网，其关键路径为。

3 A 3 B 1 2 C 5 D 3 2 E 2 F

三、算法题（每题8分，共2题，总计16分）

1、关键字序列a,b,c，d的链式存储如下，编写算法，通过更改指针实现关键字序列a，d，c,b的链式存储。

2、设计算法，现有一字符串“12468”（即该变量为字符数组，每个单元存放一个char型的值，分别为1，2，4，6，8），若该字符串表示的是数值型的八进制数值，即（12468）8，设计算法将它转换为十进制数并输出。

四、操作题（每题6分，共4题，总计24分）

1、已知一棵树如下图所示，要求： ①给出树的先根遍历序列和后根遍历序列（3分） ②将该树转化为二叉树（3分）

2、设有一组关键字为{8,7,13,10,9,23,15}，哈希函数为H(key)=key MOD 7，按开放定址的线性探测再散列解决冲突，即增量序列为1，2，3，?，构造表地址空间为0--9的哈希表。

head a b c d ∧ A B C D E F G H I J K

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构期末总复习题在线全文阅读。