c++答案 数据结构试卷及答案.doc

《c++答案 数据结构试卷及答案.doc》由会员分享，可在线阅读，更多相关《c++答案 数据结构试卷及答案.doc（132页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构试卷及答案1算法分析的目的是( )。A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性2（ ）是具有相同特性数据元素的集合，是数据的子集。 A.数据符号 B.数据对象 C.数据 D.数据结构3用链表表示线性表的优点是 ( )。A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同4输入序列为（A,B,C,D）不可能的输出有（ ）。 A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D)5在数组表示的循环队列中，front、re

2、ar分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( )。A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front6设有串t=I am a good student ，那么Substr(t,6,6)=（ ）。A. student B. a good s C. good D. a good7设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则 a85地址为（ ）。 A.23 B.33 C.18 D. 408已知广义表LS=(

3、A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（ ）。 A. Gethead(Gethead(LS) B. Gettail(Gethead(LS) C. Gethead(Gethead(Gettail(LS) D. Gethead(Gettail(LS)9若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( ) 。A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10下列存储形式中，( ) 不是树的存储形式。A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法11对待排序的元素

4、序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是 ( )。A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序12采用折半查找方法进行查找，数据文件应为（ ），且限于（ ）。A.有序表 顺序存储结构 B.有序表 链式存储结构 C.随机表 顺序存储结构 D.随机表 链式存储结构13就平均查找速度而言，下列几种查找速度从慢至快的关系是（ ）A.顺序 折半 哈希 分块 B.顺序 分块 折半哈希 C.分块 折半 哈希 顺序 D.顺序 哈希 分块 折半14执行下面程序段时，执行S语句的次数为（ ）for(int I=1

5、;I=n;I+) for(int j=1;jdata); if(p-rchild!=NULL) (3) ; stacktop=p-rchild; if( (4) ) top+; (5) ; 3.请在标号处填写合适的语句。完成下列程序。(每空1分，共5分)int Binary_Search(S_TBL tbl，KEY kx) /* 在表tbl中查找关键码为kx的数据元素，若找到返回该元素在表中的位置，否则，返回0 */ int mid，flag=0；low=1；high=length； while( &!flag ) /* 非空，进行比较测试 */mid= ； if(kxtbl.elemmid.

6、key) ； else flag= ；break； return flag; 4.下面是一个采用直接选择排序方法进行升序排序的函数，请在标号处填写合适的语句。(每空1分，共5分)程序：Void seletesort(int An,int n) int i,j,t,minval,minidx; for(i=1;i=n-1;i+) minval=Ai+1; (1)for(j=i+2;j0(3) top+(4) p-lchild!=NULL(5) stacktop=p-lchild3 （5分，每空1分）（1）lowAj(3) minval=Aj(4) i!=j(5) Ai+1=Aminidx5（10

7、分，不同答案，酌情得分）输入顶点和弧信息，建立其邻接表计算每个顶点的入度对其进行拓扑排序排序过程中求顶点的Vei将得到的拓扑序列进栈按逆拓扑序列求顶点的Vli计算每条弧的ei和li,找出ei=li的关键活动第 2 学期 数据结构试卷A一、 选择题（本大题共15小题，每题2分，共30分；答案填在下表内）1.从一个长度为100的顺序表中删除第30个元素时需向前移动 个元素A、70 B、71 C、69 D、302.在一个具有N个单元的顺序表中,假定以地址低端(即下标为1的单元)作为底,以top作为顶指针,则当做进栈处理时top变化为_。A、 top不变 B、top=0 C、top=top-1 D、t

8、op=top+13.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功情况下,则平均比较_个结点。 A、n B、n/2 C、(n-1)/2 D、(n+1)/24.在一个单链表中,若要删除p指针所指结点的后继结点,则执行A、p- next; p- next=p- next- next;B、p- next=p- next- next;C、p=p- next;D、p=p- next-next;5.在一个链队列中,假定front和rear分别为队首和队后指针,则进行插入S结点的操作时应执行_。A、front- next=s； front=s；B、s- next=rear; rear=s；C、

9、rear- next=s; rear=s；D、s- next=front; front=s；6.在一棵度为3的树中度为3的结点数为3个,度为2的结点数为1个,度为1的结点数为1个,那么度为0的结点数为_个A、6 B、7 C、 8 D、97.假定一棵二叉树的结点数为33个,则它的最小高度为_,最大高度为_A、 4,33 B、5,33 C、6,33 D、6,328. 在一棵完全二叉树中,若编号为i的结点有右孩子,则该结点的右孩子编号为_。A、2i B、2i+1 C、2i-1 D、i/29.在一个有向图中,所有顶点的入度之和等于所有弧数和_倍。 A、1 B、2 C、3 D、410.对于一个具有N个顶

10、点的图,若用邻接矩阵表示,则该矩阵的大小为_。 A、 N B、(N-1)2 C、(N+1)2 D、 N211.已知一个图如图所示，在该图的最小生成树中各边上数值之和为_。A、21 B、26 C、28 D、33 12.已知一个图如图所示，由该图行到的一种拓朴序列为 A、v1 v4 v6 v2 v5 v3 B、v1 v2 v3 v4 v5 v6 C、v1 v4 v2 v3 v6 v5 D、v1 v2 v4 v6 v3 v513.二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M24的起始地址与M按列存储时元素 的起始地址

11、相同。 A、m24 B、M42 C、M31 D、M3114.具有6个结点的无向图至少应有 条边才能保证是连通图。A、 5 B、 6 C、 7 D、 8 15.采用邻接表存储的图的深度优先遍历类似于二叉树的 。A 先序遍历B中序遍历 C. 后序遍历 D. 按层遍历 二、填空题（本大题共5小题，每空1分，共8分；答案填在下表内）123456781.数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示，根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、线性结构、（1） 和 （2） 。2.评价算法的标准很多，通常是以执行算法所需要的 （3） 和所占用的（4） 来判别

12、一个算法的优劣。3.线性表的顺序存储结构特点是表中逻辑关系相邻的元素在机器内的（5） 也是相邻的。4.空格串的长度为串中所包含 （6） 字符的个数，空串的长度为 （7） 5.加上表示指向前驱和 （8） 的线索的二叉数称为线索二叉树。三、判断题（对的打“”，错的打“”。每小题1分，共10分）（ ）1.线性表的唯一存储形式是链表。（ ）2.已知指针P指向键表L中的某结点，执行语句P=P-next不会删除该链表中的结点。（ ）3.在链队列中，即使不设置尾指针也能进行入队操作。（ ）4.如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（ ）5.设与一棵树T所对应的二叉树为BT，则与T中的

13、叶子结点所对应的BT中的结点也一定是叶子结点。（ ）6.快速排序是不稳定排序。（ ）7.任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最短的一条。（ ）8.若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。（ ）9.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。（）10.基数排序是多关键字排序。从最低位关键字起进行排序。四、应用题。（共44分）1.画出该图的邻接矩阵和邻接表。根据邻接表从A开始求DFS和BFS序列。（12分）2.假设用于通信的电子由字符集a,b,c,d,e,f,g,h中的字母构成，这8个字母在电文中出现的

14、概率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10画出哈夫曼树，并为这8个字母设计哈夫曼编码。（8分）3. 已知序列70，73，69，23，93，18,11，68请给出直接插入排序作升序排序每一趟的结果和快速排序作升序排序时一趟的结果。（10分）4.设有一组关键字关键码集为 47，7，29，11，16，92，22，8，3，哈希表表长为11， Hash(key)=key mod 11，用线性探测法处理冲突，构造哈希表，并求它成功查找的ASL。（8分）5. 二叉树的先序遍历序列为 A B C D E F G H I，中序遍历序列为 B C A E D G H

15、F I，画出这棵二叉树。(6分)五、算法设计题（8分）定义有序表抽象数据类型，并据此类型设计折半查找算法。2学期数据结构试卷A参考答案及评分标准一、 选择题本大题共15小题，每题2分，共30分123456789101112131415ADDBCCCBADBADAA二、 填空题（本大题共5小题，每空1分，共8分）12345678树型结构图型结构时间空间位置空格零后继三、判断题（每小题1分，共10分）12345678910四、 应用题44分）1.（12分）210 A301 B020C513D4354E245FDFS序列:ABDEFCBFS序列:ABCDFE2. （8分） 7192632321100

16、010100000000010100001110113. （10分） 直接插入排序70，73，69，23，93，18,11，6870，73，69，23，93，18,11，68 70，69，73， 23，93，18,11，68 23,70，69，73， 93，18,11，68 23,70，69，73， 93，18,11，68 18,23,70，69，73， 93， 11，6811，18,23,70，69，73， 93， 6811，18,23,68,70，69，73， 93快速排序68,11,69,23,18 ,70,93,734. （8分） 0 1 2 3 4 5 6 7 8 9 1011224

17、7921637298 ASL=5/35. （6分）AHBCFDEGI五、 算法设计题（8分）typedef struct int key; float info;JD;int binsrch(JD r,int n,int k) int low,high,mid,found; low=1; high=n; found=0; while(lowrmid.key) low=mid+1; else if(k=rmid.key) found=1; else high=mid-1; if(found=1) return(mid); else return(0);程序设计教程用C+语言编程（第二版习题解答）

18、目 录第1章 概述2第2章 基本数据类型和表达式4第3章 程序的流程控制语句7第4章 过程抽象函数16第5章 构造数据类型22第6章 数据抽象类37第7章 操作符重载53第8章 继承派生类77第9章 类属（泛型）机制模板87第10章 输入/输出（I/O）89第11章 异常处理90第12章 实例面向对象的Windows应用程序框架90第1章 概述简述冯诺依曼计算机的工作模型。答：冯诺依曼计算机的工作模型是：待执行的程序从外存装入到内存中，CPU从内存中逐条地取程序中的指令执行；程序执行中所需要的数据从内存或从外设中获得，程序执行中产生的中间结果保存在内存中，程序的执行结果通过外设输出。简述寄存器

19、、内存以及外存的区别。答：寄存器主要用于记录下一条指令的内存地址、当前指令的执行状态以及暂时保存指令的计算结果供下一（几）条指令使用，其作用主要是减少访问内存的次数，提高指令的执行效率。内存用于存储计算机程序（指令和数据），内存由许多存储单元构成，每个存储单元都有一个地址，对存储单元的访问是通过其地址来进行的，与寄存器相比，内存的容量要大得多，但指令访问内存单元所花费的时间比访问寄存器要多得多。外存是大容量的低速存储部件，用于永久性地存储程序、数据以及各种文档等信息，存储在外存中的信息通常以文件形式进行组织和访问，外存储了在容量和速度上与内存不同，另一个区别在于内存中存储的是正在运行的程序和正

20、在使用的数据，外存中存储的则是大量的、并非正在使用的程序和数据。CPU能执行哪些指令？答：CPU所能执行的指令通常有：算术指令：实现加、减、乘、除等运算。比较指令：比较两个操作数的大小。数据传输指令：实现CPU的寄存器、内存以及外设之间的数据传输。执行流程控制指令：用于确定下一条指令的内存地址，包括转移、循环以及子程序调用/返回等指令。什么是软件？软件是如何分类的？答：计算机软件是计算机系统中的程序以及有关的文档。程序是对计算任务的处理对象（数据）与处理规则（算法）的描述；文档是为了便于人理解程序所需的资料说明，供程序开发与维护使用。软件通常可以分为系统软件、支撑软件和应用软件。系统软件居于计

21、算机系统中最靠近硬件的一级，它与具体的应用领域无关，其他软件一般要通过系统软件发挥作用，如操作系统属于系统软件。支撑软件是指支持软件开发与维护的软件，一般由软件开发人员使用，如软件开发环境就是典型的支撑软件。应用软件是指用于特定领域的专用软件，如人口普查软件、财务软件等。什么是虚拟机？答：在由硬件构成的计算机（称为“裸机”）之上，加上一些软件就得到了一个比它功能更强的计算机，称为“虚拟机”。十进制数0.1的二进制表示是什么？答：(0.1)10 = (0.)2，它是无限循环小数。也就是说，十进制数0.1无法精确用二进制表示！简述程序设计范型。答：基于不同的计算模型来对计算进行描述就形成了不同的程

22、序设计范型。典型的程序设计范型有：过程式、对象式、函数式以及逻辑式等。过程式程序设计是一种以功能为中心、基于功能分解和过程抽象的程序设计范型。一个过程式程序由一些子程序构成，每个子程序对应一个子功能，它实现了功能抽象。对象式程序设计是一种以数据为中心、基于数据抽象的程序设计范型。一个面向对象程序由一些对象构成，对象是由一些数据及可施于这些数据上的操作所组成的封装体。函数式程序设计是围绕函数来进行的，计算过程体现为一系列的函数应用。逻辑程序设计是把程序组织成一组事实和一组推理规则，在事实基础上运用推理规则来实施计算。简述程序设计的步骤。答：程序设计一般遵循以下步骤：明确问题； 系统设计； 用某种

23、语言进行编程； 测试与调试； 运行与维护低级语言与高级语言的不同之处是什么？答：低级语言是指与特定计算机体系结构密切相关的程序语言，它是特定计算机能够直接理解的语言（或与之直接对应的语言），包括机器语言和汇编语言。低级语言的优点在于：写出的程序效率比较高，包括执行速度快和占用空间少。其缺点是：程序难以设计、理解与维护，难以保证程序的正确性。高级语言是指人容易理解和有利于人对解题过程进行描述的程序语言。高级语言的优点在于：程序容易设计、理解与维护，容易保证程序正确性。高级语言的缺点是：用其编写的程序相对于用低级语言编写的程序效率要低，翻译成的目标代码量较大。简述编译与解释的区别。答：编译是指把高

24、级语言程序首先翻译成功能上等价的机器语言程序或汇编语言程序，然后执行目标代码程序，在目标代码程序的执行中不再需要源程序。解释则是指对源程序中的语句进行逐条翻译并执行，翻译完了程序也就执行完了，这种翻译方式不产生目标程序。一般来说，编译执行比解释执行效率要高。简述C程序的编译执行过程。在你的C+开发环境中运行1.3.2节中给出的简单C+程序。答：首先可以利用某个编辑程序把C+源程序输入到计算机中，并作为文件保存到外存中，文件名为“*.cpp”和“*.h”。然后利用某个C+编译程序对保存在外存中的C+源程序进行编译，编译结果作为目标文件保存到外存，文件名为“*.obj”。然后再通过一个联接程序把由源文件产生的目标文件以及程序中用到的一些系统功能所在的目标文件联接起来，作为一个可执行文件保存到外存，文件名为“*.exe”。最后通过操作系统提供的应用程序运行机制，把可执行文件装入内存，运行其中的可执行程序。在Visual C+ 6.0环境中，首先要建立一个project（项目）；其次往该project中添加、