10.后缀式算术表达式

数据结构-习题-第六章-树和二叉树E F D G A B / + + * - C * 第六章 树和二叉树一、选择题1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( )A ．-A+B*C/DE B. -A+B*CD/EC ．-+*ABC/DE D. -+A*BC/DE【北京航空航天大学 1999 一、3 （2分)】2．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ ）【中山大学 1999 一、5】A ．ab+cde/*B ．abcde/+*+C ．abcde/*++D ．abcde*/++ 3. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ ）【南京理工大学1999 一、20（2分）】A. A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G)C. (A*B+C)/(D*E+（F-G ）)D.A*B+C/D*E+F-G4. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）A ．5B ．6C ．7D．8【南京理工大学 2000 一、8 （1.5分）】5. 在下述结论中，正确的是（）【南京理工大学 1999 一、4 （1分）】①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③ B．②③④ C．②④ D．①④6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定【南京理工大学2000 一、17（1.5分）】7. 树是结点的有限集合，它（ (1）)根结点，记为T。

其余结点分成为m（m>0）个(（2）)的集合T1，T2，…，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。

数据结构《数据结构》教学⼤纲哈尔滨师范⼤学信息科学系《数据结构》⼀、课程设置的有关说明1．课程性质：是必修课、选修课<数据结构>是信息与计算科学专业的必修的核⼼课程。

是学习计算机和本专业后续课程的基础，也是今后⼯作中必备的和最常⽤的知识。

2．课程定义：(简要描述、该课程在学习中的地位、作⽤及发展状况)它主要内容是讨论现实世界中数据(既事物的抽象描述)的各种逻辑结构,以及进⾏各种⾮数值运算的算法。

⽬的是使学⽣掌握数据组织、存储和处理的常⽤⽅法，为以后进⾏软件开发和学习后续专业课打下基础。

3．设置本课程的⽬的和基本要求：本课程是为继续学学习计算机软件和进⾏软件开发打下坚实的基础。

为此，本课程在选材和内容组织等⽅⾯⼒求做到：科学性、新颖性和实⽤性相结合，⼒图在阐明基本原理和⽅法的同时，也能反映某些最新研究成果，使学⽣牢固地掌握本学科的基本知识。

4．教学内容简介数据的逻辑结构分为线性结构、树（层次）结构和图形结构、链接结构、索引结构和散列结构中的⼀种或多种的组合。

对数据进⾏的⾮数值运算主要包括插⼊、删除、查找、和输出等。

需要特别指出：数据的存储结构既适⽤于内存，也适⽤于外存，不仅要学会对内存数据操作的算法，⽽且要学会对外存数据（⽂件）操作的算法，这样才能解决实际软件开发的问题，达到学以致⽤的⽬的。

⼆、具体教学内容第⼀章绪论(4学时)教学⽬的和教学基本要求：要求了解什么是数据结构，及其相关的术语。

了解学习本课程所必须的C++知识。

掌握如何进⾏算法评价，包括正确性、健壮性、可读性、简单性、时间复杂性和空间复杂性等。

内容提要：第⼀节常⽤术语基本教学内容：对数据结构中⼀些常⽤的名词和术语给以确定的含义。

包括数据、数据元素、数据记录、关键字、关键项、数据处理、数据结构、线性结构、树形结构、图形结构、数据类型、抽象数据类型、数据对象和算法。

重点是关键字、线性结构、树形结构和图形结构，难点是数据结构的⼏种形式。

数据结构模拟考试试卷(1卷)一．判断题（下列各题，正确的请在前面的括号内打√；错误的打×）（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。

（ㄨ）（2）线性表的链式存储结构优于顺序存储。

（√）（3）将中缀表达式转换成后缀表达式是栈的重要应用。

（×）（4）栈和队列都是顺序存储的线性结构。

（×）（5）“DT”是“DA TA”的子串。

（×）（6）在二叉树中，具有一个子女的父结点，在中序遍历的序列中，它没有后继子女结点。

（×）（7）带权图的最小生成树是唯一的。

（√）（8）散列存储法的基本思想是由关键字的值决定数据的存储地址。

（√）（9）希尔排序是不稳定的排序。

（√）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。

二．填空题1．线性结构中元素之间存在一对一关系。

2．树形结构和图形结构合称为：非线性结构。

3．顺序表中逻辑上相邻的元素在物理位置上必须相连。

4．在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为O (n) 。

5．同一栈的各元素的类型相同。

6．已知表达式，求它的后缀表达式是栈的典型应用之一。

7．队列在进行出队操作时，首先要判断队列是否为空。

8．设循环队列的头指针front指向队头元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为front==(rear+1)% MAXLEN 。

9．串的链式存储结构简称为链式串。

10．求子串函数SubStr("Today is 30 July,2005",13,4)的结果是：July 。

11．给定如下图所示的二叉树，其层次遍历序列为：ABCEFGH 。

12．将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，该结点右孩子的编号为：2*i+1 。

13．图的遍历有：深度优先搜和 _广度优先搜 __等方法。

软件评测师上午基础知识考试选择题专项强化真题试卷1(题后含答案及解析)题型有：1.1．验收测试的定义是(52)。

A．由用户按照用户手册对软件进行测试以决定是否接收B．由某个测试机构代表用户按照需求说明书和用户手册对软件进行测试以决定是否接收C．按照软件任务书或合同，供需双方约定的验收依据进行测试，决定是否接收D．由开发方和用户按照用户手册执行软件验收正确答案：C解析：本题考查验收测试的定义。

验收测试是按照项目任务书或合同、供需双方约定的验收依据文档进行的对整个系统的测试与评审，决定是否接收或拒收系统。

验收测试的测试计划、测试方案与测试案例一般由开发方制定，由用户方与监理方联合进行评审。

验收小组由开发方、用户方、监理方代表、主管单位领导及行业专家构成。

2．CD上声音的采样频率为44.1kHz，样本精度为16b/s，双声道立体声，那么其未经压缩的数据传输率为(14)。

A．88.2kb/sB．705.6kb/sC．1411.2kb/sD．1536.0kb/s正确答案：C解析：本题考查波形声音信号的数据传输率。

波形声音信息是一个用宋表示声音振幅的数据序列，它是通过对模拟声音按一定间隔采样获得的幅度值，再经过量化和编码后得到的便于计算机存储牙口处理的数据格式。

未经压缩的数字音频数据传输率可按下式计算：数据传输率(b/s)=采样频率(Hz)×量化位数(b)×声道数3．为保证测试活动的可控性，必须在软件测试过程中进行软件测试配置管理，一般来说，软件测试配置管理中最基本的活动包括(65)A．配置项标识、配置项控制、配置状态报告、配置审计B．配置基线确立、配置项控制、配置报告、配置审计C．配置项标识、配置项变更、配置审计、配置跟踪D．配置项标识、配置项控制、配置状态报告、配置跟踪正确答案：A解析：本题考查测试配置管理中基本活动的基础知识。

测试配置管理的基本活动包括配置项标识、配置项控制、配置状态报告以及配置审计。