当前位置:首页 >> IT认证 >>

数据结构试卷及答案2套

数据结构试卷 1
一、单项选择题:(每小题 2 分,共 20 分) 1. 在一个长度为 n 的顺序表中顺序搜索一个值为 x 的元素时,在等概率的情况下,搜索成 功时的数据平均比较次数为________。 A. n B. n/2 C.(n+1)/2 D.(n-1)/2 B. first == NULL; D. first != NULL; D. 指定位置 2. 不带头结点的单链表 first 为空的判定条件是_________。 A. first->next == NULL; C. first->next == first; A. 栈顶 __________。 A. front==rear C. rear!=NULL 的执行结果为________。 A.y B.(a, b) A. n A. n B. n-1 B. n+1 C.(x,(a,b)) C. n+1 C. 2*n D.x D. 2*n D. 2*n-1 D. n(n-1) 6. 在一棵具有 n 个结点的二叉树中,所有结点的空子树个数等于_________。 7. 利用 n 个值作为叶结点的权重,生成的霍夫曼树中共包含有_________个结点。 8. 设无向图的顶点个数为 n,则该图最多有________条边。 A. n-1 B. n(n-1)/2C. n(n+1)/2 A.只有一棵 C. 一定有多棵 B. 9. 任何一个无向连通图的最小生成树_________。 一棵或多棵 D. 可能不存在 B. front!=NULL D. front==NULL B. 栈底

3. 栈的插入和删除操作在__________进行。 C. 任意位置 4. 假定一个链式队列的队头和队尾指针分别为 front 和 rear ,则判断队空的条件为

5. 设有一个广义表 A ( (x, (a, b) ), (x, (a, b), y) ),运算 Head (Head (Tail (A) ) )

10. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较, 然后将其放在 已排序序列的合适位置,该排序方法称为_______排序法。 A.选择 B.二路归并 C.交换 D. 插入 二、填空题(每空 1 分,共 20 分) 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的____________以及它们之间 的___________和运算等的学科。 2. 顺序表中逻辑上相邻的元素的物理位置________相邻。单链表中逻辑上相邻的元素的物 理位置__________相邻。 3. 在单链表中,除了首元结点外,任一结点的存储位置由 ___________________ 指示。 4. ________ 是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性

表。 5. 设有二维数组 A[0..19,0..10], 其每个元素占两个字节, 第一个元素的存储地址为 1000, 若按行优先顺序存储, 则元素 A[4,6]的存储地址为________ , 按列优顺序存储, 元素 A[4,6] 的存储地址为__________ 。 6. 按照二叉树的定义,有 3 个结点的二叉树有________种形态。 7. 具有 n(n>0)个结点的完全二叉树的深度为__________。 8. 含有 n 个顶点 e 条边的无向连通图, 利用 Kruskal 算法生成最小代价生成树其时间复杂度 为__________,利用 Prim 算法生成最小代价生成树时间复杂度为__________。 9. 从有序表(12,18,30,43,56,78,82,95)中折半查找元素 56 时,其查找长度为________。 10. 快速排序在平均情况下的时间复杂度为 ___________ ,在最坏情况下的时间复杂度为 ____________。 三、应用题(每小题 5 分,共 30 分) 1. 输入下列整数序列,17,31,13,11,20,35,25,8,4,11,24,40,27,画出建立 的二叉排序树,最后分别图示将 9 插入,86 删除后的二叉排序树。 2. 已知二叉树 T 的中序遍历序列为 DIGJLKBAECHF, 后序遍历序列为 ILKJGDBEHFCA, 请画出 该二叉树,并写出先序序列。 3. 对于如图 1 所示的有向图,试给出 (1)每个顶点的入度和出度; (2)邻接矩阵; (3)邻接表; 6 3 2 4 1 5

4. 试对图 2 所示的 AOE 网络,解答下列问 题。 (1) 求每个事件的最早开始时间 Ve(i)和 最迟开始时间 Vl(i)。 (2) 求每个活动的最早开始时间 e( )和 最迟开始时间 l( )。 (3) 确定哪些活动是关键活动。画出由 所有关键活动构成的图,指出哪些活动 加速可使整个工程提前完成。 5. 字符 a,b,c,d,e,f,g 的使用频度分

图1

3

图2

别是 0.07,0.09,0.12,0.22,0.20,0.27,0.03,写出 a,b,c,d,e,f,g 的 Huffman 编码(在构造 哈夫曼树时,要求左子树根结点的权值小于等于右子树根结点的权值)。 6. 设哈希函数 H(K)=k%13,给定键值序列为 87,25,31,8,27,13,68,95,18,12,70,63, 47,处 理冲突的方法为线性探测再散列, 试在 0~18 的散列地址空间中对该关键字序列构造哈希表, 并计算该表的成功查找的平均查找长度。

