数据结构实验题目2016

2016年4月高等教育自学考试全国统一命题考试数据结构试卷(课程代码02331)注意事项：1．本试卷分为两部分，第一部分为选择题，第二部分为非选择题。

2．应考者必须按试题顺序在答题卡(纸)指定位置上作答，答在试卷上无效。

3．涂写部分、画图部分必须使用2B铅笔书写部分必须使用黑色字迹签字笔。

第一部分选择题一、单项选择题（本大题共15小题，每小题2分，共30分）1．下列选项中，属于非线性数据结构的是（）A．队列B．栈C．二叉排序树D．线性表2．瑞士计算机科学家沃思教授曾指出：算法+数据结构=程序．这里的数据结构指的是（）A．数据的逻辑结构和存储结构B．数据的线性结构和非线性结构C．数据的紧凑结构和非紧凑结构D．数据的顺序结构和链式结构3．线性表顺序存储时，逻辑上相邻的两个数据元素，其存储地址（）A．一定相邻B．一定不相邻C．不一定相邻D．可能不相邻4．数据元素1，2，3，4，5依次入栈，则不可能得到的出栈序列是（）A．4，5，3，2，1 B．1，2，3，4，5C．4，3，5，1，2 D．5，4，3，2，15．设顺序表首元素A[0]的存储地址是4000，每个数据元素占5个存储单元，则元素A[20]的起始存储地址是（）A．4005 B．4020 C．4100 D．41056．广义表 A=(a，(b，c，(e，f)))，函数 head(head(tail(A)))的运算结果是（）A．a B．b C．c D．e7．设高度为h的二叉树中，只有度为0和2的结点，则此类二叉树包含的结点数至少是（）A．2h B．2h-1 C．2h+1 D．h+18．—棵非空二叉树T的前序遍历和后序遍历序列正好相反，则T一定满足（）A．所有结点均无左孩子B．所有结点均无右孩子C．只有一个叶子结点D．是一棵满二叉树9．设图的邻接矩阵A如下所示。

各顶点的度依次是（）A．1，2，1，2 B．2，2，1，1 C．3，4，2，3 D．4，4，2，21O．无向图G如题10图所示，从顶点a开始进行深度优先遍历，下列遍历序列中，正确的是（）A．a，b，e，c，d，f B．a，c，f，e，d，bC．a，c，b，e，f，d D．a，e，d，f，c，b11．设带权连通图G中含有n（n>1）个顶点，下列关于G的最小生成树T的叙述中，正确的是（）A．T中可能含有回路B．T中含有图G的所有边C．T是唯一的，且含有n-1条边D．T可能不唯一，但权一定相等12．若要求对序列进行稳定的排序，则在下列选项中应选择（）A．希尔排序B．快速排序C．直接插入排序D．直接选择排序13．下列排序算法中，空间复杂度最差的是（）A．归并排序B．希尔排序C．冒泡排序D．堆排序14．下列排序算法中，初始数据有序时，花费的时间反而更多的算法是（）A．插入排序B．冒泡排序C．快速排序D．希尔排序15．对线性表L进行二分查找时，要求L必须满足（）A．以顺序方式存储B．以顺序方式存储，且数据元素有序C．以链接方式存储D．以链接方式存储，且数据元素有序第二部分非选择题二、填空题（本大题共10小题，每小题2分，共20分）16．下面程序段的时间复杂度是_________。

通过上机实验加深对课程内容的理解，增加感性认识，提高算法设计、程序编写及调试的能力。

要求所编的程序能正确运行（最好用C++调试），并提交实验报告。

实验题目先由理论课程的教师给学生，实验前学生必须做好准备，实验报告理论教师可以相当于作业登记。

上实验课程的教师督促、监控学生是否自己调试程序，相关情况作为成绩评定的依据。

实习报告规范：实习报告开头有题目，班级，姓名，学号和完成日期，并包括以下七个内容：1. 需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？明确规定：输入的形式和输入值的范围；输出的形式；程序所能达到的功能；测试数据；2. 概要设计：说明本程序中用到的所有抽象数据类型的定义，主程序的流程以及各程序模块之间的层次关系。

3. 详细设计：对每个操作写出伪码算法；对主程序和其他模块也需要写出伪码算法；画出函数的调用关系图。

提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。

