北航10秋学期《算法与数据结构》模拟题一

北航《算法与数据结构》在线作业一单选题一、单选题（共 25 道试题，共 100 分。

）1. 排序方法中,从未排序序列中依次取出元素与己排序序列(初始时为空)中的元素进行比较,将其放入己排序序列的正确位置上的方法,称为（）A. 希尔排序B. 起泡排序C. 插入排序D. 选择排序-----------------选择：C2. 设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好（）排序法。

A. 起泡排序B. 快速排序C. 堆排序D. 基数排序-----------------选择：B3. 以下说法正确的是 ( )A. 因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况B. 因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况C. 对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”D. 对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。

-----------------选择：A4. 对于数据结构课程的主要内容，以下解释正确的是A. 数据结构的定义，包括逻辑结构、存储结构和基本运算集B. 数据结构的实现，包括存储实现、运算实现和基本运算集C. 数据结构的评价和选择，包括逻辑结构的选择、基本运算集的选择和存储选择D. 以上说法均不正确-----------------选择：C5. 堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|_n/2_|,满足( )A. ki≤k2i≤k2i+1B. ki<k2i+1<k2iC. ki≤k2i且ki≤k2i+1(2i+1≤n)D. ki≤k2i 或ki≤k2i+1(2i+1≤n)-----------------选择：C6. 某二叉树结点的前序序列为E、A、C、B、D、G、F，中序遍历为A、B、C、D、E、F、G。

该二叉树结点的后序序列为 ( )。

A. B,D,C,A,F,G,EB. B,D,C,F,A,G,EC. E,G,F,A,C,D,B。

数据结构与算法模考试题（含参考答案）一、单选题（共100题，每题1分，共100分）1、某公司秘书小莉经常需要用Word编辑中文公文，她希望所录入的正文都能够段首空两个字符，最简捷的操作方法是：A、在每次编辑公文前，先将“正文”样式修改为“首行缩进 2 字符”。

B、每次编辑公文时，先输入内容然后选中所有正文文本将其设为“首行缩进 2 字符”。

C、在一个空白文档中将“正文”样式修改为“首行缩进 2 字符”，然后将当前样式集设为默认值。

D、将一个“正文”样式为“首行缩进 2 字符”正确答案：C2、现代微型计算机中所采用的电子元器件是：A、大规模和超大规模集成电路B、电子管C、晶体管D、小规模集成电路正确答案：A3、图书馆管理系统中实体图书和实体借阅人之间的联系是A、1：1B、1：NC、M：ND、N：1正确答案：C4、计算机网络最突出的优点是：A、资源共享和快速传输信息B、高精度计算和收发邮件C、运算速度快和快速传输信息D、存储容量大和高精度正确答案：A5、在 Excel 工作表单元格中输入公式时，F$2 的单元格引用方式称为：A、绝对地址引用B、交叉地址引用C、混合地址引用D、相对地址引用正确答案：C6、域名代码 MIL 表示：A、政府机关B、国际组织C、商业组织D、军事部门正确答案：D7、以下对 Excel 高级筛选功能，说法正确的是：A、高级筛选之前必须对数据进行排序B、利用“数据”选项卡中的“排序和筛选”组内的“筛选”命令可进行高级筛选C、高级筛选通常需要在工作表中设置条件区域D、高级筛选就是自定义筛选第 6 组正确答案：C8、软件工程的三要素是A、方法、工具和过程B、方法、工具和文档第 47 组C、方法、工具和环境D、方法、平台和管理正确答案：A9、字长是计算机的一个重要指标，在工作频率不变和 CPU 体系结构相似的前提下，字长与计算机性能的关系是：A、字长越长，计算机的数据处理速度越快B、字长越短，计算机的数据处理速度越快C、字长表示计算机的存储容量大小，字长越长计算机的读取速度越快D、字长越短，表示计算机的并行能力越强正确答案：A10、下面描述错误的是A、类中包含数据（属性）和方法（或操作）B、类中包含对数据的操作（方法）C、类是对象的实例D、类具有抽象性第 49 组正确答案：C11、在数据库的三级模式中,可以有任意多个A、模式B、内模式（物理模式）C、外模式（用户模式）正确答案：C12、以下关于计算机病毒的说法，不正确的是：A、计算机病毒一般会寄生在其他程序中B、计算机病毒一般会传染其他文件C、计算机病毒一般会具有自愈性D、计算机病毒一般会具有潜伏性正确答案：C13、CPU 的参数如 2800MHz，指的是：A、CPU 的速度B、CPU 的大小C、CPU 的时钟主频D、CPU 的字长正确答案：C14、设栈与队列初始状态为空。

