数据结构习题

1、第一章选择:1.数据结构是研究数据的（ ）以及它们之间的相互关系。 A）存储结构，物理结构 B）理想结构，抽象结构 C）物理结构，逻辑结构 D）抽象结构，逻辑结构2.在数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A）存储 B）物理 C）逻辑 D）物理与存储3.数据结构课程主要研究以下三方面的内容，它们是（ ）。 A）数据、数据元素、数据类型 B）数据元素、数据类型、算法实现 C）数据元素、数据的逻辑结构、数据的存储结构 D）数据的逻辑结构、数据的存储结构、数据的运算4.在以下的复杂度量级中，量级最低的是（）。 A）O(n) B）O(log2n) C）O(nlog2n) D）O(n2

2、)5.在下列叙述中，正确的是（）。 A）数据的逻辑结构要考虑数据元素本身的内容 B）不同类型的数据元素可以归类到同一的逻辑结构中 C）数据元素之间的关联关系在数据的逻辑结构中体现 D）数据元素是数据不可分割的最小标识单位6.计算机算法必须具备输入、输出和（）等五个特性。 A）可行性、可移植性和可扩充性 B）可行性、确定性和有穷性 C）确定性、稳定性和有穷性 D）易读性、稳定性和安全性7.算法分析的目的是（）。 A)找出数据结构的合理性 B)研究算法中的输入/输出关系 C)分析算法的易读性 D)分析算法的效率以求改进8.设n>=10，下面程序段的时间复杂度是（）。 for(i=10; i&

3、lt;n; i+) j=k=0; while(j+k<=i) if(j>k)k+; else j+; A）O（log2n） B）O(n) C）O(nlog2n) D）O(n2)9.计算机算法是指( )。 A)计算方法 B)排序方法 C)调度方法 D)解决问题的有限运算序列10.数据的定义取决于数据的逻辑结构，而数据的实现取决于数据的物理结构( )。 A)正确 B) 不正确 11.下面说法错误的是（ ） A)算法原地工作的含义是指不需要任何额外的辅助空间 B)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 C)所谓时间复杂度是指最坏情况下，估算算法执行时

4、间的一个上界 D)同一个算法，实现语言的级别越高，执行效率就越低判断：1. 数据元素是数据的最小单位。( )2. 记录是数据处理的最小单位。 ( )3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( )4. 算法的优劣与算法描述语言无关，但与所用计算机有关。( )5. 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( )6. 算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。( )7. 数据的物理结构是指数据在计算机内的实际存储形式。( ) 8. 数据结构的抽象操作的定义与具体实现有关。( )9. 数据结构的基本操作的设置的最重要的

5、准则是，实现应用程序与存储结构的独立。( ) 10. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的存储结构. ( ) 语句频度与时间复杂度1.计算机执行下面的语句时,语句s的执行次数为: (n+3)(n-2)/2。 for(i=l；i<n-l；i+) for(j=n;j>=i;j-) s; 2.下面程序段中带有下划线的语句执行次数的量级是( log2n2 ) i=n*n while (i!=1) i=i / 2;3.下面程序段中带下划线的语句的执行次数的数量级是(nlog2n )。 i=1; while( i<n) for j=1;j<=n;j+ x=x+

6、1; i=i*2； 4. 在下面的程序段中，对的赋值语句的频度为: n(n+1)(n+2)/6 O(n3) for（i= 1；i<=n; i+） for(j=1;j<=i;j+) for (k1;k<=j; k+) +1；5. 已知如下程序段,则各语句的频度为: for（i= n；i>=1; i- -） /语句1 n+1 x=x+1； /语句2 n for（j= n；j>=i;j-） /语句3 n(n+3)/2 y=y+1; /语句4 n(n+1)/2 答案：选择：1. C 2.C 3. D 4.B 5.C 6.B 7. D 8.D 9.D 10.A 11.AD判

7、断：1.× 2.× 3.× 4.× 5. 6.× 7. 8.× 9. 10.×第二章选择：1.下列有关线性表的叙述中，正确的是（ ）。 A）线性表中元素之间的关系是线性关系 B）线性表中至少有一个元素 C）线性表中的任一元素有且仅有一个直接前趋 D）线性表中的任一元素有且仅有一个直接后继2.下述哪一条是顺序存储结构的优点？（ ） A）存储密度大 B）插入方便 C）删除方便 D）可方便地用于各种逻辑结构的存储表示3.在一个长度为n的顺序表中，在第i个元素（1<=i<=n）之前插入一个新元素时需向后移动（ ）个元素。

