数据结构与算法复习

发布 2021-05-02 16:59:28 阅读 5594

第二部分模拟试卷。

模拟试卷一。

单选题(每题 2 分,共20分)

以下数据结构中哪一个是线性结构?(

a. 有向图 b. 队列 c. 线索二叉树 d. b树。

在一个单链表hl中,第二部分模拟试卷。

模拟试卷一。

一、 单选题(每题 2 分,共20分)

1. 以下数据结构中哪一个是线性结构?(

a. 有向图 b. 队列 c. 线索二叉树 d. b树。

2. 在一个单链表hl中,若要在当前由指针p指向的结点后面插入一个由q指向的结点,则执行如下( )语句序列。

a. p=q; p->next=qb. p->next=q; q->next=p;

c. p->next=q->next; p=qd. q->next=p->next; p->next=q;

3. 以下哪一个不是队列的基本运算?(

a. 在队列第i个元素之后插入一个元素 b. 从队头删除一个元素。

c. 判断一个队列是否为空d.读取队头元素的值。

4. 字符a、b、c依次进入一个栈,按出栈的先后顺序组成不同的字符串,至多可以组成( )个不同的字符串?

a.14b.5c.6d.8

5. 由权值分别为3,8,6,2的叶子生成一棵哈夫曼树,它的带权路径长度为( )

a. 11 b.35 c. 19 d. 53

以下6-8题基于图1。

6. 该二叉树结点的前序遍历的序列为( )

a. e、g、f、a、c、d、b

b. e、a、g、c、f、b、d

c. e、a、c、b、d、g、f

d. e、g、a、c、d、f、b

7. 该二叉树结点的中序遍历的序列为( )

a. a、b、c、d、e、g、f

b. e、a、g、c、f、b、d

c. e、a、c、b、d、g、f

e. b、d、c、a、f、g、e

8. 该二叉树的按层遍历的序列为( )

a.e、g、f、a、c、d、bb. e、a、c、b、d、g、f

c. e、a、g、c、f、b、dd. e、g、a、c、d、f、b

9. 下面关于图的存储的叙述中正确的是( )

a.用邻接表法存储图,占用的存储空间大小只与图中边数有关,而与结点个数无关。

b.用邻接表法存储图,占用的存储空间大小与图中边数和结点个数都有关。

c. 用邻接矩阵法存储图,占用的存储空间大小与图中结点个数和边数都有关。

d.用邻接矩阵法存储图,占用的存储空间大小只与图中边数有关,而与结点个数无关。

10. 设有关键码序列(q,g,m,z,a,n,p,x,h),下面哪一个序列是从上述序列出发建堆的结果?(

a. a,g,h,m,n,p,q,x,z b. a,g,m,h,q,n,p,x,z

c. g,m,q,a,n,p,x,h,zd. h,g,m,p,a,n,q,x,z

二、 填空题(每空1分,共26分)

1. 数据的物理结构被分为顺序, 链表, 索引, 散列, 四种。

1. 对于一个长度为n的顺序存储的线性表,在表头插入元素的时间复杂度为在表尾插入元素的时间复杂度为。

2. 向一个由hs指向的链栈中插入一个结点时p时,需要执行的操作是删除一个结点时,需要执行的操作是假设栈不空而且无需**被删除结点)。

3. 对于一棵具有n个结点的二叉树,一个结点的编号为i(1≤i≤n),若它有左孩子则左孩子结点的编号为___若它有右孩子,则右孩子结点的编号为___若它有双亲,则双亲结点的编号为___

4. 当向一个大根堆插入一个具有最大值的元素时,需要逐层___调整,直到被调整到位置为止。

5. 以二分查找方法从长度为10的有序表中查找一个元素时,平均查找长度为___

6. 表示图的三种常用的存储结构为和。

7. 对于线性表(70,34,55,23,65,41,20)进行散列存储时,若选用h(k)=k %7作为散列函数,则散列地址为0的元素有___个,散列地址为6的有___个。

8. 在归并排序中,进行每趟归并的时间复杂度为___整个排序过程的时间复杂度为空间复杂度为。

9. 在一棵m阶b_树上,每个非树根结点的关键字数目最少为___个,最多为___个,其子树数目最少为___最多为___

三、 运算题(每题 6 分,共24分)

1. 写出下列中缀表达式的后缀形式:

1) 3x/(y-2)+1

2) 2+x*(y+3)

2. 试对图2中的二叉树画出其:

1) 顺序存储表示的示意图;

2) 二叉链表存储表示的示意图。

3. 判断以下序列是否是小根堆? 如果不是, 将它调整为小根堆。

4. 已知一个图的顶点集v和边集e分别为:

v=;e=;

按照普里姆算法从顶点1出发得到最小生成树,试写出在最小生成树中依次得到的各条边。

四、 阅读算法(每题7分,共14分)

1. void ae(stack& s);

for(i=0;i<5;i++)push(s,2*a[i]);

while(!stackempty(s)) cout< }

该算法被调用后得到的输出结果为:

2. void abc (btnode *bt,int &c1,int &c2) /if

该函数执行的功能是什么?

五、 算法填空(共8分)

向单链表的末尾添加一个元素的算法。

void insertrear(lnode*& hl,const elemtype& item)

lnode* newptr;

newptr=new lnode;

ifcerr<<"memory allocation failare!"

item;newptr->next=null;

if (hl==null)

hlelse{

lnode* p=hl;

while (p->next!=null)

数据结构与算法复习

数据结构与算法课程考试复习资料。一 填空题。a卷 arraylist类在。net框架的 命名空间中。a b卷 c 语言中,数组的基类是 array a b卷 c 语言中提供了两种类分别用来表示栈和队列,它们是。stack类和 queue类。a卷 查找指定字符的方法是 substring a卷 c 中...

数据结构与算法

本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则,规定了解决某一特定类型问题的一系列运算,是对解题方 与完整的描述。算法是解题的步骤,可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...

算法与数据结构

学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生,定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...