好风光好感动1、线性表的逻辑顺序与物理顺序总是⼀致的。( x )2、线性表的顺序存储表⽰优于链式存储表⽰。( X )
3、线性表若采⽤链式存储表⽰时所有结点之间的存储单元地址可连续可不连续。( v )4、⼆维数组是其数组元素为线性表的线性表。( v )
5、每种数据结构都应具备三种基本运算：插⼊、删除和搜索。( x )
6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储⽅式和数据的运算三个⽅⾯。( v )
7、线性表中的每个结点最多只有⼀个前驱和⼀个后继。（x ）
8、线性的数据结构可以顺序存储，也可以链接存储。⾮线性的数据结构只能链接存储。（x ）9、栈和队列逻辑上都是线性表。（v ）
10、单链表从任何⼀个结点出发，都能访问到所有结点（v ）
11、删除⼆叉排序树中⼀个结点，再重新插⼊上去，⼀定能得到原来的⼆叉排序树。（x ）12、快速排序是排序算法中最快的⼀种。（x ）13、多维数组是向量的推⼴。（x）
14、⼀般树和⼆叉树的结点数⽬都可以为0。（v）15、直接选择排序是⼀种不稳定的排序⽅法。（x ）
16、98、对⼀个堆按层次遍历，不⼀定能得到⼀个有序序列。（v ）
17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（18、折半搜索只适⽤与有序表，包括有序的顺序表和有序的链表。（x ）19、堆栈在数据中的存储原则是先进先出。（x ）20、队列在数据中的存储原则是后进先出。（x ）
21、⽤相邻矩阵表⽰图所⽤的存储空间⼤⼩与图的边数成正⽐。（x ）22、哈夫曼树⼀定是满⼆叉树。（x ）23、程序是⽤计算机语⾔表述的算法。（v）
24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（v ）25、⽤⼀组地址连续的存储单元存放的元素⼀定构成线性表。（v ）26、堆栈、队列和数组的逻辑结构都是线性表结构。（v ）27、给定⼀组权值，可以唯⼀构造出⼀棵哈夫曼树。（x ）
28、只有在初始数据为逆序时，冒泡排序所执⾏的⽐较次数最多。（v ）29、希尔排序在较率上较直接接⼊排序有较⼤的改进。但是不稳定的。（v ）30、在平均情况下，快速排序法最快，堆积排序法最节省空间。（v ）31、快速排序法是⼀种稳定性排序法。（x ）32、算法⼀定要有输⼊和输出。（x ）
33、算法分析的⽬的旨在分析算法的效率以求改进算法。（v ）
x ）34、⾮空线性表中任意⼀个数据元素都有且仅有⼀个直接后继元素。（x ）
35、数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。（x ）36、若频繁地对线性表进⾏插⼊和删除操作，该线性表采⽤顺序存储结构更合适。（x ）
37、若线性表采⽤顺序存储结构，每个数据元素占⽤4个存储单元，第12个数据元素的存储地址为144，则第1个数据元素的存储地址是101。（x ）
38、若长度为n的线性表采⽤顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。（x ）39、符号p->next出现在表达式中表⽰p所指的那个结点的内容。（x ）40、要将指针p移到它所指的结点的下⼀个结点是执⾏语句p←p->next。（x ）41、若某堆栈的输⼊序列为1,2,3,4，则4,3,1,2不可能是堆栈的输出序列之⼀。（v ）42、线性链表中各个链结点之间的地址不⼀定要连续。（v ）43、程序就是算法，但算法不⼀定是程序。（v ）
44、线性表只能采⽤顺序存储结构或者链式存储结构。（v ）
45、线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的。（v ）46、除插⼊和删除操作外，数组的主要操作还有存取、修改、检索和排序等。（x ）47、稀疏矩阵中0元素的分布有规律，因此可以采⽤三元组⽅法进⾏压缩存储。（v ）48、不管堆栈采⽤何种存储结构，只要堆栈不空，可以任意删除⼀个元素。（v ）49、确定串Ｔ在串Ｓ中⾸次出现的位置的操作称为串的模式匹配。（v）50、深度为h的⾮空⼆叉树的第i层最多有2i-1 个结点。（x ）51、满⼆叉树也是完全⼆叉树。（v ）
52、已知⼀棵⼆叉树的前序序列和后序序列可以唯⼀地构造出该⼆叉树。（x ）53、⾮空⼆叉排序树的任意⼀棵⼦树也是⼆叉排序树。（v ）
54、对⼀棵⼆叉排序树进⾏前序遍历⼀定可以得到⼀个按值有序的序列。（x ）55、⼀个⼴义表的深度是指该⼴义表展开后所含括号的层数。（v ）
56、散列表的查找效率主要取决于所选择的散列函数与处理冲突的⽅法。（v ）57、序列初始为逆序时，冒泡排序法所进⾏的元素之间的⽐较次数最多。（v ）58、已知指针P指向键表L中的某结点，执⾏语句P=P-〉next不会删除该链表中的结点。（v ）
59、在链队列中，即使不设置尾指针也能进⾏⼊队操作。（v ）
60、如果⼀个串中的所有字符均在另⼀串中出现，则说前者是后者的⼦串。（x ）
61、设与⼀棵树T所对应的⼆叉树为BT，则与T中的叶⼦结点所对应的BT中的结点也⼀定是叶⼦结点。（x ）62、若图G的最⼩⽣成树不唯⼀，则G的边数⼀定多于n-1，并且权值最⼩的边有多条（其中n为G 的顶点数）。（63、给出不同的输⼊序列建造⼆叉排序树，⼀定得到不同的⼆叉排序树。（v ）
64、由于希尔排序的最后⼀趟与直接插⼊排序过程相同，因此前者⼀定⽐后者花费的时间多。（x ）65、程序越短，程序运⾏的时间就越少。（x ）
66、采⽤循环链表作为存储结构的队列就是循环队列。（x ）67、堆栈是⼀种插⼊和删除操作在表的⼀端进⾏的线性表。（v ）
v ）68、⼀个任意串是其⾃⾝的⼦串。（v ）69、哈夫曼树⼀定是完全⼆叉树。（x ）
70、带权连通图中某⼀顶点到图中另⼀定点的最短路径不⼀定唯⼀。（v ）71、折半查找⽅法可以⽤于按值有序的线性链表的查找。（x ）72、稀疏矩阵压缩存储后,必会失效掉随机存取功能。（x ）73、由⼀棵⼆叉树的前序序列和后序序列可以唯⼀确定它。（x ）74、在n个结点的元向图中,若边数在于n-1,则该图必是连通图。（x ）75、在完全⼆叉树中,若某结点元左孩⼦,则它必是叶结点。（v ）
76、若⼀个有向图的邻接矩阵中,对⾓线以下元素均为0,则该图的拓扑有序序列必定存在。（v ）77、树的带权路径长度最⼩的⼆叉树中必定没有度为1的结点。（v ）78、⼆叉树可以⽤0≤度≤2的有序树来表⽰。（x ）79、⼀组权值，可以唯⼀构造出⼀棵哈夫曼树。( x )
80、101，88，46，70，34，39，45，58，66，10）是堆；（v ）81、将⼀棵树转换成⼆叉树后，根结点没有左⼦树；（x ）82、⽤树的前序遍历和中序遍历可以导出树的后序遍历；（v ）
83、在⾮空线性链表中由p所指的结点后⾯插⼊⼀个由q所指的结点的过程是依次执⾏语句：q->next=p->next;p->next=q。（v）
84、⾮空双向循环链表中由q所指的结点后⾯插⼊⼀个由p指的结点的动作依次为：p->prior=q, p->next=q->next,q->next=p,q->prior->next←p。（x ）
85、删除⾮空链式存储结构的堆栈(设栈顶指针为top)的⼀个元素的过程是依次执⾏:p=top,top= p->next,free (p)。( v )86、哈希的查找⽆需进⾏关键字的⽐较。（v ）
87、⼀个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。（v ）
88、排序是计算机程序设计中的⼀种重要操作，它的功能是将⼀个数据元素（或记录）的任意序列，重新排列成⼀个按关键字有序的序列。（v ）
89、队列是⼀种可以在表头和表尾都能进⾏插⼊和删除操作的线性表。（x ）
90、在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不与表的个数有关，⽽与每⼀块中的元素个数有关。（x ）
91、对于有向图，顶点的度分为⼊度和出度，⼊度是以该顶点为终点的⼊边数⽬；出度是以该顶点为起点的出边数⽬，该顶点的度等于其⼊度和出度之和。（v ）
92、⽆向图的邻接矩阵是对称的有向图的邻接矩阵是不对称的。（x ）93、具有n个顶点的连通图的⽣成树具有n-1条边（v ）⼆、填空题：
1、《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和______运算________。2、数据结构算法中，通常⽤时间复杂度和__________________两种⽅法衡量其效率。3、⼀个算法⼀该具有______,______,____,______和____这五种特性。
4、若频繁地对线性表进⾏插⼊与删除操作，该线性表应采⽤____________存储结构。
5、在⾮空线性表中除第⼀个元素外，集合中每个数据元素只有⼀个_______；除最后⼀个元素之外，集合中每个数据元素均只有⼀个_________。
6、线性表中的每个结点最多有________前驱和____________后继。7、______链表从任何⼀个结点出发，都能访问到所有结点。
8、链式存储结构中的结点包含____________域，_______________域。
9、在双向链表中，每个结点含有两个指针域，⼀个指向______结点，另⼀个指向________结点。10、某带头结点的单链表的头指针head，判定该单链表⾮空的条件______________。
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，执⾏的语句_______________。
15、线性表的链式存储结构地址空间可以_________，⽽向量存储必须是地址空间___________。16、栈结构允许进⾏删除操作的⼀端为_____________。
17、在栈的顺序实现中，栈顶指针top，栈为空条件______________。
18、对于单链表形式的队列，其空队列的F指针和R指针都等于__________________。
19、若数组s[0..n-1]为两个栈s1和s2的共⽤存储空间，仅当s[0..n-1]全满时，各栈才不能进⾏栈操作，则为这两个栈分配空间的最佳⽅案是：s1和s2的栈顶指针的初值分别为_________。
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)，则A ij的存储地址loc(A ij)=____________________。35、稀疏矩阵⼀般采⽤__________⽅法进⾏压缩存储。
36、稀疏矩阵可⽤_________进⾏压缩存储，存储时需存储⾮零元的________、________、________。37、若矩阵中所有⾮零元素都集中在以主对⾓线为中⼼的带状区域中，区域外的值全为0，则称为__________。38、若⼀个n 阶矩阵A中的元素满⾜：A ij=A ji (0<=I ,j<=n-1)则称A为____________矩阵；若主对⾓线上⽅(或下⽅)的所有元素均为零时，称该矩阵为______________。
39、对于上三⾓形和下三⾓形矩阵，分别以按⾏存储和按列存储原则进⾏压缩存储到数组M[k]中，若矩阵中⾮0元素为A ij，则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 顶点的⽆向图中，要连通全部顶点⾄少需要________条边。 83、给定序列{100, 86, 48, 73, 35, 39, 42, 57,66, 21}, 按堆结构的定义, 则它⼀定_________堆。
84、从未排序序列中选择⼀个元素，该元素将当前参加排序的那些元素分成前后两个部分，前⼀部分中所有元素都⼩于等于所选元素，后⼀部分中所有元素都⼤于或等于所选元素，⽽此时所选元素处在排序的最终位置。这种排序法称为_____________排序法。
85、折半搜索只适合⽤于___________________。
86、结点关键字转换为该结点存储单元地址的函数H 称为_____________或叫__________。 87、在索引查找中，⾸先查找________，然后查找相应的_________，整个索引查找的平均查找长度A B CC
B A B =010100110
等于查找索引表的平均长度与查找相应⼦表的平均查找长度的_______。三、选择题：
（）1.数据结构通常是研究数据的及它们之间的联系。A存储和逻辑结构B存储和抽象
C理想和抽象D理想与逻辑
（）2.在堆栈中存取数据的原则是。A先进先出B后进先出C先进后出D随意进出
（）3.将⼀棵有100个结点的完全⼆叉树从上到下，从左到右依次对结点进⾏编号，根结点的编号为1，则编号为49的结点的左孩⼦的编号为______。
( )4.对于如图所⽰⼆叉树采⽤中根遍历，正确的遍历序列应为( )
（）5.设有100个元素，⽤折半查找法进⾏查找时，最⼤⽐较次数是_____ 。（）6.快速排序在_____情况下最易发挥其长处。A.被排序数据中含有多个相同排序码B.被排序数据已基本有序C.被排序数据完全⽆序
D.被排序数据中最⼤值和最⼩值相差悬殊
（）7.由两个栈共享⼀个向量空间的好处是______。
A减少存取时间,降低下溢发⽣的机率B节省存储空间,降低上溢发⽣的机率C减少存取时间,降低上溢发⽣的机率D节省存储空间,降低下溢发⽣的机率
（）8.某⼆叉树的前序和后序序列正好相反，则该⼆叉树⼀定是_____的⼆叉树A空或者只有⼀个结点B⾼度等于其结点数C任⼀结点⽆左孩⼦D任⼀结点⽆右孩⼦
（）9.设散列表长m=14,散列函数H（K）=K％11，已知表中已有4个结点：r(15)=4; r(38)=5; r(61)=6;r(84)=7，其他地址为空，如⽤⼆次探测再散列处理冲突，关键字为49的结点地址是________。A8 B3C5 D9
（）10.在含有n个项点有e条边的⽆向图的邻接矩阵中，零元素的个数为________。（）11.图的深度优先遍历类似于⼆叉树的_______。A.先序遍历B.中序遍历C.后序遍历D.层次遍历
（）12.设长度为n的链队列⽤单循环链表表⽰，若只设头指针，则⼊队操作的时间复杂度为_______。A. O(1)B. O(log2n)C. O(n)D. O(n2)
（）13.堆的形状是⼀棵_______。A.⼆叉排序树B.满⼆叉树
C.完全⼆叉树D.平衡⼆叉树
（）14.⼀个⽆向连连通图的⽣成树是含有该连通图的全部项点的_______。A.极⼩连通⼦图B.极⼩⼦图C.极⼤连通⼦图D.极⼤⼦图
（）15.⼀个序列中有10000个元素，若只想得到其中前10个最⼩元素，最好采⽤_______⽅法A.快速排序B.堆排序C.插⼊排序D.⼆路归并排序
（）16.设单链表中结点的结构为
typedef struct node { ElemType data；struct node * Link；} ListNode；
已知指针p所指结点不是尾结点，若在*p之后插⼊结点*s，则应执⾏下列哪⼀个操作______。A. s->link = p；p->link = s；B. s->link = p->link；p->link = s；C. s->link = p->link；p = s；D. p->link = s；s->link = p；（）17.设单链表中结点的结构为typedef struct node
{ data；node * Link；ListNode；
⾮空的循环单链表first的尾结点（由p所指向）满⾜：______A. p->link == NULL；B. p == NULL；C. p->link == first；D. p == first；
（）18.计算机识别、存储和加⼯处理的对象被统称为_________A．数据 B.数据元素C.数据结构D.数据类型
（）19.在具有n个结点的有序单链表中插⼊⼀个新结点并使链表仍然有序的时间复杂度是________A．O（1）（n）(nlogn) (n2)
（）20．队和栈的主要区别是________A.逻辑结构不同B.存储结构不同
C.所包含的运算个数不同D.限定插⼊和删除的位置不同
（）21．链栈与顺序栈相⽐，⽐较明显的优点是________A.插⼊操作更加⽅便B.删除操作更加⽅便C.不会出现下溢的情况D.不会出现上溢的情况
（）22．在⽬标串T[0…n-1]=”xwxxyxy”中，对模式串p[0…m-1]=”xy”进⾏⼦串定位操作的结果_______（）23．已知⼴义表的表头为A，表尾为(B,C)，则此⼴义表为________A.（A,(B,C)）B.（A,B,C）C.(A,B,C)D.(( A,B,C))
（）24．⼆维数组A按⾏顺序存储，其中每个元素占1个存储单元。若A[1][1]的存储地址为420，A[3][3]的存储地址为446，则A[5][5]的存储地址为_______
（）25．⼆叉树中第5层上的结点个数最多为________
（）26．如果某图的邻接矩阵是对⾓线元素均为零的上三⾓矩阵，则此图是_______A.有向完全图B.连通图C.强连通图D.有向⽆环图
（）27．对n个关键字的序列进⾏快速排序，平均情况下的空间复杂度为_______（1）（logn）（n）（nlogn）
（）28．对于哈希函数H(key)=key%13，被称为同义词的关键字是_______A．35和41 和39和44 和51
（）29. 由权值分别为3,8,6,2,5的叶⼦结点⽣成⼀棵哈夫曼树，它的带权路径长度为________。A、24B、48C、72D、53
（）30．对包含N个元素的散列表进⾏检索，平均检索长度
A、为o(log2N)B、为o(N)C、不直接依赖于ND、上述三者都不是
（）31. 向堆中插⼊⼀个元素的时间复杂度为________。A、O(log2n)B、O(n)C、O(1)D、O(nlog2n)
（）32．下⾯关于图的存储的叙述中，哪⼀个是正确的。________
A．⽤相邻矩阵法存储图,占⽤的存储空间数只与图中结点个数有关,⽽与边数⽆关B．⽤相邻矩阵法存储图,占⽤的存储空间数只与图中边数有关,⽽与结点个数⽆关C．⽤邻接表法存储图，占⽤的存储空间数只与图中结点个数有关，⽽与边数⽆关D．⽤邻接表法存储图，占⽤的存储空间数只与图中边数有关，⽽与结点个数⽆关（）33.输⼊序列为（A,B,C,D），不可能得到的输出序列是______.A. (A,B,C,D)B.(D,C,B,A)C.(A, C,D,B)D.(C,A,B,D)
（）34.在长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移____个元素。A、n-iB、n-i+1C、n-i-1D、i
（）35.设⼀个⼴义表中结点的个数为n，则求⼴义表深度算法的时间复杂度为____。A、O(1)B、O(n)C、O(n2)D、O(log 2 n)
（）36.假定⼀个顺序队列的队⾸和队尾指针分别为f和r，则判断队空的条件为____。A、f+1==rB、r+1==fC、f==0D、f==r
（）37.从堆中删除⼀个元素的时间复杂以为____。A、O(1)B、O(log 2 n)C、O(n)D、O(nlog 2 n)
（）38．若需要利⽤形参直接访问实参，则应把形参变量说明为____参数。A.指针B.引⽤C.值D.变量
（）39．在⼀个单链表HL中，若要在指针q所指结点的后⾯插⼊⼀个由指针p所指向的结点，则执⾏____。
A. q⼀>next=p⼀>next；p⼀>next=q；C. q⼀>next=p⼀>next；p⼀>next=q；B. p⼀>next=q⼀>next；q=p； D. p⼀>next=q⼀>next；q⼀>next=p；（）40．在⼀个顺序队列中，队⾸指针指向队⾸元素的____位置。A.前⼀个B.后⼀个C.当前D.最后⼀个
（）41．向⼆叉搜索树中插⼊⼀个元素时，其时间复杂度⼤致⼒____。A O（1）B O（1og2n）C O（n）D O（nlog2n）
（）42.算法指的是________A.计算机程序
B.解决问题的计算⽅法C.排序算法
D.解决问题的有限运算序列
（）43.线性表采⽤链式存储时，结点的存储地址________A.必须是不连续的B.连续与否均可C.必须是连续的
D.和头结点的存储地址相连续
（）44.将长充为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为________（1）（n）
（m）（m+n）
（）45.由两个栈共享⼀个向量空间的好处是：________A.减少存取时间，降低下溢发⽣的机率B.节省存储空间，降低上溢发⽣的机率C.减少存取时间，降低上溢发⽣的机率D.节省存储空间，降低下溢发⽣的机率
（）46.设数组DAtA[m]作为循环队列SQ的存储空间，front为队头指针，reAr为队尾指针，则执⾏出队操作后其头指针front值为________A. front=front+1B. front=(front+1)%(m-1)C. front=(front-1)%mD. front=(front+1)%m
（）47.如下陈述中正确的是________A. 串是⼀种特殊的线性表B. 串的长度必须⼤于零C. 串中元素只能是字母D. 空串就是空⽩串
（）48.若⽬标串的长充为n，模式串的长度为[n/3]，则执⾏模式匹配算法时，在最坏情况下的时间复杂度是________（1）（n）（n2）（n3）
（）49.⼀个⾮空⼴义表的表头________A.不可能是⼦表B.只能是⼦表C.只能是原⼦D.可以是⼦表或原⼦
（）50. 从堆中删除⼀个元素的时间复杂度为________。A、O(1)B、O(n)C、O(log2n)D、O(nlog2n)
（）51.⼀棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为________（）52. 从⼆叉搜索树中查找⼀个元素时，其时间复杂度⼤致为________。A、O(n)B、O(1)C、O(log2n)
D、O(n2)
（）53. 根据n个元素建⽴⼀棵⼆叉搜索树时，其时间复杂度⼤致为________。A、O(n)B、O(log2n )C、O(n2)D、O(nlog2n)
（）54.⽤某种排序⽅法对关键字序列（25，84，21，47，15，27，68，35，20）进⾏排序时，序列的变化情况是如下________：
20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采⽤的排序⽅法是________A.选择排序B.希尔排序C.归并排序D.快速排序
（）55.适于对动态查找表进⾏⾼效率查找的组织结构是________A.有序表B.分块有序表C.⼆叉排序树D.线性链表
（）56. 若需要利⽤形参直接访问实参，则应把形参变量说明为________参数。A 指针B 引⽤C 值D 常量
（）57.链式栈与顺序栈相⽐，⼀个⽐较明显的优点是________。A. 插⼊操作更加⽅便B. 通常不会出现栈满的情况C. 不会出现栈空的情况D. 删除操作更加⽅便
（）58.设单链表中结点的结构为（data, link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插⼊结点*s，则应执⾏下列哪⼀个操作________A. s->link = p->link; p->link = s;B. p->link = s; s->link = q;C. p->link = s->link; s->link = p;
D. q->link = s; s->link = p;
（）59．若让元素1,2,3依次进栈，则出栈次序不可能出现________种情况。A. 3, 2, 1B. 2, 1, 3C. 3, 1, 2D. 1, 3, 2
（）60.线性链表不具有的特点是________。A. 随机访问
B. 不必事先估计所需存储空间⼤⼩C. 插⼊与删除时不必移动元素D. 所需空间与线性表长度成正⽐
（）61．在稀疏矩阵的⼗字链接存储中，每个列单链表中的结点都具有相同的_____。Ａ．⾏号Ｂ．列号Ｃ．元素值Ｄ．地址
（）62.假定⼀个顺序队列的队⾸和队尾指针分别为front和rear，存放该队列的数组长度为N，则判断队空的条件为________。
A．（front+1）% N == rear C．front == 0B．（rear+1）% N == front D．front == rear（）63．栈的插⼊和删除操作在＿＿＿进⾏．(Ａ)．栈顶(Ｂ)．栈底(Ｃ)．任意位置(Ｄ).指定位置
（）64. 在⼀个顺序循环队列中，队⾸指针指向队⾸元素的________位置。A. 后两个B. 后⼀个C. 当前D.前⼀个
（）65．下⾯算法的时间复杂度为＿＿。int f（int n）{
if （n＝＝0）return 1；else return n＊f（n-1）；}A．O(1) B．O(n)C．O(n2) D．O(n!)
（）66.数据结构是⼀门研究⾮数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算的学科①Ａ、操作对象Ｂ、计算⽅法Ｃ、逻辑存储Ｄ、数据映象②Ａ、结构Ｂ、关系Ｃ、运算Ｄ、算法
（）67.数据结构被形式地定义为(K，R)，其中K是（①）的有限集合，R是K上（②）
的有限集合
①Ａ、算法Ｂ、数据元素Ｃ、数据操作Ｄ、逻辑结韵②Ａ、操作Ｂ、映象Ｃ、存储Ｄ、关系
（）68.在数据结构中，从逻辑上可以把数据结构分为________Ａ、动态结构和静态结构Ｂ、紧凑结构和⾮紧凑结构Ｃ、线性结构和⾮线性结构Ｄ、内部结构和外部结构
（）69.线性表的顺序存储结构是⼀种_________的存储结构，线性表的链式存储结构是⼀种________的存储结构Ａ、随机存取Ｂ、顺序存取Ｃ、索引存取Ｄ、HASH存取
（）70.算法分析的⽬的是（①），算法分析的两个主要⽅⾯是（②）①Ａ、找出数据结构的合理性Ｃ、分析算法的效率以求改进
Ｂ、研究算法中的输⼊和输出的关系Ｄ、分析算法的易懂性和⽂档性②Ａ、空间复杂性和时间复杂性Ｃ、可读性和⽂档性Ｂ、正确性和简明性Ｄ、数据复杂性和程序复杂性
（）71.计算机算法指的是（①），它必具备输⼊、输出和（②）等五个特性①Ａ、计算⽅法Ｂ、排序⽅法
Ｃ、解决莱⼀问题的有限运算序列Ｄ、调度⽅法
②Ａ、可执⾏性、可移植性和可扩充性Ｃ、确定性、有穷性和稳定性Ｂ、可执⾏性、确定性和有穷性Ｄ、易谩性、稳定性和安全性
（）72.线性表若采⽤链表存储结构时，要求内存中可⽤存储单元的地址________Ａ、必须是连续的Ｂ、部分地址必须是连续的
Ｃ、⼀定是不连续的Ｄ、连续不连续都可以（）73.在以下的叙述中，正确的是__________
Ａ、线性表的线性存储结构优于链表存储结构Ｃ、栈的操作⽅式是先进先出
Ｂ、⼆维数组是它的每个数据元素为⼀个线性表的线性表Ｄ、队列的操作⽅式是先进后出（）74. ⼀个数组元素A[i]与________的表⽰等价。A、*(A+i)B、A+iC、*A+iD、&A+i
（）75. 对于两个函数，若函数名相同，但只是____________不同则不是重载函数。A、参数类型B、参数个数C、函数类型D、函数变量
（）76. 若需要利⽤形参直接访问实参，则应把形参变量说明为________参数
A、指针B、引⽤C、值D、函数
（）77.下⾯程序段的时间复杂度为____________。for(int i=0; ifor(int j=0; jA[i][j]=i*j;A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)
（）78. 执⾏下⾯程序段时，执⾏S语句的次数为____________。for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A、n2B、n2/2C、n(n+1)D、n(n+1)/2
（）79. 下⾯算法的时间复杂度为____________。int f( unsigned int n ) {
if ( n==0 || n==1 ) return 1; else return n*f(n-1);}A、O(1)B、O(n)C、O(n2)D、O(n!)
（）80．在⼀个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插⼊⼀个新元素时，需要从后向前依次后移个元素。A、n-iB、n-i+1C、n-i-1D、i
（）81．在⼀个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移_____个元素。A、n-i
B、n-i+1C、n-i-1D、i
（）82.在⼀个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均⽐较次数，假定查找每个元素的概率都相等）为_____。A、nB、n/2C、(n+1)/2D、(n-1)/2
（）83．在⼀个单链表HL中，若要向表头插⼊⼀个由指针p指向的结点，则执⾏_____ 。A、HL = p; p->next = HL; C、p->next = HL; p = HL;
B、p->next = HL; HL = p; D、p->next = HL->next; HL->next = p;
（）84．在⼀个单链表HL中，若要在指针q所指的结点的后⾯插⼊⼀个由指针p所指的结点，则执⾏_____。A、q->next = p->next ; p->next = q; C、q->next = p->next; p->next = q;B、p->next = q->next; q = p; D、p->next = q->next ; q->next = p;
（）85．在⼀个单链表HL中，若要删除由指针q所指向结点的后继结点，则执⾏_____。A、p = q->next ; p->next = q->next; C、p = q->next ; q->next = p->next;B、p = q->next ; q->next = p; D、q->next = q->next->next; q->next = q;
（）86. 在稀疏矩阵的带⾏指针向量的链接存储中，每个⾏单链表中的结点都具有相同的________。A、⾏号B、列号C、元素值D、地址
（）87. 设⼀个⼴义表中结点的个数为n，则求⼴义表深度算法的时间复杂度为_______。A、O(1)B、O(n)C、O(n2)D、O(log2n)
（）88．栈的插⼊与删除操作在_____进⾏。A、栈顶B、栈底C、任意位置D、指定位置
（）89．当利⽤⼤⼩为N的⼀维数组顺序存储⼀个栈时，假定⽤top==N表⽰栈空，则向这个栈插⼊⼀个元素时，⾸先应执⾏_____语句修改top指针。A、top++
B、top--C、top=0D、top
（）90．若让元素1，2，3依次进栈，则出栈次序不可能出现_____种情况。A、3，2，1B、2，1，3C、3，1，2D、1，3，2
（）91．在⼀个循环顺序队列中，队⾸指针指向队⾸元素的_____位置。A、前⼀个B、后⼀个C、当前D、后⾯
（）92．当利⽤⼤⼩为N的⼀维数组顺序存储⼀个循环队列时，该队列的最⼤长度为_____。A、N-2B、N-1C、ND、N+1
（）93．从⼀个循环顺序队列删除元素时，⾸先需要_____。A、前移⼀位队⾸指针B、后移⼀位队⾸指针
C、取出队⾸指针所指位置上的元素D、取出队尾指针所指位置上的元素
（）94．假定⼀个循环顺序队列的队⾸和队尾指针分别为f和r，则判断队空的条件是_____。A、f+1==rB、r+1==fC、f==0D、f==r
（）95．假定⼀个链队的队⾸和队尾指针分别为front和rear，则判断队空的条件是_____。A、front==rearB、front!=NULLC、rear!=NULLD、front==NULL四、应⽤题：
1、栈和队列都是特殊线性表，其特殊性是什么
2、设有⼀顺序队列sq，容量为5，初始状态==0，划出作完下列操作的队列及其头尾指针变化状态，若不能⼊队，简述理由后停⽌。1）d,e,b ⼊队。2）d,e 出队。3）i,j ⼊队。4）b 出队。5）n,o,p ⼊队。
3、设有⼀个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量⾄少应为多少
4、将两个栈存⼊数组V[1..m]中应如何安排最好这时栈空、栈满的条件是什么5、已知稀疏矩阵如下：
请写出该稀疏矩阵三元组表⽰。
6、⼴义表A=（a,b,(c,d),(e,(f,g))）,求其长度，及深度。7、请画出下⾯⼴义表相应的加⼊表头结点的单链表表⽰，D(A(x,y,L(a,b))，B(z,A(x,y,L(a,b))))。
8、⼀棵具有n个结点的理想平衡⼆叉树（即除离根最远的最底层外其他各层都是满的，最底层有若⼲结点）有多少层若设根结点在第0层，则树的⾼度h如何⽤n来表⽰（注意n可能为0）9、设⼆叉树后根遍历为BAC，画出所有可能的⼆叉树。
10、假设⼀棵⼆叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树。11、有⼀个完全⼆叉树按层次顺序存放在⼀维数组中，如下所⽰：
请指出结点P的⽗结点，左⼦⼥，右⼦⼥。12、给出下列⼆叉树的先序序列。
13、已知某⾮空⼆叉树采⽤顺序存储结构，树中结点的数据信息依次存放在⼀个⼀维数组中，即
ABC□DFE□□G□□H□□，该⼆叉树的中序遍历序列为：
14、设⼀棵⼆叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5,4,7,8,6,9,试画出该⼆叉树。15、已知⼀组元素为（46，25，78，62，12，37，70，29），试画出按元素排列次序插⼊⽣成的⼀棵⼆叉树。
16、由于元素插⼊的次序不同，所构成的⼆叉排序树也有不同的状态，请画出⼀棵含有1，2，3，4，5，6六个结点且以1为根，深度为4的⼆叉排序树。17、什么是线索⼆叉树为什么要线索化
18、有n个顶点的有向连通图最多有多少条边最少有多少条边19、下图中给出由7个顶点组成的⽆向图。从顶点1出发，
对它进⾏深度优先遍历得到的顶点序列是：进⾏⼴度优先遍历得到的顶点序列是：
20、什么是连通图的⽣成树21、什么是哈夫曼（Huffman）树
22、已知结点a,b,c,d及其权值写出哈夫曼树的构造过程。a b c d7 5 2 4
23、已知图G={V , E}V={ a, b, c, d, e }
E={(a, b),(b, d),(c, d),(d, e),(e, a),(a, c)}画出图G，画出图G的邻接表。
因篇幅问题不能全部显示，请点此查看更多更全内容