西安理工大学数据结构2000真题

第一章概论一、选择题1、研究数据结构就是研究（D ）。

A. 数据的逻辑结构B。

数据的存储结构C. 数据的逻辑结构和存储结构D。

数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。

A。

空间复杂度和时间复杂度 B. 正确性和简单性C。

可读性和文档性D。

数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。

A。

图B。

树C。

广义表D。

栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、( B )等5个特性。

A. 可执行性、可移植性和可扩充性B。

可执行性、有穷性和确定性C。

确定性、有穷性和稳定性 D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C )。

for(i=0；i<m;i++）for(j=0;j〈n；j++）a[i］[j]=i＊j；A. O(m2) B。

O（n2) C。

O（m*n) D. O（m+n)6、算法是（D ）。

A。

计算机程序 B. 解决问题的计算方法C。

排序算法 D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8），其时间复杂度表示( C ）。

A。

O（n） B. O（nlog2n) C。

O（n2） D. O （log2n)8、下面程序段的时间复杂度为（ C ）.i=1；while(i<=n）i=i*3；A. O(n）B。

O(3n) C。

O(log3n) D. O(n3）9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A. 结构B。

关系C。

运算D。

算法10、下面程序段的时间复杂度是（A ）。

i=s=0；while（s<n)｛i++；s+=i;}A. O(n) B。

O（n2）C。

O（log2n）D。

O(n3)11、抽象数据类型的三个组成部分分别为（A）。

A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是（)。

一、选择题1. 算法的计算量的大小称为计算的（ B ）。

【北京邮电大学2000 二、 3（ 20/8 分）】A．效率 B.复杂性 C.现实性 D.难度2.算法的时间复杂度取决于（ C ）【中科院计算所1998二、1（2分）】A．问题的规模 B.待处理数据的初态 C. A 和 B3.计算机算法指的是（ C），它必须具备（ B）这三个特性。

(1) A ．计算方法 B.排序方法 C. 解决问题的步骤序列D. 调度方法(2) A ．可执行性、可移植性、可扩充性 B .可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D.易读性、稳定性、安全性【南京理工大学1999一、1（2分）【武汉交通科技大学1996一、1（ 4 分）】4．一个算法应该是（B）。

【中山大学1998二、1（2分）】A ．程序B．问题求解步骤的描述C．要满足五个基本特性D．A 和 C.5.下面关于算法说法错误的是（D）【南京理工大学2000一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D.以上几个都是错误的6.下面说法错误的是（C）【南京理工大学2000一、2（1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（ 2）在相同的规模n 下，复杂度O(n) 的算法在时间上总是优于复杂度nO(2 ) 的算法（ 3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（ 4）同一个算法，实现语言的级别越高，执行效率就越低4A ． (1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（C）两大类。

【武汉交通科技大学1996一、4（2 分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（D）【。

北方交通大学2000二、1（ 2 分）】A．循环队列 B.链表 C.哈希表 D.栈9．以下数据结构中，哪一个是线性结构（D）？【北方交通大学2001一、 1（ 2 分）】A．广义表 B.二叉树 C.稀疏矩阵 D.串10．以下那一个术语与数据的存储结构无关？（ A 【）北方交通大学 2001 一、2（ 2 分）】A．栈 B.哈希表 C.线索树 D.双向链表11．在下面的程序段中，对x 的赋值语句的频度为（C）【北京工商大学2001 一、 10（ 3 分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n)B． O(n)C2Dn ．O(n )． O(log 2 )12．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与 A[j+1] 对换；其中 n 为正整数，则最后一行的语句频度在最坏情况下是（D）A. O （ n）B. O(nlogn)C. O(n3)D.O(n 2)【南京理工大学 1998 一、 1(2 分 ) 】13．以下哪个数据结构不是多型数据类型（D）【中山大学1999一、 3（1 分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（ A）是非线性数据结构【中山大学1999一、4】A．树B．字符串C．队D．栈15.下列数据中，（ C ）是非线性数据结构。

