数据结构知识要点

数据结构知识要点

知识点一

一、填空题

1、数据的物理结构主要包括顺序存储结构和链式存储结构两种情况。

2、设一棵完全二叉树中有500个结点，则该二叉树的深度为—9—;若用二叉链表作为该完全

二叉树的存储结构，则共有501个空指针域。

3、设输入序列为1、2、3,则经过栈的作用后可以得到5种不同的输出序列。

4、设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i

的—出度,第i列上所有元素之和等于顶点i的—入度。

5、设哈夫曼树中共有n个结点，则该哈夫曼树中有__0__个度数为1的结点。

6、设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d,则e和d的关系为e=d____。

7,—中序——遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序)。

8、设查找表中有100个元素，如果用二分法查找方法查找数据元素X,则最多需要比较7—次

就可以断定数据元素X是否在查找表中。

9、不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为0(1)

10、设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点

的双亲结点编号为i/2,右孩子结点的编号为___2i+l«

11、设一组初始记录关键字为(72,73,71,23,94,16,5),则以记录关键字72为基准的一趟快

速排序结果为_(5,16,71,23,72,94,73)一。

12、设有向图G中有向边的集合E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>},则该图的一种

拓扑序列为(1,4,3,2)。

13、下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。

structrecord{intkey;intothers;);

inthashsqsearch(structrecordhashtable[],intk)

(

inti,j;j=i=k%p;

while(hashtablehl.kev!=k&&hashtableliI.flag!=0)Ii=(i+1)%m;if(i==j)return(-l);}

if(hashtable」].key=k)retum(j);elseretum(-l);

14.下列算法实现在二叉排序树上查找关键值k,请在下划线处填上正确的语句。

typedefstructnode{intkey;structnode*lchild;structnode*rchiId;}bitree;

bitree*bstsearch(bitree*t,intk)

(

if(t==0)retum(0);elsewhile(t!=0)

if(t->key==k)(return(t));elseif(t->key>k)t=t->lchild;

else(t=t->rchild);

)

二、选择题

1.设某数据结构的二元组形式表示为A=(D,R),D={01,02,03,04,05,06,07,08,09),

R={r),r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>},

则数据结构人是()。

(A)线性结构(B)树型结构(C)物理结构(D)图型结构

2.下面程序的时间复杂为()

for(i=l,s=0；i<=n；i++){t=l；for(j=l；j<=i；j++)t=t*j；s=s+t；}

