1、 数据结构 习题 一、单项选择题 1对矩阵进行压缩存储是为了（ ） A节省存储空间 B提高运算速度 C便于运算 D方便存储 2链式栈与顺序栈相比，一个比较明显的优点是（ ） A插入操作更加方便 B通常不会出现栈满的情况 C不会出现栈空的情况 D删除操作更加方便 3设输入序列为 1， 2， 3， 4， 5，则借助一个队列可以得到的输出序列是（ ） A 3， 4， 1， 2， 5 B 1， 2， 3， 4， 5 C 2， 3， 4， 1， 5 D 5， 4， 3， 2， 1 4.一个栈的输入序列是 6,5,4,3,2,1,可能的输出序列是（ ） A 4,3,2,1,5,6 B 3,6,2,1,5,
2、4 C 1,2,3,5,4,6 D 5,4,1,3,2,6 5设输入序列为 A， B， C， D。借助一个栈可以得到的输出序列是（ ） A A， C， D， B B C， A， D， B C D， C， A， B D D， A， B， C 6将含 100 个结点的完全二叉树从根开始，每层从左到右依次对 结点编号，根结点的编号为 1，则编号为71 的结点的双亲结点的编号为（ ） A 34 B 35 C 36 D无法确定 7已知完全二叉树有 80 个结点，则该二叉树有 （ ） 个度为 1 的结点。 A 0 B 1 C 2 D不确定 8任何一个无向连通图的最小生成树（ ） A只有一棵 B有一棵或多棵
3、 C一定有多棵 D可能不存在 9设图 G 用邻接表存储，对该图进行深度优先搜索遍历，则算法的时间复杂度为 （ ） A O(n) B O(n+e) C O(n2) D O(n3) 10用 n 个键值构造一棵二叉排序树，最低高度为（ ） A n/2 B n C 2n D 2n+1 11如果以链表作为栈的存储结构，则执行出栈操作时（ ） A必须判断栈是否满 B必须判断栈是否空 C判断栈元素的类型 D对栈不作任何判断 12设数组 Datam作为循环队列 SQ 的存储空间， front 为队头指针， rear 为队尾指针，则执行出队操作的语句为 （ ） A front=front+1 B front=(
4、front+1)%m C rear=(rear+1)%m D front=(front+1)%(m+1) 13线性表的长度是指（ ） A顺序存储方式 下数组所占用的元素个数 B链表存储方式下的结点个数 C表中的元素个数 D所能存储的最大的结点个数 14设有一个无向图 G (V， E)和 G= (V， E )，如果 G 是 G 的生成树，则下面不正确的说法是（ ） A G 为 G 的子图 B G 为 G 的连通分量 C G 为 G 的极小连通子图且 V =V D G 是 G 的一个无环子图 15在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功 的情况下，所探测的
5、这些位置上的键值（ ） A一定都是同义词 B一定都不是同义词 C都相同 D不一定都是同义词 16在有序表 A20中按二分查找方法查找 A13依次比较的元素的下标是（ ） A 9， 14， 12， 13 B 9， 15， 12， 13 C 9， 14， 11， 12， 13 D 10， 15， 12， 13 17栈和队列都是（ ） A顺序存储的线性表 B链式存储的线性表 C限制的线性表 D限制存储点的非线性结构 18向顺序栈中压入新元素时，应当（ ） A先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针 C 先后次序无关紧要 D同时进行 19若树的先序序列和中序序列正好相同，则一定是一棵
6、（ ） 的二叉树。 A结点个数可能大于 1 且该树无左子树 B结点个 数可能大于 1 且根结点无左孩子 C结点个数可能大于 1 且各结点均无左孩子 D其中任意一个结点的度不为 2 20下列算法中，在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终位置上的算法是 ( ) A归并排序 B直接插入排序 C快速排序 D冒泡排序 21当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较元素的次数为 （ ） A n2 B n 2n C 2n D n-1 22下列排序算法中，在最好情况下，时间复杂度为 O(n)的算法是（ ） A直接选择排序 B归并排序 C快速排序 D冒泡排序 23下列排序方
7、法中，排序所花费时间不受数据初始排列特性影响的算法是（ ） A直接插入排序 B冒泡排序 C直接选择排序 D快速排序 24对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方 法是（ ） A直接选择排序 B直接插入排序 C快速排序 D起泡排序 25对 5 个不同的数据元素进行直接插入排序，最多需要进行（ ）次比较。 A 8 B 10 C 15 D 25 26在一个具有 n 个结点的双链表中插入一个新结点 ,则该操作的时间复杂性的量级为（ ） A O(1) B O(n) C O(nlog2n) D O(n2) 27二
8、分查找法要求被查找的表是 （ ） A顺序表 B分块有序表 C顺序表且是按键值递增或递减次序排列 D不受上述任何限制 28若某线性表中最常用的操作是在最后一个元素之后插人一个元素和删除第 1 个元素，则采用（ ）存储方式最节省运算时间。 A单链表 B仅有头指针的单循环链表 C仅有尾指针的单循环链表 D双链表 29在一个顺序存储的循环队列中，队头指针指向队头元素的（ ） A前一个位置 B后一个位置 C队头元素位 置 D队尾元素的前一个位置 30设循环队列用数组 An存储，头尾指针为 front 和 rear,求解当前队列中元素个数的公式 ( ) A rear-front B front-rear
9、C n-(front-rear) D (n+rear-front) n 31已知完全二叉树有 100 个结点，则该完全二叉树共有（ ）个叶子结点。 A 37 B 49 C 50 D不确定 32下列存储形式中，（ ）不是树的存储形式。 A双亲表示法 B左子女右兄弟表示法 C广义表表示法 D顺序表示法 33在一棵具有 5 层的满二叉树中结点总数为（ ） A 31 B 32 C 33 D 16 34设有 100 个数据元素，采用折半搜索时，最大比较次数为（ ） A 6 B 7 C 8 D 10 35在顺序存储的线性表 (a1,a2,.,an)中 ,删除任意一个结点时所需移动结点的平均次数为（ ） A
10、 n B n/2 C (n-1)/2 D (n+1)/2 36下列说法不正确的是（ ） A数据元素是数据的基本单位 B数据项是数据中不可分割的最小标识单位 C数据可由若干个数据元素构成 D数据项可由若干个数据元素构成 37为了方便在线性结构的数据中插入一个数据元素 ,则其数据结构宜采用（ ）方式 A顺序存储 B链式存储 C索引存储 D散列存储 38矩阵 A56 的每个元素占 5 个单元，将其按行优先次序存储在起始地址为 1000 的连续的内存单元中，则元素 A55的地址为 （ ） A 1120 B 1125 C 1140 D 1145 39设矩阵 A(aij， 0 i,j 9)的元素满足： a
11、ij 0 (i j,0 i,j 9) aij =0 (it1-r1=s-t1;s-r1-t1=s-r1; B s-t1-r1=s-r1;s-r1-t1=s-t1; C s-r1=s-t1-r1;s-t1=s-r-t1; D s-t1=s-t1-r1;s-r1=s-r-t1; 66.假设 left 和 right 为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针 s 所指的新结点作为非空双链表中 q 所指地点 (中间结点 )的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是 ( ) A q-right=s; s-left=q; q-right-left=s;
12、s-right=q-right; B s-left=q; q-right=s; q-right-left=s; s-right=q-right; C s-left=q; s-right=q-right; q-right-left=s; q-right=s; D以上都不对 67.已知一个稀疏矩阵的三元组表如下： (1， 2， 3)， (1， 6， 1)， (3， 1， 5)， (3， 2， -1)， (4， 5， 4)，(5， 1， -3)，则其转置矩阵的三元组表中第 3 个三元组为 ( ) A (2， 1， 3) B (3， 1， 5) C (3， 2， -1) D (2， 3， -1) 68
13、.顺序查找法与二分查找法对存储结构的要求是 ( ) A. 顺序查找与二分查找均只适用于顺序表 B顺序查找只适用于顺序表 C顺序查找与二分查找既适用于顺序表，也适用于链表 D二分查找只适用于顺序表 69.程序段 for (i=0;inext; B p-next=p-next-next; C p-next=p; D p=p-next-next; 71.在头指针为 head 且表长大于 1 的单循环链表中，若指针 p-next-next=head,则 ( ) A p 指向头结点 B p 指向尾结点 C *p 的直接后继是头结点 D *P 的直接后继是尾结点 72.广义表 A=(a,(b),(),(c
14、,d,e)的长度为 ( ) A 4 B 5 C 6 D 7 73.无向图中一个顶点的度是指图中 ( ) A通过该顶点的简单路径数 B与该顶点相邻接的顶点数 C通过该顶点的回路数 D与该顶点连通的顶点数 74.已知一个图如下所示，从顶点 a 出发进行广度优先遍历可能得到的序列为 ( ) A a c e f b d B a c b d f e C a c b d e f D a c d b f e 75.设顺序存储的线性表共有 123 个元素，按分块查找的要求等分成 3 块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( )
15、A 21 B 23 C 41 D 62 76.下面的二叉树中， ( )不是完全二叉树。 77.下列说法错误的是 ( )。 A一个图的邻接矩阵表示是唯一的 B一个图的邻接表表示是不唯一的 C一个图的生成树必为该图的极小连通子图 D一个无环有向图的拓扑排序序列必唯一 78.设有 6 个结点的无向图，该图至少应有 ( )条边才能确保是一个连通图。 A 5 B 6 C 7 D 8 79.二叉树在线索化后，仍不能有效求解的问题是 ( ) A先序线索二叉树中求先序后继 B中序线索二叉树中求中序后继 C中序线索二叉树中求中序前趋 D后序线索二叉树中求后序后继 80.数据表 A 中有 10000 个元素，如果
16、仅要求求出其中最大的 10 个元素，则采用 ( )排序算法最节省时间。 A堆排序 B希尔排序 C快速排序 D直接选择排序 81若给定有 n 个元素的向量 ，则建立一个有序单向链表的时间复杂性的量级是 ( ) A O(1) B O(n) C O(n2) D O(nlog2n) 82在一个具有 n 个结点的单链表中查找值为 m 的某结点，若查找成功，则平均比较 ( )个结点。 A n B n 2 C (n-1) 2 D (n+1) 2 83研究数据结构就是研究 ( ) A数据的逻辑结构 B数据的存储结构 C数据的逻辑结构和存储结构 D数据的逻辑结构、存储结构及其数据在运算上的实现 84设有 13
17、个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有 ( )个结点。 A 13 B 12 C 26 D 25 85.下列四种排序方法中，不稳定的方法是（ ） A直接插入排序 B冒泡排序 C归并排序 D直接选择排序 86下列说法中不正确的是 ( ) A无向图中 的极大连通子图称为连通分量 B连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D有向图的遍历不可采用广度优先搜索方法 87下列说法中不正确的是（ ） A图的遍历过程中每一顶点仅被访问一次 B遍历图的基本方法有深度优先搜索和广度优先搜索两种 C图的深度优先搜索的方法不适用于有向图
18、D图的深度优先搜索是一个递归过程 88对有序表 (18， 20， 25， 34， 48， 62， 74， 85)用二分查找法查找 85，所需的比较次数为 ( ) A 1 次 B 2 次 C 3 次 D 4 次 89散列表的平均查找长度 ( ) A与处理冲突方法有关而与表的长度无关 B与处理冲突方法无关而与表的长度有关 C与处理冲突方法有关且与表的长度有关 D与处理冲突方法无关且与表的长度无关 90.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为 ( ) A顺序存储结构 B链式存储结构 C索引存储结构 D散列存储结构 91.若进栈序列为 a,b,c，则通过入出栈操作可能得到的
19、 a,b,c 的不同排列个数为 ( ) A 4 B 5 C 6 D 7 92.三维数组 A456按行优先存储方法存储在内存中，若每个元素占 2 个存储单元，且数组中第一个元素的存储地址为 120，则元素 A 45的存储地址为 ( ) A 356 B 358 C 360 D 362 93.下列陈述中正确的是 ( ) A二叉树是度为 2 的有序树 B二叉树中结点只有一个孩子时无左右之分 C二叉树中必有度为 2 的结点 D二叉树中最多只有两棵子树，并且有左右之分 94.n 个顶点的有向完全图中含有向边的数目最多为 ( ) A n-1 B n C n(n-1)/2 D n(n-1) 95.设有一 个含
20、 200 个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过 1.5，则散列存储空间应能够至少容纳（ ）个表项。（设搜索成功的平均搜索长度为Snl=(1+1/(1-a)/2,其中 a 为装填因子） A 400 B 526 C 624 D 676 96.在有向图中每个顶点的度等于该顶点的 （ ） A入度 B出度 C入度与出度之和 D入度与出度之差 97.一个二叉 树按顺序方式存储在一维数组中，如图则结点 E 在二叉树的第（ ）层。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G H I J A 1 B 2
21、C 3 D 4 98设某线性链表的头结点指针为 L, L-data 表示该链表的结点个数， L-next 指向该链表的第一个结点，p 指向新建立的结点，其类型与 L 相同。在建立该链表的过程中，若希望 L-next 始终指向新输入的结点，可采用如下的 C 语言语句实现：（ ） A. p-next=L-next, L-next=p， L-data+; B. p-next=NULL, L-next=p, L-data+; C. L-data+, L-next=p-next, p-next=L; D.以上都不是。 99.以数组 Q0.m-1存放循环队列中的元素，变量 rear 和 qulen 分别指
22、示循环队列中队尾元素的 实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（ ） A rear - qulen B rear - qulen + m C m - qulen D 1 +（ rear + m - qulen） % m 100.设结点 x 和结点 y 是二叉树 T 中的任意两个结点，若在先根序列中 x在 y 之前，而在后根序列中 x 在y 之后，则 x 和 y 的关系是（ ） A x 是 y 的左兄弟 B x 是 y 的右兄弟 C x 是 y 的祖先 D x 是 y 的后代 101.对线性表进行二分查找时，要求线性表必须 ( )。 A以顺序方式存储 B以链接方式存储 C以顺
23、序方式存储，且结点按关键字有序排序 D以链接方式存储，且结点按关键字有序排序 二、判断题 (若正确在 ( )内打，否则打。 ) ( ) 1对链表执行插入和删除操作时，不必移动结点。 ( ) 2双链表中只有一个结点的后继指针为空。 ( ) 3 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。 ( ) 4 线性表的逻辑顺序与物理 顺序总是一致的。 ( ) 5 线性表的顺序存储表示优于链式存储表示。 ( ) 6栈是实现函数调用的必不可少的数据结构。 ( ) 7线性表的长度是线性表所占用的存储空间的大小。 ( ) 8在带头结点的单链表中插入元素结点不会改变头指针的值。 ( ) 9对
24、链队列执行出队操作不会改变尾指针的值。 ( )10树 (或森林 )转化为对应的二叉树后，两者的分支数相等。 ( )11由给定的 n 个权值所构造的哈夫曼树可能不唯一，其结点个数也可能不确定。 ( )12图中一个顶点 i 的出度等于其邻接矩阵中 第 i 列的非 0 元素个数。 ( )13 二叉树是树的特殊情形。 ( )14所谓冲突即是两个关键字的值不同的元素，其散列地址相同。 ( )15二叉树的先序序列和后序序列正好相反。 ( )16在循环队列中，若尾指针 rear 大于头指针 front，则其元素总数为 rear-front ( )17一个有向图的邻接表和逆邻接表中的结点个数一定相等。 ( )
25、18在编号的完全二叉树中 (根结点的编号为 1)，编号为 100 的结点一定在其左子树中。 ( )19在索引顺序表的查找中，对索引表的查找既可采用顺序查找 法，也可采用二分查找法。 ( )20对同一组键值的不同顺序的输入序列，所构造的二叉排序树一定不同。 ( )21稀疏矩阵只能用三元组表压缩存储。 ( )22在一个大根堆中，关键字最大的两个元素一定在数据表的前三个元素中。 ( )23线性表采用链表存储后，线性表的长度等于链表中的结点个数 ( )24双循环链表中，任一结点的前趋指针均指向其逻辑前趋。 ( )25如果一棵二叉树的中序序列是递增有序序列，则一定是一棵二叉排序树。 ( )26对一个有序
26、表作二分查找，查找每个元素所需的查找次数 均比用顺序查找所需的查找次数要少。 ( )27对有 n 个元素的数据表用直接选择排序方法进行排序，最好情况下所需的时间复杂度是 O(n)。 ( )28快速排序算法是所有排序算法中时间复杂度最好的一种排序算法。 ( )29顺序表用一维数组作为存储结构，因此顺序表是一维数组。 ( )30通常使用两个类来协同表示单链表，即链表的结点类和链表类。 ( )31具有 n 个结点的完全二叉树的高度为 log2(n+1)。（ n=0，根结点在第 0 层） ( )32闭散列法通常比开散列法时间效率更高。 ( )33已知指针 P 指向单链表 L 中的某结点，执行语句 P=
27、P-next 不会删除该链表中的结点。 ( )34在链队列中，即使不设置尾指针也能进行入队操作。 ( )35如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。 ( )36 数据的逻辑结构与数据元素本身的内容和形式无关。 ( )37 从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。 ( )38由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。 ( )39数据的基本单位是数据项。 ( )40带权的无向连通图的最小生成树是唯一的。 ( )41用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。 ( )42在霍夫曼编码中，当两个字符出现的频率相
28、同时，其编码也相同，对于这种情况应当特殊处理。 ( )43. 线性表采用顺序存储表示时，必须占用一片连续的存储单元。 ( )44. 装载因子是散列表的一个重要参数，它反映了散列表的装满程度。 ( )45算法和程序没有区别，所以在数据结构中二者是通用的。 ( )46在顺序表中无需为表示结点间的逻辑关系而增加存储空间。 ( )47单链表中的头结点就是单链表的第一个结点。 ( )48队列和栈都是运算受限的线性表。 ( )49任何一棵二叉树中至少有一个结点的度为 2。 ( )50对于 n 个记录的集合进行冒泡排序，所需要的平均时间是 0(n)。 ( )51一棵哈夫曼树中不存在度为 1 的结点。 ( )
29、52二叉树中的叶子结点就是二叉树中没有左右子树的结点。 ( )53一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。 ( )54由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。 ( )55 在用循环 单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 ( )56 一个广义表的表尾总是一个广义表。 ( )57 对于一棵具有 n 个结点，其高度为 h 的二叉树，进行任一种次序的遍历的时间复杂度为 O(h)。 ( )58 数据结构是数据对象与对象中数据元素之间关系的集合。 ( )59 所谓数据的逻辑结构是指数据元素之间的逻辑关系。 ( )60 二维数组是其数组元素为
30、一维数组的线性表，因此它是线性结构。 ( )61若图 G 的最小生成树不唯一，则 G 的边数一定多于 n-1，并且权值最小的边有多条（其中 n 为 G的顶点数）。 ( )62用直接选择排序方法分别对序列 S1=（ 1， 2， 3， 4， 5， 6）和序列 S2=（ 5， 3， 2， 4， 1， 6） 进行排序，两者的比较次数不相同。 ( )63用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可以是没有按键值排好序的。 ( )64 当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。 ( )65 同一
31、数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项 的个数都相等。 ( )66 若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果的最后一个结点。 ( )67如果二叉树中每个结点的值都大于其左孩子结点的值、小于其右孩子结点的值，则可断定它是二叉排序树。 ( )68在循环队列中， front 指向队列中第 1 个元素的前一位置， rear 指向实际的队尾元素，则队列为满的条件是 front=rear。 ( )69在用线性探测法解决冲突所构造的闭散列表中，每组同义词中至少有一个元素的地址正好等于其散列地址。 ( )70 设与一棵树 T
32、 所对应的二叉树为 BT，则与 T 中的叶子结点所对应的 BT 中的结点也一定是叶子结点。 ( )71对有向图 G，如果从任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是有向完全图。 ( )72若一个栈的输入序列为 123 n，其输出序列的第一个元素为 n，则其输出序列的每个元素 ai 一定满足 ai=n-i+1(i=1,2.,n) 三、填空题 1双循环链表中，在指针 P 所指结点前插入指针 S 所指的结点，应执行下列语句： S next P； S prior ； P prior S； ； 2在有 n 个叶子结点的哈夫曼树中，结点总数是 3已知完全二叉树的第六层有 5
33、个结点，则其叶子结点的个数是 4栈的特性是 ，队列的特性是 5有 n 个顶点的有向图最多有 条弧。 6在有 n 个元素的待排序序列已经有序的情况下，用冒泡排序算法进行排序，所作的比较元素的次数为 ， 交换元素的次数为 7单循环链表 L 为空的条件是 8带头结点的双循环链表为空表的条件是 9设指针 r 指向单链表的最后一个结点，要在最后一个结点之后插入指针 s 所指的结点，需执行的三条语句是 ； r=s； r-next=NULL； 10在单链表中，若要删除指针 P 所指结点的后继结点，则需执行下列三条语句 ： U=P next； ； free(U) ； 11设链队列的队头指针为 front，队尾
34、指针为 rear，队列为空的条件是 12已知一棵度为 3 的树有 2 个度为 1 的结点， 3 个度为 2 的结点， 4个度为 3的结点，则该树中有 个叶子结点。 13已知一棵二叉树中有 10 个叶子结点，有 15 个结点仅有左孩子结点， 20 个结点仅有右孩子结点，则整个二叉树有 个结 点。 14有 n 个顶点的连通图的生成树有 条边。 15设有一个链栈，结点中有 data 和 next 两个字段，栈顶指针 Ls 不空，则结点 *S 入栈操作的语句为：Ls-next=S； Ls= ； 16一棵二叉树的先序序列和后序序列正好相反的条件是 17一棵二叉排序树中若有 14 个结点的查找长度 4，则
35、有 个结点的查找长度 3。 18在对有 12 个元素的有序表做二分查找时，有 个结点的查找长度是 4。 19栈可看成是一种运算受限制的线性表 ,其中可以进行插入和删除的一端称为 20设链队列 1q 中结点的格式为 data next, 头指针为 1q-front，尾指针为 1q-rear,队列为空的条件是 。 21无向图中的极大连通子图称为该无向图的 22闭散列表中通常采用 构造后继散列以减少堆积。 23 算法的时间复杂度取决于 _ _ 24设一棵二叉树结点的先根序列为 ABDECFGH，中根序列为 DEBAFCHG，则二叉树中叶子结点是 _ 25 n 个顶点的无向连通图用邻接矩阵表示时 ,该
36、矩阵至少有 _个非零元素 . 26取出广义表 A=(x,(a,b,c,d)中原子 a 的函数是 27在线性表的单链表达式存储中，若一个元素所在结点 的地址为 p，则其后继结点的地址为 ，若假定 p 为一个数组 a 中的下标，则其后继结点的下标的 。 28对于一个具有 n 个顶点和 e 条边的连通图，其生成树中的顶点数和边数分别为 和 。 29二分查找过程所对应的判定树既是一棵 ，又是一棵 。 30若长度 n=10000 的线性表进行二级索引存储：每级索引表中的索引项是下一级 20 个记录的索引，则一级索引表的长度为 ，二级索引表的长度为 。 31设数组 B1.4,1.5中的任一元素均占 3 个
37、单元，从首地址 sb 开始把数组 B 按行优先存储， 则元素B3,4的地址为 _ _。 32 在 n 个结点的线索二叉链表中，有 _个线索指针。 33在对有 10 个数据的有序表作二分查找时，有 _个结点的查找长度是 4。 34在开散列表上查找键值等于 K 的结点，首先必须计算该键值的 _ ,然后再通过指针查找该结点。 35对静态表顺序查找算法采用设置岗哨方式与普通的 设置循环控制变量相比，进行一次查找所花费的平均时间大约减少 _ _。 36若要对某二叉排序树进行遍历，保证输出的所有结点键值序列按递增次序排列，应对该二叉树采用_ 遍历法。 37设需将一组数据按升序排序。在无序区中依次比较相邻两个元素 ai和 ai+1的值，若 ai的值大于 ai+1的值，则交换 ai和 ai+1。如此反复，直到某一趟中没有记录需要交换为止，该排序方法被称为 _。 38 在队列中，允许进行插入操作的一端称为 _，允许进行删除操作的一端称为 _。 39 如图两个栈共享一个向量空间， top1 和 top 分别为指向两个栈顶元素的指针，则“栈满”的判定条件是 _ 。 40如果在排序前，关键字序列已接近正序，则在堆排序和快速排序两者之中，选用 _较为适当。 41通常从四个方面评价算法的质量： _、 _、 _和 _。 42在具有 n 个单元的循环队列中，队满时共有 _个元素