1、3个结点可构成棵不同形态的树。

2、利用直接选择排序算法对n个记录进行排序，最坏的情况下，记录交换的次数为。

3、一个图的_______表示法是唯一的，而______表示法是不唯一的。

4、一棵深度为h的满二叉树上的结点总数为，一棵深度为h的完全二叉树上的结点总数的最小值为，最大值为。

5、在一棵完全二叉树中有n个结点，对这些结点按层序编号，若一个结点编号为69，则其双亲编号为，有左孩子的条件是，其左孩子编号为。

6、二维数组M的成员是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要________个字节；M的第8列和第5行共占___________个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的________元素的起始地址一致。

7、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是________。

8、在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线性表的链式存储中，元素之间的逻辑关系是通过_________决定的。

9、n个顶点的连通图的生成树有n-1条边。

10、通常数组只有______给定一组有定义的下标，存取相应的数据__和___给定一组有定义的下标，修改相应数据元素的值_____两种运算，因此常采用__顺序_______来存储数组。

11、3个节点可以构成 5 棵不同形态的二叉树。

12、对于一棵具有n个结点的二叉树，当它为一棵完全二叉树时具有最小高度，即为∟log2n」+1，当它为一棵单支树时具有最大高度，即为n 。

13、在一棵有n个结点的完全二叉树中，对这些结点按层序编号，若一个结点编号为59，则其双亲编号为，若一个结点编号为23，则其有右孩子的条件是。

14、数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址EA开始连续存放在存储器中。

计算机专业基础综合数据结构（概论）历年真题试卷汇编2(总分：88.00，做题时间：90分钟)一、单项选择题(总题数：11，分数：22.00)1.数据元素之间的关系称为( )。

【北京理工大学2006九、2(1分)】（分数：2.00）A.操作B.结构√C.数据对象D.数据集合解析：2.(多选)一个算法具有( )等特点。

【华中科技大学2007二、17(2分)】（分数：2.00）A.有0个或多个输入量B.健壮性√C.正确性D.可行性解析：3.下面程序的时间复杂性为( )。

