2011广东省数据结构与算法一点通科目一

11年数据结构试卷（无答案）一选择1、下列程序段的时间复杂度为（）。

k=0;for(i=0; i<10; i++)k++;A．O(1) B．O(logn) C．O(n) D．O(n )2、已知在一个单链表中，q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入 s 结点，则执行语句（）。

A．s->next=p->next; p->next=s;B. p->next=s->next; s->next=p;C．q->next=s; s->next=p;D. p->next=s; s->next=q;3、若用一个长度为 6 的数组来实现循环队列，且当前 front 和 rear 的值分别为 4 和 1，则该队列的长度是（）。

A．2 B．3 C．4 D．64、稀疏矩阵的常用压缩方法有两种，即（）。

A. 二维数组和三维数组B. 三元组顺序表和散列表C. 三元组顺序表和十字链表D. 十字链表和散列表5、在有向图的拓扑序列中，若顶点 a 在顶点 b 之前，则下列情形不可能出现的是（）。

A. G 中有弧<a, b>B. G 中有一条从 a 到 b 的路径C. G 中没有弧<a, b>D. G 中有一条从 b 到 a 的路径6、具有 35 个结点的完全二叉树的深度为（）。

A．5 B．6 C．7 D．87、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到查找表中。

这种方式主要适合于（）。

A．动态查找表 B．静态查找表C．静态查找表与动态查找表 D．静态查找表或动态查找表 8、二分查找要求被查找的表是（）。

A．键值有序的链表 B．链表但键值不一定有序C．键值有序的顺序表 D．顺序表但键值不一定有序9、若在排序中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较，将其放入已排序序列的正确位置，则该方法称为（）。

第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

4．存储结构由哪两种基本的存储方法实现？5．选择题（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．栈6．试分析下面各程序段的时间复杂度。

（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

模拟考试科目一带答案一、单项选择题（每题2分，共10题）1. 以下哪个选项是计算机科学的基础概念？A. 人工智能B. 算法C. 网络D. 数据库答案：B2. 在计算机编程中，哪种数据结构允许随机访问元素？A. 链表B. 数组C. 栈D. 队列答案：B3. 计算机操作系统的主要功能不包括以下哪一项？A. 管理硬件资源B. 提供用户界面C. 实现多任务处理D. 进行数据加密答案：D4. 以下哪个选项不是计算机编程语言？A. PythonB. JavaC. SQLD. HTML答案：D5. 在计算机科学中，什么是二进制？A. 一种编程语言B. 一种加密方法C. 一种数字系统D. 一种网络协议答案：C6. 以下哪个选项是计算机存储的基本单位？A. 字节B. 千字节C. 兆字节D. 吉字节答案：A7. 计算机病毒的主要传播途径不包括以下哪一项？A. 电子邮件B. 软件下载C. 社交媒体D. 纸质书籍答案：D8. 在计算机科学中，什么是算法的复杂度？A. 算法的运行时间B. 算法的内存使用量C. 算法的步骤数量D. 算法的输入数据大小答案：A9. 以下哪个选项是计算机硬件的组成部分？A. 操作系统B. 中央处理器C. 编程语言D. 数据库管理系统答案：B10. 计算机科学中的“面向对象编程”主要关注什么？A. 程序的功能B. 程序的效率C. 程序的结构D. 程序的可读性答案：C二、多项选择题（每题3分，共5题）1. 以下哪些是计算机操作系统的常见类型？A. WindowsB. macOSC. LinuxD. Android答案：A, B, C, D2. 计算机编程中的控制结构包括哪些？A. 顺序结构B. 选择结构C. 循环结构D. 并行结构答案：A, B, C3. 以下哪些是计算机存储设备的类型？A. 硬盘B. 固态硬盘C. 内存D. 光盘答案：A, B, C, D4. 计算机科学中的算法设计需要考虑哪些因素？A. 效率B. 可读性C. 可扩展性D. 可维护性答案：A, B, C, D5. 计算机硬件的组成部分包括哪些？A. 中央处理器B. 内存C. 输入设备D. 输出设备答案：A, B, C, D结束语：以上是模拟考试科目一的试题及答案，希望对你有所帮助。

数据结构与算法模拟习题（附参考答案）一、单选题（共86题，每题1分，共86分）1.具有5个顶点的有向完全图有多少条弧？A、16B、20C、25D、10正确答案：B2.下列程序的时间复杂度为（）。

i = 0; s = 0;while(s < n){i++;s = s + i;}A、Θ(n)B、Θ(1)C、Θ(n2)D、Θ(n½)正确答案：D3.栈和队列的共同点是（）。

A、没有共同点B、只允许在端点处插入和删除元素C、都是先进后出D、都是先进先出正确答案：B4.下面描述中正确的为( )。

A、线性表的逻辑顺序与物理顺序总是一致的B、线性表的顺序存储表示优于链式存储表示。

