当前位置:文档之家› 吉林省专升本数据结构习题及答案——第八章

吉林省专升本数据结构习题及答案——第八章

吉林省专升本考试数据结构分章习题及参考答案———选择题

(第八章)

1、若数据元素序列{11,12,13,78,9,23,4,5}是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法只能是( )

A、冒泡排序

B、插入排序

C、选择排序

D、归并排序

2、若将两个各有n个元素的有序表归并成一个有序表,则最少比较次数是()。

A、 n

B、 2*n-1

C、 2n

D、 n-1

3、已知数据表中每个元素距其最终位置不远,则采用()方法最节省时间

A、堆排序

B、插入排序

C、快速排序

D、直接选择排序

4、下列排序算法中,()算法可能会出现下面情况:在后一趟开始之前,所有元素都不在其终的位置上。

A、堆排序

B、冒泡排序

C、快速排序

D、插入排序

5、下述几种排序方法中,要求内存量最大的是()。

A、插入排序

B、快速排序

C、归并排序

D、选择排序

6、就排序算法所用的辅助空间而言,堆排序,快速排序,归并排序的关系是()

A、堆排序<快速排序<归并排序

B、堆排序<归并排序<快速排序

C、堆排序>归并排序>快速排序

D、堆排序>快速排序>归并排序

7、快速排序方法在( )情况下最不利于发挥其长处。

A、要排序的数据量太大

B、要排序的数据中含有多个相同值

C、要排序的数据已基本有序

D、要排序的数据个数为奇数

8、对关键字由大到小进行冒泡排序,在下列()情况下比较的次数最多。

A、从小到大排序

B、从大到小排序

C、元素无序

D、元素基本有序

9、对5个不同的数据元素进行直接插入排序,最多需要进行()次比较。

A、 8

B、 10

C、 15

D、 25

10、如果只想得到1000个元素组成的序列中第5个小元素之前的部分排序的序列,用()方法快。

A、起泡排序

B、快速排列

C、堆排序

D、简单选择排序

11、设有1000个无序的元素,希望用最快的速度挑选出其中前十个最大的元素,在以下的排序方法中采用哪一种最好?()

A、快速排序

B、归并排序

C、堆排序

D、基数排序

12、下列排序算法中,()可能会出现下面情况:在最后一趟开始之前,所有元素都不在最终位置上。

A、起泡排序

B、插入排序

C、快速排序

D、堆排序

13、对以下数据序列利用快速排序进行排序,速度最快的是()

A、21,25,5,17,9,23,30

B、25,23,30,17,21,5,9

C、21,9,17,30,25,23,5

D、5,9,17,21,23,25,30

14、快速排序在下列( )情况下最易发挥其长处。

A、被排序的数据中含有多个相同排序码

B、被排序的数据已基本有序

C、被排序的数据完全无序

D、被排序的数据中的最大值和最小值相差悬殊

15、在含有n个关键字的小根堆(堆顶元素小)中,关键字最大的记录有可能存储在()位置上。

A、⎣n/2⎦

B、⎣n/2⎦-1

C、1

D、⎣n/2⎦+2

16、堆排序是()类排序.

A、插入

B、交换

C、归并

D、选择

17、下面给出的四种排序法中()排序法是不稳定性排序法。

A、插入

B、冒泡

C、二路归并

D、堆

18、若需在O(nlog2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是()。

A、快速排序

B、堆排序

C、归并排序

D、直接插入排序

19、对序列{15,9,7,8,20,-1,4}进行排序,经一趟排序后的排列为{9,15,7,8,20,-1,4},则采用的是()排序。

A、选择

B、堆

C、直接插入

D、冒泡

20、在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是( )。

A、希尔排序

B、起泡排序

C、插入排序

D、选择排序

21、对关键码序列{23,17,72,60,25,8,68,71,52}进行堆排序,输出两个最小关键码后的剩余堆是()

A、{23,72,60,25,68,71,52}

B、{23,25,52,60,71,72,68}

C、{71,25,23,52,60,72,68}

D、{23,25,68,52,60,72,71}

22、对于关键字序列{46,58,15,45,90,18,10,62},其快速排序第一趟的结果是()

A、 15 45 18 46 10 62 58 90

B、 10 15 18 45 46 58 62 90

C、 10 18 15 45 46 90 58 62

D、 15 10 18 45 46 62 58 90

23、冒泡排序是一种()的排序。

A、插入

B、选择

C、交换

D、归并

24、当待排序序列基本有序或个数较小的情况下,最佳的内部排序方法是()

A、直接插入排序

B、冒泡排序

C、简单选择排序

D、快速排序

25、有一组数据(15,9,7,8,20,-1,7,4)用快速排序的划分方法进行一趟划分后数据的排序为()(按递增序)。

A、下面的B,C,D都不对。

B、9,7,8,4,-1,7,15,20

C、20,15,8,9,7,-1,4,7

D、9,4,7,8,7,-1,15,20

26、对序列{15,9,7,8,20,-1,4,}用希尔排序方法排序,经一趟后序列变为{15,-l,4,8,20,9,7}则该次采用的增量是()

A、l

B、4

C、3

D、2

27、对长度为10的表作选择(简单选择)排序,共需比较()次关键字。

A、 45

B、 90

C、 55

D、 110

28、对初始状态为递增有序的序列进行排序,最费时间的是()

A、堆排序

B、插入排序

C、快速排序

D、直接选择排序

29、下述排序方法中,时间性能与待排序记录的初始状态无关的有()

A、插入排序和快速排序

B、归并排序和快速排序

C、选择排序和归并排序

D、插入排序和归并排序

30、分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是()

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)

