奥鹏东北师范大学2020年9月《数据结构》考前练兵.doc

1、单选题L内排序方法的稳定性是指()。A.该排序算法不允许有相同的关键字记录B.该排序算法允许有相同的关键字记录C.平均时间为0(nlog2n )的排序方法D.以上都不对答案：D2.顺序文件采用顺序结构实现文件的存储,对大型的顺序文件的少量修 改，要求重新复制整个文件，代价很高，采用()的方法可降低所需的 代价。A.附加文件B.按关键字大小排序C.按记录输入先后排序D.连续排序答案：A3 .在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是 OoA. 0(log2n )B. 0( 1 )C. 0(n )D. 0(nlog2n )答案：B4 .在n个结点的线索二叉树中线索的数目为()。A.

2、 nTB. nC. n+1D. 2n答案：C5,插入、删除只能在同一端进行的线性表，称为（）。A.队列B.循环队列C.栈D.循环栈 答案：C6 .在下述几种排序方法中，不稳定的排序方法是（）。A.直接插入排序B.冒泡排序C.直接选择排序D.归并排序 答案：C7 .用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶 点，则输出的顶点序列是（）。A.逆拓扑有序8 .拓扑有序C.无序的D.部分有序的 答案：A8. AVL树中任一结点的平衡因子的绝对值都应小于等于（）。A. 0B. 1C. 2D. 3答案：B9 .数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是（）A.线

3、性表B.广义表C.树形结构D.图结构 答案：A10 .求图的最小（代价）生成树问题，考虑的是下面的哪一种图（）。A.无向图B.有向图C.带权的无向图D.带权的有向图答案：C11 .设有n个结点的AVL树，其平均查找长度为（）。A. 0 （ 1 ）B. 0 （log2n）C. 0 （n）D. 0 （nlog2n）答案：B12 .在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关OoA.直接插入排序B.冒泡排序C.快速排序D.直接选择排序答案：D13.由3个结点可以构造出多少种不同形态的有向树？（）A. 2B. 3C. 4D. 5答案：A14.对于3个结点a、b、c,可构成不同的二叉树的棵

4、数为（）。A. 24B. 28C. 30D. 32答案：C15.采用邻接表存储的图的广度优先遍历类似于二叉树的()。A.前序遍历B.中序遍历C.后序遍历D.层次遍历答案：D16,设二维数组A0. m-1 0. n-1按行优先顺序存储且每个元素占c 个单元，则元素的地址为()。A. L0C(A0 0) + (j*m+i)*cB. L0C(A0 0) + (i*n+j)*cC. L0C(A0 0) + (j-l)*m+i-l*cD. LOC (A0 0) + (i-l)*n+j-l*c答案：B17.若X是中序线索二叉树中一个有左子女的结点，且X不为根，则X 的中序前驱为()。A. X的双亲B.X的

5、右子树中最左下的结点 C.X的左子树中最右下的结点D. X的左子树中最右下的叶结点 答案：C18.若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是()。A.根结点无右子树的二叉树B.根结点无左子树的二叉树C.根结点可能有左子树和必有右子树D.各结点只有一个子女的二叉树 答案：C23.设有100个关键字,用折半查找法进行查找时,最大比较次数为（）。19 .有n个顶点的无向连通图的边数最少为（）。A. n/2B. n-lC. nD. n+1答案：B20 .平衡的二叉排序树（AVL树）属于（）的数据结构。A.动态B.静态C.线性D.无结构答案：A21 .设有一个10阶的对称矩阵A,采用压缩存储

6、方式，以行序为主存储, all为第一个元素，其存储地址为100,每个元素占一个地址空间，则 a 85的地址为（）。A. 112B. 132C. 118D. 140答案：B22.在有向图G的拓扑序列中，若顶点Vi在Vj之前，则下列情形不可 能出现的是（）。A.G 中有弧VVi , Vj >B.G中有一条从Vi到Vj的路径C.G中没有弧VVi , Vj >D.G中有一条从Vj到Vi的路径答案：DA. 6B. 7C. 25D. 50 答案：B24.数组A 6, 7的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5,5的地址是（）。A. 1165B. 1

