没有合适的资源?快使用搜索试试~ 我知道了~
《数据结构》复习题.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 135 浏览量
2021-10-11
14:23:23
上传
评论
收藏 45KB DOC 举报
温馨提示
试读
13页
《数据结构》复习题.doc
资源推荐
资源详情
资源评论
一、填空题
1、数据结构就是一门研究数据的逻辑结构和物理结构,以与它们之间的关系和所定义的
算法如何运行的学科。
2、四种根本逻辑结构分别是集合、线性结构、树形结构和图状结构。
3、算法的质量可从以下几个方面来评价:正确性、易读性、健壮性和高效率。
4、线性表的最根本操作有插入、删除和定位〔查找〕三种。
5、设每个数据元素占用 K 个存储单元,假设 a[1]的地址为 Loc(a1),那么 a[i]的地址为
Loc(a1)+(i-1)*k。
6、栈是一种操作在栈顶一端进展的线性表。
7、栈的结构特征是后进先出。
8、在队列中,允许进队的一端称为队尾,允许出队的一端称为队首。
9、队列的结构特征是先进先出。
10、假设串的长度为 0 时,该串称之为空串。
11、树中度数为 0 的结点称为叶结点。
12、一个顺序存储的线性表,设每个结点需占 m 个存储单元,假设第 1 个元素的地址为
address,那么第 i 个结点的地址是 address+(i-1)*m。
13、线性表有两种存储结构:顺序存储结构和链式存储结构,就两种存储结构完成以下填
空:
顺序存储结构存储密度较大,链式存储结构 存储利用率较高,顺序存储结构可以随机存取,
链式存储结构不可以随机存取,链式存储结构插入和删除操作比拟方便。
14、顺序表中逻辑上相邻的元素在物理位置上也相邻,在链表中逻辑上相邻的元素的物理
位置不一定相邻。
15 、 在 顺 序 表 la 的 第 i 个 元 素 前 插 入 一 个 新 元 素 , 那 么 有 效 的 i 值 围 是 1
<=i<=length;在顺序表 lb 的第 j 个元素之后插入一个新元素,那么 j 的有效围是 1 <=
j<=length;要删除顺序表 lc 的第 k 个元素,那么 k 的有效围是 1 <=k<=length。
16、设有一个空栈,现有输入序列为 1,2,3,4,5,经过操作序列 push , pop ,
push , push , pop, push ,push ,pop 后,现在已出栈的序列是 1,3,5 ,栈顶元素的值
是 4 。
17 、 设 有 栈 S , 假 设 线性表 元 素 入 栈 顺 序 为 1, 2 , 3 , 4 , 得 到 的 出 栈 序 列 为
1,3,4,2,那么用栈的根本运算 Push, Pop 描述的操作序列为 push , pop, push,
push , pop, push , pop, pop。
18、在一个链队列中,假设队首指针为 front,队尾指针为 rear,那么判断该队列只有一
个结点的条件 front!=NULL&&front=rear。
19、设循环队列的头指针 front 指向队头元素,尾指针 rear 指向队尾元素后的一个空闲
元素,队列的最大空间为 MAX ,那么队空的标志为 front=rear,队满的标志为
((rear+1)%MAX=front),当 rear<front 时队列长度是 rear-front+MAX
20、某二叉树的先序遍历次序为 afbcdeg,中序遍历次序为 cedbgfa。
其后序遍历次序为 edcgbfa。层次遍历次序为 afbcgde。
21、设有二维数组 A (5 x 7) ,每一元素用相邻的 4 个字节存储,存储器按字节编址。A00
的存储地址为 100。那么按行存储时,元素 A14 的第一个字节的地址是 144;按列存储
时,元素 A14 的第一个字节的地址是 184。
22、队列的插入操作是在队列的队尾进展,删除操作是在队列的队首进展。
23、当用长度为 N 的数组顺序存储一个栈时,假定用 top==N 表示栈空,那么表示栈满
的条件是 top==0。
1 / 13
24、设 W 为一个二维数组,其每个数据元素占用 4 个字节,行下标 i 从 0 到 7 ,列下标 j
从 0 到 3 ,那么二维数组 W 的数据元素共占用 128 个字节。W 中第 6 行的元素和第 4 列
的元素共占用 44 个字节。假设按行顺序存放二维数组 W,其起始地址为 100,那么二维
数组元素 W[6,3]的起始地址为 208。
25、二叉树是指度为 2 的有序树。一棵结点数为 N 的二叉树,其所有结点的度的总和是
n-1。
26、用具有 n 个元素的一维数组存储一个循环队列,那么其队首指针总是指向队首元素的
前一个位置,该循环队列的最大长度为 n-1。
27、一棵高度为 5 的二叉树中最少含有 5 个结点,最多含有 31 个结点;
28、在串 S=“structure〞中,以 t 为首字符的子串有 12 个。
29、假设一个 9 阶的上三角矩阵 A 按列优先顺序压缩存储在一维数组 B 中,其中 B[0]存
储矩阵中第 1 个元素 a1,1,那么 B[31]中存放的元素是 a4,8。
30、设一棵完全二叉树中有 21 个结点,如果按照从上到下、从左到右的顺序从 1 开始顺
序编号,那么编号为 8 的双亲结点的编号是 4,编号为 8 的左孩子结点的编号是 16。
31、在一个长度为 n 的顺序表中第 i 个元素〔1<=i<=n〕之前插入一个元素时,需向后
移动 n-i+1 个元素。
32、在单链表中设置头结点的作用是简化插入、删除操作。
33、根据线性表的链式存储结构中每一个结点包含的指针个数,将线性链表分成单链表和
多重链表;
34、在双向循环链表中 , 向 p 所 指 的 结 点 之后 插入 指针 f 所指的结点,其操作 是 f-
>rnext=p->rnext、p->rnext->lnext=f、p->rnext=f、f->lnext=p。
35、存储的特点是利用指针来表示数据元素之间的逻辑关系。
36、指针 p 指向单链表 L 中的某结点,那么删除其后继结点的语句是: p->next=p-
>next->next
37、对于栈操作数据的原那么是后进先出。
38、栈是限定仅在表尾进展插入或删除操作的线性表。
39、在作进栈运算时应先判别栈是否栈满;在作退栈运算时应先判别栈是否栈空;
40、循环队列的引入,目的是为了克制假溢出
41、队列的特点是先进先出。
42、数组的存储结构采用顺序存储方式。
43、设有二维数组 A[0..9,0..19],其每个元素占两个字节,第一个元素的存储地址为
100,假设按列优先顺序存储,那么元素 A[6,6]存储地址为 232。
44、二叉树由根结点,左子树,右子树三个根本单元组成。
45 、 在 二 叉 树 中 , 指 针 p 所 指 结 点 为 叶 子 结 点 的 条 件 是 p->lnext=NULL &&p-
>rnext=NULL。
46、深度为 k 的完全二叉树至少有 2
k-1
个结点,至多有 2
k
-1 个结点。
二、算法填空题
1、顺序表的定位算法
struct node
{int data[20];
int length;};
int loc(struct node *l,int item)
{int i,j;
2 / 13
j=l->length;
if(j==0) return 0;
for(i=0;i<j;i++)
if(l->data[i]==item) return i;
printf(“找不到!〞);
return 0;}
2、顺序表的插入算法
struct node
{int data[20];
int length;};
int ins(struct node *l,int i,int x)
{int j;
if(i<1||i>l->length+1) return 0;
for(j=l->length;j>=i;j--)
l->data[j]=l->data[j-1];
l->data[j-1]=x;
l->length++;
return 1;
}
3、顺序表删除算法
struct node
{int data[20];
int length;};
int del(struct node *l,int i;)
{int j;
if(i<1||i>l->length)return 0;
for(j=i-1;j<l->length-2;j++)
l->data[j]=l->data[j+1];
l->length--;
return 1;
}
4、单链表的定位算法
struct node
{int data;
struct node *next;};
int loc(struct node*l,int item)
{int i;
struct node *temp;
temp=l->next;
while(temp!=NULL&&temp->data!=item)
{ i++;
temp=temp->next;}
3 / 13
剩余12页未读,继续阅读
资源评论
beibeidzh
- 粉丝: 8
- 资源: 24万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功