《数据结构模拟题》由会员分享，可在线阅读，更多相关《数据结构模拟题（9页珍藏版）》请在金锄头文库上搜索。
1、数据结构模拟题一、单项选择题1. 分析下列算法 suanfa1(n):void suanfa1(int n) int i,j,x=1；for(i=0； in； i+)for(j=0；jn； 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 )
2、次关键字。A.45B.90C.10D.1104下列算法suanfa2(n)的时间复杂度为(A )。int suanfa1(int n) int i,x=0；for (i=0； i5； i+)for (j=1； j0)个结点的完全二叉树的深度为log2(n+1)|或Llog2n+1或Llog2nJ+15. 线性表中兀素的数目称为线性表的长度。6. 限定在表头作删除,在表尾作插入的线性表称为队列。7. 设n个元素的线性表顺序存储，若在它的第i个(1WiWn)元素之后插入一个新元素,共需移动 n-i _个兀素。8. 构造 Hash 函数的方法有直接定址法、随机数法、_数字分析法、除留余数法 、平方取
3、中法、折叠法_等。9对n个记录的表进行简单选择排序，共计需要进行n(n-1)/2 _次比较关键字， 在最坏情况下,共计交换_ n-1_对记录。10字符串A中连续字符组成子序列称为串A的子串,_仅由空格字符组成的字符串称为空 格串。11. 深度为k(k0)的满二叉树共有2-1个非叶子。12. 在有向图G中,以顶点i为弧尾的弧的数目称为i的出度。四、画图题1. 试画出下列稀疏矩阵以行序为主序的三元组表。00180300000024000000660稀疏矩阵参考答案：1.行序为主序的三元组表131821334245366行号列1234号值2. 下列树的双亲表示法:参考答案：2下列树的双亲表示法:序号
4、 data paren tA0B1C1D3E3F3G43. 试画出下列有向图G的逆邻接表。有向图 G参考答案：3.有向图的逆邻接表:4.二叉树 T 的顺序存储结构:ABECGDFtl. . 131 2 3 4 5 6 7 8 9 10 11 12 13T的顺序结构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, 试生成一棵
5、二叉排序树,(1)画出 生成之后的二叉排序树；(2)对该二叉排序树作中序、逆中序遍历，写出遍历序 列,(3)假定每个元素的查找概率相等, 试计算查找成功时平均查找长度 。参考答案： 1.依次输入元素10,6,8,3,7,42,25,30,27,60, 试生成一棵二叉排序树, (1)生成的二叉排序树是: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）假设每个元素的查找概率相等，计算该树的平
6、均查找长度ASL。参考答案： 2.解:（1）构造二叉排序树:3030303011113d3030555II57019194)as4) (18(2)平均査找长度：ASL=(l+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语
7、言 类型定义分别写出结点类型和指针类型的定义。参考答案：1.设单链表的结点为(data,next),其中data为整型，next为指针型，试用C语言 类型定义分别写出结点类型和指针类型的定义。typedef struct node int data;struct node *mext;node,*linklist;七、简答题1.二叉树有哪几种基本形态? 试举例说明。参考答案：1 .答:二叉树有5种基本形态,举例如下Bl B2 B3 B4B5其中：B1：为空二叉树；B2 :有根结点，左右子树均为空二叉树；B3 :有根结点，左子树为非空二叉树,右子树为空二叉树；B4: 有根结点， 左子树为空二叉树
8、， 右子树为非空二叉树；B5:有根结点,左右子树均为非空二叉树。2. 线性表的顺序存储结构和链式存储结构各有哪些优点和缺点?参考答案：2.答: 对于顺序存储结构:(1) 优点:是一种随机存取结构,存取任何元素的时间是一个常数,速度快；结构简单, 逻辑上相邻的元素在物理上也是相邻的；不使用指针, 节省存储空间。(2) 缺点:插入和删除元素,平均需要移动约半个表的元素,消耗大量时间；需要提供一 个连续的存储空间；插入元素可能发生“溢出”；表尾之后的自由存储空间不能被其它表 的数据占用(共享)。对于链式存储结构:(1) 优点:插入和删除元素,不必移动元素,只需修改相关结点的指针；不需要一个连续 的存
9、储空间。(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(
10、%d,&e)；f-data=e； q=head； p=；while (p & ep-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 & ep-data)p=q-next: *) q=p； p=p-next ； (* 或 q=q-next f-next=p； q-next=fwhile(e) ；return head；
