中国铁道出版社数据结构(第二版)单元5练习参考答案
单元练习5
一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）
（ㄨ）（1）串是n个字母的有限序列。
（√）（2）串的数据元素是一个字符。
（ㄨ）（3）串的长度是指串中不同字符的个数。
（ㄨ）（4）如果两个串含有相同的字符，则说明它们相等。
（ㄨ）（5）如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。
（√）（6）串的堆分配存储是一种动态存储结构。
（ㄨ）（7）“DT”是“DA TA”的子串。
（ㄨ）（8）串中任意个字符组成的子序列称为该串的子串。
（√）（9）子串的定位运算称为模式匹配。
（√）（10）在链串中为了提高存储密度，应该增大结点的大小。
二．填空题
（1）由零个或多个字符组成的有限序列称为字符串（或串）。
（2）字符串按存储方式可以分为：顺序存储、链接存储和堆分配存储。
（3）串的顺序存储结构简称为顺序串。
（4）串顺序存储非紧凑格式的缺点是：空间利用率低。
（5）串顺序存储紧凑格式的缺点是对串的字符处理效率低。
（6）串链接存储的优点是插入、删除方便，缺点的空间利用率低。
（7）在C或C++语言中，以字符\0 表示串值的终结。
（8）空格串的长度等于空格的个数。
（9）在空串和空格串中，长度不为0的是空格串。
（10）两个串相等是指两个串相长度等，且对应位置的字符都相同。
（11）设S="My Music"，则LenStr(s)= _ 8 。
（12）两个字符串分别为：S1="Today is"，S2="30 July,2005",ConcatStr(S1,S2)的结果是： Today is 30 July,2005 。
（13）求子串函数SubStr("Today is 30 July,2005",13,4)的结果是：July 。
（14）在串的运算中，EqualStr(aaa,aab)的返回值为<0 。
（15）在串的运算中，EqualStr(aaa,aaa)的返回值为0 。
（16）在子串的定位运算中，被匹配的主串称为目标串，子串称为模式。
（17）模式匹配成功的起始位置称为：有效位移。
（18）设S="abccdcdccbaa"，T="cdcc"，则第 6 次匹配成功。
（19）设S="c:/mydocument/text1.doc"，T="mydont "，则字符定位的位置为0 。（20）若n为主串长度，m为子串长度，且n>>m，则模式匹配算法最坏情况下的时间复杂度为：(n-m+1)*m 。
三．选择题
（1）串是一种特殊的线性表，其特殊性体现在（ B ）。
A.可以顺序存储B．数据元素是一个字符
C.可以链接存储D．数据元素可以是多个字符
（2）某串的长度小于一个常数，则采用（ B ）存储方式最节省空间。
A．链式 B．顺序 C．堆结构D．无法确定
（3）以下论述正确的是（ C ）。
A．空串与空格串是相同的B．"tel"是"Teleptone"的子串
C．空串是零个字符的串 D. 空串的长度等于1
（4）以下论述正确的是（ B ）。
A．空串与空格串是相同的B．"ton"是"Teleptone"的子串
C．空格串是有空格的串 D. 空串的长度等于1
（5）以下论断正确的是( A )。
A．""是空串，" "空格串 B．"BEIJING"是"BEI JING"的子串
C．"something"<"Somethig" D．"BIT"="BITE"
（6）设有两个串S1和S2，则EqualStr(S1,S2)运算称作( D )。
A. 串连接B．模式匹配
C. 求子串D．串比较
（7）串的模式匹配是指（ D ）。
A．判断两个串是否相等C．找某字符在主串中第一次出现的位置
B．对两个串比较大小D．找某子串在主串中第一次出现的第一个字符位置（8）若字符串"ABCDEFG"采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节。则该字符串的存储密度为( D )。
A．20％ B．40％ C．50％ D．33．3％
（9）若字符串"ABCDEFG"采用链式存储，假设每个指针占用2个字节，若希望存储密度50％，则每个结点应存储( A )个字符。
A．2 B．3 C．4 D．5
（10）设串S1="I AM"，S2="A SDUDENT",则ConcatStr(S1,S2)=( B )。
A．"I AM" B．"I AM A SDUDENT"
C．"IAMASDUDENT" D. "A SDUDENT"
（11）设S=""，则LenStr（S）=（ A ）。
A．0 B．1 C．2 D．3
（12）设目标串T="AABBCCDDE"，模式P="ABCDE"，则该模式匹配的有效位移为( A )。
A．0 B．1 C．2 D．3
（13）设目标串T="AABBCCDDEEFF"，模式P="CCD"，则该模式匹配的有效位移为( D )。
A．2 B．3 C．4 D. 5
（14）设目标串T="aabaababaabaa"，模式P="abab",朴素匹配算法的外层循环进行了( D )次。
A．1 B．9 C．4 D．5
（15）朴素模式匹配算法在最坏情况下的时间复杂度是( D )。
A．O（m） B．O（n） C．0（m+n） D．0（m*n）
（16）S="morning"，执行求子串函数SubStr(S,2,2)后的结果为( B )。
A．"mo" B．"or" C．"in" D．"ng"
（17）S1="good"，S2="morning"，执行串连接函数ConcatStr(S1,S2)后的结果为( A )。
A．"goodmorning" B．"good morning"
C．"GOODMORNING" D．"GOOD MORNING"
（18）S1="good"，S2="morning"，执行函数SubStr(S2,4,LenStr(S1))后的结果为( B )。
A．"good" B．"ning"
C．"go" D．"morn"
（19）设串S1="ABCDEFG"，S2="PQRST" ,
则ConcatStr(SubStr(S1,2,LenStr(S2)),SubStr(S1,LenStr(S2),2))的结果串为( D )。
A．BCDEF B．BCDEFG C．BCPQRST D. BCDEFEF
（20）若串S="SOFTWARE"，其子串的数目最多是：（ C ）。
A．35 B．36 C．37 D．38
（8+7+6+5+4+3+2+1+1=37）
四．程序题填空（每空2分，共50分）
1．下面程序是把两个串r1和r2首尾相连的程序，即：r1=r1+r2，试完成程序填空。
typedef Struct
{ char vec[MAXLEN]; // 定义合并后串的最大长度
int len; // len为串的长度
}St ;
void ConcatStr(Str *r1,Str *r2) // 字符串连接函数
{ int i;
cout << r1->vec<
if(r1->len+r2->len> MAXLEN )
cout<< "两个串太长，溢出！";
else
{ for(i=0;i< r2->len ;i++) // 把r2连接到r1
r1->vec[ r1->len+i ]=r2->vec[i];
r1->vec[r1->len+i]= '\0' ; // 添上字符串结束标记
r1->len= r1->len+r2->len ; // 修改新串长度
}
}
2. 设x和y两个串均采用顺序存储方式，下面的程序是比较x 和y两个串是否相等的函数，试完成程序填空。
#define MAXLEN 100
typedef struct
{ char vec[MAXLEN]; len;
} str;
int same (x,y)
str *x,*y;
{ int i=0,tag=1;
if (x->len!= y->len) return (0); // (或<> )
else
{ while ( i
{ if ( x->vec[i] != y->vec[i] ) tag=0 ;
i++ ; （或i=i+1 ）
}
return (tag);
}
}
3．下面算法是判断字符串是否为回文（即正读和倒读相同），试完成程序填空。解：#include "stdio.h"
typedef struct
{ char vec[MAXLEN];
int len;
}str;
void Palindrome (str s)
{ int i=0;
ing j= s.len-1 ;
while ( j-i>=1 )
{ if ( s.vec[i]== s.vec[j] )
{i++; j-- ;continue} // (或 j=j+1 )
else
break;
}
if ( j-i>=1 )
cout<<"It is not a palindrome\n";
else
cout<<"It is a palindrome\n";
}
五．编程题
1．设下面所用的串均采用顺序存储方式，其存储结构定义如下，请编写下列算法：#define MAXLEN 100
typedef struct
{ char vec[MAXLEN];
int len;
} str;
（1）将串中r中所有其值为ch1的字符换成ch2的字符。
（2）将串中r中所有字符按照相反的次序仍存放在r中。
（3）从串r中删除其值等于ch的所有字符。
（4）从串r1中第index个字符起求出首次与字符r2相同的子串的起始位置。
（5）从串r中删除所有与串r3相同的子串（允许调用第（4）小题的函数）。
（6）编写一个比较x 和y两个串是否相等的函数。
2．设计一算法判断字符串是否为回文（即正读和倒读相同）
3．设计一算法从字符串中删除所有与字串"del"相同的子串
4．设计一算法统计字符串中否定词"not"的个数
1．解：
（1）算法思想：从头至尾扫描r串，对于值为ch1的元素直接替换成ch2即可。
str *trans (r,ch1,ch2)
str *r;
char ch1,ch2;
{ int i;
for (i=0;i
if (r->vec[i]==ch1)
r-vec[i]=ch2;
return(r);
}
（2）算法思想是：将第一个元素与最后一个元素交换，第二个元素与倒数第二个元素交换，依次类推，便将该串的所有字符反序了。
str *invert (r)
str *r;
{ int i;
char x;
for (i=0;i< (r->len%2) ;i++)
{ x=r->vec[i];
r->vec[i]=r->[r->len-i+1];
r->vec[r->len-i+1]=x;
}
return (r );
}
（3）算法思想：从头到尾扫描r串，对于值为ch的元素用移动的方式进行删除。
str *delall (r,ch)
str *r;
char ch;
{ int i,j;
for (i=0;i
if (r->vec[i]==ch)
{
for (j=i;j
r->vec[i]=r->vec[i+1];
r->len=r->len-1;
}
return (r );
}
（4）算法思想：从第index个元素开始扫描r1，当其元素值与r2的第一个元素的值相同时，判定它们之后的元素值是否依次相同，直到r2结束为止，若都相同则返回，否则继续上述过程直到r1扫描完为止。
int partposition(r2,r1,index)
str *r2, *r1;
int index;
{ int i,j,k;
for (i=index;r1->vec[i];i++)
for (j=i,k=0;r1->vec[j]==r2->vec[k];j++,k++)
if (!r2->vec[k+1])
return(i);
return(-1);
}
（5）算法思想：从位置1开始调用第（4）小题的函数partposition（），若找到了一个相同子串，则调用delsubstring（），再相同的方法查找后面位置的相同子串。
str *delstringall(r,r3)
str *r, *r3;
{ int i=0;
while (i
{ if (partposition(r,r3,i)!=-1)
delsubstring(r,i,r3->len)
i++;
}
}
（6）两个串相等的条件是两个串的长度相等，且两个串的对应的字符必须都相同。
int same(x,y)
str *x,*y;
{ int i=0,tag=1;
if (x->len!=y->len)
return(0);
else
{ while (i
{ if (x->vec[i]!=y->vec[i])
tag=0;
i++;
}
return(tag);
}
}
2．解：#include "stdio.h"
typedef struct
{ char *head;
int length;
}Hstring;
void isPalindrome(Hstring s)
{
int i=0;
int j=s.length-1;
while (j-i>=1)
{
if (s.head[i]==s.head[j])
{i++; j--; continue;}
else
break;
}
if (j-i>=1)
printf("Tt is not a palindrome\n ");
else
printf("it is a palindrome\n");
}
3．解：#include "stdio.h"
#include "string.h"
typedef struct
{ char *head;
int length;
}Hstring;
char *DeleteSubString(Hstring S,Hstring T)
{
int i=0;
int j,k;
int Slength=S.length;
int Tlength=T.length;
char *tail;
while (i<=Slenght-Tlength)
{
j=0;k=i;
while (j if (j==Tlength) // 若匹配则执行下面的程序 { if (i==0) // 若位于头位置则改变头指针 { S.head=S.head+Tlength; S.length-=Tlength; Slength-=Tlength; i=0; } else if (i+Tlength tail=S.head+i+Tlength; strcpy(S.head+i,tail); S.length-=Tlength; Slength-=Tlength; } else // 若位于尾部则割去 strncpy(S.head+i,”\0”,1); } else // 若不匹配则i加1 i++; } return S.head; } 4．解：#include "stdio.h" #include "string.h" int Find_word(char *text, const char *word) { int textlength=strlen(text); int wordlength=strlen(word); int i,j,k; int count=0; for (i=0;i { j=0; k=i;} while (j if (j==wordlength && word[j]==’\0’) // 匹配成功计数器加1 count ++; } return count; } 模拟考题 1．下列程序是在字符串s的第i个字符起，连续删除长度为j的子串，试完成程序填空。 #include "stdio.h" typedef struct { char vec[MAXLEN]; int len; }str; void DelStr(Str *s,int i,int j) { int k; if (i+j-1> s->len ) cout<<"\n\t\t所要删除的子串超界！\n"; else { for (k=i+j;k< s->len ;k++,i++) s->vec[i]=s->vec[ k ]; s->len=s->len-j; s->vec[s->len]=' \0 '; } } main（） { cout<< "\n\t\t请输入从第几个字符开始："; cin>>i; cout<<"\n\t\t请输入删除的连续字符数："; cin>>j; DelStr(s, i-1 ,j); } 2．下列程序是在字符串s的第i个字符前，插入一个子串s1，试完成程序填空。 #include "stdio.h" typedef struct {char vec[MAXLEN]; int len; }str; Str *InsStr(Str *s,Str *s1,int i) { int k; if (i>=s->len|| s->len+s1->len >MAXLEN) printf("\n\t\t不能插入!\n"); else {for (k=s->len-1;k>=i; k-- ) s->vec[ s1->len+k ]=s->vec[k]; for (k=0;k< s1->len ;k++) s->vec[i+k]=s1->vec[k]; s->len= s->len+s1->len ; s->vec[s->len]='\0'; } return s; } main() { cout<< "\n\t\t请输入在第几个字符前插入："; cin>>i; cout<< "\n\t\t请输入所要插入的字符串："; s1=CseateStr(&b); InsStr(s,s1,i-1); } 3．下列程序是在字符串s的第i个字符起，取出长度为j的子串，试完成程序填空。 #include "stdio.h" typedef struct {char vec[MAXLEN]; int len; }str; void SubStr(Str *s,int i,int j) { int k; Str a; Str *s1=&a; if (i+j-1> s->len ) { cout<< "\n\t\t子串超界!\n"; return; } else { for(k=0; k s1->vec[k]=s->vec[ i+k-1 ]; s1->len=j; s1->vec[s1->len]='\0'; } cout<< "\n\t\t取出字符为："; puts(s1->vec); } main() { cout<< "\n\t\t请输入从第几个字符开始："; cin>>i; cout<< "\n\t\t请输入取出的连续字符数："; cin>>j; SubStr (s,i,j); } ⒉什么是操作系统？操作系统追求的主要目标是什么？ 答：操作系统是计算机系统中的一个系统软件，是能有效地组织和管理计算机系统中的硬件和软件资源，合理地组织计算机工作流程，控制程序的执行，并向用户提供各种服务功能，使得用户能够灵活、方便、有效地使用计算机，并使整个计算机系统能高效地运行的一组程序模块的集合。 操作系统追求的主要目标包括四个方面，分别是：方便性、有效性、可扩充性、开放性。⒌操作系统分成哪几类？ 答：单道批处理系统、多道批处理系统、分时系统、实时系统、微机操作系统、多处理机操作系统、网络操作系统和分布式操作系统。 ⒍从资源管理观点看，操作系统具有哪些功能？ 答：处理机管理、存储器管理、I/O设备管理、文件管理。 ⒕简述操作系统的特性。 答：并发、共享、虚拟、异步性。 第二章 ⒊什么叫作业调度？作业调度选择作业的必要条件是什么？ 答：操作系统根据允许并行工作的道数和一定的算法从等待的作业（后备作业）中选取若干作业装入主存储器，使它们可以去获得处理器运行，这项工作称为作业调度。作业调度的必要条件是，即只有在系统当前尚未分配的资源可以满足在系统中等待执行的作业的资源要求。 ⒍系统采用不能移动已在主存储器中作业的可变分区方式管理主存储器，现有供用户使用的主存空间100K，系统配有4台磁带机，有一批作业见表2.6。 表2.6 作业序号进输入井时间要求计算时间需要主存量申请磁带机数 1 l0:00 25分钟15K 2台 2 10:20 30分钟60K 1台 3 10:30 10分钟50K 3台 4 10:3 5 20分钟10K 2台 5 10:40 15分钟30K 2台 该系统采用多道程序设计技术，对磁带机采用静态分配，忽略设备工作时间和系统进行调度所花的时间，请分别写出采用“先来先服务调度算法”、“计算时间短的作业优先算法”和选中作业执行的次序以及各个作业的装入主存时间、开始执行时间、完成时间、周转时间以及它们的平均周转时间。 答：先来先服务调度算法”、“计算时间短的作业优先算法”和选中作业执行的次序以及它们的平均周转时间的结果是一样的： 选中作业的次序：选中作业执行的次序均为1，2，4，5，3。 作业1的周转时间：25分钟； 作业2的周转时间：35分钟； 作业3的周转时间：70分钟； 作业4的周转时间：40分钟； 数据结构实验五矩阵的压缩存储与运算 第五章矩阵的压缩存储与运算 【实验目的】 1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现； 2. 掌握稀疏矩阵的加法、转置、乘法等基本运算； 3. 加深对线性表的顺序存储和链式结构的理解。 第一节知识准备 矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。 一、特殊矩阵的压缩存储 1. 对称矩阵和上、下三角阵 若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。 问题已经转化为：已知二维矩阵A[i，j]，如图5-1， 我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。 任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里： k=i(i+1)/2+j (i≥j) 图5-1 下三角矩阵 a00 a10 a11 a20 … an-1,0 … an-1,n-1 k= 0 1 2 3 …n(n- 1)/2 …n(n+1)/2-1 图5-2下三角矩阵的压缩存储 反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。这里，i=d-1，（d是使sum= > k的最小整数），j= 。 2. 三对角矩阵 在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。 图5-3 三对角矩阵A 与下三角矩阵的存储一样，我们也可以用一个一维数组ma[0..3n-2]来存放三对角矩阵A，其对应关系见图5-4。 a00 a01 a10 a11 a12 … an-1,n-2 an-1,n-1 k= 0 1 2 3 4 … 3n-3 3n-2 图5-4下三角矩阵的压缩存储 A中的一对下标(i,j)与ma中的下标k之间有如下的关系： 公式中采用了C语言的符号，int()表示取整，‘%’表示求余。 考研计算机数据结构模拟试题及答案(五) 一、选择题(30分) 1. 设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为( )。 (A) 20 (B) 30 (C) 40 (D) 45 2.执行一趟快速排序能够得到的序列是( )。 (A) [41，12，34，45，27] 55 [72，63] (B) [45，34，12，41] 55 [72，63，27] (C) [63，12，34，45，27] 55 [41，72] (D) [12，27，45，41] 55 [34，63，72] 3.设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是( )。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0 4.时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是( )。 (A) 堆排序(B) 冒泡排序(C) 希尔排序(D) 快速排序 5.设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是( )。 (A) 空或只有一个结点(B) 高度等于其结点数 (C) 任一结点无左孩子(D) 任一结点无右孩子 6.一趟排序结束后不一定能够选出一个元素放在其最终位置上的 是( )。 (A) 堆排序(B) 冒泡排序(C) 快速排序(D) 希尔排序 7.设某棵三叉树中有40个结点，则该三叉树的最小高度为( )。 (A) 3 (B) 4 (C) 5 (D) 6 8.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为( )。 (A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n) 9.二路归并排序的时间复杂度为( )。 (A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n) 10. 深度为k的完全二叉树中最少有( )个结点。 (A) 2k-1-1 (B) 2k-1 (C) 2k-1+1 (D) 2k-1 11.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为( )。 (A) front->next=s;front=s; (B) s->next=rear;rear=s; (C) rear->next=s;rear=s; (D) s->next=front;front=s; 12.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为( )。 (A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3) 13.设某哈夫曼树中有199个结点，则该哈夫曼树中有( )个叶子结点。 (A) 99 (B) 100 (C) 101 (D) 102 实验报告 课程名称数据结构实验名称查找与排序的实现 系别专业班级指导教师11 学号实验日期实验成绩 一、实验目的 (1)掌握交换排序算法（冒泡排序）的基本思想； (2)掌握交换排序算法（冒泡排序）的实现方法； (3)掌握折半查找算法的基本思想； (4)掌握折半查找算法的实现方法； 二、实验内容 1.对同一组数据分别进行冒泡排序，输出排序结果。要求： 1)设计三种输入数据序列：正序、反序、无序 2)修改程序： a)将序列采用手工输入的方式输入 b)增加记录比较次数、移动次数的变量并输出其值，分析三种序列状态的算法时间复杂 性 2.对给定的有序查找集合，通过折半查找与给定值k相等的元素。 3.在冒泡算法中若设置一个变量lastExchangeIndex来标记每趟排序时经过交换的最后位置， 算法如何改进？ 三、设计与编码 1.本实验用到的理论知识 2.算法设计 3.编码 package sort_search; import java.util.Scanner; public class Sort_Search { //冒泡排序算法 public void BubbleSort(int r[]){ int temp; int count=0,move=0; boolean flag=true; for(int i=1;i 单元练习3 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （√）（1）栈是运算受限制的线性表。 （√）（2）在栈空的情况下，不能作出栈操作，否则产生下溢出。 （ㄨ）（3）栈一定是顺序存储的线性结构。 （√）（4）栈的特点是“后进先出”。 （ㄨ）（5）空栈就是所有元素都为0的栈。 （ㄨ）（6）在C或C++语言中设顺序栈的长度为MAXLEN，则top=MAXLEN时表示队满。 （√）（7）链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。 （ㄨ）（8）一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。 （ㄨ）（9）递归定义就是循环定义。 （√）（10）将十进制数转换为二进制数是栈的典型应用之一。 二．填空题 （1）在栈结构中，允许插入、删除的一端称为栈顶。 （2）在顺序栈中，当栈顶指针top=-1时，表示栈空。 （3）在有n个元素的栈中，进栈操作的时间复杂度为 O（1）。 （4）在栈中，出栈操作的时间复杂度为：O(1) 。 （5）已知表达式，求它的后缀表达式是栈的典型应用。 （6）在一个链栈中，若栈顶指针等于NULL，则表示栈空。 （7）向一个栈顶指针为top的链栈插入一个新结点*p时，应执行p->next=top；和top=p；操作。 （8）顺序栈S存储在数组 S->data[0..MAXLEN-1]中，进栈操作时要执行的语句有：S->top ++ 。（或= S->top+1） （9）链栈LS，指向栈顶元素的指针是 LS->next 。 （10）从一个栈删除元素时，首先取出栈顶元素，然后再移动栈顶指针。 （11）由于链栈的操作只在链表的头部进行，所以没有必要设置头结点。 （12）已知顺序栈S，在对S进行进栈操作之前首先要判断栈是否满。 （13）已知顺序栈S，在对S进行出栈操作之前首先要判断栈是否空。 （14）若内存空间充足，链栈可以不定义栈满运算。 （15）链栈LS是空的条件是 LS->next=NULL 。 （16）链栈LS的栈顶元素是链表的首元素。 （17）同一栈的各元素的类型相同。 （18）若进栈的次序是A、B、C、D、E，执行三次出栈操作以后，栈顶元素为 B 。 （19）A+B/C-D*E的后缀表达式是：ABC/+DE*- 。 （20）四个元素按A、B、C、D顺序进S栈，执行两次Pop（S，x）运算后，x的值是 C 。 数据结构实验五图子系统 实验五 实验题目:图子系统 指导老师:王春红 专业班级:计算机科学与技术系1105班姓名:李慧2011100521杜丽20111005122 白莹2011100523王媛2011100529 2013年 5月23日 实验类型综合实验室_软件实验室一__ 一、实验题目 1 图子系统 二、实验目的和要求 ,(掌握图的存储思想及其存储实现 ,(掌握图的深度、广度优先遍历算法思想及其程序实现 ,(掌握图的常见应用算法的思想及其程序实现。三、实验内容 实验内容二:所有顶点对的最短路径 1(设置4个村庄之间的交通，村庄之间的距离用各边上的权值来表示。现在要求从这4个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。 2(设计分析 用有向加权图表示的交通图中，有向边 第六章树 1. 对于图6.29给出的树，指出树中的根结点、叶结点和分支结点。并指出各个结点的度数和层数。 2. 对图6.29所示的树，采用先根次序、后根次序和中根次序遍历。问得到怎样的结点序列？ 3. 对图6.29所示的树，分别采用先根次序的父指针表示法、长子-兄弟表示法，试画出各种方法的图示。 4. 用三个结点A，B，C可以构成多少种不同的二叉树？请把它们画出来。 5. 将图 6.29所示的树转换成对应的二叉树是什么样子？请把它画出来。 6. 请按先根、后根和对称序遍历图6.30所示的二叉树，列出遍历所得的结点序列。 7 请将图6.30所示的二叉树转换成对应的树林，并按先根次序和后根次序遍历树林。 8. 对于给定的一组权值 w＝｛1，4，9，16，25，36，49，64，81，100｝， 构造具有Huffman树。并求出它的带权路径长度。 9 给出(a)所示树的双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代？ 10．画出下图所示的各二叉树所对应的森林。 11．假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。 1) 为这8个字母设计Huffman编码。 26构造连通网最小生成树的两个典型算法是______。 27．求图的最小生成树有两种算法，______算法适合于求稀疏图的最小生成树。 28. Prim（普里姆）算法适用于求______的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求______的网的最小生成树。 单元练习8 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （√）（1）图可以没有边，但不能没有顶点。 （ㄨ）（2）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。 （ㄨ）（3）邻接表只能用于有向图的存储。 （√）（4）一个图的邻接矩阵表示是唯一的。 （ㄨ）（5）用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。 （ㄨ）（6）有向图不能进行广度优先遍历。 （√）（7）若一个无向图的以顶点V1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。 （√）（8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。 （ㄨ）（9）用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。（√）（10）若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。 二．填空题 （1）图常用的存储方式有邻接矩阵和邻接表等。 （2）图的遍历有：深度优先搜和广度优先搜等方法。 （3）有n条边的无向图邻接矩阵中，1的个数是 _2n____。 （4）有向图的边也称为 _ 弧___ 。 （5）图的邻接矩阵表示法是表示 __顶点____之间相邻关系的矩阵。 （6）有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 __出度____。 （7）n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为：O（n2）。 （8）n个顶点e条边的图若采用邻接表存储，则空间复杂度为：O（n+e）。 （9）设有一稀疏图G，则G采用 _邻接表____存储比较节省空间。 （10）设有一稠密图G，则G采用 _邻接矩阵____存储比较节省空间。 （11）图的逆邻接表存储结构只适用于 __有向____图。 （12） n个顶点的完全无向图有 n(n-1)/2_ 条边。 （13）有向图的邻接表表示适于求顶点的出度。 （14）有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点V i的入度。 （15）对于具有n个顶点的图，其生成树有且仅有n-1 条边。 （16）对n个顶点，e条弧的有向图，其邻接表表示中，需要n+e 个结点。 （17）从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图的遍历。 （18）无向图的邻接矩阵一定是对称矩阵。 实验报告五查找（学科：数据结构） 姓名单位班级学号实验日期成绩评定教师签名批改日期 实验名称：实验五查找 5.1 折半查找 【问题描述】 某班学生成绩信息表中，每个学生的记录已按平均成绩由高到低排好序，后来发现某个学生的成绩没有登记到信息表中，使用折半查找法把该同学的记录插入到信息表中，使信息表中的记录仍按平均成绩有序。 【基本信息】 （1）建立现有学生信息表，平均成绩已有序。 （2）输入插入学生的记录信息。 （3）用折半查找找到插入位置，并插入记录。 【测试数据】 自行设计。 【实验提示】 （1）用结构数组存储成绩信息表。 （2）对记录中的平均成绩进行折半查找。 【实验报告内容】 设计程序代码如下: #include low=1; hight=n; strcpy(y,s[0].name ); x=s[0].avg ; while(low<=hight) { mid=(low+hight)/2; if(x>s[mid].avg ) hight=mid-1; else low=mid+1; } for(k=0;k 1. 实验步骤： 先定义顺序表的结点： typedef struct { KeyType key; InfoType otherinfo; }ElemType; typedef struct { ElemType *R; int length; }SqList; 然后定义一个随机取数的函数，存到顺序表中： void CreateList(SqList &L,int n) 然后定义一个显示顺序表的函数，将顺序表中的数据显示出来： void ListTraverse(SqList L) 然后通过排序函数，将所有的数据按照从大到小的顺序排列： void BubbleSort(SqList &L) 实验结果： 测试数据： 38 86 9 88 29 18 58 27 排序后： 9 18 27 29 38 58 86 88 BubbleSort排序方法中数据的比较次数为：27 疑难小结： 这个程序的难点在于排序函数，总是把从第几个数开始排序以及怎样循环弄错。 源代码： #include 第一章引论 1、计算机硬件是指计算机系统中由电子、机械和光电元件等组成的各种部件和设备。由这些部件和设备依据计算机系统结构的要求构成的有机整体，称为计算机硬件系统 2、计算机软件是指安装在计算机系统中的程序和有关的文件 3、按应用将软件分类为：系统软件、支撑软件和应用软件 4、操作系统的定义：操作系统是计算机系统中的系统软件，能有效的组织和管理计算机系统中的硬件和软件资源，合理的组织计算机工作流程，控制程序的执行，并向用户提供各种服务功能，使的用户能够合理、方便、有效的使用计算机，使整个计算机系统能更高效运行的一组程序模块的集合。 5、操作系统的目标：①方便性。②有效性。③可扩充性。④开放性。 6、单道批处理系统的特征：①自动性。②顺序性。③单道性。 7、多处理机操作系统的类型：①非对称多处理机模式②对称多处理机模式 8、网络操作系统的功能：①网络通信。②资源管理。③网络服务。 ④网络管理。⑤互操作能力。 9、资源的分类（4类）：处理机、存储器、I/O设备以及文件（程序和数据）。 10、处理及管理的功能:1进程控制 2进程同步 3进程通信 4调度。 11、处理机 :一般的处理机由运算器、一系列的寄存器以及高速缓存构成。 12、计算机存储系统的设计主要考虑3个问题：容量、速度和成本。 13、缓冲区：硬件设备之间进行数据传输时，专门用来暂存这些数据的一个存储区域。 第二章用户接口和作业管理 1、作业；通常是指用户在一次计算过程中或者一次事物处理过程中要求计算机系统所做的工作的集合。 2、每个作业有一个作业控制块，所有作业的作业控制块构成一个表，该表称为作业表 3、操作系统与用户之间的接口可以分为命令接口、程序接口和图形接口。 4、一个作业的建立过程包括两个子过程：一个是作业控制块JCB的建立，一个是作业的输入。 5、一般可以将作业的状态分为4个状态，即提交状态、后备状态、运行状态、完成状态。 第三章进程与进程管理 1、进程：进程是具有独立功能的可并发执行的程序在一个数据集合上的运行过程 2、进程的特征：（1）动态性（2）并发性（3）独立性（4）异步 实验五 查找算法实现 1、实验目的 熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法，比较它们的平均查找长度。 2、问题描述 查找表是数据处理的重要操作，试建立有100个结点的二叉排序树进行查找，然后用原数据建立AVL树，并比较两者的平均查找长度。 3、基本要求 （1）以链表作为存储结构，实现二叉排序树的建立、查找和删除。 （2）根据给定的数据建立平衡二叉树。 4、测试数据 随即生成 5、源程序 #include<> #include<> #include<> #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)>(b)) typedef int Keytype; typedef struct { Keytype key; //关键字域 }ElemType; typedef struct BSTnode { ElemType data; int bf; struct BSTnode *lchild,*rchild; }BSTnode,*BSTree; void InitBSTree(BSTree &T) {T=NULL; } void R_Rotate(BSTree &p) {BSTnode *lc; lc=p->lchild; p->lchild=lc->rchild; lc->rchild=p; p=lc; } void L_Rotate(BSTree &p) {BSTnode *rc; rc=p->rchild; p->rchild=rc->lchild; 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 《数据结构与算法分析》 实验报告书 学期：2014 － 2015 学年第 2 学期 班级：信息管理与信息系统2班 学号： 1310030217 姓名：田洪斌 实验类别：（★）基础型（）设计型 实验时间： 成绩： 信息管理系 一、实验内容 实现程序，按满二叉树给元素编号并输入的方式构造二叉树。 二、实验目的 1、掌握二叉树的静态及操作特点； 2、掌握二叉树的各种遍历方法； 3、掌握二叉树的存储、线索化等在C语言环境中的实现方法； 4、掌握哈夫曼树的构造方法及编码方法。 三、需求分析 用二叉树结构表示来完成输入、编辑、调试、运行的全过程。并规定： a.手动输入数字建立二叉树 b.程序可以输入、调试、运行、显示、遍历 c.测试数据：用户手动输入的数据 四、系统设计 1．数据结构设计 在本程序中对二叉树的存储主要用的是顺序存储结构，将二叉树存储在一个一维数组中。数据的输入输出都是采用整型数据进行。在主函数中只是定义数据类型，程序的实现功能化主要是在主函数中通过给要调用的函数参数来实现程序要求的功能。 2．程序结构设计 （1）程序中主要函数功能： main()/////////////////////////////////////////////主函数 menu()/////////////////////////////////////////////菜单 BiTree CreateBiTree()///////////////////////先序建立二叉树 （2）函数调用关系 见图4-1。 图4-1 函数关系图 五、 调试分析 1.算法和函数中出现了一些系统无法识别的变量，照成程序出现了错 误。原因是没有注意算法与源程序的区别。算法是简单的对源程序进行描述 的，是给人阅读的，所以有些变量没有定义我们就能看懂。而程序中的变量一定要先定义才能够被引用，才能被计算机识别。 2.在调试过程中遇到问题是利用C++程序进行调试的，找出错误并改正。 3.数据输出函数运行不正常，经检查程序，发现是定义错误，更改后错误排除； 六、 测试结果 1．运行时输入正确密码进入主界面，系统根据输入的数字选项来调用相应的函数。主要实现“功能选择”的界面，在这个界面里有显示系统的五大功能，根据每个功能前面的序号进行选择。以下为该界面： main BiTree CreateB iTree() meun() 单元测验4 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （√）（1）队列是限制在两端进行操作的线性表。 （√）（2）判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。 （×）（3）在链队列上做出队操作时，会改变front指针的值。 （√）（4）在循环队列中，若尾指针rear大于头指针front，其元素个数为rear- front。（×）（5）在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。（√）（6）链队列在一定范围内不会出现队满的情况。 （×）（7）在循环链队列中无溢出现象。 （×）（8）栈和队列都是顺序存储的线性结构。 （×）（9）在队列中允许删除的一端称为队尾。 （×）（10）顺序队和循环队关于队满和队空的判断条件是一样的。 二．填空题 （1）在队列中存取数据应遵循的原则是先进先出。 （2）队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 （3）在队列中，允许插入的一端称为队尾。 （4）在队列中，允许删除的一端称为队首（或队头）。 （5）队列在进行出队操作时，首先要判断队列是否为空。 （6）顺序队列在进行入队操作时，首先要判断队列是否为满。 （7）顺序队列初始化后，front=rear= -1 。 （8）解决顺序队列“假溢出”的方法是采用循环队列。 （9）循环队列的队首指针为front，队尾指针为rear，则队空的条件为 front == rear 。 （10）链队列LQ为空时，LQ->front->next= NULL 。 （11）设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为 O（n）。 （12）设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为 0（1）。 （13）在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为空。 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 数据结构与算法课程实验报告实验五：图的相关算法应用 姓名：cll 班级： 学号： 【程序运行效果】 一、实验内容： 求有向网络中任意两点之间的最短路 实验目的： 掌握图和网络的定义，掌握图的邻接矩阵、邻接表和十字链表等存储表示。掌握图的深度和广度遍历算法，掌握求网络的最短路的标号法和floyd算法。 二、问题描述： 对于下面一张若干个城市以及城市间距离的地图，从地图中所有可能的路径中求出任意两个城市间的最短距离及路径，给出任意两个城市间的最短距离值及途径的各个城市。 三、问题的实现： 3.1数据类型的定义 #define MAXVEX 50 //最大的顶点个数 #define MAX 100000 typedef struct{ char name[5]; //城市的名称 }DataType; //数据结构类型 typedef struct{ int arcs[MAXVEX][MAXVEX]; //临接矩阵 DataType data[MAXVEX]; //顶点信息 int vexs; //顶点数 }MGraph,*AdjMetrix; //邻接矩阵表示图 3.2主要的实现思路： 用邻接矩阵的方法表示各城市直接路线的图，之后用Floyd算法求解两点直接的最短距离，并用递归的方法求出途经的城市。 主要源程序代码： #include 单元练习9 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （√）（1）二分查找法要求待查表的关键字值必须有序。 （ㄨ）（2）对有序表而言采用二分查找总比采用顺序查找法速度快。 （ㄨ）（3）在二叉排序树中，根结点的值都小于孩子结点的值。 （√）（4）散列存储法的基本思想是由关键字的值决定数据的存储地址。 （√）（5）哈希表是一种将关键字转换为存储地址的存储方法。 （ㄨ）（6）选择好的哈希函数就可以避免冲突的发生。 （ㄨ）（7）在有序的顺序表和有序的链表上，均可以采用二分查找来提高查找速度。 （√）（8）采用分块查找，既能实现线性表所希望的查找速度，又能适应动态变化的需要。 （√）（9）哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。 （ㄨ）（10）在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。 二．填空题 （1）顺序查找法，表中元素可以任意存放。 （2）在分块查找方法中，首先查找索引，然后再查找相应的块。 （3）顺序查找、二分查找、分块查找都属于静态查找。 （4）静态查找表所含元素个数在查找阶段是固定不变的。 （5）对于长度为n的线性表，若进行顺序查找，则时间复杂度为 O（n）。 （6）对于长度为n的线性表，若采用二分查找，则时间复杂度为： O（log2n）。 （7）理想情况下，在散列表中查找一个元素的时间复杂度为： O（1）。 （8）在关键字序列（7，10，12，18，28，36，45，92）中，用二分查找法查找关键字92，要比较 4 次才找到。 （9）设有100个元素，用二分查找时，最大的比较次数是 7 次。 （10）对二叉排序树进行查找的方法是用待查的值与根结点的键值进行比较，若比根结点小，则继续在左子树中查找。 （11）二叉排序树是一种动态查找表。 （12）哈希表是按散列存储方式构造的存储结构 （13）哈希法既是一种存储方法，又是一种查找方法。 （14）散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。（15）设散列函数H和键值k1，k2，若k1≠k2，且H（k1）=H（k2），则称这种现象为冲突。（16）处理冲突的两类主要方法是开放定址法和拉链法（或链地址法）。 （17）散列表（或散列）查找法的平均查找长度与元素个数n无关。 （18）在哈希函数H(key)=key % P中，P一般应取质数。 （19）在查找过程中有插入元素或删除元素操作的，称为动态查找。 （20）各结点左右子树深度之差的绝对值至多为 1 的二叉树称谓平衡二叉树。操作系统习题答案(中国铁道出版社_刘振鹏_李亚平_王煜_张明) (2)
数据结构实验五矩阵的压缩存储与运算学习资料
最新考研计算机数据结构模拟试题及答案(五)
数据结构实验五-查找与排序的实现
中国铁道出版社数据结构(第二版)单元3练习参考答案
数据结构实验五图子系统
数据结构复习模拟题5
中国铁道出版社数据结构(第二版)单元8练习参考答案
数据结构实验报告5(电大)
数据结构实验五
操作系统 第三版 中国铁路出版社
数据结构实验——查找算法的实现
数据结构模拟试题及答案
数据结构实验五A
中国铁道出版社数据结构(第二版)单元4练习参考答案
数据结构模拟试题1
数据结构-实验五-图
中国铁道出版社数据结构(第二版)单元9练习参考答案
- 《C语言程序设计实验指导与习题集》练习题的参考答案(中国铁道出版社)期末测试题参考答案
- 中国铁道出版社数据结构(第二版)单元8练习参考答案
- (完整版)《Android移动应用基础教程》铁道出版社课后习题(附答案)
- 《Android移动应用基础教程》中国铁道出版社课后习题(附答案)
- 离散数学习题解答(铁道邵学才)
- 中国铁道出版社数据结构(第二版)单元3练习参考答案
- 操作系统习题答案(中国铁道出版社,刘振鹏,李亚平,王煜,张明)
- 中国铁道出版社数据结构(第二版)单元9练习参考答案
- 《android移动应用基础教程》中国铁道出版社课后习题附答案
- 大学计算机基础 铁道出版社 2015年第1版 第7章 习题答案
- 教材习题答案_铁道出版社
- 中国铁道出版社数据结构(第二版)单元3练习参考答案
- 中国铁道出版社2019年招聘应届高校毕业生试题及答案解析 .doc
- 土力学课后习题答案(中国铁道出版社)
- 《Android移动应用基础教程》中国铁道出版社课后习题(附答案).pdf
- 大学计算机基础 铁道出版社 2015年第1版 第1章 习题答案
- Android移动应用基础教程中国铁道出版社课后习题附答案
- 土力学课后习题答案(中国铁道出版社) - 副本
- 高速铁路常识复习考试题库
- Android移动应用基础教程铁道出版社课后习题附答案图文稿