31、就平均时间而言,()最佳。

A、直接插入排序

B、冒泡排序

C、简单选择排序

D、快速排序

32、排序趟数与序列的原始状态(原始排列)有关的排序方法是()排序方法。

A、直接插入排序

B、简单选择排序

C、冒泡排序

D、快速排序

33、目前以比较为基础的内部排序方法中,其比较次数与待排序的记录的初始排列状态无关的是()。

A、插入排序

B、直接选择排序

C、快速排序

D、冒泡排序

34、在下列算法中,()算法可能出现下列情况:在最后一趟开始之前,所有的元素都不在其最终的位置上。

A、堆排序

B、冒泡排序

C、插入排序

D、快速排序

35、下列排序方法中,哪一个是稳定的排序方法?()

A、直接选择排序

B、插入排序

C、希尔排序

D、快速排序

36、归并排序中,归并的趟数是()。

A、O(n)

B、O(logn)

C、O(nlogn)

D、O(n*n)

37、快速排序方法在()情况下不利于发挥其长处。

A、要排序的数据量太大

B、要排序的数据中含有多个相同值

C、要排序的数据个数为奇数

D、要排序的数据已基本有序

38、下述几种排序方法中,要求内存最大的是( )

A、希尔排序

B、快速排序

C、归并排序

D、堆排序

39、对于下列关键字序列,不可能构成某二叉排序树中一条查找路径的序列是()。

A、95, 22, 91, 24, 94, 71

B、92, 20, 91, 34, 88, 35

C、21, 89, 77, 29, 36, 38

D、12, 25, 71, 68, 33, 34

40、若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序,需进行()次比较。

A、3

B、10

C、15

D、25

41、下面给出的四种排序方法中,排序过程中的比较次数与序列的初始状态无关

的是。()

A、选择排序法

B、插入排序法

C、快速排序法

D、堆排序法

42、改进的冒泡排序在最好情况下时间复杂度为()

A、 O(1)

B、 O(nlog2n)

C、 O(n)

D、 O(n2)

43、希尔排序法属于哪一种类型的排序法()。

A、交换类排序

B、插入类排序

C、选择类排序

D、建堆排序法

44、下列排序算法中,( )不能保证每趟排序至少能将一个元素放到其最终的位置上。

A、希尔排序

B、快速排序

C、冒泡排序

D、堆排序

45、如果待排序序列中两个数据元素具有相同的值,在排序前后它们的相互位置发生颠倒,则称该排序算法是不稳定的。()就是不稳定的排序方法。

A、起泡排序

B、归并排序

C、Shell排序

D、直接插入排序

46、设有5000个元素,希望用最快的速度挑选出前10个最大的元素,采用()方法最好。

A、快速排序

B、堆排序

C、希尔排序

D、归并排序

47、为实现快速排序算法,待排序序列宜采用的存储方式是( )。

A、顺序存储

B、散列存储

C、链式存储

D、索引存储

48、数据序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的()的两趟排序后的结果。

A、选择排序

B、冒泡排序

C、插入排序

D、堆排序

49、()方法是从未排序序列中挑选元素,并将其放入已排序序列的一端。

A、归并排序

B、插入排序

C、快速排序

D、选择排序

50、下列排序算法中()不能保证每趟排序至少能将一个元素放到其终的位置上。

A、快速排序

B、shell排序

C、堆排序

D、冒泡排序

参考答案:

1.B

2.A

3.B

4.D

5.C

6.A

7.C

8.A

9.B10.C

11.C12.B13.A14.C15.D16.D17.D18.C19.C20.D

21.D22.C23.C24.A25.A26.B27.A28.C29.C30.C

31.D32.D33.B34.C35.B36.B37.D38.C39.A40.C

41.A42.C43.B44.A45.C46.B47.A48.C49.D50.B

数据结构第八章习题及答案

习题八查找 一、单项选择题 1.顺序查找法适合于存储结构为()的线性表。 A.散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储 2.若查找每个记录的概率均等,则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为( )。 A. (n-1)/2 B. n/2 C. (n+1)/2 D. n 3.适用于折半查找的表的存储方式及元素排列要求为( ) A.链接方式存储,元素无序 B.链接方式存储,元素有序 C.顺序方式存储,元素无序 D.顺序方式存储,元素有序 4.当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的查找速度( ) A.必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减5.当采用分块查找时,数据的组织方式为 ( ) A.数据分成若干块,每块内数据有序 B.数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块 C. 数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块 D. 数据分成若干块,每块(除最后一块外)中数据个数需相同 6.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法()。 A.正确 B. 错误 7. 二叉查找树的查找效率与二叉树的((1) )有关, 在 ((2) )时其查找效率最低。 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 8.如果要求一个线性表既能较快的查找,又能适应动态变化的要求,则可采用( )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 9.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( )。 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) 10.下图所示的4棵二叉树,( )是平衡二叉树。 (A)(B)(C)(D) 11.散列表的平均查找长度()。 A.与处理冲突方法有关而与表的长度无关 B.与处理冲突方法无关而与表的长度有关 C.与处理冲突方法有关且与表的长度有关 D.与处理冲突方法无关且与表的长度无关 12. 设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79},用链地址法构造散列表,散列函数为H(key)=key MOD 13,散列地址为1的链中有()个

数据结构习题及答案 (1)

