算法与数据结构常见考题笔试题

常见的算法习题,填空题,基础知识汇总

二、填空题：

1、《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和___运算___________。

2、数据结构算法中，通常用时间复杂度和____空间复杂度______________两种方法衡量其效率。

3、一个算法一该具有__有穷性____,__确定性____,__可行性__,___输入___和_输出___这五种特性。

4、若频繁地对线性表进行插入与删除操作，该线性表应采用_链式___________存储结构。

5、在非空线性表中除第一个元素外，集合中每个数据元素只有一个_直接前驱______；除最后一个元素之外，集合中每个数据元素均只有一个___直接_后继_____。

6、线性表中的每个结点最多有__一个_直接___前驱和______一个直接___后继。

7、____循环__链表从任何一个结点出发，都能访问到所有结点。

8、链式存储结构中的结点包含__指针__________域，________数据_______域。

9、在双向链表中，每个结点含有两个指针域，一个指向___前驱__结点，另一个指向__后继______结点。

10、某带头结点的单链表的头指针head，判定该单链表非空的条件__head->next!=NULL____________。

11、在双向链表中，每个结点含有两个指针域，一个指向前驱结点，另一个指向 后续结点。

12、已知指针p指向单链表中某个结点，则语句p->next=p->next->next的作用__删除p 的后继结点_。

13、已知在结点个数大于1的单链表中，指针p指向某个结点，则下列程序段结束时，指针q指向*p的____后继_________结点。

q=p;

while(q->next!=p)

q=q->next;

14、若要在单链表结点*P后插入一结点*S，执行的语句_p->next=s->next;p->next=s_____。

15、线性表的链式存储结构地址空间可以_不连续_，而向量存储必须是地址空间__连续____。

16、栈结构允许进行删除操作的一端为_栈顶__。

17、在栈的顺序实现中，栈顶指针top，栈为空条件__top=-1____________。

18、对于单链表形式的队列，其空队列的F指针和R指针都等于__头结点__________。

19、若数组s[0..n-1]为两个栈s1和s2的共用存储空间，仅当s[0..n-1]全满时，各栈才不能进行栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为s[0],s[n-1]__。

20、允许在线性表的一端插入,另一端进行删除操作的线性表称为_队列______。插入的一端为_对尾_____,删除的一端为_对头_____。

21、设数组A[m]为循环队列Q的存储空间，font为头指针，rear为尾指针，判定Q为空队

常见的算法习题,填空题,基础知识汇总

列的条件__ __________________。

22、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为___________。

23、已知循环队列的存储空间为数组data[21]，且头指针和尾指针分别为8和3，则该队列的当前长度__________。

24、一个串的任意个连续的字符组成的子序列称为该串的________，包含该子串的串称为________。

25、求串T在主串S中首次出现的位置的操作是________________。

26、在初始为空的队列中插入元素A,B,C,D以后，紧接着作了两次删除操作，此时的队尾元素是__________。

27、在长度为n的循环队列中，删除其节点为x的时间复杂度为_______________。

28、已知广义表L为空，其深度为___________。

29、已知一顺序存储的线性表，每个结点占用k个单元，若第一个结点的地址为DA1，则第i个结点的地址为______________。

30、设一行优先顺序存储的数组A[5][6]，A[0][0]的地址为1100，且每个元素占2个存储单元，则A[2][3]的地址为_____________。

31、设有二维数组A[9][19]，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为______________，按列优顺序存储，元素A[6,6]的存储地址为______________。

32、在进行直接插入排序时, 其数据比较次数与数据的初始排列________关；而在进行直接选择排序时，其数据比较次数与数据的初始排列__________关。

33、假设以行为优先存储的三维数组A[5][6][7]，A[0][0][0]的地址为1100，每个元素占两个存储单元，则A[4][3][2]的地址为_______。