4. 调试分析：调试过程中遇到的问题；算法的时空分析和改进思想；经验和体会。

5. 用户使用说明：说明如何使用你编写的程序，详细列出每一步的操作步骤。

6. 测试结果：列出你的测试的结果，包括输入和输出。

7. 附录：带注释的源程序。

《数据结构》实验题目实验一栈的实现及应用一、实验目的及要求：1、熟悉栈的定义和栈的基本操作。

2、掌握顺序存储栈和链式存储栈的基本操作的具体实现。

3、加深对栈结构的理解，并逐步培养解决实际问题的编程能力二、实验内容说明：以下题目选择其一编程实现，在报告中说明栈实现的方式1．数制转换将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题，用"除B取余法"来解决。

【例】将十进制数13转化为二进制数。

解答：按除2取余法，得到的余数依次是1、0、1、1，则十进制数转化为二进制数为1101。

2．表达式求值（后缀表达式）当用户输入一个合法的后缀表达式后，能够返回正确的结果。

西交16年《数据结构》作业考核试题一、单项选择题〔共 30 道试题，共 60 分。

〕1. 设某哈夫曼树中有199个结点，则该哈夫曼树中有〔〕个叶子结点。

A. 99[正确]B. 100C. 101D. 102总分值：2 分2. 字符串的长度是指〔〕A. 串中不同字符的个数B. 串中不同字母的个数[正确]C. 串中所含字符的个数D. 串中不同数字的个数总分值：2 分3. 设某有向图中有n个顶点，则该有向图对应的邻接表中有〔〕个表头结点。

A. n-1[正确]B. nC. n+1D. 2n-1总分值：2 分4. 设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为〔〕。

A. 6B. 11C. 5[正确]D. 6.5总分值：2 分5. 在一棵具有5层的满二叉树中结点数为〔〕[正确]A. 31B. 32C. 33D. 16总分值：2 分6. 下面关于线性表的表达错误的选项是〔〕。

A. 线性表采用顺序存储必须占用一片连续的存储空间B. 线性表采用链式存储不必占用一片连续的存储空间C. 线性表采用链式存储便于插入和删除操作的实现[正确]D. 线性表采用顺序存储便于插入和删除操作的实现总分值：2 分7. 设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为〔〕。

A. nB. eC. 2n总分值：2 分8. 设一组初始记录关键字的长度为8，则最多经过〔〕趟插入排序可以得到有序序列。

A. 6[正确]B. 7C. 8D. 9总分值：2 分9. 设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为〔〕。

A. 2i+1[正确]B. 2iC. i/2D. 2i-1总分值：2 分10. 设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为〔〕。

A. top=top+1;B. top=top-1;C. top->next=top;[正确]D. top=top->next;总分值：2 分11. 二叉排序树中左子树上所有结点的值均〔〕根结点的值。

实验题目一一、单链表基本运算【问题描述】设计并实现线性表的单链表存储和运算。

【基本要求】实现单链表的插入、删除和遍历运算，每种操作用一个函数实现。

插入操作：将一个新元素插入表中指定序号的位置。

删除操作：将指定序号的元素从表中删除。

遍历操作：从表头按次序输入所有元素的值，若是空表，则输出信息“empty list!”。

【实现提示】程序运行时，首先在main函数中创建空的、带头结点的单链表。

然后多次调用实现插入操作的函数（每次都将元素在序号1位置上插入），将元素依次插入表中，最后调用实现遍历操作的函数输出所有元素。

之后再多次调用实现删除操作的函数将表还原为空表（每次都删除第1个元素，每删除一个元素后，将表中剩余元素都输出一次）。

【测试数据】输入数据：1 2 3 4 5 0（为0时结束，0不存入链表）第一次输出：5 4 3 2 1第二次输出：4 3 2 1第三次输出：3 2 1第四次输出：2 1第五次输出：1第六次输出：empty list!二、约瑟夫环问题【问题描述】编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。

报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出列为止。

【基本要求】利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

【测试数据】M的初始值为20；n等于7，7个人的密码依次为：3，1，7，2，4，8，4。

输出为：6，1，4，7，2，3，5【实现提示】程序运行时，首先要求用户指定初始报数上限值，然后读取各人的密码。

可设n≤30。

此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。

【选作内容】用顺序存储结构实现该题目。

