模拟试卷一一、 一、 单选题（每题 2 分，共20分）1. 1. 以下数据结构中哪一个是线性结构？( )A. 有向图B. 队列C. 线索二叉树D. B 树2. 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. 3. 以下哪一个不是队列的基本运算？（ ）A. 在队列第i 个元素之后插入一个元素B. 从队头删除一个元素C. 判断一个队列是否为空D.读取队头元素的值4. 4. 字符A 、B 、C 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( )个不同的字符串？A.14B.5C.6D.85. 5. 由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。
A ． 11 B.35 C. 19 D. 53以下6-8题基于图1。
6. 6. 该二叉树结点的前序遍历的序列为( )。
A. A. E 、G 、F 、A 、C 、D 、BB. B. E 、A 、G 、C 、F 、B 、DC. C. E 、A 、C 、B 、D 、G 、FD. D. E 、G 、A 、C 、D 、F 、B7. 7. 该二叉树结点的中序遍历的序列为( )。
A. A 、B 、C 、D 、E 、G 、FB. E 、A 、G 、C 、F 、B 、DC. E 、A 、C 、B 、D 、G 、F E. E. B 、D 、C 、A 、F 、G 、E8. 8. 该二叉树的按层遍历的序列为( )。
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. 9. 下面关于图的存储的叙述中正确的是( )。
A ．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B ．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D ．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关EA G CB D F 图110.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二、三、运算题（每题 6 分，共24分）1. 1. 写出下列中缀表达式的后缀形式：（1）（1）3X/(Y-2)+1（2）（2）2+X*(Y+3)2. 2. 试对图2中的二叉树画出其：(1)(1) 顺序存储表示的示意图；(2)(2) 二叉链表存储表示的示意图。
F33. 判断以下序列是否是小根堆? 如果不是,图2将它调整为小根堆。
（1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 }3. 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出发得到最小生成树，试写出在最小生成树中依次得到的各条边。
三、六、编写算法（共8分）编写从类型为List的线性表L中将第i个元素删除的算法，（假定不需要对i的值进行有效性检查,也不用判别L是否为空表。
）void Delete(List& L, int i)模拟试卷一参考答案一、一、单选题（每题2分，共20分）1.B2.D3.A4.B5.B6.C7.A8.C9.B 10.B1.二、运算题（每题6分，共24分）1.(1) 3 X * Y 2 - / 1 +(2) 2 X Y 3 + * +2.（1）0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 161 2 3 4 5 6 7 8 9（2）见图3所示：3.(1)不是小根堆。
调整为：{12,65,33,70,24,56,48,92,86,33}(2)是小根堆。
4.普里姆算法从顶点1出发得到最小生成树为：(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20三、编写算法（8分）void Delete(List& L, int i){for(int j=i-1;j<L.size-1; j++)L.list[j]=L.list[j+1]; //第i个元素的下标为i-1L.size--;}模拟试卷二一、单选题（每题 2 分，共20分）1. 1. 在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。
A. HL=p; p->next=HL;B. p->next=HL->next; HL->next=p;C. p->next=HL; p=HL;D. p->next=HL; HL=p;2.若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（）个元素.A. nB.n-1C. n+1D.不确定3.下述哪一条是顺序存储方式的优点？（）A．存储密度大 B.插入和删除运算方便C. 获取符合某种条件的元素方便D.查找运算速度快4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？(脚注(10)表示用10进制表示,m>3)A．658 B．648 C．633 D．6535.下列关于二叉树遍历的叙述中，正确的是( ) 。
A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6.k层二叉树的结点总数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.对线性表进行二分法查找，其前提条件是( ).A.A.线性表以链接方式存储，并且按关键码值排好序B.B.线性表以顺序方式存储，并且按关键码值的检索频率排好序C.C. 线性表以顺序方式存储，并且按关键码值排好序D.D.线性表以链接方式存储，并且按关键码值的检索频率排好序8.对n个记录进行堆排序，所需要的辅助存储空间为n） B. O（n） C. O（1） D. O（n2） A. O（1og29. 对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H （K ）=K %7作为散列函数，则散列地址为0的元素有（ ）个，A ．1B ．2C ．3D ．410. 下列关于数据结构的叙述中，正确的是( ).A. 数组是不同类型值的集合B. 递归算法的程序结构比迭代算法的程序结构更为精炼C. 树是一种线性结构D. 用一维数组存储一棵完全二叉树是有效的存储方法二、三、 运算题（每题 6 分，共24分）1． 在如下数组A 中链接存储了一个线性表，表头指针存放在A [ 0].next ，试写出该线性表。
A 0 1 2 3 4 5 6 7data 60 50 78 90 34 40next 4 0 5 2 7 1 32． 已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ, 中序遍历的结果是KBCDAFHIGJ, 试画出这棵二叉树。
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, 2, 5, 8, 3, 6, 10, 1时，每加入一个数据后堆的变化。
四、五、 编写算法（共8分）HL 为单链表的表头指针，试写出在该单链表中查找具有给定的元素item 的算法。
bool Find(LNode* HL, ElemType &item)模拟试卷二参考答案一、 一、 单选题（每题2分，共20分）1.B2.B3.A4.C5.D6.A7.C8.C9.D 10.D1. O(log 2n) O(nlog 2n)2. n/m二、 三、 运算题（每题6分，共24分）1. 线性表为：（90，40，78，50，34，60）2. 当前序序列为ABKCDFGHIJ ，中序序列为KBCDAFHIGJ 时，逐步形成二叉树的过程如下图4所示：FHIGJ A A B K F CD HIGJ A B K F C D G J HI A B K F C D G JH图4 3. 用克鲁斯卡尔算法得到的最小生成树为：(1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)74. 见图5。
三、 编写算法（8分）bool Find(LNode* HL, ElemType &item){LNode* p=HL;while pif (p->data==item){return true;}else p=p->next;return false;}模拟试卷三一、 单选题（每题 2 分，共20分）1. 对一个算法的评价，不包括如下（ ）方面的内容。
A ．健壮性和可读性B ．并行性C ．正确性D ．时空复杂度2. 在带有头结点的单链表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. 对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 3 KBCD I 4 4 4 4 4 2 2 2 5 5 5 2 2 8 8 4 35 2 8 3 4 5 2 8 3 46 5 2 8 3 4 6 10 5 1 3 2 4 6 10 85. AOV 网是一种（ ）。