数据结构与算法同步训练模拟试题及答案解析(1/43)选择题第1题下列叙述中正确的是()。

A.循环队列是队列的一种链式存储结构B.循环队列是队列的一种顺序的存储结构C.循环队列是非线性结构D.循环队列是一种逻辑结构下一题(2/43)选择题第2题算法的有穷性是指()。

A.算法程序的运行时间是有限的B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的D.算法只能被有限的用户使用上一题下一题(3/43)选择题第3题算法的空间复杂度是指()。

A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数上一题下一题(4/43)选择题第4题定义无符号整数类为UInt，下面可以作为类UInt实例化值的是()。

A.-369B.369C.0.369D.整数集合{1,2,3,4,5}上一题下一题(5/43)选择题第5题下列叙述正确的是()。

A.算法就是程序B.设计算法时只需要考虑数据结构的设计C.设计算法时只需要考虑结果的可靠性D.以上三种说法都不对上一题下一题(6/43)选择题第6题下列叙述中正确的是()。

A.有一个以上根结点的数据结构不一定是非线性结构B.只有一个根结点的数据结构不一定是线性结构C.循环链表是非线性结构D.双向链表是非线性结构上一题下一题(7/43)选择题第7题下列关于线性链表的叙述中，正确的是()。

A.各数据结点的存储空间可以不连续，但他们的存储顺序与逻辑顺序必须一致B.各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间不需连续C.进行插入数据与删除数据时，不需要异动表中的元素D.以上说法均不对上一题下一题(8/43)选择题第8题下列叙述中正确的是()。

A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间上一题下一题(9/43)选择题第9题下列叙述中正确的是()。

2010－2011第一学期期中考试试题考试科目：数据结构与算法 适用学生：软件091、092一、选择题 （共21题，每题2分，共42分）1. 为解决计算机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构是________。

[2009考研试题]A 栈B 队列C 树D 图2. 设栈S 和队列Q 的初始状态均为空，元素a,b,c,d,e,f,g 依次进入栈S 。

若每个元素出栈后立即进入队列Q ，且7个元素出队的顺序是b,d,c,f,e,a,g ，则栈S 的容量至少是______。

[2009考研试题]A 1B 2C 3D 43. 给定二叉树如下图所示。

设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。

若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是________。

[2009考研试题]A LRNB NRLC RLND RNL4. 下列二叉排序树中，满足平衡二叉树定义的是______。

[2009考研试题]A.B.C.D.5. 已知一棵完全二叉树的第6层（设根为第1层）有8个叶子结点，则该完全二叉树的结点个数最多是_____。

[2009考研试题]A 39B 52C 111D 1196.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是__。

[2009考研试题] Ⅰ 父子关系 Ⅱ 兄弟关系 Ⅲ u 的父结点与v 父结点是兄弟关系A. 只有Ⅱ B Ⅰ和Ⅱ C Ⅰ和Ⅲ D Ⅰ、Ⅱ和Ⅲ7. 下列关于无向连通图特性的叙述中，正确的是_______。

[2009考研试题] Ⅰ所有顶点的度之和为偶数 Ⅱ 边数大于顶点个数减1Ⅲ 至少有一个顶点的度为1A. 只有Ⅰ B 只有Ⅱ C Ⅰ和Ⅱ D Ⅰ和Ⅲ8. 下列叙述中，不符合 m 阶B 树定义要求的是_______。

北航《算法与数据结构》在线作业一一、单选题（共 25 道试题，共 100 分。

）1. 以下说法错误的是（）A. 线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻B. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻C. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻D. 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素满分：4 分2. 带头节点的单链表head 为空的判定条件（）。

A. head=NULLB. head->next=NULLC. head->next=headD. head!=head满分：4 分3. 设有10000个元素组成的无序序列,希望尽快挑选出其中前10个最大值元素,在不改变已有算法结构的前提下,以下几种内排序算法中( )最合适。

