数据结构模拟考试试卷5

1、线性表是具有n个______的有限序列(n>0)。

A．表元素B．字符C．数据元素D．数据项2、栈和队列都是______。

A．顺序存储的线性结构B．链式存储的线性结构C．限制存取点的线性结构D．限制存取点的非线性结构3、若对n阶对称矩阵A以行序列为主序方式将其上三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1….(n(n+1))/2]中，则在B中确定a ij(i<j)的位置k的关系为______。

A．i×(i-1)/2+jB．j×(j-1)/2+iC．i×(i+1)/2+jD．j×(j+1)/2+i4、树是以结点的分支定义______结构，表示数据元素之间______的关系。

①网状②层次③一对多④多对多 A．①④B．②④C．②③D．①③5、一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足______。

A．其中任意一个节点均无左孩子 B．其中任意一个节点均无右孩子C．其中只有一个叶结点 D．其中度为2的结点最多为一个6、一个含有n个顶点和e条边得简单无向图，在其邻接矩阵存储结构中共有______个零元素。

A.eB.2eC.n2-eD.n2-2e7、设网中的定点数为n，边的条数为e，则普里姆(Prim)最小生成树算法和克鲁斯卡尔(Kruskal)最小生成树算法的时间复杂度分别为______。

A．O(n2), O(n2) B．O(n2), O(eloge) C．O(n2), O(nlogn)D．O(nlogn), O(eloge)8、用顺序查找方法查找长度为n的线性表时，在等概率情况下的平均查找长度为______。

A.nB.n/2C.(n-1)/2D.(n+1)/29、某类排序方法的稳定性是指______。

A．该算法不允许有相同的关键字记录B．该算法允许有相同的关键字记录C．平均时间为O(nlogn)的排序方法D．以上都不对10、一组记录的关键码为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为______。

数据结构模拟试题一一、判断题（每小题1 分，共15分）1.计算机程序处理的对象可分为数据和非数据两大类。

2.全体自然数按大小关系排成的序列是一个线性表。

3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。

4.顺序栈是一种规定了存储方法的栈。

5.树形结构中的每个结点都有一个前驱。

6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。

7.若某顶点是有向图的根，则该顶点的入度一定是零。

8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。

9.用一维数组表示矩阵可以节省存储空间。

10.广义表的长度与广义表中含有多少个原子元素有关。

11.分块查找的效率与线性表被分成多少块有关。

12.散列表的负载因子等于存入散列表中的结点个数。

13.在起泡排序过程中，某些元素可能会向相反的方向移动。

14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。

15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。

二、填空题（每空1分，共15分）1.顺序表是一种_____________线性表。

2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。

3.栈和队列的区别在于________的不同。

4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。

5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域为空的结点。

6.n个顶点的有根有向图中至少有___条边，至多有___条边。

7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。

8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是_____。

9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。

一、判断题 (每题1分,共10分)1. 有回路的有向图不能完成拓扑排序。

( )2. 图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。

( )3. 边数很多的稠密图，适宜用邻接矩阵表示。

（）4. 在二叉排序树中插入新结点时，新结点总是作为叶子结点插入。

（）5. 对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键字大小排列到一个拓扑有序的序列中。

( )6. 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。

( )7. 进行折半查找的表必须是顺序存储的有序表。

( )8. 对平衡二叉树进行中根遍历，可得到结点的有序序列。

（）9. 邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）( )。

10. 对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。

( )二、单项选择题 (每题2分,共20分)1. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。