8、 A）1 B）n-i C）n-i-1 D）n-i+14.如果某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，那么采用（ ）存储方式最节省时间。 A）顺序表 B）单链表 C）双链表 D）循环链表5.对顺序存储的线性表，设其长度为n，且在任何位置上插入或删除操作都是等概率的。则插入一个元素时平均要移动表中的（ ）个元素。 A）n/2 B）(n+1)/2 C）(n-1)/2 D）n6.下述哪一条是顺序存储结构的缺点？（ ） A）存储密度太大 B）随机存取 C）一般要估计最大的需要空间 D）只能应用于少数几种逻辑结构的存储表示7.在单链表中，增加头结点的目的是（ ）。 A）使单链表至少有一个

9、结点 B）标志表中首结点的位置 C）方便运算的实现 D）说明单链表是线性表的链式存储表示8.单链表不具有的特点是（ ）。 A)可随机访问任一元素 B)插入和删除不需要移动元素 C)不必事先估计存储空间 D)所需空间和线性表长度成正比9.循环链表的主要优点是（ ）。 A）不再需要头指针了 B）已知某个结点的位置后，能够容易找到他的直接前趋 C）在进行插入、删除运算时，能更好的保证链表不断开 D）从表中的任意结点出发都能扫描到整个链表10.链表对于数据元素的插入与删除是（ ）。 A）不需移动结点，不需改变结点指针 B）不需移动结点，只需改变结点指针 C）只需移动结点，不需改变结点指针 D）既需移动

10、结点，又需改变结点指针11.在一个单链表中,已知q所指结点是p所指结点的前驱结点,若要在q 和p所指结点之间插入s所指的结点,则执行（ ）。 A）s->next = p->next; p->next = s; B）q->next = s; s->next = p; C）p->next = s; s->next = q; D）p->next = s->next; s->next = p; 12.向一个有115个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。 A) 115 B) 114 C) 58 D) 57 1

11、3.带头结点的单链表Head为空表的判定条件是 ( ) 。 A) Head->next=Head B) Head->next=NULL C) Head!=NULL D) Head=NULL14.若要求能快速地实现在链表的末尾插入结点和删除第一个结点的运算，则选择( )最合适。 A) 单链表 B) 带尾指针的单循环链表 C) 双链表 D) 双循环链表15.给定有n个元素的向量，建立一个有序单链表的时间复杂度是( )。 A)O(n) B)O(log2n) C)O(nlog2n) D. O(n2)16.线性表采用链式存储时，其地址( )。 A)必须是连续的 B)必须是不连续的 C)连续与

12、否均可 D)部分地址必须是连续的17.在一个具有n个结点的有序单链表中，插入一个新的结点并使之仍然有序的时间复杂度是( )。 A)O(n) B)O(log2n) C)O(1) D)O(n2) 答案：1.A 2.A 3. D 4.A 5.A 6.C 7.C 8.A 9.D 10.B 11.B 12.C 13.B 14.B15.D 16.C 17.A第三章选择：1.在下列排序算法中，时间复杂度不受数据初始特性影响，恒为O(n2)的是（ ）。 A）插入排序 B）冒泡排序 C）选择排序 D）堆排序2.在各种排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序

13、序列的正确位置上的方法，称为（ ）。 A）希尔排序 B）冒泡排序 C）插入排序 D）选择排序3.快速排序方法在（）情况下最不利于发挥其长处。 A）要排序的数据量太大 B）要排序的数据含有多个相同值 C）要排序的数据已基本有序 D）要排序的数据个数为奇数4.已知10个数据元素为(54,28,16,34,73,62,95,60,26,43),对该数列按从小到大排序，经过一趟冒泡排序后的序列为（）。 A）16，28，34，54，73，62，60，26，43，95 B）28，16，34，54，62，73，60，26，43，95 C）28，16，34，54，62，60，73，26，43，95 D）16，

14、28，34，54，62，60，73，26，43，955.一组记录的关键字为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为（ ）。 A）38,40,46,56,79,84 B）40,38,46,79,56,84 C）40,38,46,56,79,84 D）40,38,46,84,56,79 6.用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,元素序列的变化情况如下: (1)20,15,21,25,47,27,68,35,84 (2)15,20,21,25,35,27,47,68,84 (3)15,

