结点《数据结构》期末考试试题及答案

数据结构试题  时间:2021-02-09  阅读:()

(2003-2004学年第2学期)

一、 单项选择题

1对于一个算法 当输入非法数据时也要能作出相应的处理这种要求称为 。

(A)、正确性 (B).可行性 (C).健壮性 (D). 输入性

2设S为C语言的语句,计算机执行下面算法时算法的时间复杂度为 。for(i=n-1 i>=0 i--)for(j=0 j<i j++) S

(A)、 n2 (B).O(nlgn) (C).O(n) (D). O(n2)

3折半查找法适用于 。

A、有序顺序表 B、有序单链表

C、有序顺序表和有序单链表都可以 D、无限制

4顺序存储结构的优势是 。

A、利于插入操作 B、利于删除操作

C、利于顺序访问 D、利于随机访问

5深度为k的完全二叉树其叶子结点必在第 层上。

A、 k-1 B、 k C、 k-1和k D、 1至k

6具有60个结点的二叉树其叶子结点有12个则度过1的结点数为 

A、 11 B、 13 C、 48 D、 37

7 图的Depth-First Search(DFS)遍历思想实际上是二叉树 遍历方法的推广。

A、先序 B、 中序 C、后序 D、层序

8在下列链队列Q中元素a出队的操作序列为 

A、 p=Q.front->ne xt;p->ne xt=Q.front->ne xt;

B、 p=Q.front->ne xt;Q.front->ne xt=p->ne xt;

C、 p=Q.re ar->next;p->next=Q.re ar->next;

D、 p=Q->n e xt;Q->ne xt=p->ne xt;

9 Huffman树的带权路径长度WPL等于 

A、除根结点之外的所有结点权值之和 B、所有结点权值之和C、各叶子结点的带权路径长度之和 D、根结点的值

10线索二叉链表是利用 域存储后继结点的地址。

A、 lchild B、 data C、 rchild D、 root

二、填空题

1 逻辑结构决定了算法的  而存储结构决定了算法的 。

2 栈和队列都是一种 的线性表栈的插入和删除只能在 进行。

3 线性表a1,a2,…,an的顺序存储结构中设每个单元的长度为L元素ai

4 已知一双向链表如下(指针域名为next和prior) 

现将 p 所指的结点插入到 x和 y 结点之间 其操作步骤为 

  

5 n个结点无向完全图的的边数为 n个结点的生成树的边数为 。

6 已知一有向无环图如下

A

任意写出二种拓扑排序序列 、 。

7已知二叉树的中序遍历序列为BCA后序遍历序列为CBA则该二叉树的先序遍历序列为 层序遍历序列为 。

三、应用题

1 设散列函数H(k)=k% 13,设关键字系列为{22, 12,24,6,45,7,8, 13,21} ,要求用线性探测法处理冲突。 (6分)

(1)构造HASH表。

(2)分别求查找成功和不成功时的平均查找长度。

2 给定表19, 14,22, 15,20,21,56, 10 . 8分

1 按元素在表中的次序建立一棵二叉排序树

2 对(1)中所建立的二叉排序树进行中序遍历写出遍历序列。

3 画出对(2)中的遍历序列进行折半查找过程的判定树。

3 已知二个稀疏矩阵A和B的压缩存储三元组表如下

A B

写出A-B压缩存储的三元组表。 5分

4 已知一维数组中的数据为18, 12,25,53, 18 ,试写出插入排序升序过程。并指出具有n个元素的插入排序的时间复杂度是多少 (5分)

5 已知一网络的邻接矩阵如下求从顶点A开始的最小生成树。 (8分要有过程)

A B C D E F

1求从顶点A开始的最小生成树。

2分别画出以A为起点的DFS生成树和BFS生成树。

6 已知数据六个字母及在通信中出现频率如下表

把这些字母和频率作为叶子结点及权值完成如下工作(7分要有过程) 。

1 画出对应的Huffman树。

2 计算带权路径长度WPL。

3 求A、 B、 C、 D、 E、 F的Huffman编码。

7 已知有如下的有向网

求顶点A到其它各顶点的最短路径采2用Dijkstra算法要有过程。 6分

三、 设计题30分每题10分,用C语言写出算法做在答题纸

上

1 已知线性表a1,a2,…,an以顺序存储结构为存储结构其类型定义如下

#define LIST_INIT_SIZE 100 //顺序表初始分配容量

设计一个算法删除其元素值为x的结点假若x是唯一的。并求出其算法的平均时间复杂度。其算法函数头部如下

Status ListDelete(Sqlist&L,Elemtype x)

{

……

}

设计算法将栈顶元素出栈并存入e中 base

3设二叉链树的类型定义如下typedef int Elemtype;typedef struct node{

Elemtype data;struct node *lchild,*rchild;

}BinNode, *BinTre e;

试写出求该二叉树叶子结点数的算法:

Status CountLeaves(BinTree&root,int&n)

{//n is the number of leaves

……

}

答案

选择题每题1分

1、 C2、 D3、A4、 D5、 C6、 D7、A8、 B9、 C10、 C

一、填空题

1设计、实现

2特殊、栈顶

3 LO Ca 1 +(i-1)*L

4 p->next=q->next;q->next->prior=p; q->next=p;p->pr i or=q;

5 n(n-1)/2、 n-1

6 AD CBFEG、 ABCD EFFG

7 AB C、 AB C

二、应用题

1  1Hash表4分

2查找成功的平均查找长度 1分

5*1+1*2+2*3+1*7 /9=20/9

查找不成功的平均查找长度 1分

2+1+9+8+7+6+5+4+3+2+1 /13=

2 1、构造3分

(2)、 10 1415 1920212256 2分

3、 3分

3、 (5分每行0.5)

4、 初始关键字 [18] 12 25 53 18