C、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

D、二维数组是其数组元素为线性表的线性表。

正确答案：C5.对N个不同的数据采用冒泡算法进行从大到小的排序，下面哪种情况下肯定交换元素次数最多？A、从大到小排好的B、元素无序C、元素基本有序D、从小到大排好的正确答案：D6.表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。

A、3, 2, 8；( * ^ -B、3, 2, 4, 2, 2；( * ^ ( -C、3, 2, 4, 1, 1；( ^ ( + -D、3, 2, 8；( * ^ ( -正确答案：D7.二叉树的高度若根节点为高度1，一棵具有 1025 个结点的二叉树的高度为▁▁▁▁▁ 。

A、10～1024 之间B、11～1025 之间C、10D、11正确答案：B8.数据采用链式存储结构时，要求( )A、每个节点占用一片连续的存储区域B、所有节点占用一片连续的存储区域C、节点的最后一个数据域一定是指针类型D、每个节点有多少个后继就设多少个指针域正确答案：A9.在N个结点的顺序表中，算法的时间复杂度为O(1)的操作是：A、将N个结点从小到大排序B、删除第i个结点（1≤i≤N）C、访问第i个结点（1≤i≤N）和求第i个结点的直接前驱（2≤i≤N）D、在第i个结点后插入一个新结点（1≤i≤N）正确答案：C10.将元素序列{18, 23, 4, 26, 31, 33, 17, 39}按顺序插入一个初始为空的、大小为13的散列表中。

1、串的逻辑结构与（ D ）的逻辑结构不相同。

A）线性表 B）栈C）队列 D）集合2、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A) 单链表 B) 仅有头指针的单循环链表C) 双链表 D) 仅有尾指针的单循环链表3、线性表的链接实现有利于（ A ）运算。

A）插入 B）读元素C）查找 D）定位4、设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（ B ）。

A）3，2，5，6，4，1 B）1，5，4，6，2，3C）2，4，3，5，1，6 D）4，5，3，6，2，15、链式存储的存储结构所占存储空间（ A ）。

A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B）只有一部分，存放结点值C）只有一部分，存储表示结点间关系的指针D）分两部分，一部分存放结点值，另一部分存放结点所占单元数6、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=（ D ）。

A） (G) B） (D) C） C D） D7、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n)),Tn表示式中记号O表示（ A ）。

A）一个数量级别 B）一个平均值C）一个最大值 D）一个均方值8、设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列是（ C ）。

A） A, B, C, D, EB） B, C, D, E, AC） E, A, B, C, DD） E, D, C, B, A9、下面程序段的时间复杂度是( A )。

s =0;for( i =0; i<n; i++)for(j=0;j<n;j++)s +=B[i][j];sum = s ;A） O(n2) B） O(n)C） O(m*n) D）O(1)10、二叉树第i(i≥1)层上至多有（ C ）结点。

科目一模拟考试题一、选择题1. 下列哪项不是程序设计的步骤？A. 分析问题B. 编写程序C. 测试和调试D. 设计结构2. C语言的标准输入函数是？A. scanf()B. printf()C. gets()D. puts()3. 计算机网络模型中，不包括哪一层？A. 应用层B. 传输层C. 执行层D. 网络层4. 在计算机中，文件存储是以什么单位进行的？B. 比特C. 千兆字节D. 千字节5. 以下不属于常见计算机外设的是？A. 鼠标B. 打印机C. 显卡D. 锅炉二、判断题6. 数据结构是一种具体的数据形式或数据类型。

A. 对B. 错7. Linux是一种闭源操作系统。

A. 对B. 错8. 层次化设计是一种常见的程序设计方法。

B. 错9. IPv6地址一般比IPv4地址长。

A. 对B. 错10. 多线程在操作系统中可以提高程序运行效率。

A. 对B. 错三、简答题11. 请简述什么是算法？12. 请简要介绍一下TCP/IP协议族。

13. 简要描述一下计算机内存的类型和作用。

14. 什么是数据库管理系统（DBMS）？简要说明其作用。

15. 请简述一下操作系统的功能。

四、编程题16. 编写一个C语言程序，实现输入两个整数，输出其中较大的一个数。

17. 编写一个Python程序，实现将一个列表进行倒序排序。

五、综合题18. 请根据以下条件设计一个简单的数据库表结构：- 表格名称为“学生信息表”- 包含字段：学生姓名、学生年龄、所在班级、联系方式19. 一份文档文件经过多次修改，可能出现什么问题？如何避免这些问题？20. 如何避免在程序设计过程中出现逻辑错误？请给出几条建议。

以上就是科目一模拟考试题的全部内容，希望大家能够认真答题，做到最好的水平。

祝各位考试顺利！。

数据结构试卷（一）一、单选题（每题2 分，共20分）1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．6965.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：_________、_________、_________和_________。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。