15、20,21,25,27,35,47,68,84则所采用的排序方法是（ ）。 A）选择排序 B）希尔排序 C）归并排序 D）快速排序7.在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）。 A）插入排序 B）快速排序 C）归并排序 D）选择排序8.一组记录的排序码为（20,29,11,74,35,3,8,56）,则利用堆排序方法建立的初始(小顶)堆为（ ）。 A）20,29,11,74,35,3,8,56 B）3,29,8,56,35,11,20,74 C）3,8,11,20,29,35,56,74 D）20,29,3,8,11,35,74,569.下列关键码序列中，属于堆的是（）。

16、A)（15，30，22，93，52，71） B)（15，71，30，22，93，52） C)（15，52，22，93，30，71） D)（93，30，52，22，15，71）10.若要求尽可能快地对实数数组进行稳定的排序，则应选()。 A)快速排序 B)堆排序 C)归并排序 D)基数排序11.下列排序算法的时间复杂度最小的是（）。 A)冒泡排序 B)希尔排序 C)简单选择排序 D)归并排序12.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好（ ）排序法。 A)起泡排序 B)快速排序 C)堆排序 D)基数排序13.插入排序算法在每一趟都能选取出一个元素放在其最终的位

17、置上。( ) A)正确 B)不正确 14.直接插入排序是不稳定的排序方法。( ) A)正确 B)不正确15.直接插入排序的最坏情况是初始序列为（ ）序。 A)正 B)反 C)正和反 D)无16.在各排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为( )。 A)希尔排序 B)归并排序 C)插入排序 D)选择排序答案：1.C 2.C 3. C 4.B 5.C 6.D 7.A 8.B 9.A 10.C 11.D 12.C 13.B 14.B 15.B 16.D第四章选择：1.栈的特点是( )。 A）先进先出 B）后进先出 C）进优于出 D）出优于进2.栈和

18、队列都是（）。 A）顺序存储的线性结构 B）链式存储的线性结构 C）操作受限的线性结构 D）操作受限的非线性结构3.链栈与顺序栈相比，有一个比较明显的优点是（）。 A）插入操作更加方便 B）通常不会出现栈满的情况 C）不会出现栈满的情况 D）删除操作更加方便4.一个栈的入栈序列是a,b,c,d, 则下列序列中不可能的输出序列是（ ）。 A）acbd B）dcba C）acdb D）dbac 5.设有一空栈,现有输入序列为1,2,3,4,5,经过PUSH,PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列为（ ）。 A）5,4,3,2,1 B）2,1 C）2,3 D）2,4 6.

19、下面哪种数据结构不适合作栈的存储结构（ ）。 A）数组 B）单链表 C）静态链表 D）二叉树结构7.设计一个判别表达式中左右括号是否配对出现的算法，最好采用（ ）结构。 A）线性表 B）队列 C）堆栈 D）树8.队列的操作原则是( ) 。 A）先进先出 B）先进后出 C）只能进行插入 D）只能进行删除 9. 判断一个循环队列是空队列的条件是（ ）。 A）Q.rear = Q.front B）Q.front = 0 C）Q.rear = 0 D）(Q.rear+1)%maxsize = Q.front 10.在具有n个单元顺序存储的循环队列中，队满时共有（ ）个元素。 A）n+1 B）n-1 C

20、）n D）n+211.若一个栈的输入序列是1,2,3,n,输出序列的第一个元素是n,则第i个输出元素是( )。 A) n-i B) n-i+1 C) i D) 不确定 12.判断当字符序列 x5y 作为字符堆栈的输入时，输出长度为3的且可以作为C语言标识符的个数是（ ）。 A) 3个 B) 4个 C) 5个 D) 6个 13.采用不带尾指针的单链表方式表示一个栈，便于结点的插入与删除。栈顶结点的插入与删除通常在链表的（）进行。 A)任意位置 B)链表头尾两端 C)链表头一端 D)链表尾一端14.递归函数f(n)=f(n-1)十n(n>1)的递归出口，比较合理的是（ ）。 A)f(1)=0

21、 B)f(1)=1 C)f(0)=0 D)f(n)=n 15.在一个链队列中,若Q.front、Q.rear分别为队首、队尾指针，则插入s所指结点的操作为（ ）。 A) Q.front->next=s; Q.front=s; B) Q.rear->next=s; Q.rear=s; C) s->next=Q.front; Q.rear=s; D) s->next=Q.front; Q.front=s;答案: 1.B 2.C 3.B 4.D 5.C 6.D 7.C 8.A 9.A 10.B 11.B 12.A 13.C 14. B 15.B 第五章选择;1.串是一种特殊的