第八章查找 一、判断题 1.用二分查找法对一个顺序表进行查找,这个顺序表可以是按各键值排好序的,也可以是没有按键值排好序的。() 2.哈希表的查找不用进行关键字的比较。() 3.哈希表的定义函数H(key)=key%p(p<=m)这种方法是直接定址法。() 4.装填因子α的值越大,就越不容易发生冲突。( ) 5.选择hash函数的标准为:随机性好、均匀性好和尽量避免冲突。( ) 参考答案:1、×2、×3、×4、×5、√ 二、填空题 1.顺序查找法的平均查找长度为__________,二分查找法的平均查找长度为________,分块查找法(以顺序查找确定块)的平均查找长度为__________,分块查找法(以二分查找确定块〉的平均查找长度为_________,哈希表查找法采用链接法处理冲突时的平均查找长度为_________。 (n+1)/2;((n+1)*log2(n+1))/n-1;(s2+2s+n)/2s;log2(n/s+1)+s/2;1+α 2.在各种查找方法中,平均查找长度与结点个数n无关的查法方法是_________ 哈希表查找 3.二分查找的存储结构仅限于_________,且是__________。 顺序;有序的 4.在分块查找方法中,首先查找__________,然后再查找相应的___________。 索引;块 5.长度为255的表,采用分块查找法,每块的最佳长度是____________。 15 6.在散列函数H(key)=key%p中,p应取_______________。 小于表长的最大素数 7.假设在有序线性表A[1..20]上进行二分查找,则比较一次查找成功的结点数为 _________,则比较二次查找成功的结点数为__________,则比较三次查找成功的结点数为 _________,则比较四次查找成功的结点数为________,则比较五次查找成功的结点数为 _________,平均查找长度为_________。 ①1 ②2 ③4 ④8 ⑤5 ⑥3.7

吉林省专升本数据结构习题及答案——第八章

吉林省专升本考试数据结构分章习题及参考答案———选择题 (第八章) 1、若数据元素序列{11,12,13,78,9,23,4,5}是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法只能是( ) A、冒泡排序 B、插入排序 C、选择排序 D、归并排序 2、若将两个各有n个元素的有序表归并成一个有序表,则最少比较次数是()。 A、 n B、 2*n-1 C、 2n D、 n-1 3、已知数据表中每个元素距其最终位置不远,则采用()方法最节省时间 A、堆排序 B、插入排序 C、快速排序 D、直接选择排序 4、下列排序算法中,()算法可能会出现下面情况:在后一趟开始之前,所有元素都不在其终的位置上。 A、堆排序 B、冒泡排序 C、快速排序 D、插入排序 5、下述几种排序方法中,要求内存量最大的是()。 A、插入排序 B、快速排序 C、归并排序 D、选择排序 6、就排序算法所用的辅助空间而言,堆排序,快速排序,归并排序的关系是() A、堆排序<快速排序<归并排序 B、堆排序<归并排序<快速排序 C、堆排序>归并排序>快速排序 D、堆排序>快速排序>归并排序 7、快速排序方法在( )情况下最不利于发挥其长处。 A、要排序的数据量太大 B、要排序的数据中含有多个相同值 C、要排序的数据已基本有序 D、要排序的数据个数为奇数 8、对关键字由大到小进行冒泡排序,在下列()情况下比较的次数最多。 A、从小到大排序 B、从大到小排序 C、元素无序

D、元素基本有序 9、对5个不同的数据元素进行直接插入排序,最多需要进行()次比较。 A、 8 B、 10 C、 15 D、 25 10、如果只想得到1000个元素组成的序列中第5个小元素之前的部分排序的序列,用()方法快。 A、起泡排序 B、快速排列 C、堆排序 D、简单选择排序 11、设有1000个无序的元素,希望用最快的速度挑选出其中前十个最大的元素,在以下的排序方法中采用哪一种最好?() A、快速排序 B、归并排序 C、堆排序 D、基数排序 12、下列排序算法中,()可能会出现下面情况:在最后一趟开始之前,所有元素都不在最终位置上。 A、起泡排序 B、插入排序 C、快速排序 D、堆排序 13、对以下数据序列利用快速排序进行排序,速度最快的是() A、21,25,5,17,9,23,30 B、25,23,30,17,21,5,9 C、21,9,17,30,25,23,5 D、5,9,17,21,23,25,30 14、快速排序在下列( )情况下最易发挥其长处。 A、被排序的数据中含有多个相同排序码 B、被排序的数据已基本有序 C、被排序的数据完全无序 D、被排序的数据中的最大值和最小值相差悬殊 15、在含有n个关键字的小根堆(堆顶元素小)中,关键字最大的记录有可能存储在()位置上。 A、⎣n/2⎦ B、⎣n/2⎦-1 C、1 D、⎣n/2⎦+2 16、堆排序是()类排序. A、插入 B、交换 C、归并

吉林省高校专升本 计算机科学与技术专业综合试题及答案 数据结构

吉林省普通高校专升本教育试点考试 计算机科学与技术专业综合试卷 (数据结构部分共90分) 一、填空题(每小题2分,共26分) 1. 栈的主要特点是_先进后出_ ;队列的主要特点是__先进先出__ 。 2. 在一长度为n的向量中的第i个元素(1≤i≤n)之前插入一个元素时,需向 后移动__n-i+1__ 个元素。 3. 对于一个具有n个结点的单链表,在已知P所指结点都插入一个新结点的时 间复杂度为__O(1)__ ;在给定值为x的结点后插入一个新结点的时间复杂度为__O(n)___。 4. 设n行n列的下三角矩阵A已压缩到一维数组s[0 … n*(n+1)/2]中,若按行序 为主存储,则A[i][j]对应的s中的存储位置为__i(i-1)/2+j-1__ 。 5. 将f=1+1/2+1/3+ … +1/n转化成递归函数,其递归出口是__f(1)=1__,递归体 是__f(n)=f(n-1)+1/n___ 。 6. 设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含 的结点数至少为__2h-1__ 。 7. 具有n个叶子结点的哈夫曼树中,其结点总数为__2n-1__ 。 8. 对一个满二叉树,m个树叶,n个结点,深度为h,则n = __2h-1__ 。 9. 判定一个有向图是否存在回路,除了可以利用拓扑排序方法外,还可以利用 __深度优先遍历___ 算法。 10. 在各种查找方法中,平均查找长度与结点个数n无关的查找方法是__哈希表 查找__ 。 11. 快速排序在最坏情况下的时间复杂度为__O(n2)__ 。 12. 一组记录的排序码为(46,79,56,38,40,84),则利用堆排序方法建立 的初始堆为_(84,79,56,38,40,46)_ 。 13. 直接存取文件是用__哈希__ 方法组织的。 二、单项选择题(每小题2分,共20分) 1. 线性表的顺序存储结构是一种()的存储结构;线性表的链式存储结构是 一种()的存储结构。 A. 随机存取,顺序存取 B. 顺序存取,随机存取 C. 索引存取,散列存取 D. 散列存取,随机存取 2. 表达式a*(b+c)-d的后缀表达式为()。 A. abcd+-* B. abc+*d- C. abc*+d- D. -+*abcd 3. 在一个单链中,若P所指结点不是最后的结点,在P之后插入S所指结点, 则执行()。 A. S->next=P ; P->next = S ; B. S->next=P->next ; P->next=S; C. S->next=P->next ; P=S ; D. P->next=S ; S->next=P ; 4. 一个栈的入栈序列为1,2,…,n,其输出序列为P1,P2,…,Pn,若P1=n, 则P i为()。 A. i B. n-iI C. n-i+1 D. 不确定 5. 数组A中,每个元素A的长度为3个字节,行下标i从1到8,列下标j从1 到10,从首地址为SA开始连续存放在存储器内,该数组按行序存放时,元 1

数据结构与算法第8章答案

第8 章排序技术 课后习题讲解 1. 填空题 ⑴排序的主要目的是为了以后对已排序的数据元素进行()。 【解答】查找 【分析】对已排序的记录序列进行查找通常能提高查找效率。 ⑵对n个元素进行起泡排序,在()情况下比较的次数最少,其比较次数为()。在()情况下比较次数最多,其比较次数为()。 【解答】正序,n-1,反序,n(n-1)/2 ⑶对一组记录(54, 38, 96, 23, 15, 72, 60, 45, 83)进行直接插入排序,当把第7个记录60插入到有序表时,为寻找插入位置需比较()次。 【解答】3 【分析】当把第7个记录60插入到有序表时,该有序表中有2个记录大于60。 ⑷对一组记录(54, 38, 96, 23, 15, 72, 60, 45, 83)进行快速排序,在递归调用中使用的栈所能达到的最大深度为()。 【解答】3 ⑸对n个待排序记录序列进行快速排序,所需要的最好时间是(),最坏时间是()。 【解答】O(nlog2n),O(n2) ⑹利用简单选择排序对n个记录进行排序,最坏情况下,记录交换的次数为()。 【解答】n-1 ⑺如果要将序列(50,16,23,68,94,70,73)建成堆,只需把16与()交换。 【解答】50 ⑻对于键值序列(12,13,11,18,60,15,7,18,25,100),用筛选法建堆,必须从键值为()的结点开始。 【解答】60 【分析】60是该键值序列对应的完全二叉树中最后一个分支结点。 2. 选择题 ⑴下述排序方法中,比较次数与待排序记录的初始状态无关的是()。 A插入排序和快速排序B归并排序和快速排序 C选择排序和归并排序D插入排序和归并排序 【解答】C

数据结构(第二版) 教学课件 作者 郑泳 方风波 习题答案和源代码 第八章

数据结构(第二版) 教学课件 作者:郑泳方风波 第八章:习题答案和源代码 习题答案 1.请说明什么是图的遍历,并分别介绍深度优先遍历(DFS)和广度优先遍历(BFS)的特点。 答:图的遍历是指对图中的所有顶点进行一次且仅 一次的访问。图的遍历有两种方式:深度优先遍历(DFS)和广度优先遍历(BFS)。 –深度优先遍历(DFS):从某个顶点出发,访 问此顶点,并递归地访问此顶点的邻接顶点,直到没 有未被访问的邻接顶点。然后回溯到前一个顶点,继 续访问其他未被访问的邻接顶点,直到图中所有顶点 都被访问过为止。DFS通常使用栈来实现非递归方式。 –广度优先遍历(BFS):从某个顶点出发,先 访问此顶点,然后访问其所有邻接顶点。再逐级地访

问邻接顶点的邻接顶点,直到所有顶点都被访问过为止。BFS通常使用队列来实现。 2.请用邻接矩阵和邻接表分别实现图的数据结构,并编写相应的源代码。 –邻接矩阵实现图的数据结构: class Graph: def__init__(self, vertices): self.V = vertices self.graph = [[0] *self.V for _ i n range(self.V)] def add_edge(self, u, v): self.graph[u][v] =1 self.graph[v][u] =1 –邻接表实现图的数据结构: class Node: def__init__(self, data): self.data = data self.next =None class Graph: def__init__(self, vertices): self.V = vertices self.graph = [None] *self.V

专升本《数据结构》 试卷 答案

专升本《数据结构》试卷答案 专升本《数据结构》-试卷-答案 专升本《数据结构》 一、(共75题,共150分后) 1.数据的逻辑结构是由()部分组成的。(2分)a.2b.3c.4d.5 标准答案:a 2.算法是对某一类问题求解步骤的有限序列,并具有()个特性。(2分) a.3 b.4 c.5 d.6 标准答案:c 3.队列的入队操作是在()进行的。(2分)a.队头b.队尾c.任意位置d.指定位置 标准答案:b 4.队列的出队操作是在()进行的。(2分)a.队头b.队尾c.任意位置d.指定位置 标准答案:a 5.数组通常采用顺序存储的优点是()。(2分)a.便于增加存储空间b.便于依据下标进行随机存取c.避免数据元素的移动d.防止下标溢出 标准答案:b 6.下列给出的操作中,()是允许对队列进行的操作。(2分)a.删除队首元素b.取出最近进队的元素c.按元素大小排序d.中间插入元素 标准答案:a 7.采用带头结点的单链表存储的线性表,若表长为n,在删除第号元素时,需要移动指针()次。(2分) a.k+1 b.k c.k-1 d.k-2 标准答案:c 8.字符数组a[1..100]使用顺序存储,a[6]地址就是517,则a的首地址为()。(2分后)a.510b.512c.514d.516 标准答案:b

9.深度为n的全然二叉树最多存有()个结点。(2分后)a.2n+1b.2n-1c.2nd.2n-1 标准答案:d 10.若二叉树对应的二叉链表共计n个非空链域,则该二叉树存有()个结点的二叉树。(2分后)a.n-1b.nc.n+1d.2n 标准答案:a 11.下面描述错误的就是()。(2分后)a.借助队列可以同时实现对图的广度优先结点b.二叉树中序结点的序列就是有序c.只有一个结点的二叉树的度为0 d.空格串是指由1个或以上的空格符号组成的串 标准答案:b 12.以下与数据的存储结构无关的术语是()。(2分)a.循环队列b.链表c.哈希表 d.栈 标准答案:d 13.在一个长度为n的链式栈中入栈实现算法的时间复杂度为()。(2分) a.o(1) b.o(logn) c.o(n) d. 标准答案:a 14.在具有n个度数为2的二叉树中,必有()个叶子结点。(2分) a.n+2 b.n+1 c.n d.n-1 标准答案:b 15.在关键字序列(10,15,20,25,30)中采用折半法查找20,依次与()关键字进行了比较。(2分)a.30,20b.30,10,20c.40,20d.20 标准答案:b 16.某二叉树的前序遍历序列和和中序遍历序列分别为abc和bca,该二叉树的后序遍历序列是()。a.cbab.bcac.abcd.acb 标准答案:a 17.m个顶点的无向完全图有()个边。(2分)a.m(m-1)/2b.m(m-1)c.m2d.2m 标准答案:a 18.可以采用()这种数据结构,实现图的广度优先遍历运算。(2分)a.队列b.树c.栈d.集合

专升本《数据结构》_试卷_答案

专升本《数据结构》 一、(共75题,共150分) 1. 数据的基本单位是(). (2分) A。数据元素 B.记录 C.数据对象 D.数据项 。标准答案:A 2。()是数据的不可分割的最小单位。(2分) A.数据对象 B。数据元素 C.数据类型 D。数据项 .标准答案:D 3. 算法的空间复杂度是对算法()的度量。(2分) A。时间效率 B.空间效率 C。可读性 D.健壮性 .标准答案:B 4。()是限制了数据元素的内部结构仅为一个字符的线性表。(2分) A。栈 B.队列 C。串 D。数组 。标准答案:B 5. 串的长度是指串中所含()的个数。(2分) A.不同字符 B。不同字母 C。相同字符 D.所有字符 .标准答案:D 6. 采用带头结点双向链表存储的线性表,在删除一个元素时,需要修改指针()次。 (2分) A.1 B。2 C.3 D。4 。标准答案:B 7. 线性表的顺序存储结构是一种()的存储结构. (2分) A.顺序存取 B。随机存取 C。索引存取 D.Hash存取 。标准答案:B 8. 数组a[1。。m]采用顺序存储,a[1]和a[m]地址分别为1024和1150,每个元素占2字节,则m是(). (2分) A。64 B。32 C。16 D。8 。标准答案:A 9。深度为h的二叉树,第h层最多有()个结点。(2分) A。h B.2h—1 C.2h—1 D。2h 。标准答案:C 10。 m个结点的二叉树,其对应的二叉链表共有()个非空链域。(2分) A。m B.m+1 C.2m D.m—1 .标准答案:B 11. 下面叙述错误的是()。 (2分) A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系 B。对于空队列进行出队操作过程中发生下溢现象 C.有向图的邻接矩阵一定是对称的 D。具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的 .标准答案:C 12. 以下与数据的存储结构无关的术语是()。 (2分) A。循环队列 B。双向链表 C。哈希表 D.数组 。标准答案:D 13。在一个长度为n的链式栈中出栈实现算法的时间复杂度为()。(2分)A.O(1) B.O(log n) C。O(n) D.O(n2) 。标准答案:A 14. 在具有k个度数为2的二叉树中,必有()个叶子结点。(2分) A.k B.k—1 C。2k D。k+1 。标准答案:D 15. 在关键字序列(10,20,30,40,50)中,采用折半法查找20,关键字之间比较需要()次。 (2分) A。1 B。2 C。3 D.4 .标准答案:C 16. 16某二叉树的后序遍历序列和和中序遍历序列均为abcd,该二叉树的前序遍历序列是(). (2分) A。abcd B。dcba C。acbd D。dbca 。标准答案:B 17。 n个顶点的无向连通图的生成树,至少有()个边. (2分) A。n(n-1) B.n(n—1)/2 C.2n D.n—1 .标准答案:D 18. 可以采用()这种数据结构,实现二叉树的层次遍历运算。(2分) A.队列 B。树 C.栈 D。集合 .标准答案:A

专升本《数据结构》_试卷_答案

专升本《数据结构》 一、 (共75题,共150分) 1。数据的基本单位是(). (2分) A.数据元素 B。记录 C.数据对象 D。数据项 。标准答案:A 2. ()是数据的不可分割的最小单位. (2分) A.数据对象 B。数据元素 C.数据类型 D。数据项 。标准答案:D 3。算法的空间复杂度是对算法()的度量。(2分) A。时间效率 B.空间效率 C.可读性 D。健壮性 。标准答案:B 4。()是限制了数据元素的内部结构仅为一个字符的线性表。(2分) A.栈 B.队列 C。串 D。数组 。标准答案:B 5。串的长度是指串中所含()的个数。(2分) A。不同字符 B。不同字母 C。相同字符 D。所有字符 .标准答案:D 6。采用带头结点双向链表存储的线性表,在删除一个元素时,需要修改指针()次。(2分) A.1 B.2 C。3 D。4 .标准答案:B 7。线性表的顺序存储结构是一种()的存储结构。(2分) A。顺序存取 B。随机存取 C。索引存取 D。Hash存取 。标准答案:B 8. 数组a[1.。m]采用顺序存储,a[1]和a[m]地址分别为1024和1150,每个元素占2字节,则m是()。 (2分) A。64 B.32 C。16 D.8 .标准答案:A 9. 深度为h的二叉树,第h层最多有()个结点。(2分) A。h B.2h—1 C.2h—1 D。2h .标准答案:C 10. m个结点的二叉树,其对应的二叉链表共有()个非空链域。 (2分) A。m B。m+1 C。2m D。m—1 .标准答案:B 11。下面叙述错误的是()。 (2分) A。顺序表是借助物理单元相邻表示数据元素之间的逻辑关系 B。对于空队列进行出队操作过程中发生下溢现象 C。有向图的邻接矩阵一定是对称的 D。具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的 。标准答案:C 12. 以下与数据的存储结构无关的术语是(). (2分) A.循环队列 B。双向链表 C.哈希表 D。数组 。标准答案:D 13. 在一个长度为n的链式栈中出栈实现算法的时间复杂度为()。(2分) A。O(1) B.O(log n) C。O(n) D.O(n2) 。标准答案:A 14。在具有k个度数为2的二叉树中,必有()个叶子结点。(2分) A。k B。k-1 C。2k D.k+1 。标准答案:D 15。在关键字序列(10,20,30,40,50)中,采用折半法查找20,关键字之间比较需要()次。(2分) A.1 B.2 C。3 D。4 .标准答案:C 16。 16某二叉树的后序遍历序列和和中序遍历序列均为abcd,该二叉树的前序遍历序列是()。(2分) A。abcd B。dcba C。acbd D。dbca 。标准答案:B 17。 n个顶点的无向连通图的生成树,至少有()个边。(2分) A.n(n—1) B。n(n—1)/2 C。2n D.n-1 .标准答案:D 18。可以采用()这种数据结构,实现二叉树的层次遍历运算. (2分) A。队列 B.树 C。栈 D。集合 。标准答案:A 19。假设以数组A[0..n-1]存放循环队列的元素,其头指针front指向队头元素、尾指针rear指向队尾元素一个,则在少用一个元素空间的前提下,队列空的判定条件为()。(2分) A。rear= =front B。(front+1)%n= =rear C。rear+1= =front D。(rear+1)%n= =front .标准答案:A 20。序列(21,19,37,5,2)经冒泡排序法由小到大排序,第一趟后所得结果为()。(2分) A。(19,21,37,5,2) B。(19,21,5,2,37) C。(19,21,5,37,2) D。(19,21,2,5,37) .标准答案:B 21。二叉链表适合作为()的存储结构。(2分) A。队列 B。二叉树 C。树 D。森林 。标准答案:B,C,D 22。设哈希(Hash)函数为H(k)= k % 17,其中k为关键字,关键字()是同义词。(2分) A.44,5,15 B.28,45,62 C.6,57,125 D。201,31,48 。标准答案:B,C,D 23。下列各项键值()序列不是堆的。 (2分)

课程:数据结构(专升本)试题和答案

课程:数据结构(专升本)--试题和答案 1. (单选题) 一棵满二叉树共有64个叶子结点,则其深度为( )。(本题3.5分) A、 4 B、 6 C、7 D、8 学生答案:未答题 标准答案:C 解析: 得分: 2. (单选题) 线性表的静态链表存储结构与顺序存储结构相比,优点是( )。(本题 3.5分) A、所有的操作算法实现简单 B、便于随机存取 C、便于插入和删除 D、便于利用零散的存储器空间 学生答案:未答题 标准答案:C 解析: 得分: 3. (判断题) 在单链表中,可以从头结点开始查找任何一个结点。( )(本题3.0分)

A、正确 B、错误 学生答案:未答题 标准答案:A 解析: 得分: 4. (单选题) ( )不是算法的基本特性。(本题3.5分) A、可行性 B、长度有限 C、在规定的时间内完成 D、确定性 学生答案:未答题 标准答案:B 解析: 得分: 5. (单选题) 一个有n个顶点的有向图最多有( )条边。(本题3.5分) A、n B、n(n-1) C、n(n-1)/2 D、2n 学生答案:未答题 标准答案:B

解析: 得分: 6. (单选题) 数据的逻辑结构可以分为( )。(本题3.5分) A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、内部结构和外部结构 D、线性结构和非线性结构 学生答案:未答题 标准答案:D 解析: 得分: 7. (单选题) 某算法的时间复杂度为O(n2),表明该算法的( )。(本题3.5分) A、问题规模是n2 B、执行时间等于n2 C、执行时间与n2成正比 D、问题规模与n2成正比 学生答案:未答题 标准答案:C 解析: 得分: 8. (单选题) 线性表是具有n个( )的有限序列。(本题3.5分)

专升本《数据结构》试卷答案(精选文档)

专升本《数据结构》试卷答 案 专升本《数据结构》 一、(共75题,共150分) 1。数据的基本单位是(). (2分) A.数据元素 B.记录C.数据对象 D。数据项 。标准答案:A 2。()是数据的不可分割的最小单位。(2分) A.数据对象 B.数据元素 C.数据类型 D.数据项 .标准答案:D 3。算法的空间复杂度是对算法()的度量。(2分) A。时间效率B.空间效率 C.可读性D.健壮性 。标准答案:B 4.()是限制了数据元素的内部结构仅为一个字符的线性表。(2分) A.栈 B.队列 C.串D。数组 .标准答案:B 5。串的长度是指串中所含()的个数。 (2分)A.不同字符 B。不同字母C.相同字 符 D.所有字符 .标准答案:D 6. 采用带头结点双向链表存储的线性表,在删除 一个元素时,需要修改指针()次。(2分) A。1 B.2C。3 D.4 ...文档交流仅供参考... .标准答案:B 7.线性表的顺序存储结构是一种()的存储结 构。(2分) A。顺序存取 B.随机存取C.索引 存取D.Hash存取 。标准答案:B 8. 数组a[1。。m]采用顺序存储,a[1]和 a[m]地址分别为1024和1150,每个元素占2字 节,则m是(). (2分)...文档交流仅供参考... A.64 B。32 C.1 6 D。8 ...文档交 流仅供参考... .标准答案:A 9。深度为h的二叉树,第h层最多有()个结 点. (2分) A.h B.2h-1 C。2h-1 D.2h .标准答案:C 10. m个结点的二叉树,其对应的二叉链表共有() 个非空链域。 (2分)

数据结构专升本模拟题及参考答案汇总

、单项选择题 A. 2 B .3 C. 4 D .6 5、一 •个顺序存储线性表的第一 个兀素的存储地址是 90, 每个兀素的长度是 2,则第6个兀素的存储地址 是( )° A. 98 B . 100 C. 102 D . 106 6、判疋一个栈s (取多兀素为 m0为空的条件是( : ) ° A. s- > top! =0 B .s- > top= :=0 C. s- > top! =m0 D .s- > top= :=m0 7、 循环队列用数组 A[m](下标从0到m-1)存放其元素值,已知其头尾指针分别是 front 和rear ,则当 前队 列中的元素个数是( )。 A. (rear-front+m ) %m B . rear-front+1 C. rear-front-1 D . rear-front 8、 设有两个串S1与S2,求串S2在S1中首次出现位置的运算称作( )) A .连接 B •求子串 C.模式匹配 D .判子串 9、 设串S1='ABCDEFG ; S2='PQRST',函数con (x , y )返回x 和y 串的连接串,subs(s,i,j) 返回串S 的 的从序号i 的字符开始的j 个字符组成的子串,le n(s)返回串S 的长度,则 con (subs(S1,2,le n(S2)),subs(S1,le n(S2),2)) 的结果是( )。 作业题(一) 1. 从逻辑上可以把数据结构分为( A.动态结构、静态结构 B C.线性结构、非线性结构 D 2. 链表不具有的特点是( ) A 插入、删除不需要移动元素 C.不必事先估计存储空间 D . 3. 下面程序段的时间复杂度的量级为 For(i=1;i<=n ;i++) For(j=1;j<=l;j++) For(k=1;k<=j;k++) X=x+1; A. 0(1) B C. 0(n2) D 4. 在一个带头结点的双向循环链表中, 个指针域的值。 )两大类。 •顺序结构、链式结构 •初等结构、构造型结构 B •可随机访问任一元素 所 需空间与线性长度成正比 ( )。 .O(n) .O(n3) 若要在p 所指向的结点之前插入一个新结点, 则需要相继修改()

最全版专升本《数据结构》试题答案

[试题分类]:专升本《数据结构》_08004150 [题型]:单选 [分数]:2 个顶点的无向连通网的最小成本树,至少有()个边。 (n-1) (n-1)/2 答案:C 个顶点的连通无向图,至少有()个边。 (m-1) (m-1)/2 答案:C 3.空串的长度是()。 答案:A 4.假设以数组A[0..n-1]存放循环队列的元素,其头指针front指向队头元素、尾指针rear指向队尾元素一个,则在少用一个元素空间的前提下,队列空的判定条件为()。 A.(front+1)%n==rear B.(rear+1)%n==front +1==front ==front 答案:D 5.可以采用()这种数据结构,实现二叉树的层次遍历运算。 A.集合 B.栈 C.队列

D.树 答案:C 6.线性表的顺序存储结构是一种()的存储结构。 A.随机存取 存取 C.顺序存取 D.索引存取 答案:A 7.采用带头结点双向链表存储的线性表,在删除一个元素时,需要修改指针()次。 答案:D 8.队列的出队操作是指()操作。 A.队头删除 B.队尾删除 C.队头插入 D.队尾插入 答案:A 9.在关键字序列(10,15,20,25,30)中,采用折半法查找25,关键字之间比较需要()次。 答案:B 10.串下列关于串的叙述中,正确的是()。 个串的长度相等,则2个串相等 B.替换操作可以实现字符的删除 C.空串至少包一个空格 D.一个串的长度至少是1 答案:B

11.若二叉树对应的二叉链表共有n个非空链域,则该二叉树有()个结点的二叉树。 +1 答案:D 12.下面叙述错误的是()。 A.在无向图的邻接矩阵中每行1的个数等于对应的顶点度 B.借助于队列可以实现对二叉树的层遍历 C.对于单链表进行插入操作过程中不会发生上溢现象 D.栈的特点是先进后出 答案:C 13.算法是对某一类问题求解步骤的有限序列。其中,()是算法具有的5个特性之一。 A.可读性 B.有穷性 C.正确性 D.健壮性 答案:B 14.队列的入队操作是在()进行的。 A.任意位置 B.指定位置 C.队尾 D.队头 答案:C 15.在关键字序列(10,15,20,25,30)中采用折半法查找20,依次与()关键字进行了比较。,20 ,20 ,10,20 答案:C 16.线性表采用带头结点单链表实现,head为头指针,则判断表空的条件为()。 ==NULL >next!=NULL

吉林省数据结构专升本习题

概论 1、评价一个算法时间性能的主要标准是(算法的时间复杂度)。 2、算法的时间复杂度与问题的规模有关外,还与输入实例的(初始状态)有关。 3、一般,将算法求解问题的输入量称为(问题的规模)。 4、在选择算法时,除首先考虑正确性外,还应考虑哪三点? 答:选用的算法首先应该是"正确"的。此外,主要考虑如下三点:①执行算法所消耗的时间;②执行算法所消耗的存储空间,其中主要考虑辅助存储空间;③算法应易于理解,易于编码,易于调试等等。 6、以下四种排序方法中,不稳定的方法是( D ) A、直接插入排序 B、冒泡排序 C、归并排序 D、直接选择排序 7、按增长率由小至大的顺序排列以下各函数: 2100, (3/2)n,(2/3)n,nn ,n0.5 , n! ,2n ,lgn ,nlgn, n3/2 答:常见的时间复杂度按数量级递增排列,依次为: 常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(nk)、指数阶0(2n)。显然,时间复杂度为指数阶0(2n)的算法效率极低,当n值稍大时就无法应用。先将题中的函数分成如下几类: 常数阶:2100 对数阶:lgn K次方阶:n0.5、n3/2 指数阶(按指数由小到大排):nlgn、(3/2)n、2n、n!、nn 注意:(2/3)n由于底数小于1,所以是一个递减函数,其数量级应小于常数阶。 根据以上分析按增长率由小至大的顺序可排列如下: (2/3)n <2100 < lgn < n0.5< n3/2 < nlgn <(3/2)n < 2n < n! < nn 8、常用的存储表示方法有哪几种? 常用的存储表示方法:顺序存储方法、链接存储方法、索引存储方法、散列存储方法。 9、设有两个算法在同一机器上运行,其执行时间分别为100n2和2n,要使前者快于后者,n至少要〔15〕。 二、线性表 1、以下关于线性表的说法不正确的选项是( C )。 A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。 C、线性表中的每个结点都有且只有一个直接前趋和直接后继。 D、存在这样的线性表:表中各结点都没有直接前趋和直接后继。 2、线性表是一种典型的(线性)构造。 3、线性表的逻辑构造特征是什么? 答:对于非空的线性表:①有且仅有一个开始结点A1,没有直接前趋,有且仅有一个直接后继A2;②有且仅有一个终结结点AN,没有直接后继,有且仅有一个直接前趋AN-1; ③其余的内部结点AI〔2≤I≤N-1〕都有且仅有一个直接前趋AI-1和一个AI+1。 4、线性表的顺序存储构造是一种(随机存取)的存储构造。 5、在顺序表中,只要知道(基地址和结点大小),就可在一样时间内求出任一结点的存储地址。 6、在等概率情况下,顺序表的插入操作要挪动(一半)结点。 7、在一个长度为n的顺序表中删除第i个元素,要挪动( n-i)个元素

专升本十套-数据结构(试题及答案)

数据结构试卷(一) 一、单选题(每题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.692D.696 5.树最适合用来表示()。 A、有序数据元素B、无序数据元素 C、元素之间具有分支层次关系得数据 D、元素之间无联系得数据 6.二叉树得第k层得结点数最多为( )、 A。2k—1 B、2K+1 C、2K-1 D、 2k-1 7.若有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(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.4 10.设有6个结点得无向图,该图至少应有()条边才能确保就是一个连通图。 A、5 B、6 C、7 D、8 二、填空题(每空1分,共26分) 1.通常从四个方面评价算法得质量:_________、_________、_________与______ ___. 2.一个算法得时间复杂度为(n3+n2log2n+14n)/n2,其数量级表示为________. 3.假定一棵树得广义表表示为A(C,D(E,F,G),H(I,J)),则树中所含得结点数为__ ________个,树得深度为___________,树得度为_________。 4.后缀算式9 2 3 +— 10 2 /—得值为__________.中缀算式(3+4X)-2Y/3对应得 后缀算式为_______________________________。 5.若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子与右孩子得两个指 针。在这种存储结构中,n个结点得二叉树共有________个指针域,其中有________个指针域就是存放了地址,有________________个指针就是空指针。 6.对于一个具有n个顶点与e条边得有向图与无向图,在其对应得邻接表中,所含边结点 分别有_______个与________个。 7.AOV网就是一种___________________得图。 8.在一个具有n个顶点得无向完全图中,包含有________条边,在一个具有n个顶点得 有向完全图中,包含有________条边。

相关主题
文本预览
相关文档 最新文档