三、一元多项式相加、减运算器【问题描述】设计一个一元稀疏多项式简单计算器。

华师网院2016春《数据结构》作业100%1．第1题以下叙述错误的是( )。

A.数据的三个层次是数据、数据元素、数据项B.数据类型是指相同性质的计算机数据的集合C.每种逻辑结构都有一个运算的集合D.储存结构中不仅要储存数据的内容，还要把数据间的关系表示出来。

您的答案：B题目分数：2此题得分：2.02．第2题多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为( )。

A.数组的元素处在行和列两个关系中B.数组的元素必须从左到右顺序排列C.数组的元素之间存在次序关系D.数组是多维结构，内存是一维结构您的答案：A题目分数：2此题得分：2.03．第3题线性表采用链式存储时，其地址( )。

A.必须连续B.部分地址必须连续C.一定不连续D.连续与否均可您的答案：D题目分数：2此题得分：2.04．第5题线索二叉树中某结点为叶子的条件是( )。

A.p-> lchild!=NULL || p-> rchild!=NULLB.p-> ltag==0 || p-> rtag==0C.p-> lchild!=NULL && p-> rchild!=NULLD.p-> ltag==1 && p-> rtag==1您的答案：D题目分数：2此题得分：2.05．第6题设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为( )。

A)O(nlogn)2B)O(en)n)C)O(elog2D)O(n+e)A.AB.BC.CD.D您的答案：D题目分数：2此题得分：2.06．第7题n)且稳定的排序方法是( )。

最好和最坏时间复杂度均为O(nlog2A.快速排序B.堆排序C.归并排序D.基数排序您的答案：C题目分数：2此题得分：2.07．第8题假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行( )次探侧。

A.k-1B.kC.k+1D.k(k+1)/2您的答案：D题目分数：2此题得分：2.08．第9题n个记录直接选择排序时所需的记录最多交换次数是( )。

一元多项式计算能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减和相乘, 并将结果输出。

矩阵的运算采用十字链表表示稀疏矩阵, 并实现矩阵的加法运算, 要求: 要检查有关运算的条件, 并对错误的条件产生报警。

迷宫求解输入一个任意大小的迷宫数据, 用递归和非递归两种方法求出一条走出迷宫的路径, 并将路径输出；宾馆订房和退房系统假设一个宾馆有n个标准的客房, 每个标准客房有m个标准间, 利用链表、栈或者队列等数据结构设计出具有订房和退房等功能的管理系统。

建立二叉树和线索二叉树分别用以下方法建立二叉树并用图型显示出来:用先序遍历的输入序列用层次遍历的输入序列用先序和中序遍历的结果最后对所建立的二叉树进行中序线索化, 并对此线索树进行中序遍历(不使用栈)。

学生成绩查询系统试编写程序完成学生成绩记录的查询。

按学号排序后对学号进行折半查找。

随机输入以学号为关键字的学生信息并构建二叉排序树, 对学号进行二叉排序树查找。

马的遍历问题设计程序完成如下要求: 在中国象棋棋盘上, 对任一位置上放置的一个马, 均能选择一个合适的路线, 使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。

要求:1)依次输出所走过的各位置的坐标。

2)最好能画出棋盘的图形形式, 并在其上动态地标注行走过程。

教学计划编制问题大学的每个专业都要编制教学计划。

假设任何专业都有固定的学习年限, 每学年含两学期, 每学期的时间长度和学分上限都相等。

每个专业开设的课程都是确定的, 而且课程的开设时间的安排必须满足先修关系。

每个课程的先修关系都是确定的, 可以有任意多门, 也可以没有。

每一门课程恰好一个学期。

试在这样的情况下设置一个教学计划编制程序。

设计要求：针对计算机系本科课程, 根据课程之间的依赖关系(如高级语言、离散数学应在数据结构之前开设)制定课程安排计划, 并满足各学期课程数目大致相同。

设计一个模拟计算器的程序要求对包含加、减、乘、除、括号运算符的任意整型表达式进行求解。

实验一单链表实验一、实验目的1、掌握用Visual C++6.0上机调试单链表的基本方法2、掌握单链表的插入、删除、查找、求表长以及循环单链表的实现二、实现内容1、约瑟夫环问题[问题描述] 已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。

从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到只剩下一个人为止。