7、170C. 1175D.1180 答案：C25一个顺序栈一旦被说明，其占用空间的大小（）。A.可以改变B.不能固定C.已固定D.动态变化答案：C26.设有2500个无序的记录，希望以最快的速度挑选出其中前10个排 序码最大的记录，最好选用的排序方法是（）。A.直接插入排序B.堆排序C.冒泡排序 D.快速排序 答案：B27.求顶点间的最短路径问题，考虑的是下面的哪一种图（）。A.无向图B.有向图C.带权的无向图D.带权的有向图答案：D28.用折半查找法查找表的元素的速度比顺序查找法（）。A.必定快B.必定慢C.相等D.不能确定答案：D29 . head指向的带表头结点的单链表为空的判定条件是（）

8、。A. head = = NULLB. head->next = = headC. head ! = NULLD.head->next = = NULL答案：D30 .下列序列中，（）是执行第一趟按递减序快速排序后所得的序列。A. 68,11 , 18 ,69 70 23 ,93, 73B. 68,11 , 69 ,23 70 18,93,73C. 93,73 70 68,11, 69, 23, 18 D. 68,11 , 69,23,18 70 93,73答案：C31 .四个元素进入队列QU的顺序是U、V、X、Y,进行DeQueue （QU, x） 操作后，队头元素是（）。A.U

9、B. VC.XD. Y答案：B32.若设根结点的层数为0,则具有37个结点的完全二叉树的深度（或 高度）为（）。A. 4B. 5C. 6D. 7 答案：B33.在线索二叉树中，p所指结点没有左子树的充要条件是（）。A.p->lchild = = NULLB.p->ltag = = 1C. p->ltag = = 1 且 p->lchild = = NULLD.p->ltag = = 0答案：B34.在查找过程中，仅进行查找操作，没有引起表本身的改动，这种查找则称为（）。A.静态查找B.动态查找C.内查找D.外查找答案：A35.完全二叉树是下列情况的哪一种（）oA.

10、 一定是满二义树B.可能是满二义树C. 一定不是满二义树D.不是二叉树答案：B36.若有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑 有序序列（）。A.存在B.不存在C.不一定存在D.可能不存在答案：A37.将一棵有100个结点的完全二叉树从上到下、从左到右依次对结点 进行编号,根结点的编号为1,则编号为49的结点的右子女编号为()。A. 48B. 50C. 98D. 99答案：D38.快速排序算法在下述哪种情况下效率最高()oA.被排序的数据已完全有序B.被排序的数据中含有多个相同的排序码C.被排序的数据已基本有序D.被排序的数据完全无序答案：D39.任何一棵二叉树的叶结点在前序、

11、中序和后序遍历序列中的相对次 序()。A.不发生改变B.发生改变C.稍有改变D.不能确定答案：A40 .在一个图中，所有顶点的度数之和等于图的边数的几倍()。A. 1/2B. 1C. 2D. 4答案：C41 .下列排序算法中，在每一趟都能选出一个元素放到其最终位置上， 并且其时间性能受数据初始特性影响的是()。A.直接插入排序B ,快速排序C.直接选择排序D.堆排序答案：B42 .一个栈的入栈序列是a、b、c,则栈的不可能的输出序列是（）。A. acbB. abcC. bcaD. cab答案：D43 .递归过程的实现需用到（）。A.线性表B.链表C.栈D .队列 答案：C44 .若X是中序线索