34、设二维数组A[m][n]按列优先存储，每个元素占1个存储单元，元素A00的存储地址loc(A00)，则Aij的存储地址loc(Aij)=____________________。

35、稀疏矩阵一般采用__________方法进行压缩存储。

36、稀疏矩阵可用_________进行压缩存储，存储时需存储非零元的________、________、________。

37、若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为__________。

38、若一个n 阶矩阵A中的元素满足：Aij=Aji (0<=I ,j<=n-1)则称A为____________矩阵；若主对角线上方(或下方)的所有元素均为零时，称该矩阵为______________。

39、对于上三角形和下三角形矩阵，分别以按行存储和按列存储原则进行压缩存储到数组M[k]中，若矩阵中非0元素为Aij，则k对应为________和__________。

40、设有一上三角形矩阵A[5][5]按行压缩存储到数组B中，B[0]的地址为100，每个元素占2个单元，则A[3][2]地址为____________。

常见的算法习题,填空题,基础知识汇总

41、广义表（A,(a,b),d,e,((i,j),k)）,则广义表的长度为___________，深度为___________。

42、已知广义表A=((a,b,c),(d,e,f)),则运算head(head (tail（A）)))=___ ________。

43、已知广义表ls =(a,(b,c,d),e),运用head和tail函数取出ls中的原子b的运算是_____。

44、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个___________,且存在一条从根到该结点的_______________。

45、度数为0的结点，即没有子树的结点叫作__________结点或_________结点。同一个结点的儿子结点之间互称为___________结点。

46、假定一棵树的广义表为A(B(e),C(F(h,i,j),g),D),则该树的度为___________，树的深度为_________，终端结点为______，单分支结点为，双分支结点个数为 _______，三分支结点为_______，C结点的双亲结点是______，孩子结点是______。

48、完全二叉树、满二叉树、线索二叉树和二叉排序树这四个名词术语中，与数据的存储结构有关系的是_____________。

47、有三个结点的二叉树，最多有________种形状。

48、每一趟排序时从排好序的元素中挑出一个值最小的元素与这些未排小序的元素的第一个元素交换位置，这种排序方法成为_____________排序法。

49、高度为k的二叉树具有的结点数目，最少为_____,最多为_____。

50、对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0=_______。

51、在含100个结点的完全二叉树，叶子结点的个数为_______。

52、将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫_____。

53、若一棵满二叉树含有121个结点，则该树的深度为_________。

54、一个具有767个结点的完全二叉树，其叶子结点个数为________。

55、深度为90的满二叉树，第11层有________个结点。

56、有100个结点的完全二叉树，深度为________。

57、设一棵二叉树中度为2的结点10个，则该树的叶子个数为________。

58、若待散列的序列为(18,25,63,50,42,32,9)，散列函数为H(key)=key MOD 9，与18发生冲突的元素有_____________个。

59、含有3个2度结点和4个叶结点的二叉树可含__________个1度结点。

60、一棵具有５层满二叉树中节点总数为___________。

61、一棵含有16个结点的完全二叉树，对他按层编号，对于编号为7的结点，他的双亲结点及左右结点编号为______、______、_______。

62、深度为k(设根的层数为1)的完全二叉树至少有_______个结点, 至多有_______个结点。

63、若要对某二叉排序树进行遍历，保证输出所有结点的值序列按增序排列，应对该二叉排序树采用________遍历法。

64、在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素24，需要进行______________次元素之间的比较。

65、设有10个值，构成哈夫曼树，则该哈夫曼树共有______个结点。

66、从树中一个结点到另一个结点之间的分支构成这两个结点之间的____________。

常见的算法习题,填空题,基础知识汇总

67、关键字自身作为哈希函数，即H（k）=k，也可自身加上一个常数作为哈希函数，即H(k)=k+C这种构造哈希函数的方式叫____________。

68、对于一个图G，若边集合E（G）为无向边的集合，则称该图为____________。