22、线性表，其特殊性体现在( ) 。 A)可以顺序存储 B)可以用链表存储 C)数据元素是一个字符 D)数据元素可以是多个字符2.串是（ ）。 A）少于一个字母的序列 B）任意个字母的序列 C）不少于一个字符的序列 D）有限个字符的序列3.串的长度是（ ）。 A）串中不同字母的个数 B）串中不同字符的个数 C）串中所含字符的个数，且大于0 D）串中所含字符的个数4.设有两个串p和q,求q在p中首次出现的位置的运算( ). A）连接 B）模式匹配 C）求子串 D）求串长5.若某串的长度小于一个常数，则采用( )存储方式最为节省空间。 A)链式 B)堆结构 C)顺序6.串中任意多个连续字符组成的子序列

23、称为该串的子串( ). A)正确 B)不正确7.如果两个串含有相同的字符集，则说两者相等( ). A)正确 B)不正确 补充习题:8.存取数组中任一元素的时间都是相等的，这种存取方式为（ ）存取方式。 A）顺序 B）随机 C）线性 D）非线性 9.设一个一维数组第一个元素的存储单元的地址是100，每个元素的长度是6，则它的第5个元素的地址是（ ）。 A）130 B）105 C）106 D）12410.设n阶方阵是一个上三角矩阵，则需要存储的元素个数是（）。 A）n2/2 B）n(n+1)/2 C）n D）n211.对一些特殊矩阵采用压缩存储的目的主要是为（ ）。 A）表达变得简单 B）减少不必

24、要的存储空间的开销 C）去掉矩阵中的多余元素 D）对矩阵元素的存取变得简单 12.三元组表不包括（ ）。 A) 行数 B) 列数 C) 元素值 D) 元素总数 13.设已知一个稀疏矩阵的三元组如下：(1,2,3),(1,6,1), (3,1,5),(3,2,-1),(4,5,4),(5,1,-3),则其转置矩阵的三元组表中第3个三元组为（ ）。 A) (2,1,3) B) (3,1,5) C) (3,2,-1) D) (2,3,-1) 14.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（ ） A)正确 B)不正确15.两维数组是一种

25、非线性结构。（ ） A)正确 B)不正确16.数组A三维的长度分别为b3,b2,b1；每个数组元素占一个存储单元；LOC0，0，0为基址。若以行序为主序，则元素Aijk的地址为( )(其中0<=i<b3,0<=j<b2,0<=k<b1) A)LOC0,0,0+i*b2*b1+j*b1+k B)LOC0,0,0+i*b3*b2+j*b1+k C)LOC0,0,0+b3*i+b2*j+k D)LOC0,0,0+b3*i*j+b2*j+k 答案：1.C 2.D 3.D 4.B 5.C 6.A 7.B 8.B 9.D 10.B 11.B 12.D 13.A 14.B

26、 15.B 16.A 第六章选择;1.树最适合用来表示（ ）。 A)有序数据元素 B)无序数据元素 C)元素之间具有分支层次关系的数据 D)元素之间无联系的数据2.设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至多为( )。 A)2h-1 B)2(h-1) C)2*h-1 D)2*h3.在一棵二叉树中，第5层上的结点数最多有( )。 A)10 B)15 C)16 D)32 4.下图所示的二叉树中，( )不是完全二叉树。5.有100个结点的完全二叉树,叶子结点的个数为:( )。 A)49 B)50 C)51 D)52说明:由完全二叉树的性质知:第100个结点的父结点为

27、50，而且2*51>100,即第51个结点无左孩子,为叶子结点,故叶子结点编号为:51- -100,叶子结点数为50。6.已知某二叉树的叶子结点数为20 ,10个结点有一个左孩子,15个结点有一个右孩子，求该二叉树的总结点数？解：该二叉树叶子结点数:n0=20,度为1的结点数:n1=10+15,根据二叉树的性质3,n0=n2+1,n2=n0-1=19, 则:n=n0+n1+n2=64补充习题: 7.具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其中（ ）个指针域为空。 A）50 B）99 C）100 D）1018.首先访问结点的左子树，然后访问该结点