(A)0(n)(B)0(n2)(00(n3)(D)0(n4)

3.设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列为(A

(A)q=p->next；p->data=q->data；p->next=q->next；free(q)；

(B)q=p->next；q->data=p->data；p->next=q->next；free(q)；

(C)q=p->next；p->next=q->next；free(q)；

(D)q=p->next；p->data=q->data；free(q)；

4.设有n个待排序的记录关键字，则在堆排序中需要()个辅助记录单元。

2

(A)1(B)n(C)nlog2n(D)n

5.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记录的一

趟快速排序结束后的结果为()。

伍uX

-10,15,14,18,20,36,40,21

IX

(B/10,15,14,18,20,40,36,21

(C

10,15,14,20,18,40,36,21

(DIX

/15,10,14,18,20,36,40,21

6.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为()。

2

(A)0(1)(B)0(log2n)(C)(D)0(n)

7.设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为()。

(A)n,e(B)e,n(C)2n,e(D)n,2e

8.设某强连通图中有n个顶点，则该强连通图中至少有()条边。

(A)n(n-l)(B)n+1(C)n(D)n(n+l)

9.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，

则用下列()方法可以达到此目的。

(A)快速排序(B)堆排序(C)归并排序(D)插入排序

10.下列四种排序中()的空间复杂度最大。

(A)插入排序(B)冒泡排序(C)堆排序(D)归并排序

参考答案：

l.B2.B3.A4.A5.A

6.B7.D8.C9.B10.D

IL设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s

指向将要入队列的结点X,则入队列的操作序列为(C)o

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

A、0(n+e)B、0(n2)C、0(ne)D、0(n3)

13.设某哈夫曼树中有199个结点，则该哈夫曼树中有(B)个叶子结点。

A、99B、100C、101D、102

14.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为(D)。

2

A、0(n)B、0(n)C、OCnlogm)D^0(log2n)

15.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为(B)o

A、第i行非0元素的个数之和B、第i列非0元素的个数之和

C、第i行。元素的个数之和D、第i列0元素的个数之和

填空题：

1.for(i=Lt=l,s=0；i<=n；i++){t=t*i；s=s+t；}的时间复杂度为(0(n))o

2.设指针变量p指向单链表中结点A,指针变量s指向被插入的新结点X,则进行插入操作的语句序列

为(s->next=p->next;p->next=s)(设结点的指针域为next)。

3.设有向图G的二元组形式表示为G=(D,R),D={1,2,3,4,5|,R={r),r={<l,2>,<2,4>,<4,5>,

<1,3>,<3,2>,<3,5>},则给出该图的一种拓扑排序序列((1,3,2,4,5))。

4.设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是(n-l)o

5.设二叉树中度数为0的结点数为50,度数为1的结点数为30,则该二叉树中总共有(129)个结点

数。

6.设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为(F==R)。

7.设二叉树中结点的两个指针域分别为Ichild和rchild,则判断指针变量p所指向的结点为叶子结点

的条件是(p->lchild==0&&p->rchild-0)o

8.简单选择排序和直接插入排序算法的平均时间复杂度为(0(/))。

四、算法设计题

1.设计在顺序有序表中实现二分查找的算法。

参考答案：

structrecord{intkey;intothers;};

intbisearchfstructrecordr[],intk)

(

intlow=Ozmidzhigh=n-l;

while(low<=high)

mid=(low+high)/2;

if(r[mid].key==k)return(mid+l);elseif(r[mid].key>k)high=mid-l;elselow=mid+l;

)

return(O);

)

2、设计判断二叉树是否为二叉排序树的算法。

参考答案：

intminnum=-32768,flag=l;

typedefstructnode{intkey;structnode*lchild/*rchild;}bitree;

voidinorder(bitree*bt)

(

if(bt!=0){inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);}

)

3.在链式存储结构上设计直接插入排序算法

voidstraightinsertsort(lklist*&head)

(

Iklist*s/p/q;intt;

if(head==011head->next==O)return;

elsefor(q=head/p=head->next;p!=0;p=q->next)

(

for(s=head;s!=q->next;s=s->next)if(s->data>p->data)break;

if(s==q->next)q=p;

else{q->next=p->next;p->next=s->next;s->next=p;t=p->data;p->data=s->data;s->data=t;}

)

)

快速排序算法的空间复杂度平均情况下为(最坏的情况下为(

9.0(nlog2n)),0(n)

10.散列表中解决冲突的两种方法是(开放定址法)和(链地址法)。

三、计算题

1.已知待散列的线性表为(36,15,40,63,22),散列用的一维地址空间为假定选用的散列

函数是H(K)=Kmod7,若发生冲突采用线性探查法处理，试：

(1)计算出每一个元素的散列地址并在下图中填写出散列表：

'0123456

(2)求出在查找每一个元素概率相等情况下的平均查找长度。

参考答案：

H(36)=36mod7=1;H：(22)=(1+1)mod7=2;….冲突

.冲突

H(15)=15mod7=1;…H2(22)=(2+l)mod7=3;

H,(15)=(l+1)mod7=2;

H(40)=40mod7=5;

H(63)=63mod7=0;

H(22)=22mod7=1;.…冲突

(1)0123456

6336152240

(2)ASL=(1+2+1+1+3)5=1.6

2.已知序列(10,18,4,3,6,12,1,9,18,8)请用快速排序写出每一趟排序的结果。

答：(8,9,4,3,6,1),10,(12,骂18)

(1,6,4,3),8,⑼,10,12,(西18)

1,(3,4,6),8,9,10,12,匈18)

13(4,6),8,9,10,12,骂18

1,3,4,6,8,9,10,12,丝,18

3、设计在单链表中删除值相同的多余结点的算法。

答：

lypedefintdatatype;

typedefstructnode{datatypedata;structnode*next;}lklist;

voiddelredundant(lklist*&head)

{

Iklist*p,*q,*s;

fbr(p=head;p!=0;p=p->next)

(

ibr(q=p->next,s=q;q!=0;)

if(q->data==p->data){s->next=q->next;free(q);q=s->next;)

else{s=q,q=q->next;}

)

)

4、设计求结点在二叉排序树中层次的算法。

答：

intlev=0;

typedefstructnode{intkey;structnode*lchild,*rchild;)bilree;

voidlevel(bitree*bt,intx)

{

if(bt!=O)

{lev++;if(bl->key==x)return;elseif(bt->key>x)level(bt->lchild,x);elselevel(bt->rchild,x)；)

知识点二

1.在数据结构中，从逻辑上可以把数据结构分为线性结构和非线性结构

2.在数据结构中，与所使用的计算机无关的是数据的逻辑结构。

3.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序不发生

改变

4.在下述论述中，只有一个结点的二叉树的度为0;深度为K的顺序二叉树的结点

个数小于或等于深度相同的满二叉树。

5.某二叉树结点的中序序列为ABCDEFG,后序序列为BDCAFGE,则其左子树中结点

数目为：4

6.顺序查找法适合于存储结构为顺序存储或链式存储的线性表。

7.采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为

0(log2n)

8.线性表是具有n个数据元素的有限序列。

9.若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算

法的时间复杂度为0(n)

10.线性表(al,a2,…，an)以链式方式存储,访问第i位置元素的时间复杂度为

O(n)

11.允许对队列进行的操作有删除队头元素

12.若串S=­software?,其子串的数目是37

13.一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是dceab

14.从队列中删除第i个元素不是队列的基本运算？

15.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间

复杂度是0(n)

16.与单链表相比,双链表的优点之一是顺序访问相邻结点更灵活

17.在长度为n的顺序表的第i个位置上插入一个元素(1WiWn+1),元素的移

动次数为:n-i+1

18.一个队列的入队序列是1,2,3,4,则队列的输出序列是1,2,3,4

19.设有两个串p和q,求q在p中首次出现的位置的运算称为模式匹配

20假设该数组的内存起始位置为200,average[15]的内存地址是260

21.设二维数组A[1…m,1…n]按行存储在数组B中，则二维数组元素A[i,j]

在一维数组B中的下标为n*(i-l)+j

22.有一个100X90的稀疏矩阵,非0元素有10,设每个整型数占2个字节,则用

三元组表示该矩阵时,所需的字节数是66

23.数组A[0…4,-1…-3,5…7]中含有的元素个数是55

24.对矩阵进行压缩存储是为了减少存储空间

25.设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，al,1为第

一个元素,其存储地址为1,每个元素占1个地址空间，则a8,5的地址为33

26.稀疏矩阵一般的压缩存储方式有两种，即三元组和十字链表

27.树最适合用来表示元素之间具有分支层次关系的数据

28.在以下的叙述中，二维数组是其数据元素为线性表的线性表

29.链表不具备的特点是可随机访问任一结点

30.需要分配较大空间，插入和删除不需要移动元素的线性表,其存储结构是静态

链表

31算法的5个重要特性是有穷性、确定性、可行性、输入和

输出。

32.在顺序表中插入或删除一个数据元素，需要平均移动n个数据元素，移动

数据元素的个数与位置有关。

33.在双链表中，每个结点有两个指针域，一个指向前驱节点，另一个指向

后继结点。

34.带头结点的循环链表L中只有一个元素结点的条件是L->next->

next=Lo

35.一个字符串中任意个连续字符构成的部分称为该串的子串。

36.在有n个结点的二叉链表中，空链域的个数为._n+l__0

37.顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过

指针表示元素之间的关系的。

38.子串"str"在主串"datastructure”中的位置是5。

39.稀疏矩阵一般的压缩存储方法有两种，即三元组表和十字链表。

40.线索二叉树的左线索指向其遍历序列中的前驱，右线索指向其遍历序列

中的后继。

41.在各种查找方法中,平均查找长度与结点个数n无关的查找方法是散列查

找法。

42.索引是为了加快检索速度而引进的一种数据结构。一个索引隶属于某个数据

记录集，它由若干索引项组成，索引项的结构为关