2012广东省数据结构与算法理论考试试题及答案

数据结构与算法期末考试题及答案一、选择题1. 用于分离由加权无向边组成的完全连通图中连通分量中不相邻顶点的单纯形算法是（C）A. 最小生成树算法B. 广度优先搜索算法C. 最大流算法D. 关键路径算法2. 要设计一个使用图来表示的行业里的公司的决策问题，图的顶点应该表示（B）A. 公司拥有的资源B. 公司所面对的决策选择C. 公司内部的组织结构D. 公司的竞争对手3. 算法的计算时间复杂度O(log2n)中的n表示（A）A. 求解问题规模B. 求解算法所处理的数据量C. 求解问题中所涉及的参数量D. 求解算法所进行的求解步骤4. 以树形结构存储的优先队列中元素出队的操作时间复杂度是（C）A. O(1)B. O(n)C. O(log2n)D. O(n2)5. 以下关于贝尔曼-福特算法的描述错误的是（A）A. 贝尔曼-福特算法是求图 G=(V,E)最小生成树的法B. 贝尔曼-福特算法克服了Prim算法因存储顶点增量重复而带来的内存浪费C. 求解过程中，要维护贝尔曼-福特树中任意两个顶点之间的最短距离D. 贝尔曼-福特算法可以解决单源最短路径问题二、简答题1. 请说明拓扑排序的概念，以及如何使用拓扑排序解决求解关键路径的问题。

拓扑排序是指对有向无环图进行排序，得到一个顶点的线性序列，使得对于图中的每条有向边（u,v），均有u在v之前。

拓扑排序可用于求解关键路径，首先对所有活动按照拓扑排序的方法进行排序，计算该活动的最早开始时间ESi和最晚开始时间LSi，若ESi=LSi，则此活动运行期间不能延迟，为关键活动；若ESi≠LSi，则此活动可以合理推迟，不为关键活动。

875华南理工大学2012年攻读硕士学位研究生入学考试试卷（请在答题纸上做答，试卷上做答无效，试后本卷必须与答题纸一同交回）科目名称：数据结构适用专业：软件工程(专硕)本卷满分：150分共 3 页一、填空题(30分)1.在2n2，30 log n，5n，2n中，当n变大时所对应的增长率最有效率的算法是________。

2.数据结构中评价算法的两个重要指标是_______和_______。

3.设三位数组a【4】【5】【6】（下标从0开始）每个元素长度为2，则a【2】【3】【4】的地址是__________（设首元素地址为1000，数据以行优先存储）。

4.在双向链表结构中，若要求在p指针所指借点之前插入指针为s所指的借点，需执行下列语句_________；s^.prior:=p^.prior；_________；__________。

5.设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后输出序列为________,栈顶指针的值是_______，设栈为顺序栈，每个元素占四个字节。

6.快速排序算法的平均情形的算法时间复杂度是________。

7.设n0为哈夫曼输的叶子节点数目，则该哈夫曼树共有_______个节点。

8.一棵高度为5的完全二叉树，最少有____个结点。

9.3个节点的二叉树有____种不同形状。

10.具有n个顶点的有向连通简单平面图最少有_____条边，最多有_________条边。

二、判断题(20分)1.快速排序是一种交换排序。

2.抽象数据类型与计算机内部表示和实现无关。

3.顺序存方式的优点是存储密度大,且插入,删除运算效率高。

4.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的存储结构。

5.一个带权的无向连通图的最小生成树不一定唯一。

6.由二叉树的前序序列和中序序列可以唯一确定一棵二叉树。

数据结构试题6一、单项选择题（每小题3分，共30分）1．设栈的输入序列是1、2、3、4，则______不可能是其出栈序列。

( )[A] 1234 [B] 2134 [C] 1432 [D] 43122．在一个具有n个结点的线性链表中查找某个结点，若查找成功，需要平均比较_____个结点。

( )[A] n [B] n/2 [C] (n+1)/2 [D] (n-1)/23．设每个字符占一个字节，二维数组A中每个元素有6个字符组成，其行下标从0到9，列下标从0到3，元素_____当A按行优先存储起始地址与当A按列优先存储的起始地址相同。

( )[A] A[3][0] [B] A[3][1] [C] A[3][2] [D] A[2][3]4．具有2000个结点的非空二叉树的最小深度为_______。

