2014山东省数据结构与算法一点通科目一

第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个元素的地址是（）。

数据结构与算法模拟习题（附参考答案）一、单选题（共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、以下VB表达式中：⑴Sqr(x) ⑵Text1.text ⑶Command1.caption ⑷"45"+"34" ⑸45+34值为字符串类型的是〔〕A⑴⑵⑶ B⑵⑶⑷ C ⑴⑶⑸ D⑵⑷⑸2、如果给出三条线段的长分别为a、b、c，且已知a≤b≤c，要问这三条线段能否构成三角形，仅需以下选项中的哪个判定条件即可？〔〕A 其他选项都不对B a+c>bC a+b>cD b+c>a3、VB程序中“Dim n As Integer”这条语句的作用是〔〕A 定义一个事件过程B 定义一个数据输入方法C 定义一个变量D 定义一个数据处理方法4、关于算法的描述，以下选项中正确的选项是〔〕A 算法的每一步骤必须有确切的含义B 算法必须有输入C 算法的步骤可以是无穷的D 算法本身就是一种程序设计语言5、关于算法的描述，正确的选项是〔〕A同一种算法只能用一种程序语言实现B算法就是数值计算的方法C描述算法的方法只有流程图D算法是描述解决问题的方法和步骤6、算法的描述方法有多种，以下选项中不适合描述算法的是〔〕A机器语言 B自然语言 C流程图 D伪代码7、长度分别为a、b、c的三条线段，能够组成三角形的条件是〔〕A a+b>c Or a+c>b Or b+c>aB a+b>c or a+c>b And b+c>aC a+b>c Or a+c>b And b+c>aD a+b>c And a+c>b And b+c>a8、已知海伦公式：p=12〔a+b+c〕，a、b、c分别为三角形的三条边长。

利用海伦公式求三角形面积的算法属于〔〕A 排序法B 解析法C 穷举法D 查找法9、以下程序段中循环体执行的次数是〔〕s=0i=0Do While s<10i=i+1s=s+i*iLoopA 1B 3C 2D 410、以下VB表达式中，能正确表达不等式方程|x|>1的解的是〔〕A x>-1 and x<1B x>-1 or x<1C x<-1 and x>1D x<-1 or x>111、一元二次方程ax2+bx+c=0(a≠0)的两个实数根分别为：x12以下表达式正确的选项是〔〕A x2=-b-sqr(b^2-4*a*c)/(2*a) B x1=(-b+sqr(b^2-4ac))/(2*a)C x 2=(-b-sqr(b^2-4*a*c))/(2*a)D x 1=-b+sqr(b^2-4*a*c)/(2*a) 12、关于算法的描述，以下选项中正确的选项是〔 〕A 、一个算法可以没有输入B 、算法只能用流程图表示C 、一个算法，当没有输入时，也没有输出D 、一个算法的执行步骤可以是无限的。

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章绪论习题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个元素的地址是（）.A．110 B．108C．100 D．120（2）在n个结点的顺序表中，算法的时间复杂度是O（1)的操作是（）。

1、与无向图相关的术语有（ C ）。

A）强连通图 B）入度C）路径 D）弧2、n个顶点，e条边的有向图的邻接矩阵中非零元素有（ C ）个。

A）n B）2e C）e D） n+e3、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=（ D ）。

A） (G) B） (D) C）C D） D4、设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（ A ）。

A）p->next=p->next->next; B） p=p->next;C）p=p->next->next; D） p->next=p;5、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（ C ）。

A）top不变 B）top=0 C）top-- D）top++6、串的逻辑结构与（ D ）的逻辑结构不同。

A）线性表 B）栈C）队列 D）树7、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ C ）。

A）顺序表示法 B）单字符为结点的单链表表示法C）等量分块表示法 D）不等量分块表示法8、与无向图相关的术语有（ C ）。

A）强连通图 B）入度C）路径 D）弧9、有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99}。

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

A) 4 B)3 C)2 D)1210、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( B )。

A）9 B）11 C）15 D）不能确定11、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a??11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。

1、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。

二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。

分析你的算法的时、空复杂度。

2、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。

int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数{if(bt==null || k<1) return(0);BiTree p=bt,Q[]; //Q是队列，元素是二叉树结点指针,容量足够大int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针，level 是二叉树的层数while(front<=rear){p=Q[++front];if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点if(p->lchild) Q[++rear]=p->lchild; //左子女入队if(p->rchild) Q[++rear]=p->rchild; //右子女入队if(front==last) {level++; //二叉树同层最右结点已处理,层数增1last=rear; } //last移到指向下层最右一元素if(level>k) return (leaf); //层数大于k 后退出运行}//while }//结束LeafKLevel3、我们用l代表最长平台的长度，用k指示最长平台在数组b中的起始位置（下标）。

用j记住局部平台的起始位置，用i指示扫描b数组的下标，i从0开始，依次和后续元素比较，若局部平台长度（i-j）大于l时，则修改最长平台的长度k（l=i-j）和其在b中的起始位置（k=j），直到b数组结束，l即为所求。

《数据结构》模拟题2010年7月一、单选题（每空2分，共10分）1、队列的删除操作是在（）进行。

A．队首B．队尾C．队前D．对后2、当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。

A．top++; B．top=0; C．top--; D．top=N;3、由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。

A．51 B．23 C．53 D．744、在一棵二叉树中，第4层上的结点数最多为（）。

A．31 B．8 C.15 D．165、向堆中插入一个元素的时间复杂度为（）。

A．O(log2n) B．O(n) C．O(1) D．O(nlog2n)二、填空题（每空1分，共20分）1、数据的逻辑结构被分为____________、___________、____________和____________四种。

2、若对一棵二叉树的结点编号从1开始顺序编码，按顺序存储，把编号为1的结点存储到a[1]中，其余类推，则a[i]元素的左孩子元素为______，右孩子元素为_____，双亲元素(i>0)为________。

3、从一个栈删除元素时，首先取出，然后再前移一位。

4、后缀表达式“2 10 + 5 * 6 – 9 /”的值为。

5、假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J)),K)，则度为3、2、1、0的结点数分别为______、______、______和______个。

6、在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。

7、在索引表中，若一个索引项对应主表中的一条记录，则称此索引为________索引，若对应主表中的若干条记录，则称此索引为________索引。

8、对于二分查找所对应的判定树，它既是一棵_ ____，又是一棵_____ __ ___。