东华理工大学数据结构A卷

东华理工大学2013 —2014 学年第二学期补考试卷数据结构与算法设计课程闭/开卷课程类别：考试/考查一、填空题：（20分，每空2分）1．一个算法的效率可分为__________________效率和空间效率。

2．当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。

相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。

3．栈和队列都是线性结构，对于栈只能在_______位置插入元素；只能在_______位置删除元素。

4．设有一空栈，现有输入序列1，2，3，4，5，经过push，push，pop，push，pop，push，push，pop，pop，pop后，输出序列是_________。

5．一个广义表为(a,(a,b,d,e),((i,j),k))，则该广义表的深度为_________。

6．对于一个高度为h的二叉树，则它最多有_______个结点。

7．对于一棵具有n个结点的二叉树，若对结点从上到下从左到右进行编号(1≤i≤n)，一个结点的编号为i，则它的左孩子结点的编号为________。

8．假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为{<a,c>, <a,e>, <c,f>, <d,c>,<e,b>, <e,d>}，则入度为1的顶点个数为_________。

二、选择题1．算法分析的两个主要方面是（）A 正确性和简明性B 空间性能和时间性能C 可读性和文档性D 数据复杂性和程序复杂性2．若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（）存储方法最节省时间。

A 单链表B 带头指针的单循环链表C 双链表D 带尾指针的单循环链表3．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A O（i） B O（1） C O（n） D O（i-1）4．一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（）。

第1章绪论一、选择题1.算法的计算量的大小称为计算的（）。

A．效率 B. 复杂性 C. 现实性 D. 难度2.算法的时间复杂度取决于（）A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性4.一个算法应该是（）。

A．程序B．问题求解步骤的描述C．数据结构+程序D．以上都不对.5.下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6.下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指随问题规模的增大，算法执行时间的增长率。

（4）空间复杂度是算法所需存储空间的量度。

A．(1) B.(1),(2) C.(1),(4) D.(3)7.从逻辑上可以把数据结构分为（）两大类。

A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8.以下与数据的存储结构无关的术语是（）。

A．循环队列 B. 链表 C. 哈希表 D. 栈9.连续存储设计时，存储单元的地址（）。

A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续10.以下属于逻辑结构的是（）。

A．顺序表 B. 哈希表 C.有序表 D. 单链表第2章线性表一、选择题1.下述哪一条是顺序存储结构的优点？（）A．存储密度大B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2.下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。

