您好,欢迎来到吉趣旅游网。
搜索
您的当前位置:首页《数据结构与算法》模拟试卷一

《数据结构与算法》模拟试卷一

来源:吉趣旅游网
《数据结构与算法》模拟试卷一

一、填空题(每空2分,共20分)

1. 在一个长度为n的循环链表中,删除其元素值为x的结点的时间复杂度为______。 2. 如果入栈序列是1,3,5,…,97,99,且出栈序列的第一个元素为99,则出栈序列中第30个元素为______。

3. 根据数据元素之间关系的不同特性,通常有下列四类基本结构:集合、 _____、 树状结构、______。

4. 线性表的链式存储方式中,每个结点包括两个域,分别是:_____ 和 _____ 。 5. 一棵高度为5的二叉树中最少含有_____个结点,最多含有_____个结点;

6. 在对一组记录(,38,96,72,60,15,60,45,83)进行直接插入排序时,当把第5个记录60插入到有序表时,为寻找插入位置需比较________次。

7. 有向图G用邻接表矩阵存储,其第i行的所有元素之和等于顶点i的________。

二、选择题(从下列各题四个备选答案中选出一个正确答案,并将其代号写在答题纸相应位置处。每小题2分,共10分。)

1. 对线性表进行折半查找最方便的存储结构是_____。

A. 顺序表 B.有序的顺序表 C.链表 D.有序的链表 2. 计算递归函数如不用递归过程通常借助的数据结构是_____。 A.线性表 B.双向队列 C.树 D.栈

3. 如果T2是由有序树T转换来的二叉树,则T中结点的后序排列是T2结点的_____。 A.先序排列 B.中序排列 C.后序排列 D.层序排列 4. n个结点的线索二叉树中线索的数目为_____。

A.(n-1)个 B.n个 C.(n+1)个 D.(n+2)个

5. 设数组A[m]为循环队列Q的存储空间,front为队头指针,rear为队尾指针,则判定Q为空队列的条件是_____。

A.(rear-front)%m= =1 B.front= =rear C.(rear-front)%m= =m-1 D.front= =(rear+1)%m

6. 假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中,其中根结点存放在BT[0],若BT[i]中的结点有左孩子,则左孩子存放在_____。

A.BT[i/2] B.BT[2*i-1] C.BT[2*i] D.BT[2*i+1] 7. 连通图是指图中任意两个顶点之间_____。

A.都连通的无向图 B.都不连通的无向图 C.都连通的有向图 D.都不连通的有向图

8. 在一个长度为n的顺序线性表中顺序查找值为x的元素时,查找成功时的平均查找长度(即x与元素的平均比较次数,假定查找每个元素的概率都相等)为_____。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2

9. 若一个栈的输入序列是1,2,3,4,…,n,输出序列的第一个元素是n,则第i个输出元素是_____。

【第 1 页 共 3 页】

A. 不确定 B. n-i C. n-i+1 D. n-i-1

10. 在单链表中插入一个结点,要修改____个结点的指针域。 A. 1 B. 2 C. 3 D. 4

三、简答题(要求写出主要操作步骤及结果。每小题5分,共35分)

1. 若进栈元素依次为A、B、C、D,写出至少5种可能的出栈顺序。

2. 已知一棵二叉树先序遍历顺序为 ABDEGHJCFI,中序为 DBGEHJACIF,试构造该二叉树。

3. 假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为0.08, 0.18, 0.02, 0.06, 0.35, 0.10, 0.16, 0.05。试为这8个字母设计哈夫曼编码。并计算其平均编码长度(即WPL)。

4.将下面森林转换为相应的二叉树。

A B C J H D E F M N K L G I

5. 给出下图所示的无向图G的邻接矩阵和邻接表两种存储结构。

V1V3V4V2V5 6. 使用普里姆算法构造如下图所示的图G的一棵最小生成树。(画出构造过程)

V16V23V51566V34V6 【第 2 页 共 3 页】

55V427. 对数据元素序列15,13,12,8,22,37,4,33,8,6进行降序排序,用筛选法构造堆排序的初始小顶堆,画出堆形。

四、证明题(要求写出证明过程。共8分)

一棵二叉树T,如果其终端结点数为n0,度为2的结点为n2,则n0=n2+1,试证明之。 五、算法设计题(共17分,第1题8分,第2题9分) 1.写出折半查找算法。

2.给出二叉树的二叉链表存储结构,并写一算法求二叉树的深度。

【第 3 页 共 3 页】

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- jqkq.cn 版权所有 赣ICP备2024042794号-4

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务