上海交通大学继续教育学院《算法设计与分析》期末大作业

如需代做或答案请联系本站客服，包正确必过！

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

1. 数据结构是研究数据的      以及它们之间的相互关系。

(A) 理想结构，物理结构   (B) 理想结构，抽象结构

(C) 物理结构，逻辑结构   (D) 抽象结构，逻辑结构

2. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址       。

A．必须是连续的     B．部分地址必须是连续的

C．一定是不连续的    D．连续或不连续都可以

3. 栈和队列的共同点是       。

A．都是先进先出       B．都是先进后出

C．只允许在端点处插入和删除元素   D．没有共同点

4. 在线性表两个数据元素a和b之间插入x，已知p指向a，s指向x，则操作为_______。

   A．s->next=p->next； p->next=s    B．s->next=p->next； p=s

C．s=p->next； p->next=s     D．p->next=s；s->next=p->next

5. 深度为5的二叉树至多有       个结点。

A．16   B．32   C．31   D．10

6. 在有n个叶子结点的哈夫曼树中，其结点总数为       。

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

7. 采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为       。

A．O(n²)   B．O(nlog₂n)   C．O(n)   D．O(log₂n)

8. 快速排序法在       情况下最不利于发挥其长处。

A．待排序的记录数据量太大   B．待排序的记录中含有多个相同值   C．待排序的数据已基本有序   D．待排序的数据个数为奇数

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

A. head==NULL      B. head->next==NULL

C. head->next==head     D. head !=NULL

10. 对二叉树来说，第i层上至多有______个结点

A. 2ⁱ          B. 2ⁱ-1  C. 2^i-1   D. 2^i-1-1

11. 利用二叉链表存储二叉树，则根结点的右指针是_______。

A. 指向最左孩子  B. 指向最右孩子  C. 非空  D. 空

12. 将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么21号结点的双亲结点的编号是_______。

   A. 10          B. 11       C. 20         D. 41

13. 设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作为_______。

(A) top=top+1;      (B) top=top-1;  

(C) top->next=top;     (D) top=top->next;

14. 设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为_______。

(A) front->next=s；front=s； (B) s->next=rear；rear=s；

(C) rear->next=s；rear=s；  (D) s->next=front；front=s；

15. 有向图的邻接矩阵存储结构中，下列说法正确的是_______。

A. 第i行非0元素个数之和为结点vi的出度  

B. 第i行非0元素个数之和为结点vi的入度

C. 第i列非0元素个数之和为结点vi的出度  

D. 以上都不对

二、判断题（每小题2分，共20分。以“T”表示“对”，以“F”表示“错”）

1. 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（   ）

2. 由树转化成二叉树，该二叉树的右子树不一定为空。（   ）

3. 完全二叉树中的叶子结点只可能在最后两层中出现。（   ）

4. 线性表中的所有元素都有一个前驱元素和后继元素。（   ）

5. 如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（   ）

6. 用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。（   ）

7. 对链表进行插入和删除操作时不必移动链表中结点。（   ）

8. 带权无向图的最小生成树是唯一的。（   ）

9. 根据关键字查找数据元素的效率高低取决于数据元素的组织结构和算法。（   ）

10. 对于给定的图，其邻接矩阵表示和邻接表表示均是唯一的。（   ）

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

1. 一棵具有35个结点的完全二叉树的深度为__________。

2. 在一个具有n个顶点的无向完全图中，包含__________条边。

3. 在长度为n的顺序表中插入第i个元素(1≤i≤n)需向后移动__________个元素。

4. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为__________。

5. 下面程序段的时间复杂度为__________。

s=i=0;

do  { i=i+1;  s=s+i;

} while(i<=n);

6. 树型结构最适合用来表示元素之间具有__________关系的数据。

7. 设有7个结点的无向图，该图至少应有__________条边才能确保是一个连通图。

8. 含有n个结点的二叉树采用二叉链表存储时，空指针域的个数为__________。

9. 简单选择排序的时间复杂度是__________，快速排序的平均时间复杂度是__________。

四、简答题（每小题6分，共30分）

 

1、有一结点序列为(8,6,4,1,5,2,10)，要求构造并画出一棵二叉排序树，并输出以中序方式遍历该树的序列。

 

2、已知待排序的结点序列为：(46，79，56，38，40，84)，请给出利用快速排序法对该序列按升序排列时的每一趟的结果。

3、 对图1所示的无向网，要求构造出一棵最小生成树（中间过程可以省略），并计算该最小生成树的权。

 

4、已知一棵二叉树的中序序列和后序序列分别为：DBGEACHF和DGEBHFCA，请画出该二叉树，并写出该二叉树的前序序列。

 

5、请按升序方式排列以下数量级的大小关系： O(1)，O(log₂n)，O(2ⁿ)，O(nlog₂n)，O(n)，O(n²)，O(n³)。

 

本文链接：https://www.daizuozuoye8.com/?id=480

转载声明：本站发布文章及版权归原作者所有，转载本站文章请注明文章来源！