东华理工大学2012 —2013 学年第1 学期考试试卷Java程序设计课程闭课程类别：考查A1 选择题（共35分）1.What is suffix(后缀) of Java source code？（A）?A、.javaB、.classC、.txtD、.ext2. Which command can compile Java source code? ( D )?A、editB、dirC、javaD、javac3. Which identifies is illegal ( C)?A、$_$123B、_somethingC、some**nameD、you_can_al4. Which conversion (转换) is illegal ( B )?注意：byte类型的范围-128-127A、short x=1000;B、byte x=1000;C、byte x=100;D、float x=12L; 5．class example {public static void main(String args[]) {boolean b;b = (2 > 3) && (3 < 2);System.out.print("b = "+b);b = false || true ;System.out.println("b = "+b); } }What is the result?( A )A、b=false b=trueB、b=true b= falseC、b=true b= trueD、b= false b= false6. class example {public static void main(String args[]) {int i=1;a[i++]=a[i++]+2;ln(a[i++]);}} What is the result?( C)A, 4 B, 5 C 3, D,6 7．public class Example{String str=new String("good");char[]ch={'a','b','c'};public static void main(String args[]){Example ex=new Example();ex.change(ex.str,ex.ch);System.out.print(ex.str+" and ");Sytem.out.print(ex.ch); }public void change(String str,char ch[]){str="test ok";ch[0]='g'; } } What is the result?( D )A good and abcB good and gbcC test ok and abcD test ok and gbc8. Set x=1,y=2,z=3, expression :y+=z--/++x what is result ( A )A 3B 3.5C 4D 59. what is result ( A)?class example{static int a=3;public static void main(String args[]){new example().a++;new example().a+=2;System.out.println(example.a);}}A 6B 7C 4D 510. 1.class X{ ( D)2.public static void main(String args[]){3. String s1=new String(“true”);4. Boolean b1=new Boolean(true);5. if(s1.equals(b1)){6. System.out.println(“equal”);}}}A the program runs and prints nothingB the program runs and prints “equal”C An error at line 5 causes compilation to failD The program runs but aborts with an exception11.1.interface A{2. int a=3;3. void show();4.}5.class B implement A{6. void show(){}7.public static void main(String args[]){8. System.out.println(a++);}}Which lines are incorrect when the code is compiled?( C )A 5 7B 6 8C 5 6 8D 5 612 class A{int a=2;}class B extends A{int a=3;}class test{public static void main(String args[]){A g=new B(); //不能把子类的东西给父类System.out.println(g.a);}}What is result? ( B)A 2B no resultC 1D 313 what is result ( A)class A{public static void main(String args[]){try{int a=1/0;int []b={1,2};b[4]=4; }catch(ArrayIndexOutOfBoundsException e){System.out.print("vvv");}catch(ArithmeticException e){//算法异常System.out.print("rrr");}finally{System.out.println("sss");} } }A rrrvvvB rrrsssC vvvsssD sssrrr14. class A{final int i4=(int)(Math.random()*20);static final int i5=(int)(Math.random()*20);public void print(){System.out.println("i4="+i4+"i5="+i5);}public static void main(String args[]){A g1= new A();g1.print();A g2= new A();g2.print(); }}Assume i4=15 i5=16 when g1.print() method is executed . what result is displayed when g2.print() is executed( A)A 15 16B 15 17C 18 14D 15 1515.class A{void f(int x){System.out.println(x);}void f(long x){System.out.println(x);}public static void main(String args[]) {A g1= new A();g1.f(5.6); }}What is result( D )A 5.6B 5C 6D error二、翻译题20分，每小题5分1）Encapsulation（封装）is the mechanism（进程；途径）that binds （约束）together code and the data it manipulates（操纵；操作）, and keep both safe from outside interference（干扰）and misuse（滥用）.封装是结合在一起的代码和数据处理机制，并保持安全不受外界干扰和误用。

2022年东华理工大学软件工程专业《计算机系统结构》科目期末试卷A（有答案）一、选择题1、流水机器对全局性相关的处理不包括( )A.猜测法B.提前形成条件码C.加快短循环程序的执行D.设置相关专用通路2、不同系列的机器之间，实现软件移植的途径不包括( )A.用统一的高级语言B.用统一的汇编语言C.模拟D.仿真3、下列关于标量流水机的说法不正确的是（）A.可对标量数据进行流水处理B.没有向量数据表示C.不能对向量数据进行运算D.可以对向量、数组进行运算4、"一次重叠"中消除"指令相关"最好的方法是( )。

A.不准修改指令B.设相关专用通路C.推后分析下条指令D.推后执行下条指令5、输入输出系统硬件的功能对（）是透明的。

A.操作系统程序员B.应用程序员C.系统结构设计人员D.机器语言程序设计员6、非线性流水线是指( )A.一次运算中使用流水线中的多个功能段B.一次运算中要多次使用流水线中的某些功能段C.流水线中某些功能段在各次运算中的作用不同D.流水线的各个功能段在各种运算中有不同的组合7、以下说法不正确的是( )A.线性流水线是单功能流水线B.动态流水线是多功能流水线C.静态流水线是多功能流水线D.动态流水线只能是单功能流水线8、开发并行的途径有（），资源重复和资源共享。

A.多计算机系统B.多道分时C.分布式处理系统D.时间重叠9、与全相联映象相比，组相联映象的优点是( )A.目录表小B.块冲突概率低C.命中率高D.主存利用率高10、"从中间开始"设计的"中间"目前多数是在( )。

A.传统机器语言级与操作系统机器级之间B.传统机器语言级与微程序机器级之间C.微程序机器级与汇编语言机器级之间D.操作系统机器级与汇编语言机器级之间二、填空题11、Cache存贮器对应用程序员是________的。

对系统程序员是________的（填“透明”或“不透明”）12、浮点数尾数基值增大。

注意：答案请做在答题纸上，做在试卷上无效
第 1 页，共 2 页 东华理工大学2016年硕士生入学考试初试试题
科目代码： 811 ; 科目名称：《数据结构（含C 程序设计）》；（A 卷） 适用专业（领域）名称：077500、081200计算机科学与技术
一、编写程序题：（共5小题，每小题12分，共60分）
1. 某百货公司进行促销活动，对于购物价格x≥5000元的8折，5000>x≥3000元的
8.5折，3000>x≥1000的9折，否则没有折扣。

编写函数，计算对购物x 元的折后价。

2. 计算1+(1×2)+(1×2×3)+…+(1×2×3×…×n)。

3. 已知一个班1门课的成绩，计算高于平均分的学生人数所占的百分数。

4. 输入一行字符，统计出26个大小写英文字母的个数。

5. 从键盘输入一串字符，除了空格，逐个把这些字符写入磁盘文件中，直到用户输入一个‘@’为止。

二、综合过程题：（共9小题，每小题10分，共90分）
1.设结点的类型如下：
typedef struct node
{ char data;
struct node *next;
}linklist;
编写建立带头结点的单链表的函数,结点值从键盘输入，当输入为‘#’时结束。

2.已知顺序栈的结构定义如下，编写出栈的函数。

typedef struct
{ int d[100];
int top;
}sqstack;
3.已知二叉树如下图，写出其前、中、后续的遍历结果。

2022年东华理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。

A.n*nB.n(n+1)C.n/2D.n*(n-1)2、下列说法不正确的是（）。

A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。

A.单链表B.双向链表C.单循环链表D.顺序表4、动态存储管理系统中，通常可有（）种不同的分配策略。

A.1B.2C.3D.45、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.2341566、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）8、在下述结论中，正确的有（）。

①只有一个结点的二叉树的度为0。

②二叉树的度为2。

③二叉树的左右子树可任意交换。

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

南京邮电学院 2004/2005 学年第二学期期末数据结构A 试题纸 (A卷)班级 ____ 学号 ___ 姓名 __ 得分 __一、单项选择题（每小题2分，共20分）1.一个栈的输入序列为1,2,3,4，下面哪一个序列不可能是这个栈的输出序列？（）A. 1，3，2，4B. 2，3，4，1C. 4，3，1，2D. 3，4，2，12.循环队列顺序存储在一维数组q中，数组的允许长度是MaxSize。

教材上采用在循环队列中至少保留一个空闲元素的方法来区分空队列和满队列。

按照教材所述方法，判断队列为满的条件是（）A. front= =rearB. (front+1)%MaxSize= =rearC. (rear+1)%MaxSize= =frontD. front+rear= =MaxSize3.中缀表达式(A-B*C)/D+E的后缀形式是（）A. ABC*-D/E+B. ABC*-D/+EC. ABC*-DE/+D. A-BC*D/E+4.对下列哪种二叉树作中序遍历必将得到一个树中结点的非降有序序列( )。

A．AVL搜索树 B．哈夫曼树 C. 完全二叉树 D. 胜方树5.适用于对半搜索的表的存储方式及元素排列要求为( )A．链接存储，元素无序 B．链接存储，元素有序C．顺序存储，元素无序 D．顺序存储，元素有序6.下面关于m阶B-树和m阶B+树的叙述中，不正确的是（）A．B-树和B＋树每个非叶结点最多有m个孩子B．B-树和B＋树每个非叶结点至少有⎡m/2⎤个孩子C. B-树和B＋树的根结点至少有两个关键字D. B-树和B＋树都能有效地支持随机检索7.设有n个顶点e条边的AOV网采用邻接表存储，则相应的拓扑排序算法的时间复杂度为（）A. O(n2)B.O(e)C.O(n)D.O(n+e)8．下列说法中错误的是（）A.n个结点的树的各结点度数之和为n-1B.n个结点的无向图最多有n*(n-1)条边C.用邻接矩阵存储图时所需存储空间大小仅与图的顶点数有关D.用邻接表存储图时所需存储空间大小与图的顶点数和边数都相关9．下列何种排序算法的比较次数与元素的初始排列状态无关？（ D ）A. 直接插入排序B.起泡排序C.快速排序D.简单选择排序10．下列关于文件的说法中，不正确的是（ A ）。

数据结构(本)(网教)202301-模拟卷注：找到所考试题直接看该试题所有题目和答案即可。

查找按键：Ctrl+F超越高度一、单选题(共10题，20分)1、设循环队列中数组的下标范围是l~n,其头尾指针分别尾f、r,则队列中元素的个数为().A、r-fB、r-f+1C、(r-f+1)modnD、(r-f+n)modn正确答案：D2、以下哪一个不是队列的基本运算？A、从队尾插入一个新元素B、从队列中删除第i个元素C、判断一个队列是否为空D、读取队头元素的值正确答案：B3、有一个有序表｛1,3,9,12,32,41,62,75,77,86,95,100),当二分查找值为86的关键字时,需要比较的次数是()。

A、2B、3C、4D、5正确答案：C4、栈S最多能容纳4个元索。

现有6个元索按A、B、C、D、E、F的顺序进栈,问下列哪一个序列是可能的出栈序列？Λ.E、D、C、B、A、FB.B、C、E、F、A、DC.C、B、E、D、A、FD.A、D、F、E、B、C正确答案：C5、n个顶点的无向连通图至少有()条边。

A、n-1B、nC、n+1D、2n正确答案：A6、设有IOOOO个无序元索,希望用较快速度挑选出其中前15个最大元素,采用()方法最好.A、直接插入排序B、堆排序C、快速排序D、归并排序正确答案：B7、已知一棵二叉排序树,通过()可以得到结点的有序序列。

A、前序遍历B、中序遍历C、后序遍历D、线索化正确答案：B8、S="A;/document/Mary.doc",则的字符定位的位置为().A、2B、3C、12D、11正确答案：B9、假设有60行70列的二维数组a[b∙∙60,1…70]以列序为主序顺序存储,其基地址为10000,每个元索占2个存储单元,那么第32行第58列的元素a[32,58]的存储地址为()。

(无第。

行第0列元素)A、16902B、16904C、14454D、答案A,B,C均不对正确答案：A10、具有36个结点的完全二叉树的深度为()。

一、选择题（每空2分，共20分）1、设语句x++的时间是单位时间，则以下语句的时间复杂度为（B）for(i=1; i<=n; i++)for(j=i; j<=n; j++)x++;A.O(1)B.O(n2)C.O(n)D.O(n3)2、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（C）存储方式最节省运算时间。

(A) 双链表(B) 单链表(C) 顺序表(D) 单循环链表3、若长度为n的线性表采用顺序存储结构，在其第i（1≤i≤n+1）。

个位置插入一个新元素的算法的时间复杂度为（C）A．O(0) B．O(1) C．O(n) D．O(n2)4、若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是n，则第i个输出元素是（D）A. 不确定B.n-iC. n-i-1D. n-i+15、设有广义表D=（a，b，D），其长度为（C）A.1B.2C.3D.无穷6、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（C）A．4 B．5 C．6 D．77、在有n个叶子节点的哈夫曼树中，其节点总数为（D）A、不确定B、2nC、2n+1D、2n-18、要联通一个具有n个顶点的无向图中，要连通全部顶点至少需要( A)条边。

A.n-1B.nC.n+1D.2n9、在一个具有ｎ个顶点和ｅ条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（D）Ａ．ｎＢ．ｎ×ｅＣ．ｅＤ．２×ｅ10、下列排序方法中，哪一个是稳定的排序方法？（A）A．直接插入排序B．希尔排序C．堆排序D．快速排序二、填空题（每空2分，共20分）1、线性表是一种线性结构,一个线性表中的所有元素应与结点之间存在一对一的关系2、一个顺序表的第一个元素的存储地址是2000，若每个元素的所占存储空间长度为5，则第8个元素的存储地址是20353、在表长为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，插入的新元素作为第i个元素，则涉及到的元素的移动次数为n-i+14、对于一单链表L（L为头指针，且结点的后继指针分量为next），其p结点（p为链表中某结点的指针）既不是第一个结点，也不是最后一个结点，在p结点后插入s结点（s为某结点的指针）的语句序列是s->next=p->next; p->next=s;5、设有广义表D=（（a，b），（c，d））则Head（D）=（a，b）Tail（D）=（c，d）6、设F 和R 分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为F==R。

注意：答案请做在答题纸上，做在试卷上无效
第 1 页，共 2 页 东华理工大学2016年硕士生入学考试初试试题
科目代码： 811 ; 科目名称：《数据结构（含C 程序设计）》；（A 卷） 适用专业（领域）名称：077500、081200计算机科学与技术
一、编写程序题：（共5小题，每小题12分，共60分）
1. 某百货公司进行促销活动，对于购物价格x≥5000元的8折，5000>x≥3000元的
8.5折，3000>x≥1000的9折，否则没有折扣。

编写函数，计算对购物x 元的折后价。

2. 计算1+(1×2)+(1×2×3)+…+(1×2×3×…×n)。

3. 已知一个班1门课的成绩，计算高于平均分的学生人数所占的百分数。

4. 输入一行字符，统计出26个大小写英文字母的个数。

5. 从键盘输入一串字符，除了空格，逐个把这些字符写入磁盘文件中，直到用户输入一个‘@’为止。

二、综合过程题：（共9小题，每小题10分，共90分）
1.设结点的类型如下：
typedef struct node
{ char data;
struct node *next;
}linklist;
编写建立带头结点的单链表的函数,结点值从键盘输入，当输入为‘#’时结束。

2.已知顺序栈的结构定义如下，编写出栈的函数。

typedef struct
{ int d[100];
int top;
}sqstack;
3.已知二叉树如下图，写出其前、中、后续的遍历结果。

一、编写程序题：（共 5 小题，每小题 12 分，共 60 分）
1. 铁路托运行李，从甲地到乙地，设规定每张客票托运费计算方法是：行李重量不超 过 50 千克时，每千克 0.25 元；超过 50 千克而不超过 100 千克时，其超过部分每千克 0.35 元；超过 100 千克时，其超过部分每千克 0.45 元。编写函数，根据行李重量，返 回托运的费用。 2. 计算 1-(1/3)+(1/5)-(1/7)…前 n 项之和。 3. 计算 N 个实数的方差。
typedef struct N { int d; struct N *next; }Link;
写出统计结点值小于给定值的结点数的函数。 2.已知队列的结构定义如下
typedef struct { char d[100]; int front; int rear; } sequeue;
编写入队的函数。
东华理工大学
考研专业课初试真题
硕士研究生入学考试专业课初试真题
注意：答案请做在答题纸上，做在试卷上无效
东华理工大学 2017 年硕士生入学考试初试试题 科目代码： 811 ; 科目名称：《数据结构（含 C 程序设计）》；（A 卷） 适用专业（领域）名称：077500、081200 计算机科学与技术
3.已知二叉树中序遍历为 CBEDFAGH,后序遍历为 CEFDBHGA，画出该二叉树。 4．已知一个无向图如下，画出它的邻接矩阵及邻接表。
第 1 页，共 2 页
注意：答案请做在答题纸上，做在试卷上无效
1
2
3
4
5
5．对下图以 A 为起点进行深度优先与广度优先遍历（在相同条件下，先遍历排在前面 的字母）。
为平均值 4. 编写函数,实现 strlen 计算字符串长度的功能。 5. 已知一个字符串的文本文件 data.txt 存放在当前文件目录下，从文件中读入字符 串放入字符数组中，并将大写字母(ASCII：65-90)转为小写字母(ASCII：97-122)。

delete fence;
}
}
public:
LList(int size=DefaultListSize) { init(); }
~LList() { removeall(); } // Destructor
bool insert(const Elem&item);
………………………..
};
其中insert函数为插入函数，它将元素item插入到fence位置后，如果插入成功，则函数返回true，否则返回为false，写出insert函数的实现。
bool pop(Elem& it)//出栈函数，将栈顶元素出栈并赋值给it，如果出栈成功，则函数返回为true，否则函数返回为false
bool isEmpty()//判断栈是否为空函数，如果栈为空，则函数返回为true，否则返回为false
队列ADT的函数有：
bool enqueue(const Elem& it)//入队函数，将元素it入队，如果入队成功，函数返回为true，否则返回为false
fence = tail = head = new Link<Elem>;
leftcnt = rightcnt = 0;
};
void removeall() { // Return link nodes to free store
while(head != NULL) {
fence = head;
head = head->next;
一、填空题（20分，每题2分）
1、线性表是一种典型的_________结构。
2、在一个长度为n的顺序表中删除第i个元素，则需移动______个元素。

东华理工大学2021 —2021学年第 一 学期考试模拟试卷 A一、 填空题〔50分〕1、数据构造是一门研究非数值计算的程序设计问题中的 数据元素 以及它们之间 关系 和运算等的科学。

〔2分〕2、数据构造的类型通常分为： 集合、线性构造、树形构造、图状构造或网状构造 ；从逻辑上可以把它们分成： 线性构造和非线性构造 。

3、数据的 逻辑构造 只抽象反映数据元素的 逻辑关系 ；数据的 存储〔物理〕构造 是数据的逻辑构造 在计算机存储器中的实现 。

4、算法分析的目的是分析算法的 效率以求改良 ，算法分析的两个主要方面是 空间复杂度和时间复杂度 。

A5、计算机算法是解决问题的 有限运算序列 ，它必须具备 输入、输出、确定性、有穷性和稳定性 等5个方面的特性。

6、线性构造中元素之间的关系存在 一对一 关系，树形构造中元素之间的关系存在 一对多 关系，图形构造中元素之间的关系存在 多对多 关系。

7、试写出以下算法的时间复杂度i=s=0while (s<n) {i++;s += i;}7、试写出以下算法的时间复杂度i = 1 while( i <= n) )(n Oi = i*2O(log2n)8、抽象数据类型的定义由三元组来定义：(D,S,P)其中，D是数据对象， S是D上的关系集，P是对D的根本操作集。

9、写出抽象数据类型线性表的定义ADT List{数据对象：D={ai | ai ∈Elemset, i=1,2,…,n,n≥0}数据关系：R={< ai-1 , ai> | ai-1 , ai ∈D, i=2,…,n}根本操作：InitList(&L) //构造一个空的线性表LDestroyList(&L) //消毁线性表LListLength(L) //返回L中数据元素的个数ListInsert(&L,i,e) // 1 ≤ i ≤ ListLength(L)+1,在L中第i个位置之前插入数据元素e,L长度加1ListDelete(&L,i,&e) // 1 ≤ i ≤ ListLength(L),删除L中的第i个元素，并用e 返回ListTraverse(L,visit()) //依次对L的每个元素调用函数visit()…………} ADT List10、指出线性表顺序存储、链式存储构造的优缺点。

数据结构A卷以及答案-考试⽤华东交通⼤学2012—2013学年第⼀学期考试卷试卷编号：（A ）卷数据结构课程课程类别：必考⽣注意事项：1、本试卷共5页，总分100分，考试时间120分钟。

2、考试结束后，考⽣不得将试卷、答题纸和草稿纸带出考场。

⼀、选择题(每题2分，共20分)1、在⼀个链队列中，若f ，r 分别为队⾸、队尾指针，则插⼊s 所指结点的操作为( )(A) f->next=c ；f=s (B) r->next=s ；r=s (C) s->next=r ；r=s (D) s->next=f ；f=s 2、下⾯程序的时间复杂度为（）for(i=0;ifor(j=0;jA[i][j]=i*j;(A) O(M2) (B) O(N2) (C) O(M*N) (D) O(M+N)3、设⾼度为h 的⼆叉树上只有度为0和度为2的结点，则此类⼆叉树中所包含的结点数⾄少为： ( )(A) 2h (B) 2h-1 (C) 2h+1 (D) h+1 4、设指针变量p 指向单链表中结点A ，若删除单链表中结点A ，则需要修改指针的操作序列为（）。

(A) q=p->next ；p->data=q->data ；p->next=q->next ；free(q)； (B) q=p->next ；q->data=p->data ；p->next=q->next ；free(q)； (C) q=p->next ；p->next=q->next ；free(q)； (D) q=p->next ；p->data=q->data ；free(q)；5、含N 个顶点的连通图中的任意⼀条简单路径，其长度不可能超过( )(A) 1(B) N/2 (C) N-1 (D)N6、设⼀组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的⼀趟快速排序结束后的结果为( )。

一、判断(共计40分,每题2.5分)1、线性表中的所有元素都有一个前驱元素和后继元素。

（）A. 正确B. 错误参考答案：【B】2、入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。

( )A. 正确B. 错误参考答案：【A】3、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。

（）A. 正确B. 错误参考答案：【A】4、若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。

( )A. 正确B. 错误参考答案：【A】5、如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。

（）A. 正确B. 错误参考答案：【A】6、图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。

（）A. 正确B. 错误参考答案：【A】7、不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。

（）A. 正确B. 错误参考答案：【A】8、哈夫曼树中没有度数为1的结点。

（）A. 正确B. 错误参考答案：【A】9、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。

（）A. 正确B. 错误参考答案：【A】10、调用一次深度优先遍历可以访问到图中的所有顶点。

（）A. 正确B. 错误参考答案：【B】11、设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。

（）A. 正确B. 错误参考答案：【A】12、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。

（）A. 正确B. 错误参考答案：【B】13、带权无向图的最小生成树是唯一的。

（）A. 正确B. 错误参考答案：【B】14、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。

（）A. 正确B. 错误参考答案：【A】15、子串“ABC”在主串“AABCABCD”中的位置为2。

( )A. 正确B. 错误参考答案：【A】16、对链表进行插入和删除操作时不必移动链表中结点。

数据结构（本）模拟卷1一、填空题（共10题,每题1分,共10分）1. 图的深度优先遍历类似于树的________遍历。

（1分）★标准答案：1. 先序;2. 有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的________。

（1分）★标准答案：1. 出度;3. 具有n个顶点的有向图最多有________________________条边。

（1分）★标准答案：1. n（n-1）;4. 设一棵完全二叉树具有1000个结点，则此完全二叉树有____________个叶子结点，有____________个度为2的结点，有____________个结点只有非空左子树，有____________个结点只有非空右子树。

（1分）★标准答案：1. 500;2. 499;3. 1;4. 0;5. 图的广度优先遍历类似于树的________遍历。

（1分）★标准答案：1. 层次;6. 有8个结点的无向图最多有________条边。

（1分）★标准答案：1. 28;7. 由树转换为二叉树，其根节点的右子树总是________。

（1分）★标准答案：1. 为空;8. 设有两个串p和q，求q在p中首次出现的位置的运算称作________________。

（1分）★标准答案：1. 子串定位;9. 已知二维数组A[20][10]采用行序为主方式存储，每个元素占2个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的存储地址是________________。

（1分）★标准答案：1. 1168;10. 队列是一种先进先出的线性表，允许插入的一端称为________。

（1分）★标准答案：1. 队尾;二、单选题（共10题,每题2分,共20分）1. 判断线索二叉树中某结点p没有左孩子的条件是（）。

（2分）A.p!=nullB.p->lchild!=nullC.p->ltag=0D.p->ltag=1★标准答案：D2. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。

华东理工大学2020年春季数据结构（本）网上作业1华东理工大学2020年春季数据结构（本）网上作业1一、单选题1.(5分)设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好采用（）排序法。

A.冒泡排序B.快速排序C.堆排序基数排序纠错得分：5收起解析答案C解析2.(5分)具有n个顶点的有向图最多有（）条边。

A.nB.n(n-1)C.n(n+1)D.n2纠错得分：5收起解析答案B解析3.(5分)在数据结构中，从逻辑上可以把数据结构分成（）。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构纠错得分：5收起解析答案C解析4.(5分)设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如右图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i≤j), 在一维数组B 中下标k的值是：( )。

A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j纠错得分：0收起解析答案A解析5.(5分)设有100个元素，用折半查找法进行查找时，最大比较次数为（）。

A.25B.50C.10D.7纠错得分：5收起解析答案D解析6.(5分)在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。

A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B.在第i个结点后插入一个新结点（1≤i≤n）C.删除第i个结点（1≤i≤n）D.将n个结点从小到大排序纠错得分：5收起解析答案A解析7.(5分)如果二叉树中某结点p->rtag=1，则在对该二叉树按照某种次序进行线索化时，该指针域指向该结点的（）。

A.左孩子B.右孩子C.遍历前驱D.遍历后继纠错得分：5收起解析答案D解析8.(5分)设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第( )次匹配成功。