《c++答案数据结构试卷及答案.docx》由会员分享，可在线阅读，更多相关《c++答案数据结构试卷及答案.docx（129页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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、rear分别为队列的头
2、、尾指针,maxSize为数 组的最大长度,队满的条件是()A. front=maxSizeB. (rear+1 )%maxSize=frontC. rear=maxSizeD. rear=front6 .设有串 t=,I am a good student 那么 Substr(t,6,6)= ( )A. studentB. a good sC. goodD. a good7 .设有一个对称矩阵A,采用压缩存储方式，以行序为主序存储all为第一个元素, 其存储地址为1,每个元素占个地址空间,则a85地址为( )A.23B.33C.18D. 408 .已知广义表LS=(A,(B,C,D),E)运
3、用head和tail函数,取出LS中原子b的运算()A. Gethead(Gethead(LS)B. Gettail(Gethead(LS)C. Gethead(Gethead(Gettai 1(LS)D. Gethead(Gettail(LS)9.若已知一棵叉树先序序列为ABCDEFG,中序序列为CBDAEGF,则其后序序 列为()A. CDBGFEAB. CDBFGEAC. CDBAGFED. BCDAGFE10 .下列存储形式中,（）不是树的存储形式。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=l；I=n;I+）for(int j=l;jdata);if(p-rchild!=NULL) (3)
5、; stacktop=p-rchild;if( (4) ) top+; (5) ;)(1)(2)(3)(4)(5)3.请在标号处填写合适的语句。完成下列程序。(每空1分,共5分)int B inary_Search(S_TB L tbl, KEY kx) /在表tbl中查找关键码为kx的数据元素,若找到返回该元素在表中的位置,否则 返回 /int mid, flag=O；low= 1 ； high=length；while( &!flag_)/非空,进行比较测试/mid=_ (2)；if(kxtbl.elemmid.key) (4)；return flag;(1)(2)(3)(4) (5)4.
6、下面是个采用直接选择排序方法进行升序排序的函数,请在标号处填写合适的 语句。(每空1分,共5分)程序:int i, j, t, minval, minidx;for(i=l;i=n-l;i+)一5(1)for (j=i+2;j0(3) top+(4) p-lchild!=NULL(5) stack Ltop=p-lchild3 (5分,每空1分)(1) IowAj(3) minval=Aj(4) i!=j(5) Ai+l=Aminidx5 (10分,不同答案,酌情得分) 输入顶点和弧信息,建立其邻接表 计算每个顶点的入度对其进行拓扑排序排序过程中求顶点的Vei将得到的拓扑序列进栈按逆拓扑序列求
7、顶点的VI i计算每条弧的ei和li,找出ei=l条的关键活动第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-l D、top=top+l3 .从一个具有n个结点的单链表中査找其值等于x结点时,在查找成功情况下,则平 均比较个结点。A、 n B、 n/2 C、 (n-
8、l)/2 D、 (n+l)/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、 rear- next=s;rear=s；D、 s- next=front;front=s；6 .在一棵度为3的树中度为3的结点数为3
9、个,度为2的结点数为1个,度为1的结点数为1个,那么度为O的结点数为 个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+l C、 2i-l D、 i/29 .在个有向图中,所有顶点的入度之和等于所有弧数和一倍。A、 1 B、 2 C, 3 D、 410 .对于个具有N个顶点的图,若用邻接矩阵表示,则该矩阵的大小为。A、 N B、 (N-l)2 C、 (N+l)2 D、 N211 .已知一个图如图
10、所示,在该图的最小生成树中各边上数值之和为一6(3)18、6A, 21 B、 26 C、 28 D、 3312 .已知一个图如图所示,由该图行到的种拓朴序列为13 .二维数组M的元素是4个字符（每个字符占个存储单元）组成的串,行下标 i的范围从到4,列下标j的范围从。到5, M按行存储时元素M的起始地 址与M按列存储时元素一的起始地址相同。A、m4 B、M4 C、M3l D、M3l14 .具有6个结点的无向图至少应有 条边能保证是连通图。A、5 B、6 C、 7 D、 815 .采用邻接表存储的图的深度优先遍历类似于叉树的 0A先序遍历B中序遍历C,后序遍历D.按层遍历二、填空题（本大题共5小
11、题,每空1分,共8分;答案填在下表内）123456781 .数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示,根据数据元素之间关系的不同特性,通常有下列四类基本结构:集合、 线性结构、和 。2 .评价算法的标准很多,通常是以执行算法所需要的（3）和所占用的（4）来判别个算法的优劣。3 .线性表的顺序存储结构特点是表中逻辑关系相邻的元素在机器内的 也是相 邻的。4 .空格串的长度为串中所包含 （6） 字符的个数,空串的长度为 （7）5 .加上表示指向前驱和（8） 的线索的叉数称为线索叉树。三、判断题（对的打“丿”,错的打X二 每小题1分，共10分）（）1.线性表的唯一
12、存储形式是链表。（）2.已知指针P指向键表L中的某结点,执行语句P=Pnext不会删除该链 表中的结点。（）3.在链队列中,即使不设置尾指针也能进行入队操作。（）4.如果一个串中的所有字符均在另串中出现,则说前者是后者的子串。（）5.设与一棵树T所对应的叉树为BT,则与T中的叶子结点所对应的BT中 的结点也一定是叶子结点。（）6.快速排序是不稳定排序。（）7.任一 A0E网中至少有一条关键路径，且是从源点到汇点的路径中最短的 条。（）8.若图G的最小生成树不唯一,则G的边数一定多于nT,并且权值最小的 边有多条（其中n为G的顶点数）。（）9.给出不同的输入序列建造叉排序树，一定得到不同的叉排序
13、树。 10.基数排序是多关键字排序。从最低位关键字起进行排序。四、应用题。（共44分）L画出该图的邻接矩阵和邻接表。根据邻接表从A开始求DFS和BFS序列。（12分）2.假设用于通信的电子由字符集岫,艰帥中的字母构成,这8个字母在电文中 出现的概率分别为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, 2
14、9, 11, 16, 92, 22, 8, 3）,哈希表表长 为11, Hash（key）=key mod 11,用线性探测法处理冲突,构造哈希表,并求它成功 查找的ASL。（8分）5 .叉树的先序遍历序列为ABCDEFGHI,中序遍历序列为B C A E D G H F I,画出这棵叉树。（6分）五、算法设计题（8分）定义有序表抽象数据类型,并据此类型设计折半查找算法2学期数据结构试卷A参考答案及评分标准、选择题本大题共15小题,每题2分,共30分123456789101112131415ADDBCCCBADBADAA二、填空题（本大题共5题,每空1分,共8分）12345678树型结构图型结
15、构时间空间位置空格后继三、判断题（每小题1分,共10分）12345678910XVVXX-JXXXX四、应用题44分）1. （12 分）011000101000100001010010000101001010AB0. 2A3ACDEF35ADFS 序列:ABDEFCBFS 序列:ABCDFE2. （8 分）7192632321100010100000000010100001110113. （10 分）直接插入排序70, 73, 69, 23, 93, 18,11, 6870, 73, 69, 23, 93, 18,11, 6870, 69, 73, 23, 93, 18,11, 6823,70
16、, 69, 73, 93, 18,11, 6823,70, 69, 73, 93, 18, 11, 6818, 23, 70, 69, 73, 93, 11, 6811, 18,23, 70, 69, 73, 93, 6811, 18, 23, 68, 70, 69, 73, 93快速排序168,11,69,23,18 ,70,93,734. （8 分）0123456789 10112247921637298ASL=5/35. （6 分）五、算法设计题(8分)typedef struct int key;float info;JD;int binsrch(JD r,int n,int k) i
17、nt low,high,mid,found;low=l; high=n; found=0;while(lowrmid.key) low=mid+l;else if(k=rmid.key) found=l;i;if(found=l)return(mid);elsereturn(O);程序设计教程用C+语言编程（第二版习题解答）目录第1章概述24第2章基本数据类型和表达式26第3章 程序的流程控制语句29第4章过程抽象函数38第5章构造数据类型47第6章 数据抽象类63第7章操作符重载82第8章 继承派生类106第 9 草 类属（泛型）机制模板117第10章 输入/输出（I/O） 123第11章异
18、常处理130第12章 实例面向对象的Windows应用程序框架132第1章概述简述冯诺依曼计算机的工作模型。答:冯诺依曼计算机的工作模型是:待执行的程序从外存装入到内存中,CPU从内存中逐条 地取程序中的指令执行:程序执行中所需要的数据从内存或从外设中获得,程序执行中产生的 中间结果保存在内存中,程序的执行结果通过外设输出。简述寄存器、内存以及外存的区别。答：寄存器主要用于记录下一条指令的内存地址、当前指令的执行状态以及暂时保存指令的计 算结果供下（几）条指令使用,其作用主要是减少访问内存的次数，提高指令的执行效率。内存用于存储计算机程序（指令和数据）,内存由许多存储单元构成,每个存储单元都有
19、一 个地址,对存储单元的访问是通过其地址来进行的，与寄存器相比，内存的容量要大得多，但 指令访问内存单元所花费的时间比访问寄存器要多得多。外存是大容量的低速存储部件,用于永久性地存储程序、数据以及各种文档等信息，存储 在外存中的信息通常以文件形式进行组织和访问,外存储了在容量和速度上与内存不同，另 个区别在于内存中存储的是正在运行的程序和正在使用的数据,外存中存储的则是大量的、并 非正在使用的程序和数据。CPU能执行哪些指令?答：CPU所能执行的指令通常有：算术指令：实现加、减、乘、除等运算。比较指令：比较两个操作数的大小。数据传输指令：实现CPU的寄存器、内存以及外设之间的数据传输。执行流程
20、控制指令：用于确定下一条指令的内存地址，包括转移、循环以及子程序调用/返回等 指令。什么是软件?软件是如何分类的?答：计算机软件是计算机系统中的程序以及有关的文档。程序是对计算任务的处理对象（数据） 与处理规则（算法）的描述;文档是为了便于大理解程序所需的资料说明,供程序开发与维护 使用。软件通常可以分为系统软件、支撑软件和应用软件。系统软件居于计算机系统中最靠近硬 件的级，它与具体的应用领域无关，其他软件一般要通过系统软件发挥作用,如操作系统属 于系统软件。支撑软件是指支持软件开发与维护的软件,一般由软件开发大员使用,如软件开 发环境就是典型的支撑软件。应用软件是指用于特定领域的专用软件，如
21、大口普查软件、财务 软件等。什么是虚拟机?答:在由硬件构成的计算机（称为“裸机”）之上,加上些软件就得到了一个比它功能更强的 计算机,称为“虚拟机”。十进制数0.1的二进制表示是什么?答:（0.1）10 = （0.000110011）2,它是无限循环小数。也就是说,十进制数0.1无法精确用二进制 表示!简述程序设计范型。答：基于不同的计算模型来对计算进行描述就形成了不同的程序设计范型。典型的程序设计范 型有：过程式、对象式、函数式以及逻辑式等。过程式程序设计是种以功能为中心、基于功能分解和过程抽象的程序设计范型。一个过 程式程序由一些子程序构成,每个子程序对应个子功能，它实现了功能抽象。对象式
22、程序设计是一种以数据为中心、基于数据抽象的程序设计范型。一个面向対象程序 由一些对象构成，对象是由一些数据及可施于这些数据上的操作所组成的封装体。函数式程序设计是围绕函数来进行的，计算过程体现为系列的函数应用。逻辑程序设计是把程序组织成一组事实和一组推理规则，在事实基础上运用推理规则来实 施计算。简述程序设计的步骤。答：程序设计一般遵循以下步骤:明确问题: 系统设计: 用某种语言进行编程: 测试与调试: 运行与维护低级语言与高级语言的不同之处是什么?答：低级语言是指与特定计算机体系结构密切相关的程序语言,它是特定计算机能够直接理解 的语言（或与之直接对应的语言），包括机器语言和汇编语言。低级语
23、言的优点在于:写出的程 序效率比较高,包括执行速度快和占用空间少。其缺点是：程序难以设计、理解与维护,难以 保证程序的正确性。高级语言是指人容易理解和有利于人对解题过程进行描述的程序语言。高级语言的优点在 于:程序容易设计、理解与维护,容易保证程序正确性。高级语言的缺点是：用其编写的程序 相对于用低级语言编写的程序效率要低,翻译成的目标代码量较大。简述编译与解释的区别。答:编译是指把高级语言程序首先翻译成功能上等价的机器语言程序或汇编语言程序,然后执 行目标代码程序,在目标代码程序的执行中不再需要源程序。解释则是指対源程序中的语句进行逐条翻译并执行,翻译完了程序也就执行完了,这种翻 译方式不产
24、生目标程序。一般来说,编译执行比解释执行效率要高。简述C+ +程序的编译执行过程。在你的C+开发环境中运行1.3.2节中给出的简单C+程序。 答:首先可以利用某个编辑程序把C+源程序输入到计算机中,并作为文件保存到外存中，文 件名为“*.cpp”和“*.h”。然后利用某个C+编译程序对保存在外存中的C+源程序进行编译, 编译结果作为目标文件保存到外存,文件名为“*.obj。然后再通过个联接程序把由源文件 产生的目标文件以及程序中用到的一些系统功能所在的目标文件联接起来,作为个可执行文 件保存到外存，文件名为“*.exe。最后通过操作系统提供的应用程序运行机制，把可执行文 件装入内存,运行其中的
25、可执行程序。在Visual C+6.0环境中,苜先要建立一个project （项目）;其次往该project中添加、编辑 程序模块（源文件）;然后选择菜单Build中的Build .或Rebuild AH;最后选择菜单Build中 的Execute .运行程序。C+的单词分成哪些种类?答:构成C+的单词有:标识符、关键词、字面常量、操作符以及标点符号等。下面哪些是合法的C+标识符?extern, _book, Car, car_l, calr, Icar, friend, carl_Car, Car_Type, No.1, 123 答:合法的 C+标识符:_book, Car, car_l,
26、calr, carl_Car, Car_Type第2章 基本数据类型和表达式C+提供了哪些基本数据类型?检查你的计算机上各种类型数据所占内存空间的大小（字节数）。答:C+提供了以下5种基本数据类型:整数类型、实数类型、字符类 型、逻辑类型以及空值类型。一台计算机上各种数据类型的数据所 占用的内存大小（字节数）可以通过“sizeof（类型名）”来计算。下面哪一些是合法的C+字面常量,它们的类型是什么?-5.23, .20, -000, red,le+50, e5, A, r,105,20-0.0e5, Xn* ,3.14, false答:字面常量是指在程序中直接写出常量值的常量。-5.23, l
27、e + 50,-25, 20 , .20, le-5, -0.0e5, n, 000, A,5, r, f , Today is Monday.,都是字面常量。其中: 整数类型常量:-25, 20, -000 实数类型常量:-5.23, le+50 , .20, le-5, -0.0e5 字符常量:n, A, 5, r, f字符串常量：Today is Monday. , 什么是符号常量?符号常量的优点是什么?答：符号常量是指有名字的常量,在程序中通过常量的名字来使用这些常量。程序屮使用符号 常量有以下优点：1）增加程序易读性2）提高程序对常量使用的一致性3）增强程序的易维护性如何理解变量?变
28、量定义和声明的作用是什么?答:在程序中,其值可以改变的量称为变量。变量可以用来表示可变的数据。程序中使用到的每个变量都要有定义。变量定义指出变量的类型和变量名，另外还可以为 变量提供个初值。C+中使用变量之前，必须对使用的变量进行声明（变量定义属于种声明，即：定义性 声明）,变量声明指出了一个变量的类型，使得编译程序能对变量的操作进行类型检查并 做相应的类型转换。整个程序中,某变量的定义只能由一个，但它的声明可以有多个。什么是表达式?其作用是什么?答：表达式是由操作符、操作数以及圆括号所组成的运算式。在程序设计语言中，对数据操作 的具体实施是通过表达式来描述的。操作符的优先级和结合性分别是指的
29、什么?答：运算符的优先级和结合性决定表达式中各个运算符的运算次序。操作符的优先级规定了相 邻的两个操作符谁先运算：优先级高的先计算;如果相邻的两个操作符具有相同的优先级, 则需根据操作符的结合性来决定先计算谁,操作符的结合性通常分为左结合和右结合:左 结合表示从左到右计算,右结合表示从右到左计算。表达式中的类型转换规则是什么?下面的表达式计算时如何进行操作数类型转换?3/5*12.3a+10*5.212U+3.0F*24L答:表达式中类型转换规则是:基于单个操作符依次进行转换。1) 3与5同类型,不转换,结果为,转换成double型后与12.3做乘法。2) 10转换成double型与5.2做乘
30、法,，a，转换成double型后与前者结果做加法。3) 3.0F与24L均转换成double型后做乘法,12U转换成double型后与前者结果做加法。将下列公式表示成C+的表达式：加+ (可利用C+标准库中的求平方根的函数:sqrt(x)2aJs(s _ a)(s _ b)(s - c)答:1) (-l*b+sqrt(b*b-4*a*c)/(2*a)2) sqrt(s*(s-a)*(s-b)*(s-c)3) (a*b)/(c*d)*(3/(l+(b/(2.5+c)+(4*pi*r*r*r/3)写出下列条件的C+表达式i能被j整除。Ch为字母字符。m为偶数。n是小于100的奇数。a、b、c构成三
31、角形的三条边。答：1) i%j=02) (ch=a)&(ch=A)&(ch=Z)3) m%2=04) (n0) & (b0) & (c0) & (a+bc) & (b+ca) & (c+ab) 或(a+b) c) & (abs (a-b) 0) & & (b0) & (c0)可以不用判断在你的计算机上运行下面的程序:#include using namespace std;int main() double a=3.3, b=l.1;int i=a/b;cout i endl;return 0;结果与你预期的是否相符?如果不符,请解释它的原因。答:运行结果为2。由于十进制小数3.3和1.1无法
32、用double型精确表示。通过查看结果内存内 的内容,最终结果比3.0略小,所以强制转换成int型后结果为2。不引进第三个变量,如何交换两个整型变量的值?答：方法一：a=b人a;b=aAb;a=bAa;方法二：a=a+b;b=a-b;a=a-b;举例说明把int类型转成float类型可能会丢失精度。答：如果int型与float型都是4个字节，由于在float型的数据表示中，有若干位用来表示指数, 因此,尾数的位数不到4个字节(根据IEEE标准，只有23个二进制位)。如果个int型的数 大于23位(二进制)，则无法用float型精确表示。例如：int x=0x01000001;float y=x; /x的最后一位T不是被截掉就是被舍入!cout x endl setprecision(30) y endl;第3章程序的流程控制语句编写个程序,将华氏温度转换为摄氏温度。转换公式为:c= |(f-32),其中，c为摄氏温度，f为华氏温度解：#include using namespace std;int main() double c, f;cout Please inp