数据结构第九章习题课
1.用二分（对半）查找表的元素的速度比用顺序法( )
A．必然快 B. 必然慢 C. 相等 D. 不能确定
2.具有12个关键字的有序表，折半查找的平均查找长度（）
A. 3.1
B. 4
C. 2.5
D. 5
3．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。
A. 分块查找
B. 顺序查找
C. 折半查找
D. 基于属性4．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )
A．（100，80，90，60，120，110，130） B.（100，120，110，130，80，60，90）
C.（100，60，80，90，120，110，130）
D. (100，80，60，90，120，130，110)
5. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。
A. LL
B. LR
C. RL
D. RR
7. 下面关于B和B+树的叙述中，不正确的是( )
A. B树和B+树都是平衡的多叉树。
B. B树和B+树都可用于文
件的索引结构。
C. B树和B+树都能有效地支持顺序检索。
D. B树和B+树都能有效地
支持随机检索。
8. m阶B-树是一棵( )
A. m叉排序树
B. m叉平衡排序树
C. m-1叉平衡排序树
D. m+1叉平衡排序树
9. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个记录。
A．1 B. 2 C. 3 D. 4
10.下面关于哈希(Hash，杂凑)查找的说法正确的是( )
A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B．除留余数法是所有哈希函数中最好的
C．不存在特别好与坏的哈希函数，要视情况而定
D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
11. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需(（1）)
个链表。这些链的链首指针构成一个指针数组，数组的下标范围为(（2）) （1）A．17 B. 13 C. 16 D. 任意
（2）A．0至17 B. 1至17 C. 0至16 D. 1至16 12.设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法
解决冲突，则放入的位置是( )
A．8 B．3 C．5 D．9
13.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( )
A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次
14.将10个元素散列到100000个单元的哈希表中，则（）产生冲突。
A. 一定会
B. 一定不会
C. 仍可能会
15.散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处
理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。
（1）元素59存放在散列表中的地址是（）。
A．8 B. 9 C. 10 D. 11
（2）存放元素59需要搜索的次数是（）。
A． 2 B. 3 C. 4 D. 5
16.在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____。
答：4
17．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为__________。
答：6,9,11,12
18.在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__________
答：5
19. 在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是__________;若在某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是__________。
答：m-1,「m/2 -1
20、哈希表是通过将查找码按选定的__(1)__和__(2)__，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是_(3)__和__(4)__。一个好的哈
希函数其转换地址应尽可能__(5)__，而且函数运算应尽可能__(6)__。
答：(1)哈希函数(2)解决冲突的方法(3)选择好的哈希函数(4)处理冲突的方法(5)均匀(6)简单
21、哈希函数H（key）=key%p中，p值最好取__________。
答：小于等于表长的最大素数或不包含小于20的质因子的合数
22、对于长度为255的表，采用分块查找，每块的最佳长度为__________。答：16
23.如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。
答：(n+1)/2
24. __________法构造的哈希函数肯定不会发生冲突。
答：直接定址法
25. 127阶B-树中每个结点最多有__(1)__个关键字；除根结点外所有非终端结点至少有__(2)__棵子树；65阶B+树中除根结点外所有结点至少有__(3)__个关键字；最多有__(4)__棵子树；
答：(1)126 (2)64 (3)33 (4)65
26.已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。
#define N /*学生人数*/
int uprx(int a[N],int x ) /*函数返回大于等于X分的学生人数*/
{ int head=1,mid,rear=N;
do {mid=(head+rear)/2;
if(x<=a[mid]) __(1)__ else __(2)__;
}while(__(3)__);
if (a[head] return head; } 答：(1)rear=mid-1 (2)head=mid+1 (3)head>rear 27. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,…,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 succ 以关键字27为例：H（27）=27%7=6（冲突）H1=（6+1）%10=7（冲突）H2=（6+22）%10=0（冲突）H3=（6+33）%10=5 所以比较了4次。 28. 设一组数据为{1,14,27,29,55,68,10,11,23}，现采用的哈希函数是H(key)=key MOD 13，即关键字对13取模，冲突用链地址法解决，设哈希表的大小为13(0..12)，试画出插入上述数据后的哈希表。 29.设哈希(Hash)表的地址范围为0～17，哈希函数为：H (K)=K MOD 16, K 为关键字，用线性探测再散列法处理冲突，输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49)造出哈希表，试回答下列问题： (1)画出哈希表示意图； (2)若查找关键字63，需要依次与哪些关键字比较? (3) 若查找关键字60，需要依次与哪些关键字比较? (4) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 63比较。 （3）查找关键字60，H（k）=60 MOD 16=12，散列地址12内为空，查找失败。（4）ASL succ=23/11 30．设依以下次序给出关键字：34,16,19,21,5,49,24,62,3,17,45,8，构造3阶B-树。要求从空树开始，每插入一个关键字,画出一个树形。 31. 已知2棵2-3 B-树如下（省略外结点）： （1）对树（a）,请分别画出先后插入26，85两个新结点后的树形； （2）对树（b）,请分别画出先后删除53，37两个结点后的树形。 (a) （b） 32. 已知长度为11的表（xal,wan,wil,zol,yo,xul,yum,wen，wim,zi,yon），按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 33.依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排 序树 (1)试画出生成之后的二叉排序树; (2)对该二叉排序树作中序遍历，试写出遍历序列; (3)假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。答：（2）10,12,15,20,24,28,30,35,46,50,55,68 （3）ASL succ=41/12 34.已知关键字序列R={11,4,3,2,17,30,19}，请按算法步骤： （1）构造一棵哈夫曼树，并计算出它的带权路径长度WPL （2）构造一棵二叉排序树，如果对每个关键字的查找概率相同，求查找成功时的平均查找长度ASL。 35. 按下述次序输入关键字：e,i,p,k,,m,l,b,试画出A VL树的构造与调整过程。（要求画出每插入一个关键字检索树的形状及调整后的结果）。 36.对有14个元素的有序表A[1…14]作折半查找，当比较到A[4]时算法结束。被比较元素除A[4]外，还有哪几个？ 答：在有序表A[1..14]中，比较到A[4]时，已查找元素依次是A[7]，A[3]，A[5]。 37.假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题： (1).画出描述折半查找过程的判定树； (2).若查找元素54，需依次与那些元素比较? (3).若查找元素90，需依次与那些元素比较? (4).假定每个元素的查找概率相等，求查找成功时的平均查找长度。 38. 写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针p所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。用类C语言将上述算法写为过程形式。 void Delete（BSTree t，p） // 在二叉排序树t中，删除f所指结点的右孩子（由p所指向）的算法 {if（p->lchild==null）{f->rchild=p->rchild；free（p）；} //p无左子女 else //用p左子树中的最大值代替p结点的值 {q=p->lchild；s=q； while（q->rchild）{s=q；q=q->rchild ；}//查p左子树中序序列最右结点 if（s==p->lchild）//p左子树的根结点无右子女 {p->data=s->data；p->lchild=s->lchild；free（s）；} else{p->data=q->data；s->rchild=q->lchild；free（q）；} } }//Delete 39．给出折半查找的递归算法，并给出算法时间复杂度性分析。 int BinSrch（rectype r[ ]，int k，low，high） //在长为n的有序表中查找关键字k，若查找成功，返回k所在位置，查找失败返回0。 {if（low≤high）//low和high分别是有序表的下界和上界 {mid=（low+high）/2； if（r[mid].key==k）return （mid）； else if（r[mid].key>k）return （BinSrch（r,k，mid+1，high））; else return （BinSrch（r,k，low，mid-1））; } else return （0）；//查找失败。 }//算法结束 算法时间复杂度为O（logn）。 40．写出从哈希表中删除关键字为K的一个记录的算法，设哈希函数为H，解决冲突的方法为链地址法。 [题目分析] 用链地址法解决冲突的哈希表是一个指针数组，数组分量均是指向单链表的指针，（第i个）单链表结点有两个域，一个是哈希地址为i的关键字，另一个是指向同义词结点的指针。删除算法与单链表上删除算法类似。 typedef struct node {keytype key； struct node *next； }HSNode；*HSList typedef struct node *HLK； void Delete（HLK HT[]，keytype K） //用链地址法解决冲突，从哈希表中删去关键字为K的记录 {i=H（K）；//用哈希函数确定关键字K的哈希地址 if（HT[i]==null）{printf（“无被删除记录\n”）；exit（0）；} HLK p,q; p=H[i]；q=p；//p指向当前记录（关键字），q是p的前驱 while（p && p->key！=k）{q=p；p=p->next；} if（p==null）{printf（“无被删除记录”）；exit(0); } if（q==H[i]）//被删除关键字是链表中第一个结点 { HT[i]=HT[i].next；free（p）；} else{ q->next=p->next；free（p）；} }//结束Delete 41．设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。 （1）递归算法 void DecPrint(BSTree t） //递减序输出二叉排序树t中所有左子树为空右子树非空的结点数据域的值。 {if（t） {DecPrint(t->rchild)； if（!t->lchild && t->rchild）printf(t->data)； DecPrint(t->lchild）； } }//DecPrint （2）非递归算法 void DecPrint(BSTree t） // 递减序输出二叉排序树t中所有左子女为空右子女非空的结点的值{BSTree S[]；//S是二叉排序树结点指针的栈，容量足够大 int top=0； while（t || top>0） {while（t） {S[++top]=t；t=t->rchild ；} //沿右分枝向下 if（top>0） {t=S[top--]； if（!t->lchild && t->rchild）printf(t->data)； t=t->lchild；// 去左分枝 }//if }//while }//算法结束 42．已知二叉排序树采用二叉链表存储结构，根结点的指针为T，链结点的结构为（lchild,data,rchild），其中lchild、rchild分别指向该结点左、右孩子的指针（当孩子结点不存在时，相应指针域为null）,data域存放结点的数据信息。请写出递归算法，从小到大输出二叉排序树中所有数据值>=x的结点的数据。要求先找到第一个满足条件的结点后再依次输出其他满足条件的结点。 [题目分析]利用二叉排序树的性质，如果根结点的值>=x,则除左分枝中可能有 void P rint（BSTree t） // 中序输出以t为根的二叉排序树的结点 {if（t）{P rint（t->lchild）； printf（t->data）； P rint（t->rchild）； } } void PrintAllx(BSTree bst，datatype x） //在二叉排序树bst中，查找值≥x的结点并输出 {p=bst； if（p） {while（p && p->data bst=p; //bst所指结点是值≥x的结点的树的根 if（p） {f=p; p=p->lchild ；//找第一个值 while（p && p->data≥x）//沿左分枝向下，找第一个值 {f=p；p=p->lchild ；} //f是p的双亲结点的指针，且指向第一个值≥x的结点 if(p) f->lchild=null; //双亲与找到的第一个值 P rint(bst)；//输出以bst为根的子树 }//while }//内层if（p） }//第一层if（p） }//PrintAllx 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"< 第三章习题 1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： ⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？ ⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出 以“S”表示进栈、以“X”表示出栈的栈操作序列）。 2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4步 操作： （1）输出队首元素； （2）把队首元素值插入到队尾； （3）删除队首元素； （4）再次删除队首元素。 直到队列成为空队列为止，得到输出序列： （1）A、C、E、C、C （2） A、C、E （3） A、C、E、C、C、C （4） A、C、E、C 3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？ 4.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操 作数栈和运算符栈的变化过程： A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ 5.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1& 序列2’ 模式的字符序列。其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。 6.假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写 正确的表达式转换为逆波兰式。 7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针）， 试编写相应的队列初始化、入队列和出队列的算法。 8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分 头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 第3章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ） A、HS->next=s; B、s->next=HS->next；HS->next=s; C、s->next=HS；HS=s; D、s->next=HS；HS=HS->next; 4.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C） A 、x=HS；HS=HS->next; B 、HS=HS->next；x=HS->data; C 、x=HS->data；HS=HS->next; D 、s->next=Hs；Hs=HS->next; 5.表达式a*(b+c)-d 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ B ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为空的条件是（） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从 队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（） A、1，5 B、2, 4 C、4，2 D、5，1 11.用单链表表示的链式队列的队头在链表的（）位置 A、链头 B、链尾 C、链中 12.判定一个链队列Q（最多元素为n 个）为空的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13.在链队列Q 中，插入s 所指结点需顺序执行的指令是（） A 、Q.front->next=s；f=s; B 、Q.rear->next=s；Q.rear=s; 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 《数据结构》实验报告 实验序号：4 实验项目名称：栈的操作 附源程序清单： 1. #include { return false; } else { st->top++; //移动栈顶位置 st->data[st->top]=x; //元素进栈 } return true; } bool Pop(SqStack *st,ElemType &e) //出栈 { if(st->top==-1) { return false; } else { e=st->data[st->top]; //元素出栈 st->top--; //移动栈顶位置} return true; } //函数名：Pushs //功能：数组入栈 //参数：st栈名,a->数组名，i->数组个数 bool Pushs(SqStack *st,ElemType *a,int i) { int n=0; for(;n 第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType; .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是__________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 课程实验报告课程名称：数据结构 专业班级：信安1302 学号： 姓名： 指导教师： 报告日期：2015. 5. 12 计算机科学与技术学院 目录 1 课程实验概述............ 错误!未定义书签。 2 实验一基于顺序结构的线性表实现 2.1 问题描述 ...................................................... 错误!未定义书签。 2.2 系统设计 ...................................................... 错误!未定义书签。 2.3 系统实现 ...................................................... 错误!未定义书签。 2.4 效率分析 ...................................................... 错误!未定义书签。 3 实验二基于链式结构的线性表实现 3.1 问题描述 ...................................................... 错误!未定义书签。 3.2 系统设计 ...................................................... 错误!未定义书签。 3.3 系统实现 ...................................................... 错误!未定义书签。 3.4 效率分析 ...................................................... 错误!未定义书签。 4 实验三基于二叉链表的二叉树实现 4.1 问题描述 ...................................................... 错误!未定义书签。 4.2 系统设计 ...................................................... 错误!未定义书签。 4.3 系统实现 ...................................................... 错误!未定义书签。 4.4 效率分析 ...................................................... 错误!未定义书签。 5 实验总结与评价 ........... 错误!未定义书签。 1 课程实验概述 这门课是为了让学生了解和熟练应用C语言进行编程和对数据结构进一步深入了解的延续。 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: "; cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } } template 习题二 ⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。 2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。 解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。 2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。 Void insert(Lnode *h,int a,int b) {Lnode *p,*q,*s; s=(Lnode*)malloc(sizeof(Lnode)); s->data=b; p=h->next; while(p->data!=a&&p->next!=NULL) {q=p; p=p->next; } if (p->data==a) {q->next=s; s->next=p;} else {p->next=s; s->next=NULL; } } 2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。 Lnode *cf(Lnode *ha) {Lnode *p,*q,*s,*hb; int t; p=ha->next; q=ha; t=0; hb=(Lnode*)malloc(sizeof(Lnode)); s=hb; while(p->next!=NULL) {if (t==0) {q=p;p=p->next;t=1;} else {q->next=p->next; p->next=s->next; s->next=p; s=p; p=p->next; t=0; } } s->next=NULL; return (hb); } 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 附录A 实验报告 课程：数据结构（c语言）实验名称：图的建立、基本操作以及遍历系别：数字媒体技术实验日期： 12月13号 12月20号 专业班级：媒体161 组别：无 姓名：学号： 实验报告内容 验证性实验 一、预习准备： 实验目的： 1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围； 2、熟练掌握几种常见图的遍历方法及遍历算法； 实验环境：Widows操作系统、VC6.0 实验原理： 1.定义： 基本定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(V ertex)的非空有限集E(G)是边(Edge)的有限集合，边是顶点的无序对(即：无方向的，（v0,v2）)或有序对（即：有方向的, 无向图中顶点V i的度TD(V i)是邻接矩阵A中第i行元素之和有向图中， 顶点V i的出度是A中第i行元素之和 顶点V i的入度是A中第i列元素之和 邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧） 特点: 无向图中顶点Vi的度为第i个单链表中的结点数有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。 图的遍历 从图中某个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次过程.。遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。图的遍历有两条路径：深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需要时间为O（n2），n为图中顶点数；而当以邻接表作图的存储结构时，找邻接点所需时间为O（e），e 为无向图中边的数或有向图中弧的数。 实验内容和要求： 选用任一种图的存储结构，建立如下图所示的带权有向图： 要求：1、建立边的条数为零的图； 第六章习题 1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，n k个度为k的结点，则该树中有多少个叶子结点并证明之。 4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 6．给出满足下列条件的所有二叉树： ①前序和后序相同 ②中序和后序相同 ③前序和后序相同 7．n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个？ 8．画出与下列已知序列对应的树Ｔ： 树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。 9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 请为这8个字母设计哈夫曼编码。 10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因. 11. 画出和下列树对应的二叉树： 12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。 15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。 数据结构(C语言版) 实验报告 专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序 的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表 LinkList CreatList(void); //函数，用头插入法建立带头结点的单链表 ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点 void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存 数据结构实验报告 想必学计算机专业的同学都知道数据结构是一门比较重要的课程，那么，下面是给大家整理收集的数据结构实验报告，供大家阅读参考。 数据结构实验报告1 一、实验目的及要求 1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。 本实验训练的要点是"栈"和"队列"的观点; 二、实验内容 1) 利用栈，实现数制转换。 2) 利用栈，实现任一个表达式中的语法检查(选做)。 3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列); 三、实验流程、操作步骤或核心代码、算法片段 顺序栈： Status InitStack(SqStack ) { S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!S.base) return ERROR; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } Status DestoryStack(SqStack ) { free(S.base); return OK; } Status ClearStack(SqStack ) { S.top=S.base; return OK; } Status StackEmpty(SqStack S) { if(S.base==S.top) return OK; return ERROR; } int StackLength(SqStack S) { return S.top-S.base; } Status GetTop(SqStack S,ElemType ) { if(S.top-S.base>=S.stacksize) { S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType)); if(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; } Status Push(SqStack ,ElemType e) { if(S.top-S.base>=S.stacksize) { S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType)); if(!S.base) return ERROR; 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data数据结构实验报告格式
(完整版)数据结构实验报告全集
数据结构第三章习题答案
数据结构实验报告
完整版数据结构习题集第3章栈和队列
数据结构实验报告模板
《数据结构》实验报告
数据结构第三章栈和队列3习题
经典数据结构面试题(含答案)
数据结构课程实验报告(15)
数据结构实验报告--图实验
数据结构上机例题及答案
数据结构实验报告及心得体会
数据结构实验报告(图)
数据结构课后习题及解析第六章
数据结构实验报告 - 答案汇总
数据结构实验报告
数据结构经典算法试题