[基本要求]输入n和m，输出最后剩下的人的编号。

实验二栈的实现及应用一、实验目的1、掌握顺序栈的类型定义方法。

2、掌握在顺序栈上实现的六种基本算法。

2、掌握顺序栈的简单应用。

二、实验内容1、利用顺序栈将一个非负的十进制整数N转换为对应的B进制数。

[基本要求]非负的十进制整数N和B都从键盘输入；转换结果从屏幕输出。

实验三队列的实现及应用一、实验目的1、掌握队列的类型定义方法。

2、理解和掌握循环队列解决假溢出的方法。

二、实验内容1、利用循环队列模拟舞伴配对问题：在舞会上，男、女各自排成一队。

舞会开始时。

依次从男队和女队的队头各出一人配成舞伴。

如果两队初始人数不等，则较长的那一队中未配对者等待下一轮舞曲。

2、假设初始男、女人数及性别已经固定，舞会的轮数从键盘输入。

试模拟解决上述舞伴配对问题。

3、要求：从屏幕输出每一轮舞伴配对名单，如果在该轮有未配对的，能够从屏幕显示下一轮第一个出场的未配对者的姓名。

实验四树的基本操作一、实验目的1、进一步掌握指针变量、动态变量的含义。

2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。

3、掌握用指针类型描述、访问和处理二叉树的运算。

二、实验内容（二选一）1、以二叉链表作存储结构，试编写前序、中序、后序遍历二叉树的算法。

2、赫夫曼树的算法。

实验五图的基本操作一、实验目的（二选一）1、掌握图的存储方式2、掌握图的相关操作二、实验内容1、实现拓扑排序算法。

2、最短路径算法。

实验六查找一、实验目的1、掌握查找的不同方法，并能用高级语言实现查找算法。