( )[A] 9 [B] 10 [C] 11 [D] 125．已知某二叉树的后根序列是dabec，中根序列是debac，则先根序列是_____。

( )[A] acbed [B] decab [C] deabc [D] cedba6. 无向图中所有边的数目等于所有顶点的度数之和的_____倍。

( )[A] 1 [B] 2 [C] 1/2 [D] 不一定7．递归函数F(n)=F(n-1)+n+1(n>1)的递归体是_______。

( )[A] F(0)=0 [B] F(1)=1 [C] F(n)=n+1 [D] F(n)=F(n-1)+n+18. 若需要在O(nlog2n)的时间内完成对n个元素的排序，且要求排序是稳定的,则可选择的排序方法是_______。

( )[A] 快速排序[B] 堆排序[C] 归并排序[D] 直接插入排序9．在对n个元素的序列进行排序时,堆排序所需要的附加存储空间是__。

( )[A] O(1) [B] O(log2n) [C] O(n) [D] O(n log2n)10．假定有K个关键字互为同义词，若用线性探查法把这K个关键字存入散列表中，则总的探查次数至少为______。

数据结构复习参考2012年一、单选题：。

1、在表长为n的顺序表上做删除运算，在等概率的情况下，平均要移动的结点数为（）。

（A）n/2 (B) （n-1）/2 (C) n/3 (D) n/42、一个队列的入队序列是a，b，c，d，则队列的输出序列是（）。

（A）dcba （B）abcd （C）adcb （D）cbda3、设长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为（）。

（A）O(1) (B) O(lgn) (C) O(n) （D）O(n2)4、将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次堆结点编号，根结点的编号为1。

编号为49的结点X的双亲的编号为（）。

(A) 24 (B) 25 (C) 23 (D) 无法确定5、设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）。

(A)front=front+1 (B)front=(front+1)%(m-1)(C)front=(front-1)%m (D)front=(front+1)%m6、空串是指（）。

（A）空白串（B）长度为零的串（C）长度为1的串（D）仅由空格组成的串7、设n阶方阵是一个上三角矩阵，则需存储的元素个数为( )。

（A）n (B) n2 (C)n2/2 (D)n(n+1)/28、有m个叶结点的哈夫曼树所具有的结点数为（）。

(A)m (B) m+1 (C) 2m (D) 2m-19、在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )。

(A)e (B)2e (C)n2－e (D)n2－2e10、一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。

(A) 250 (B) 501 (C)254 (D)50511、设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

(A)5 (B)6 (C)7 (D)812、无向图的邻接矩阵是一个( )。

第二部分数据结构(共 100分)一、单项选择题 (本大题共12小题，每小题2分，共24分)1、双向链表的一个结点有( B )个指针。

A、lB、2C、0D、32、在n个结点的顺序表中，算法的时间复杂度都是O(1)的操作是( A )。

A、访问第i个结点(l≤i≤n)和求第i个结点的直接前趋(l≤i≤n)B、在第i个结点后插入一个新结点(l≤i≤n)C、删除第i个结点(l≤i≤n)D、将n个结点从小到大排序3、在队列中存取数据的原则是( A )。

A、先进先出B、后进后出C、先进后出D、不进不出4、在栈中，出栈操作的时间复杂度为( A )。

A、O(1)B、O(log2n)C、O(n)D、O(n2)5、设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为( C )。

A、O(1)B、O(log2n)C、O(n)D、O(n2)6、如果二叉树的叶结点数为n0，则具有双分支的结点数也等于( D )。

A、n0+1B、n0C、2*n0D、n0-17、一棵二叉树满足下列条件:对任一结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。

现采用( B )遍历方式就可以得到这棵二叉树所有结点的递增序列。

A、先根B、中根C、后根D、层次8、用邻接表表示图进行深度优先遍历时，其非递归算法通常采用( A )来实现算法。

A、栈B、队列C、树D、图9、广度优先遍历类似于二叉树的( D )。

A、先序遍历B、中序遍历C、后序遍历D、层次遍历10、在一个有向图中，所有顶点的人度之和等于所有顶点的出度之和的( B )。

A、1/2倍B、l倍C、2倍D、4倍11、任何一个带权无向连通图的最小生成树( B )。

