2022年数据结构课程习题汇编解答推荐 .pdf

《2022年数据结构课程习题汇编解答推荐 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构课程习题汇编解答推荐 .pdf（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、选择题1、若入栈序列的元素顺序为A、B、C、D、E，判断下列哪一个出栈序列是不可能的。（）AA、B、C、D、EB. B、C、D、 E、ACE、A、B、C、DD. D、C、B、A、 E 2、某程序的时间复杂度为（3n+nlog2n+n2+8 ）, 其数量级表示为（） 。AO（n）BO（nlog2n） CO（n2）DO（log2n）3、一个循环队列的队首和队尾指针分别是front 和 rear,则判别队空的条件是（）Afront+1=rear Bfront=rear+1 Cfront=0 Dfront=rear 4、一个非空广义表的表头（）A不可能是子表B只能是子表C只能是原子D.可以是子表或原子

2、5、一个有顺序表有255 个对象，采用顺序搜索法查表，平均搜索长度为（）A 128 B 127 C 126 D 255 6、设有一个含200 个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列存储空间应能够至少容纳（）个表项。（搜索成功的平均搜索长度为Snl=(1+1/(1-a)/2, 其中 a 为装填因子A 400 B 526 C 624 D 676 7、在一棵度为3 的树中， 度为 3 的结点个数为2，度为 2 的结点个数为1，则度为 0 的结点个数为( )。A. 4 B. 5 C. 6 D. 7 8以下哪个数据结构不是多型数据类型（）A栈B

3、广义表C有向图D字符串9以下数据结构中， （）是非线性数据结构A树B字符串C队D栈10. 下列数据中， （）是非线性数据结构。A栈B. 队列C. 完全二叉树D. 堆11连续存储设计时，存储单元的地址（） 。A一定连续B一定不连续C不一定连续D部分连续，部分不连续12对稀疏矩阵进行压缩存储目的是（） 。A便于进行矩阵运算B便于输入和输出C节省存储空间D降低运算的时间复杂度13以下属于逻辑结构的是（） 。A顺序表B. 哈希表C.有序表D. 单链表14从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

4、- - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 26 页 - - - - - - - - - A原树高度加1 B原树高度减1 C原树高度D不确定15在一个具有n 个顶点的无向图中，要连通所有顶点则至少需要（）条边。An B2n Cn-1 D n+1 16在某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用 ( )存储方式最节省运算时间。A 单链表B、仅有头指针的单循环链表C、双链表D、仅有尾指针的单循环链表17下列 4 种排序方法中，不稳定的方法是（） 。A直接插入排序B冒泡排序C归并排序D直接选择排序18串是一种特

5、殊的线性表，其特殊性体现在（）A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符19在一个图中，所有顶点的度数之和等于所有边数的（）倍。A.1/2 B.1 C.2D.4 20有一个有序表为1 ，3， 9，12，32，41，45，62，75，77，82，95， 100，当二分查找值为 82 的结点时，（）次比较后查找成功。A.1 B.2 C.4 D.8 21一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（） 。A.0 B.1 C.2 D.不确定22在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（） 。A.快速排序B.希尔排序C.冒泡排序

6、D.堆排序23向顺序栈中压入新元素时，应当（） 。A先移动栈顶指针，再存入元素B先存入元素，再移动栈顶指针C先后次序无关紧要D同时进行24在线索二叉树中，下面说法不正确的是( ) A. 在中序线索树中，若某结点有右孩子，则其后继结点是它的右子树的左支末端结点。B.线索二叉树是利用二叉树的n+1 个空指针来存放结点前驱和后继信息的。C.每个结点通过线索都可以直接找到它的前驱和后继D.在中序线索树中，若某结点有左孩子，则其前驱结点是它的左子树的右支末端结点。25广义表A=(a,b,(c,d),(e,(f,g), 则下面式子的值为（） 。Head(Tail(Head(Tail(Tail(A) A.

7、(g) B. (d) C. c D. d 26有三个数字1,2,3,将它们构成二叉树，中序遍历序列为1,2,3 的不同二叉树有( )种。A. 5 B. 6 C. 7 D.8 27一个算法应该是（） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 26 页 - - - - - - - - - A程序B问题求解步骤的描述C要满足五个基本特性DA 和 C. 28. 下面关于算法说法错误的是（）A算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的

8、C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的29. 下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n 下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A(1) B.(1),(2) C.(1),(4) D.(3) 30从逻辑上可以把数据结构分为（）两大类。A动态结构、静态结构B顺序结构、链式结构C线性结构、非线性结构D初等结构、构造型结构31以下与数据的存储结构无关的术语是（） 。A循环队列B. 链表C. 哈

9、希表D. 栈32以下数据结构中，哪一个是线性结构（）？A广义表B. 二叉树C. 稀疏矩阵D. 串33以下那一个术语与数据的存储结构无关？（）A栈B. 哈希表C. 线索树D. 双向链表34一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（） 。A .0 B. 1 C. 2 D 不确定35在一棵二叉树中，第4 层上的结点数最多为（） 。A31 B8 C15 D16 36向堆中插入一个元素的时间复杂度为（） 。AO(log2n) BO(n) CO(1) DO(nlog2n) 37广义表L= （a， （b，c） ） ，进行 Tail（L）操作后的结果为（） 。A. c B. b，c C.（b，c

10、）D.（ （b，c） ）38一棵完全二叉树上有1001 个结点，其中叶子结点的个数是（）A250 B、500 C 254 D、501 39计算机算法必具备输入、输出和( ) 等五个特性A. 可行性、可移植性和可扩充性B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D.易读性、稳定性和安全性名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 26 页 - - - - - - - - - 40. 下面的叙述不正确的是（）A线性表在链式存储时，查找第i 个元素的时间同i 的

11、值成正比B. 线性表在链式存储时，查找第i 个元素的时间同i 的值无关C. 线性表在顺序存储时，查找第i 个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i 个元素的时间同i 的值无关41 在长度为n 的顺序表的第i(1 in+1)个位置上插入一个元素，元素的移动次数为( ) A n-i+1 B.n-i C.i D.i-1 42对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( ) A. 顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表43若一个具有N 个顶点， K 条边的无向图是一个森林(NK) ，则该森林中必有( )棵树。A. K B. N

12、 C .N-K D.1 44若已知一个栈的入栈序列是1，2，3，.，n，其输出序列为p1,p2,p3, pn,若 p1 是 n，则 pi 是 ( ) A. i B. n-i C. n-i+1 D. 不确定45表达式a*(b+c)-d 的后缀表达式是( ) A.abcd*+- B.abc+*d-C .abc*+d- D.-+*abcd 46在倒排文件中，通常包含有( ) 倒排表。A. 一个B.多个C.两个D.一个或两个47二维数组Mi,j 的元素占三个字节，行下标 i 的范围从0 到 4，列下标 j 的范围从0 到 5，M 按行存储时元素M3 ，5的起始地址与M 按列存储时元素( ) 的起始地址

13、相同。A、 M2,4 B、M3,4C、M3,5 D、M4,4 48在一个单链表HL 中，若要在指针q 所指结点的后面插入一个由指针p 所指向的结点，则执行（） 。A. q-next=p-next;p-next=q; B. p-next=q-next;q=p; C. q-next=p-next;p-next=q; D. p-next=q-next;q-next=p; 49非空的循环链表head的尾结点 *p 满足（）A. p-next =NULL B. p=NULL C. p-next=head D. p=head 50若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选（）A 快速排

14、序B 堆排序C 归并排序D 基数排序。51二叉树在线索化后，仍不能有效求解的问题是（） 。A.先序线索二叉树中求先序后继B. 中序线索二叉树中求中序后继C.中序线索二叉树中求中序前驱D. 后序线索二叉树中求后序后继52在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A 的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 26 页 - - - - - - - - - 左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（）型调整以使其平衡。A.LL B.L

15、R C.RL D.RR 53对有 18 个元素的有序表做折半查找，则查找A3 的比较序列的下标依次（） 。A.1-2-3 B.9-5-2-3 C.9-5-3 D. 9-4-2-3 54计算机算法指的是（）A计算方法B.排序方法C解决问题的有限运算序列D调度方法55设森林 F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2 和 M3。与森林 F 对应的二叉树根结点的右子树上的结点个数是（） 。AM1 BM1+M2 C M3 DM2+M3 56以下叙述正确的是（）A 线性表的线性存储结构优于链表存储结构B 二维数组是其数据元素为线性表的线性表C 栈的操作方式是先进先出D 队列的操作方式

16、是先进后出57一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（）A 100 B 108 C 110 D 120 58判定一个栈ST（最多元素为m）为空的条件是（）A ST-top 0 BST-top = 0 C ST-top m D ST-top = m 59静态链表中指针表示的是（）. A 内存地址B数组下标C下一元素地址D左、右孩子地址60 .已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）Aacbed Bdecab Cdeabc Dcedba 61有 n 个叶子的哈夫曼树的结点总数为（） 。A不确定B2

17、n C2n+1 D 2n-1 62在一非空二叉树的中序遍历序列中，根结点的右边（）A只有右子树上的所有结点B只有右子树上的部分结点C只有左子树上的部分结点D只有左子树上的所有结点63对于一个具有n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）An B （n1）2Cn1 Dn264.下面的叙述中，不正确的是( ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 26 页 - - - - - - - - - A关键活动不按期完成就会影响整个工程的完成时间B任何一个

18、关键活动提前完成，将使整个工程提前完成C所有关键活动若提前完成，则整个工程将提前完成D某些关键活动若提前完成，将使整个工程提前完成65.二叉树上叶结点数等于（） 。A分支结点数加1 B单分支结点数加1 C双分支结点数加1 D双分支结点数减1 66若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置， 利用 ( )遍历方法最合适。A前序B中序C后序D按层次67.每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（）排序A插入B交换C选择D归并68.设循环队列中数组的下标范围是1n，其头尾指针分别为f 和 r，则其元素个数为（） 。Ar-f Br-f+1 C(

19、r-f) mod n +1 D (r-f+n) mod n 69.二叉树在线索化后，仍不能有效求解的问题是（） 。A先序线索二叉树中求先序后继B 中序线索二叉树中求中序后继C中序线索二叉树中求中序前驱D 后序线索二叉树中求后序后继70 下面说法正确的为（）（1）二叉树按某种方式线索化后，任一结点均有指向前驱和后继的线索（2）二叉树的前序遍列序列中，任意一个结点均处在子孙结点前（3）二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值A （1） （2） （3）B （1） （2）C （1） （ 3）D前面的可选答案都不对71 下面的说法中正确的是（）(1) 任何一棵二叉树的叶结点在三种遍历中的

20、相对次序不变; (2) 按二叉树定义 ,具有三个结点的二叉树共有6 种 ; A(1),(2) B(1) C (2) D(1),(2) 都错72.一棵二叉树高度为h,所有结点的度或为0,或为 2,则这棵二叉树最少有（）个结点A 2h B2h-1 C2h+1 Dh+1 73下列排序算法中，在待排序数据已有序时，花费时间反而最多的是（）排序A冒泡B希尔C快速D堆74与链表不相适宜的叙述是（）A、动态存储分配B、可表示任何类型的数据结构名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，

21、共 26 页 - - - - - - - - - C、插入和删除操作灵活D、查找速度快75 设 i 为 n 个结点的二叉树结点编号，i=1,2,n； 若 inext=p-next;p-next=q; B、 p-next=q-next;q=p; C、 q-next=p-next;p-next=q; D、 p-next=q-next;q-next=p; 79 S=software ，其子串的数目是（）A、8 B、37 C、36 D、9 80下面的说法中正确的是（）. （1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；（2）按二叉树定义，具有三个结点的二叉树共有6 种。A(1)(2) B(1

22、) C(2) D(1)、(2)都错81二维数组Mi,j 的元素占三个字节，行下标 i 的范围从0 到 4，列下标 j 的范围从0 到 5，M 按行存储时元素M3 ，5的起始地址与M 按列存储时元素( )的起始地址相同。A、 M2,4 B、M3,4 C、M3,5 D、M4,4 82下列几种排序方法中，平均查找长度最小的是( ) A、插入排序B、选择排序C、快速排序D、归并排序83采用顺序查找方法查找长度为n 的线性表时，每个元素的平均查找长度为（）A、n B、n/2 C、 （n1）/2 D、 （n1）/2 84下述几种排序方法中，要求内存量最大的是（）A、插入排序B、选择排序C、快速排序D、归并

23、排序85 数据结构是一门研究非数值计算的程序设计问题中计算机的（） ， 以及它们之间的 （）和运算等的学科。A、操作对象关系B、计算方法结构C、逻辑存储运算D、数据映象算法86下述哪一条是顺序存储结构的优点？（）A存储密度大B插入运算方便名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 26 页 - - - - - - - - - C删除运算方便D可方便地用于各种逻辑结构的存储表示87计算机算法必须具备输入、输出、（）等五个特性。A、 可行性、可移植性和可扩充性B、可行性、

24、确定性和有穷性C、 确定性、有穷性和稳定性D、易读性、稳定性和安全性88栈和队列的共同点是（）A、 都是先进后出B、 都是先进先出C、 只允许在端点处插入和删除元素D、没有共同点89在一个单链表中，若删除p所指结点的后续结点，则执行（）A、p - next = p -next-next;B、p = p-next; p-next = p-next-next C、p-next = p-next; D、p = p-next-next; 90深度为5 的二叉树至多有（）个结点A、16 B、32 C、31 D、10 91 设循环队列中数组的下标范围是1n， 其头尾指针分别为f 和 r， 则其元素个数为

25、（） 。A、r-f B、r-f+1 C、(r-f) mod n +1 D、 (r-f+n) mod n 92递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。A队列B多维数组C栈D. 线性表93对一棵二叉排序树进行（）遍历得到的结点序列是一个有序序列。A、前序B、中序C、后序D、层序94任何一个无向连通图的最小生成树（） 。A、有一棵或多棵B、只有一棵C、一定有多棵D、可能不存在95数组 A1.5,1.6 的每个元素占5 个单元，将其按行优先顺序存储在起始地址为1000 的连续的内存单元中，则元素A5,5 的地址为（） 。A. 1140 B. 1145 C. 1120 D

26、1125 96下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（） 。A.堆排序B.冒泡排序C.快速排序D.直接插入排序97设栈 S 和队列 Q 的初始状态为空，元素e1，e2，e3，e4,e5 和 e6依次通过栈S，一个元素出栈后即进队列Q，若 6 个元素出队的序列是e2，e4，e3,e6,e5,e1则栈 S 的容量至少应该是( )。A 6 B. 4 C. 3 D. 2 100一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A所有的结点均无左孩子B所有的结点均无右孩子C只有一个叶子结点D是任意一棵二叉树101在二叉树结点的先序序列，中序序列和后序

27、序列中，所有叶子结点的先后顺序（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 26 页 - - - - - - - - - A都不相同B完全相同C先序和中序相同，而与后序不同D中序和后序相同，而与先序不同102某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A空或只有一个结点B任一结点无左子树C高度等于其结点数D任一结点无右子树103若线性表最常用的操作是存取第i 个元素及其前驱的值，则采用（ ） 存储方式节省时间。A. 单向链表B.双向链表C.单

28、循环链表D.顺序表104对二叉树的结点从1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一双亲的左、右孩子中，左孩子的编号小于右孩子的编号，则可采用（）顺序实现编号。A. 前序遍历B.中序遍历C.后序遍历D.层序遍历105设连通图G 的顶点数n，则 G 的生成树的边数为（ ） 。A.n B.n-1 C.2n D，2n-1 106 若长度为 n 的线性表采用顺序存储结构，删除一元素需要移动元素的平均个数为（）A (n-1)/2 B n C n-1 D n/2 107设 A 是 n*n 的对称矩阵， 将 A 的对角线及对角线上方的元素以列为主的次序存放在一维数组 B1.n(n+1

29、)/2 中，对上述任一元素aij(1 i，jn，且 ij)在 B 中的位置为 ( )。A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-1 108设栈的输入序列为（1，2，3，4） ，则不可能的出栈序列为（）A 1234 B 2134 C 1432 D 4312 109从一棵深度为h 的二叉排序树中查找一个元素时，其时间复杂度为( )。AO(h) BO(h2) CO(log2h) D O(n*log2h) 110一个循环队列的队首和队尾指针分别是front 和 rear,则判别队空的条件是（）A.front+1=rear B.f

30、ront=rear+1 C.front=0 D.front=rear111由两个栈共享一个向量空间的好处是（）A、减少存取时间，降低下溢发生的机率B、节省存取空间，降低上溢发生的机率C、减少存取时间，降低上溢发生的机率D、节省存取空间，降低下溢发生的机率112如下陈述中正确的是（）A、串是一种特殊的线性表B、串的长度必须大于零C、串中元素只能是字母D、空串就是空白串名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 26 页 - - - - - - - - - 113 引入二

31、叉线索树的目的是（）A加快查找结点的前驱或后继的速度B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲D使二叉树的遍历结果唯一114线索二叉树是一种（）结构。A 逻辑B 逻辑和存储C 物理D线性115n 个结点的线索二叉树上含有的线索数为（）A2n Bnl Cnl Dn 116二叉树在线索后，仍不能有效求解的问题是（） 。A前（先）序线索二叉树中求前（先）序后继B中序线索二叉树中求中序后继C中序线索二叉树中求中序前驱D后序线索二叉树中求后序后继117 设 F 是一个森林，B 是由 F 变换得的二叉树。若F 中有 n 个非终端结点，则B 中右指针域为空的结点有（）个。A n-1 B n

32、 C n+1 D n+2 118 如果 T2 是由有序树T 转换而来的二叉树， 那么 T 中结点的后序就是T2 中结点的（） 。A先序B中序C后序D层次序119、无向图G=（ V，E） ，其中： V= a,b,c,d,e,f ,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d) 对该图进行深度优先遍历，得到的顶点序列正确的是（）A.a,b,e,c,d,f B.a,c,f,e,b,d C.a,e,b,c,f,d D.a,e,d,f,c,b 120对序列 15 ，9，7，8， 20，-1，4进行排序，进行一趟后数据的排列变为4，9， -1，8，20，7，15 ；

33、则采用的是（）排序。A. 选择B. 快速C. 希尔D. 冒泡121设哈希表长为14，哈希函数是H(key)=key%11, 表中已有数据的关键字为15,38,61,84共四个，现要将关键字为49 的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）A. 8 B.3 C.5 D.9 122用数组r 存储静态链表, 结点的next 域指向后继 , 工作指针j 指向链中结点,使 j 沿链移动的操作为（）A. j=rj.next B. j=j+1 C. j=j-next D. j=rj-next 123判定一个有图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用( )。A.求关键路径的

34、方法B.求最短路径的Dijkstra 方法C.深度优先遍历算法D.广度优先遍历算法124为查找某一特定单词在文本中出现的位置，可应用的串运算是( ) A.插入B.删除C.串联接D.子串定位名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 26 页 - - - - - - - - - 125设单循环链表中结点的结构为（data，next） ，且 rear 是指向非空的带头结点的单循环链表的尾结点的指针。若要删除链表的第一个结点，则应执行下列哪一个操作？( ) A. s=re

35、ar; rear=rear-next; free(s); B. rear=rear-next; free(s); C. rear=rear-next-next; free(s); D s=rear-next-next; rear-next-next=s-next; free(s); 126下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（） 。A. 直接插入排序B. 快速排序C. 直接选择排序D. 堆排序127在一棵二叉树上，第4 层上的结点数最多为( ) A.31 B.8 C.15 D.16 128 快速排序方法在( )情况下，最不利于发挥其长

36、处A.要排序的数据量太大B.要排序的数据含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数129 对于无向图的生成树，下列说法不正确的是( ) A.生成树是遍历的产物B.从同一顶点出发所得的生成树相同C.生成树是图的极小连通子图D.不同遍历方法所得到的生成树不同130算法分析的目的是( ) A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性131下列陈述中正确的是( ) A. 二叉树是度为2 的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2 的结点D.二叉树中最多只有两棵子树，并且有左右之分132

37、判断有向图是否有回路，除了可以用深度优先遍历算法外，还可以用( ) A. 求关键路径的方法B. 广度优先遍历算法C. 求最短路径的方法D. 拓扑排序133有一个有序表为5,8,10,15,32,41,45,62,75,77,82,95,100, 当二分查找值为82 的数据时( ) 次比较成功。A.1 B.4 C.2 D.8 134下列关于AOE 网的叙述中，不正确的是（） 。A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前完成名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整

38、理 - - - - - - - 第 11 页，共 26 页 - - - - - - - - - C所有的关键活动提前完成，那么整个工程将会提前完成D某些关键活动提前完成，那么整个工程将会提前完成135采用顺序查找方法查找长度为n 的线性表，平均查找长度为( )。A.n B.n/2 C.(n+1)/2 D.(n-1)/2 136下列哪一种图的邻接矩阵是对称矩阵？（）A有向图B无向图CAOV 网DAOE 网137对线性表采用折半查找法，该线性表必须( )。A. 采用顺序存储结构B.采用链式存储结构C.采用顺序存储结构，且元素按值有序D.采用链式存储结构，且元素按值有序138已知二叉树的前序序列为A

39、BDCEFG ，中序序列为DBCAFEG ，则后序序列为( )。A.DCBAFGE B.DCBFGEA C.DCBFEGA D.DCBGFEA 139当利用大小为N 的数组顺序存储一个栈时，假定用top = = N 表示栈空，则退栈时，用（）语句修改top 指针。Atop+; Btop=0; Ctop-;Dtop=N; 140数据序列（2，1，4，9，8， 10，6，20）只能是下列排序算法中的( )的两趟排序后的结果。A. 快速排序B. 冒泡排序C. 选择排序D. 插入排序141从一棵 B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是 （） 。A原树高度加1 B原树高度减1 C

40、原树高度D不确定142在倒排文件中，通常包含有倒排表。A.一个B.多个C.两个D.一个或两个143若用冒泡排序方法对序列10,14,26,29,41,52 从大到小排序，需进行（）次比较。A. 3 B. 10 C. 15D. 25 144循环队列A0.m-1 存放其元素值，用front 和 rear 分别表示队头及队尾，则当前队列中的元素数是A.(rear - front + m)%m B.rear - front + 1 C. rear - front - 1 D.rear-front 145下列说法不正确的是（） 。A图的遍历是从给定的源点出发每一个顶点仅被访问一次B图的深度遍历不适用于有

41、向图C遍历的基本算法有两种：深度遍历和广度遍历D图的深度遍历是一个递归过程146. 一个队列的入队序列是1、2、3、4，则队列的输出序列是（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 26 页 - - - - - - - - - A. 4、3、2、1 B.1、2、3、4 C.1、4、3、 2 D.3、2、4、1 147.在一个单链表中，已知q 所指结点是p 所指结点的前驱结点，若在q 和 p 之间插入s 结点，则执行（）A. s - next = p - next

42、; p-next = s;B.p-next = s-next; s-next = p; C.q-next = s; s-next = p; D.p-next = s; s-next = q; 148下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。A.快速排序B. shell 排序C. 堆排序D.冒泡排序149具有 n 个顶点的有向图最多有（）条边。An B.n(n-1) C.n(n+1) D.n*n 150在数据结构中，逻辑上数据结构可分为（） 。A动态结构和静态结构B线性结构和非线性结构C紧凑结构和非紧凑结构D内部结构和外部结构151在下面的排序方法中，辅助空间为O（

43、n）的是 ( ) 。A希尔排序B. 堆排序C. 选择排序D. 归并排序152不便于插入和删除操作的是（） 。A单链表B双链表C顺序表D循环链表153在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是（） 。AG 中有弧 BG 中有一条从Vi 到 Vj 的路径CG 中没有弧 DG 中有一条从Vj 到 Vi 的路径154下面关于求关键路径的说法不正确的是（） 。A求关键路径是以拓扑排序为基础的B一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D关键活动一定位于关键路径上15

44、5树最适合用来表示（）A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据156具有 4 个顶点的无向完全图至多有（）条边。A.6 B.12 C.16 D.20 157具有 6 个顶点的无向图至少应有（）条边才能确保是一个连通图。A.5 B.6 C.7 D.8 158假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入散列表中，至少要进行多少次探测？( ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 26 页 - -

45、 - - - - - - - Ak-1 次 B. k次 C. k+1次 D. k（k+1）/2 次159设哈希表长为14，哈希函数是H(key)=key%11, 表中已有数据的关键字为15，38，61，84 共四个，现要将关键字为49 的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) A8 B 3 C5 D9 160设有一组记录的关键字为19， 14，23，1，68，20，84， 27，55，11，10，79 ，用链地址法构造散列表，散列函数为H （key）=key MOD 13, 散列地址为1 的链中有 （）个记录。A1 B. 2 C. 3 D. 4名师资料总结 - - -精

46、品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 26 页 - - - - - - - - - 填空题二、填空题1 栈的特点是 ( )，队列的特点是( )。2 设二维数组A-20.30,-30.20, 每个元素占有4 个存储单元 , 存储起始地址为200. 如按行优先顺序存储, 则元素 A25,18的存储地址为( )；如按列优先顺序存储, 则元素A-18,-25的存储地址为( )。3 一个图的 ( 邻接矩阵)表示法是唯一的，而(邻接表)表示法是不唯一的。4 二叉树由 ( )，( )，( )三个基本

47、单元组成。5 树在计算机内的表示方式有( )，( )，( )。6 在二叉树中，指针p 所指结点为叶子结点的条件是( )。7 中缀式 a+b*3+4* （c-d ） 对应的前缀式为( )， 若 a=1， b=2， c=3， d=4， 则后缀式 db/cc*a-b*+的运算结果为 ( )。8 二叉树中某一结点左子树的深度减去右子树的深度称为该结点的( )。9 具有 256 个结点的完全二叉树的深度为( )。10 已知一棵度为3 的树有 2 个度为 1 的结点， 3 个度为 2 的结点， 4 个度为 3 的结点，则该树有 ( )个叶子结点。11 在顺序表 （8,11,15,19,25,26,30,3

48、3,42,48,50）中，用二分（折半） 法查找关键码值20，需做的关键码比较次数为( )。12 深度为 H 的完全二叉树至少有( )个结点；至多有( )个结点； H和结点总数N之间的关系是( )。13 高度为 4 的 3 阶 b-树中，最多有( )个关键字。14 在完全二叉树中，编号为i 和 j 的两个结点处于同一层的条件是( )。15 具有 n 个结点的满二叉树，其叶子结点的个数为( ). 16 已知广义表A=(9,7,( 8,10,(99),12)，试用求表头和表尾的操作Head( ) 和 Tail( )将原子元素99 从 A中取出来 ( )。17 已知广义表L=（ （x,y,z）,a,

49、(u,t,w)）, 则 head(tail(tail(L)= ( )。18 设有二维数组A0.9,0.19,其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A6,6 存储地址为 ( )。19一棵有n 个结点的满二叉树有( 0 )个度为 1 的结点、有 ( (n-1)/2 )个分支（非终端）结点和 ( (n+1)/2 )个叶子，该满二叉树的深度为( )。20假设根结点的层数为，具有个结点的二叉树的最大高度是( n )。21 在一棵二叉树中， 度为零的结点的个数为N0,度为 2 的结点的个数为N2,则有 N0 =( )。22 设只含根结点的二叉树的高度为0，则高度为k

50、 的二叉树的最大结点数为( ),最小结点数为 ( )。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 26 页 - - - - - - - - - 23设有N 个结点的完全二叉树顺序存放在向量A1:N 中，其下标值最大的分支结点为( )。24假定有k 个关键字互为同义词，若用线性探测再散列法把这k 个关键字存入散列表中，至少要进行 ( )次探测。25高度为8 的完全二叉树至少有( )个叶子结点。26已知二叉树有50 个叶子结点，则该二叉树的总结点数至少是( )。27一个