2011黑龙江省数据结构基础考资料

1、设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为(B) 注：利用公式n=n0+n1+n2、n0=n2+1和完全二叉数的特点可求出A. 349B. 350C. 255D. 3512、下列叙述中正确的是(C)A.数据库是一个独立的系统，不需要操作系统的支持B.数据库设计是指设计数据库管理系统C.数据库技术的根本目标是要解决数据共享的问题D.数据库系统中，数据的物理结构必须与逻辑结构一致3、下列关于队列的叙述中正确的是(C)A. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表4、算法的空间复杂度是指(D)A. 算法程序的长度B. 算法程序中的指令条数C. 算法程序所占的存储空间D. 算法执行过程中所需要的存储空间5、设有下列二叉树：图见书P46对此二叉树中序遍历的结果为(B)A. ABCDEFB. DBEAFCC. ABDECFD. DEBFCA6、在下列选项中，哪个不是一个算法一般应该具有的基本特征(C)A. 确定性B. 可行性C. 无穷性D. 拥有足够的情报7、在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是(D)A. 概要设计B. 详细设计C. 可行性分析D. 需求分析8、下列模式中，能够给出数据库物理存储结构与物理存取方法的是(A)A. 内模式B. 外模式C. 概念模式D. 逻辑模式9、在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送(D)A. 调用语句B. 命令C. 口令D. 消息10、按条件f对关系R进行选择，其关系代数表达式为(C)A. R|X|RB. R|X|RfC. бf(R)D. ∏f(R)11、下面不属于软件工程的3个要素的是(D)A. 工具B. 过程C. 方法D. 环境12、关系数据库管理系统能实现的专门关系运算包括(B)A. 排序、索引、统计B. 选择、投影、连接C. 关联、更新、排序D. 显示、打印、制表13、算法一般都可以用哪几种控制结构组合而成(D)A. 循环、分支、递归B. 顺序、循环、嵌套C. 循环、递归、选择D. 顺序、选择、循环14、数据库系统的核心是(B)A. 数据模型B. 数据库管理系统C. 软件工具D. 数据库15、对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为(B) 注：要牢记A. N+1B. NC. (N+1)/2D. N/216、下面不属于软件设计原则的是(C)A. 抽象B. 模块化C. 自底向上D. 信息隐蔽17、在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。

1、在Internet中，用户通过FTP可以____。

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、PC机的含义是____。

A、个人计算机B、大型机C、巨型机D、苹果机8、计算机之所以能实现自动连续运算，是由于采用了_____原理。

A、布尔逻辑B、存储程序C、数字电路D、集成电路9、在因特网上，域名各部分之间用____作为分隔符A、点B、逗号C、冒号D、分号10、计算机正常启动后，我们在屏幕上首先看到的是____A、Windows的桌面B、关闭Windows的对话框C、有关帮助的信息D、出错信息11、在编辑状态，依次打开了d1．doc、d2．doc、 d3．doc、d4．doc四个文档，当前的活动窗口是____的窗口。

A、d1．docB、d2．doc C。

d3．doc D、 d4．doc12、微型计算机的核心部件是____。

A、控制器B、存储器C、微处理器D、运算器13、下列域名中，代表非营利组织的是____。

A、.orgB、.eduC、.comD、.net14、在Windows 中，用户可以同时启动多个应用程序，在启动了多个应用程序后，用户可以按组合键____在各应用程序之间进行切换。

A、Alt+TabB、Alt+ShiftC、Ctrl+AltD、Ctrl+Esc15、系统软件的核心是____。

A、操作系统B、诊断程序C、软件工具D、语言处理程序16、在PowerPoint中，文件的扩展名默认为____。

⿊龙江⼤学数据结构考试题《数据结构课程设计》讲义⼀、表达式求值问题1.1 问题定义及设计要求表达式求值是程序设计语⾔编译中的⼀个最基本问题。

⼈们在书写表达式时通常采⽤将运算符放在两个操作数中间的“中缀”表⽰形式，称为中缀表达式。

但是这种表达式形式对计算机处理来说是不太适合的。

在计算机领域，经常将算术表达式表⽰成“后缀”表⽰形式，称为后缀表达式。

如: 中缀表达式3+2*(7-5)对应的后缀表达式为3275-*+。

要求实现（1）算数四则运算中缀表达式到后缀表达式的转换；（2）后缀表达式的求值；（3）中缀表达式的求值。

要求以字符序列的形式从终端输⼊语法正确的、不含变量的整数表达式。

要求演⽰在求值过程中运算符栈、操作数栈、输⼊字符和主要操作过程及运算结果。

要求配备菜单，含如下选项：------------------------------------------------------1.中缀表达式到后缀表达式的转换2.后缀表达式的计算3.中缀表达式的计算4.退出-------------------------------------------------------1.2 中缀表达式到后缀表达式的转换（1）问题分析假设在算术表达式中只含四种基本运算符，操作数是10以内的整数。

假设⼀个中缀表达式中没有括号（如4+2*3，它的后缀表达式为423*+）。

在扫描到中缀表达式中的2后，能⽴即输出+，因为*具有较⾼优先级，必须必须先运算，因此需先保存+。

也就是说，新扫描运算符优先级必须与前⼀个运算符的优先级做⽐较，如果新的运算符优先级⾼，就要像前⼀个运算符那样保存它，直到扫描到第⼆个操作数，将它输出后才能将该运算符输出。

因此，在转化中必须保存两个运算符，后保存的运算符先输出。

⽤计算机来实现这个转化过程，就需要⽤到能后进先出的数据结构----栈。

如果在中缀表达式中含⼩括号，那么由于括号隔离了优先级规则，它在整个表达式的内部产⽣了完全独⽴的⼦表达式。

1、采用链结构存储线性表时，其地址（ B ）。

A）必须是连续的 B）连续不连续都可以C）部分地址必须是连续 D）必须是不连续的2、有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99}。

当用二分查找法查找键值为84的结点时，经（ B ）比较后查找成功。

A) 4 B)3 C)2 D)123、下列序列中，执行第一趟快速排序后得到的序列是（ A ）。

A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b]C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]4、n个顶点的强连通图至少有（ A ）条边。

A）n B）n+1 C）n-1 D）n(n-1)5、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。

A）上三角矩阵 B) 稀疏矩阵C) 对角矩阵 D) 对称矩阵6、n个顶点，e条边的有向图的邻接矩阵中非零元素有（ C ）个。

A）n B）2e C）e D） n+e7、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。

这样的排序方法是（ A ）。

A）直接选择排序 B）直接插入排序C）快速排序 D）起泡排序8、线性表的链接实现有利于（ A ）运算。

A）插入 B）读元素C）查找 D）定位9、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=（ D ）。

A） (G) B） (D) C） C D） D10、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入一个结点的操作为（ B ）。

A）front=front->next; B） rear=rear->next;C） rear=front->next; D） front=rear->next ;11、下面程序段的时间复杂度是( A )。

更多内容尽在/第 1 章绪论课后习题讲解1. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。

【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。

【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

数据结构试卷（一）王彬一、单选题（每题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进制表示。

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

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( d ).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的元素有（ c d）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

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

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