PTA——中国大学MOOC-陈越、何钦铭-数据结构-2019秋期中考试(答案)

本文主要是介绍PTA——中国大学MOOC-陈越、何钦铭-数据结构-2019秋期中考试(答案),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

PTA——中国大学MOOC-陈越、何钦铭-数据结构-2019秋期中考试——答案

    • 选择题 1--10
    • 填空题 1--12
    • 程序填空题 1--2

选择题 1–10

1-1 算法分析的两个主要方面是时间复杂度和空间复杂度的分析。 (2分)

  • T
  • F

答案:T
作者: DS课程组 单位: 浙江大学

1-2 所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。 (2分)

  • T
  • F

答案:F
作者: DS课程组 单位: 浙江大学

1-3 通过对堆栈S操作:Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为:123。 (3分)

  • T
  • F

答案:F
作者: DS课程组 单位: 浙江大学

1-4 在一棵由包含4、5、6等等一系列整数结点构成的二叉搜索树中,如果结点4和6在树的同一层,那么可以断定结点5一定是结点4和6的父亲结点。 (3分)

  • T
  • F

答案:F
作者: DS课程组 单位: 浙江大学

1-5 用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关。 (3分)

  • T
  • F

答案:T
作者: DS课程组 单位: 浙江大学

1-6 若一个结点是某二叉树的中序遍历序列的最后一个结点,则它必是该树的前序遍历序列中的最后一个结点。 (3分)

  • T
  • F

答案:F
作者: DS课程组 单位: 浙江大学

1-7 如果无向图G必须进行两次广度优先搜索才能访问其所有顶点,则G一定有2个连通分量。 (3分)

  • T
  • F

答案:T
作者: DS课程组 单位: 浙江大学

1-8 将一棵完全二叉树存于数组中(根结点的下标为1)。则下标为23和24的两个结点是兄弟。 (3分)

  • T
  • F

答案:F
作者: 何钦铭 单位: 浙江大学

1-9 若一棵平衡二叉树的所有非叶结点的平衡因子都是0,则其必为完美二叉树。(3分)

  • T
  • F

答案:T
作者: 徐镜春 单位: 浙江大学

1-10 在具有N个结点的单链表中,访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。 (3分)

  • T
  • F

答案:F
作者: DS课程组 单位: 浙江大学

填空题 1–12

2-1 下列代码

for(i=0; i<n; i++)for(j=i; j>0; j/=2)printf(“%d\n”, j);

的时间复杂度是: (4分)

  • A. O(N×i)
  • B. O(N)
  • C. O(N2)
  • D. O(NlogN)

答案:D
作者: DS课程组 单位: 浙江大学

2-2 三叉树中,度为1的结点有5个,度为2的结点3个,度为3的结点2个,问该树含有几个叶结点? (4分)

  • A. 8
  • B. 10
  • C.12
  • D.13

答案:A
作者: DS课程组 单位: 浙江大学

2-3 下列函数中,哪两个函数具有相同的增长速度:(4分)

  • A. 2N和NN
  • B. N和2/N
  • C. N2logN和NlogN2
  • D. NlogN2和NlogN

答案:D
作者: DS课程组 单位: 浙江大学

2-4 表达式a*(b+c)-d的后缀表达式是: (4分)
A. a b c + * d -
B. a b c d * + -
C. a b c * + d -
D. - + * a b c d

答案:A
作者: DS课程组 单位: 浙江大学

2-5 在并查集问题中,已知集合元素0~8所以对应的父结点编号值分别是{ 1, -4, 1, 1, -3, 4, 4, 8, -2 }(注:−n表示树根且对应集合大小为n),那么将元素6和8所在的集合合并(要求必须将小集合并到大集合)后,该集合对应的树根和父结点编号值分别是多少? (4分)

  • A. 1和-6
  • B. 4和-5
  • C. 8和-5
  • D. 8和-6

答案:B
作者: DS课程组 单位: 浙江大学

2-6 在将数据序列( 6, 1, 5, 9, 8, 4, 7 )建成大根堆时,正确的序列变化过程是:(4分)

  • A. 6,1,7,9,8,4,5 → 6,9,7,1,8,4,5 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5
  • B. 6,9,5,1,8,4,7 → 9,6,5,1,8,4,7 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5
  • C. 6,9,5,1,8,4,7 → 6,9,7,1,8,4,5 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5
  • D. 6,1,7,9,8,4,5 → 7,1,6,9,8,4,5 → 7,9,6,1,8,4,5 → 9,7,6,1,8,4,5

答案:A
作者: 考研真题 单位: 浙江大学

2-7 已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则该完全二叉树的结点个数最多是: (4分)

  • A. 39
  • B. 52
  • C. 111
  • D. 119

答案:C
作者: DS课程组 单位: 浙江大学

