数据结构模拟试卷 联系客服

发布时间 : 星期五 文章数据结构模拟试卷更新完毕开始阅读b6571789d0d233d4b14e69c0

模 拟 试 卷 A

一、单项选择题

1.评价一个算法时间性能的主要标准是( )

A.算法易于调试 B. 算法易于理解 C.算法的稳定性和正确性 D.算法的时间复杂度 2.可用带表头结点的链表来表示表,也可用不带表头结点的链表来表示表,前者的主要好处是( )

A. 可以加快对表的遍历 B. 使空表和非空表的处理统一 C. 提高存取结点的速度 D. 节省存储空间 3.稀疏矩阵一般的压缩存储有两种,即( )。

A.一维数组和二维数组 B.一维数组和三元组 C.二维数组和十字链表 D.三元组和十字链表

4.若进栈序列为a,b,c,d,进栈过程中可以出栈,则( )不可能是一个出栈序列。 A.cbad B.bdca C.cdba D.adbc

5.将一棵有100个结点的完全二叉树从根的这一层开始,每一层从左到右依次对结点进行编号,根结点编号为1,则编号为49的结点的左孩子的编号为( )

A.98 B.99 C.50 D.48 6.任何一个无向连通图的最小生成树( )。

A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 7.对于如下右图所示的带权有向图,从顶点1到顶点5的6 最短路径为( ) 9 1 4 A.(1,4,5) B.(1,2,3,5)

2 3 C.(1,4,3,5) D.(1,2,4,3,5) 1 8 5 2 3

8.下列排序方法中,要求附加的内存容量最大的是( )。

A.冒泡排序 B.快速排序 C.堆排序 D.归并排序 9.( )不是哈希查找中的冲突处理方法。

A.链地址法 B.再哈希法 C.除留余数法 D.随机探测法 10. 在一棵7阶B-树中,除根结点外,每个结点中最多有( )个关键字。

A. 6 B.5 C.4 D.3

5 二.填空题

1. 在长度为n的顺序表中删除一个元素时,等概率情况下的平均移动元素的次数是【 】 。 2. 仅允许在表的同一端进行插入和删除运算的线性表被称为【 】. 3.大小为M的顺序存储的循环队列sq队满的条件为【 】。

4.已知一棵二叉树的先根序列为ABDFCE,中根序列为DFBACE,则后根序列为【 】.

5.在无向图G的邻接矩阵表示中,第j列中非零元的个数等于该顶点的【 】。

1

6. 克鲁斯卡尔算法适用于求【 】的网的最小生成树。 7.设待排序的表为(42,55,12,47,94,06,18,63),利用快速排序方法对其进行排序,经第一趟排序后,表的状态为【 】。 8.由关键字序列{36,96,84,18,52,27}建成的最小堆是【 】。

9.用折半查找法查找一个线性表中的元素时,此线性表必须是【 】。 10.已知8个数据元素为(34,76,45,18,26,54,92,65),按照依次插入结点的方法生成一棵二叉排序树后,最后两层上的结点总数为【 】 。

三.应用题

1.有七个带权结点,其权值分别为{3,7,18,2,6,10,14},试以它们为叶子结点构造一棵哈夫曼树(请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造),并计算出该树的带权路径长度。

2.已知关键字序列为{66,80,36,55,93,21,42,72,38,47,11},试写出希尔排序过程中每一趟排序后关键字的排列情况(di=5,2,1)。

3.已知关键字序列为:(75,33,52,41,12,88,66,27)哈希表长为10,哈希函数为:H (k)=k %9,解决冲突用线性探测再散列法,试构造哈希表,求等概率下查找成功的平均查找长度.

4.已知一个AOV网如图所示。

(1)试画出它的邻接链表。(顶点号递减出现在各邻接表中)

(2)试写出按照拓扑排序算法得到的拓扑序列。

V4V6V1V3V5V2四、算法设计题

1..有一带表头结点的单链表,其结点的元素值以非递减有序排列,编写一个算法在该链表中插入一个元素x,使得插入后的单链表仍有序。

2.设二叉树T采用二叉链表结构存储,数据元素为字符类型。设计算法将二叉链表中所有data域为小写字母的结点改为大写字母。

2

模拟试卷B

一.单项选择题

1.数据结构中,与所使用的计算机无关的是数据的( ) 结构。