A. 选择排序法B. 快速排序法C. 堆排序法D. 冒泡排序法。

满分：4 分4. 在以下栈的基本运算中，不是加工型运算的是（）.A. lnitStack(S)B. Push(S,X)C. Pop(S)D. empty(S)满分：4 分5. 设矩阵A是一对称矩阵(aij=aji,1<=i,j<=8)，若每个矩阵元素占3个单元，将其上三角部分（包括对角线）按行序为主序存放在数组B中，B的首地址为1000，则矩阵元素a67的地址为（）A. 1031B. 1093C. 1096D. 1032满分：4 分6. 线性表是一个具有n个（）的有限序列。

A. 表元素B. 字符C. 数据元素D. 数据项满分：4 分7. 向二叉排序树中插入一个元素时，其时间复杂度大致为( )。

A. O(log2n(其中2是底数))B. O(n)C. O(1)D. O(n*log2n(其中2是底数))满分：4 分8. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。

《算法与数据结构》模拟试题3一、填空题（每小题2分，共18分）1、数据的逻辑结构包括，和三种结构。

2、算法分析的两个主要方面是和。

3、在双向链表中，每个结点有两个指针域，一个指向，另一个指向。

4、空串是，其长度等于。

5、有一个10阶对称矩阵A，采用压缩存储方式，以行为主存储下三角形到一个一维数组中，若A[0][0]的地址是200（每个元素占2个基本存储单元），则A[9][5]的地址是。

6、在非空二叉树的中序遍历序列中，根结点的右边。

7、采用邻接链表存储图，则图的深度优先搜索算法类似于二叉树的。

8、在分块查找方法中，首先查找，然后再查找相应的。

9、对于文件，按其记录的类型可将文件分为文件、文件。

二、单项选择题（请将答案写在题目后的括号中。

每题2分，共18分）1、有如下递归函数fact(n)，其时间复杂度是（）。

Fact(int n){ if (n<=1) return 1;else return(n*fact(n-1)) ;}（A）O(n) （B）O(n2) （C）O(㏒2n) （D）O(n㏒2n)2、设有一个栈顶指针为top的顺序栈S，top为0时表示栈空，则向S中压入一个元素P执行的操作是（）。

（A）S[top++]=p；（B）S[++top]=p；(C) S[--top]=p；（D）S[top--]=p；3、稀疏矩阵一般的压缩存储方法有主要有（）两种。

（A）二维数组和三维数组（B）三元组和散列（C）三元组和十字链表（D）散列和十字链表4、一般树的存储结构主要有（）。

（A）双亲表示法，孩子表示法，链表表示法（B）双亲表示法，孩子表示法，孩子—兄弟表示法（C）双亲表示法，孩子—兄弟表示法，链表表示法（D）双亲表示法，孩子—兄弟表示法，链表表示法5、一棵有n(n≥0)个结点的满二叉树的叶子结点的数目是，非叶子结点的数目是。

（）（A）2[㏒2n]2[㏒2n]（B）2[㏒2n]-1 2[㏒2n]（C）2[㏒2n]-1 2[㏒2n]-1 （D）2[㏒2n] 2[㏒2n]-16、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍，所有顶点的度之和等于所有顶点的入度之和的倍。

完美WORD格式编辑《数据结构与算法》模拟题一、填空题：（共15分）（每空一分）1.按照排序时，存放数据的设备，排序可分为<1> 内部排序和<2> 外部排序。

2.图的常用的两种存储结构是<3> 邻接矩阵存储和<4>邻接表面存储。

3.数据结构中的三种基本的结构形式是<5> x线性结构和<6> 树形结构、<7> 图形结构。

4.一个高度为6的二元树，最多有<8> 63 个结点。

5.线性查找的时间复杂度为：<9> ，折半查找的时间复杂度为：<10> 、堆分类的时间复杂度为：<11> 。

6.在采用散列法进行查找时，为了减少冲突的机会，散列函数必须具有较好的随机性，在我们介绍的几种散列函数构造法中，随机性最好的是<12>随机数法、最简单的构造方法是<13> 除留余数法。

7.线性表的三种存储结构是：数组、<14> 链表、<15>静态链表。

