2022年数据结构试题及答案可用 .pdf

《2022年数据结构试题及答案可用 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构试题及答案可用 .pdf（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 一、判断题：1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( )6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。 ( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（）8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（）9、栈和队列逻辑上都是线性表。（）10、单链表从任何一个结点

2、出发，都能访问到所有结点（）11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（）12、快速排序是排序算法中最快的一种。（）13、多维数组是向量的推广。 （）14、一般树和二叉树的结点数目都可以为0。 （）15、直接选择排序是一种不稳定的排序方法。（）16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（）17、 在只有度为0 和度为 k 的结点的 k 叉树中，设度为 0 的结点有 n0 个，度为 k 的结点有 nk 个，则有 n0=nk+1。（）18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（）19、堆栈在数据中的存储原则是先进先出。（）20、队

3、列在数据中的存储原则是后进先出。（）21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（）22、哈夫曼树一定是满二叉树。（）23、程序是用计算机语言表述的算法。（）24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（）25、用一组地址连续的存储单元存放的元素一定构成线性表。（）26、堆栈、队列和数组的逻辑结构都是线性表结构。（）27、给定一组权值，可以唯一构造出一棵哈夫曼树。（）28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（）29、希尔排序在较率上较直接接入排序有较大的改进。但是不稳定的。（）30、在平均情况下，快速排序法最快，堆积排序法最节

4、省空间。（）31、快速排序法是一种稳定性排序法。（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 21 页 - - - - - - - - - 2 32、算法一定要有输入和输出。（）33、算法分析的目的旨在分析算法的效率以求改进算法。（）34、非空线性表中任意一个数据元素都有且仅有一个直接后继元素。（）35、数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。（）36、若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。（）37、若线

5、性表采用顺序存储结构，每个数据元素占用4 个存储单元，第12 个数据元素的存储地址为144，则第 1 个数据元素的存储地址是101。 （）38、若长度为n 的线性表采用顺序存储结构，删除表的第i 个元素之前需要移动表中n-i+1个元素。（）39、符号 p-next 出现在表达式中表示p 所指的那个结点的内容。 （）40、要将指针p 移到它所指的结点的下一个结点是执行语句pp-next 。 （）41、若某堆栈的输入序列为1,2,3,4 ，则 4,3,1,2不可能是堆栈的输出序列之一。（）42、线性链表中各个链结点之间的地址不一定要连续。（）43、程序就是算法，但算法不一定是程序。（）44、线性表

6、只能采用顺序存储结构或者链式存储结构。（）45、线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的。（）46、除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。（）47、稀疏矩阵中0 元素的分布有规律，因此可以采用三元组方法进行压缩存储。（）48、不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。（）49、确定串在串中首次出现的位置的操作称为串的模式匹配。（）50、深度为 h 的非空二叉树的第i 层最多有 2i-1 个结点。（）51、满二叉树也是完全二叉树。（）52、已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。（）53、非空二叉排序树的任意

7、一棵子树也是二叉排序树。（）54、对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。（）55、一个广义表的深度是指该广义表展开后所含括号的层数。（）56、散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。（）57、序列初始为逆序时，冒泡排序法所进行的元素之间的比较次数最多。（）58、已知指针P指向键表 L 中的某结点，执行语句P=P-next 不会删除该链表中的结点。（）59、在链队列中，即使不设置尾指针也能进行入队操作。（）60、如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（）61、设与一棵树T 所对应的二叉树为BT ，则与 T 中的叶子结点所对应的BT

8、中的结点也一定是叶子结点。（）62、 若图 G的最小生成树不唯一， 则 G的边数一定多于n-1， 并且权值最小的边有多条（其中 n 为 G的顶点数）。（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 21 页 - - - - - - - - - 3 63、给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。（）64、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。（）65、程序越短，程序运行的时间就越少。（）66、采用循环链表作为存

9、储结构的队列就是循环队列。（）67、堆栈是一种插入和删除操作在表的一端进行的线性表。（）68、一个任意串是其自身的子串。（）69、哈夫曼树一定是完全二叉树。（）70、带权连通图中某一顶点到图中另一定点的最短路径不一定唯一。（）71、折半查找方法可以用于按值有序的线性链表的查找。（）72、稀疏矩阵压缩存储后, 必会失效掉随机存取功能。 （）73、由一棵二叉树的前序序列和后序序列可以唯一确定它。（）74、在 n 个结点的元向图中, 若边数在于n-1, 则该图必是连通图。 （）75、在完全二叉树中, 若某结点元左孩子,则它必是叶结点。 （）76、若一个有向图的邻接矩阵中, 对角线以下元素均为0, 则

10、该图的拓扑有序序列必定存在。（）77、树的带权路径长度最小的二叉树中必定没有度为1 的结点。（）78、二叉树可以用0度 2 的有序树来表示。 （）79、一组权值，可以唯一构造出一棵哈夫曼树。( ) 80、101，88，46，70，34，39，45，58，66，10）是堆；（）81、将一棵树转换成二叉树后，根结点没有左子树；（）82、用树的前序遍历和中序遍历可以导出树的后序遍历；（）83 、 在 非 空 线 性 链 表 中 由p所 指 的 结 点 后 面 插 入 一 个 由q 所 指 的 结 点 的 过 程 是 依 次 执 行 语 句 ：q-next=p-next;p-next=q。 （）84、

11、 非 空 双 向 循 环 链 表 中 由q 所 指 的 结 点 后 面 插 入 一 个 由p 指 的 结 点 的 动 作 依 次 为 ： p-prior=q, p-next=q-next,q-next=p,q-prior-nextp。 （）85、 删除非空链式存储结构的堆栈( 设栈顶指针为top) 的一个元素的过程是依次执行:p=top,top= p-next,free (p) 。( ) 86、哈希的查找无需进行关键字的比较。（）87、一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。（）88、排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记

12、录）的任意序列，重新排列成一个按关键字有序的序列。 （）89、队列是一种可以在表头和表尾都能进行插入和删除操作的线性表。（）90、在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不与表的个数有关，而与每一块中的元素个数有关。（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 21 页 - - - - - - - - - 4 91、对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和

13、。（）92、无向图的邻接矩阵是对称的有向图的邻接矩阵是不对称的。（）93、具有 n 个顶点的连通图的生成树具有n-1 条边（）二、填空题：1、 数据结构课程讨论的主要内容是数据的逻辑结构、存储结构和_。2、数据结构算法中，通常用时间复杂度和_两种方法衡量其效率。3、一个算法一该具有_,_,_,_和_这五种特性。4、若频繁地对线性表进行插入与删除操作，该线性表应采用_存储结构。5、在非空线性表中除第一个元素外，集合中每个数据元素只有一个_；除最后一个元素之外，集合中每个数据元素均只有一个_。6、线性表中的每个结点最多有_前驱和 _后继。7、_链表从任何一个结点出发，都能访问到所有结点。8、链式存

14、储结构中的结点包含_域， _域。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 后插入一结

15、点 *S，执行的语句 _。15、线性表的链式存储结构地址空间可以_，而向量存储必须是地址空间_。16、栈结构允许进行删除操作的一端为_。17、在栈的顺序实现中，栈顶指针top，栈为空条件 _。18、对于单链表形式的队列，其空队列的F 指针和 R 指针都等于 _。19、若数组 s0.n-1为两个栈s1 和 s2 的共用存储空间，仅当s0.n-1 全满时，各栈才不能进行栈操作，则为这两个栈分配空间的最佳方案是：s1 和 s2的栈顶指针的初值分别为_。20、允许在线性表的一端插入,另一端进行删除操作的线性表称为_。插入的一端为_,删除的一端为_。21、 设数 组Am 为 循 环 队列Q 的 存 储

16、空 间 ， font为 头 指 针 ， rear 为 尾 指 针 ， 判定Q 为 空 队 列 的 条 件名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 21 页 - - - - - - - - - 5 _。22、对于顺序存储的队列，存储空间大小为n，头指针为 F，尾指针为 R。若在逻辑上看一个环，则队列中元素的个数为 _。23、已知循环队列的存储空间为数组data21，且头指针和尾指针分别为8 和 3，则该队列的当前长度_。24、一个串的任意个连续的字符组成的子序列称为该

17、串的_，包含该子串的串称为_。25、求串 T 在主串 S 中首次出现的位置的操作是_。26、在初始为空的队列中插入元素A,B,C,D 以后，紧接着作了两次删除操作，此时的队尾元素是_。27、在长度为n 的循环队列中，删除其节点为x 的时间复杂度为 _。28、已知广义表L 为空，其深度为 _。29、已知一顺序存储的线性表，每个结点占用k 个单元，若第一个结点的地址为DA1 ，则第i 个结点的地址为_。30、设一行优先顺序存储的数组A56 ，A00 的地址为1100，且每个元素占2 个存储单元，则A23 的地址为_。31、设有二维数组A919 ，其每个元素占两个字节，第一个元素的存储地址为100，

18、若按行优先顺序存储，则元素A6,6 的存储地址为 _，按列优顺序存储，元素A6,6 的存储地址为 _。32、在进行直接插入排序时, 其数据比较次数与数据的初始排列_关；而在进行直接选择排序时，其数据比较次数与数据的初始排列_关。33、假设以行为优先存储的三维数组A567 ，A000 的地址为 1100，每个元素占两个存储单元，则A432的地址为 _。34、设二维数组Amn 按列优先存储，每个元素占1 个存储单元，元素A00的存储地址loc(A00)，则 Aij的存储地址loc(Aij)=_。35、稀疏矩阵一般采用_方法进行压缩存储。36、稀疏矩阵可用 _进行压缩存储，存储时需存储非零元的_、_

19、、_。37、若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为 _。38、若一个 n 阶矩阵 A 中的元素满足： Aij=Aji (0=I ,jlink = 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 file:/链表结点定义ElemType data ； file:/数据struct node * Link； file:/结点后继指针 L

20、istNode；非空的循环单链表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） B.O（n）C.O(nlogn) D.O(n2) （）20队和栈的主要区别是_ A.逻辑结构不同 B.存储结构不同C.所包含的运算个数不同 D.限定插入和删除的位置不同（）21链栈与顺序栈相比

21、，比较明显的优点是_ A.插入操作更加方便 B.删除操作更加方便名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 21 页 - - - - - - - - - 10 C.不会出现下溢的情况 D.不会出现上溢的情况（）22在目标串T0n-1= ”xwxxyxy”中，对模式串p0 m-1=”xy”进行子串定位操作的结果_ A.0 B.2 C.3 D.5 （）23已知广义表的表头为A，表尾为 (B,C) ，则此广义表为 _ A.（A,(B,C) ） B. （A,B,C ）C.(A

22、,B,C) D.( A,B,C) （）24二维数组 A按行顺序存储，其中每个元素占1 个存储单元。若A11的存储地址为420，A33的存储地址为 446，则 A55的存储地址为 _ A.470 B.471 C.472 D.473 （）25二叉树中第5 层上的结点个数最多为_ A.8 B.15 C.16 D.32 （）26如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是_ A.有向完全图 B.连通图C.强连通图D.有向无环图（）27对 n 个关键字的序列进行快速排序，平均情况下的空间复杂度为_ A.O（1） B.O（logn ）C.O（n） D.O（nlogn ）（）28对于哈希函数H

23、(key)=key%13 ，被称为同义词的关键字是_ A 35 和 41 B.23和 39 C.15 和 44 D.25和 51 （）29. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为_。A 、 24 B、 48 C 、 72 D、 53 （）30对包含 N 个元素的散列表进行检索，平均检索长度 _ A 、为 o(log2N) B、为 o(N) C 、不直接依赖于N D、上述三者都不是（）31. 向堆中插入一个元素的时间复杂度为_。A 、 O(log2n) B、 O(n) C 、 O(1) D、 O(nlog2n) （）32下面关于图的存储的叙述中，哪一个是正

24、确的。 _ AC B D E F 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 21 页 - - - - - - - - - 11 A用相邻矩阵法存储图, 占用的存储空间数只与图中结点个数有关, 而与边数无关B用相邻矩阵法存储图, 占用的存储空间数只与图中边数有关, 而与结点个数无关C用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关（）33. 输入序列为（ A,B,C,D ） ，

25、不可能得到的输出序列是_. A. (A,B,C,D) B.(D,C,B,A) C.(A, C,D,B) D.(C,A,B,D) （）34. 在长度为 n 的顺序存储的线性表中，删除第i 个元素（1i n）时，需要从前向后依次前移_个元素。A 、n-i B、n-i+1 C 、n-i-1 D、i （）35. 设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为_。A、O(1) B、O(n) C、O(n2) D、O(log 2 n) （）36. 假定一个顺序队列的队首和队尾指针分别为f 和 r，则判断队空的条件为 _。A 、f+1=r B、r+1=f C 、f=0 D、f=r （）37.

26、从堆中删除一个元素的时间复杂以为_。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在一个顺序队列中，队首指针指向队首元素的

27、_位置。A.前一个 B.后一个C.当前 D.最后一个（）41向二叉搜索树中插入一个元素时，其时间复杂度大致力_。A O （1） B O（1og2n）C O（n） D O（nlog2n ）（）42. 算法指的是 _ A.计算机程序 B.解决问题的计算方法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 21 页 - - - - - - - - - 12 C.排序算法D.解决问题的有限运算序列（）43. 线性表采用链式存储时，结点的存储地址_ A.必须是不连续的 B.连续与否

28、均可C.必须是连续的D.和头结点的存储地址相连续（）44. 将长充为 n 的单链表链接在长度为m的单链表之后的算法的时间复杂度为_ A.O（1） B.O（n）C.O（m ） D.O（m+n ）（）45. 由两个栈共享一个向量空间的好处是：_ A.减少存取时间，降低下溢发生的机率 B. 节省存储空间，降低上溢发生的机率C.减少存取时间，降低上溢发生的机率 D. 节省存储空间，降低下溢发生的机率（）46. 设数组 DAtAm作为循环队列SQ的存储空间， front为队头指针， reAr 为队尾指针，则执行出队操作后其头指针 front值为 _ A. front=front+1 B. front=(

29、front+1)%(m-1) C. front=(front-1)%m D. front=(front+1)%m （）47. 如下陈述中正确的是_ A. 串是一种特殊的线性表 B. 串的长度必须大于零C. 串中元素只能是字母 D. 空串就是空白串（）48. 若目标串的长充为n，模式串的长度为n/3，则执行模式匹配算法时，在最坏情况下的时间复杂度是_ A.O（1） B.O（n）C.O（n2） D.O（n3）（）49. 一个非空广义表的表头_ A.不可能是子表B. 只能是子表C.只能是原子 D.可以是子表或原子（）50. 从堆中删除一个元素的时间复杂度为_。A 、 O(1) B、 O(n) C 、

30、 O(log2n) D、 O(nlog2n) （）51. 一棵度为 3 的树中，度为3 的结点个数为2，度为 2 的结点个数为1，则度为 0 的结点个数为 _ A.4 B.5 C.6 D.7 （）52. 从二叉搜索树中查找一个元素时，其时间复杂度大致为_。A 、 O(n) B、 O(1) C 、 O(log2n) D、 O(n2) 0 2 3 3 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 21 页 - - - - - - - - - 13 （）53. 根据 n

31、 个元素建立一棵二叉搜索树时，其时间复杂度大致为_。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，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是_ A.选择排序 B.希尔排序C.归并排序 D.快速排序（）55. 适于对动态查找表进行高效率查找的组织结构是_ A.有序表 B.分块有序

32、表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

33、 = s-link; s-link = p; D. q-link = s; s-link = p; （）59若让元素 1,2,3依次进栈，则出栈次序不可能出现_种情况。A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 （）60. 线性链表不具有的特点是_。A. 随机访问 B. 不必事先估计所需存储空间大小C. 插入与删除时不必移动元素 D. 所需空间与线性表长度成正比（）61在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的_。行号列号元素值地址名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -

34、- - - 名师精心整理 - - - - - - - 第 13 页，共 21 页 - - - - - - - - - 14 （）62. 假定一个顺序队列的队首和队尾指针分别为front和 rear ，存放该队列的数组长度为N，则判断队空的条件为 _。A （front+1 ）% N = rear C front = 0 B （rear+1 ）% N = front D front = rear （）63栈的插入和删除操作在进行() 栈顶 () 栈底() 任意位置 (). 指定位置（）64. 在一个顺序循环队列中，队首指针指向队首元素的_位置。A. 后两个 B. 后一个C. 当前 D.前一个（）6

35、5下面算法的时间复杂度为。int f（int n） if （n 0）return 1；else return nf（n-1 ） ； A O(1) BO(n) C O(n2) DO(n!) （）66. 数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的（）和运算的学科、操作对象、计算方法、逻辑存储、数据映象、结构、关系、运算、算法（）67. 数据结构被形式地定义为(K，R)，其中 K 是（）的有限集合，R是 K上（）的有限集合、算法、数据元素、数据操作、逻辑结韵、操作、映象、存储、关系（）68. 在数据结构中，从逻辑上可以把数据结构分为_ 、动态结构和静态结构、紧凑结构和非紧

36、凑结构、线性结构和非线性结构、内部结构和外部结构（）69. 线性表的顺序存储结构是一种_的存储结构，线性表的链式存储结构是一种_的存储结构、随机存取、顺序存取、索引存取、 HASH 存取（）70. 算法分析的目的是（） ，算法分析的两个主要方面是（）、找出数据结构的合理性、分析算法的效率以求改进、研究算法中的输入和输出的关系、分析算法的易懂性和文档性名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 21 页 - - - - - - - - - 15 、空间复杂性和时间复杂

37、性、可读性和文档性、正确性和简明性、数据复杂性和程序复杂性（）71. 计算机算法指的是（） ，它必具备输入、输出和（）等五个特性、计算方法、排序方法、解决莱一问题的有限运算序列、调度方法、可执行性、可移植性和可扩充性、确定性、有穷性和稳定性、可执行性、确定性和有穷性、易谩性、稳定性和安全性（）72. 线性表若采用链表存储结构时，要求内存中可用存储单元的地址_ 、必须是连续的、部分地址必须是连续的、一定是不连续的、连续不连续都可以（）73. 在以下的叙述中，正确的是_ 、线性表的线性存储结构优于链表存储结构、栈的操作方式是先进先出、二维数组是它的每个数据元素为一个线性表的线性表、队列的操作方式是

38、先进后出（）74. 一个数组元素Ai 与_的表示等价。A 、 *(A+i) B、 A+i C 、 *A+i D、 &A+i （）75. 对于两个函数，若函数名相同，但只是_不同则不是重载函数。A 、 参数类型 B、 参数个数C 、 函数类型 D、函数变量（）76. 若需要利用形参直接访问实参，则应把形参变量说明为_参数A 、 指针 B、 引用C 、 值D、函数（）77. 下面程序段的时间复杂度为_。 for(int i=0; im; i+) for(int j=0; jn; j+) Aij=i*j; A 、 O(m2) B、 O(n2) C 、 O(m*n) D、 O(m+n) （）78. 执

39、行下面程序段时，执行S 语句的次数为 _。 for(int i=1; i=n; i+) for(int j=1; jnext = 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 =

40、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 、

41、O(1) B、 O(n) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 21 页 - - - - - - - - - 17 C 、 O(n2) D、 O(log2n) （）88栈的插入与删除操作在_进行。A 、栈顶 B、栈底C 、任意位置 D、指定位置（）89当利用大小为N的一维数组顺序存储一个栈时，假定用top=N 表示栈空，则向这个栈插入一个元素时，首先应执行 _语句修改 top 指针。A、top+ B、top- C、top=0 D、top （）90若让元素1，2

42、，3 依次进栈，则出栈次序不可能出现_种情况。A 、3，2，1 B、2，1，3 C 、3，1，2 D、1，3，2 （）91在一个循环顺序队列中，队首指针指向队首元素的_位置。A 、前一个 B、后一个C 、当前 D、后面（）92当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为_。A 、N-2 B、N-1 C 、N D、N+1 （）93从一个循环顺序队列删除元素时，首先需要_。A 、前移一位队首指针 B、后移一位队首指针C 、取出队首指针所指位置上的元素 D、取出队尾指针所指位置上的元素（）94假定一个循环顺序队列的队首和队尾指针分别为f 和 r ，则判断队空的条件是_。A 、f

43、+1=r B、r+1=f C 、f=0 D、f=r （）95假定一个链队的队首和队尾指针分别为front和 rear ，则判断队空的条件是_。A 、front=rear B、front!=NULL C 、rear!=NULL D、front=NULL 一、判断题：1、 2 、 3 、 4 、5、 6 、 7 、 8 、 9 、 10 、 11 、12、13、 14 、 15、 16 、 17 、 18 、 19 、 20 、 21 、 22 、 23 、 24 、 25 、 26 、 27、 28 、 29 、 30 、 31 、 32 、 33 、 34 、 35 、 36 、 37 、 3

44、8 、 39、 40 、 41 、 42 、 43 、 44 、 45 、 46 、 47 、 48 、 49 、50、 51 、 52 、 53 、 54 、 55 、 56 、 57 、 58 、 59 、 60 、 61 、 62 、 63 、 64 、 65 、 66、 67 、 68 、 69 、 70 、 71 、 72 、 73、 74 、 75 、 76 、 77 、 78 、 79 、 80 、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 21 页

45、- - - - - - - - - 18 81 、 82 、 83、 84 、 85 、 86 、 87 、88、 89 、 90 、91、 92 、 93 、二、填空题：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、s0，sn-1 20、队列，队尾队头21、Q-font=Q-re

46、ar 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、有，无名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 21 页 - - - - - - - - - 19 33、1482 34、loc（a00）+(j*m+i)*1 35、三元组

47、36、三元组，行号，列号，值37、三对角矩阵38、上（下）三角矩阵39、i*（i-1）/2+j-1 (ij)，j*(j-1)/2+i-1 (ij) 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 6

48、6、路径名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 21 页 - - - - - - - - - 20 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、索引表，子表，和三、选择题：1. A 2.C 3. A 4. D 5.

49、D 6.C 7.B 8. B 9. D 10.D 11.A 12.C 13 C 14.A 15. B 16. B 17.C 18.A 19. B 20 D 21 D 22 C 23 B 24 C 25 C 26 D 27 D 28 D 29.D 30C 31 A 32 A 33. D 34.A 35. D 36. D 37. B 38 A 39 D 40 A 41 B 42. D 43. B 44.C 45. B 46. D 47.A 48. B 49. D 50. C 51.C 52.C 53. D 54. D 55.C 56.A 57. B 58. D 59C 60.A 61 62. D

50、63 64. D 65 B 66. DA 67. DA 68. 69. BA 70. CA 71. CB 72. 73. 74.A 75. C 76. A 77.C 78. D 79.B 80B 81 A 82. D 83 D 84 D 85 B 86.A 87. B 88A 89 B 90 C 91 A 92 B 93 B 94 D 95A 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 21 页 - - - - - - - - - 21 名师资料总结 - - -精品