2022年c语言数据结构试题模拟试卷 .pdf

《2022年c语言数据结构试题模拟试卷 .pdf》由会员分享，可在线阅读，更多相关《2022年c语言数据结构试题模拟试卷 .pdf（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、模拟试卷一一、一、单选题（每题2 分，共 20 分）1.1.以下数据结构中哪一个是线性结构？( 2 ) A. 有向图B. 队列C. 线索二叉树D. B 树2.2.在一个单链表HL 中，若要在当前由指针p 指向的结点后面插入一个由q 指向的结点，则执行如下( 4 )语句序列。 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.3.以下哪一个不是队列的基本运算？（1 ）A. 在队列第 i 个元素之后插入一个元素B. 从队头删除一个元素C. 判断一个队列是否为空D

2、.读取队头元素的值4.4.字符 A、B、C 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( b )个不同的字符串？ A.14 B.5 C.6 D.8 5.5.由权值分别为3,8,6,2 的叶子生成一棵哈夫曼树，它的带权路径长度为( b )。A 11 B.35 C. 19 D. 53 以下 6-8 题基于图1。6.6.该二叉树结点的前序遍历的序列为( 3 )。A.A.E、G 、 F、A、C、D、 B B.B.E、A 、 G 、C、F、B、 D C.C.E、A 、 C、B、D、G 、 F D.D.E、G 、 A、C、D、F、 B 7.7.该二叉树结点的中序遍历的序列为( 1 )

3、。A. A 、B、C、D、 E、G、F B. E 、A、G 、C、 F、B、D C. E 、A、C、B、 D、G、F E.E.B、D 、 C、A、F、G 、 E 8.8.该二叉树的按层遍历的序列为( 3 )。 AE、G、F、A、C、D 、 B B. E、A、C、B、D、G 、F C. E、A、G 、C、F、B、 D D. E 、G、A、C、D、F、B 9.9.下面关于图的存储的叙述中正确的是2 )。 A 用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数

4、和边数都有关D用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.10.设有关键码序列(q，g，m，z，a，n，p，x， h)，下面哪一个序列是从上述序列出发建堆的结果?( 2 ) A. a，g，h，m ， n，p，q，x，z B. a，g，m ，h，q，n，p， x，z C. g，m ，q，a， n，p，x，h，z D. h，g，m ，p，a，n，q， x，z二、二、填空题（每空1 分，共 26 分）1.1.数据的物理结构被分为_顺序、链表 _、_索引 _和_散列四种。E A G C B D F 图 1名师归纳总结 精品学习资料 - - - - - - - - -

5、- - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 1 页，共 21 页 - - - - - - - - - 2.2.对于一个长度为n 的顺序存储的线性表，在表头插入元素的时间复杂度为_o(n)_，在表尾插入元素的时间复杂度为_O(1)_。3.3.向 一 个 由HS指 向 的 链 栈 中 插 入 一 个 结 点 时p 时 ， 需 要 执 行 的 操 作 是p-next=HS,HS =p;删除一个结点时，需要执行的操作是HS=HS-next （假设栈不空而且无需回收被删除结点）。4.4.对于一棵具有n 个结点的二叉树，一个结点的编号为

6、i(1in)，若它有左孩子则左孩子结点的编号为_2i_， 若它有右孩子， 则右孩子结点的编号为_2i+1_ ，若它有双亲，则双亲结点的编号为_2/i_ 。5.5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_向上 _调整，直到被调整到根_位置为止。6.6.以二分查找方法从长度为10 的有序表中查找一个元素时，平均查找长度为_2.9_。7.7.表示图的三种常用的存储结构为邻接矩阵 _、邻接表 _和 _边集数组 _。8.8.对于线性表（70， 34，55，23， 65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数， 则散列地址为0 的元素有 _个， 散列地址为6 的有