12、二叉树中一个有右子女的结点，且X不为根，则X 的中序后继为（）。A.X的双亲B.X的右子树中最左下的结点 C.X的左子树中最右下的结点D. X的右子树中最左下的叶结点 答案：B45 .顺序查找法适合于存储结构为下列哪一种方式的线性表（）。A.散列存储B.顺序存储或链接存储C.压缩存储D .索引存储 答案：B46 .广义表运算式tail ( ( ( a , b ) , ( c , d )的操作结果 是()。A. ( c , d )B. c , dc. ( ( c , d )D. d答案：C47 .设散列地址空间为。nrl, key为关键字，用p去除key,将得到 的余数作为key的散列地址，即h

13、(key) = key % p。为了减少发生冲 突的频率，一般取p为()。A.小于等于m的最大奇数 B.小于等于m的最大偶数 C.小于等于m的最大素数 D.小于等于m的最大合数 答案：C48 .有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是()。A. 60B. 66C. 18000D. 33答案：A49.算法的计算量的大小称为计算的。A.效率B.复杂性C.现实性D.难度答案：B50.在数据结构中，从逻辑上可以把数据结构分成（）。A.动态结构和静态结构B .紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 答案：

14、c5L head指向的非空的单循环链表的尾结点（由p所指向）满足（）。A.p->next = = NULLB. p 二二 NULLC. p->next = = headD. p = = head 答案：C52.广义表（a , b , c , d ）的表头是（）。A. aB.()C. ( a , b , c , d )D. ( b , c , d )答案：c53 .在栈中存取数据的原则是()。A.先进先出 B.后进先出 C .后进后出 D.随意进出 答案：B54 .在查找过程中，若同时还要做增、删工作，这种查找则称为（）。A.静态查找B.动态查找C.内查找D.外查找答案：B55,下列

15、排序算法中，其中（）是稳定的。A.堆排序，起泡排序B.快速排序，堆排序C.归并排序，起泡排序D.直接选择排序，归并排序 答案：C56 .对于二维数组A4 4,数组的起始位置LOC（A00）=1000,元素长度为 2,则 L0C（A33）为（）。A. 1000B.1010C. 1008 D.1020 答案：D57 .下列四个序列中，哪一个是堆（）。A. 75,65,30,B. 75,65,45,C. 75,45,65,D. 75,45,65,15 , 25 ,10 , 30 ,30 , 15 ,10 , 25 ,45 , 20 ,25 , 20 ,25 , 20 ,30 , 20 ,101510

16、15答案：C58 .如果BT是由有序树T转换而来的二叉树,那么T中结点的后根序列 就是BT中结点的（）序列。A.前序B.中序C.后序D.层次次序 答案：B59. B+树应用在（）文件系统中。A. ISAMB. VSAMC.顺序 D.散列 答案：B60 .设有n个结点的最佳二叉排序树，对于成功的查找，最少的比较次 数为()。A. 0 ( 1 )B. 0 (log2n)C. 0 (n)D. 0 (nlog2n)答案：A61 .有m个叶结点的哈夫曼树所具有的结点数为()。A. mB. m+1C. 2m- 1D. 2m答案：c62.对下列四种排序方法，在排序中关键字比较次数同记录初始排列无 关的是()

17、oA.直接插入排序B.冒泡排序C.快速排序D.归并排序答案：D63 .设 si = "abc” , JBJ strlen(sl)=()。A. 0B. 1C. 2D. 3答案：D64 .已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结 点的地址为LOC（aO）,则第i个结点的地址为（）。A. LOC(aO) + (i-l)*cB. LOC(aO)+i*cC. LOC(aO)-i*cD. LOC(aO) + (i+l)*c 答案：B65 .在下面的排序方法中，其比较次数与待排序记录的初始排列状态无 关的是（）。A.直接插入排序B.快速排序C.直接选择排序D.归并排序 答案：C6

18、6 . ISAM是索引顺序存取方法，该方法是专为下面的哪一种设备设计的OoA.磁带B.磁盘C.光盘D.外存储器 答案：B67 .在下列情况中，可称为二叉树的是（）。A.每个结点至多有两棵子树的树B.哈夫曼树C.每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树答案：B68 .稀疏矩阵常用的压缩存储方法有两种，它们是（）。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表 答案：C69 .数据序列（8 , 9 , 10 , 4 , 5 , 6 , 20 , 1 , 2 ）只能是下列 排序算法中的（）的两趟排序后的结果。A.直接选择排序B.冒泡排序C.直接插入排序D

19、.堆排序 答案：C70 .下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。（）A.二义排序树B.哈夫曼树C. AVL 树D.堆答案：D71 .在k叉树中，无父母的结点称为（）。A.根B.叶C.祖先D.子孙 答案：A72 .设根结点层次为1,某二叉树的结点前序序列和后序序列正好相反, 则该二叉树一定是（）。A.空或只有一个结点 B.高度等于其结点数C .任一结点无左子女 D.任一结点无右子女 答案：B73 .折半查找要求结点（）。A .无序、顺序存储 B.无序、链接存储 C .有序、顺序存储 D.有序、链接存储 答案：c74 .下面关于串的叙述中，哪一个是

20、不正确的？（）A.串是字符的有限序列B ,空串是由空格构成的申C.模式匹配是串的一种重要运算D.吊既可以采用顺序存储，也可以采用链式存储 答案：B75 .一个存储结点存放一个。oA.数据项B.数据元素 C.数据结构 D.数据类型 答案：B76 .散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值（）。A.同等概率B.最大概率C.最小概率D.平均概率答案：A77.广义表 A=(a, b, ( c, d ) , (e, ( f , g ),则式子 head (tail (head ( tail ( tail ( A )的值为()。A. ( g )B. ( d )C. cD. d

21、 答案：D78.从一个栈顶指针top的链栈中删除一个结点时，用x保存被删除的 元素，执行（）。A. x = top; top = top->next;B.top = top->next; x = top->data;C.x = top->data;D.x = top->data; top = top->next;答案：D79 .下面的排序方法中，辅助空间为0（ n ）的是（）。A.希尔排序B.堆排序C.选择排序 D,归并排序 答案：D80 .倒排文件中倒排表是指（）。A.主关键字索引B.次关键字索引C.物理顺序与逻辑顺序不一致D.多关键字索引答案：B81 .

22、（）的遍历仍需要栈的支持。A.前序线索二义树 B.中序线索二叉树 C .后序线索二叉树D.前三种均需要 答案：C82 . head指向的不带表头结点的单链表为空的判定条件是（）。A. head = = NULLB.head->next = = headC. head ! = NULLD. head->next = = NULL答案：A83.二叉树在线索化后，仍不能有效求解的问题是（）。A.前序线索二义树中求前序后继B.中序线索二义树中求中序前驱C.中序线索二义树中求中序后继D.后序线索二义树中求后序后继答案：D84 .在下述几种排序方法中，辅助空间需要最多的是（）。A.直接插入排序

23、B.快速排序C.直接选择排序D.归并排序答案：D85 .算法分析的两个主要方面是（）oA.正确性与健壮性B.可读性与可用性C.时间复杂度与空间复杂度D.数据复杂性与程序复杂性答案：C86.下列哪项不是利用查找表中数据元素的关系进行查找的方法（）oA.有序表的查找B.二义排序树的查找C. AVL 树D.散列查找答案：D87.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找 长度为（）。A. nB. （n-l）/2C. n/2D. （n+l）/2答案：D88.若要求尽可能快地对序列进行稳定的排序，则应选（）。A.快速排序B.归并排序C.起泡排序D.希尔排序答案：B89.某二叉树结点的前序

24、序列为ECBAD,中序序列为EBCDA,则该二叉树 结点的后序序列为（）。A. ABCEDB. DECABC. DEABCD. BDACE答案：D90.串是一种特殊的线性表，其特殊性体现在（）。A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符 答案：B91.一个算法应该是。A.程序B.问题求解步骤的描述C.要满足五个基本特性D. A 和 C答案：BA.加快查找结点的前驱或后继的速度B ,为了能方便地找到双亲C.为了能在二叉树中方便地进行插入与删除D ,使二叉树的遍历结果唯一答案：A93 .在待排序的元素序列基本有序的前提下，效率最高的排序方法是0。A.直接插入排

25、序B.快速排序C.直接选择排序D.归并排序 答案：A94 .设有n个结点的二叉排序树，对于成功的查找，最多的比较次数为OoA. 0 ( 1 )B. 0 (log2n)C. 0 (n)D. 0 (nlog2n)答案：C95 .判断线索二叉树中某结点p有右子女的条件是()。A.p->rtag = = 0B.p->rtag = = 1c.p ! = NULLD. p->lchild ! = NULL答案：A96 .设有两个串si和s2,求s2在si中首次出现的位置的运算称为()oA.求子吊B .求串长C.联接D.模式匹配 答案：D97 .一个队列的入队序列是a、b、c、d,则队列的

26、输出序列是（）。A. abedB. debaC. adebD. cbda答案：A98.分块查找要求表中的结点（）。A.全部无序B.块之间无序C.全部有序D.块之间有序答案：D99.堆的形状是一棵（）。A.二又排序树B.满二义树C.完全二叉树D. AVL 树答案：C100.若设根结点的层数为0,则高（或深）度为4的二叉树至多含有的结 点数为（）。A. 10B. 16C. 31D. 32答案：C10L二叉树在中序线索化后，仍不能有效求解的问题是（）。A.求指定结点的前序后继B.求指定结点的中序前驱C.求指定结点的中序后继D.求指定结点的后序后继答案：D102 .在队列中存取数据的原则是（）。A.先

27、进先出 B.后进先出 C.先进后出 D ,随意进出 答案：A103 .存放在外存中的数据的组织结构是（）。A.数组B.表C.文件D.链表答案：C104 .静态链表中的指针表示的是（）。A.内存地址B.数组下标C.下一元素地址D.左、右子女地址 答案：B105 .在一个单链表中，在p所指结点之后插入s所指结点，则执行（）oA.s->next = p; p->next = s;1.5- >next = p->next; p->next = s;C. s->next = p->next; p = s;D. p->next = s; s->next

28、 = p->next; 答案：B106 .在下面的叙述中，正确的是（）。A .树的先根遍历序列与其对应的二义树的前序遍历序列相同 B .树的先根遍历序列与其对应的二义树的中序遍历序列相同 C .树的先根遍历序列与其对应的二义树的后序遍历序列相同 D .树的后根遍历序列与其对应的二义树的后序遍历序列相同答案：A107 . 一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数 是：()A.不确定B. 0C. 1D. 2答案：D108.下列排序方法中，哪一个是稳定的排序方法？()A.直接选择排序B.直接插入排序C.希尔排序D.快速排序答案：B109 .一个有n个结点的图，连通分量的个数最多

29、为()。A. 0B. 1C. nTD. n答案：D110 .线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ()。A.必须是连续的B.部分地址必须是连续的C. 一定是不连续的D.连续或不连续都可以答案：D11L “堆积”问题是由于()引起的。A.同义词之间发生冲突B.散列函数C.不同的同义词子表结合在一起D.散列表“溢出”答案：C112.在索引顺序文件中，（）。A .主文件是无序的 B.主文件是有序的 C.不适宜随机查找 D.索引是稠密索引 答案：B113.设根结点的层数为0,若高度为h的二叉树上只有度为0和度为2 的结点，则此二叉树上所包含的结点数至少为（）。A. h+1B.2h-

30、lC. 2hD. 2h+l 答案：D114.下列描述中正确的是（）oA.线性表的逻辑顺序与存储顺序总是一致的B.每种数据结构都具备查找、插入和删除三种基本运算C.数据结构实质上包括逻辑结构和存储结构两方面的内容D.选择合适的数据结构是解决应用问题的关键步骤 答案：D115.在具有n个结点的完全二叉树中，若设根结点的编号为1,则编号 为i（i>l）的结点的双亲结点的编号是（）。A. 2iB. 2i+l116 .线索二叉树是一种（）结构。A.逻辑B.物理C.逻辑和存储D.线性答案：B117 .下面哪些方法可以判断出一个有向图是否有环（回路）？（）A.广（宽）度优先遍历B.拓扑排序C.求最短路

31、径D.求关键路径 答案：B118 .判断线索二叉树中某结点p有左子女的条件是（）。A.p ! = NULLB.p->lchild != NULLC.p->ltag = = 0D.p->ltag = = 1答案：c119 .每一个（存储）结点不仅含有一个数据元素，还包含一组指针，该存 储方式是（）。A.顺序存储 B.链接存储 C.索引存储 D.散列存储 答案：B120 .散列文件使用哈希函数将记录的关键字值计算转化为记录的存储 地址，因为哈希函数是一对一的关系，则选择好的0方法是散列文件 的关键。A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理 答案：D121.

32、非线性结构的逻辑特征是一个结构可能有（）。A. 一个前驱和一个后继B.多个前驱和一个后继C. 一个前驱和多个后继D.多个前驱和多个后继答案：D122.在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点 的操作是（）。A. r = f->next;B.r = r->next;C.f = f->next;D.f = r->next;答案：c123.单链表的存储密度（）。A.大于1B.等于1C.小于1D.不能确定答案：C124.最佳二叉排序树属于（）的数据结构。A.动态B.静态C.线性 D.无结构 答案：BA.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基

33、本方法有两种：深度优先遍历和广度优先遍历C.图的深度优先遍历不适用于有向图D.图的深度优先遍历是一个递归过程答案：C126. 一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个 数是：()。A.不确定B. 0C. 1D. 2答案：C127.一个有向无环图的拓扑排序序列()是唯一的。A. 一定B.不一定C.可能D.三者均不对答案：B128.假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测？。A. k-1 次B.k次C. k+1 次D.k(k+l)/2 次答案：D129.若由树转化得到的二叉树是非空的二叉树，则二叉树形状是()。A.根结点无右子

34、树的二叉树B.根结点无左子树的二叉树C.根结点可能有左子树和右子树 D.各结点只有一个子女的二叉树 答案：A125.下列说法不正确的是（）。130.将一个A 1. 100, 1. 100的三对角矩阵，按行优先次序存入一 维数组B1L.298中,A中元素A 66, 65在数组B中的位置K为（）。A. 193B. 195C. 197D. 199答案：B131.若一组记录的排序码为 46,79,56,38,40,84 ,则利用堆排序的 方法建立的初始堆为（）。A. 79, 46, 56, 38, 40, 84B. 84, 79, 56, 38, 40, 46C. 84, 79, 56, 46, 40

35、, 38D. 84, 56, 79, 40, 46, 38答案：B132.顺序表中逻辑上相邻的结点其物理位置也（）。A. 一定相邻B.不必相邻C.按某种规律排列D.无要求答案：A133.某二叉树结点的中序序列为DGBAECHF,后序序列为GDBEHFCA,则 该二叉树结点的前序序列为（）。A. AHFECGDBB. AHFCEBDGC. ABDGCEFHD. BDGAECHF答案：C134 .下列哪一种图的邻接矩阵是对称矩阵？（）A.有向图B.无向图C. AOV 网D. AOE 网 答案：B135.n个结点的线索二叉树上含有的线索数为（）。A. nTB. nC. n +1D. 2n 答案：c1

36、36.下述文件中适合于磁带存储的是（）。A.顺序文件B.索引文件C.散列文件D.多关键字文件答案：A137.如果要求一个线性表既能较快地查找、又能适应动态变化的要求,则可采用的查找方法是（）。A.顺序查找B.折半查找C.分块查找D.基于属性的查找答案：C138 .在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序 序列（初始时为空）的一端的方法，称为（）。A.希尔排序 B.插入排序 C.归并排序 D.选择排序 答案：D139 .在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在P之前插入s所指结点，则执行()。A.p->next = s; s->next = q;1

37、.5- >next = p->next; p->next = s;C. p->next = s->next; s->next = p;D. q->next = s; s->next = p;答案：D140.树最适合用来表示()。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据答案：C14L下面关于算法说法错误的是O。A.算法最终必须由计算机程序实现B .为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上儿个都是错误的答案：D142.有n个顶点的有向图的边数最多为

38、()。A. nB. n(n-l)C. n(n-l)/2D. 2n答案：B143. 一个栈的入栈序列是a、b、c、d,则栈的不可能的输出序列是()oA. acbdB. abedC. dbeaD. adeb答案：c144 .排序趟数与序列的原始状态有关的排序方法是（）排序法。A.直接插入B.直接选择C.冒泡D.归并 答案：C145 .有n个顶点的无向图的边数最多为（）。A. nB. n（n-l）C. n（n-l）/2D. 2n答案：C146.对关键码序列28 , 16 , 32, 12, 60, 2, 5, 72快速排序（从小到大序），一次划分的结果为（）。A. ( 2 , 5 ,B. ( 5 ,

39、 16 , C. ( 2 , 16 , D. ( 5 , 16 , 答案：B12 , 16 )28 ( 60 ,28 ( 60 ,28 ( 60 ,28 ( 32 ,32 ,32 ,32 ,60 ,72 )72 )72 )72 )147.下面说法不正确的是（）。A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C.广义表常采用链接存储结构D.广义表可以是一个多层次的结构 答案：A148 .用ISAM组织文件适合于（）oA.磁带B.磁盘C .光盘D.外存储器 答案：B149 .在k叉树中，结点度数的最大值为（）。A. k-1B. kC. k+1D. k*n 答案：B150.若对n阶对称

40、矩阵A按行优先顺序将其下三角形的元素（包括主对 角线上的所有元素）依次存放于一维数组B l.n（n+l）/2 中，则在 B中确定aij （ i < j）的位置k的关系为（）。A. i*(i-l)/2+jB. j*(j-l)/2+iC. i*(i+l)/2+jD. j*(j+l)/2+i 答案：B判断题1 .在二叉树中插入结点，则此二叉树便不再是二叉树了。A.错误B.正确答案：A2 .采用二叉链表作为存储结构，树的先根遍历和其相应的二叉树的前序 遍历的结果是一样的。3 .树（森林）的结点的先根遍历和后根遍历分别与它相应二又树的结点 前序遍历和后序遍历是一致的。A.错误B.正确 答案：A4

41、.哈希表（散列表）的结点中只包含数据元素自身的信息，不包含任何指 针。A.错误B.正确答案：A5 .结构的存储密度定义为数据本身所占的存储量与整个结构所占的存 储量之比。A.错误B.正确答案：B6 .无向图的邻接矩阵一定是对称矩阵,有向图的邻接矩阵一定是非对称 矩阵。A.错误B.正确答案：A7 .在有向图中，度为0的顶点称为终端顶点（或叶子）。8 .倒排文件的优点是维护简单。A .错误B.正确答案：BA .错误B.正确答案：A9 .倒排文件是对次关键字建立索引oA .错误 B.正确 答案：B10 .二叉树的中序遍历序列中，任意一个结点均处在其右子女结点（若 存在）的前面。A.错误 B.正确 答

42、案：B11 .二叉树是度为2的有序树。A .错误 B.正确 答案：A12 .广义表的同级元素（直属于同一个表中的各元素）具有线性关系。A .错误 B.正确 答案：B13 .分块查找在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中的元素个数有关。14 .二叉排序树删除一个结点后，仍是二叉排序树。A.错误B.正确答案：BA .错误B.正确答案：A15 .中序线索二叉树的优点是便于在中序下查找前驱结点和后继结点oA .错误 B.正确 答案：B16 .任何无向图都存在生成树。A .错误B.正确答案：A17 .最佳二叉排序树是静态的，而平衡二叉排序树（AVL树）是动态的。A.错误B

43、.正确答案：B18 .排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终 止。A .错误 B.正确 答案：A19 .对有序的单链表可以进行折半查找。A.错误B.正确 答案：A20 .无向图的邻接矩阵可用一维数组存储。21 .数组不适合作为任何二叉树的存储结构。A .错误 B.正确 答案：A22 .拓扑排序算法仅适用于有向无环图。A .错误B.正确答案：A23 .对n个记录的文件进行堆排序，最坏情况下的执行时间是0（nlog2n ）。A.错误B.正确答案：B24 .有向图的邻接矩阵是对称的。A .错误 B.正确 答案：A25 .在平衡的二叉排序树中，向某个平衡因子不为零的结点的树中插入一

44、新结点，必引起平衡旋转。A.错误B.正确答案：A26 .数据的逻辑结构是指数据的各数据项之间的逻辑关系。27 .广义表的取表尾运算，其结果通常是一个表，但有时也可是一个单元素值。A.错误B.正确答案：A28 .空串与空格串是相同的。A.错误 B.正确 答案：A29 .通常使用队列来处理函数或过程的调用。A .错误 B.正确 答案：A30 .广义表的取表尾运算，其结果仍是一个广义表。A .错误 B.正确 答案：B31 .所谓取广义表的表尾就是返回广义表中最后一个元素。A.错误B.正确 答案：A32 .对无序表用折半查找比顺序查找快。A .错误B.正确答案：A33 .循环队列也存在空间溢出问题。A

45、 .错误 B.正确 答案：B34 .二叉树的叶结点，在前序遍历、中序遍历和后序遍历下皆以相同的 相对位置出现。A.错误 B.正确 答案：B35 .倒排文件与多重表文件的次关键字索引结构是不同的。A .错误 B.正确 答案：B36 .文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。A.错误B.正确答案：B37 .为了方便的插入和删除数据，可以使用双向链表来存放数据。A.错误B.正确答案：B38 .二叉树按某种次序线索化后，任一结点均有指向其前序结点和后继 结点的线索。A.错误B.正确答案：A39 .当一棵具有m个叶结点的二叉树的WPL值为最小时，称其

46、树为Huffman树，且其二叉树的形状必是唯一的。A.错误B.正确答案：A40 .若一个广义表的表头为空表，则此广义表亦为空表。A.错误B.正确答案：A41 .二叉树的前序遍历序列中，任意一个结点均处在其子女结点（若存 在）的前面。A.错误B.正确 答案：B42 .数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的 存储结构。43 .栈和队列都是限制存取点的线性结构。A.错误B.正确答案：AA .错误B.正确 答案：B44 .从逻辑结构上看，n维数组的每个元素均属于n个向量。A .错误 B.正确 答案：B45 .对于任何数据结构，链接存储结构一定优于顺序存储结构。A .错误B.正确答案

47、：A46 . AOV网的含义是以顶点表示活动的网。A.错误B.正确答案：B47 .顺序存储方式只能用于存储线性结构。A .错误B.正确答案：A48 .快速排序总比简单的排序方法快。A .错误 B.正确 答案：A49 .二叉树的前序遍历并不能唯一确定这棵树形，但是，如果还知道该 树的根结点是哪一个，则可以确定这棵二叉树。A .错误B.正确 答案：A50 .若一个有向图的邻接矩阵对角线以下的元素均为零，则该图的拓扑 有序序列必定存在。A.错误B.正确 答案：B51 .最小生成树问题是构造带权连通图（网）的最小代价生成树。A.错误 B.正确 答案：B52 .顺序存储结构的主要缺点是不利于插入、删除操

48、作。A .错误 B.正确 答案：B53 . ( 101, 88, 46, 70, 34, 39, 45, 58, 66, 10)是堆。A .错误 B.正确 答案：B54 .有向图中顶点Vi的度等于其邻接矩阵里第i行中的1的个数。A.错误B.正确 答案：A55 .二叉树的后序遍历序列中，任意一个结点均处在其子女结点（若存 在）的后面。A .错误B.正确答案：A56 .空串是由空格构成的串。A.错误B.正确答案：A57 .两个串相等的充分必要条件是两个串的长度相等且对应位置的字符 相同。A.错误B.正确答案：B58,有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩 阵中非零元素之和。A.

49、错误B.正确答案：A59 .需要借助于一个栈来实现DFS算法。A.错误B.正确答案：B60 .链表中的表头结点使得插入、删除操作简单。A.错误B.正确答案：B61 .对于查找运算来说，链接存储结构一定优于顺序存储结构。62 .二叉树中除叶结点外，任一结点X ,其左子树根结点的值小于该结 点X的值；其右子树根结点的值大于等于该结点X的值，则此二叉树一 定是二叉排序树。A.错误B.正确答案：A63,线性表的特点是每个元素都有一个前驱和一个后继。A.错误B.正确答案：A64.直接访问文件也能顺序访问，只是一般效率不高。A.错误B.正确答案：A65.对大小均为n的有序表和无序表分别进行顺序查找，在等概

50、率查找 的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找 失败，它们的平均查找长度是不同的。A.错误B.正确答案：B66 .在查找树（二叉排序树）中插入一个新结点，总是插入到叶结点下 面O67 .二叉树的遍历结果不是唯一的。A .错误 B.正确 答案：B68 .哈夫曼树的结点个数不能是偶数。A .错误B.正确答案：B69 .用一维数组存储二叉树时，总是以前序遍历顺序存储结点。A.错误B.正确答案：A70 .程序一定是算法。A ,错误B.正确答案：A71 .两个栈共用静态存储空间，对接使用方式减少了空间溢出的可能性。A .错误 B.正确 答案：B72 .二叉树中每个结点至多有两个子

51、结点，而对一般的树则无此限制。因此，二叉树是树的特殊情形。73 .在中序线索二叉树中，每一非空的线索均指向其祖先结点。A .错误 B.正确 答案：B74 .栈是实现过程和函数等子程序所必需的结构。A .错误B.正确答案：B75 .数据结构的运算（操作）是定义在数据的逻辑结构之上的。A.错误B.正确答案：B76 .数据对象是具有相同性质的数据元素的集合。A ,错误B.正确答案：B77 .广义表中的元素或者是一个不可分割的原子，或者是一个非空的广 义表。A.错误 B.正确 答案：A78 .二叉树中序线索化后，不存在空指针域。A .错误B.正确答案：A79 .对一棵二叉排序树按前序方法遍历得到的结点

52、序列是从小到大的序 列。A.错误B.正确答案：A80 .存放在磁盘、磁带上的文件，既可以是顺序文件，也可以是索引结 构或其他结构类型的文件。A.错误B.正确答案：A81 .当广义表中的每个元素都是原子时，广义表便成了线性表。A.错误B.正确答案：B82 .完全二叉树肯定是平衡二叉排序树。A.错误B.正确答案：A83 .哈希表与哈希文件的唯一区别是哈希文件引入了 “桶”的概念。84 .串是一种数据对象和操作都特殊的线性表。A.错误B.正确答案：B85 .将一棵树转成二叉树，根结点没有右子树。A .错误 B.正确 答案：B86 .数组是同类型值的集合。A.错误B.正确 答案：A87 .串只能按顺序存储方式进行存储。A.错误 B.正确 答案：A88 .链表与顺序存储结构相比，在链表中进行插入、删除操作的效率高。A .错误B.正确 答案：B89