东华理工大学数据结构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.已知二叉树如下图，写出其前、中、后续的遍历结果。