A.顺序 B.物理 C.逻辑 D.物理和存储

2.在长度为n的顺序表中插入一个元素时,等概率情况下的平均移动元素的次数是( ) 。

A.(n-1)/2 B.n/2 C.n*(n-1)/2 D.(n+1)/2 3.对于一个头指针为H的带头结点的单链表,判定该表为空表的条件是( )

A. H==NULL B.H!=NULL C.H→next ==H D.H→next==NULL

4. 在一个顺序表中,若表的第一个元素的存储地址是210,每一个元素的长度为3,则第5个元素的存储地址是( )。

A.219 B.222 C.225 D.228

5. 栈S最多能容纳4个元素,现有6个元素按a,b,c,d,e,f的顺序进栈,下面序列( )是可能的出栈序列。

A.edcbaf B.bcefad C.cbedaf D.adfebc

6.循环队列用数组A[M]存放元素,已知其头尾指针分别为front和rear,则当前队列中的元素个数是( )。

A.rear-front+1 B.rear-front-1

C.rear-front D.(rear-front+M) % M

7.已知一棵二叉树的有35个叶子结点,则该二叉树至少有( )个结点。 A. 69 B. 70 C. 71 D. 72 8.在有向图的顶点的拓扑序列中,如果Vi在Vj之前,则下列情况一定不会出现的是( )

A. 图中有弧 B. 图中Vi到Vj有一条路径 C. 图中没有弧 D. 图中有弧< Vj,Vi > 9.下列哪种排序方法在最坏的情况下的时间复杂度是O(n*log2n)( )

A .直接插入排序 B. 堆排序 C. 简单选择排序 D. 快速排序 10. 在一棵6阶的B-树中,除根结点外,每个结点中的至少有( )个关键字。 A)5 B)4 C)3 D)2

二.填空题

1. 设有程序段为

for (i=1 ;i<10;i++) for (j=1 ;j<=i;j++)

{p=i*j; printf(“M\\n”,p);}

则执行p=i*j的次数为 【 】 。

2.在单链表中某P结点后插入S结点的操作是【 】。

3. 有一个10阶三角矩阵A,采用压缩方式(以行序为主存储)存储在一维数组B中,若A[1,1] 存储在B[1]中,则A[5,8] 存储在B【 】 。 4. 链队列lq为空的条件为【 】。

5. 设有二叉树根结点的层次为0,棵高度为h的满二叉树中的叶子结点个数是【 】。 6.由分别带权为9,2,5,7的四个叶子结点构造的哈夫曼树的带权路径长度为【 】。 7.在有向图的邻接表表示中,每个顶点邻接表中所含的结点数等于该顶点的【 】。 8.普里姆算法适用于求 【 】的网的最小生成树。

9.直接插入排序在初始有序时,进行【 】次关键字比较。

10.设序列{25,36,40,45,48,56,60,68,72,85},当用折半查找方法查找36时,所需比较

3

的次数为【 】。

三.应用题

1.已知一组数据元素为(57,24,96,73,18,45,30,40,82),要求: (1)试从空树开始画出按元素排列顺序输入而生成的一棵二叉排序树; (2)画出删除结点57后的二叉排序树。

2.已知一个图的邻接表如下所示.请画出该邻接表表示的图,并依此邻接表进行从顶点A出发的深度优先遍历,求出由此得到的遍历序列和深度优先生成树. A0 1 2 4 ∧ a B1 3 ∧ b

C

2 1 ∧

3 D 2 ∧

4 E 2 3 ∧ ∧ 3.已知关键字序列{34,26,47,12,63,41,22,59},利用堆排序的方法对其排序。 (1)写出在构成初始堆后关键字的排列情况。

(2)写出在堆排序的过程中输出前4个记录时,每次调整后关键字的排列情况。

4. 选取哈希函数为H(K)=K % 13,用链地址法处理冲突。试在0~12的散列地址空间中对关键字序列{87,25,310,08,27,132,68,95,187,123,70,63,47}构造哈希表,并求出等概率下查找成功的平均查找长度。

四.算法设计题

1.编写算法判断带表头结点的单链表L是否是递增的。若递增返回1,否则返回0。

2.假设一个算术表达式由字符串exp表示,请设计算法,要求利用栈的基本运算实现判别给定表达式中所含圆括号是否正确配对出现。 。

4