第 一 趟 [12 18] 25 53 18

第 二 趟 [12 18 25] 53 18

第 三 趟 [12 18 25 53] 18

第 四 趟 [12 18 18 25 53] 4分

On2 1分。

5、 7分

1 4分

2 4分

6、 (1)3分

A B C D

2WP L=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21= (1分)3A 010 B 011 C 110 D 111 E 00 F 10 3分

12、A-B A、 B 1分

A-C A、 D、 C 2分

A-D A、 D 1分

A-E A、 D、 E 2分

三设计题20分

1、 (10分)

Status ListDelete(Sqlist&L,ElemType x)

{int i,j;for(i=0;i<L->length;i++)if(L->elem[i]==x)break;if(i=L->length) return ERROR;for(j=i;j<L->lengthi-1;j++)

L->elem[j]=L->e lem[j+1];

;

平均时间复杂度 2分

设元素个数记为n则平均时间复杂度为

E

2 10分void pop(Stac k&S,Elemtype&e)

{if(S.top==S.bas e)return ERROR;

S.top--;e=*s.top;

}

2、 10分voidCountLeaves(BinTree T,int&n)

{if(T)

{if((!(T->lchild)&&!(T->rchild))n++;

CountLeaves (T->lc hild,n);

CountLeaves (T->rc hild,n);

}

}

习题1

一、单项选择题

1 .数据结构是指  。

A.数据元素的组织形式 B.数据类型

C.数据存储结构 D.数据定义

2.数据在计算机存储器内表示时物理地址与逻辑地址不相同的称之为   。

A.存储结构 B.逻辑结构

C.链式存储结构 D.顺序存储结构

3.树形结构是数据元素之间存在一种  。

A.一对一关系 B.多对多关系

C.多对一关系 D.一对多关系

4.设语句x++的时间是单位时间则以下语句的时间复杂度为   。for(i=1 ; i<=n; i++)for(j=i ; j<=n; j++)x++;

A.O(1) B.O( ) C.O(n) D.O( )

5.算法分析的目的是1 算法分析的两个主要方面是2 。

1  A.找出数据结构的合理性 B.研究算法中的输入和输出关系

C.分析算法的效率以求改进 D.分析算法的易懂性和文档性

2 A.空间复杂度和时间复杂度 B.正确性和简明性

C.可读性和文档性 D.数据复杂性和程序复杂性

6.计算机算法指的是1  它具备输入输出和2等五个特性。

1  A.计算方法 B.排序方法

C.解决问题的有限运算序列 D.调度方法

2 A.可行性可移植性和可扩充性 B.可行性确定性和有穷性

C.确定性有穷性和稳定性 D.易读性稳定性和安全性

7.数据在计算机内有链式和顺序两种存储方式在存储空间使用的灵活性上链式存储比顺序存储要  。

A.低 B.高 C.相同 D.不好说

提速啦(24元/月)河南BGP云服务器活动 买一年送一年4核 4G 5M

提速啦的来历提速啦是 网站 本着“良心 便宜 稳定”的初衷 为小白用户避免被坑 由赣州王成璟网络科技有限公司旗下赣州提速啦网络科技有限公司运营 投资1000万人民币 在美国Cera 香港CTG 香港Cera 国内 杭州 宿迁 浙江 赣州 南昌 大连 辽宁 扬州 等地区建立数据中心 正规持有IDC ISP CDN 云牌照 公司。公司购买产品支持3天内退款 超过3天步退款政策。提速啦的市场定位提速啦主...

TmhHost暑假活动:高端线路VPS季付8折优惠,可选洛杉矶CN2 GIA/日本软银/香港三网CN2 GIA/韩国双向CN2等

tmhhost怎么样?tmhhost正在搞暑假大促销活动,全部是高端线路VPS,现在直接季付8折优惠,活动截止时间是8月31日。可选机房及线路有美国洛杉矶cn2 gia+200G高防、洛杉矶三网CN2 GIA、洛杉矶CERA机房CN2 GIA,日本软银(100M带宽)、香港BGP直连200M带宽、香港三网CN2 GIA、韩国双向CN2。点击进入:tmhhost官方网站地址tmhhost优惠码:Tm...

TTcloud(月$70)E3-1270V3 8GB内存 10Mbps带宽 ,日本独立服务器

关于TTCLOUD服务商在今年初的时候有介绍过一次,而且对于他们家的美国圣何塞服务器有过简单的测评,这个服务商主要是提供独立服务器业务的。目前托管硬件已经达到5000台服务器或节点,主要经营圣何塞,洛杉矶以及日本东京三个地区的数据中心业务。这次看到商家有推出了新上架的日本独立服务器促销活动,价格 $70/月起,季付送10Mbps带宽。也可以跟进客户的需求进行各种DIY定制。内存CPU硬盘流量带宽价...

数据结构试题为你推荐
google地球打不开google earth打不开怎么办?961556225317563152822是哪个银行的如何免费开通黄钻怎样才能免费开通黄钻博客外链博客外链怎么做好bluestacks安卓模拟器BlueStacks如何安装使用?唱吧电脑版官方下载唱吧有没有电脑版的啊?开机滚动条电脑开机启动滚动条时间长怎么办?雅虎天盾雅虎天盾、瑞星杀毒软件、瑞星防火墙、卡卡上网安全助手能同时使用吗?虚拟专用网拨号网络与虚拟专用网的区别网站优化方案几种常用的网站优化方法
域名空间代理 三级域名网站 zpanel kvmla 256m内存 nerd 天猫双十一秒杀 南昌服务器托管 免费全能空间 老左正传 699美元 傲盾官网 中国电信宽带测速器 带宽租赁 免费的域名 建站行业 卡巴下载 linuxvi命令 ssd kosspp 更多