北京邮电大学数据结构期末考试试题

北京邮电大学数据结构期末考试试题(A卷)

一．单项选择题（2分/题）

1．一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（A）。

A.23415

B.54132

C.31245

D.14253

2．设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（D）。

A.r-f

B.r-f+1

C.(r-f) mod n +1

D.(r-f+n) mod n 3．二叉树在线索化后，仍不能有效求解的问题是（D）。

A.先序线索二叉树中求先序后继

B. 中序线索二叉树中求中序后继

C.中序线索二叉树中求中序前驱

D. 后序线索二叉树中求后序后继

4．求最短路径的FLOYD算法的时间复杂度为（D）。

A.O(n)

B.O(n+e)

C.O(n2)

D.O(n3)

5．一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（B）。

A.0

B.1

C.2

D.不确定

6．数组A[1..5,1..6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（A）。

A.1140

B.1145

C.1120

D.1125

7．在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（A）。

A.快速排序

B.希尔排序

C.冒泡排序

D.堆排序8．对有18个元素的有序表做折半查找，则查找A[3]的比较序列的下标依次为（C）。

A.1-2-3

B.9-5-2-3

C.9-5-3

D. 9-4-2-3

9．下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（D）。

A.堆排序

B.冒泡排序

C.快速排序

D.直接插入排序10．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（B）型调整以使其平衡。

A.LL

B.LR

C.RL

D.RR

二．判断题（1分/题）

1.线性表的长度是线性表所占用的存储空间的大小。 F

2.双循环链表中，任意一结点的后继指针均指向其逻辑后继。F

3.在对链队列做出队操作时，不会改变front指针的值。F

4.如果两个串含有相同的字符，则说它们相等。F

5.如果二叉树中某结点的度为1，则说该结点只有一棵子树。T

6.已知一棵树的先序序列和后序序列，一定能构造出该树。F

7.图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。T

8.图G的拓扑序列唯一，则其弧数必为n-1（其中n为顶点数）。F

9.对一个堆按层次遍历，不一定能得到一个有序序列。T

10.直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为O(n2)。T

三．填空题（2分/空）

1．已知完全二叉树的第8层有8个结点，则其叶子结点数是（68）。68+8-4 2．将下三角矩阵A[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7,5]的地址是（1100）。

3．有n个顶点的强连通有向图G至少有（n）条弧。

4．有n个结点并且其高度为n的二叉树的数目是（2^（n-1））。

5．高度为8的平衡二叉树的结点数至少是（54）。

6．3个结点可构成（5）棵不同形态的树。

（以上是部分题目和答案，其他题目会在近期献上）

数据结构期末考试试题及答案

《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 、 1. 对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 (c )。 (A)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■

北邮算法与数据结构习题参考标准答案

作业参考答案 一、（带头结点）多项式乘法C= A×B： void PoｌyAdd ( list &C,liｓｔR) ／／R为单个结 点 { p=C; while(（!p-＞ｎeｘt) &＆(p->nexｔ-＞eｘp>Ｒ->eｘp)) p=p－>ｎｅｘt； ｉf (（p->next) ｜｜(ｐ->neｘt->ｅｘp<Ｒ-＞eｘp)) {R－＞nｅxt=ｐ->ｎeｘｔ;p->neｘｔ=Ｒ;} ｅlse { ｐ-＞nｅxt－＞inf +=R->inｆ;delｅte R; if （！p－>neｘｔ-＞iｎｆ) { R=ｐ-＞nｅxt；p－>next=R->ｎext;deleｔe R; ｝ } } ｖoｉｄPｏlｙMul （lｉst A, lｉst B，lｉst &C ） ｛ C=new sｔｒuct nｏｄe; Ｃ-＞neｘt=ＮUＬL；q=B->next; Wｈｉｌe (q ） { p＝A->neｘｔ; whiｌｅ（p ) { ｒ= new struct node；r->ｅxｐ= p->ｅxp ＋ｑ－>exp； r-＞ｉnf ＝ｐ-＞inf* q－>iｎf; PolyAｄd(C，r）； p=p-＞next; ｝ q=q－>ｎext; ｝ } 二、梵塔的移动次数: 已知移动次数迭代公式为：M ( ｎ)= 2M (n－1 ) + 1 初值为: Ｍ( 0 ) ＝0 则：M （n）＝ 2 （2M

（n-2 ) + 1) + 1 =4M( n-2 )+ 3 = 8Ｍ(n－3 )+ 7 =２i M ( n-i ) + 2i– 1 若n＝ｉ，则Ｍ（n-ｎ) ＝0,故：M ( n ) =2ｎM( ｎ-n）+2n–1 =2n– 1 所以,梵塔的移动次数为2ｎ– 1次。 三、简化的背包问题： ｖoid Pacｋ( int ｍ, int i, ｉnt t ）// 初始值为:１１t ｛ for (k=i; k<＝ｎ; k＋＋) { soｌutiｏｎ[m] = ｗeighｔ[k]; if( t == weigｈｔ[k]) ｛ for ( j=1; ｊ<=m；j+＋) cout<＜ｓolutｉon［j]；coｕt< wｅight［k]) Pａck （ｍ＋１，k ＋1，t - wｅighｔ[ｋ] ); } } 四、判断括号是否配对： int Correcｔ( sｔrinｇs ) { Iｎiｓtack（Ｑ）; ｆoｒ( ｉ=0；s［i］＝= ‘=’；i++ )// 表达式以‘＝’结束 { swｉｔch (s[i] ) { cａsｅ‘(’: ｃａｓｅ‘[’: ｃase ‘｛’:

2017年数据结构期末考试题及答案A

2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出

8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点

数据结构 期末考试复习题及答案

1.什么是最小生成树？简述最小生成树的Prime算法的思想。 答：最小生成树就是构造一棵生成树，使得树上各边的代价之和最小。 普里姆算法(Prim)的基本思想： 从连通网络N = { V, E }中的某一顶点u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 2.简述AOV网络中为何不能出现回路，如何判断AOV网络是否有回路？ 答：在AOV网络中，如果活动vi必须在vj之前进行，则称为存在有向边；在AOV网络中不能出现有向回路，如果出现了，则意味着某项活动应以自己作为先决条件。 如何检查AOV网是否存在有向环： 检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。（1）这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 （2）如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV 网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。

3.为何需要采用循环队列？n个空间的循环队列，最多存储多少个元素？为什 么？ 答：循环队列以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用，所以采用循环队列。 n个空间的循环队列，最多存储n-1个元素，那是为了区别循环队列的队空和队满的条件。队空的条件是Q.front==Q.rear，而队满的条件是(Q.rear+1)%N==Q.front(N是数组中单元的总数)，因此，Q.rear所指向的数组单元处于未用状态。所以说，N个单元的数组所存放的循环队列最大长度是N-1。 4.简述堆的删除算法，其删除的是那个值？ 答：堆的删除算法：首先，移除根节点的元素（并把根节点作为当前结点）比较当前结点的两个孩子结点的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的孩子结点作为当前结点，并再比较当前结点的孩子的大小，以此循环，直到最后一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数，则退出循环。最后把最后叶子结点的元素移给当前结点。 在堆的算法里面，删除的值为根值。 5.线索二叉树中，什么是线索，它是否唯一？可有根据什么顺序得到？

数据结构期末考试题及答案

数据结构期末考试题及答案 、选择题 1.在数据结构中, 从逻辑上能够把数据结构分为 A. 动态结构和静态结构 B ．紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2. 数据结构在计算机内存中的表示是指 A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系 3. 在数据结构中, 与所使用的计算机无关的是数据的 结构。 A.逻辑 B.存储 C.逻辑和存储 D.物理 4. 在存储数据时, 一般不但要存储各数据元素的值, 而且还 要存储C A. 数据的处理方法 B. 数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5.在决定选取何种存储结构时般不考虑A 。 A. 各结点的值如何 B. 结点个数的多少 C.对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6.以下说法正确的是 A. 数据项是数据的基本单位

B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据能够有相同的逻辑结构7．算法分析的目的是C , 算法分析的两个主要方面是A 。 (1) A.找出数据结构的合理性 和输出的关系 C. 分析算法的效率以求改进 档性 ( 2) A .空间复杂度和时间复杂度 C. 可读性和文档性 性 8. 下面程序段的时间复杂度是 s = 0; for( I = 0; i v n; i + + ) for( j = 0; j v n; j ++ ) s +二B[i][j]; sum = s ; 9. 下面程序段的时间复杂度是 for( i = 0; i v n; i + + ) for( j = 0; j v m; j ++ ) B .研究算法中的输入 C .分析算法的易读性和文 B .正确性和简明性D .数据复杂性和程序复杂 O( n2) 。 O( n*m) 。

北邮算法与数据结构习题参考答案

北邮算法与数据结构习题参考答案

作业参考答案 一、（带头结点）多项式乘法 C = A×B： void PolyAdd ( list &C, list R) // R 为单个结点 { p=C; while ((！p->next) && (p->next->exp>R->exp)) p=p->next; if ((p->next) || (p->next->expexp)) { R->next=p->next; p->next=R; } else { p->next->inf += R->inf; delete R; if ( ! p->next->inf ) { R=p->next; p->next=R->next; delete R; } } } void PolyMul ( list A, list B, list &C ) { C=new struct node; C->next=NULL; q=B->next; While ( q ) { p=A->next; while ( p ) { r = new struct node; r->exp = p->exp + q->exp; r->inf = p-> inf * q->inf; PolyAdd(C, r); p=p->next; } q=q->next; } } 二、梵塔的移动次数： 已知移动次数迭代公式为：M ( n ) = 2M ( n-1 ) + 1 初值为：M ( 0 ) = 0 则：M ( n ) = 2 ( 2M ( n-2 ) + 1 ) + 1 = 4M ( n-2 ) + 3 = 8M ( n-3 ) + 7 = 2i M ( n-i ) + 2i– 1 若n=i ,则M ( n-n ) = 0,故：M ( n ) = 2n M ( n-n ) + 2n– 1 = 2n– 1

数据结构复习资料,java数据结构期末考试

第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长

《数据结构》期末考试题及答案

2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序

数据结构(c语言版)期末考试复习试题

《数据结构与算法》（c语言版）期末考复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位

B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i

2017数据结构期末考试试题及答案

2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1.

数据结构》期末考试试题及答案 1 单选题（每题 2 分，共 20 分） 1. 栈和队列的共同特点是 （ ）。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列，在进行插入运算时 （ ）. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构？ （ ） A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（io ）, A[2][2]存放 若有18个元素的有序表存放在一维数组 A[19]中，第一个元素放A[1]中, 现进行二分查找，则查找 A [3]的比较序列的下标依次为（ A. 1 ， 2， 3 B. 9， 5， 2， 3 C. 9， 5， 3 D. 9， 4， 2， 3 8. 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O （1） B. O （n ） C. O （ 1 og 2n ） D. O （n2） 9. 对于线性表（ 7， 34， 55， 25， 64， 46， 20， 10）进行散列存储时，若选 用 H （K ）=K %9 作为散列函数，则散列地址为 1 的元素有（ ）个， 位置在 676（10），每个元素占一个空间， 表示用 10 进制表示。 问 A[3][3] （10）存放在什么位置？脚注 （10） 5. A ．688 B ．678 C ． 692 D ． 696 树最适合用来表示 （ ）。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 （ ）. A ．2-1 B.2K+1 C.2K-1 D. 2k-1 7.

数据结构期末考试试题A卷(完成,不知对不对)

第 1 页，共 11 页 任课教师签名： 命题教师签名： 系主任签名： 主管院长签名： 湛江师范学院2007年－2008学年度第1学期 期末考试试题A 卷 (考试时间:120分钟) 考试科目： 数据结构 请将所有答案填写在答题卡上，交卷时请将所有试卷上交 一、单选题(每小题2分，共40分) 1．下列算法的时间复杂度是（ B ）。 for ( i=0; inext==L C L->next==p D p->next==NULL 4．4个元素进S 栈的顺序是A 、B 、C 、D ，进行两次Pop(S,x)操作后， 栈顶元素的值是（ B ）。 A A B B C C D D 5．经过下列栈的运算后GetTop(S)的值是（ A ）。 InitStack(s); Push(s,a); Push(s,b); Pop(s); A a B b C 1 D 2

6．栈的特点是（B ）。 A 先进先出 B 后进先出 C 后进 后出 D 不进不出 7．经过下列运算后GetHead(Q)的值是（ A ） InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); A a B b C 1 D 2 8．一维数组的元素起始地址loc[0]=1000，元素长度为4，则loc[2]为（ C ）。 A 1000 B 1010 C 1008 D 1020 9．二叉树第i层上最多有（ C ）个结点。 A 2i B 2i-1 C 2i-1 D i2 10．满二叉树（ A ）二叉树。 A 一定是完全 B 不一定是完全 C 不是 D 不是完全 11．二叉树按二叉链表存储，每个结点包含三个域（lchild、data、rchild），若p指针指向二叉树的根结点，经过运算while ( p->rchild!=null ) p=p->rchild，则（ A ）。 A p指向二叉树的最右下方的结点 B p指向二叉树的 最左下方的结点 C p仍指向根结点 D p为null 12．在具有n个结点的完全二叉树中，结点i(2i

北邮 计算机学院 数据结构 期末试题

O S TEST 1．Fill in the blanks with the proper words.( 10 cents) 1. Operating system is a program that acts as an intermediary between _____ and ______. 2.To prevent user programs from interfering with the proper operation of the system, the hardware has two modes: _________, __________. 3.___________ is the separation of user ______ from physical memory. User would be able to write programs for an extremely large __________ space, simplifying the programming task. 4.The file system consists of two distinct parts: _______, each storing related data and _______, which organizes and provides information about all the files in the system. 5.System call provide the interface between _____ and _____ . 6.________ provide an object-oriented way of implementing file systems, and it allows the same system call interface (the API) to be used for different types of file systems. 7. A process is a program in execution. A process needs certain resources, including ____, ______, files, and ______ to accomplish its task. 8.Disk-scheduling algorithms can improve _________, _________, and ________. 9.The primary distinction between long-term scheduler and short-term scheduler is _______. 10.The device drivers present a uniform device-access interface to ______ , much as system calls provide a standard interface between the application and the operating system. 2. Choose the best answer, and each blank has one answer. (23 cents) 1. Operating system is a kind of(1) , (2) is not the main problem it handles. (1). A. Application software; B. System software; C. Common software; D. Software package; (2). A. managing the bar-machine; B. designing, providing the interface between user program and hardware system; C. managing the information resource of the computer; D. the compiling of the high-level program-designing language. 2. The utilization of the memory can be improved by __(1)___. Its basic task is __(2)_ for each program; and each program can run safely and separately, main by __(3)____. (1), (3): A. memory-allocating B. memory-protecting

《数据结构》期末考试试卷

广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 2 分，共 40 分） 1.计算机识别、存储和加工处理的对象被统称为（）。 A ．数据 B ．数据元素 C ．数据结构 D ．数据类型 2.数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括（）三方面内容。 A ．数据的逻辑结构、数据的存储结构、数据的描述 B ．数据的逻辑结构、数据的存储结构、数据的运算 C ．数据的存储结构、数据的运算、数据的描述 D ．数据的逻辑结构、数据的运算、数据的描述3．数据的逻辑结构包括（）。 A ．线性结构和非线性结构 B ．线性结构和树型结构 C ．非线性结构和集合结构

D ．线性结构和图状结构 4.（）的特征是：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。 A ．线性结构 B ．非线性结构 C ．树型结构 D ．图状结构 5. 评价一个算法时间性能的主要标准是（）。 A ．算法易于调试 B ．算法易于理解 C ．算法的稳定性和正确性 D ．算法的时间复杂度 6. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i

数据结构期末考试试题及答案

贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；jnext; p->next= Q.rear->next; （D）、p=Q->next; Q->next=p->next; 9． Huffman树的带权路径长度WPL等于（） （A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和 （C）、各叶子结点的带权路径长度之和（D）、根结点的值 10．线索二叉链表是利用（）域存储后继结点的地址。 （A）、lchild （B）、data （C）、rchild （D）、root 二、填空题

数据结构试卷(20050108)

数据结构期末试卷2005/01/08 班级__________姓名___________学号_______成绩___________ 一、填空和选择(共15分) 1．在n个元素的顺序表中插入或删除一个元素，需平均移动______个元素。 2．在双向链表p所指结点之后插入s所指结点的操作是______________ A．p→right=s; s→left=p; p→right→left=s; s→right=p→right; B．p→right=s; p→right→left=s; s→left=p; s→right=p→right; C．s→left=p; s→right=p→right; p→right=s; p→right→left=s; D．s→left=p; s→right=p→right; p→right→left=s; p→right=s; 3．在数据结构中，从逻辑上可以把数据结构分成_________。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 4．算法分析的两个主要方面是____。 A．空间复杂性和时间复杂性B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 5．线性表的顺序存储结构是一种______的存储结构，线性表的链式存储结构是一种______的存储结构。 A．随机存取B．顺序存取C．索引存取D．散列存取 6．向量、栈和队列都是______结构，可以在向量的________位置插入和删除元素；对于栈只能在_________插入和删除元素；对于队列只能在_______插入元素和在_______删除元素。 7．设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为___________。 A．r-f B．r-f+1 C．(r-f) mod n +1 D．(r-f+n) mod n 8．将下三角矩阵A[7,7]的下三角部分逐行地存储到起始地址为1000的内存单元中(下标从0开始，不存储上三角部分)，已知每个元素占4个单元，则A[5,4]的地址是_____________。 9．某二叉树的前序遍历结点访问顺序是abdgcefh, 中序遍历的结点访问顺序是dgbaechf, 则其后序遍历的结点访问顺序是______ A.bdgcefha B.gdbecfha C.bdgaechf D.gdbehfca

数据结构期末考试试题含答案

2005年－2006学年第二学期“数据结构”考试试题（A） 姓名学号(序号)_ 答案隐藏班号 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1．数据的运算a 。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 答：A。 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 答：参见本节要点3。本题答案为：A。 3. 在顺序表中删除一个元素的时间复杂度为 c 。 A.O(1) B.O(log2n) C.O(n) D.O(n2) 答：C。 4．以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 解 D。 5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。

A.edcba B.decba C.dceab D.abcde 答：C。 6. 循环队列qu的队空条件是 d 。 A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front 答：D。 7. 两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 答：B。 8. 用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是c 。 A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90, 80 C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94, 40 答：C。 9. 以下序列不是堆（大根或小根）的是 d 。 A.{100,85,98,77,80,60,82,40,20,10,66} B.{100,98,85,82,80, 77,66,60,40,20,10} C.{10,20,40,60,66,77,80,82,85,98,100} D.{100,85,40,77,80, 60,66,98,82,10,20}

2015年数据结构期末考试题及答案

2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。

s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。