69、对于一个图G，若边集合E（G）为有向边的集合，则称该图为____________。

70、对于有向图，顶点的度分为入度和出度，以该顶点为终点的边数目叫________；以该顶点为起点的边数目叫_________。

71、一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个______________。

72、有一个n个顶点的有向完全图的弧数_____________。

73、在无向图中，若从顶点A到顶点B存在_________，则称A与B之间是连通的。

74、在一个无向图中，所有顶点的度数之和等于所有边数的___________倍。

75、一个连通图的生成树是该图的____________连通子图。若这个连通图有n个顶点, 则它的生成树有__________条边。

76、无向图的邻接矩阵是一个_____________矩阵。

77、如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_____ _______。

78、若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的____________遍历。

79、若图的邻接矩阵是对称矩阵，则该图一定是________________。

80、从如图所示的临接矩阵可以看出，该图共有______个顶点。如果是有向图，该图共有______条弧；如果是无向图，则共有________条边。

81、如果从一个顶点出发又回到该顶点，则此路径叫做___________。

82、一个具有个n顶点的无向图中，要连通全部顶点至少需要________条边。 A B C 011 AB 001 B 83、给定序列{100, 86, 48, 73, 35, 39, 42, 57, 66, 21}, 按堆结构的定义, 则它一 010 C定_________堆。

84、从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于或等于所选元素，而此时所选元素处在排序的最终位置。这种排序法称为_____________排序法。

85、折半搜索只适合用于___________________。

86、结点关键字转换为该结点存储单元地址的函数H称为_____________或叫__________。

87、在索引查找中，首先查找________，然后查找相应的_________，整个索引查找的平均查找长度等于查找索引表的平均长度与查找相应子表的平均查找长度的_______。

二、填空题答案：

1、运算

2、空间复杂度。

3、有穷性，确定性，可行性，输入，输出

4、链表

5、直接前驱，直接后继

6、1个直接，1个直接

7、循环

常见的算法习题,填空题,基础知识汇总

8、指针，数据

9、前驱，后继

10、head->next!=Null

11、前驱，后继

12、删除p 的后继结点

13、后继

14、s->next=p->next;p->next=s

15、不连续，连续

16、栈顶

17、top=-1

18、头结点

19、s[0]，s[n-1]

20、队列，队尾队头

21、Q->font=Q->rear

22、(R-F)%n

23、17

24、子串，主串

25、Index(S,T,pos)

26、D

27、O(n)

28、1

29、DA1+(i-1)*k

30、1100+（6*2+3）*2=1130

31、100+（19*6+6）*2=340，100+（9*6+……）*2=220

32、有，无

33、1482

34、loc（a00）+(j*m+i)*1

35、三元组

36、三元组，行号，列号，值

37、三对角矩阵

38、上（下）三角矩阵

39、i*（i-1）/2+j-1? ?(i≥j) ，j*(j-1)/2+i-1 (i<j) 40、108

41、5，3

42、d

43、head(head(tail(s)))

44、前驱，路径

45、叶子，终端，兄弟

46、3；3；e,h,I,j,g；C； A,F ； A；F,g

48、线索

47、5

48、选择

49、k，2k-1

50、n1+n2

常见的算法习题,填空题,基础知识汇总

51、50

52、排序

53、7

54、384

55、1024

56、7

57、11

58、2

59、1（0）

60、31

61、3，14，15

62、2k-1，2k-1

63、中序

64、4

65、19

66、路径

67、直接定址法

68、无向图

69、有向图

70、入度，出度

71、对称矩阵

72、n(n-1)

73、路径

74、2

75、极小（ 最小），n-1

76、对称

77、连通

78、层次

79、无向图

80、3，4，3

81、环/回路

82、n-1

83、大根堆

84、快速

85、有序表

86、哈希函数，散列函数

87、索引表，子表，和

本文来源：https://www.bwwdw.com/article/zu61.html