【南京理工大学2004一、4(1分)】for(int i=0；i（分数：2.00）A.O(n 2 )B.O(m*n) √C.O(m 2 )D.O(m+n)解析：4.在下列算法中，“x=x*2”的执行次数是( )。

【华中科技大学2006一、16(2分)】int suanfa]．(int n){int i，j，x=1;for(i=0；i（分数：2.00）A.m(n+1)／2 √B.Nlog 2 nC.n 2D.n(n一1)／2解析：5.执行下列算法suanfa2(1000)，输出结果是( )。

【华中科技大学2006一、17(2分)】void suanfa2(int n){int i=i;while(i<=n)i*=2；printf(“％d”，i);}（分数：2.00）A.2000B.512C.1024 √D.2 1000解析：6.当n足够大时下述函数中渐近时间最小的是( )。

【哈尔滨工业大学2005二、4(1分)】（分数：2.00）A.T(n)=nlog 2 n=1000log 2 nB.T(n)=nlog 2 3=1 000log 2 n √C.T(n)=n 2 =1000log 2 nD.T(n)=2nlog 2 n=1 000log 2 n解析：7.下面算法时间复杂度是( )。

【华中科技大学2006一、18(2分)】int suanfa3(int n){int i=i，s=l；while(s（分数：2.00）A.O(n) √B.O(2 2 )C.O(log 2 n)解析：8.下列函数中渐进时间复杂度最小的是( )。

2022年西安理工大学数据科学与大数据技术专业《数据库系统原理》科目期末试卷A（有答案）一、填空题1、数据的安全性是指____________。

2、完整性约束条件作用的对象有属性、______和______三种。

3、在RDBMS中，通过某种代价模型计算各种查询的执行代价。

在集中式数据库中，查询的执行开销主要包括______和______代价。

在多用户数据库中，还应考虑查询的内存代价开销。

4、SQL Server中数据完整性包括______、______和______。

5、从外部视图到子模式的数据结构的转换是由______________实现；模式与子模式之间的映象是由______________实现；存储模式与数据物理组织之间的映象是由______________实现。

6、事务故障、系统故障的恢复是由______完成的，介质故障是由______完成的。

7、在SELECT命令中进行查询，若希望查询的结果不出现重复元组，应在SEL ECT语句中使用______保留字。

8、在SQL Server 2000中，数据页的大小是8KB。

某数据库表有1000行数据，每行需要5000字节空间，则此数据库表需要占用的数据页数为_____页。

9、数据仓库是______、______、______、______的数据集合，支持管理的决策过程。

10、有两种基本类型的锁，它们是______和______。

二、判断题11、在SQL中，ALTERTABLE语句中MODIFY用于修改字段的类型和长度等，ADD用于添加新的字段。

（）12、在数据库恢复中，对已完成的事务进行撤销处理。

（）13、SQL语言有嵌入式和交互式两种使用方法。

（）14、在第一个事务以S锁方式读数据R时，第二个事务可以进行对数据R加S锁并写数据的操作。

（）15、机制虽然有一定的安全保护功能，但不精细，往往不能达到应用系统的要求。

（）16、在关系数据库中，属性的排列顺序是可以颠倒的。

第1章绪论一、判断题1.数据的逻辑结构与数据元素本身的内容和形式无关。

（√）2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。

（√）3.数据元素是数据的最小单位。

（×）4.数据的逻辑结构和数据的存储结构是相同的。

（×）5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。

（×）6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。

（√）7.数据的存储结构是数据的逻辑结构的存储映象。

（√）8.数据的物理结构是指数据在计算机内实际的存储形式。

（√）9.数据的逻辑结构是依赖于计算机的。

（×）10.算法是对解题方法和步骤的描述。

（√）二、填空题1.数据有逻辑结构和存储结构两种结构。

2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。

3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。

4.树形结构和图形结构合称为非线性结构。

5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。

6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。

7.数据的存储结构又叫物理结构。

8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。

9.线性结构中的元素之间存在一对一的关系。

10.树形结构中的元素之间存在一对多的关系。

11.图形结构的元素之间存在多对多的关系。

12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的内容。

13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。

14.算法是一个有穷指令的集合。

15.算法效率的度量可以分为事先估算法和事后统计法。

16.一个算法的时间复杂度是算法输入规模的函数。

17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。

18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（nlog2n）。

计算机2000-1、2、3、4、5数据结构考试试题参考答案一、 单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干的括号内。

每小题2分，共20分）1．B 2．B 3．B 4．A 5．A 6．B 7．A 8．C 9．C 10. D 二、判断题（判断下列各题是否正确，正确在括号内打“√”，错的打“×”。

每小题1分，共10分）1．× 2．× 3．√ 4．× 5．√ 6．× 7．× 8．× 9．× 10．× 三、填空题（每题2分，共20分） 1．P->next->next 2．2m-13．mid-1 R[mid].KEY==K 或 l>h 4．R->next->next 5．36．q->next->prior=S7．第i 列非零元素之和（第i 列非零元素个数，∑=nk aki 1）第i 行非零元素之和（第i 行非零元素个数，∑=nk aik 1）8．Ls==NULL ls=ls->link 9．Lq->front==lq->rear 10．a b e f c d g四、应用题（共36分） 1．（6分） （1）(4分)解：由题义知 m=13a)因为 h(35)=35 % 13 =9 但位置9不是35，所以又双重散列得 h1(35)=35 % 11 +1=3所以 h1=(9+1*3) % 13=12 但位置12 不是 35，所以 又双重散列得h2=(9+2*3) % 13 =2 可知，位置2 是 35 ，所以 查找35共比较了3次。

b)因为 h(20)=20 % 13 = 7 但位置7不是20，所以又双重散列得 h1(20)=20 % 11 +1=10h1=(7+1*10) % 13 =4 可知，位置4 是 20 ，所以 查找20共比较了2次。

计算机专业基础综合数据结构（集合）历年真题试卷汇编3(总分60,考试时间90分钟)2. 填空题1. 一棵含有15个关键字的4阶B树，其非叶结点数最少不能少于__________个，最多可以为__________个。

【中国科学技术大学1997二、4(4分)】2. 对于m=4(4阶)的B一树，如果根的层次为第1层，则高度为2的B一树最少要存储__________个关键字，最多可以保存__________个关键字。

【北京理工大学2005二、4(2分)】3. 具有n个关键字的B树的查找路径长度不会大于__________。

【中科院计算机1999二、2(1分)】4. 127阶B一树中每个结点最多有(1)个关键字；除根结点外所有非终端结点至少有(2)棵子树；65阶B+树中除根结点外所有结点至少有(3)个关键字；最多有(4)棵子树；【北方交通大学1999二、5(4分)】5. 设高为h的m阶B一树上共有k个关键字，则其叶子结点有__________个。

【北京交通大学2006二、8(2分)】6. 高度为h的2-3树中叶子结点的数目至多为__________。

【西安电子科技大学1999软件一、6(2分)】7. 哈希表用__________确定记录的存储位置。

【北京理工大学2005二、5(2分)】8. 在哈希造表中，不同的关键字产生同一哈希地址的现象，称为__________。

【北京理工大学2006十、6(1分)】9. 设已知n个关键字具有相同的散列函数值，并且采用线性探测再散列方法处理冲突，将这n个关键字散列到初始为空的地址空间中，一共发生了__________次散列冲突。

【北京航空航天大学2006一、9(1分)】【西安电子科技大学2001软件一、7(2分)】6. 综合题1. 设有n个值不同的元素存于顺序结构中，试问：你能否用比(2n一3)少的比较次数选出这n个元素中的最大值和最小值?若能，请说明是如何实现的；在最坏情况下，至少要进行多少次比较。

计算机专业基础综合数据结构（排序）历年真题试卷汇编2(总分：58.00，做题时间：90分钟)一、单项选择题(总题数：10，分数：20.00)1.以下序列不是堆的是( )。

【西安电子科技大学2001计算机应用一、5(2分)】（分数：2.00）A.(100，85，98，77，80，60，82，40，20，lO，66)B.(100，98，85，82，80，77，66，60，40，20，10)C.(10，20，40，60，66，77，80，82，85，98，100)D.(100，85，40，77，80，60，66，98，82，10，20) √解析：2.一组关键字为(46，79，56，38，40，84)，则利用堆排序的方法建立大顶堆的初始堆为( )。

【北京交通大学2006一、8(2分)】（分数：2.00）A.79，46，56，38，40，84B.84，79，56，38，40，46 √C.84，79，56，46，40，38D.84，56，79，40，46，38解析：3.在对，z个元素的序列进行排序时，堆排序所需要的附加存储空间是( )。

【西安电子科技大学2001计算机应用一、10(2分)】（分数：2.00）A.O(log 2 n)B.D(1) √C.O(n)D.()(nlog 2 n)解析：4.对n个记录的文件进行堆排序，最坏情况下的执行时间是多少? ( )。

【北京交通大学2001一、9(2分)】（分数：2.00）A.O(log 2 n)B.O(n)C.O(nlog 2 n) √D.O(n*n)解析：5.有一组数据(15，9，7，8，20，一1，7，4)，用堆排序的筛选方法建立的初始堆为( )。

【南京理工大学1996二、5(2分)】（分数：2.00）A.一1，4，8，9，20，7，15，7B.一1，7，15，7，4，8，20，9C.一1，4，7，8，20，1 5，7，9 √D.A，B，C均不对解析：6.归并排序中，归并的趟数是( )。