【题目】若两棵二叉树T1和T2皆为空，或者皆不空且T1的左、右子树和T2的左、右子树分别相似，则称二叉树T1和T2相似.试编写算法,判别给定两棵二叉树是否相似.二叉链表类型定义:typedef struct BiTNode ｛TElemType data;struct BiTNode *lchild， *rchild；} BiTNode， *BiTree;＊****＊＊＊*＊/Status Similar（BiTree T1, BiTree T2)/＊判断两棵二叉树是否相似的递归算法＊/｛if(!T1＆＆！T2）//同为空时,两树相似return TRUE；else if(T1&＆T1)｛if(Similar（T1 -> lchild，T2 -> lchild）＆& Similar(T1 -> rchild,T2 —> rchild）)//两树都不为空时,判断左右子树是否相似return TRUE；elsereturn FALSE；}else//以上两种情况都不符合,就直接返回FALSEreturn FALSE;}/**＊*＊＊＊***【题目】编写递归算法,求对二叉树T先序遍历时第k个访问的结点的值。

二叉链表类型定义：typedef struct BiTNode ｛TElemType data;struct BiTNode *lchild, *rchild;} BiTNode, *BiTree;＊*＊*＊*＊**＊/TElemType PreOrder（BiTree T， int &k) ｛TElemType x=’＃’;if（T==NULL）return '#'；if（k==1）return T-〉data;if（T—>lchild!=NULL)｛k--；x=PreOrder(T—>lchild,k）；｝if（T->rchild!=NULL＆&x==’#’)｛k—-;x=PreOrder(T-〉rchild， k）;}return x；｝TElemType PreOrderK(BiTree T, int k）/* 求对二叉树T先序遍历时第k个访问的结点的值。

2016级数据结构实验报告实验名称：实验一线性表——题目1学生姓名：李文超班级：2015661131班内序号：15学号：2015522147日期：2016年11月13日1.实验要求实验目的：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。

线性表存储结构（五选一）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：要求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他：可自行定义编写测试main()函数测试线性表的正确性。

2.程序分析2.1 存储结构单链表的存储：（1）链表用一组任意的存储单元来存放线性表的结点。

这组存储单元既可以是连续的，也可以是不连续的，甚至零散地分布在内存的某些位置。

（2）链表中结点的逻辑次序和物理次序不一定相同。

为了能正确表示结点间的逻辑关系，在存储每个元素值的同时，还要存储该元素的直接后继元素的位置信息，这个信息称为指针或链。

结点结构┌──┬──┐ data 域---存放结点值的数据域│data │next │ next 域---存放结点的直接后继的地址的指针域└──┴──┘单链表在内存中的存储示意地址 内存单元1000H头指针 1020H1080H10C0H2.2 关键算法分析1、关键算法：（1）头插法自然语言描述：a:在堆中建立新结点b:将a[i]写入到新结点的数据域c:修改新结点的指针域d:修改头结点的指针域。

将新结点加入链表中伪代码描述a:Node <T> * s=new Node <T>b:s->data=a[i]c:s->next=front->next;d:front->next=s（2）尾插法自然语言描述：a:在堆中建立新结点：b:将a[i]写入到新结点的数据域：c:将新结点加入到链表中d:修改修改尾指针伪代码描述a:Node <T> * s=new Node <T>b:s->data=a[i]c:r->next=s;d:r=s（3）遍历打印函数自然语言描述：a:判断该链表是否为空链表，如果是，报错b:如果不是空链表，新建立一个temp指针c:将temp指针指向头结点d:打印temp指针的data域e:逐个往后移动temp指针，直到temp指针的指向的指针的next域为空伪代码描述a: If front->next==NULL①Throw ”an empty list ”②Node<T>* temp=front->next;b:while(temp->next)c:cout<<temp->data<<" ";d:temp=temp->next;(4) 获取链表长度函数自然语言描述：a:判断该链表是否为空链表，如果是，输出长度0b:如果不是空链表，新建立一个temp指针，初始化整形数n为0c:将temp指针指向头结点d:判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return ne: 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n伪代码描述a:if ront->next==NULLb:Node<T>* temp=front->next;c:while(temp->next)d:temp=temp->next;（5）析构/删除函数自然语言描述：a:新建立一个指针，指向头结点b:判断要释放的结点是否存在，c:暂时保存要释放的结点d:移动a中建立的指针e:释放要释放的指针伪代码描述a:Node <T> * p=frontb:while(p)c:front=pd:p=p->nexte:delete front（6）按位查找函数自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，直到p为空或者j等于1①：p指向下一个结点②：j加1c:若p为空，说明第i个元素不存在，抛出异常d:否则，说明p指向的元素就是所查找的元素，返回元素地址伪代码描述a:Node <T> * p=front->next;j=1;b:while(p&&j!=1)①:p=p->next②:j++c:if(!p) throw ”error”d:return p（7）按位查找函数自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，找到这个元素或者p指向最后一个结点①：判断p指向的结点是不是要查找的值，如果是，返回j，否则p指向下一个结点，并且j的值加一c:如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息伪代码描述a:Node <T> * p=front->next;j=1;b:while(p)①: if(p->next==x) return jp=p->nextj++c:return “error”（8）插入函数自然语言描述：a:在堆中建立新结点b:将要插入的结点的数据写入到新结点的数据域c:修改新结点的指针域d:修改前一个指针的指针域，使其指向新插入的结点的位置伪代码描述a:Node <T> * s=new Node <T>;b:s-data=p->datac:s->next=p->nextd:p->next=se:p->data=x（9）删除函数自然语言描述：a:从第一个结点开始，查找要删除的位数i前一个位置i-1的结点b:设q指向第i个元素c:将q元素从链表中删除d:保存q元素的数据e:释放q元素伪代码描述a:q=p->nextb:p->next=q->nextc:x=q->datad:delete q2、代码详细分析（插入）：（1）从第一个结点开始，查找节点，使它的数据比x大，设p指向该结点：while (x>p->data) { p=p->next;}（2）新建一个节点s，把p的数据赋给s：s->data=p->data;（3）把s加到p后面：s->next=p->next; p->next=s;（4）p节点的数据用x替换：p->data=x;示意图如图所示xp->datas3、关键算法的时间复杂度：O（1)3.程序运行结果1. 流程图：2、结果截图3.测试结论：可以正确的对链表进行插入，删除，取长度，输出操作。

《数据结构》实验指导第一章实验0 C/C++程序设计一、实验基础知识二、实验案例1 学生成绩统计系统[问题描述]一个班同学的学号为1-n，输入n位同学的学号、姓名、语文、数学、英语等3门课程成绩，统计每位同学的总分后按成绩从高到低的次序输出。

