数据结构 试题(A)-答案(2)

第二学期“数据结构”考试试题（A）

姓名

学号(序号)_ 班号

要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。

一、单项选择题（每小题2分，共20分）

1．数据的运算a 。

A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 3. 在顺序表中删除一个元素的时间复杂度为 c 。

A.O(1) B.O(log2n) C.O(n) D.O(n2)

4．以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 。

5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。 A.edcba C.dceab 。

6. 循环队列qu的队空条件是 d 。

B.decba D.abcde

A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front

7. 两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 。

8. 用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是 c 。 A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90,80 C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94,40 。

9. 以下序列不是堆（大根或小根）的是 d 。

2 数据结构期末考试试题（共3页） A.{100,85,98,77,80,60,82,40,20,10,66} B.{100,98,85,82,80,77,66,60,40,20,10} C.{10,20,40,60,66,77,80,82,85,98,100} D.{100,85,40,77,80,60,66,98,82,10,20} 。

10. 以下排序方法中，b ，在初始序列已基本有序的情况下，排序效率最高。 A.直接选择排序 B.昌泡排序 C.快速排序 D.堆排序 。

二、填空题（每题2分，共10分）

1. 将f=1+

12++…

311n(n>3)转化成递归函数，其递归出口是 ① ，递归体是 ②

评分标准：每空1分

2．广义表((),a,(a),((a)))的长度是 4 ① ，深度是3 ② 。 评分标准：每空1分

3. 具有n个结点的二叉树采用二叉链存储结构，共有 n+1 个空指针域。 4. 在有n个顶点的有向图中，每个顶点的度最大可达 n-1 。

5. 外排序的基本方法是归并法。它一般要经历文件预处理①和 多路归并②两个阶段。 评分标准：每空1分

三、问答题（共30分）

1．设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度（需写出过程）。（6分）

int m=0,i,j;

for (i=1;i<=n;i++)

for (j=2*i;j<=n;j++) m++;

∑i=1```i=n/2 (n-2i+1) (n+1)n/2-2*(1+2+…n/2)

=(n+1)n/2-2*(n/2+1)*n/2/2 =(n+1)n/2-(n/2+1)*n/2 =n2/4

2. 如果对线性表的运算只有4种，即删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后一个元素的后面插入新元素，则最好使用以下哪种存储结构，需说明理由： （10分）

（1）只有表尾指针没有表头指针的循环单链表 （2）只有表尾指针没有表头指针的非循环双链表 （3）只有表头指针没有表尾指针的循环双链表 （4）既有表头指针也有表尾指针的循环单链表

数据结构期末考试试题（共3页） 3 3. 有一个有序表R[1..13]={2,3,5,10,32,41,45,62,75,77,85,95,100}，当用二分查找法查找关键字为75的结点时，经多少次比较后查找成功，依次与哪些关键字进行比较？（6分）

4. 设二叉排序树中关键字互不相同，证明，其中最小关键字结点必无左孩子，最大关键字结点必无右孩子。（8分）

四、算法设计题（共40分）

1．设计一个算法，将一个头结点为L的单链表（假设结点值为整数）分解成两个单链表L1和L2，使得L1链表中含有原链表L1中值为奇数的元素，而L2链表中含有原链表A中值为偶数的元素，且保持原来的相对顺序。（10分）

{

2．假设二叉树采用二叉链存储结构存储，设计一个算法，求先序遍历序列中第k(1≤k≤二叉树中结点个数)个结点的值。（15分） 3. 假设图G采用邻接表存储，设计一个算法，判断无向图G是否连通。若连通则返回1；否则返回0。（15分）

提示：采用深度优先遍历或广度优先遍历求解，需写出相应的遍历算法。

本文来源：https://www.bwwdw.com/article/7her.html