【精选】数据结构单元10练习参考答案

数据结构试卷（一）参考答案一、选择题（每题2分，共20分）1.A2.D3.D4.C5.C6.D7.D8.C9.D 10.A 二、填空题（每空1分，共26分）1. 正确性 易读性 强壮性 高效率2. O(n)3. 9 3 34. -1 3 4 X * + 2 Y * 3 / -5. 2n n-1 n+16. e 2e7. 有向无回路8. n(n-1)/2 n(n-1)9. （12，40） （ ） （74） （23,55，63） 10.增加111.O(log 2n) O(nlog 2n) 12.归并三、计算题（每题6分，共24分）1. 线性表为：（78，50，40，60，34，90）2. 邻接矩阵：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0111010101110111010101110邻接表如图11所示：图113. 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204. 见图12图124 4 4 4 4 2 2 25 552 2 8 84 352 83 4四、读算法（每题7分，共14分）1.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,…,a n,a1）2.递归地后序遍历链式存储的二叉树。

五、法填空（每空2分，共8 分）true BST->left BST->right六、编写算法（8分）int CountX(LNode* HL,ElemType x){ int i=0; LNode* p=HL;//i为计数器while(p!=NULL){ if (P->data==x) i++;p=p->next;}//while, 出循环时i中的值即为x结点个数return i;}//CountX数据结构试卷（二）参考答案一、选择题1.D2.B3.C4.A5.A6.C7.B8.C二、填空题1.构造一个好的HASH函数，确定解决冲突的方法2.stack.top++，stack.s[stack.top]=x3.有序4.O(n2)，O(nlog2n)5.N0-1，2N0+N16.d/27.(31，38，54，56，75，80，55，63)8.(1，3，4，5，2)，(1，3，2，4，5)三、应用题1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2.q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q;3.2,ASL=91*1+2*2+3*4+4*2)=25/94.树的链式存储结构略，二叉树略5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}6.略四、算法设计题1.设有一组初始记录关键字序列（K1，K2，…，K n），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K i，右半部分的每个关键字均大于等于K i。

一、单选题（每题 2 分，共20分）1. 1.对一个算法的评价，不包括如下（B）方面的内容。

A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行(A )。

A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3. 3.对线性表，在下列哪种情况下应当采用链表表示？( B )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. 5.AOV网是一种（D）。

A．有向图B．无向图C．无向无环图D．有向无环图6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（B）。

A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（D）参数。

A．值B．函数C．指针D．引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（A）。

A．行号B．列号C．元素值D．非零元素个数9.9.快速排序在最坏情况下的时间复杂度为（D）。

A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题 6 分，共24分）1. 1.数据结构是指数据及其相互之间的______________。

当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。

第10章排序10.1 知识点分析1．排序基本概念：（1）排序将数据元素的任意序列，重新排列成一个按关键字有序（递增或递减）的序列的过程称为排序。

（2）排序方法的稳定和不稳定若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对原先具有相同键值元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳定的。

（3）内排序整个排序过程都在内存进行的排序称为内排序，本书仅讨论内排序。

（4）外排序待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。

2．直接插入排序直接插入排序法是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。

3．二分插入排序二分插入排序法是用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入的排序方法。

4．希尔排序希尔排序的基本思想是：先选取一个小于n的整数d1作为第一个增量，把待排序的数据分成d1个组，所有距离为d1的倍数的记录放在同一个组内，在各组内进行直接插入排序，每一趟排序会使数据更接近于有序。

然后，取第二个增量d2，d2< d1，重复进行上述分组和排序，直至所取的增量d i=1（其中d i< d i-1 < ……< d2< d1），即所有记录在同一组进行直接插入排序后为止。

5．冒泡排序冒泡法是指每相邻两个记录关键字比大小，大的记录往下沉（也可以小的往上浮）。

每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束。

6．快速排序快速排序法是通过一趟排序，将待排序的记录组分割成独立的两部分，其中前一部分记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比枢轴记录的关键字大，枢轴记录得到了它在整个序列中的最终位置并被存放好。

第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且它们又分别分割出独立的两个子序列……。

最新版《数据结构》各章习题及答案第一章绪论一、选择题1.组成数据的基本单位是（）（A）数据项（B）数据类型（C）数据元素（D）数据变量2.数据结构是研究数据的（）以及它们之间的相互关系。

（A）理想结构，物理结构（B）理想结构，抽象结构（C）物理结构，逻辑结构（D）抽象结构，逻辑结构3.在数据结构中，从逻辑上可以把数据结构分成（）（A）动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。

① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像② （A）结构（B）关系（C）运算（D）算法5.算法分析的目的是（）。

（A）找出数据结构的合理性（B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5 个特性。

① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性（C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性二、判断题1.数据的机内表示称为数据的存储结构。

（）2.算法就是程序。

（）3.数据元素是数据的最小单位。

（）4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。

（）5.算法的时间复杂度取决于问题的规模和待处理数据的初态。

（）三、填空题1.数据逻辑结构包括________、________、_________ 和__________ 四种类型,其中树形结构和图形结构合称为_____ 。

2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______ 个前驱结点；最后一个结点______后续结点,其余每个结点有且只有 _______ 个后续结点。

3.在树形结构中,树根结点没有_______ 结点,其余每个结点有且只有_______个前驱结点；叶子结点没有 ________ 结点,其余每个结点的后续结点可以_________。

习题6一．填空题1．树中除根结点外，其他结点有且只有个直接前驱结点，但可以有个直接后继结点。

2．树中结点的度，是指结点拥有的个数；一棵具有n个结点的树，该树中所有结点的度数之和为。

3．深度为h的完全二叉树至少有个结点，至多有个结点，若按层序从1开始编号，则编号最小的叶子结点的编号是。

5．将一棵完全二叉树按层序从1进行编号，对编号为i的结点，如果有左孩子，则左孩子的编号应该是；如果有右孩子，则右孩子的编号应该是。

6．一棵完全二叉树有1001个结点，其深度是，叶子结点个数是。

78．树的先根遍历序列与其对应二叉树的遍历序列相同，树的后根遍历序列与其对应二叉树的遍历序列相同。

9．若二叉树共有n个结点，采用线索链表存储其线索二叉树，那么在所有存储结点里，一共有个指针域，其中有个指针是指向其孩子结点的，个指针是指向其前驱后继结点的。

指向前驱后继结点的指针称为。

10．哈夫曼树又称。

它是n个带权叶子结点构成的所有二叉树中，带权路径长度的二叉树。

11．哈夫曼树中，权值较大的叶结点一定离根结点。

由n个带权值的叶结点生成的哈夫曼树中共有个结点，其中有个分支结点。

12．哈夫曼树中不存在度为的结点。

二．选择题1．有关二叉树下列说法正确的是（）A．二叉树的度为2 B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 2．二叉树的第i层上最多含有结点数为（）A．2i B．2i-1-1 C．2i-1D．2i-13．一棵具有1025个结点的二叉树的高度为( )。

A．11 B．10 C．11至1025之间D．10至1024之间4．一棵高度为5的二叉树，其结点总数为（）。

A．6~17 B．5~16 C．6~32 D．5~315．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( )。

A．9 B．11 C．15 D．不能确定6．一棵完全二叉树具有600个结点，则它有( ) 个度为1的结点。

1．下列排序算法中，其中（ D ）是稳定的。

A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序2．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。

A．下面的B，C，D都不对。

B．9，7，8，4，-1，7，15，20C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，203.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ B ）。

A. 直接插入排序B. 快速排序C. 直接选择排序D. 堆排序4．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D ）方法最快。

A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序5．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。

A. 插入B. 选择C. 希尔D. 二路归并6. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ A ）。

A. 选择B. 冒泡C. 插入D. 堆7. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（ C ）次比较。

A. 3B. 10C. 15D. 258. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( B )A. lB. 4C. 3D. 29. 堆排序是（ E ）类排序A. 插入B. 交换C. 归并D. 基数E. 选择10．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端；交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法，而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。

第九章查找一、填空题1.在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找(线性查找) 。

2.线性有序表(a i，a2，a3,…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索_8 次。

设有100个结点，用二分法查找时，最大比较次数是_7_ ____________ 。

3•假设在有序线性表a[1..2O]上进行折半查找，则比较一次查找成功的结点数为1;比较两次查找成功的结点数为_2 ___________ ;比较四次查找成功的结点数为8 ,其下标从小到大依次是1,3,6,8,11,13,16,19 _ ，平均查找长度为 3.7 。

解：显然，平均查找长度二0( log 2n) <5次(25)。

但具体是多少次，则不应当按照公式ASL =U|°g2(n⑴来计算(即(21 X log 221) /20 = 4.6次并不正确！)。

因为这是在假设n = 2m-1 n 的情况下推导出来的公式。

应当用穷举法罗列：全部元素的查找次数为=(1 + 2X 2+ 4X 3+ 8X 4+ 5X 5)= 74; ASL= 74/20=3.7 !!! 4•折半查找有序表(4, 6，12，20, 28, 38，50，70, 88，100)，若查找表中元素20,它将依次与表中元素28 , 6, 12, 20 比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找。

6. 散列法存储的基本思想是由关键字的值决定数据的存储地址。

7. 有一个表长为m的散列表，初始状态为空，现将n (n<m)个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。

如果这n个关键码的散列地址都相同，贝U探测的总次数是n(n-1)/2= ( 1 土2+…+ n-1 )。

(而任一元素查找次数 < n-1)&设一哈希表表长M为100，用除留余数法构造哈希函数，即H( K) =K MOIP ( P<=M ,为使函数具有较好性能，P应选(97 )9、在各种查找方法中，平均查找长度与结点个数无关的是哈_______10、对线性表进行二分查找时，要求线性表必须以顺序方式存储，且结点按关键字有序排列。

9.1选择题1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（）排序法。

A）插入B）选择C）希尔D）二路归并【答案】A2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（）A）快速排序B）直接插入排序C）堆排序D）归并排序【答案】B3．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，无序序列的变化情况如下：25 84 21 47 15 27 68 35 2020 15 21 25 47 27 68 35 8415 20 21 25 35 27 47 68 8415 20 21 25 27 35 47 68 84则所采用的排序方法是（）Ａ）选择排序Ｂ）希尔排序Ｃ）归并排序Ｄ）快速排序【答案】Ｄ4．下面给出的四种排序法中，（）排序是不稳定排序法。

A）插入B）冒泡C）二路归并D）堆【答案】D5．快速排序方法在（）情况下最不利于发挥其长处。

Ａ）要排序的数据量太大Ｂ）要排序的数据中含有多个相同值Ｃ）要排序的数据已基本有序Ｄ）要排序的数据个数为奇数【答案】Ｃ6．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）Ａ）38,40,46,56,79,84B）40,38,46,79,56,84C）40,38,46,56,79,84D）40,38,46,84,56,79【答案】Ｃ7．对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：50,26,38,80,70,90 ,8,30,40,2050,8,30,40,20,90,26,38,80,7026,8,30,40,20,80,50,38,90,708,20,26,30,38,40,50,70,80,90其使用的排序方法是（）A）快速排序B）基数排序C）希尔排序D）归并排序【答案】C8．以下序列不是堆的是（）A）100,85,98,77,80,60,82,40,20,10,66B）100,98,85,82,80,77,66,60,40,20,10C）10,20,40,60,66,77,80,82,85,98,100D）100,85,40,77,80,60,66,98,82,10,20【答案】D【解析】根据堆采用完全二叉树的顺序存储形式及堆的特点，因第一个结点即根结点关键字值最大，则应建立一个大根堆，但依据此数据序列建立起堆后关键字值为40的左右孩子结点分别为60、66，不符合大根堆特点。

数据结构练习题（含答案）①A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2.数据结构DS(DataStruct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。

①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象②A．操作Ｂ．映象Ｃ．存储Ｄ．关系3.在数据结构中，从逻辑上可以把数据结构分成。

A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4.算法分析的目的是①，算法分析的两个主要方面是②。

①A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性②A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性5.计算机算法指的是①，它必具备输入、输出和②等五个特性。

①A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法②A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性1.2填空题（将正确的答案填在相应的空中）1.数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。

2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。

3.在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。

4.在图形结构中，每个结点的前驱结点数和后续结点数可以。

5.线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。

6.算法的五个重要特性是____,____,____,____,____。

7.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是____。

for(i=0;i<n;i++)for(j=0;j<n;j++)A[i][j]=0;8.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是____。

数据结构习题及解答第1章 概述【例1-1】分析以下程序段的时间复杂度。

for(i=0;i<n;i++) for(j=0;j<m;j++) A[i][j]=0;解：该程序段的时间复杂度为O (m*n )。

【例1-2】分析以下程序段的时间复杂度。

i=s=0; ① while(s<n) { i++; ② s+=i; ③ }解：语句①为赋值语句，其执行次数为1次，所以其时间复杂度为O (1)。

语句②和语句③构成while 循环语句的循环体，它们的执行次数由循环控制条件中s 与n 的值确定。

假定循环重复执行x 次后结束， 则语句②和语句③各重复执行了x 次。

其时间复杂度按线性累加规则为O (x )。

此时s 与n 满足关系式：s ≥n ，而s=1+2+3+…+x 。

所以有：1+2+3+…+x ≥n ，可以推出：x=nn 241212811+±-=+±-x 与n 之间满足x=f(n ），所以循环体的时间复杂度为O (n )，语句①与循环体由线性累加规则得到该程序段的时间复杂度为O (n ）。

【例1-3】分析以下程序段的时间复杂度。

i=1; ① while(i<=n) i=2*i; ②解：其中语句①的执行次数是1，设语句②的执行次数为f (n )，则有：n n f ≤)(2。

log)得：T（n）=O(n2【例1-4】有如下递归函数fact(n)，分析其时间复杂度。

fact(int n){ if(n<=1)return(1);①elsereturn(n*fact(n-1));②}解：设fact（n）的运行时间函数是T(n)。

该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n-1)+ O(1)，其中O(1)为常量运行时间。

由此可得fact（n）的时间复杂度为O(n)。

习题1一、单项选择题1.数据结构是指（1. A ）。

A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（2. C ）。

第十章内部排序一、择题1．用直接插入排序法对下面四个表进行（由小到大）排序，比较次数最少的是（B）。

A．（94，32，40，90，80，46，21，69）插32，比2次插40，比2次插90，比2次插80，比3次插46，比4次插21，比7次插69，比4次B．（21，32，46，40，80，69，90，94）插32，比1次插46，比1次插40，比2次插80，比1次插69，比2次插90，比1次插94，比1次C．（32，40，21，46，69，94，90，80）插40，比1次插21，比3次插46，比1次插69，比1次插94，比1次插90，比2次插80，比3次D．（90，69，80，46，21，32，94，40）插69，比2次插80，比2次插46，比4次插21，比5次插32，比5次插94，比1次插40，比6次2．下列排序方法中，哪一个是稳定的排序方法（BD）。

A．希尔排序B．直接选择排序C．堆排序D．冒泡排序下列3题基于如下代码：for(i=2;i<=n;i++){ x=A[i];j=i-1;while(j>0&&A[j]>x){ A[j+1]=A[j];j--;}A[j+1]=x}3．这一段代码所描述的排序方法称作（A）。

A．插入排序B．冒泡排序C．选择排序D．快速排序4．这一段代码所描述的排序方法的平均执行时间为（D）A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)5．假设这段代码开始执行时，数组A中的元素已经按值的递增次序排好了序，则这段代码的执行时间为（B）。

A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)6．在快速排序过程中，每次被划分的表（或了表）分成左、右两个子表，考虑这两个子表，下列结论一定正确是（B）。

A．左、右两个子表都已各自排好序B．左边子表中的元素都不大于右边子表中的元素C．左边子表的长度小于右边子表的长度D．左、右两个子表中元素的平均值相等7．对n个记录进行堆排序，最坏情况下的执行时间为（C）。

第10章排序一、选择题1．某内排序方法的稳定性是指( )。

【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法 D．以上都不对2．下面给出的四种排序法中( )排序法是不稳定性排序法。

【北京航空航天大学 1999 一、10 （2分）】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积3．下列排序算法中，其中（）是稳定的。

【福州大学 1998 一、3 (2分)】A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序4．稳定的排序方法是（）【北方交通大学 2000 二、3（2分）】A．直接插入排序和快速排序 B．折半插入排序和起泡排序C．简单选择排序和四路归并排序 D．树形选择排序和shell排序5．下列排序方法中，哪一个是稳定的排序方法？（）【北方交通大学 2001 一、8（2分）】A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。

【北京邮电大学 2001 一、5（2分）】7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。

（）就是不稳定的排序方法。

【清华大学 1998 一、3 (2分）】A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。

A．直接插入 B．直接选择 C．堆 D．快速 E．基数【中科院计算所 2000 一、5（2分）】9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。

A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序【中国科技大学 1998 二、4（2分）】【中科院计算所 1998 二、4（2分）】10．下面的排序算法中，不稳定的是（）【北京工业大学 1999 一、2 (2分)】序 D.希尔排序 E.基数排序 F.堆排序。

单元测验10一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（ㄨ）（1）如果某种排序算法不稳定，则该排序方法就没有实用价值。

（√）（2）希尔排序是不稳定的排序。

（ㄨ）（3）冒泡排序是不稳定的排序。

（√）（4）对n个记录的进行快速排序，所需要的平均时间是O(nlog2n)。

（ㄨ）（5）堆排序所需的时间与待排序的记录个数无关。

（√）（6）当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。

（ㄨ）（7）快速排序在任何情况下都比其它排序方法速度快。

（√）（8）对快速排序来说，初始序列为正序或反序都是最坏情况。

（√）（9）采用归并排序可以实现外排序。

（√）（10）采用希尔方法排序时，若关键字的排列杂乱无序，则效率最高。

（√）（11）快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。

（√）（12）冒泡排序的时间复杂度是O（n2）。

二．填空题（1）大多数排序算法都有两个基本的操作：比较和移动。

（2）评价排序算法优劣的主要标准是时间复杂度和算法所需的附加空间。

（3）根据被处理的数据在计算机中使用不同的存储设备，排序可分为：内排序和外排序。

（4）外排序是指在排序过程中，数据的主要部分存放在计算机的外存中。

（5）对n个关键字进行冒泡排序，其可能的最小比较次数为： n-1 次。

（6）在最坏情况下，在第i趟直接插入排序中，要进行 i-1 次关键字的比较。

（7）对n个关键字进行冒泡排序，时间复杂度为 O(n2) 。

（8）快速排序在最坏情况下的时间复杂度是 O(n2) 。

（9）对于n个记录的集合进行归并排序，所需要的平均时间为： O(log2n) 。

（10）对于n个记录的集合进行归并排序，所需要的附加空间是 O(n) 。

（11）若原始数据接近无序，则选用快速排序最好。

（12）在排序前，关键字值相等的不同记录，排序后相对位置保持不变的排序方法，称为稳定排序方法。

计算机考研数据结构试卷十（练习题含答案）共25套适用于计算机考研数据结构系统练习（PS：其他正在整理，敬请期待）数据结构试卷10一、选择题1．下列程序段的时间复杂度为（）。

i=0，s=0；while (s(A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)2．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（）存储方式最节省运算时间。

(A) 单向链表(B) 单向循环链表(C) 双向链表(D) 双向循环链表3．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（）。

(A) s->next=p->next；p->next=-s；(B) q->next=s； s->next=p；(C) p->next=s->next；s->next=p；(D) p->next=s；s->next=q；4．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。

(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1(C) 3，1，2，5，4，6 (D) 1，5，4，6，2，35．设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（）。

(A) 10 (B) 19 (C) 28 (D) 556．设一棵m叉树中有N1个度数为1的结点，N个度数为2的结点，……，Nm个度数为m的结点，则该树中共有（）个叶子结点。

(A) ∑=-miiNi1)1((B) ∑=miiN1(C) ∑=miiN2(D) ∑=-+iiNi2)1(17. 二叉排序树中左子树上所有结点的值均（）根结点的值。

(A) < (B) > (C) = (D) !=8. 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。

数据结构课堂练习综合1一、单项选择题1、数据结构被形式地定义为（D,R），其中R 是（）。

A. 算法B. 操作的集合C. 数据元素的集合D. 数据关系的集合2、循环队列是线性表的（）A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 散列存储结构3、某二叉树的前序遍历序列为ABDEFC，中序遍历为DBEFAC，则后序遍历序列为（）A. DFEBCAB. DBECFAC. BDECFAD. DBEFCA4、设将数字1,2,3,4,5依次进栈，出栈可任意，最后都出栈，则出栈序列不可能的是（）A. 23415B. 54132C. 23145D. 154325、若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（）A．层次遍历算法 B．前序遍历算法C．中序遍历算法 D．后序遍历算法6、广义表((a))的表尾是（）A. aB. （（））C.( )D.（a）7、用Prim算法求下列连通的带权图的最小代价生成树，在算法执行的某刻，已选取的顶点集合U＝{1，2，5}，边的集合TE＝{（1，2），（2，5）}，要选取下一条权值最小的边，应当从（）组中选取。

(A){（1，4），（3，4），（3，5），（2，5）}(B){（5，4），（5，3），（5，6）}(C){（1，2），（2，3），（3，5）}(D){（3，4），（3，5），（4，5），（1，4）}8、若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是（）A. s－>next=p－>next; p－>next=sB. p－>next=s; s－>next=p－>nextC. p－>next=s－>next; s－>next=pD. s－>next=p; p－>next=s－>next二、算法应用题：如果需传送的电文为‘ABACCDA’，即：A, B, C, D的频率（即权值）分别为0.43, 0.14, 0.29, 0.14，试构造哈夫曼编码。

单元测验10一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（ㄨ）（1）如果某种排序算法不稳定，则该排序方法就【没】有实用价值。

（√）（2）希尔排序是不稳定的排序。

（ㄨ）（3）冒泡排序是【不】稳定的排序。

（√）（4）对n个记录的进行快速排序，所需要的平均时间是O(nlog2n)。

（ㄨ）（5）堆排序所需的时间与待排序的记录个数【无】有关。

（√）（6）当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。

（ㄨ）（7）快速排序不是在任何情况下都比其它排序方法速度快。

（√）（8）对快速排序来说，初始序列为正序或反序都是最坏情况。

（√）（9）采用归并排序可以实现外排序。

（√）（10）采用希尔方法排序时，若关键字的排列杂乱无序，则效率最高（√）（11）快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。

（√）（12）冒泡排序的时间复杂度是O（n2）。

二．填空题（1）大多数排序算法都有两个基本的操作：比较和移动。

（2）评价排序算法优劣的主要标准是时间复杂度和算法所需的附加空间。

（3）根据被处理的数据在计算机中使用不同的存储设备，排序可分为：内排序和外排序。

（4）外排序是指在排序过程中，数据的主要部分存放在计算机的外存中。

（5）对n个关键字进行冒泡排序，其可能的最小比较次数为：n-1次。

（6）在最坏情况下，在第i趟直接插入排序中，要进行i-1次关键字的比较。

（7）对n个关键字进行冒泡排序，时间复杂度为 O(n2) 。

（8）快速排序在最坏情况下的时间复杂度是 O(n2) 。

（9）对于n个记录的集合进行归并排序，所需要的平均时间为： O(log2n) 。

（10）对于n个记录的集合进行归并排序，所需要的附加空间是 O(n) 。

（11）若原始数据接近无序，则选用快速排序最好。

（12）在排序前，关键字值相等的不同记录，排序后相对位置保持不变的排序方法，称为稳定排序方法。

数据构造试卷〔一〕一、单项选择题〔每题 2 分，共20分〕1.栈和队列的共同特点是( a )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进展插入运算时( d ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据构造中哪一个是非线性构造？( d )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

cA．688 B．678 C．692 D．6965.树最适合用来表示( c )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( d ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.假设有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进展二分查找，那么查找A［3］的比拟序列的下标依次为( c d)A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进展快速排序，所需要的辅助存储空间大致为 cA. 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的元素有〔 c d〕个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( a )条边才能确保是一个连通图。

二、填空题〔每空1分，共26分〕1.通常从四个方面评价算法的质量：____时间正确性_____、____占用内存_易读性____、____复杂度__强壮性___和_____准确度_ 高效率___。