[基本要求]实现成绩表的录入、总分统计、总分排序和输出。

[测试数据]对于10个同学的学号、姓名、语文、数学、英语等3门课程成绩设计实例数据[实现提示]1）用结构体设计同学记录，学号、各课程成绩和总分数据域用整型，姓名域采用字符数组；学生成绩表用数组模拟，数组大小根据实际学生数动态申请；学生成绩统计系统通过主菜单形式提供成绩表初始化、学生成绩录入、学生总分统计和排名、成绩表输出等功能。

[提高部分]1）实现成绩表的文件录入和文件保存2）实现成绩键盘录入的有效数据限制2复数计算器[问题描述]设计一个能进行复数运算的演示程序。

[基本要求]实现复数的基本运算：1）由输入的实部和虚部生成一个复数；2）求两个复数的和；3）求两个复数的差；4）求两个复数的乘积；5）求复数的实部；6）求复数的虚部[测试数据]0+0=03.1,0;4.22,8.9;输出7.32+i8.99,8;-9,8;输出i169,-8;-9,-8;输出-i16-9,8;-9,-8;输出-189,-7;-9,8;输出i9,-9;-9,8;输出-i[实现提示]将复数的实部和虚部组成结构体数据类型，利用实数的操作实现复数的操作。

[提高部分]1）实现复数的除法运算；2）求共轭复数3有理数计算器[问题描述]设计一个能进行有理数运算的演示程序。

[基本要求]实现有理数的基本运算：1）由输入的分子和分母生成一个有理数；2）求两个有理数的和；3）求两个有理数的差；4）求两个有理数的乘积；5）求有理数的分子；6）求有理数的分母[实现提示]将有理数的分子和分母组成结构体数据类型，利用整数的操作实现有理数的操作。

[提高部分]1）实现有理数的除法运算；第二章线性表一、实验基础知识二、实验案例4顺序表基本操作演示系统[问题描述]设计一个能进行顺序表基本运算的演示程序。

2016年10月高等教育自学考试全国统一命题考试数据结构导论试卷(课程代码 02142)本试卷共4页，满分l00分，考试时间l50分钟。

考生答题注意事项：1．本卷所有试题必须在答题卡上作答。

答在试卷上无效，试卷空白处和背面均可作草稿纸。

2．第一部分为选择题。

必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。

3．第二部分为非选择题。

必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。

4．合理安排答题空间。

超出答题区域无效。