二、回答下列问题：（共30分）1.现有如右图的树，回答如下问题：A）根结点有：6B）叶结点有：5C）具有作大度的结点：9和10D）结点☐的祖先是：0和2E）结点☐的后代是：102.栈存放在数组A[m]中，栈底位置是m-1。

试问：A）栈空的条件是什么？B）栈满的条件是什么？3.数据结构和抽象数据型的区别与联系：4.已知一株非空二元树，其先根与中根遍历的结果为：先根：ABCDEFGHI中跟：CBEDAGFHI将此二元树构造出来。

5.分析下列程序的运行时间：A)void mystery(int n){int i, j, k;for(i=1; i<n; i++)for(j=i+1; j<=n; j++)for(k=1; k<=j; k++){some statement requiring O(1) time;}}B）void podd(int n){int I, j, x, y;for(I=1; I<=n; I++)if( odd(I ) ){for(j=I; j<=n; j++)x=x+1;for(j=1; j<=I; j++)y=y+1;}}6.已知数学表达式是(3+b)sin(x+5)—a/x2，求该表达式的波兰表示法的前缀和后缀表示（要求给出过程）。

北航算法与数据结构复习题北航《算法与数据结构》复习题单选题（每小题2分，总分10分）1、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（D ）A、必需是联系的B、部分地址必须是连续的C、一定是不连续的D、连续不连续都可以2、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以什么为标准操作（B）A、条件判断B、结点移动C、算术表达式D、赋值语句3、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B ）A、p->next=s;s->next=p->next;B、s->next=p->next;p->next=s;C、p->next=s;p->next=s->next;D、p->next=s->next;p->next=s;4、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（C ）A、(2,5,12,16)26(60,32,72)B、(5,16,2,12)28(60,32,72)C、(2,16,12,5)28(60,32,72)D、(5,16,2,12)28(32,60,72)5、稀疏矩阵的压缩存储方法是只存储（A ）A、非零元素B、三元组（i,j, aij）C、aijD、i,j1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（A）排序法。

A、插入B、选择C、希尔D、二路归并2、用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（D ）A、一定都是同义词B、一定都不是同义词C、都相同D、不一定都是同义词3、将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为（D ）A、42B、40C、21D、204、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B ）A、不确定B、n-i+1C、ID、n-i5、设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（C）个A、k+1B、2kC、2k-1D、2k+1判断题（每小题1分，总分10分）(A==对，B==错)6、在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。

北航《算法与数据结构》复习题一一、单选题（本大题共20小题，每小题1.5分，共30分）1、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为( B )。

A．SA+141B．SA+180C．SA+222D．SA+2252、将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用（ C ）方法能够最快地找出其中最大的正整数。

A．快速排序B．插入排序C．选择排序D．归并排序3、当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（D ）A．n2B．nlog2nC．log2nD．n-14、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（B ）。

A．n-2B．n-1C．nD．n+15、二叉树上叶结点数等于（ C ）。

A．分支结点数加1B．单分支结点数加1C．双分支结点数加1D．双分支结点数减16、计算机算法必须具备输入、输出和（B ）等5个特性。

A．可行性、可移植性和可扩充性B．可行性、确定性和有穷性C．确定性、有穷性和稳定性D．易读性、稳定性和安全性7、深度为6（根的层次为1）的二叉树至多有（ D ）结点。

A．64B．32C．31D．638、在一个无向图中，所有顶点的度数之和等于所有边数的（ B ）倍。

A．3B．2C．1D．1/29、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ C ）。

A．1B．3C．4D．510、一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。

现采用（ B ）遍历方式就可以得到这棵二叉树所有结点的递增序列。

BA．先根B．中根C．后根D．层次11、下面算法的时间复杂度为（ B ）。

int f( unsigned int n ){if ( n==0 || n==1 ) return 1;else return n*f(n-1);}A．O(1)B．O(n)C．O(n2)D．O(n!)12、每一个存储节点只含有一个数据元素，数据元素按散列函数确定存储位置的存储方式是（ 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进制表示。

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，3 B。

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。

5 B.6 C.7 D。

8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：_________、_________、_________和_________.2.一个算法的时间复杂度为（n3+n2log2n+14n）/n2，其数量级表示为________。