四、算法设计题(每小题 10 分,共 30 分) 1.已知单链表 L 中的元素有序,写一算法,删除其重复结点,即实现如图 3 的操作。(a)为 删除前,(b)为删除后。 H H 10 10 10 15 15 18 ∧ ∧ 15 25 18 ∧ ∧ (a) (b)

图3

删除重复结点

2. 编写递归算法,求二叉树中以元素值为 x 的结点为根的子树的深度。 3. 编写一个双向起泡的排序算法,即相邻两遍向相反方向起泡。

数据结构试卷 2
一、单项选择题(从下列各题四个备选答案中选出一个正确答案,每小题 2 分,共 20 分) 1.算法分析的两个主要方面是( ) A.空间复杂性和时间复杂性 C.可读性和文档性 2.在以下的叙述种正确的是 ( ) B.正确性和简明性 D.数据复杂性和程序复杂性

A.线性表的顺序存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表 C.栈的操作方式是先进先出 D.队列的操作方式是后进先出 3. 循环队列用数组 A[0,m-1]存放其元素值, 已知其头尾指针分别是 front 和 rear,则当前 队列中的元素个数是( ) B. rear-front+1 D. rear-front )

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

4. 带头结点的单链表 head 为空的判定条件是 ( A. head==NULL C. head->next==head

B.head->next==NULL D.head!=NULL ) 。

5.在双循环链表的 p 指针所指结点之后插入 s 指针所指结点的操作是( A.p->next=s; s->priou=p; p->next->priou=s; s->next=p->next B.p->next=s; p->next->priou=s; s->priou=p; s->next=p->next C.s->priou=p;s->next=p->next;p->next=s; p->next->priou=s; D.s->priou=p;s->next=p->next;p->next->priou=s; p->next=s; 6.稀疏矩阵一般的压缩存储方法有两种,即 ( A. 二维数组和三维数组表 C. 三元组表和十字链表 )

B. 三元组和散列 D.散列和十字链表 ) ;