A.O(1)B.O(n)C.O(n2)D.O(nlog2n)2. 数组A[5][6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[4][4]的地址为（）。

A.1140B.1145C.1120D.11253. 在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算是（）。

A.f->next=s;f=s;B.r->next=s;r=s;C.s->next=r;r=s;D.s->next=f;f=s;4. 在一个单链表中已知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;5. 对于如下图所示的带权有向图，从顶点1到顶点5的最短路径为（）。

数据结构试题（A05）一、选择题(共10小题，每小题1分,共10分）1。

下面程序段的时间复杂度是( ）m=0；for(i=1；i<=n;i++)for（j=1;j<=n；j++)m=m+1;A. O（n2) B。

O（m+n+1）C。

O(m+n）D。

O(n）2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继"的语句是（）A。

p=p—>next; B.p—〉next=p->next—>next;C.p—>next=p;D.p=p->next—>next;3。

在长度为n的顺序表，当在任何位置上删除一个元素的概率相等时,删除一个元素需要移动的元素的平均个数为( )A.n/2B.(n-1）/ 2C.（n+1)/2D.(n+2）/24.一个栈的输入序列为 1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（)A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 26。

设循环队列中数组的下标范围是1~n,其头尾指针分别为f和r，则其元素个数为( )A. r—fB. r—f+1C. （r-f）mod n+1D. （r—f+n) mod n7.以下序列不是堆的是（）。

A。

（100，85，98，77,80，60,82，40，20，10，66）B.（100,98，85，82，80，77，66，60，40,20，10）C。

（100，85，40，77，80,60,66，98，82,10，20)D。

（10,20,40,60,66，77，80，82，85，98,100）8．在有序表（12，24，36,48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为( )。

A。

3 B。

4 C。

5 D. 29。

在待排序的元素序列基本有序的前提下,效率最高的排序方法是（）。

A.选择排序B.冒泡排序C。

快速排序 D.插入排序二、填空题（共20小题，每小题1分，共20分）1、在单链表中，删除指针P所指结点的后继结点的语句是.2、线性表的两种存储结构分别是和.3、己知完全二叉树的第4层有5个结点，则其叶子结点数是.4、将下三角矩阵A[1…。

数据结构试卷（一）一、选择题（20分）1．组成数据的基本单位是（）。

(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（）。

(A) 线性结构(B) 树型结构(C) 图型结构(D) 集合3．数组的逻辑结构不同于下列（）的逻辑结构。

(A) 线性表(B) 栈(C) 队列(D) 树4．二叉树中第i(i≥1)层上的结点数最多有（）个。

(A) 2i (B) 2i(C) 2i-1(D) 2i-15．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。

(A) p->next=p->next->next (B) p=p->next(C) p=p->next->next (D) p->next=p6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（）。

(A) 6 (B) 4 (C) 3 (D) 27．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。

(A) 100 (B) 40 (C) 55 (D) 808．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。

(A) 3 (B) 4 (C) 5 (D) 19．根据二叉树的定义可知二叉树共有（）种不同的形态。

(A) 4 (B) 5 (C) 6 (D) 710.设有以下四种排序方法，则（）的空间复杂度最大。

(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序二、填空题(30分)1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。

数据结构模拟试题5参考答案一、选择题（20分）1-5 C C D A A6-10 D B C B B二、填空题（20分）1．结点*p的左右链域为空2．深度优先3．N-14．A[N/2]5．sq.front=（sq.fron+1）%M （sq.rear+1）%M = = sq.front 6．4，9，14，17，207．0 入度减1 环三、应用题（30分）1．参考答案如下：1）二叉树2）对应的森林·2·数据结构上机实验与习题解析2．参考答案如下：3．参考答案如下：1）G1的邻接表和G1的逆邻接表2）G1的强连通分量第3部分模拟试题及参考答案·3·4．参考答案如下：2）所有字符的哈夫曼编码如下：A（7）： 0011B（19）： 011C（5）： 0010D（16）： 010E（42）： 01F（11）： 0005．参考答案如下：事件的发生时间活动的开始时间·4·数据结构上机实验与习题解析6．参考答案如下：1）该序列是一个小根堆四．算法设计题（30分）1．算法源代码如下：void fun(bitree T, char x, int m){ if(T){ m++;if(T->data==x) {printf("%d",m); return ;}fun (T->lchild,x,m);fun (T->rchild,x,m);}}main(){ bitree bt;int m=0;fun(bt,m);}2．算法源代码如下：#define maxsizetypedef struct{int elem[maxsize];第3部分模拟试题及参考答案·5·int top[2];}stack;stack s;1）入栈操作int push(int i,int x){ if(i<0||i>1) { printf("输入数据有误"); return 0;}if(s.top[1]-s.top[0]==1) {printf("栈满"); return 0;}switch(i){ case 0: s.elem[++s.top[0]]=x; break;case 1: s.elem[--s.top[1]]=x;}return 1;}2）出栈操作int pop(int i, int *x){ if(i<0||i>1) { printf("输入数据有误"); return 0;}switch(i){ case 0:if(s.top[0]==-1) {printf("栈空"); return -1;}else *x=s.elem[s.top[0]--];break;case 1:if(s.top[0]==maxsize) {printf("栈空"); return -1;}else *x=s.elem[s.top[1]++];}return 1;}3．算法源代码如下：void dijkshort(mgraph G,int v){int s[30]; int d[30]; int pre[30];int i,j,k,p,min;for(i=1;i<=G.vexnum;i++){ d[i]=G.arcs[v][i]; s[i]=0;if(d[i]<32767) pre[i]=v;else pre[i]=0;}s[v]=1;for(i=1;i<=G.vexnum;i++){ min=32767; k=0;·6·数据结构上机实验与习题解析for(j=1;j<=G.vexnum;j++)if(!s[j]&&d[j]<min) {min=d[j];k=j;}if(k==0) /*已没有顶点可往第一组加*/return;else{ s[k]=1; /*将找到的顶点加入到第一组中*/for(j=1;j<=G.vexnum;j++) /*修改第二组中顶点的距离值*/if(!s[j]&&d[j]>d[k]+G.arcs[k][j]) { d[j]=d[k]+G.arcs[k][j]; pre[j]=k;}}for(j=1;j<=G.vexnum;j++) /*输出结果*/if(pre[j]){ printf("\n%c",G.vexs[j]); p=pre[j];while(p){printf("<%c",G.vexs[p]);p=pre[p];}printf(": %d",d[j]); }elseif(j!=v) printf("\n%c<%c : no path",G.vexs[j],G.vexs[v]);}。

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

2、队列是操作受限的线性结构，只能在插入元素，而在删除元素。

3、串是一种特殊的线性表，其特殊性体现在。

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

5、在高度为h的二叉树的中只有度为0和度为2的结点，则该类二叉树中所包含的结点数至少为。

6、对于一个有n个顶点和e条边的无向图，若采用邻接链表存储，则表头向量的大小为，邻接表中的结点总数为。

7、对线性表进行二分查找时，要求线性表必须是，且要求。

8、对于文件，按物理结构划分，可分为顺序文件、文件、文件和多关键字文件。

9、外部排序的最基本方法是，其主要时间花费在方面。

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

每题2分，共18分）1、如下函数是求1!+2!+…+n!，其时间复杂度是（）。

Long int Sum (int n){ long int sum=0 , t=1 ; int p ;for (p=1; p<=n ;p++) { t=t*p ; sum+=t ; }return(sum) ;}（A）O(n) （B）O(n2) （C）O(㏒2n) （D）O(n㏒2n)2、设有一个栈顶指针为top的顺序栈S，则弹出S的栈定元素的操作是（）。

（A）p=S[top++]；（B）p=S[++top]；(C)p=S[top--]；（D）p=S[--top]；3、广义表((a),((b),c),(((d))))的表头是，表尾是。

（）（A）(a) ((b),c),(((d))) （B）(a) (((b),c),(((d))))（C）((a),((b),c)),(((d))) （D）(a) (((d)))4、一棵二叉树，其先序遍历序列是abdgehicf，中序遍历序列是gdbheiafc，则其后序遍历序列是( )。

考试试卷一、请判断下列说法的是否正确：(10分)（1）若某堆栈的输入序列为1,2,3,4，则4,3,1,2不可能是堆栈的输出序列之一。

( )（2）队列逻辑上是一个表头和表尾既能插入又能删除的线性表。

（）（3）若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是该子树的先序遍历中的最后一个结点。

（）（4）在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关，而与每块中元素个数无关。

（）（5）二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值，小于其右孩子的值。

（）（6）在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及各种直接排序法都快。

（）（7）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的结点的个数有关，而与图的边数无关。

（）。

-（8）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。

（）（9）二分查找法不仅适用于顺序存储的有序表，而且适合于链接表。

（）（10）按中序遍历一棵二叉排序树所得到的遍历序列是一个递增序列。

（）二、填空（20分）(1)数据结构有如下四种基本结构：、、、。

（2）在一个算法中的语句频度之和为T（n）=3720n+4nlogn，则算法的时间复杂度为。

（3）已知某二叉树的叶子结点的个数为10个，度为1的结点个数为8个，则该二叉树的结点总数为：个。

(4)已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90 的元素时，需__ ___次比较可检索成功。

(5)、图的遍历方法主要有两个，一个是，另一个是。

(6)在哈希造表过程中，处理冲突的方法主要有：，，，。

（7）在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点，应执行s->next=__ ___;和p->next=___ _____的操作。

一、填空题（每空1分，共20分）1、数据结构被形式地定义为（D, R），其中D是的有限集合，R是D上的有限集合。

2、一个算法的效率可用、来衡量。

3、向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素。

4、具有n个叶子结点的哈夫曼树，其结点总数是个。

5、一般情况下，快速排序的时间复杂度是。

6、向栈中压入元素的操作是先，后。

7、称为空串；称为空白串。

8、采用三元组表存储稀疏矩阵，三元是指。

9、具有10个结点的完全二叉树，其深度是。

10、线性有序表（a1，a2，a3，…，a20）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索次。

11、散列法（哈希）存储的基本思想是由决定数据的存储地址。

12、具有n个顶点的无向图，最多有条边；如果该图是一个连通图，那它最少有条边；其生成树有条边。

13、每个结点的平衡因子的二叉排序树称为平衡二叉树，中序遍历该树可得到。

14、二、判断题（正确的画√，错误的画Χ；每题1分，共10分）1、队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

2、根据二叉树的先序和中序遍历结果，可唯一确定该二叉树。

3、栈和队列的存储方式既可是顺序方式，也可是链接方式。

4、二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

5、一个有向无环图进行拓扑排序，结果可能不唯一。

6、链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。

7、用二叉链表存储包含n个结点的二叉树，结点的2n个指针域中有n+1个为空指针。

8、具有2个结点的二叉树有2种形态。

9、线性表在链式存储时，逻辑上相邻的元素在存储的物理位置次序上也一定不相邻。

10、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

三、单项选择题（每小题2分，共30分）1、算法分析的目的是。

A、分析算法的易读性B、研究算法中输入和输出的关系C、分析算法的效率，以求改进D、找出合理的数据结构2、对图进行深度优先搜索时，使用的辅助存储结构是。

《数据结构》模拟试卷及参考答案模拟试卷一一、单选题（每题2 分，共20分）1.以下数据结构中哪一个是线性结构？( )A. 有向图B. 队列C. 线索二叉树D. B树2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下( )语句序列。

A. p=q; p->next=q;B. p->next=q; q->next=p;C. p->next=q->next; p=q;D. q->next=p->next; p->next=q;3.以下哪一个不是队列的基本运算？（）A. 在队列第i个元素之后插入一个元素B. 从队头删除一个元素C. 判断一个队列是否为空D.读取队头元素的值4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( )个不同的字符串？A.14B.5C.6D.85.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。

以下6-8题基于图1。

6.该二叉树结点的前序遍历的序列为( )。

A.E、G、F、A、C、D、BB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FD.E、G、A、C、D、F、B7.该二叉树结点的中序遍历的序列为( )。

A. A、B、C、D、E、G、FB. E、A、G、C、F、B、DC. E、A、C、B、D、G、FE.B、D、C、A、F、G、E8.该二叉树的按层遍历的序列为( )。

A．E、G、F、A、C、D、B B. E、A、C、B、D、G、FC. E、A、G、C、F、B、DD. E、G、A、C、D、F、B9.下面关于图的存储的叙述中正确的是( )。

A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?( )A. a，g，h，m，n，p，q，x，zB. a，g，m，h，q，n，p，x，zC. g，m，q，a，n，p，x，h，zD. h，g，m，p，a，n，q，x，z二、填空题（每空1分，共26分）1.数据的物理结构被分为_________、________、__________和___________四种。

数据结构模拟考试（总分100分，考试时长90分钟）一、单项选择题（每小题2 分，共 100分）1、一棵具有 n 个结点的完全二叉树的树高度(深度)是( A )A、「log2n」+1B、log2n+1C、「log2n」D、log2n-12、若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为A、O(n)B、O(0)C、O(1)D、O(n^2)3、一个顺序栈S,空栈时top的初始值为0,其栈顶指针为top,则将元素e入栈的操作是( )。

A、*S->top=e;S->top++;B、S->top++;*S->top=e;C、*S->top=eD、S->top=e;4、下列几种排序方法中要求辅助空间最大的是( )A、堆排序B、直接选择排序C、归并排序D、快速排序5、给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字典序列的次序进行排列，冒泡排序(大数下沉)的第一趟排序结果应为A、{B，F，C，J，A，E，D，I，C，H}B、{C，B，D，A，E，F，I，C，J，H}C、{B，F，C，E，A，I，D，C，H，J}D、{A，B，D，C，E，F，I，J，C，H}6、对含有 10 个数据元素的有序查找表执行折半查找,当查找失败时,至少需要比较( )次。

A、2B、3C、4D、57、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A、r-fB、(n+f-r)%nC、n+r-fD、（n+r-f)%n8、若长度为 n 的线性表采用顺序存储结构，访问其第 i 个元素的算法时间复杂度为（）A、0 ( 1 )B、0 ( n )C、0 ( n2 )D、0 ( log2n )9、(6分)若希望1000个无序元素中尽快求得前10个最大元素,应借用(A)。

数据结构模拟试题一、单选题(每小题2分，共12分)1．在一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤n+1)的位置插入一个新元素时，需要从后向前依次后移( )个元素。

A．n-i B．n-i+1 C．n-i-1 D．i ，2．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（）。

A．p=q->next；p->next=q->next； B．p=q->next；q->next=p；C．p=q->next；q->next=p->next； D．q->next=q->next->next；q->next=q；3．当利用大小为N的数组顺序存储一个队列时，该队列的最大长度为( )。

A．N-2 B．N-1 C．N D．N+14．根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为( )。

A．O(lon2n) B．O(n) C．O(nlog2n) D．O(n2)5.向具有n个结点的堆中插入一个新元素的时间复杂度为( )。

A．O(1) B．O(n) C．O(log2n) D．O(nlog2n)6．对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1／2，搜索第二个元素的概率为l／3，搜索第三个元素的概率为l／6，则搜索任一元素的平均搜索长度为( )。

A．5／3 B．2 C．7／3 D．4／3二、填空题（每空1分，共28分）1．数据的存储结构被分为顺序结构、链接结构、和四种。

2．对于一个长度为n的单链接存储的线性表，在表头插入结点的时间复杂度为，在表尾插入元素的时间复杂度为。

3．中缀表达式3*x+(2.4／5.6-7.3)所对应的后缀表达式为。

4．一棵深度为4的满二叉树中的结点数为个，一棵深度为3的满四叉树中的结点数为个。

5．对于一棵含有40个结点的理想平衡树，它的高度为。

6．从一棵二叉搜索树中查找一个元素时，若给定值等于根结点的值，则表明，若给定值小于根结点的值，则继续向查找，若给定值大于根结点的值，则继续向查找。

数据结构模拟卷（含答案）经典习题.doc 练习题⼀、单项选择题1. 若将数据结构形式定义为⼆元组(K ,R) ,其中K是数据元素的有限集合,则R是K上( )A. 操作的有限集合B. 映象的有限集合C. 类型的有限集合D. 关系的有限集合2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时,元素移动的次数为( )A. n-i+1B. iC. i+1D. n-i3. 若不带头结点的单链表的指针为head ,则该链表为空的判定条件是( )A. head==NULLB. head->next==NULLC. head!=NULLD. head->next==head4. 引起循环队列队头位置发⽣变化的操作是( )A. 出队B. ⼊队C. 取队头元素D. 取队尾元素5. 若进栈序列为1 ,2 ,3 ,4 ,5 ,6 ,且进栈和出栈可以穿插进⾏,则不．可能出现的出栈序列是( )A. 2 ,4 ,3 ,1 ,5 ,6B. 3 ,2 ,4 ,1 ,6 ,5C. 4 ,3 ,2 ,1 ,5 ,6D. 2 ,3 ,5 ,1 ,6 ,46. 字符串通常采⽤的两种存储⽅式是( )A. 散列存储和索引存储B. 索引存储和链式存储C. 顺序存储和链式存储D. 散列存储和顺序存储B．数据的存储结构C．⼀组性质相同的数据元素的集合D．相互之间存在⼀种或多种特定关系的数据元素的集合8. 算法分析的⽬的是（）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输⼊与输出的关系D．鉴别算法的可读性9. 在线性表的下列运算中,不．改变数据元素之间结构关系的运算是（）A．插⼊B．删除C．排序D．定位10. 下列图⽰的顺序存储结构表⽰的⼆叉树是( )11. 设串sl=″Data Structures with Java″,s2=″it″,则⼦串定位函数index(s1,s2)的值为(）A．15 B．16C．17 D．1812. ⼆维数组A[8][9]按⾏优先顺序存储,若数组元素A[2][3]的存储地址为1087 ,A[4][7]的存储地址为1153 ,则数组元素A[6][7]的存储地址为（）A．1213 B．1209C．1211 D．120713. 在按中序遍历⼆叉树的算法中,需要借助的辅助数据结构是（）A．队列B．栈C．线性表D．有序表14. 在任意⼀棵⼆叉树的前序序列和后序序列中,各叶⼦之间的相对A．不⼀定相同B．都相同C．都不相同D．互为逆序15. 若采⽤孩⼦兄弟链表作为树的存储结构,则树的后序遍历应采⽤⼆叉树的（）A．层次遍历算法B．前序遍历算法C．中序遍历算法D．后序遍历算法16. 若⽤邻接矩阵表⽰⼀个有向图,则其中每⼀列包含的″1″的个数为（）A．图中每个顶点的⼊度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数⽬17. 图的邻接矩阵表⽰法适⽤于表⽰（）A．⽆向图B．有向图C．稠密图D．稀疏图18. 若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t）,则在⼆分查找关键字b的过程中,先后进⾏⽐较的关键字依次为（）A．f,c,b B．f,d,bC．g,c,b D．g,d,b19. 下⾯程序段的时间复杂度为( )s=0；for(i=1；ifor(j=1；js+=i*j；A.O(1)B.O(logn)C.O(n)D.O(n2)20. 已知指针p和q分别指向某单链表中第⼀个结点和最后⼀个结点。

《数据结构》试卷一一、填空题：（共２０分）1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。

2、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是。

3、在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。

4、二叉树的前序遍历序列等同于该二叉树所对应森林的遍历序列5、对一棵二叉排序树，若以遍历该树，将得到一个以关键字递增顺序排列的有序序列。

6、三个结点a,b,c组成二叉树，共有种不同的结构。

7、在AVL树中，由于在Ａ结点的右孩子的右子树上插入结点，使Ａ结点的平衡因子由-1变为-2，使其失去平衡，应采用型平衡旋转。

8、图的遍历有两种,它们是。

9、堆排序的时间复杂度为。

10、在含有N个结点的二叉链表中有空链域，通常用这些空链域存储线索，从而得另一种链式存储结构----线索链表。

二、单项选择题（共２０分）１、若进栈序列为１，２，３，４，假定进栈和出栈可以穿插进行，则可能的出栈序列是（）（A）２，４，１，３（B）３，１，４，２（C）３，４，１，２（D）１，２，３，４２、有一棵非空的二叉树，（第０层为根结点），其第i层上最多有多少个结点？（）（A）２i（B）２1-i（C）２1+i（D） i３、设电文中出现的字母为A，B，C，D，E，每个字母在电文中出现的次数分别为９，２７，３，５，１１，按huffman编码，则字母A编码为（）（A）１０（B）１１０（C）１１１０（D）１１１１４、下面关于数据结构的叙述中，正确的叙述是（）（A）顺序存储方式的优点是存储密度大，且插、删除运算效率高（B）链表中每个结点都恰好包含一个指针（C）包含n个结点的二叉排序树的最大检索长度为logn2（D）将一棵树转为二叉树后，根结点无右子树５、程序段：y:＝0while n>=(y+1)*(y+1) doy:=y+1enddo的时间复杂度为（）（A）O(n) （B）O(n2) （C）O(n2/1) （D）O(1)6、排序方法中,关键码比较的次数与记录的初始排列无关的是( )(A) shell排序 (B) 归并排序 (C) 直接插入排序 (D) 直接选择排序7、数组q[0..n-1]作为一个环行队列,f 为当前队头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数总小于n,则队列中元素个数为( )(A) r-f (B) n+f-r (C) n+r-f (D) (n+r-f) mod n8、为了有效的利用散列查找技术,需要解决的问题是:( )Ⅰ:找一个好的散列函数Ⅱ:设计有效的解决冲突的方法Ⅲ:用整数表示关键码值(A) Ⅰ和Ⅲ (B) Ⅰ和Ⅱ (C) Ⅱ和Ⅲ (D) Ⅰ,Ⅱ和Ⅲ9、引入线索二叉树的目的是（）(A) 加快查找结点的前驱或后继的速度(B) 为了能在二叉树中方便的进行插入与删除(C) :为了能方便的找到双亲(D) 使二叉树的遍历结果唯一10、用二分（折半）查找表的元素的速度比用顺序法（）(A) 必然快(B) 必然慢(C): 相等(D): 不能确定三、简答题：（共40分）１、已知某二叉树按中序遍历序列为BFDAEGC，按前序遍历序列为ABDFCEG,试画出该二叉树形状，并写出它的后序遍历序列。

数据结构模拟试题（含答案）一、单选题（共100题，每题1分，共100分）1、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。

A、5B、6C、7D、4正确答案：B2、假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。

A、15B、47C、16D、17正确答案：C3、设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

A、100B、99C、102D、101正确答案：A4、一棵含18个结点的二叉树的高度至少为( )A、5B、4C、6D、3正确答案：A5、有关栈的描述，正确的是（）A、栈是一种先进先出的特殊的线性表B、只能从栈顶执行插入、删除操作C、只能从栈顶执行插入、栈底执行删除D、栈顶和栈底均可执行插入、删除操作正确答案：B6、若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（）A、中序遍历算法B、前序遍历算法C、后序遍历算法D、层次遍历算法正确答案：A7、若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是( ) typedef struct node { char data[8]; struct node *next; } LinkStrNode;A、s->next=p; p->next=s->next;B、s->next=p->next; p->next=s;C、p->next=s->next; s->next=p;D、p->next=s; s->next=p->next;正确答案：B8、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为( )。

A、O(n)B、O(1)C、O(n2)D、O(n／2)正确答案：A9、执行一趟快速排序能够得到的序列是（）。

A、[45，34，12，41] 55 [72，63，27]B、[63，12，34，45，27] 55 [41，72]C、[12，27，45，41] 55 [34，63，72]D、[41，12，34，45，27] 55 [72，63]正确答案：D10、带权有向图G用邻接矩阵A存储，则顶点i 的入度等于A中（）。

数据结构试卷（1）一、选择题(30分)1．设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。

(A) 20 (B) 30 (C) 40 (D) 452．执行一趟快速排序能够得到的序列是（）。

(A) [41，12，34，45，27] 55 [72，63](B) [45，34，12，41] 55 [72，63，27](C) [63，12，34，45，27] 55 [41，72](D) [12，27，45，41] 55 [34，63，72]3．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。

(A) head==0 (B) head->next==0(C) head->next==head (D) head!=04．时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（）。

(A) 堆排序(B) 冒泡排序(C) 希尔排序(D) 快速排序5．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。

(A) 空或只有一个结点(B) 高度等于其结点数(C) 任一结点无左孩子(D) 任一结点无右孩子6．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。

(A) 堆排序(B) 冒泡排序(C) 快速排序(D) 希尔排序7．设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。

(A) 3 (B) 4 (C) 5 (D) 68．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。

(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)9．二路归并排序的时间复杂度为（）。

(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)10. 深度为k的完全二叉树中最少有（）个结点。

(A) 2k-1-1 (B) 2k-1(C) 2k-1+1 (D) 2k-111.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。

第五套模拟试题参考答案及解析1.所谓算法的时间复杂度，是指执行算法所需要的计算工作量。

为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。

为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。

本题答案是C。

2.根据数据结构中各数据元素之间前后间关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。

如果一个非空的数据结构满足下列两个条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

则称该数据结构为线性结构，又称线性表。

所以线性表、栈与队列、线性链表都是线性结构，而二叉树是非线性结构。

本题答案是A。

3.所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。

具有n个结点的完全二叉树，其父结点数为int(n/2)，而叶子结点数等于总结点数减去父结点数。

本题n=699，故父结点数等于int(699/2)=349，叶子结点数等于699-349=350。

本题答案是B。

4.结构化程序设计主要强调的是结构化程序清晰易读，可理解性好，程序员能够进行逐步求精、程序证明和测试，以保证程序的正确性。

本题答案为B。

5.通常，将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。

也就是说，软件产品从考虑其概念开始，到该软件产品不能使用为止的整个时期都属于软件生命周期。

软件生命周期的主要活动阶段为：（1）可行性研究和计划制定。

确定待开发软件系统的开发目标和总的要求，给出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成开发任务的实施计划。

（2）需求分析。

对待开发软件提出的需求进行分析并给出详细定义，即准确地确定软件系统的功能。

编写软件规格说明书及初步的用户手册，提交评审。

（3）软件设计。

系统设计人员和程序设计人员应该在反复理解软件需求的基础上，给出软件的结构、模块的划分、功能的分配以及处理流程。