第一部分选择题(共30分)一、单项选择题(本大题共10小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。

错涂、多涂或未涂均无分。

1．已知问题规模为n，则下列程序片段的时间复杂度是C2．若用计算机来模拟银行客户排队等待办理业务的情形，则所应该采用的数据结构是A．栈 B．队列 C．树 D．图3．若线性表采用链式存储结构，则适用的查找方法为A．随机查找 B．散列查找 C．二分查找 D．顺序查找4．已知指针P和q分别指向某单链表中第一个结点和最后一个结点，假设指针s指向另一个单链表中某个结点，则在S所指结点之后插入上述单链表应执行的语句为A．q→next；s→next；s→next2P； B．s→next=P；q→next=s→next；C．p→next=s→next；s→next=q； D．s→next2q；p→next2s→next；5．栈的运算特点是先进后出，元素a、b、c、d依次入栈，则不能得到的出栈序列是A．abed B．dcba C．cabd D．bcda6．在实现队列的链表结构中，其时间复杂度最优的是A．仅设置头指针的单循环链表 B．仅设置尾指针的单循环链表C．仅设置头指针的双向链表 D．仅设置尾指针的双向链表7．任意一棵二叉树的前序和后序遍历的结果序列中，各叶子结点之间的相对次序关系是A．不一定相同 B. 都相同 C．都不相同 D．互为逆序8．若某棵树的存储结构采用双亲表示法，如题8图所示，则该树的高度是A．2 B．3 C．4 D．59．无向图的邻接矩阵一定是A．对称矩阵 B．对角矩阵 C．稀疏矩阵 D．三角矩阵10．根据连通图的深度优先搜索的基本思想，如题10图所示的连通图的一个深度优先搜索的结果序列是A．123456 B．123465 C. 126345 D．16254311．用顺序查找方法对含有n个数据元素的顺序表按从后向前查找次序进行查找，现假设查找其中每个数据元素的概率不相等，那么A．该顺序表按查找概率由低到高的顺序来存储数据元素，其ASL最小B．该顺序表按查找概率由高到低的顺序来存储数据元素，其ASL最小C．ASL的大小与数据元素在该顺序表中的位置次序无关D．ASL的大小与查找每个数据元素的概率无关12．已知散列表的存储空间为T[0，…，l6]，散列函数为H(k)----k mod l7，用二次探测法解决冲突。

第4章栈和队列1.设一数列为1,2,3,4,5,6,通过栈操作,要得到顺序为3,2,5,6,4,1和1,5,4,6,2,3的输出序列是否可能,请阐述理由。

答案：(1)3,2,5,6,4,1是可能的,但1,5,4,6,2,3不可能.(2)因为5在4,2,3之前出栈,那么5出栈时,栈内状态为:5,4,3,2。

根据先进后出原则,其次序只能是5,4,3,2,不可能出现5,4,2,3,想出2时,2却被3压在下面,2不能比3先出栈,所以不可能出现1,5,4,6,2,3这种序列.2. 把1、2、3、4依次进栈（栈初始为空），任何时刻（只要栈不空），都可以出（退）栈，试写出所有可能的出栈序列（如1234）。

答案略第6章树3.对数列{3，1，7，4，2，8，5}构造出二叉排序树。

答案：3.假设一棵二叉树的先序序列为ABDEGHJCFI和中序序列为DBGEHJAC FI。

请画出该树。

答案：4.一棵二叉树后序遍历为DECBHGFA ，中序遍历为BDCEAFHG ，能不能唯一的确定一棵二叉树？如果能够，请构造此二叉树，并写出其前序遍历序列。

解答:前序遍历序列:ABCDEFGH5. 设有一组权ＷＧ＝1,4,9,16,25,36,49,64,81,100，试画出其哈夫曼树，并计算加权的路径长度。

答案：树不唯一，但加权路径长度均为1078WPL=1*7+4*7+9*6+16*5+25*4+36*3+49*3+64*3+81*2+100*2=1078试问：⑴哪个结点是根结点？⑵哪个结点是D的双亲结点？ ⑶C 的左右孩子分别是什么？ ⑷画出这棵二叉树。

答案:根结点为: A D 的双亲结点: C C 的左右孩子: 空、D7.已知信息为“ABCDBCDＢCBDBACB”，（1）请按此信息构造哈夫曼树；（2）计算哈夫曼树的加权路径长度WPL；（3）求出每一字符的最优编码；提示：统计各个字符的出现频率，构造哈夫曼树，算WPL，编码。

实验一C++语言编程一、实验目的：复习、巩固C++语言上机操作的基本技能和方法，熟悉：框图（或流程图）――代码――调试――修改――运行这一基本上机过程。

二、实验要求：1．认真阅读和掌握本实验的程序。

2. 上机运行程序。

3. 保存和打印出程序的运行结果，并结合程序进行分析。

4. 按照操作需要，打印出文件清单和运行结果。

三、实验内容：编写一个程序实现下列目标:1.从键盘输入集合A、B，长度随机，以-9999表示输入结束，集合A、B的并集和交集，从大到小输出，不能有同样的。

#include <iostream.h>void intersection(int a[],int b[],int m,int n) //求交集{for(int i=0;i<m;i++){for(int j=0;j<n;j++)if(a[i]==b[j])cout<<a[i]<<' ';}}void Union(int a[],int b[],int m,int n) //求并集{int i=0,j=0;while(i<m&&j<n){if(a[i]==b[j]){cout<<a[i]<<' ';i++;j++;}else if(a[i]>b[j]){cout<<a[i]<<' ';i++;}else{cout<<b[j]<<' ';j++;}}}int main(){int a[100]={0},b[100]={0},m,n,i,j;cout<<"请输入第一个数组中一共有多少元素:";cin>>m;cout<<"请输入第一个数组中的元素:";for(i=0;i<m;i++){cin>>a[i];if(a[i]==-9999)break;}cout<<"请输入第二个数组中一共有多少元素:";cin>>n;cout<<"请输入第二个数组中的元素:";for(j=0;j<n;j++){cin>>b[j];if(b[j]==-9999)break;}2. 设计一个100位以内的长整数加减运算的程序。