数据结构1-6章习题
更新时间:2023-11-07 01:58:01 阅读量: 教育文库 文档下载
- 数据结构多少章推荐度:
- 相关推荐
《算法与数据结构》第1-6章课堂测验(双号)
一、选择题
1、已知一个栈的进栈序列是1,2,3,?,n,其输出序列是p1,p2,?,pn,若p1=n,则pi的值。( c )
(A) i (B) n-i (C) n-i+1 (D) 不确定
2、设n个元素进栈序列是1,2,3,?,n,其输出序列是p1,p2,?,pn,若p1=3,则p2的值。( c )
(A) 一定是2 (B) 一定是1
(C) 不可能是1 (D) 以上都不对
3、若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是( b )
A.6 B.11 C.15 D.不确定 4、在下述结论中,正确的是( d ) ①只有一个结点的二叉树的度为0; ②二叉树的度为2;
③二叉树的左右子树可任意交换;
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A.①②③ B.②③④ C.②④ D.①④ 5、一棵树高为K的完全二叉树至少有()个结点。( a )
kk-1k-1
A.2 –1 B.2 +1 C.2 D.2k
二、简答题
1 简述下列术语:线性表,顺序表,链表。
2 3 4
线性表:最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。 顺序表:是指用一组连续的存储单元一次存储线性表中的数据元素。物理结构和逻辑结构都相邻。
链表:逻辑结构相邻的数据元素物理结构不一定相邻。采用指针的形式连接起来。
2 何时选用顺序表,何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么?
不需要经常大量的修改表或需要随机存取的情况下可以选用顺序表;
相反需要经常大量的修改表,但不是频繁的随机存取的情况下可选用链式表。
3链表所表示的元素是否有序?如有序,则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解?
答:有序。有序性体现在通过指针数据元素有序的相连。物理上不一定要相邻。 4设A和B是两个按元素值递增有序的单链表,写一算法将A和B归并为按按元素值递减有序的单链表C,试分析算法的时间复杂度。
1
void ListInsert(SqList A,SqList B,SqList C) { ElemType *p,*q,*s; P=&A; q=&B; s=&C; while(p.next!=NULL||q.next!=NULL) { if(p.next.data<=q.next.data) { if(s.next!=NULL) p.next=s.next; s.next=p.next; p++; } else { if(s.next!=NULL) q.next=s.next; s.next=q.next; q++; } } while(p.next!=NULL) { p.next=s.next; s.next=p.next; } while(q.next!=NULL) { q.next=s.next; s.next=q.next; }
4、例:什么是队列的上溢现象和假溢出现象?解决它们有哪些方法?
答:在队列的顺序存储结构中,设头指针为front,队尾指针rear,队的容量(存储空间的大小)为MaxSize。当有元素加入到队列时,若rear=MaxSize(初始时rear=0)则发生队列的上溢现象,该元素不能加入队列。 特别要注意的是队列的假溢出现
2
象:队列中还有剩余空间但元素却不能进入队列,造成这种现象的原因是由于队列的操作方法所致。
解决队列上溢的方法有以下几种:1)建立一个足够大的存储空间,但这样做会造成空间的使用效率降低。(2)当出现假溢出时可采用以下几种方法: ①采用平移元素的方法:每当队列中加入一个元素时,队列中已有的元素向队头移动一个位置(当然要有空闲的空间可供移动);②每当删除一个队头元素时,则依次移动队中的元素,始终使front指针指向队列中的第一个位置; ③采用环形队列方式:把队列看成一个首尾相接的环形队列,在环形队列上进行插入或删除运算时仍然遵循“先进先出”的原则。”
5、例:对于顺序队列来说,如果知道队首元素的位置和队列中元素个数,则队尾元素所在位置显然是可以计算的。也就是说,可以用队列中元素个数代替队尾指针。编写出这种循环顺序队列的初始化、入队、出队和判空算法。 解: 当已知队首元素的位置front和队列中元素个数count后: 队空的条件为:count==0
队满的条件为:count==MaxSize 计算队尾位置rear:
rear=(front+count)%MaxSize 对应的算法如下: typedef struct
{ ElemType data[MaxSize]; int front; /*队首指针*/ int count; /*队列中元素个数*/ } QuType; /*队列类型*/
void InitQu(QuType *&q) /*队列q初始化*/ {
q=(QuType *)malloc(sizeof(QuType)); q->front=0; q->count=0; }
int EnQu(QuType *&q,ElemType x) /*进队*/ { int rear;
if (q->count==MaxSize) return 0; /*队满上溢出*/ else
{ rear=(q->front+q->count+MaxSize)%MaxSize; /*求队尾位置*/
rear=(rear+1)%MaxSize; /*队尾位置进1*/ q->data[rear]=x; q->count++; return 1;
3
} }
int DeQu(QuType *&q,ElemType &x) /*出队*/ {
if (q->count==0) /*队空下溢出*/ return 0; else
{ q->front=(q->front+1)%MaxSize; x=q->data[q->front]; q->count--; return 1; } }
int QuEmpty(QuType *q) /*判空*/ {
return(q->count==0); }
1 设有一个栈,元素进栈的次序为a, b, c。问经过栈操作后可以得到哪些输出序列?
cba; abc; acb;bac; bca;
2循环队列的优点是什么?如何判断它的空和满?
优点:可以克服顺序队列的“假上溢”现象,能够使存储队列的向量空间得到充分利用。 判断循环队列的空或满不能以头尾指针是否相等来确定,一般是通过以下几种方法:一是另设一布尔变量来区别队列的空和满。二是约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满。三是设置一计数器记录队列中元素的总数,不仅可判别空或满,还可以得到队列中元素的个数
2 设有一个静态顺序队列,向量大小为MAX,判断队列为空的条件是什么?队列满的条件是什么?
3 队列为空:front=rear。队满:rear=MAX -1或front=rear 4 (队首指针front ,一个队尾指针rear)
5
5 设有一个静态循环队列,向量大小为MAX,判断队列为空的条件是什么?队
列满的条件是什么?
6 7
4
循环队列为空:front=rear 。 循环队列满:(rear+1)%MAX=front。 (队首指针front ,一个队尾指针rear)
8
5设Q[0,6]是一个静态顺序队列,初始状态为front=rear=0,请画出做完下列操作后队列的头尾指针的状态变化情况,若不能入对,请指出其元素,并说明理由。
a, b, c, d入队 a, b, c出队
i , j , k , l , m入队 d, i出队
n, o, p, q, r入队
其中l,m,n,o,p,q,r均由于队列假溢出问题无法入队
6假设Q[0,5]是一个循环队列,初始状态为front=rear=0,请画出做完下列操作后队列的头尾指针的状态变化情况,若不能入对,请指出其元素,并说明理由。
d, e, b, g, h入队 d, e出队
i , j , k , l , m入队 b出队
n, o, p, q, r入队
5
⑴假设在树中,结点x是结点y的双亲时,用(x,y)来表示树边。已知一棵树的树边集合为{ (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h), (a,c) } ,用树型表示法表示该树,并回答下列问题:
① 哪个是根结点? 哪些是叶子结点? 哪个是g的双亲? 哪些是g的祖先? 哪些是g的孩子? 那些是e的子孙? 哪些是e的兄弟? 哪些是f的兄弟?
② b和n的层次各是多少? 树的深度是多少? 以结点c为根的子树的深度是多少?
根节点:a 叶子节点:i ,d , j, f , l g 的双亲节点:c g 的祖先:c , a g 的孩子:j e 的子孙:i e的兄弟:d f的兄弟:g , h
b的层次:2 树的深度:4 以结点c为根的子树的深度:3
⑵一棵深度为h的满k叉树有如下性质:第h层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号,问: ①各层的结点数是多少?
②编号为i的结点的双亲结点(若存在)的编号是多少?
③编号为i的结点的第j个孩子结点(若存在)的编号是多少?
④编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少?
6
(1) 设层号为i的结点数目为m=k^(i-1) (2) 编号为i的结点的双亲结点的编号是:[(i+k-2)/k](不大于(i+k-2)/k的最大整数。也就是(i+k-2)与k整除的结果.以下/表示整除。
(3) 编号为i的结点的第j个孩子结点编号是:k*(i-1)+1+j;
(4)编号为i的结点有右兄弟的条件是(i-1)能被k整除 右兄弟的编号是i+1.
三、算法理解
1、已知P结点是某双向链表的中间节点,画图并写出下列操作的语句序列。 (1)在P结点后插入S结点。 (2)删除P结点的后继结点Q。 结点结构如下: Prior Data Next (其中Prior、Data、Next分别为前驱节点指针、数据域、后继节点指针。) 答:(1)P->Next->Prior=S; S->Next=P->Next; P->Next=S; S->Prior=P; (2) Q=P->Next; P->Next=P->Next->Next; P->Next->Prior=P; free(Q);
4、假设一棵二叉树的前序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK。请画出该树,并写出后序序列。(要求写出分析过程) 确定二叉树的结构,只需要采用递归的方式确定每棵子树的根结点和左、右子树的先序、中序序列即可。先序序列的第一个结点必然是根结点,左、右子树的中序序列在二叉树的中序序列中,分别在根结点的两边;他们的先序序列在二叉树的先序序列中先后连续排列。
7
EBACDGFHIKJ
7、(8分) 假设用于通讯的电文由A、B、C、D、E、F、G、H这8个字母组成,字母在电文中出现的频率为{ 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.1 },画出这8个字母哈夫曼树并设计哈夫曼编码。
192132623710
然后根据左0右1写出 a=1010 b=00 c=10000 d=1001 e=11 f=10001 g=01
8
⑶设有如图6-27所示的二叉树。
①分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。 ②写出该二叉树的先序、中序、后序遍历序列。
顺序存储结构:
链式存储结构
aabcdefg00hk00mn
bc?d?e?f?g?h??k??m??n? 先序:abdehkcfgmn 中序:dbhekafcmgn 后序:dhkebfmngca
⑷已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF,请画出这棵二叉树,然后给出该树的后序遍历序列。
ABCDEFGHI
后序:GHDBEIFCA
⑸设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG和DECBHGFA ,请画出这棵二叉树,然后给出该树的先序序列。
9
ABFCG
先序遍历:ABCDEFGH
DEH
⑹已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif和gdbkeihfca,请画出这棵二叉树对应的中序线索树和后序线索树。
二叉树:
中序线索树:
10
void MatrixAdd(int n,int A[MAX][MAX],int B[MAX][MAX],int C[MAX][MAX]) { int i,j;
for (i=0;i for (j=0;j C[i][j]=A[i][j]+B[i][j]; } 答:因为 C[i][j]=A[i][j]+B[i][j];这条语句执行的频率为n^2; 所以其时间复杂度为0(n^2)。 四、算法设计题 1、请描述队列和堆栈的特点,并设计一个算法实现:用两个栈(栈A,栈B)实现一个队列,请描述入队与出队的过程。 答:栈的特点是后进先出,队列的特点是先进先出。所以,用两个栈A和B模拟一个队列时,A作输入栈,逐个元素压栈,以此模拟队列元素的入队。当需要出队时,将栈A退栈并逐个压入栈B中,A中最先入栈的元素,在B中处于栈顶。B退栈,相当于队列的出队,实现了先进先出。显然,只有栈B为空且A也为空,才算是队列空。 算法: ElementType DeQueue(A) { if(Empty(A) { printf(\exit(0); } else return Pop(A); } 16 void EnQueue(A,ElementType x) { ElementType t; while(!Empty(A)) { t=Pop(A); Push(B,t); } Push(A,x); while(!Empty(B)) { t=Pop(B); Push(A,t); } 2、已知长度为n的线性表A采用顺序存储结构,设计一个算法删除线性表A中所有值为key的数据元素。 答:在顺序存储的线性表上删除元素通常要涉及到一系列元素的移动(删第i个元素第i+1至第n个元素要依次前移)本题要求删除线性表中所有值为key的数据元素并未要求元素间的相对位置不变,因此可以考虑设头尾两个指针(i=1,j=n)从两端向中间移动,凡遇到值item的数据元素时,直接将右端元素左移至值为 key 的数据元素位置。具体实现如下: void Delete(ElemType A[ ] int n) ∥A是有n个元素的一维数组 本算法删除A中所有值为item的元素 { i=1;j=n;∥设置数组低、高端指针(下标) while(i while(i i++; ∥若值不为key 左移指针 if(i j--;∥若右端元素值为key指针左移 if(i A[i++]=A[j--]; } } 3、假设程序代码中包含三种符号:圆括号( )、方括号[ ]和大括号{ },并且这些符号必须成对使用。请问能否用栈来判断程序中以上符号是否正确配对? 17 若能,请分析判断方法,并写出算法代码。 答:能,判断方法:设置一个括号栈,扫描表达式:遇到左括号( 包括(、[和{ )时进栈,遇到右括号时,若栈是相匹配的左括号,则出栈,否则,返回0。若表达式扫描结束,栈为空,返回1表示括号正确匹配,否则返回0。 算法代码: int correct(char exp[],int n) { char st[MaxSize]; int top=-1,i=0,tag=1; while (i { if (exp[i]=='(' || exp[i]=='[' || exp[i]=='{') /*遇到'('、'['或'{',则将其入栈*/ { top++; st[top]=exp[i]; } if (exp[i]==‘)’)//遇到‘)’,若栈顶是‘(’,则继续处 理,否则以不配对返回 if (st[top]=='(') { top--; } else { tag=0; } if (exp[i]==‘]’)//遇到‘]’,若栈顶是‘[’, 则继续处理,否则以不配对返回 if (st[top]=='[') { top--; } else { tag=0; } if (exp[i]==‘}’)//遇到‘}’,若栈顶是 ‘{’,则继续处理,否则以不配对返回 if (st[top]=='{') 18 { top--; } else { tag=0; } i++; /*表达式扫描完毕*/ if (top>-1) tag=0; /* return(tag); } 19 若栈不空,则不配对*/
正在阅读:
数据结构1-6章习题11-07
小学教育教学改革工作实施方案12-23
造价工程师考试建筑面积计算规则记忆方法06-01
清水池混凝土施工方案03-28
武汉大学c语言题库05-03
201209学期航空法规作业409-28
优秀小学生的评语优秀4篇03-26
阅读单词05-09
县长在财政工作会议讲话03-17
如何处理好业主与物业管理企业的关系12-28
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 数据结构
- 习题
- 山东省2016年上半年安全员B证考核考试题
- 31实用播音主持教程(婚礼策划主持人)
- MATLAB
- 有掘必探有采必探管理制度
- 上海大众凌渡 - 图文
- 七年级生物下册期末考试卷及答案 - 图文
- 临近既有线施工安全防护专项方案与临近高压线下施工安全专项方案汇编
- 度米作文汇编之初三写景作文清清的小河
- 南开17春学期《公共关系学》在线作业 免费答案
- 汕尾导游词(10个景点)
- 郭绪明心得体会
- 实验室使用安全测试题及答案11
- 第二单元 第一课 发展职业生涯要从所学专业起步 - 图文
- 山东省聊城教育学院专业山东省聊城教育学院招生网站-山东省聊城教育学院分数线
- 领导力测试 - 结构化面试
- 急性肾衰竭试题
- 年 度 考 核 登 记 表 - 图文
- 东南大学成贤学院10-11(上)高等数学B期中
- 华师大版七年级上科学期中试卷
- 德育教学案例:把爱种在你心底