数据结构复习重点.docx
《数据结构复习重点.docx》由会员分享，可在线阅读，更多相关《数据结构复习重点.docx（10页珍藏版）》请在冰点文库上搜索。
数据结构复习重点
复习重点
一、简答题
1、数据结构涉及哪几个方面？
答：
数据结构包括数据的逻辑结构，数据存储结构以及数据集合上的一组操作。
2、算法和程序的区别是什么呢？
答：
算法的含义与程序十分相似，但又有区别。
一个程序不一定满足有穷性。
另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。
算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。
一个算法若用程序设计语言来描述，则它就是一个程序。
3、试比较顺序存储结构和链式存储结构的优缺点？
顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，要求内存中存储单元的地址必须是连续的。
优点：
一般情况下，存储密度大，存储空间利用率高。
缺点：
（1）在做插入和删除操作时，需移动大量元素；
（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；
（3）表的容量难以扩充。
链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。
优点：
插入和删除元素时很方便，使用灵活。
缺点：
存储密度小，存储空间利用率低。
4、数据结构的存储方式有哪几种？
数据的存储结构可用以下四种基本存储方法得到：
（1）顺序存储方法
（2）链接存储方法
（3）索引存储方法
（4）散列存储方法
四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。
同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。
选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。
5、交换排序的基本思想是什么？
交换排序的主要操作是交换，其主要思想是：
在待排序列中选两个记录，将它们的关键码相比较，如果反序（即排列顺序与排序后的次序正好相反），则交换它们的存储位置。
直到任何两个记录的排序码都满足排序要求为止。
6、选择排序的基本思想是什么？
选择排序的主要操作是选择，其主要思想是：
每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中，直到已排序文件记录个数等于初始待排序文件的记录个数为止。
7、已知一棵二叉树的前序遍历的结果为ABCDEF，中序遍历的结果为CBAEDF，试画出此二叉树。
二、是非题
1、数据结构概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。
（T）
2、线性表简称为“顺序表”。
（F）
3、从单链表的任一结点出发，都能访问到所有结点。
（F）
4、在有序的顺序表和有序的链表上，均可使用折半查找来提高查找效率。
（F）
5、若二叉树的中序遍历序列与后序遍历序列相同，则该二叉树一定是任何结点都没有右子树。
（T）
三、单选题
1、对于顺序存储的有序表{5，12，20，26，37，42，46，50，64}，若采用折半查找，则查找元素26的比较次数为（C）。
A、2B、3C、4D、5
2、若根据查找表（23，44，36，48，52，73，64，58）建立哈希表，采用h（K）=K%7计算哈希地址，则哈希地址等于3的元素个数为（B）。
A、1B、2C、3D、4
3、若一个元素序列基本有序，则选用（A）方法较快。
A、直接插入排序B、简单选择排序C、堆排序D、快速排序
4、在一个长度为n的顺序表中向第i个元素（0A、n-iB、n-i+1C、n-i-1D、i
5、若将一个10×10阶的对称矩阵压缩存储到一个一维数组中，则该一维数组的大小应该是（A）。
A、55B、56C、45D、46
6、对一组数据（86，48，26，15，23）排序，数据的排列次序在排序过程中的变化为：
①8648261523②1548268623
③1523268648④1523264886
这个排序过程采用的排序方法是（B）。
A、冒泡B、选择C、快速D、插入
7、在数据结构中，从逻辑上可以把数据结构分为（C）。
A．动态结构和静态结构B.紧凑结构和非紧凑结构
C.线性结构和非线性结构D.内部结构和外部结构
8、根据堆定义，下面的4个序列中，（C）是堆。
A、75，65，30，15，25，45，20，10
B、75，65，45，10，30，25，20，15
C、75，45，65，30，15，25，20，10
D、75，45，65，10，25，30，20，15
四、计算题
1.写出下面二叉树的前序、中序和后序遍历序列。
前序：
ABDGCEHIF
中序：
BGDAHEICF
后序：
GDBHIEFCA
4.给出排序码47，28，32，15，94，33，14，16，试分别给出该序列在SHELL排序下，当D1=4，D2=2，D3=1时的序列变化情况及元素比较情况。
D1=44728141594333216
D2=21415321647289432
D3=11415162832334794
5.按冒泡排序方法，写出排序码35，65，16，27，26，18在第一，第二趟的排序序列。
第一趟：
351627261865
第二趟：
162726183565
五、程序设计题
1.编写计算二叉树中叶子结点数目的函数。
intf（bintnode*b）
{
if（b==NULL）
return（0）;
else
return（f（b->lchild）+f（b->rchild）+1）;
}
2.求二叉树的高（深）度depth（t）
intdepth（bintnodet）
{inth,lh,rh;
if（t==NULL）h=0;
else{lh=depth（t->lchild）;
rh=depth（t->rchild）;
if（lh>=rh）h=lh+1;
elseh=rh+1;
}
returnh;
}
3.设有一个给定顺序表a，试编写一个Ｃ函数，它将顺序表a分裂为a１和a２两个顺序表，a1由原表a中所有大于等于Ｘ的元素组成，a2由原表a中所有小于Ｘ的元素组成。
voidsprit（seqlista,seqlist*a1,seqlist*a2,intn,intx）
{
inti,j,k;
i=0;j=0;k=0;
while（i{
if（a.a[i]>=x）a1->a[j++]=a.a[i];
else
a2->a[k++]=a.a[i];
i++;
}
}
4.已知顺序表la和lb中的数据元素依值非递减有序排列，现将la和lb归并为一个新的的顺序表lc，且lc中的数据元素也依值非递减有序排列。
voidMergeList（seqlistla,seqlistlb,seqlist*lc）
{/*合并表有序表la和lb到表lc中，使得lc依然有序*/
inti,j,k;
i=j=k=0;
while（iif（la.a[i]lc->a[k++]=la.a[i++];
elseif（la.a[i]>lb.a[j]）
lc->a[k++]=lb.a[j++];
else{/*la和lb中的当前元素相等时，同时移动指针*/
lc->a[k++]=lb.a[j++];i++;
}
while（ilc->a[k++]=la.a[i++];
while（jlc->a[k++]=lb.a[j++];
lc->size=k;
}
5.假设带头结点的单链表A、B是有序表，单链表的类型定义如下：
typedefstructnode
{
Datatypedata;
Structnode*next;
}Lnode;
编写算法，从有序表A中删除所有和有序表B中有相同值的结点。
voidLdel（Lnode*ha,Lnode*hb）
{
Lnode*p,*q,*r;
r=ha;
p=ha->next;
q=hb->next;
while（p&&q）
{
if（p->datadata）
{r=p;p=p->next;}
else
{
if（p->data==q->data）
{
r->next=p->next;free（p）;
p=r->next;
}
q=q->next;
}
}
}
6.已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。
设计一个删除表中所有值小于max但大于min的元素的算法。
delete（Lnode*head,intmax,intmin）
{
LinkList*p,*q;
q=head;p=head->next;
while（p）
if（p->data<=min||p->data>=max）
{q=p;p=p->next;}
else
{q->next=p->next;free（p）;p=q->next;}
}
升级会员 