2-8 设一段文本中包含字符{a, b, c, d, e},其出现频率相应为{3, 2, 5, 1, 1}。则经过哈夫曼编码后,文本所占字节数为: (4分)

  • A. 40
  • B. 36
  • C. 25
  • D. 12

答案:C
作者: DS课程组 单位: 浙江大学

2-9 若某图的深度优先搜索序列是{V2, V0, V4, V3, V1},则下列哪个图不可能对应该序列? (4分)

  • A.在这里插入图片描述

  • B.在这里插入图片描述

  • C.在这里插入图片描述

  • D.答案

答案:D
作者: 陈越 单位: 浙江大学

2-10 设h为不带头结点的单向链表。在h的头上插入一个新结点t的语句是:(4分)

  • A. h=t; t->next=h;
  • B. t->next=h->next; h=t;
  • C. h=t; t->next=h->next;
  • D. t->next=h; h=t;

答案:D
作者: DS课程组 单位: 浙江大学

2-11 循环顺序队列中是否可以插入下一个元素()。 (4分)

  • A. 与曾经进行过多少次插入操作有关
  • B. 只与队尾指针的值有关,与队头指针的值无关
  • C. 只与数组大小有关,与队首指针和队尾指针的值无关
  • D. 与队头指针和队尾指针的值有关

答案:D
作者: 严冰 单位: 浙江大学城市学院

2-12 先序遍历图示二叉树的结果为 (4分)
在这里插入图片描述

  • A. A,B,C,D,H,E,I,F,G
  • B. A,B,D,H,I,E,C,F,G
  • C. H,D,I,B,E,A,F,C,G
  • D. H,I,D,B,E,F,G,A,C

答案:B
作者: DS课程组 单位: 浙江大学

程序填空题 1–2

5-1 下列代码的功能是从一个大顶堆H的某个指定位置p开始执行下滤。

void PercolateDown( int p, PriorityQueue H ) {    int  child;   ElementType  Tmp = H->Elements[p];    for ( ; p * 2 <= H->Size; p=child ) {child = p * 2;if ( child!=H->Size &&_____(H->Elements[child]<H->Elements[child+1])_____)child++;if ( H->Elements[child] > Tmp )_____H->Elements[p] = H->Elements[child]_____(6分);else  break;    }    H->Elements[p] = Tmp;  
}

作者: 陈越
单位: 浙江大学
时间限制: 400 ms
内存限制: 64 MB

5-2 下列代码的功能是返回带头结点的单链表L的逆转链表。

 List Reverse( List L ) {Position Old_head, New_head, Temp;New_head = NULL;Old_head = L->Next;while ( Old_head )  {Temp = Old_head->Next; ___Old_head->Next = New_head;_____(6分);New_head = Old_head;           Old_head = Temp;      }_____L->Next = New_head____(6分);return L;}

作者: DS课程组
单位: 浙江大学
时间限制: 400 ms
内存限制: 64 MB

这篇关于PTA——中国大学MOOC-陈越、何钦铭-数据结构-2019秋期中考试(答案)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/358217

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

PTA求一批整数中出现最多的个位数字

作者 徐镜春 单位 浙江大学 给定一批整数,分析每个整数的每一位数字,求出现次数最多的个位数字。例如给定3个整数1234、2345、3456,其中出现最多次数的数字是3和4,均出现了3次。 输入格式: 输入在第1行中给出正整数N(≤1000),在第二行中给出N个不超过整型范围的非负整数,数字间以空格分隔。 输出格式: 在一行中按格式“M: n1 n2 ...”输出,其中M是最大次数,n

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

目录   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点:弱密码字典爆破 四种方法:   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 访问环境 老规矩,我们先查看源代码

poj 3104 二分答案

题意: n件湿度为num的衣服,每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉,每秒可以烧掉k个湿度,但不计算蒸发了。 现在问这么多的衣服,怎么烧事件最短。 解析: 二分答案咯。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

java线程深度解析(一)——java new 接口?匿名内部类给你答案

http://blog.csdn.net/daybreak1209/article/details/51305477 一、内部类 1、内部类初识 一般,一个类里主要包含类的方法和属性,但在Java中还提出在类中继续定义类(内部类)的概念。 内部类的定义:类的内部定义类 先来看一个实例 [html]  view plain copy pu

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

【附答案】C/C++ 最常见50道面试题

文章目录 面试题 1:深入探讨变量的声明与定义的区别面试题 2:编写比较“零值”的`if`语句面试题 3:深入理解`sizeof`与`strlen`的差异面试题 4:解析C与C++中`static`关键字的不同用途面试题 5:比较C语言的`malloc`与C++的`new`面试题 6:实现一个“标准”的`MIN`宏面试题 7:指针是否可以是`volatile`面试题 8:探讨`a`和`&a`

浙大数据结构:树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre