《数据结构》模拟题（开卷）一、单项选择题1.分析下列算法suanfa1(n):void suanfa1(int n){ int i,j,x=1；for(i=0；i<n；i++)for(j=0；j<n；j++)x=x*2；printf("%d",x)}其中语句"x=x*2；"的执行次数是( D )。
A.(n*2)2B.(n-1)2C.(n+1)2D.n22.折半查找有序表(16,20,30,35,40,46,60,80),若查找元素80,需依次与表元素( D )进行比较。
A.35,46,80B.40,60C.40,60,80D.35,46,60,803.对长度为10的表作选择(简单选择)排序,共需比较( A )次关键字。
A.45B.90C.10D.1104.下列算法suanfa2(n)的时间复杂度为( A )。
int suanfa1(int n){ int i,x=0；for (i=0；i<5；i++)for (j=1；j<=n；j++)x+=2；return x；}A.O(n)B.O(n5)C.O(5n)D.O(n2)5.线性表在( B )时, 宜用顺序表作存储结构。
A.经常作插入、删除B.经常随机存取C.无足够连续存储空间D.经常作动态查找6.设广义表LS=((a,b),c,(d,e)),执行操作GetTail(GetHead(LS))后的结果是( A )。
A.(b)B.bC.(c,(d,e))D.(a,b)7.深度为k的满二叉树有( C )个叶子。
A.k2-1B.2K-1-1C.2K-1D.k28.有16个顶点的无向图最多可能有( D )个连通分量。
A.32B.8C.256D.169. ( C )是'Hua**Zhong**Da'的子串。
A.HuaB.zhongC.'*Da'D.'HuaZhongDa'10.字符串的长度指的是串中( B )的个数。
A.不同字符B.字符C.字母D.字母和数字二、多项选择题1.设哈希(Hash)函数为H(k)=k MOD 7,其中k是关键字,MOD为取模(求余)运算，下列关键字( ACD )是同义词。
A.29,22,15B.1,2,3,4C.23,16,9D.7,14,492.一个算法具有( AC )等特点。
A.可行性B.健壮性C.确定性D.至少有一个输入量3.对单链表可以进行( BCD )的操作A.折半查找B.顺序查找C.删除结点D.插入结点4.若依次进栈的元素为a,b,c,d,可得到出栈的元素序列( ACD )。
A.a,b,c,dB.c,a,b,dC.b,c,d,aD.d,c,b,a三、填空题1.有向图的存储结构有___邻接表、逆邻接表、十字链表__等表示法。
2.若7行6列的数组a以列序为主序顺序存储，基地址为1024,每个元素占2个存储单元,则第3行第5列的元素(假定无第0行第0列)的存储地址是_1084_。
3.折半查找有序表(4,6,7,8,9,10,12,20,24,37,77,110),若查找值为9的元素,它将依次与表中元素___10,7,8,9_比较大小；若查找值为80的元素,它将依次与表中元素___10,24,77,110__比较大小。
4._____树中各结点的层的最大值___ 称为树的深度。
5._______线性表中元素的数目______称为线性表的长度。
6.____限定在表头作删除,在表尾作插入_____的线性表称为队列。
7.设n个元素的线性表顺序存储,若在它的第i个(1≤i≤n)元素之后插入一个新元素,共需移动____ n-i ___个元素。
8.构造Hash函数的方法有直接定址法、随机数法、_数字分析法、除留余数法、平方取中法、折叠法__等。
9.对n个记录的表进行简单选择排序,共计需要进行__ n(n-1)/2_次比较关键字,在最坏情况下,共计交换___ n-1___对记录。
10.字符串A中_连续字符组成子序列_称为串A的子串,_仅由空格字符组成的字符串称为空格串。
11.深度为k(k>0)的满二叉树共有_____2k-1-1__个非叶子。
12.在有向图G中,以顶点i为__弧尾的弧_的数目称为i的出度。
13..有n(n>0)个结点的完全二叉树的深度为⎡log2(n+1)⎤或⎣log2n+1⎦或⎣log2n⎦+1。
四、画图题1.试画出下列稀疏矩阵以行序为主序的三元组表。
稀疏矩阵参考答案：1.行序为主序的三元组表。
12342.下列树的双亲表示法: 参考答案：2.下列树的双亲表示法:3.试画出下列有向图G的逆邻接表。
有向图G参考答案：3.有向图的逆邻接表:4.二叉树T的顺序存储结构:参考答案：4.二叉树T的顺序存储结构:5.已知二叉树的前序遍历序列和中序遍历序列分别是：B,A,C,D,E,F和B,D,C,E,A,F试画出该二叉树。
参考答案：5.前序遍历序列和中序遍历序列分别是：B,A,C,D,E,F和B,D,C,E,A,F, 对应的二叉树如下:五、求解下列问题1.依次输入元素10,6,8,3,7,42,25,30,27,60, 试生成一棵二叉排序树,(1)画出生成之后的二叉排序树；(2)对该二叉排序树作中序、逆中序遍历，写出遍历序列,(3)假定每个元素的查找概率相等,试计算查找成功时平均查找长度。
参考答案：1.依次输入元素10,6,8,3,7,42,25,30,27,60, 试生成一棵二叉排序树, (1)生成的二叉排序树是:(2)中序遍历序列: 3,6,7,8,10,25,27,30,42,60逆中序遍历序列: 60,42,30,27,25,10,8,7,6,3(3)查找成功时平均查找长度:ASL=(1+2+2+3+3+3+3+4+4+5)/10=3.02.试按表(30,11,18,4,55,19,15,70,58)中元素的排列次序,将所有元素插入一棵初始为空的二叉排序树中,使之仍是一棵二叉排序树。
(1)画出插入完成之后的二叉排序树；(2)假设每个元素的查找概率相等,计算该树的平均查找长度ASL。
参考答案： 2.解:(1)构造二叉排序树:(2)平均查找长度: ASL=(1+2+2+3+3+3+4+4+4)/9=26/9≈2.93.试对下列网,(1)从顶点A出发,求(画)出一棵宽度优先生成树；(2)从顶点D出发,用Prim(普里姆)算法求出一棵最小生成树，写出求解过程。
参考答案：3.(1)从顶点A出发,宽度优先生成树之一；•(1)从顶点D出发,用Prim(普里姆)算法求出最小生成树之一:(2)六、设计题1.设单链表的结点为(data,next),其中data为整型, next为指针型,试用C语言类型定义分别写出结点类型和指针类型的定义。
参考答案：1.设单链表的结点为(data,next),其中data为整型, next为指针型,试用C语言类型定义分别写出结点类型和指针类型的定义。
typedef struct node{ int data;struct node *mext;}node,*linklist;七、简答题1.二叉树有哪几种基本形态? 试举例说明。
参考答案：1.答:二叉树有5种基本形态,举例如下：其中：B1:为空二叉树；B2:有根结点,左右子树均为空二叉树；B3:有根结点,左子树为非空二叉树,右子树为空二叉树；B4:有根结点,左子树为空二叉树,右子树为非空二叉树；B5:有根结点,左右子树均为非空二叉树。
2.线性表的顺序存储结构和链式存储结构各有哪些优点和缺点?参考答案：2.答:对于顺序存储结构:(1)优点:是一种随机存取结构,存取任何元素的时间是一个常数,速度快；结构简单,逻辑上相邻的元素在物理上也是相邻的；不使用指针,节省存储空间。
(2)缺点:插入和删除元素,平均需要移动约半个表的元素,消耗大量时间；需要提供一个连续的存储空间；插入元素可能发生“溢出”；表尾之后的自由存储空间不能被其它表的数据占用(共享)。
对于链式存储结构:(1)优点:插入和删除元素,不必移动元素,只需修改相关结点的指针；不需要一个连续的存储空间。
(2)缺点:不是随机存取结构,查找元素的时间与元素在表中位置有关,不是一个常数；使用指针,指针需占用一定的存储空间；系统需提供动态存储管理功能。
八、算法说明:输入一列整数,以0为结束标志,生成带头结点的递增有序单链表。
结点类型定义和算法：struct Lnode{ int data；struct Lnode *next；}；struct Lnode *creat( ){ struct Lnode *head,*f,*q,*p；int e；head=(struct Lnode *)malloc(struct Lnode)；head->next=NULL；do{ f=________________________________；scanf("%d",&e)；f->data=e；q=head；p=_______________；while (p && e>p->data){ q=________； p=__________；}f->next=____； q->next=_____；}while(e)；return head；}参考答案：八、算法填空struct Lnode{ int data；struct Lnode *next；}；struct Lnode *creat( ){ struct Lnode *head,*f,*q,*p；int e；head=(struct Lnode *)malloc(struct Lnode)；head->next=NULL；do{ f=(struct Lnode *)malloc(structLnode)；scanf("%d",&e)；f->data=e；q=head；p=p->next；while(p && e>p->data){ q=p； p=p->next；} (* 或 q=q->next； p=q->next；*) f->next=p； q->next=f；}while(e)；return head；}。