A、只有一棵B、一棵或多棵C、一定有多棵D、可能不存在12、设非空单链表的数据域都为data，指针域都为next，指针p指向单链表的第i个结点，s指向生成的新结点，现将s结点插入到单链表中，使其成为第i结点，下列算法段能正确完成上述要求的是( C )。

信息与通信工程学院数据结构期中考试试题一．单项选择题（总计20分，2分/题）1.在线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表2.链表不具有的特点是（）。

A.可随机访问任一元素B.插入、删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比3.一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（）。

A.23415B.54132C.31245D.142534.设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（）。

A.r-fB.r-f+1C.(r-f) mod n +1D.(r-f+n) mod n5.数组A[1..5,1..6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（）。

A.1140B.1145C.1120D.11256.数据结构被形式地定义为（D，R），其中D是①的有限集合，R是D上的②的有限集合。

7.①A．算法B．数据元素C．数据操作D．逻辑结构8.②A．操作B．映象C．存储D．关系9.在单链表中p元素后面插入q指针所指的新元素时应进行的操作是( )。

A. p->next = q, q->next = p->nextB. q->next = p->next, p->next = qC. p ->next->next = q, q->next = pD. q->next = p, p->next->next = q10.在下面这段代码中，假定赋值运算为主要操作，那么它的时间复杂度为（）。

for(I=0；I<n；I++)for(J=I；J<n；J++) {X[I * n +J]= 0;}A．O(n) B. O(2n) C. O(n2) D. O(nlog n)11.不带头结点的单链表head为空的判定条件是a.head=NULLb. head - >next=NULLc. head- >next=headd. head!=NULL12.一个栈的入栈序列为a,b,c,d,e，那么不可能出现输出序列为( )A. edcba B decba C dceab D abcde二．判断题（总计15分，1分/题）1.（×）串长度是指串中不同字符的个数。

算法是一组严谨地定义运算顺序地规则算法地基本要素一是对数据对象地运算和操作，二是算法地控制结构算法设计基本方法列举法、归纳法、递推、递归、减半递推算法地复杂度包括时间复杂度和空间复杂度时间复杂度执行算法所需地计算工作量空间复杂度执行算法所需地内存空间数据结构相互有关联地数据元素地集合.如春、夏、秋、冬；、、、、...；父亲、儿子、女儿等都是数据元素.前件数据元素之间地关系，如父亲是儿子和女儿地前件后件如儿子是父亲地后件结构指数据元素之间地前后件关系数据地逻辑结构—是指反映数据元素之间逻辑关系，而与它们在计算机中地存储位置无关数据地存储结构（物理结构）数据地逻辑结构在计算机存储空间中地存放形式，数据元素在计算机存储空间地位置关系可能与逻辑关系不同.根据数据结构中各数据元素之间前后件关系地复杂程度，可将数据结构分两类线性结构与非线性结构线性结构（线性表）满足下列两个条件（）有且只有一个根结点（）每一个结点最多有一个前件和后件.则称该数据结构为线性结构，否则为非线性结构.线性表是最简单、最常用地一种数据结构，其数据元素之间地相对位置是线性地，其存储方式为顺序存储地，如数组栈是限定在一端进行插入与删除地线性表，一端封闭，另一端开口，其操作原则是“先进后出”，栈地运算有入栈、退栈、读栈顶元素队列是指在一端进行插入（称为队尾）而在另一端进行删除（称为队头）地线性表，其操作规则是“先进先出”，其运算有入队和退队.树是一种简单地非线性结构，而且是层次结构，是倒立地大树，有根结点、父结点、子结点、叶子结点.根结点在第一层，一个结点所拥有地后件地个数称为该结点地度，所有结点中最大地度称为树地度，树地最大层次称为树地深度.二叉树（）非空二叉树只有一个根结点（）每一个结点最多有两棵子树（左子树和右子树），其存储结构为链式.二叉树性质（）层上最多有（）个结点（）深度为地二叉树最多有个结点（）度为地结点（叶子结点）比度为地结点多一个（）具有个结点地二叉树，其深度至少为[]，其中[]表示对取整满二叉树除最后一层外，其余层地结点都有两个子结点完全二叉树除最后一层外，每一层上地结点数均达到最大值，在最后一层上只缺少右边地若干结点，叶子结点只可能在层次最大地两层上出现.满二叉树是完全二叉树，而完全二叉树不是满二叉树.完全二叉树有两个性质：（）具有个结点地完全二叉树地深度为[]（）二叉树遍历不重复地访问各个结点.分为前序遍历(根左右)、中序遍历(左根右)和后序遍历（左右根）查找技术顺序查找——对于长度为地有序线性表，查找时需要比较次二分法查找——对于长度为地有序线性表，查找时需要比较次排序技术假设线性表地长度为，则冒泡排序和简单插入排序地比较次数（时间复杂度）为();希尔排序地比较次数为();简单选择排序地比较次数为();堆排序地比较次数为().习题算法地时间复杂度是指（），算法地空间复杂度是指（）；队列是（先进先出），栈是（先进后出）；下列二叉树地遍历结果：前序遍历（）、中序遍历（）、后续遍历（）；在深度为地满二叉树中，叶子结点地个数为（）；设树地度为，其中度为，，；线性表、栈、队列、线性链表是（线性结构），树是（非线性结构）；数据地存储结构是指（）；，地结点地个数分别为，，，.则中地叶子结点地个数为（）；对于长度为地有序线性表，顺序查找次数为（）,二分法查找次数为（）；一棵完全二叉树共有个结点，则在该二叉树中有（）个叶子结点；一棵二叉树地中序遍历结果为，前序遍历结果为，则后续遍历结果为（）；冒泡排序地时间复杂度为（()）;在一个容量为地循环队列中，若头指针,尾指针,则该循环队列中共有（）元素；。

数据结构真题2012年10月(总分：100.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.一个算法的时间耗费的数量级称为该算法的______（分数：2.00）A.效率B.难度C.可实现性D.时间复杂度√解析：[考点] 算法的时间复杂度的概念[解析] 一个算法的时间耗费的数量级称为该算法的时间复杂度。

2.顺序表便于______（分数：2.00）A.插入结点B.删除结点C.按值查找结点D.按序号查找结点√解析：[考点] 顺序表的特征[解析] 顺序表便于按序号查找结点。

3.设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是______（分数：2.00）A.p-＞next-＞next==headB.p-＞next==head √C.p-＞next-＞next==NULLD.p-＞next==NULL解析：[考点] 指针变量p指向尾结点的判定条件[解析] 单循环链表的指针变量p指向尾结点的判定条件是p-＞next==head。

4.设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为______（分数：2.00）A.(rear-front+m)%m √B.rear-front+1C.(front-rear+m)%mD.(rear-front)%m解析：[考点] 队列中元素个数的计算[解析] 队列中元素的个数为(rear-front+m)%m5.下列关于顺序栈的叙述中，正确的是______（分数：2.00）A.入栈操作需要判断栈满，出栈操作需要判断栈空√B.入栈操作不需要判断栈满，出栈操作需要判断栈空C.入栈操作需要判断栈满，出栈操作不需要判断栈空D.入栈操作不需要判断栈满，出栈操作不需要判断栈空解析：[考点] 顺序栈的性质的判断[解析] 入栈操作需要判断栈满，出栈操作需要判断栈空。

6.A是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a 0，0的存储地址为1，每个元素占一个存储单元，则a 7，5的地址为______（分数：2.00）A.25B.26C.33D.34 √解析：[考点] 对称矩阵的元素的地址的计算[解析] 若对称矩阵采用下三角压缩存储，根据其地址的计算公式，可得到所求元素的地址。

数据结构试卷（一）一、单选题（每题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（10),A[2][2］存放位置在676（10），每个元素占一个空间，问A[3］［3](10)存放在什么位置？脚注（10)表示用10进制表示。

A．688 B．678 C．692 D．6965.树最适合用来表示( ）。

A.有序数据元素B。

无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ）。

A．2k—1 B.2K+1 C.2K—1 D。

2k—17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为( )A. 1,2，3 B。

9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O(1)B. O（n）C. O（1og2n） D。

O（n2）9.对于线性表（7,34,55，25，64，46,20,10)进行散列存储时，若选用H（K)=K ％9作为散列函数，则散列地址为1的元素有( )个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。

A.5B.6C.7 D。

8二、填空题(每空1分,共26分)1.通常从四个方面评价算法的质量：_________、_________、_________和_________。

2.一个算法的时间复杂度为（n3+n2log2n+14n)/n2，其数量级表示为________。