7.广义表 A=(a,b,(c,d),(e,(f,g))),则下面式子的值为( Head(Tail(Head(Tail(Tail(A))))) A. (g) B.(d) C.c D.d

8.有分别带权为 9, 2, 5, 7 的四个叶子结点构造一棵哈夫曼树, 该树的带权路径长度为 ( A. 23 B.37 C.44 ) 。 C.强连通图 D.有向无环图 D.46



9.有拓扑序列的图一定是( A.有环图 B.无向图

10.利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序 树以后,查找元素 35 要进行( A.4 次 B.5 次 )元素间的比较。 C. 7 次 D.10 次

二、填空(每空 1 分,共 20 分) 1.长度为 n 的顺序表,插入和删除元素的时间复杂性为__________;顺序存储的栈和队列, 插入和删除元素的时间复杂性为__________。 2.非空单循环链表 L 中,指针 p 所指结点是尾结点的条件是__________________。 3.在一个单链表中 p 所指结点之后插入一个由指针 s 所指结点,应执行 s->next=________; 和 p->next=_____________的操作。 4.有 n 个结点的树,则该树中所有结点的度之和为____________。 5.设有二维数组 A[0..9,0..19],其每个元素占两个字节,第一个元素的存储地址为 100, 若按行优先顺序存储, 则元素 A[4,6]的存储地址为________ , 按列优顺序存储, 元素 A[4,6] 的存储地址为__________ 。 6.试找出满足下面条件的所有二叉树:前序序列和中序序列相同____________________;中 序序列和后序序列相同_________________。 7 .二叉树以二叉链表为存储结构,在有 n(n>0) 个结点的二叉树中,空链域的个数为 _____________。 8.假定一棵二叉树的结点数为 18,则它的最小高度为_______,最大高度为__________。 9.一个连通图的生成树是一个_______连通子图,n 个顶点的生成树有_______条边。 10.具有 n 个顶点的无向完全图,边的总数为_______条;而在 n 个顶点的有向完全图中, 边的总数为_______条。 11. 设 s=’IAMASTUDENT’,t=’GOOD’,q=’WORKER’; 函 数 SubString(s,5,7) 的 值 为

____________; 函 数 Index(s,t) 的 值 为 ________; 函 数 Replace(s,’STUDENT’,q) 的 值 为 ______________。 三、回答下列问题(1—4 题每题 5 分,5 题 10 分,共 30 分) 1. 已知一棵二叉树的前序遍历的结果是 ABECDFGHIJ, 中序遍历的结果是 EBCDAFHIGJ, 试画 出这棵二叉树。 2. 假设字符 a,b,c,d,e,f 的使用频度分别是 0.07,0.09,0.12,0.22,0.23,0.27, 构造哈夫曼 树,并求 a,b,c,d,e,f 的 Huffman(哈夫曼)编码。 3.对如图 1,用 prim 算法构造一棵最小生成树,写出构造过程。 4.设哈希函数为 H(k)=k MOD 13 ,用线性探测法解决冲突,请画出 在 0—12 的 哈 希 空 间 中 , 对 于 关 键 字 序 列 20 1 9 11 2 5 1 6 10 1 6 1 10 14 5 4 6 18 图1

3

32,17,10,73,45,89,92,36,80,27,19,58 构造哈希表,并计算在等

概率情况下的平均查找长度。 5.试对右图所示的 AOE 网络,解答下列问题。 (1) 这个工程最早可能在什么时间结束。 (2) 求每个事件的最早开始时间 Ve(i)和最迟开 始时间 Vl(i)。 (3) 求每个活动的最早开始时间 e( )和最迟开始时 间 l( )。 (4) 确定哪些活动是关键活动。画出由所有关键活 动构成的图,指出哪些活动加速可使整个工程提前完成。 四、算法设计题(共 30 分) 1.设有一个由正整数组成的无序(向后)单链表,编写算法完成如下功能: 找出最小值结 点,且打印该数值。 2.设二叉树采用二叉链表表示,各结点结构为: Lchild Data Rchild

编写递归算法,求二叉树中元素值为 x 的结点在先序序列中的位置(假定二叉树中有惟一的 值为 x 的元素) 。 3 将二分查找算法改写为递归算法。

数据结构试卷 3

数据结构试卷 4


相关文章:
数据结构试卷及答案2套.doc
数据结构试卷及答案2套 - 数据结构试卷 1 一、单项选择题:(每小题 2 分,
数据结构试题及答案(10套最新).doc
数据结构试题及答案(10套最新) - 一、 单选题(每题 2 分,共 20 分)
《数据结构》试卷第2套.doc
数据结构试卷2套 - 《数据结构》习题 临时磨枪的不错选择... 《数据结构试卷2套_工学_高等教育_教育专区。《数据结构》习题 临时磨枪的不错选择 ...
十套数据结构试题及答案.doc
十套数据结构试题及答案 - 数据结构试卷(一) 一、单选题(每题 2 分,共 2
2018数据结构试题及答案14套.doc
2018数据结构试题及答案14套 - 2018 数据结构试题及答案 14 套 2018 数据结构试题及答案 01 ...
十套经典数据结构试题并带答案.doc
十套经典数据结构试题并带答案 - 学习必备 欢迎下载 数据结构试卷(一) 一、单
中南大学十套数据结构试题及答案2.doc
中南大学十套数据结构试题及答案2_计算机软件及应用_IT/计算机_专业资料。数据
最新 十套数据结构试题及答案.doc
最新 十套数据结构试题及答案 - 数据结构试卷(一) ... 1 数据结构试卷(
十套数据结构试题及答案1.doc
十套数据结构试题及答案1 - 数据结构试卷(一)... 1 数据结构试卷(一)参
2套数据结构模拟题.txt
以上答案都不对 2.数据结构中,与所使用的计算机无关的是数据的() A.存储结构 B.物理结构 C.逻辑结构 D.物理结构和存储结构 E.以上答案都不对 3.在具有n...
数据结构试题及答案三套.doc
数据结构试题及答案三套 - 1 1. 数据结构试卷(一) 2. 单选题(每题 2
《数据结构》期末考试题及答案.pdf
数据结构》期末考试题及答案 - 2011-2012 学年第一学期期末考查 《数据结构》试卷 (答案一律写在答题纸上,在本试卷上做答无效) 一、选择(每题 1 分,共 ...
十套数据结构试题及答案[3].doc
十套数据结构试题及答案[3] - 数据结构试卷(三) 一、选择题(每题 1 分,
(年)专升本十套数据结构(试题及标准答案).doc
(年)专升本十套数据结构(试题及标准答案) - 数据结构试卷(一) 一、单选题(
十套数据结构试题及答案[6].doc
十套数据结构试题及答案[6] - 数据结构试卷(六) 一、选择题(30 分) 1
十套数据结构试题及答案.doc
十套数据结构试题及答案 - 数据结构试卷(一) 二、填空题(每空 1 分,共 2
十套数据结构试题及答案[7].pdf
十套数据结构试题及答案[7] - 数据结构试卷(七) 一、选择题(30分) 1.
十套数据结构试题及答案.doc
十套数据结构试题及答案 - 数据结构试卷(一) 1 数据结构试卷(一)参考答案
十套数据结构试题及答案.doc
十套数据结构试题及答案 - 数据结构试卷(一) 二、填空题(每空 1 分,共 2
数据结构课程三套作业及答案.doc
数据结构课程三套作业及答案 - 数据结构课程作业_A 一、单选题。 1.(7 分