7、_个。9.9.在归并排序中，进行每趟归并的时间复杂度为_，整个排序过程的时间复杂度为 _，空间复杂度为_。10.10.在一棵m 阶 B_树上，每个非树根结点的关键字数目最少为_个，最多为_个，其子树数目最少为_，最多为 _。三、三、运算题（每题6 分，共 24 分）1.1.写出下列中缀表达式的后缀形式：（1）（1）3X/(Y-2)+1 （2）（2）2+X*(Y+3) 2.2.试对图 2 中的二叉树画出其：(1) (1)顺序存储表示的示意图；(2) (2)二叉链表存储表示的示意图。3.3.判断以下序列是否是小根堆? 如果不是 , 将它调整为小根堆。（1） 12, 70, 33, 65, 24,

8、56, 48, 92, 86, 33 （2） 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 4.4.已知一个图的顶点集V 和边集 E 分别为： V=1,2,3,4,5,6,7; E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4, (4,7)20,(5,6)18,(6,7)25; 按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。四、四、阅读算法（每题7 分，共 14 分）1.1.void AE(Stack& S) InitStac

9、k(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); 图 2 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 2 页，共 21 页 - - - - - - - - - int i,a5=1,5,8,12,15; for(i=0;i5;i+) Push(S,2*ai); while(!StackEmpty(S) coutPop(S)left,c1,c2); c1+; if (BT-left=NULL

10、&BT-right=NULL) c2+; ABC(BT-right,c1,c2); /if 该函数执行的功能是什么？统计结点总数和叶子总数; 五、五、算法填空（共8 分）向单链表的末尾添加一个元素的算法。Void InsertRear(LNode*& HL,const ElemType& item) LNode* newptr; newptr=new LNode; If (_newptr=NULL_) cerrMemory allocation failare!data_=item; newptr-next=NULL; if (HL=NULL) HL=_newptr_; else LNode*

