数据结构导论模拟试卷(二)
一、单项选择题(在每小题的4个备选答案中．选出1个正确的答案，并将其号码填在题干后的括号内。每小题2分，共30分)
1．一个具有n个顶点的无向完全图的边数为( )。
n(n?1)n(n?1)2 B) 2A) C) n(n?1) D) n(n?1)
2．在索引顺序表中查找一个元素，可用的且最快的方法是( )
A)用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找 B)用顺序查找法确定元素所在块，再用二分查找法在相应块中查技 c)用二分查找法确定元素所在块，再用顺序查找法在相应块中查我 D)用二分查找法确定元素所在块，再用二分查找法在相应块中查找
3．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。 A)单链表 B)双链表
C)带头结点的双循环链表 D)容量足够大的顺序表 4．串是( )。
A)一些符号构成的序列 B)有限个字母构成的序列 C)一个以上的字符构成的序列 D)有限个字符构成的序列 5．堆排序在最坏情况下，其时间复杂性为( )。
A)O(nlog2n) B)O(n2) C)O(log2n2) D)O(log2n) 6．快速排序的记录移动次数( )比较次数．其总执行时间为O(nlog2n)。
A)大于 B)大于等于 C)小于等于 D)小于
7．一棵二叉树有n个结点，要按某顺序对该二叉树中的结点编号(号码为l~n)，编号须具 有如下性质：二叉树中任一结点V，其编号等于其左子树中结点的最大编号加l，而其右子树中结点的最小编号等于V的编号加l。试问应按( )遍历顺序编号。
A)前根 B)中根 C)后根 D)层次 8．3个结点可构成( )个不同形态的二叉树。
A)2 B)3 C)4 D)5 9．对有n个记录的有序表采用二分查找其平均查找长度的量级为( )。
2A) O(log2n) B) O(nlog2n) C) O(n) D)O(n)
10．对有n个记录的表按记录键值有序的顺序建立二叉排序树，在这种情况下．其平均查找 长度的量级为( )。 A)O(n) B) O(nlog2n) C)O(1) D)O(log2n)
11．栈操作的原则是( )。
A)先进先出 B)后进先出 C)栈顶插入 D)栈顶删除 12．设矩阵A是一对称矩阵(aij?aji,1?i,j?8)，若每个矩阵元素占3个单元，将其上三角部分(包括对角线)按行序为主序存放在数组B中，B的首址为1000，则矩阵元素a67的地址为( )。
A)1031 B)1093 C)1096 D)1032
13．链表适用于顺序查找，但在链表中进行( )操作的效率比在顺序存储结构中进行同样 操作的效率高。
A)顺序查找 B)二分法查找 C)快速查找 D)插入 14．任何一个无向连通图的最小生成树( )。
A)只有一棵 B)有一棵或多棵 c)一定有多棵 D)可能不存在 15．以下有关数据结构的叙述，( )是正确的。 A)线性表的线性存储结构优于链式存储结构
B)二叉树的第i层上有2i-1个结点，深度为K的二叉树上有2k-1个结点 c)二维数组是其数据元素为线性表的线性表 D)栈的操作方式是先进先出。
二、填空题(每空2分，共28分)
1．在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句： ；L->next=U->next；free(U)； 2．有一个长度为20的有序表采用二分查找方法进行查找，共有 个元素的查找长度为3。 3．采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为 。若A初始状态为递减排列，则记录的交换次数为 。
4．在无头结点的双链表中，指针P所指结点是第一个结点的条件是 。
5．G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索．即可访问图的每个顶点，则该图一定是 图。
6．如果一个有向图中没有 ，则该图的全部顶点可以排成一个拓扑序列。 7．深度为8(根的层次号为1)的满二叉树有 个叶子结点。 8．将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT(X) 的编号为 。
9．分别采用堆排序、快速排序、冒泡排序和归并排序算法，对初始状态为递增序列的表按递增顺序排序，最省时的时 算法，最费时间的是 树算法 10．设有一个链队，结点结构为
，front为队头指针．rear为队尾指针，当
执行入队操作时需执行下列语句：
malloc(p)；p->data=x；p->next=NUlLL; ；
11．有向图G用邻接矩阵A[l．．n，l．．n]存储，其第i列的所有元素之和等于顶点i的 。
三、应用题(共28分)
1. 有向图G的邻接表如图11所示，若删去图G中的边
后图的邻接表。(4分)
顶点 入度
V1 0 2 1 ∧
V2 1 3 ∧
V3 4 6 ∧ V4 0 3 5 ∧
V5 1 3 ∧
V6 1 ∧
图11 图G的邻接表
2．对下列有向图12，写出以顶点1为出发点对图进行深度优先搜索所得到的所有可能的访问序列。(4分)
图12有向图
3．对于键值序列(49，38，65，97，76，13，27，50)，使用堆排序算法完成排序过程。要求：
1)画出初始堆(用二叉树表示)。(2分)
2)画出分别输出13，27后重建的两个堆。(4分)
4．一个深度为d(根的层次号为1)的满K叉树有如下性质：第d层上的结点都是叶子结点，其余各层上的每个结点都有K棵非空子树。如果从根这一层开始按从左到右顺序逐层对全部结点编号，且根结点的编号为1，问编号为n的结点有右兄弟的条件是什么?其右兄弟的编号是多少?(4分)
5．给定权值{5，10，12，15，30，40}，构造相应的赫夫曼树，要求写出构造步骤。(4分) 6．已知一表为(Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec)。按表中顺序依次插入初始为空的二叉排序树，要求：
1)画出建立的二叉排序树。(4分)
2)求出在等概率情况下查找成功的平均查找长度。(2分)
四、设计题(共14分)
1．设有一单链表L，结点结构为
，结点个数至少3个，试画出链表L的结
构图，并编写算法判断该单链表L中的元素是否成等差关系，即：设各元素值依次为a1，a2，a3，…，an，判断ai+1-ai= ai- ai-1是否成立，其中i满足2≤i≤n-l。(8分) 2．设一棵二叉树以二叉链表作为存储结构，结点结构为
，其中data域中存放一个字符，设计一个算法按先序遍历顺序仅打印出dam域为数字的字符 (即‘0’≤data≤‘9’)。(6分)
数据结构导论模拟试卷(二)分析与解答
一、单项选择题
1，B. 2，C. 3，D. 4，D. 5，A. 6，C. 7，B. 8，D. 9，A. 10，A. 11，B. 12，B. 13，D. 14，B. 15，C.
二、填空题
1.分析：在带有头结点的单链表L上删除第一个结点，需依次执行以下三条语句： 1) U=L->next； 2) L->next=U->next； 3) free(U)
答案：U=L->next。
2．分析：二分查找的过程可以用一棵有序树来表示，该树第三层上有4个结点，表示经过三次比较查找成功的元素个数为4。 答案：4。
3．分析：采用冒泡排序时，若初始时已经自然有序，那么经过一趟n-1次比比较后，算法就自动终止了。若初始状态为递减排列，希望排序成递增排列，则排序过程中比较一次、交换一次，总的比较、交换次数为n(n-1)／2，其中n-1为趟数，n／2为平均每趟的比较交换次数。 答案：n(n-1)／2。 4．答案：p->prior=NULL。
5．分析：对无向图来讲，不管是对它进行一次探度优先搜索还是广度优先搜索，如果都能访问到图的每个顶点，则该图一定是个连通图。 答案：连通。
6．分析：一个有向图存在拓扑序列的条件之一是有向图中不存在回路或环。 答案：回路或环。 7．答案：28-1=27=128。
8．分析：完全二叉树按层编号后，编号为m的结点，其双亲结点的编号为??m?。故?2??当m=49时，其双亲编号为?答案：24。
?49?=24。 ??2?9．答案：冒泡排序、快速排序。 10．答案：rear一>next=p，rear=p。 11．答案：入度
三、应用题
1．分析：在图11所示的有向图的邻接表上删除一条边时．不仅要在对应的出边表中删
除一个结点，而且还要修改对应顶点的入度值。 答案：修改后的有向图G的邻接表如图13所示。
顶点 入度 V1 V2 V3 V4 V5 V6 0 1 4 0 0 0 ∧ 2 3 3 3 ∧ ∧ ∧ 1 ∧ 图13 修改后的有向图G的邻接表
2．答案：共有3个访问序列：
l，2，5，4．3，6 l，3，6，4，5，2
1．3，5，4，6，2
3．分析：建堆过程参见前述(8.1节的有关说明)。在排序过程中，每输出一次根结点的 键值，都要对二叉树调整一次，使其成为一个新的堆。
答案：1)初始堆如图14所示。