28、，最后访问结点的右子树，这种遍历称为（ ）。 A）前序遍历 B）后序遍历 C）中序遍历 D）层次遍历9.任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序（ ）。 A）不发生变化 B）发生变化 C）不能确定 D）以上都不对10.某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是（ ）的二叉树。 A）空或只有一个结点 B）高度等于其结点数 C）任一结点无左孩子 D）任一结点无右孩子11.如果某二叉树的先序遍历序列是abdcef，中序遍历序列是dbaefc，则其后序遍历序列是（ ）。 A）dbafec B）fecdba C）efcdba D）dbfeca 12.按照二叉树的定义，

29、具有3个结点的二叉树形态有( )种。 A）3 B）4 C）5 D）613.二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的前面（ ）。 A）正确 B）错误14.n个结点深度为h的二叉树的线索化所需的时间复杂度是( )。 A)O(1) B)O(hn) C)O(n) D)O(nlog2h)15.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是( )。 A)a是b祖先 B)a是b子孙 C)a在b左方 D)a在b右方16.关于二叉树的三种遍历，下列说法正确的是( )。 A)任意两种遍历序列都不可以唯一决定该二叉树 B)任意两种遍历序列都可以唯一决定该二叉树 C)先序遍历序列和后序

30、遍历序列可以唯一决定该二叉树 D)先序遍历序列和中序遍历序列可以唯一决定该二叉树17.在某棵二叉树的一种序列中，如果发现其中每一结点的左孩子均是其前趋，则可判断定这种序列为中序序列( )。 A)正确 B)不正确 18.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是（ ）。 A)acbed B)decab C)deabc D)cedba 19.前序遍历和中序遍历结果相同的二叉树为（ ）。 A)只有根结点的二叉树 B)所有非叶子结点只有右子树的二叉树 C)根结点无右孩子的二叉树 D)根结点无左孩子的二叉树 20.前序遍历和后序遍历结果相同的二叉树为（ ）。 A

31、)只有根结点的二叉树 B)所有非叶子结点只有右子树的二叉树 C)根结点无右孩子的二叉树 D)根结点无左孩子的二叉树 21.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树。那么以下结论中，( )是正确的。 A)树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B)树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C)树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D)以上都不对22.若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是（ ） A)根结点无右子树的二叉树 B)根结点无左

32、子树的二叉树 C)根结点可能有左二叉树和右二叉树 D)各结点只有一个儿子的二叉树 23.由分别带权为9,2,5,7的四个叶子结点构造一棵Huffman树，则该树的带权路径长度WPL为( )。 A)23 B)37 C)44 D)4624.有m个叶子结点的Huffman树所具有的结点总数为( )。 A)m+1 B)2m-1 C)2m D. 2m+125.用HUFFMAN算法求最优二叉树时,权越大的叶子离根越远( ) A)正确 B)不正确 26.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（ ）。 A)n/2 B)n C)(n+1)/2 D)n+1 27.分别以下列序列构造二叉排序

33、树，则与其它几个序列构造的结果不同的是（ ） A)（80，70，60，75，90，85，100，10） B)（80，90，85，70，60，10，75，100） C)（80，90，70，85，10，60，75，100） D)（80，90，100，70，85，60，10，75）28.若以二叉树的任一结点出发到根的路径上所经过的序列按其关键字有序,则该二叉树是( )。 A）二叉排序树 B）赫夫曼树 C）堆 D）线索二叉树 答案: 1.C 2.A 3.C 4.C 5. B 7.说明:已知:n=n0+n1+n2,指针域为空个数:2*n0+n1=n0+n1+n2+1, 即n+1. D 8.C 9.A 1

34、0.B 11.D 12.C 13.B 14.C 15.C 16.D 17.B 18.D 19.B 20.A 21.A 22.C 23.C 24.B 25.B 26.B 27.C 28.C 29.B 30.C 第七章选择：1.在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A) 1/2 B) 1 C) 2 D) 42.具有5个顶点的有向完全图有( )条弧。 A) 10 B) 16 C) 20 D) 253.一个有10个顶点,6条边的无向图,该图是否连通( )。 A) 能 B) 不能4.在任一有向图中，所有顶点的入度之和一定等于所有顶点的出度之和( )。 A) 正确 B) 不正确5.图的深度优先遍历类似于二叉树的（ ）。 A）先序遍历 B）中序遍历 C）后序遍历 D）层次遍历6.在用邻接表表示图时,深度优先遍历算法的时间复杂度为（） A)O（n） B)O（n+e） C)O（n2） D)O（n3）7.如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（） A)G肯定不是完全图 B)G一定不是连通图 C)G中一定有回路 D)G有2个连通分量9.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点( )。 A)正确 B)不正确10.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示，则表头向