11、 P=HL; While (P-next!=NULL) p=p-next_; p-next=newptr; newptr=NULL newptr-=data newptr p=p-next 六、六、编写算法（共8 分）编写从类型为List的线性表L 中将第 i 个元素删除的算法， （假定不需要对i 的值进行有效性检查 , 也不用判别L 是否为空表。）void Delete(List& L, int i)for(j=i-1;jnext=HS;HS=p HS=HS-next4.4.2i 2i+1 i/2（或 i/2 ）5. 5.向上根6. 6.2.9 7. 7.邻接矩阵邻接表边集数组8. 8.1

12、49. 9.O(n) O(nlog2n) O(n)10. 10.m/2 -1 m-1 m/2 m 三、三、运算题（每题6 分，共 24 分）1.1.(1) 3 X * Y 2 - / 1 + (2)(2)2 X Y 3 + * + 2.2.（1）0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 （2）见图 3 所示：3.3.(1)不是小根堆。调整为：12,65,33,70,24,56,48,92,86,33 (2)是小根堆。4.4.普里姆算法从顶点1 出发得到最小生成树为：(1,2)3, (1,3)5, (1,4)8, (4,

13、6)4, (2,5)10, (4,7)20 四、四、阅读算法（每题7 分，共 14 分）1.1.30 24 16 10 2 10 2.2.该函数的功能是：统计出BT 所指向的二叉树的结点总数和叶子总数五、五、算法填空（共8分，每一空2 分）newptr=NULL newptr-=data newptr p=p-next 六、六、编写算法（ 8 分） void Delete(List& L, int i) for(int j=i-1;jnext=HL; B. p-next=HL-next; HL-next=p; C. p-next=HL; p=HL; D. p-next=HL; HL=p; 2.

14、2.若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（）个元素. A. n B.n-1 C. n+1 D.不确定3.3.下述哪一条是顺序存储方式的优点？（） A存储密度大 B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快4.4.设有一个二维数组Amn ，假设 A00 存放位置在600(10)，A33 存放位置在678(10)，每个元素占一个空间，问A23(10)存放在什么位置？(脚注(10)表示用 10 进制表示 ,m3) A658 B648 C 633 D653 5.5.下列关于二叉树遍历的叙述中，正确的是( ) 。A. 若一个树叶是某二叉树

15、的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点 D若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6.6.k 层二叉树的结点总数最多为( ). A2k-1 B.2K+1 C.2K-1 D. 2k-17.7.对线性表进行二分法查找，其前提条件是( ). A.A. 线性表以链接方式存储，并且按关键码值排好序B.B. 线性表以顺序方式存储，并且按关键码值的检索频率排好序C.C. 线性表以

16、顺序方式存储，并且按关键码值排好序D.D.线性表以链接方式存储，并且按关键码值的检索频率排好序8.8.对 n 个记录进行堆排序，所需要的辅助存储空间为 A. O（1og2n）B. O （ n） C. O（1） D. O（n2）9.9.对于线性表（ 7，34，77，25，64，49，20，14）进行散列存储时，若选用H （ K）=K %7作为散列函数，则散列地址为0 的元素有（）个， A 1 B2 C3 D4 10.10. 下列关于数据结构的叙述中，正确的是( ). A. A.数组是不同类型值的集合B. B.递归算法的程序结构比迭代算法的程序结构更为精炼名师归纳总结 精品学习资料 - - - -

17、 - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 5 页，共 21 页 - - - - - - - - - C. C.树是一种线性结构D. D.用一维数组存储一棵完全二叉树是有效的存储方法二、二、填空题（每空1 分，共 26 分）1.1.数据的逻辑结构被分为_、_、_和_四种。2.2.一个算法的时间复杂度为(3n3+2000nlog2n+90)/n2，其数量级表示为_。3.3.对于一个长度为n 的单链存储的队列，在表头插入元素的时间复杂度为_，在表尾插入元素的时间复杂度为_。4.4.假定一棵树的广义表表示为A

18、（ D（ E，G） ，H（I，J） ） ，则树中所含的结点数为_个，树的深度为_，树的度为 _。5.5.后缀算式79 2 30 + - 4 2 / * 的值为 _。 中缀算式（3+X*Y ） -2Y/3对应的后缀算式为_ 。6.6.在一棵高度为5 的理想平衡树中，最少含有_个结点，最多含有_个结点。7.7.在树中，一个结点的直接后继结点称为该结点的_。一个结点的直接前趋结点称为该结点的_。8.8.在一个具有10 个顶点的无向完全图中，包含有 _条边， 在一个具有 n 个顶点的有向完全图中，包含有_条边。9.9.假定一个线性表为(12,17,74,5,63,49,82,36)，若按 Key %

19、4 条件进行划分，使得同一 余数的元素成 为一个子表 ，则得到的四 个子表分别为_ 、 _ 、 _和_ 。10.10.对一棵 B_树进行删除元素的过程中，若最终引起树根结点的合并时，会使新树的高度比原树的高度_。11.11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_，整个堆排序过程的时间复杂度为_。12.12.在线性表的散列存储中，装填因子又称为装填系数，若用m 表示散列表的长度，n 表示待散列存储的元素的个数，则等于 _。三、三、运算题（每题6 分，共 24 分）1 1在如下数组A 中链接存储了一个线性表，表头指针存放在A 0.next ，试写出该线性表。 A 0 1 2 3

20、 4 5 6 7 data 60 50 78 90 34 40 next 4 0 5 2 7 1 3 2 2已 知 一 棵 二 叉 树 的 前 序 遍 历 的 结 果 是ABKCDFGHIJ, 中 序 遍 历 的 结 果 是KBCDAFHIGJ, 试画出这棵二叉树。3 3已知一个图的顶点集V 为：V=1,2,3,4,5,6,7; 其共有 10 条边。该图用如下边集数组存储：起点1 2 2 5 5 2 2 6 1 3 终点6 4 5 4 7 6 7 7 7 5 权1 1 2 2 2 3 3 4 5 7 试用克鲁斯卡尔算法依次 求出该图的最小生成树中所得到的各条边及权值。4 4画出向小根堆中加入数

21、据4, 2, 5, 8, 3, 6, 10, 1 时，每加入一个数据后堆的变化。四、四、阅读算法（每题7 分，共 14 分）1.1.在下面的每个程序段中，假定线性表La 的类型为List ，元素类型ElemType 为名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 6 页，共 21 页 - - - - - - - - - int ，并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。（1）（ 1）InitList(La); Int a=100,2

22、6,57,34,79; For (i=0;i5;i+) Insert(La,ai); TraverseList(La); （2）（ 2）DeleteFront(La); InsertRear(La, DeleteFront(La); TraverseList(La); （3）（ 3）ClearList(La); For (i=0;i5;i+) InsertFront(La,ai); TraverseList(La); 2.2.现面算法的功能是什么？void ABC(BTNode * BT) if BT coutdataleft); ABC(BT-right); 五、五、算法填空（共8 分）二分

23、查找的递归算法。 Int Binsch(ElemType A,int low,int high,KeyType K) if _ int mid=(low+high)/2; if (_) return mid; /查找成功，返回元素的下标 else if (KAmid.key) return Binsch(A,low,mid-1,K); /在左子表上继续查找 else return_； /在右子表上继续查找 else _； /查找失败，返回-1 六、六、编写算法（共8 分）HL 为单链表的表头指针，试写出在该单链表中查找具有给定的元素item 的算法。bool Find(LNode* HL, E

24、lemType &item)模拟试卷二参考答案一、一、单选题（每题2 分，共 20 分）1.B 2.B 3.A 4.C 5.D 6.A 7.C 8.C 9.D 10.D 二、二、填空题（每空1 分，共 26 分）名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 7 页，共 21 页 - - - - - - - - - 1.1.集合结构线性结构树结构图结构2.2.O(n) 3.3.O(1) O(1) 4.4.7 2 2 5.5.94 3 X Y * + 2 Y * 3

25、/ - 6.6.16 31 7.7.孩子（或子）结点双亲（或父）结点8.8.45 n(n-1) 9.9.（12，36）（17,5,49 ）（74，82）（63）10.10.减少 1（或减少）11.11.O(log2n) O(nlog2n) 12.12.n/m 三、三、运算题（每题6 分，共 24 分）1.1.线性表为：（90，40，78， 50，34，60）2.2.当前序序列为ABKCDFGHIJ ，中序序列为KBCDAFHIGJ时，逐步形成二叉树的过程如下图4 所示：图 4 3.3.用克鲁斯卡尔算法得到的最小生成树为：(1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)

26、3, (3,5)7 4.4.见图 5。图 5 四、四、阅读算法（每题7 分，共 14 分）1.1.(1) La=(26,34,57,79,100) (2)La=(57,79,100,34) (3)La=(79,34,57,26,100) 2.2.前序遍历链式存储的二叉树。五、五、算法填空（每空2 分，共 8 分）(lowdata=item) return true; else p=p-next; return false; 模拟试卷三一、一、单选题（每题2 分，共 20 分）1.1.对一个算法的评价，不包括如下（）方面的内容。A健壮性和可读性B并行性C正确性D时空复杂度2.2.在带有头结点的单

27、链表HL 中，要向表头插入一个由指针p 指向的结点， 则执行( )。 A. p-next=HL-next; HL-next=p; B. p-next=HL; HL=p; C. p-next=HL; p=HL; D. HL=p; p-next=HL; 3.3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变4.4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5.AOV

28、 网是一种（） 。A有向图B无向图C无向无环图D有向无环图6.6.采用开放定址法处理散列表的冲突时，其平均查找长度（） 。A低于链接法处理冲突B. 高于链接法处理冲突C与链接法处理冲突相同D高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。A值B函数C指针D引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（） 。A行号B列号C元素值D非零元素个数9.9.快速排序在最坏情况下的时间复杂度为（） 。AO(log2n) BO(nlog2n) C0(n) D0(n2) 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A

29、. O(n) B. O(1) C. O(log2n) D. O(n2)二、二、运算题（每题6 分，共 24 分）1.1.数据结构是指数据及其相互之间的_。 当结点之间存在M 对 N（M：N）的联系时，称这种结构为_。2.2.队列的插入操作是在队列的_进行，删除操作是在队列的_进名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 9 页，共 21 页 - - - - - - - - - 行。3.3.当用长度为N 的数组顺序存储一个栈时，假定用top=N 表示栈空，则表示栈

30、满的条件是 _。4.4.对于一个长度为n 的单链存储的线性表，在表头插入元素的时间复杂度为_，在表尾插入元素的时间复杂度为_。5.5.设 W 为一个二维数组，其每个数据元素占用4 个字节，行下标i 从 0 到 7 ，列下标 j 从 0 到 3 ，则二维数组W 的数据元素共占用_个字节。 W 中第 6 行的元素和第 4 列的元素共占用_个字节。 若按行顺序存放二维数组W，其起始地址为 100，则二维数组元素W6 ，3的起始地址为_。6.6.广 义 表A= (a,(a,b),(a,b),c), 则 它 的 深 度 为 _ ， 它 的 长 度 为_。7.7.二叉树是指度为2 的_树。一棵结点数为N

31、的二叉树，其所有结点的度的总和是_。8.8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个_。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的_。9.9.对 于 一 棵 具 有n 个 结 点 的 二 叉 树 ， 用 二 叉 链 表 存 储 时 ， 其 指 针 总 数 为_个，其中 _个用于指向孩子，_个指针是空闲的。10.10.若对一棵完全二叉树从0 开始进行结点的编号，并按此编号把它顺序存储到一维数组 A 中，即编号为0 的结点存储到A0 中。其余类推，则A i 元素的左孩子元素为_,右孩子元素为_，双亲元素为_。11.11.在线性表的散列存储中，处理冲突的

32、常用方法有_ 和_ 两种。12.12.当 待 排 序 的 记 录 数 较 大 ， 排 序 码 较 随 机 且 对 稳 定 性 不 作 要 求 时 ， 宜 采 用_排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用 _排序。三、三、运算题（每题6 分，共 24 分）1.1.已知一个6 5 稀疏矩阵如右所示，试：（1） （1） 写出它的三元组线性表；（2） （2） 给出三元组线性表的顺序存储表示。2.2.设有一个输入数据的序列是 46, 25, 78, 62, 12, 80 , 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。3.3.对于图6 所示的有向图若存储它采用邻接表，并

33、且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：(1) 从顶点出发进行深度优先搜索所得到的深度优先生成树；(2) 从顶点出发进行广度优先搜索所得到的广度优先生成树；4.4.已知一个图的顶点集V 和边集 E 分别为： V=1,2,3,4,5,6,7; E=,; 若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到007000000520000000100000010000图 6 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第

34、10 页，共 21 页 - - - - - - - - - 大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。四、四、阅读算法（每题7 分，共 14 分）1.1.int Prime(int n) int i=1; int x=(int) sqrt(n); while (+ix) return 1; else return 0; (1)(1)指出该算法的功能；(2)(2)该算法的时间复杂度是多少？2.2.写出下述算法的功能：void AJ(adjlist GL, int i, int n) Queue Q; InitQueue(Q); coutiadjvex; i

35、f(!visitedj) coutjnext; 五、五、算法填空（共8 分）如下为二分查找的非递归算法，试将其填写完整。Int Binsch(ElemType A ,int n,KeyType K) int low=0; int high=n-1; 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 11 页，共 21 页 - - - - - - - - - while (low=high) int mid=_ ；if (K=Amid.key) return mid;

36、/查找成功，返回元素的下标else if (Kmid.key) _; /在左子表上继续查找else _; /在右子表上继续查找 return -1; /查找失败，返回-1 六、六、编写算法（共8 分）HL 是单链表的头指针，试写出删除头结点的算法。ElemType DeleFront(LNode * & HL) 模拟试卷三参考答案一、一、单选题（每题2 分，共 20 分）1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C 二、二、填空题（每空1 分，共 26 分）1.1.联系图（或图结构）2.2.尾首3.3.top=0 4.4.O（1）O（n）5.5.128 44

37、 108 6.6.3 3 7.7.有序n-1 8.8.有序序列后缀表达式（或逆波兰式）9.9.2n n-1 n+1 10.10.2i+1 2i+2 (i-1)/2 11.11.开放定址法链接法12.12.快速归并6 5 5 1 5 1 3 2 -1 4 5 -2 5 1 5 6 3 7 图 7 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 12 页，共 21 页 - - - - - - - - - 三、三、运算题（每题6 分，共 24 分）1.1.（1）(1,5,

38、1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7) (3 分) （2）三元组线性表的顺序存储表示如图7 示。2.2.如图 8 所示。3.3.DFS：BFS：4.4.拓朴排序为：4 3 6 5 7 2 1 四、四、阅读算法（每题7 分，共 14 分）1.1.(1) 判断 n 是否是素数（或质数）（2）O（n）2.2.功能为：从初始点vi出发广度优先搜索由邻接表GL 所表示的图。五、五、算法填空（ 8 分）(low+high)/2 high=mid-1 low=mid+1 六、六、编写算法（ 8 分）ElemType DeleFront(LNode * & HL) if (H

39、L=NULL) cerr空表 next; ElemType temp=p-data; delete p; return temp; 模拟试卷四一、一、单选题（每题2 分，共 20 分）1.1.以下数据结构中哪一个是线性结构？( ) A. 有向图B. 栈C. 二叉树D. B 树2.2.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用 ( )存储方式最节省时间。A.单链表B.双链表C.带头结点的双循环链表D.单循环链表图 8名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - -

40、- - - - - - - 第 13 页，共 21 页 - - - - - - - - - 3.3.以下哪一个不是队列的基本运算？（）A. 在队列第 i 个元素之后插入一个元素B. 从队头删除一个元素C. 判断一个队列是否为空D.读取队头元素的值4.4.字符 A、B、C、D 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.15 B.14 C.16 D.21 5.5.由权值分别为4,7,6,2 的叶子生成一棵哈夫曼树，它的带权路径长度为( )。A 11 B.37 C. 19 D. 53 以下 6-8 题基于下面的叙述：若某二叉树结点的中序遍历的序列为A

41、、B、C、D、E、F、G，后序遍历的序列为B、 D、 C、 A、 F、G、E。6.6.则该二叉树结点的前序遍历的序列为( ). A. E、G、F、A、 C、D、B B. E、A、G 、 C、F、B、D C. E、A、C、B、 D、G、F D. E、G 、A、C、D、F、 B 7.7.该二叉树有（）个叶子。 A3 B.2 C.5 D.4 8.8.该二叉树的按层遍历的序列为( ) AE、G、F、A、C、D 、 B B. E、A、C、B、D、G 、F C. E、A、G 、C、F、B、 D D. E 、G、A、C、D、F、B 9.9.下面的二叉树中，( )不是完全二叉树。10.10.设有关键码序列(q

42、，g，m，z，a)，下面哪一个序列是从上述序列出发建的小根堆的结果 ?( ) A. a，g ，m ，q， z B. a， g ，m ，z,q C. g ，m ，q，a，z D. g， m， a ，q，z 二、二、填空题（每空1 分，共 26 分）1.1.数据结构是指数据及其相互之间的_ 。当结点之间存在1 对 N（1：N）的联系时，称这种结构为_。2.2.一个广义表中的元素分为_元素和 _元素两类。3.3.对于一个长度为n 的顺序存储的线性表，在表头插入元素的时间复杂度为_，在表尾插入元素的时间复杂度为_。4.4.向 一 个 由HS指 向 的 链 栈 中 插 入 一 个 结 点 时p时 ， 需

43、 要 执 行 的 操 作 是_;删除一个结点时，需要执行的操作是_（假设栈不空而且无需回收被删除结点）。5.5.栈又称为 _表，队列又称为_表。6.6.在稀疏矩阵所对应的三元组线性表中，每个三元组元素按_为主序、_为辅序的次序排列。7.7.若一棵二叉树中只有叶子结点和左、右子树皆非空的结点，设叶结点的个数为K，则左、右子树皆非空的结点个数是_。8.8.以折半（或二分）查找方法从长度为8 的有序表中查找一个元素时，平均查找长度为 _。名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - -

44、 - - 第 14 页，共 21 页 - - - - - - - - - 9.9.表 示 图 的 三 种 常 用 的 存 储 结 构 为 _ 、 _ 和_。10.10.对于线性表（ 78，4，56，30， 65）进行散列存储时，若选用H（K）=K %5 作为散列函数，则散列地址为0 的元素有 _个，散列地址为4 的有 _个。11.11.在归并排序中，进行每趟归并的时间复杂度为_，整个排序过程的时间复杂度为 _，空间复杂度为_。12.12.在 n 个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为_。WPL 称为 _。13.13.在索引表中，若一个索引项对应主表的一个记录，则此索引

45、为_索引，若对应主表的若干条记录，则称此索引为_索引。三、三、运算题（每题6 分，共 24 分）1.1.写出下列中缀表达式的后缀形式：（1）（1）3X/(Y-2H)+1 （2）（2）2+X*(Y+3) 2.2.假定一棵二叉树广义表表示为a(b(c),d(e,f) ，分别写出对它进行先序、中序、后序、按层遍历的结果。先序：中序：后序：按层：3.3.已知一个无向图的顶点集为a, b, c, d, e , 其邻接矩阵如下所示0100110010000110110110110(1) 画出该图的图形；（2）根据邻接矩阵从顶点a 出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。4.4.已知一个图的

46、顶点集V 和边集 E 分别为： V=0,1,2,3,4,5,6,7; E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20; 按照普里姆算法从顶点0 出发得到最小生成树，试写出在最小生成树中依次得到的各条边。四、四、阅读算法（每题7 分，共 14 分）1.1.void AE(Stack& S) InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); a b c d e 名师归纳总结 精品学习资料 - - - -

47、- - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 15 页，共 21 页 - - - - - - - - - int i,a5=2,5,8,22,15; for(i=0;i5;i+) Push(S,ai); while(!StackEmpty(S) coutPop(S)data;/查找成功 return true; else if(itemdata) BST=BST-_; else BST=BST-_; /while return _;/查找失败 六、六、编写算法（共8 分）用递归的算法编写出对存入在an+1

48、数组中的n 个有序元素进行二分（又称折半） 查找（假定 a0 单元不用）的程序。int halfsearch(SSTable *a, KeyType k,int low,int high)模拟试卷四参考答案一、一、单选题（每题2 分，共 20 分）1.B 2.C 3.A 4.B 5.B 6.C 7.A 8.C 9.C 10.B 二、二、填空题（每空1 分，共 26 分）1.1.联系树（或树结构）2.2.单（子）表3.3.O(n) O(1)4.4.p-next=HS;HS=p HS=HS-next5.5.先进后出先进先出6.6.行列7.7.k-1 8.8.2.625 9.9.邻接矩阵邻接表边集数

49、组10. 10. 2 111. 11. O(n) O(nlog2n) O(n)名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 16 页，共 21 页 - - - - - - - - - 12. 12. 哈夫曼树带权路径长度13. 13. 稠密稀疏三、三、运算题（每题6 分，共 24 分）1.1.(1) 3 X * Y 2 H *- / 1 + （2）2 X Y 3 + * + 2.2.先序：a,b,c,d,e,f 中序： c,b,a,e,d,f 后序： c,b,e,

50、f,d,a 按层：a,b,d,c,e,f 3.3.（1）该图的图形如图9 示：（2）深度优先遍历序列为：abdce 广度优先遍历序列为：abedc 4.4.普里姆： (0,3)2, (0,2)5, (0,1)8, (1,5)6, (3,6)10, (6,4)4, (5,7)20 四、四、阅读算法（每题7 分，共 14 分）3.3.15 22 8 5 2 10 4.4.该函数的功能是：求：akmmnnmakmmmnakmmakmmnmn( , )(, ),(,( ,),101 1001100当时当时当时五、五、算法填空（共8 分，每一空2 分） BST-data left right false