tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 其它课程 >>

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


《数据结构与算法》模拟试卷六 一、名词解释(5*3=15 分) AOV 网 队列 栈 哈夫曼树 生成树

二、 填空题(1*16=16 分) 1. 根据数据元素之间关系的不同特性,通常有下列四类基本结构:_____ 、 _____ 、 _____、_____ 。 2. 数据元素之间的关系在计算机中可用顺序映像和非顺序映像表示, 由此得到两种存 储结构是_____ 、_____。 3. 用具有 n 个元素的一维数组存储一个循环队列,该循环队列的最大长度为 _____。 一棵高度为 5 的二叉树中最少含有 _____个结点,最多含有 _____个结点; 4. 在无向图 G 的邻接矩阵 A 中, 若(vi,vj)属于图 G 的边的集合, 则对应元素 A[i][j] 等于_______,否则等于_________。 5. 二分查找的存储结构仅限于________,且是__________。 6. 在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时,当把 第 7 个记录 60 插入到有序表时,为寻找插入位置需比较________次。 7. 设顺序表中有 n 个关键字,采用顺序的方法查找,其平均查找长度为________。 8. 二叉树第 i(i≥1)层上最多有________个结点。 三、选择题(1*10=10 分) 1. 在一个不带头结点的单链表 HL 中,若要向表头插入一个由指针 p 指向的结点,则 执行_____。 A、L=p; p->next=HL; B、p->next=HL; HL=p; C、p->next=HL; p=HL; D、p->next=HL->next; HL->nxet=p; 2. 在一个长度为 n 的顺序存储的线性表中,删除第 i 个元素 (1≤i≤n+1)时,需要 从前向后依次移动 个元素_____。 A、n-i B、n-i+1 C、n-i-1 D、i 3. 在一个顺序队列中,队首指针指向队首元素的 位置。_____。 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. 左图所示带权无向图的最小生成树的权为



A.14 B.15 C.17 D.18 9. 栈的插入和删除操作在_____进行。 A.栈顶 B.栈底 C.任意位置 D.指定位置 10. 以下说法正确的是 。 A.连通图的生成树是该连通图的一个极小连通子图 B.无向图的邻接矩阵是对称的,有向图的邻接矩阵一定是不对称的 C.任何一个有向图,其全部顶点可以排成一个拓扑序列 D.有回路的图不能进行拓扑排序 四、计算和应用题(共 21 分) 1. 假设用于通信的电文仅由 8 个字母组成, 字母在电文中出现的频率分别为 0.08, 0.18, 0.02, 0.06, 0.35, 0.10, 0.16, 0.05。试为这 8 个字母设计哈夫曼编码。并计算 其平均编码长度(即 WPL)。 2.使用普里姆算法构造如下图所示的图 G 的一棵最小生成树。(画出构造过程)

V1 6 V2 3 V5 1 5 6 6 V3 4 V6 5 5 V4 2

3.待排序关键字(34,12,28,45,66,7,3,21),写出希尔排序的每趟结果。 五、算法填空(9*2=18 分) 1.如果希望循环队列中的向量单元都能得到利用,则可设置一个标志域 tag,每当尾指 针和头指针值相同时,以 tag 的值为 0 或 1 来区分队列状态是“空”还是“满”。请 对下列函数填空,使其分别实现与此结构相应的入队列和出队列的算法。 int EnQueue(CirQueue *Q,DataType x){ if( (1) ) return 0; Q->data[Q->rear]=x; Q->rear=(Q->rear+1)% MAXQSIZE

(2) return 1; } int DeQueue(CirQueue *Q,DataType *x){ if( (3) ) return 0; *x=Q->data[Q->front]; Q->front= (4) ; (5) ; return 1; } (1) (2) (3) (4) (5) 2.下列算法利用二分查找方法在有序表 r 中插入元素 x,并保持表 r 的有序性,其中参 数*n 为表 r 的长度。请在空缺处填入合适的内容,使其成为一个完整的算法。 void BinInsert(SeqList r,int *n,DataType x) { int low=1,high=*n,mid,i; while(low<=high) { mid= (1) ; if (x.key<r[mid].key)high=mid-1; else (2) ; } for(i=*n; (3) ;i--) r[i+1]=r[i]; (4) ; *n++; } (1) (2) (3) (4) 六、算法设计题(2*10=20 分) 1. 编写递归算法,将二叉树中所有结点的左右子树相互交换。 2. 给出图的邻接表存储结构,编写一深度优先遍历算法实现对存放在邻接表中图遍 历。



推荐相关:

数据结构与算法分析_六套期末复习题(含答案)

数据结构与算法分析_六套期末复习题(含答案)_工学_高等教育_教育专区。数据结构与算法分析_期末复习题(含答案) 四川大学试题一一、单项选择题(每小题 2 分,共...


《数据结构与算法》期末考试试题及答案

《数据结构与算法》期末考试试题及答案_电大_成人教育_教育专区。一、 选择题 ...数据序列(8,9,10,4,5, 6,20,1,2)只能是下列排序算 法中(C)的两趟排序...


北大数据结构与算法期末考试模拟试卷

2014年春季北大《数据结构与算法B》期末考试模拟试卷答案 2014 年春季北大《数据...【2 分】 6. 一棵有 n 个结点的满二叉树有_0_个度为 1 的结点、 有_...


哈尔滨工业大学数据结构与算法历年考题汇总_图文

8 D. 9 6. 对线性表进行二分查找时,要求线性表必须 ___。 A、以顺序方式...径 哈工大《数据结构与算法》模拟题一、填空题:(共 15 分)(每空一分) 1....


浙大远程数据结构与算法模拟卷

《数据结构与算法》模拟卷答案一、判断题(共 10 小题,每小题 1 分,共 10...(5 分) 答:直接插入排序 ( 5) ,8,3,12,16,9,17,8,6 ( 5, 8) ,...


【模拟试题】数据结构与算法分析

通信工程学院学生会学习实践部 数据结构与算法分析模拟试题第 1-3 章习题 一、...那么元素 a[6,6]的存储地址为。 7.在计算递归函数时,如果不用递归过程,则...


《数据结构与算法》期末试题试卷A

p→next=NULL 《数据结构与算法》试题卷第1页(共 6 页) 《数据结构与算法》试题卷第2页(共 6 页) XXXXXXX 学校试题卷 (17)在一棵二叉树上,第 5 层的...


数据结构与算法试卷

数据结构与算法分析 复习... 6页 免费 数据结构与算法分析模拟... 44页 免费...09春《数据结构与算法分... 6页 免费 《数据结构与算法》试卷... 暂无评...


《数据结构与算法》期末练习题

《数据结构与算法》期末练习题 - 《数据结构与算法》期末练习 一 选择题 1.以下与数据的存储结构无关的术语是( D )。 A.循环队列 B. 链表 C. 哈希表 2....


数据结构与算法期末考试复习试题

数据结构与算法期末考试复习试题_教育学_高等教育_教育专区。《数据结构与算法》...6.以下说法正确的是 D 。 A.数据项是数据的基本单位 B.数据元素是数据的最...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com